[127467] in cryptography@c2.net mail archive
Re: Upper limit?
daemon@ATHENA.MIT.EDU (Steven M. Bellovin)
Sat Jul 5 14:21:19 2008
Date: Sat, 5 Jul 2008 14:02:24 -0400
From: "Steven M. Bellovin" <smb@cs.columbia.edu>
To: Allen <netsecurity@sound-by-design.com>
Cc: Cryptography <cryptography@metzdowd.com>
In-Reply-To: <486EEE85.8060001@sound-by-design.com>
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
