Slashdot Mirror

← Back to Stories (view on slashdot.org)

Factoring Breakthrough?

Posted by michael on from the for-as-long-as-men-are-capable-of-evil dept.

An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"

8 of 489 comments (clear)

  1. damnit by Anonymous Coward · · Score: -1, Redundant

    now i am FUCKED because of this.

  2. it's a cool method by Frothy+Walrus · · Score: 1, Redundant

    basically what DJB has done is found ways to incorporate extra hardware to eliminate redundant operations when performing number field sieve (NFS). he's implemented NFS in a non-linear way, which results in a threefold increase in speed from linear NFS implementation.

    it's a wonder no one thought of it before. oh, wait, i think a three-letter agency might have...
    better update those keys!

  3. Re:For the PostScript-impaired by rjamestaylor · · Score: 0, Redundant

    Thanks for the link. Very helpful.

    --
    -- @rjamestaylor on Ello
  4. To quote another: by PureFiction · · Score: 2, Redundant

    "Holy shit. The math works. Bernstein has found ways using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies an redundancies because we kept thinking in terms of linear implementations. This is probably the bigest news in crypto in the last decade."

    Yeah, this is big news. It also sheds new light on the relaxation of the export constraints. The NSA has dedicated hardware performing this same procesing, and probably for the last 5-10 years...

    "Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fa ct very likely."

    Time to make new keys...

  5. Does this mean that the movie Sneakers.... by mbourgon · · Score: 1, Redundant

    is now viewed as technically sound? :)

    --
    "Sometimes a woman is a kind of religion, she can save your soul & set you free from all your sins" - Bad Examples
  6. Not to put on my tinfoil hat, but... by Anonymous Coward · · Score: -1, Redundant

    All of the links to the paper are dead.

  7. HELLO!! 3x speed improvement is not that much by Anonymous Coward · · Score: -1, Redundant

    Your keys should have originally been orders of magnitude larger than the time you think someone would spend to break them. 100days/3 is still 33.3days this doesn't make RSA a joke and i doesn't mean you have to increase your keylength by some huge number, just a modest one.

  8. Mirror/Cached papers here by bodin · · Score: 1, Redundant

    (as djbs koobera-server seems to be under hard pressure)

    Here you will find mirrors of the original file as well as the document in pdf-format etc:

    http://citeseer.nj.nec.com/462633.html