[Courses] [security] Crypto Scientists Crack Prime Problem
sujita at mimos.my
Wed Aug 14 16:00:49 EST 2002
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)
> 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
> 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:
> 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?
More information about the Courses