Bernstein's NFS analyzed by Lenstra and Shamir

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..."

Comments

hackers...

[coronaride]

still waiting for that level of encryption shown in everyones favorite hacking movie that displays the giant skull and crossbones in a cheezy GUI to let you know that you don't have access..

Re:Is factoring hard

[GigsVT]

Nah, factoring's easy, I can factor any prime number up you tell me, in my head, in less than a second.

Mesh routing is really the way to go

[Sheetrock]

I don't know how many of you are cryptobuffs, but you might remember the craze surrounding elliptic curves as a efficient-yet-complex method of obfuscating plaintext. There was a bit of controversy as to whether or not it would lead to predictability because of its nature (ellipses are round, keep in mind, and therefore there was some concern that what goes around comes around and an attacker could just walk full circle to arrive at a key).

Well, I believe that mesh routing might just give us all the pluses without most or all of the minuses. First of all, it involves routing, which if you've paid attention to the formation of the Internet you'll quickly realize is a design that will lead to redundancy and reliability. More importantly, it is a mesh, which means that one end of the key is not necessarily tied to the other end. This should cut off many of the attacks that would have a chance of success on elliptic curves by way of its nature. Meshing also implies redundancy... there may be some size and speed tradeoffs here, but you can be certain you'll get your data back out of the cryptopot.

Bruce Schneier, a luminary in the field of cryptography and author of the book Applied Cryptography, has a web site here.

Dot and a Database

[The Infamous TommyD]

Wow, what karma whore. You're making more shit up than a battalion of marines with dysentary.

Re:Cliff notes version

[MAXOMENOS]

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

This post should be modded +4 Understated.

Huh?

[Grip3n]

"...under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars."

Wow, we can make The Matrix in under a day for a couple grand? Better start looking in the paper for real estate in Zion...