For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by NIST.
Eine Kuriosität am Rande: auf viele Eigenschaften von elliptischen Kurven gibt es Patente von Unternehmen oder Privatpersonen, die NSA mußte für einige der auf ihrer Liste vorgeschlagenen Kurven zunächst eine Lizenz erwerben.
Quantencomputer – die es freilich noch nicht gibt – könnten mit einem Algorithmus, für den Peter Shor 1998 den (inzwischen in IMU Abacus Medal umbenannten) Nevanlinna-Preis erhielt die Primfaktorzerlegung großer Zahlen effektiv berechnen. Mit einer Variante des Shor-Algorithmus könnten sie auch diskrete Logarithmen in beliebigen zyklischen Gruppen endlicher Ordnung ziehen und damit jede Variante der auf elliptischen Kurven beruhenden Elgamal-Verschlüsselung effektiv brechen.
Warum werden Bitcoins nicht geknackt?
Wer schon immer einmal wissen wollte, welches Verschlüsselungsverfahren Bitcoins verwenden: diese Frage wurde im November 2019 auf Mathoverflow diskutiert.
Verwendet wird die sehr einfach aussehende elliptische Kurve
über dem endlichen Körper Fp mit
Tatsächlich betrachtet man in dieser elliptischen Kurve nur eine zyklische Untergruppe der Ordnung 115792089237316195423570985008687907852837564279074904382605163141518161494337.
Die Antworten auf Mathoverflow kann man wohl so zusammenfassen, dass man an die Sicherheit des Bitcoin-Algorithmus glaubt, weil viele smarte Leute versucht haben ihn zu knacken und es noch niemandem gelungen ist.
Schutz vor Quantencomputern
Zurück zur Podiumsdiskussion Ende September auf dem Heidelberg Laureate Forum. Diese begann mit einem halbstündigen Referat von Whitfield Diffie über die Geschichte der Kryptographie, das er mit dem Hinweis beendete, dass schon 2015 das Committee on National Security Systems aufgefordert hatte, zu Algorithmen zu wechseln, die auch gegen Quantencomputer – insbesondere Shors Algorithmus – resistent sind. Nach dieser Aufforderung sei sieben Jahre lang nichts passiert, aber vor wenigen Tagen sei ein auf CRYSTALS basierender neuer Algorithmus herausgekommen.
CRYSTALS steht für „Cryptographic Suite for Algebraic Lattices“, es setzt sich zusammen aus Kyber, einem IND-CCA2-secure key-encapsulation mechanism, und Dilithium, einem strongly EUF-CMA-secure digital signature algorithm. Beide Algorithmen basieren auf schweren Problemen aus der Theorie von Gittern in Moduln. Ein paar Stichworte zum mathematischen Hintergrund gibt der Wikipedia-Artikel “Lattice-based cryptography”.
Die Frage, wann mit Quantencomputern zu rechnen sei, wurde von den Teilnehmern der anschließenden Podiumsdiskussion mit Zahlen zwischen 10 und 30 Jahren beantwortet. Man solle trotzdem jetzt mit den Umstellungen beginnen, weil solch ein Wechsel eine lange Zeit benötige: Standards müßten geändert, Menschen dafür ausgebildet und zahlreiche praktische Probleme gelöst werden. Außerdem könnten wichtige Geheimnisse heute gestohlen und 20 Jahre später entschlüsselt werden, weshalb man sie schon heute gegen Angriffe durch Quantencomputer schützen sollte.
Kommentare (12)