[Courses] [security] Crypto Scientists Crack Prime Problem

[Sujita Purushothaman]

Jacinta Richardson wrote:

> > 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?

Put that way, yes , it is _possible_ but highly unlikely that two people end up
with the same number. hmm.... what are the general sources of randomness
people use to issue key pairs?

-Sujita