Subject: Re: Long RSA keys
To: Perry E. Metzger <perry@piermont.com>
From: Steven M. Bellovin <smb@research.att.com>
List: tech-security
Date: 08/29/2002 19:53:52
In message <8765xtzb48.fsf@snark.piermont.com>, "Perry E. Metzger" writes:
>

>
>If you think that you have something new and exciting to tell me that
>I've never heard of before, check if it has been published in Crypto
>or Eurocrypt or something first. If you don't know enough to read
>those conference proceedings, you don't know enough to have an
>intelligent opinion on the cost of building a machine to run djb's NFS
>factoring ideas.
>

In that vein, it's worth noting that Bernstein's results have not been 
embraced by the community qualified to have an opinion:  the 
cryptographic mathematicians.  (I'm not qualified -- the crypto I do is 
cryptographic protocol work, which is a very different beast indeed.
I have a decent knowledge of the literature, which leaves me in a
position of having to choose which authority I believe.  But we're
not dealing here with matters of opinion; my vote doesn't count for
nearly as much as, say, the authors of the paper I cite below.)

Let me refer folks to some people who are qualifed to have an opinion:  
Arjen Lenstra, Adi Shamir, Jim Tomlinson, and Eran Tromer.  You can 
find their paper at http://www.cryptosavvy.com/meshps.gz (or .pdf);
here's the abstract:

	Abstract. In [1], Bernstein proposed a circuit-based
	implementation of the matrix step of the number field sieve
	factorization algorithm. These circuits offer an asymptotic
	cost reduction under the measure construction cost × run
	time. We evaluate the cost of these circuits, in agreement
	with [1], but argue that compared to previously known
	methods these circuits can factor integers that are 1.17
	times larger, rather than 3.01 as claimed (and even this,
	only under the non-standard cost measure).  We also propose
	an improved circuit design based on a new mesh routing
	algorithm, and show that for factorization of 1024-bit
	integers the matrix step can, under an optimistic assumption
	about the matrix size, be completed within a day by a device
	that costs a few thousand dollars.  We conclude that from
	a practical standpoint, the security of RSA relies exclusively
	on the hardness of the relation collection step of the
	number field sieve.