Slashdot Mirror

← Back to Stories (view on slashdot.org)

Bernstein's NFS analyzed by Lenstra and Shamir

Posted by CmdrTaco on from the my-c0de-is-s3kr37 dept.

kousik writes "The analysis of Bernstein's NFS by Arjen Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer has been put up on cryptosavvy. Seems interesting it comes from Lenstra and Shamir. Lenstra lead the 1994 factorisation of RSA 129. From the abstract: ... 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..."

3 of 168 comments (clear)

  1. Quotes from the paper by Beryllium+Sphere(tm) · · Score: 5, Interesting

    "In particular, we show that 1024-bit RSA keys are as secure as many
    believed them to be."

    "We thus
    conclude that the practical security of RSA for commonly used modulus
    sizes is not significantly affected"

    Sounds like it only speeds up one step of the factoring process, which is important to keep an eye on but not grounds for alarm.

  2. The /. story quotes the wrong part of the paper by mridley · · Score: 5, Interesting

    Well the /. story exerpt is kind of alarmist but I think the more relevant quote from the paper is "However, the theoretical analysis shows that the cost of the relation collection step cannot be significantly reduced, regardless of the cost of the matrix step. We thus conclude that the practical security of RSA for commonly used modulus sizes is not significantly affected..." (typos probably mine)

  3. Cliff notes version by Ashurbanipal · · Score: 5, Interesting

    Basically, Dan Bernstein (who has written useable but controversial alternatives to BIND and SENDMAIL) figured out a new method for breaking RSA encryption based on custom hardware. The fellows mentioned in the headline, who are also legit crypto guys, have analysed Dr. Bernstein's work and make the following observations:

    1) it's not quite as fast as Bernstein estimated (about half as fast for cliff notes purposes)
    2) the hardware could be affordable (others have claimed costs that are only feasible for governments)
    3) you don't have to revoke all your RSA keys because there are steps that precede the application of the Berstein method that still take absurd amounts of time and horsepower.

    Oh, yeah, and it has nothing to do with Sun's NFS (Network File System, a lame and usually insecure way to share files).

    Bernstein will no doubt reply. He isn't a shy guy from my experience.