[Courses] [security] Crypto Scientists Crack Prime Problem

[Jacinta Richardson]

> > PS: Lots of the text of this email was pulled out of a computer science
> > essay I had to write last year.  I can provide code or algorithms for all
> > theories and am happy to provide such for generating RSA strong primes if
> > anyone wants them.

> Phew! You must be a maths genius.

Not at all.  A basic course in number theory and a basic course in
cryptography and that's it.  Once you've got the basics down (as Raven
discussed them) nothing in what I said should be too scarey.

> Now my mind brings up more questions. Esentially the keys are just
> large, very large, prime numbers, right? Then couldn't it be ,
> coincidentally, that someone else out there is using a the same number
> that is my key? It is probable , right? 

It's _possible_ but I'm not sure how probable.  Let's look at the numbers.
If we consider all primes between 10^200 and 10^201 (for example) 
that's
9000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
different values (good key size numbers) then the number of primes in that
range can be determined by the Prime Number Theorem.

The Prime number theorem states that the number of primes less than 'n' is
approximately n/log_10(n+1).  So the number of primes between 10^200 and
10^201 is the number less than 10^201 - the number less than 10^200, or
there abouts.

Prime Numbers less than 10^201 =~ 2.1*10^198
Prime Numbers less than 10^200 =~ 2.1*10^197

so we expect there to be about 1.9*10^198 prime numbers in this range.
That's about
1900000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000 

primes.  Now not all of these will fit the criteria I outlined in my
previous post, but I'm not sure about how many that'll eliminate.  Even if
we disregard three quarters of these primes we still have 1.425 * 10^198
primes remaining:
1425000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000.

This doesn't of course, take into account using even larger (or of course
smaller) key sizes.  For example the range 10^201 - 10^202 gives us even
more primes.

I think the chances of someone randomly picking the exact same two primes
out of this pool as you have is extremely low.  With one exception.  If
both of you have extremely poor sources of randomness (perhaps using a
simple pseudo-random generator) then the chances of you having the same
primes and key are of course much much much higher.
But you wouldn't have done something silly like that, surely?

	Jacinta


--
   ("`-''-/").___..--''"`-._          |  Jacinta Richardson	    |
    `6_ 6  )   `-.  (     ).`-.__.`)  |  Perl Training Australia    |
    (_Y_.)'  ._   )  `._ `. ``-..-'   |      +613 9354 6001 	    |  
  _..`--'_..-_/  /--'_.' ,'           | contact at perltraining.com.au |
(il),-''  (li),'  ((!.-'              |   www.perltraining.com.au   |