In einem (nicht-akademischen) Artikel beschäftigen sich Neal Koblitz und Alfred J. Menezes mit der Frage, ob Elliptic Curve Cryptography (ECC) noch sicher ist: A Riddle Wrapped In An Enigma, 2015-10-20.

Ausgangspunkt ist, daß die National Security Agency (NSA) im August 2015 unerwartet folgende Empfehlung gab:

For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

[…]

Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be.

Diese Empfehlung wurde vielfach so verstanden, daß die NSA jetzt auf einmal von ECC eher abrät und auf die schnelle Einführung von Post-Quantum Cryptography (PQC) setzt – wer noch etwa RSA benutze, solle nicht mehr auf ECC wechseln, sondern etwas warten und dann gleich auf PQC. Dabei hatte die NSA die vergangenen Jahrzehnte stark für ECC wie Elliptic Curve Diffie-Hellman (ECDH) Key Exchange und Elliptic Curve Digital Signature Algorithm (ECDSA) geworben.

Seit den Anschlägen vom 11. September 2001 ist die NSA immer mehr als Bedrohung für Internet- und Computernutzer wahrgenommen worden, nicht als Organisation zu deren Schutz. Die Snowden-Enthüllungen seit 2013 haben das bestärkt – und in den Dokumenten fand sich auch ein Hinweis, daß die NSA einen mit einer Hintertür manipulierten Zufallszahlengenerator Dual_EC_DBRG (Dual Elliptic Curve Deterministic Random Bit Generator, der auch elliptische Kurven nutzt) von NIST standardisieren und gegen die heimliche Zahlung von 10 Millionen US-Dollar vom Unternehmen RSA in seine Produkte einbauen ließ.

Sollte die NSA also Informationen oder praktische Möglichkeiten haben, Elliptische-Kurven-Kryptographie zu brechen oder kurz davor zu stehen? Etwa mit Quantencomputern und -algorithmen? Will sie die USA – Regierung, US-Unternehmen und US-Bürger – mit ihrer Empfehlung schützen?
Oder – »Verschwörungstheorie« – ist es andersrum: Will die NSA die Gesellschaft besser ausspähen können, was möglicherweise mit bisherigen Algorithmen nicht so einfach geht, vielleicht aber mit nun überstürzt einzuführender Post-Quantum Cryptography?

Die Autoren des Artikels beleuchten die Geschichte von Elliptic Curve Cryptography und der NSA. Sie stellen Spekulationen zur neuen NSA-Empfehlung vor und beurteilen sie. Das alles ist sehr lesenswert und verständlich geschrieben, mathematische Kenntnisse sollten für die größten Teile nicht nötig sein.

Als Fazit scheint man mitnehmen zu können: Weder herkömmliche Algorithmen wie RSA (bei großem Modulus, Minimum 3072 Bit) noch Elliptic Curve Cryptography (mit P-384) scheinen gebrochen, sie sollten für einige Jahre noch sicher nutzbar sein. Kleinere Bitlängen sollte man vermeiden. Wenn möglich sollte man statt der 15 Jahre alten NIST-Kurven neuere wie Edwards-Kurven verwenden. Auch scheint die NSA noch keine extrem leistungsfähigen Quantencomputer zu haben oder zu bauen.

Artikel entdeckt durch einen Retweet von Jens Kubieziel.

Nachtrag vom 2015-10-22: Auch Matthew Green empfiehlt die Lektüre des Artikels von Koblitz und Menezes. Seine Ansicht ist, daß die NSA zuletzt erste Erfolge mit Angriffen herkömmlicher Kryptoanalyse – nicht Quantencomputer – gegen das Elliptic Curve Discrete Logarithm Problem (ECDLP) und damit ECC gemacht haben könnte und daß mit weiterer Forschung die deutlich kleineren Bitlängen bei ECC eine Gefahr darstellen könnten.