How is computer randomization generated?

155

Questions

  • How is computer randomization done?
  • Which algorithm or mathematical basis the computer uses to generate these numbers?
  • For example:

    In JavaScript I use Math.random() it me returns different numbers every time as for example: 0.8908976025413722, 0.7090631313621998 and etc.

        
    asked by Silvio Andorinha 12.03.2014 в 14:48
    source

    6 answers

    159

    The only really random thing is quantum effects, like radioactive decay (which nucleus is going to break now?). And that's kind of tricky to get on home computers.

    Several of these algorithms (in particular the rand() of C, which many languages use) are based on pseudo-random generators. They generate a sequence of numbers that seems random to a person, but are totally predictable if they start from a known seed. They are, therefore, bad for security or encryption. They take a seed (initial value given, usually starting from an external source, such as the process start date / time) and apply transformations to generate the next value. The advantage is that they are fast. And the fact that they are predictable allows you to save the seed of a puzzle generated as your id, for example, and do not have to spend any space with the puzzle itself, just regenerate the same seed.

    For example: (I just invented this algorithm, not good)

    static double seed; // uma seed entre 0 e 1
    double random() {
       seed /= 1125899839733759;  // um número primo
       seed *= 18014398241046527; // outro
       seed -= (int)seed;         // normalizar
       return seed;
    }
    
    int main() {
        seed = 0.753;
        printf("%f\n", random()); // 0.048001
        printf("%f\n", random()); // 0.768009
        printf("%f\n", random()); // 0.288139
        printf("%f\n", random()); // 0.610224
        printf("%f\n", random()); // 0.763582
    }
    

    (coliru)

    One of the most widely used algorithms for this is Mersenne Twister , which is able to generate 2 19937 -1 numbers before repeating the sequence.

    In any case, it is important to take care in choosing the seed. If an attacker gains knowledge of the seed used by you, he can predict all movements of the program. An example of such an attack on an online poker site can be found in this article: How We Learned to Cheat at Online Poker : A Study in Software Security . The attack begins with the knowledge that the Randomize() function of Pascal is used and that it uses as seed the number of milliseconds since midnight. The problem is that I can kick the exact time the randomization on the server happened (ie the time poker started). Considering that you miss 1 minute for more or less, there are only 180,000 possible sequences. An extremely small number for a computer, just test all possible sequences and compare which generates the cards I have at hand. The moment you find out what the sequence is, you can extrapolate and know the cards in the hand of all players. Knowledge learned: Using only the clock as the source of a seed that should be random and hidden is a bad idea.

    Other methods rely on sources of entropy that can be obtained from the hardware, such as keyboard usage analysis, mouse movement, packet traffic on the network, etc. Having enough data this will be as close to random as possible. On Linux you can read from this source through pseudo-files /dev/random or /dev/urandom . They are a good source if you need real random numbers and can be used to initialize the seed of a pseudo-random generator, if convenient.

        
    answered by 12.03.2014 / 15:08
    source
    60

    Most pseudorandom number generators (PRNG) work as follows (LC algorithm):

     x1 = (a . x0 + b) mod n
    

    where x0 is the "seed", or previous random number, a and b are constants chosen, and n is the largest random number desired. Remembering that mod is the remainder operation of the division.

    This is used with integers, Javascript probably generates an integer of 64 bits or greater and divides by a constant before returning via Math.random() , since in this function the number comes between 0 and 1.

    The quality of this PRNG depends on the good choice of a and b . To see which constants and / or the exact implementation the way is to consult the source of the Javascript implementation in which you are interested, if it is open source (V8 / Node is, Mozilla is, others not). >

    There are more modern PRNGs than the LC. Mersenne Twister is widely used and recommended. As Javascript's Math.random () can not be "seeded", it can make use of any PRNG, so just refer to the source to see what it is.

        
    answered by 12.03.2014 в 15:05
    48

    Randomness is related to the concept of unpredictability : Given a number (or sequence of numbers) you are unable to predict what the next number will be. In addition, other requirements may be present, such as the probability of each number within the domain being drawn (which, in general, should be the same).

    Computers are usually deterministic , that is: the same program run twice with all identical inputs will produce two identical outputs. For this reason, an external source is required to produce really random results. This is not something that the computer can produce on its own.

    As such a source is rarely present, several algorithms are designed to produce sequences of numbers that are - to a certain degree - indistinguishable from a random sequence, from a single starting value (seed, or seed ). This starting value must be different for each invocation of the program, but does not necessarily have to be random, so a much-used source is the system clock. Algorithms of this type are called Pseudo-Random Number Generators (PRNG) .

    Some applications, such as cryptography, require the generated sequences to be really unpredictable without the knowledge of the external source (s). An ordinary PRNG may have its seed "guessed" after observing a finite (and computationally speaking, not very large) number of previously generated numbers. This is not a problem in domains such as simulations (since the sequence seems random), but when the security of a system and / or the confidentiality of a communication depends on that randomness, a more sophisticated algorithm does require (a CSPRNG - PRNG Cryptographically Secure).

    One way to do this is to generate a sequence of pseudorandom numbers using a secret key as a seed. This is done through a simple counter (zero, one, two ...) where each element is encrypted or hashed with the help of this key. This is even the way most stream cipher ) work, as most of the stream cipher : generate a random sequence of bytes, and combine this string with the data using XOR.

    When a secret seed is not available, all that remains is to resort to other external sources, as mentioned earlier. Several computer events can be considered "unpredictable", such as: a) the keys entered by the user or the movement of the mouse; b) the date of creation of the various files (or even their contents); c) historical CPU usage data; etc. Not always the entropy (disorder, unpredictability) of these events is sufficient, but their combination with a PRNG can greatly increase the quality of it. As mentioned in another answer , the generator numbers by a common PRNG start repeating after a certain period. If it is combined with data from external sources (#

    / p>

    Finally, if none of this is enough, all that remains is the use of hardware modules (probably involving quantum mechanics) or data from external systems. The random.org site, for example, generates a sequence of random numbers based on atmospheric information ( atmospheric noise ) - that are so unpredictable with current technology that they can be considered "really random". Of course, you should not use them for confidential operations (such as the generation of passwords and keys) as they come from third parties, but for scientific applications or perhaps sweepstakes games, they can be a good alternative.

        
    answered by 24.03.2014 в 21:37
    45

    Randomization done by Math.random() returns a positive value (greater than or equal to 0) of type Number , but less than 1, it is randomly or pseudo randomly chosen with a uniform distribution approximately over this range, using a strategy, or implementation-dependent algorithm.

    Here is the implementation of it in the Engine V8 used by Chrome to run Javascript:

    uint32_t V8::Random() {
    
        // Gerador de Número aleatório utilizando o algoritmo MWC de George Marsaglia.
        static uint32_t hi = 0;
        static uint32_t lo = 0;
    
        // Inicialize a descendência utilizando o  system random(). Se uma das
        // descendências nunca deve tornar-se a zero novamente, ou se random() retorna zero
        // nós evitamos ficar presos com zero bits no hi ou no lo, reinicializando eles na demanda.
        if (hi == 0) hi = random();
        if (lo == 0) lo = random();
    
        // Misturar os bits.
        hi = 36969 * (hi & 0xFFFF) + (hi >> 16);
        lo = 18273 * (lo & 0xFFFF) + (lo >> 16);
        return (hi << 16) + (lo & 0xFFFF);
    }
    

    References:

    Base (Source):

      

    link

    Original Response in Stack Overflow (EN)

    And also, here are some related questions in Stack Overflow (EN):

    answered by 12.03.2014 в 15:10
    38

    The answer is based on the concepts of "seed", and "pseudorandom number generators".

    Why "pseudo"? Because the random numbers that are appearing in your call to Math.random() are actually "almost" random, since they are based on a "seed." This seed is a "basis" for generating a group of numbers that seem random.

    In general, it is based on the current date / time because it is basically a number that never repeats, and because there is a strong element of randomness in small intervals (like milliseconds).

    There are also other generation techniques, such as keystrokes by the user on the keyboard, etc.

        
    answered by 12.03.2014 в 15:04
    33
    One of the most commonly used algorithms in pseudo-random numbers by computers is the GCL, also considered one of the simplest is the so-called linear congruent generator (GCL), presented by DH Lehmer in 1949: consider integers m, a, c, such that m > 0, 0 ≤ a < m, 0 ≤ a < m e 0 ≤ s < m. Putting x0 = s, define recursively for each integer n ≥ 0:

    xn + 1 = (a xn + c) mod m
    

    That is, xn + 1 is the remainder of the division of a xn + c by m. For example, if m = 10, a = 11, c = 3 and x0 = s = 3, then a x0 + c = 36. Since the remainder of the division of 36 by 10 is 6, it follows that x1 = 6. Thus x1 + c = 69. Since the remainder of the division of 69 by 10 is 9, it follows that x2 = 9. Continuing with this scheme, from the number x0 = 3, we generate the numbers x1 = 6, x2 = 9, x3 = 2, x4 = 5, x5 = 8, x6 = 1, x7 = 4, x8 = 8, x9 = 0, x10 = 3. Note that after x10, the sequence of generated numbers repeats (with period 10).

      

    response based on:    link

        
    answered by 12.03.2014 в 15:12