Slashdot Mirror

← Back to Stories (view on slashdot.org)

Math Advance Suggest RSA Encryption Could Fall Within 5 Years

Posted by Soulskill on from the which-will-be-about-the-time-encryption-becomes-useless-anyway dept.

holy_calamity writes "The two encryption systems used to secure the most important connections and digital files could become useless within years, reports MIT Technology Review, due to progress towards solving the discrete logarithm problem. Both RSA and Diffie-Hellman encryption rely on there being no efficient algorithm for that problem, but French math professor Antoine Joux has published two papers in the last six months that suggest one could soon be found. Security researchers that noticed Joux's work recommend companies large and small begin planning to move to elliptic curve cryptography, something the NSA has said is best practice for years. Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry."

3 of 282 comments (clear)

  1. OpenSSL? by pope1 · · Score: 5, Interesting

    OpenSSL has had a good working implementation of ECDSA/ECDH for years: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography

    What exactly does BlackBerry have chained down that we don't have an open solution for?

    --
    /* * pope1 */
  2. Re:Why not go back to original RSA? by slew · · Score: 5, Interesting

    Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.

    Sometimes the past needs to remain in the past...

    Although prime factoring is considered a hard problem, the sparse distribution of prime numbers (~x/ln(x)) makes RSA increasingly inefficient in that superlinearly large moduli (to match large primes) need to be used to increase security linearly.

    Lest nostalgia continue to be your guide, the original RSA was also found to be broken and needed to be patched to avoid the insecurity

    1. Messages corresponding to small input values could be simply inverted ignoring the modulus operation (just doing numerical root estimation to invert the exponentiation). The larger the modulus, the more "insecure" messages there are.

    2. Encryption is deterministic so is subject to dictionary attacks.

    When people say they are using RSA today, they are usually using RSA-OAEP (optimal asymmetric encryption padding) which patches these two specific vunerablities of RSA.

    FYI, the original RSA was patented (although later RSA labs decided to not enforce the patent and let it expire). This patent nonsense around RSA was a big issue in its day...

  3. Re:RSA = out of date by dcl · · Score: 5, Interesting

    There is another promising public key encryption method known as NTRUEncrypt (http://en.wikipedia.org/wiki/NTRUEncrypt). It's lattice based, and apparently it will still be effective in a post quantum computing world where RSA/Elliptic curve methods will fail.