[Zamknięte] Real w Czechach.

How Pseudo-Random Number Generators Work

Suppose we want to generate a random number between 1 and 52, where every number has an equal probability of appearing. Ideally, we would generate a value on the range from 0 to 1 where every value will occur with equal probability, regardless of the previous value, then multiply that value by 52. Note that there are an infinite number of values between 0 and 1. Also note that computers do not offer infinite precision!

In order to program a computer to do something like the algorithm presented above, a pseudo-random number generator typically produces an integer on the range from 0 to N and returns that number divided by N. The resulting number is always between 0 and 1. Subsequent calls to the generator take the integer result from the first run and pass it through a function to produce a new integer between 0 and N, then return the new integer divided by N. This means the number of unique values returned by any pseudo-random number generator is limited by number of integers between 0 and N. In most common random number generators, N is 2^32 (approximately 4 billion) which is the largest value that will fit into a 32-bit number. Put another way, there are at most 4 billion possible values produced by this sort of number generator. To tip our hand a bit, this 4 billion number is not all that large.

A number known as the seed is provided to a pseudo-random generator as an initial integer to pass through the function. The seed is used to get the ball rolling. Notice that there is nothing unpredictable about the output of a pseudo-random generator. Each value returned by a pseudo-random number generator is completely determined by the previous value it returned (and ultimately, the seed that started it all). If we know the integer used to compute any one value then we know every subsequent value returned from the generator.

Developing a card-shuffling algorithm is a fairly straightforward task. The first thing to realize is that an algorithm capable of producing each of the 52! shuffles is not really required. The reasoning underlying this claim is that only an infinitesimally small percent of the 52! shuffles will ever be used during play. It is important, however, that the shuffles the algorithm produces maintain an even distribution of cards. A good distribution ensures that each position in the shuffle has an approximately equal chance of holding any one particular card. The distribution requirement is relatively easy to achieve and verify. The following pseudo-code gives a simple card-shuffling algorithm that, when paired with the right random number generator, produces decks of cards with an even distribution.

START WITH FRESH DECK
GET RANDOM SEED
FOR CT = 1, WHILE CT <= 52, DO
X = RANDOM NUMBER BETWEEN CT AND 52 INCLUSIVE
SWAP DECK[CT] WITH DECK[X]

Key to the success of our algorithm is the choice of a random number generator (RNG). The RNG has a direct impact on whether the algorithm above will successfully produce decks of even distribution as well as whether these decks will be useful for secure online card play. To begin with, the RNG itself must produce an even distribution of random numbers. Pseudo-random number generators (PRNG), such as those based on the Lehmer algorithm, have been shown to possess this mathematical property. It is therefore sufficient to use a good PRNG to produce "random" numbers for card shuffling.

Przykładowy prosty algorytm:
procedure TDeck.Shuffle;
var
ctr: Byte;
tmp: Byte;

random_number: Byte;
begin
{ Fill the deck with unique cards }
for ctr := 1 to 52 do
Card[ctr] := ctr;

{ Generate a new seed based on the system clock }
randomize;

{ Randomly rearrange each card }
for ctr := 1 to 52 do begin
random_number := random(51)+1;
tmp := card[random_number];
card[random_number] := card[ctr];
card[ctr] := tmp;
end;

CurrentCard := 1;
JustShuffled := True;
end;

We understand that a use of a fair and unpredictable shuffle algorithm is critical to our software. To ensure this and avoid major problems, we are using two independent sources of truly random data:
user input, including summary of mouse movements and events timing, collected from client software
Quantis , a true hardware random number generator developed by Swiss-based company ID Quantique, which uses quantum randomness as an entropy source
Each of these sources itself generates enough entropy to ensure a fair and unpredictable shuffle.
Shuffle Highlights:
A deck of 52 cards can be shuffled in 52! ways. 52! is about 2^225 (to be precise, 80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000,000,000,000,000, 000,000,000 ways). We use 249 random bits from both entropy sources (user input and quantum randomness) to achieve an even and unpredictable statistical distribution.
Furthermore, we apply conservative rules to enforce the required degree of randomness; for instance, if user input does not generate required amount of entropy, we do not start the next hand until we obtain the required amount of entropy from the Quantis RNG.
We use the SHA-1 cryptographic hash algorithm to mix the entropy gathered from both sources to provide an extra level of security
We also maintain a SHA-1-based pseudo-random generator to provide even more security and protection from user data attacks
To convert random bit stream to random numbers within a required range without bias, we use a simple and reliable algorithm. For example, if we need a random number in the range 0-25:
we take 5 random bits and convert them to a random number 0-31
if this number is greater than 25 we just discard all 5 bits and repeat the process
This method is not affected by biases related to modulus operation for generation of random numbers that are not 2n, n = 1,2,..
To perform an actual shuffle, we use another simple and reliable algorithm:
first we draw a random card from the original deck (1 of 52) and place it in a new deck - now original deck contains 51 cards and the new deck contains 1 card
then we draw another random card from the original deck (1 of 51) and place it on top of the new deck - now original deck contains 50 cards and the new deck contains 2 cards
we repeat the process until all cards have moved from the original deck to the new deck
This algorithm does not suffer from "Bad Distribution Of Shuffles"

PokerStars submitted extensive information about the PokerStars random number generator (RNG) to an independent organization. We asked this trusted resource to perform an in-depth analysis of the randomness of the output of the RNG, and its implementation in the shuffling of the cards on PokerStars. Information about the results can be seen below.

Cigital, the largest consulting firm specializing in software security and quality, has confirmed the reliability and security of the random number generator (RNG) that PokerStars uses to shuffle cards on its online poker site, showing the solution meets or exceeds best practices in generating unpredictable and statistically random values for dealing cards.
“Truly random numbers are the heart of fair online gaming,” said Paco Hope, Manager of Cigital’s Gaming Services. “Our assessment looked at the entire solution, including the hardware and the software, and confirmed that the output of the RNG is cryptographically random and truly unpredictable.” Given the results of this examination Cigital believes that online players should have full confidence that each hand is randomly dealt and the cards being dealt cannot be predicted in advance.
Cigital analyzed the source code, entropy sources and documentation for PokerStars' RNG implementation. In addition, a sample RNG output stream provided by PokerStars was subjected to—and passed—FIPS 140-2 style testing. Using standard methods for exploiting RNGs and having full access to the source code, Cigital found no weaknesses in the PokerStars RNG, concluding that the implementation adheres to the current state-of-the-practice in generating random seed values.
"Cigital's reputation for excellence is well known in the gaming industry," said a PokerStars spokesperson. "Their previous discovery of critical RNG implementation weakness at a major online poker site made our decision to work with Cigital an easy one. Their considerable technical expertise and thorough approach to software reliability and security have established them as a trusted third-party evaluator."
"Building software that can properly generate reliable random numbers is non-trivial, but it is an absolute requirement in the gaming industry," said Dr. Gary McGraw, Chief Technology Officer at Cigital and author of the book Exploiting Online Games. "We are pleased to provide extensive expert analysis of the PokerStars random number generator and act as a trusted advisor. Our analysis shows conclusively that the PokerStars RNG used to generate the poker hands dealt on PokerStars makes proper use of statistically random sequences. A safe and fair gaming environment is an important part of any online gaming experience, and PokerStars meets those criteria."
About Cigital
Cigital, Inc. is the leading software security and quality consulting firm in the world. Established in 1992, Cigital plans and implements initiatives that help organizations ensure their applications are secure and reliable while also improving how they build and deploy software. Their recognized experts apply a combination of proven methodologies, tools, and best practices to meet each client's unique requirements. Cigital is headquartered outside Washington, D.C. with regional offices in the U.S., Europe, and India. For more information visit www.cigital.com.