RSA key size and safety
in [Cryptography]
|
From: Andrew Haley on 7 Sep 2009 12:39 biject <biject.bwts(a)gmail.com> wrote: > On Aug 26, 8:48?am, pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > On Aug 26, 10:41?am, George Orwell <nob...(a)mixmaster.it> wrote: > > > > >http://www.keylength.com/ > > > > > Has anyone seen these numbers? They're calculations for the estimated > > > safety period for different encryption algorithms. > > > > > What strikes me is that most of these predict that 4096 bits > > > assymmetric (RSA) will be safe for the next 50 years (or thereabouts). > > > However, the NIST recommends 7680 (for decades?) and even 15360 bits > > > for RSA (for centuries?). > > > > > Any one want to guess what their drift is? > > > > I have no idea. ?Noone can predict that far out. > I have been watching ever since RSA came out. It was not that long > ago when it was considered that keys of a 1000 bits would last longer > than till the sun burned out. In 1991, [1] said "For most applications a modulus size of 1024 bits should achieve a sufficient level of security for "tactical" secrets for the next ten years. This is for long term secrecy purposes; for short term authenticity purposes 512 bits might suffice in this century." Andrew. [1] Th. Beth, M. Frisch and G. Simmons, Public Key Cryptography: State of the Art and Future Directions, LNCS 578, SpringerVerlag,1992
From: Tom St Denis on 7 Sep 2009 13:05 On Sep 7, 12:39 pm, Andrew Haley <andre...(a)littlepinkcloud.invalid> wrote: > biject <biject.b...(a)gmail.com> wrote: > > On Aug 26, 8:48?am, pubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > On Aug 26, 10:41?am, George Orwell <nob...(a)mixmaster.it> wrote: > > > > >http://www.keylength.com/ > > > > > Has anyone seen these numbers? They're calculations for the estimated > > > > safety period for different encryption algorithms. > > > > > What strikes me is that most of these predict that 4096 bits > > > > assymmetric (RSA) will be safe for the next 50 years (or thereabouts). > > > > However, the NIST recommends 7680 (for decades?) and even 15360 bits > > > > for RSA (for centuries?). > > > > > Any one want to guess what their drift is? > > > > I have no idea. ?Noone can predict that far out. > > I have been watching ever since RSA came out. It was not that long > > ago when it was considered that keys of a 1000 bits would last longer > > than till the sun burned out. > > In 1991, [1] said > > "For most applications a modulus size of 1024 bits should achieve a > sufficient level of security for "tactical" secrets for the next ten > years. This is for long term secrecy purposes; for short term > authenticity purposes 512 bits might suffice in this century." > > Andrew. > > [1] Th. Beth, M. Frisch and G. Simmons, Public Key Cryptography: State > of the Art and Future Directions, LNCS 578, SpringerVerlag,1992 From what I see the 512-bit factorization occurred around 2000. So that statement is fairly dead on. Even in the mid 90s when I was getting into cryptography it was fairly common place to be using AT LEAST 768-bit RSA keys. From what I understand, the QS and MPQS were the systems used originally, so any time estimates were likely based on those. A quick google suggests that the GNFS came around out of the SNFS in the early 90s. Probably after that paper was written, so all in all, the estimates were scientific. One thing I see missing is the concept of forward secrecy. You should always have in mind a system for renewing keys. They become insecure for more reasons than just factorization. If you can't ever change your public keys your system is fairly dead in the water. Tom
From: Lucian Solaris on 8 Sep 2009 03:24 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 I applied moore's law to my version of GnuPG by making the hard limit higher than any theoretical keysize I may need in the next 100 years. Now there are limits to what an unmodified GnuPG will accept, and that's 16384 bits and below RSA and the largest DSA2 key I've ever tested was 4096 bits. These limits are increased significantly in mpicoder on my modified version. I am working on integrating an existing ECC patch, but I will not release a version with it until I'm able to generate a new curve differing from the official ones (since there is suspicion that the current public curves have 'back door' sister curves, google it). My key is a 16384 bit RSA key, a 4096- bit DSA2 signing subkey, and a 4096- bit ElGamal encryption subkey. sks-keyservers handles it just fine, as well as keyserver.pgp.com. pgp-keys.mit.edu and other servers using pks-keyserver software will choke on it. Unfortunately, the only way to beat moore's law is to increase bitsize at a percentage equal to that of moore's law or find a harder problem. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 - *.:{Hack.I.T Edition r0001}:.* iJ4EAREKAAYFAkqmBqAACgkQ+7Rzy15t3vbYEAH7BYzydx0FV1E1zWDsxQq4yOgM HEANiYnyXk0HlFWdBdivHw32uGTzzO7BPzqmStlPcf4RxdXQJlEU3TzYgOM53QH7 B36mgQCTri4F9ElOxysVmbxMJvU/hBK4vHobr4vaBFKIbIWzV2dCR9s7qJotsZiP FmVMmu0r1McyyJDb+5mNlg== =t1S7 -----END PGP SIGNATURE-----
From: Tom St Denis on 8 Sep 2009 08:28 On Sep 8, 3:24 am, Lucian Solaris <luciansola...(a)gmail.com> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA512 > > I applied moore's law to my version of > GnuPG by making the hard limit higher > than any theoretical keysize I may need > in the next 100 years. Now there are > limits to what an unmodified GnuPG > will accept, and that's 16384 bits and > below RSA and the largest DSA2 key > I've ever tested was 4096 bits. These <snip> Yes and no. First off, 2^80 time is huge. Worse >2^40 memory is huge. What you fail to take into account is that future advances in factoring might make the problem very tractable in that no practical size is secure whatsoever. Look at the advances of GNFS over MPQS in that regard. So no, using a 16384-bit RSA key today is NOT a good idea. It's hugely expensive to compute, consumes a lot of bandwidth, and isn't necessarily more secure. Tom
From: Harold Johanssen on 8 Sep 2009 09:58
On Tue, 08 Sep 2009 00:24:39 -0700, Lucian Solaris wrote: > My key is a 16384 bit RSA key, a 4096- bit DSA2 signing subkey, and a > 4096- Do you really think you need a key that big? I mean, who is it that might want to break your system, and who could do so without any problems if you were using a 1024 bit RSA key? |