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.