Merit Network
Can't find what you're looking for? Search the Mail Archives.
  About Merit   Services   Network   Resources & Support   Network Research   News   Events   Home

Discussion Communities: Merit Network Email List Archives

North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: Banc of America Article

  • From: Dave Howe
  • Date: Sun Jan 26 10:55:46 2003

E.B. Dreger wrote:
>> Date: Sun, 26 Jan 2003 00:22:02 -0500 (Eastern Standard Time)
>> From: Alex Rubenstein
>> Agreed. And, even if it is super encrypted, who cares? Enough
>> CPU and time will take care of that.
> Articles about "1000 years to crack using brute force" are a bit
> disconcerting if someone has access to 10,000x compromised hosts.
> While we're on the subject: root certificates, anybody?
> Each worm seems to prove the availability of CPU and time.
Might not  even need a worm - just enough money to form a seed.
according to recent paper (TWIRL) the main step towards breaking a 1024 key
(such as used by all the CAs currently) could be done in under a year by a
machine with a cost of $10M (surely not beyond the reach of a large
multinational company or crime organisation). In detail:
Factoring Large Numbers with the TWIRL Device
(preliminary draft)

Adi Shamir, Eran Tromer

Department of Computer Science and Applied Mathematics Weizzmann Institute
of Science, Rehavot 76100, Israel Ishamir,

January 23, 2003


The security of the RSA cryptosystem depends on the difficulty of factoring
large integers. The best current factoring algorithm is the Number Field
Sieve (NFS), and its most difficult part is the sieving step. In 1999 a
large distributed computation involving thousands of workstations working
for many months managed to factor a 512-bit RSA key, but 1024-bit keys were
believed to be safe for the next 15-20 years. In this paper we describe a
new hardware implementation of the NFS sieving step (based on standard
0.13pm, I GHz VLSI technology) which is 3-4 orders of magnitude more cost
effective than the best previously published designs (such as the opt
electronic TWINKLE of 1131 and the mesh-based sieving of 151)- Based on a
detailed analysis of all the critical components (but without an actual
implementation), we believe that the NIPS sieving step for 1024-bit RSA keys
can be completed in less than a year by a $10M device, and that the NFS
sieving step for 512-bit RSA keys can be completed in less than ten minutes
by a $10K device. Coupled with recent results about the difficulty of the
NFS matrix step [10], this raises some concerns about the security of these
key sizes-

Discussion Communities

About Merit | Services | Network | Resources & Support | Network Research
News | Events | Contact | Site Map | Merit Network Home

Merit Network, Inc.