The following usenet posting from 1993 provides an interesting bit (no pun itended) of history on RSA key sizes. The key passage is the last paragraph, asserting that 1024-bit keys should be ok (safe from key-factoring attacks) for "a few decades". We're currently just under 1.75 decades on from that message. I think the take-home lesson is that forecasting progress in factoring is hard, so it's useful to add a safety margin...
From: p...@ox.ac.uk (Paul C Leyland) Newsgroups: sci.crypt Subject: Re: Questions about RSA. Message-ID: <pcl.93feb16102...@rhodium.ox.ac.uk> Date: 16 Feb 93 10:26:11 GMT References: <1993feb10.183246.29...@ee.ubc.ca> Distribution: sci.crypt, alt.security Organization: Oxford University Computing Services, 13 Banbury Rd Oxford OX2 6NN Lines: 59 In-reply-to: jrusm...@ee.ubc.ca's message of 10 Feb 93 18:32:46 GMT In article <1993feb10.183246.29...@ee.ubc.ca> jrusm...@ee.ubc.ca (RUSMISEL JASON DIRK) writes: ... 1) The article suggests that the length of 'n', (where n is the product of two large primes p and q, and n is the modulus used with the encryption and decrytion keys to decode and encode) be 200 digits. [page 125, top right] 200 digits base 10 is about 664 binary digits. Now, to the question. The program PGP provides various levels of key length, 384 bits, 512 bits and 1024 bits. How were these numbers decided on? I The PGP values are round numbers (3/8, 1/2 and 1) in kilobits. They are (handwaving furiously here) "about the right size" for testing, routine use and archival security. The RSA values are about the right size for routine use. realize that the state of computer technology at the time the RSA article was written was very different than it is now, but have there been significant advances in crypto breaking since 1978 that would make factoring such large numbers much easier? (Perhaps the Connection Machine.....) Really I'm interested in a discussion of the design decisions/tradeoffs here. Let me try to justify the armwaving a little. First, we must realise that the larger the keys, the greater the run-time of the encryption and decryption process. Purists may nit pick, but roughly speaking doubling the number of digits in the key increases the run time eightfold. [Purists: I'm assuming a n-squared multiplication routine and the simple binary method of exponentiation]. So small moduli are good. So far as is known, the only way to find the RSA secret key (other than espionage, bribery, extortion, etc) is to factorize the modulus. Here large moduli are good. Roughly speaking *adding* a few bits to the length of the modulus raises the factorizing cost eightfold. Compare this to the encryption, where *doubling* costs us that much. The meaning of "a few bits" can also be argued over, but it is around 20 bits, depending on methods and the size of the number. Current state of the art described in the open literature factorizes 120-digit numbers in a time of order one year, using machines of order 1000mips performance. Again, purists can post better numbers if they wish. 384 bits is 116 digits so the PGP test keys can, with sufficient effort, be cracked with today's technology. 512 bits is well beyond current technology (155 digits) but *might* be accessible in a few years with better algorithms and faster machines and more of them working in parallel and ... (I'm handwaving again). 1024-bits, so far as is known should be ok for a few decades. I'd be happy to be proved wrong, as there's lots of other numbers I'd like to be able to factorize. Paul -- Paul Leyland <p...@oxford.ac.uk> | Hanging on in quiet desperation is Oxford University Computing Service | the English way. 13 Banbury Road, Oxford, OX2 6NN, UK | The time is come, the song is over. Tel: +44-865-273200 Fax: +44-865-273275 | Thought I'd something more to say. Finger p...@black.ox.ac.uk for PGP key | -- -- "Jonathan Thornburg [remove -animal to reply]" <jth...@astro.indiana-zebra.edu> Dept of Astronomy, Indiana University, Bloomington, Indiana, USA "Washing one's hands of the conflict between the powerful and the powerless means to side with the powerful, not to be neutral." -- quote by Freire / poster by Oxfam --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com