Upper limit?

[Steven M. Bellovin]

On Fri, 04 Jul 2008 20:46:13 -0700
Allen <netsecurity at 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 at metzdowd.com