At Blackhat 2013 this week, there was a talk saying RSA is (essentially) doomed in the near future.

networkworld.com ~ “Black Hat: Elliptic curve cryptography coming as smarter algorithms threaten RSA”

What "two devastating attacks in the past 6 months" is Mr Ritter referring to, and how real is the threat to RSA?

  • $\begingroup$ See also threatpost.com/… : probably a confusion with recent discrete logs improvements. $\endgroup$
    – minar
    Aug 2 '13 at 19:11
  • 2
    $\begingroup$ I was surprised after a quick search to not find any reference to their company selling EC products/solutions. $\endgroup$
    – Michael
    Aug 2 '13 at 21:33
  • 1
    $\begingroup$ @Michael ...yet $\endgroup$
    – orlp
    Aug 2 '13 at 22:23
  • 1
    $\begingroup$ So, we should use "elliptical" curve cryptography, eh? $\endgroup$
    – Reid
    Aug 2 '13 at 23:01
  • 1
    $\begingroup$ Elliptic curve cryptanalysis has had 1/100th the attention of RSA and yet these guys want to run to it? I'm guessing if we start to convert to ECC, the recommended key lengths will quickly increase in the next few years. $\endgroup$
    – Fixee
    Aug 3 '13 at 3:20

Behold! The slides from the presentation, as pulled from the Black Hat 2013 iSEC Partners page. The presenters are not cryptographers — they're security researchers. You can find more information about the presentation at the Black Hat website, including a brief biography of the researchers in question.

It appears that the presentation focused on advancements in the discrete logarithm problem, particularly by Joux, and less on factoring itself; instead, the argument was that since advances in the discrete logarithm problem tend to lead to advances in factoring (and vice versa), and since Joux has been making some particularly good progress in that area, RSA is thus in imminent danger.

I'm ambivalent on the matter.

To answer your question directly, I'm not sure which two "devastating attacks" the article in question is talking about. The slides, as linked above, contain links to many different results (see page 26 and onward). However, if I had to guess, I would suspect they are talking about

  1. Joux's A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, published on Feb. 20, 2013, and
  2. Barbulescu et al.'s A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, published on Jun. 18, 2013.

These two papers are cited in the slides on pages 26 and 28, respectively.

  • 3
    $\begingroup$ Thanks for posting this. I am not an algebraist, but breakthroughs in discrete log for small-characteristic finite fields doesn't seem particularly related to factoring in zero-characteristic rings like $\mathbb{Z}$. Of course it may be relevant to RSA (which is on the ring $\mathbb{Z}_N$) and despite many wrong proclamations in the cited articles, breaking RSA does not require factoring. In any case, in my opinion the presenters have overstepped in declaring a state of emergency with respect to RSA. Remember 10 years ago all the factorization papers (Bernstein and Shamir mostly)? $\endgroup$
    – Fixee
    Aug 3 '13 at 3:18
  • 4
    $\begingroup$ Personally I don't take anything seriously if it's written in comic sans. $\endgroup$
    – rath
    Aug 3 '13 at 5:03
  • $\begingroup$ Seems that Schneier (and other cryptographers) agree with me: schneier.com/blog/archives/2013/08/the_cryptopocal.html $\endgroup$
    – Fixee
    Aug 31 '13 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.