Date: Thu, 29 Aug 2002 19:53:52 -0400 From: "Steven M. Bellovin" <smb@research.att.com> To: "Perry E. Metzger" <perry@piermont.com> Cc: freebsd-security@FreeBSD.org, tech-security@netbsd.org, misc@openbsd.org Subject: Re: Long RSA keys Message-ID: <20020829235353.026E37B4C@berkshire.research.att.com>
next in thread | raw e-mail | index | archive | help
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. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-security" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020829235353.026E37B4C>