[TIME_WARP] 1280-Bit RSA

[Jonathan Thornburg]

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: pcl at ox.ac.uk (Paul C Leyland)
   Newsgroups: sci.crypt
   Subject: Re: Questions about RSA.
   Message-ID: <PCL.93Feb16102611 at rhodium.ox.ac.uk>
   Date: 16 Feb 93 10:26:11 GMT
   References: <1993Feb10.183246.29386 at ee.ubc.ca>
   Distribution: sci.crypt, alt.security
   Organization: Oxford University Computing Services, 13 Banbury Rd Oxford OX2 6NN
   Lines: 59
   In-reply-to: jrusmise at ee.ubc.ca's message of 10 Feb 93 18:32:46 GMT
   
   In article <1993Feb10.183246.29386 at ee.ubc.ca> jrusmise at 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 <pcl at 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 pcl at black.ox.ac.uk for PGP key    |

-- 
-- "Jonathan Thornburg [remove -animal to reply]" <jthorn at 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 majordomo at metzdowd.com