Re: Upper limit?

On Fri, 04 Jul 2008 20:46:13 -0700
Allen <netsecurity@sound-by-design.com> wrote:

> Is there an upper limit on the number of RSA Public/Private 1024 bit
> key pairs possible? If so what is the relationship of the number of
> 1024 bit to the number of 2048 and 4096 bit key pairs?
>
There are limits, but they're not particularly important.

I'll oversimplify. Roughly speaking, a 1024-bit RSA public key is the
product of two 512-bit primes. According to the Prime Number Theorem,
the number of primes < n is approximately n/log(n). Actually, what we
need is the number of primes >2^511 and <2^512, but that correction
doesn't make much differences -- work through the math yourself to see
that. Call the number of such primes P.

Now, we need two such primes. There are therefore P^2 pairs, more than
2^1000. The numbers are very much larger for 2048- and 4096-bit keys,
but I'll leave those as an exercise for the reader.

--Steve Bellovin, http://www.cs.columbia.edu/~smb

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com