[Top] [All Lists]

Re: New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman

2000-12-14 11:01:19

I haven't followed the latest thinking on breaking algorithms such as RSA, so 
I'll take your word for the fact that the Number Field Sieve is currently the 
most efficient algorithm.  But isn't it at least possible that there might be 
other methods that although  less efficient than the NFS on a single machine, 
might be more well-suited to a distributed attack?  Likewise, would other 
algorithms be less constrained by a 64-bit addressing limitation?

Interesting point, though, in any case.



Robert R. Jueneman
Security Architect
Novell, Inc.

<FRousseau(_at_)chrysalis-its(_dot_)com> 12/13/00 10:36PM >>>

I am sorry for the multiple postings, but I thought this particular subject, 
although probably quite controversial, might be of interest to the many peoples 
following these mailing lists, especially because of the upcoming adoption of 
the AES algorithm by many IETF protocols.
As symmetric keys grow, they can be attacked by more processors without a 
change in processor technology since the memory requirements for breaking 
symmetric keys remain trivial.  However, for the Number Field Sieve (NFS) 
algorithm, which is currently the most efficient method to break RSA keys, this 
is not true.  Based on this premise, the "time and space" based RSA key size 
equivalents previously published in the RSA Labs Bulletin #13 of April 2000 by 
Robert Silverman ( have recently been 
extended to cover all the AES symmetric key sizes in the latest draft of ANSI 
X9.44, which will eventually become the ANSI standard for RSA key transport:
                        Time and Space 
Symmetric               Equivalent 
Key Size                RSA Key Size 
(in bits)               (in bits) 
64                      450 
128                     1620 
192                     2500 
256                     4200 
These "time and space" based key sizes equivalents assume that both time and 
memory are binding constraints in order to break RSA keys.  This same draft 
also indicates that beyond RSA key sizes of 768 bits one can no longer 
effectively utilize 32-bit processors with the NFS algorithm because the 
required memory exceeds what can be addressed in 32 bits; one is forced to use 
64-bit machines.  Beyond RSA key sizes of about 2500 bits, the memory 
requirements for the NFS algorithm exceed what can be addressed even on 64 bit 
For your information, here are also the estimated "time" only based RSA key 
size equivalents for solving the NFS problem from the same ANSI draft:
                        Time Only 
Symmetric               Equivalent 
Key Size                RSA Key Size 
(in bits)               (in bits) 
64                      512 
128                     2550 
192                     6700 
256                     13500 
Note that either of these sets of RSA key size equivalents could be used with 
Diffie-Hellman for solving the value of "p" since the NFS algorithm is also the 
most efficient method to break Diffie-Hellman algorithm today.  Note also that 
these time only equivalents numbers are slightly smaller than those from ANSI 
X9.42 for Diffie-Hellman (i.e. 2550 vs 3072 for 128 bits, 6700 vs 7680 for 192 
bits and 13500 vs 15360 for 256 bits) and the numbers in Hilarie Orman's 
Internet Draft (i.e. draft-orman-public-key-lengths-01.txt).
Shouldn't IETF standards mention these new "time and space" based key size 
equivalents in addition to existing "time" only based key size equivalents, and 
possibly even suggest that "time and space" based key size equivalents be used 
for RSA and Diffie-Hellman?  Why mandate larger equivalent key sizes when 
smaller equivalent key sizes can probably suffice?
Food for thought! 
Francois Rousseau 
Director of Standards and Conformance 
1688 Woodward Drive 
Ottawa, Ontario, CANADA, K2C 3R7 
frousseau(_at_)chrysalis-its(_dot_)com      Tel. (613) 723-5076 ext. 419     Fax. (613) 723-5078 
<Prev in Thread] Current Thread [Next in Thread>
  • Re: New Time and Space Based Key Size Equivalents for RSA and Diffie-Hellman, Bob Jueneman <=