13 Random Number Generation

Hiteishi Diwanji

epgp books

Blum Blum Shub Generator(Cryptographically secure psuedorandom bit generator):

 

¨  based on public key algorithms

¨  use least significant bit from iterative equation xi = xi-12 mod n

¨   where n=p.q, and primes p≡q≡3 mod 4

¨   unpredictable, passes next-bit test

¨   security rests on difficulty of factoring n

¨   is unpredictable given any run of bits

¨   slow, since very large numbers must be used

¨   too slow to use for cipher use, good for key generation

 

Example Blum Blum Shub Generator:

 

¨  n=192649=383×503

¨   Seed s=101355

 

i Xi Bi
0 20749
1 1
143135
2 177671 1
3 97048 0

 

 

Fermat’s Theorem

¨ ap-1 = 1 (mod p)

  • ¨ where p is prime and gcd(a,p)=1
  • ¨ also ap = p (mod p)
  • ¨ useful in public key and primality testing

Euler’s Theorem:

  • ¨ a generalisation of Fermat’s Theorem aø(n) = 1 (mod n)
  • ¨ for any a,n where gcd(a,n)=1
  • ¤ a=3;n=10; ø(10)=4;

hence 34 = 81 = 1 mod 10

  • ¤ a=2;n=11; ø(11)=10;

hence 210 = 1024 = 1 mod 11

 

Primality Testing:

  • ¨ divide by all numbers (primes) in turn less than the square root of the number
  • ¨ only works for small numbers
  • ¨ alternatively can use statistical primality tests based on properties of primes
  • 1) for which all primes numbers satisfy property.
  • 2) some composite numbers, also satisfy the property.

Miller Rabin Algorithm- a test based on Fermat’s Theorem:

  • ¨ algorithm is:
  1. 1.¤ TEST (n) is:
  2. Find integers k, q, k > 0, q odd, so that (n–1)=2kq
  3. Select a random integer a, 1<a<n–1
  4. if aq mod n = 1 then return (“maybe prime”);
  5. for j = 0 to k – 1 do
  6. if (a2jq mod n = n-1)

then return(” maybe prime “)

  1. return (“composite”)

Applying Miller Rabin Algorithm:

  • ¨ n=29
  • ¨ n-1=28=22×7=2kqa=10
  • ¨ 107 mod 29=17 neither 1 nor 28.
  • ¨ (107)2 mod 29=28
  • ¨ Returns inconclusive(29 may be prime) Try again a=2
  • ¨ 27 mod 29=12 neither 1 nor 28.
  • ¨ 214 mod 29=28
  • ¨ Returns inconclusive(29 may be prime)
you can view video on Random Number Generation

Suggested Reading:

 

  1. Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
  2. Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
  3. Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
  4. The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
  5. Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
  6. Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
  7. www.snort.org
  8. https://nmap.org