Pseudo Random Number

Related to Internet and Network Security

1. ACTIVE LEARNING ASSIGNMENT FOR THE SUBJECT “Information & network security” Pseudo Random Number Guided By : - Prof. G. J. Sahani Prepared By :- Hemant H. Chetwani (130410107010 LY CE-II)

2. Random Number ??? A random number is a number that is selected from a infinite set or finite range, in which each number in the range is equally likely to be selected.

3. Pseudo Random Number True random numbers can only be generated by observations of random physical events, like dice throws. But when it comes to the computer program or computational machine which has to generate a random number, than at the back there always will be some mathematical process or a function or a particular algorithm procedure which will produce a random number. So, ultimately here random numbers are not actually random as it follows some sequence and hence it is known as “PSEUDO RANDOM NUMBER”.

4. Applications of Random Numbers Cryptography, games, and many statistical models rely on random numbers. Example from cryptography – keys for encryption of data. Example from games – the behavior of a computer-controlled character. Example from statistics - the Monte Carlo method.

5. Random Numbers in Cryptography The secret key in the DES encryption. The prime numbers p, q in the RSA encryption. The private key in DSA. The initialization vectors (IVs) used in ciphers. The keystream in the one-time pad.

6. Pseudo-random Number Generator Pseudo-random number generator : A polynomial-time computable function f (x) that generates a random number x that appears random. Not truly random in that : Deterministic algorithm Dependent on initial values Objectives Fast Secure

7. Pseudorandom Number Generators Different PRNG’s approximate different properties of random numbers, and desirable properties vary with application. Therefore, different PRNG’s are suitable for different applications. For example, a generator that produces unpredictable but not uniformly distributed number sequences may be useful in cryptography but not in the Monte Carlo method.

8. PRNGs Middle Square Method. (Simple) Linear Congruential Method. (Crypto graphical) Mersenne Twister Method ( Statstical )

9. Middle-Square Method - History The middle-square method was first suggested by John von Neumann in 1946 for use in models of neutron collisions in nuclear reactions. The method was flawed, but it was simple and fast enough to be implemented using an ENIAC computer. John von Neumann

10. Middle-Square Method Begin with an n-digit seed number x 0. Square it to obtain a 2n-digit number, adding a leading zero if necessary. Take the middle n digits as the next random number. Repeat. Numbers generated can be scaled to any interval by multiplication and/or addition.

11. Middle-Square Method - Example Let’s generate four-digit numbers starting with the seed 2041. Square the seed and a leading zero to obtain 04165681. Take the middle four digits, 1656 as the next random number. Repeat to get the following sequence: 2041,1656, 7423, 1009, 180, 324, 1049, 1004, 80, 64, 40,16, 2, 0, 0, 0, 0, 0…

12. Middle-Square Method - Flaw This sequence illustrates a serious flaw in the middle-square method; it tends to degenerate to zero. Here, just we have to take care is choosing of a appropriate seed.

13. Linear Congruence Method Due to its tendency to quickly degenerate to zero and/or repeat, the middle-square method is not a very practical algorithm. The linear congruence method provides more reliable results. Derrick H. Lehmer developed this method in 1951. Since then, it has become one of the most commonly used PRNG’s. Derrick H. Lehmer

14. Linear Congruence Method The method uses the following formula: X n+1 = (a * X n + b) mod c given seed value X and integer values of a, b, and c. (“y mod z” means the remainder of the division of y by z.)

15. Linear Congruence Method – Example Let a = 1, b = 7, c = 10, and X = 7. X 1 = (1 * 7 + 7) mod (10) = 4 Repeat to get the following sequence: 7, 4, 1, 8, 5, 2, 9, 6, 3, 0, 7, 4, 1, 8, 5, 2, 9… { Note that the sequence cycles after every ten terms. Pseudorandom numbers always cycle eventually. }

16. Linear Congruence Method – Choosing Parameters X n+1 = (a * X n + b) mod c. The period (number of terms in a cycle) depends on the choice of parameters . a, b, c and X can be chosen such that the generator has a full period of c. Large values of c ensure long cycles.

17. Linear Congruence Method - Flaws The cycles of linear congruential generators may be too short for some applications. Issues arise from the easily detectable statistical interdependence of the members of sequences generated with this method. For example, it makes the method unsuitable for cryptography. The correlation of members of the sequences results in the uneven distribution of points generated in greater than 2 dimensions. Ordered triples of numbers generated by the algorithm lie on a finite number of planes.

18. Recent PRNG’s – Mersenne Twister The Mersenne Twister is now often used in place of the linear congruential generator. The Mersenne Twister was developed by mathematicians Makoto Matsumoto and Takuji Nishimura in 1997. The generator runs faster than all but least statistically sound PRNG’s. It is distributed uniformly in 623 dimensions. The generator passes numerous tests for randomness.

19. Mersenne Twister The Mersenne Twister gets its name from its huge period of 2^19937-1. This number is a Mersenne prime. It would probably take longer to cycle than the entire future existence of humanity (and, perhaps, the universe.) Observing enough numbers generated by the Mersenne Twister allows all future numbers to be predicted. The Mersenne Twister is, therefore, not suitable in cryptography. This illustrates the fact that no single PRNG is the best choice for all applications.

20. Summary PRNG’s are algorithms that produce sequences of numbers that simulate randomness. PRNG’s are useful in game design, cryptography, and statistical modeling. Different PRNG’s are suitable for different applications. It is important to choose a good set of parameters for a PRNG. The middle-square method uses the middle digits of the square of the n th term to generate the (n+1) th term. The linear congruence method is defined by the recursive formula X n+1 = (a * X n + b) mod c . Mersenne Twister is powerful statistical PRNG.