Morituri te salutant! (2) : Warum Quantencomputer heutige asymmetrische Kryptoverfahren bedrohen und wie deren jetziges Sicherheitsniveau begründet ist – ein Ausflug in die Mathematik

Im ersten Teil dieses Beitrags wurde eingehend dargestellt, welche mathematischen Konzepte für den bekannten RSA-Algorithmus genutzt werden: die sogenannten Primkörper Fp für Primzahlen p. Auch zu Zahlen m, die keine Primzahlen sind, lassen sich ganz analog Rechenbereiche bilden – allerdings verdienen sie dann nicht mehr die Bezeichnung Körper, sondern gehören nur noch zur Kategorie der Ringe und werden als Restklassenringe Zm bezeichnet.

Jedes Element x eines Körpers (mit Ausnahme des Nullelements 0) besitzt stets ein Reziprokes x−1 (= 1 /x ), sodass die Division durch x stets möglich ist – nämlich durch Multiplikation mit eben diesem Reziproken x−1. In Ringen kann es außer der Null weitere Elemente geben, die kein Reziprokes besitzen. Alle anderen Elemente eines Ringes R, die ein Reziprokes haben, bilden die Einheitengruppe R* dieses Ringes (im Hinblick auf die Multiplikation).

Ebenfalls vorgestellt wurde die Eulersche ϕ-Funktion, die für jede natürliche Zahl n definiert ist, indem ϕ(n) die Anzahl der Elemente der Einheitengruppe Zn * angibt. Für Primzahlen p (und nur für Primzahlen) gilt dann insbesondere ϕ(p) = p − 1. Denn in den Primkörpern Fp (mit p Elementen) besitzt ja nur die Null kein Reziprokes (wohingegen die anderen Restklassenringe Zn sog. Nullteiler ohne Reziprokes besitzen).

Man mag sich die Frage stellen, weshalb eigentlich derartige mathematische Konzepte der elementaren Zahlentheorie überhaupt erforderlich sind. Ließe sich nicht auch in den „gewohnten“ Rechenbereichen ein Algorithmus zur Verschlüsselung und Entschlüsselung entwerfen? Kaum: Denn Kryptoalgorithmen klassischer Bauart versuchen einerseits, die Vertraulichkeit durch einen impraktikablen Rechenaufwand für potenzielle Angreifer zu schützen, und dürfen andererseits keinesfalls fehleranfällig sein. Die gewöhnliche Fließkomma-Arithmetik, die das Rechnen im Körper der rationalen Zahlen Q approximiert, ist jedoch anfällig für Rundungsfehler – denn in diesem Körper liegen Zahlen beliebig dicht beieinander: Zwischen 1 und 100 liegen ebenso viele rationale Zahlen (lies: Brüche = Dezimalzahlen mit endlich vielen Stellen nach dem Komma oder einer Periode) wie zwischen 0 und 0,001. Niemals liegen zwei Brüche so dicht beieinander, dass sich nicht noch eine, ja sogar beliebig viele weitere dazwischen angeben ließen. Daher sind Rechenbereiche, in denen Zahlen deutlich voneinander getrennt („diskret“) liegen, besser geeignet, um punktgenaue Algorithmen zu ermöglichen.

Problem des Diskreten Logarithmus (DLP)

Der Logarithmus ist die Umkehrung der Exponentiation. Wenn bx = y, dann heißt x der Logarithmus von y zur Basis b, geschrieben als x = logb y

Dies ist bekannt aus dem Umgang mit gewohnten Zahlbereichen wie den rationalen Zahlen Q oder den reellen Zahlen R (lies: beliebige Dezimalzahlen, auch mit unendlich vielen Stellen nach dem Komma, wie etwa die Kreiszahl π). Doch nichts hindert daran, derartiges auch in „ungewohnten Rechenbereichen“ zu tun, etwa in Restklassenkörpern, solange dort die Rechenoperationen interpretiert und ausgeführt werden können.

Schauen wir uns beispielsweise F53 zum primen Modul p = 53 an: Dieser Restklassenkörper hat 53 Elemente (jedes davon ist eine Restklasse), seine Einheitengruppe F53* besteht aus 52 Elementen (ϕ(53) = 52). Es gibt also – anders als auf der kontinuierlichen Zahlengerade – nur endlich viele Elemente, die „diskret“ (sprich: getrennt) nebeneinander liegen, ohne einen derart leicht erkennbaren geometrischen Zusammenhang, wie ihn die reelle Zahlengerade darstellt. Daher spricht man in solchen Fällen vom diskreten Logarithmus.

Zwar kann man eine Restklasse b aus F53 nicht mit einer reellen (oder beliebigen rationalen) Zahl potenzieren, aber zweifellos lässt sie sich mit einer natürlichen Zahl k potenzieren: Unter bk versteht man wie gewohnt das k-malige Produkt von b mit sich selbst: b · … · b = bk , wobei der Faktor b auf der linken Seite k-mal erscheint. Wenn nun als Ergebnis bk = a vorliegt, dann ist umgekehrt logb a = k (eine natürliche Zahl). Offensichtlich gilt dann bk · bl = bk+l, denn im Produkt b · … · b summiert sich ja die Anzahl der Faktoren. Damit ist es sinnvoll, b0 = 1 zu setzen, denn nur dann bleibt die eben erwähnte Gleichung bk · bl = bk+l für k=0 gültig. Ebenso ist es sinnvoll, unter b−k das Reziproke von bk zu verstehen, denn damit gilt dann bk · b−k = bk−k = b0 = 1. So lässt sich nun jede Restklasse b aus Fp mit einer ganzen Zahl k – sei sie null, positiv oder negativ – potenzieren.

Man kann nun zeigen, dass jede der Klassen aus der Einheitengruppe F53* des Primkörpers F53 eine Potenz eines Elements aus F53* ist, nämlich beispielsweise der Klasse 2. Ähnliches gilt für die Einheitengruppe F* jedes endlichen Körpers F, wobei nicht immer die Klasse 2 die „Basis“ ist. Es können auch andere Restklassen als sogenanntes erzeugendes Element fungieren – und zwar durchaus mehrere: Genauer gesagt beträgt ihre Anzahl ϕ(p−1) für die Einheitengruppe Fp * mit ihren p – 1 Elementen. Im Falle von p = 53 besitzt F53* insgesamt ϕ(p−1) = ϕ(52) = ϕ(13) · ϕ(4) = 12·2 = 24 solcher erzeugenden Elemente – neben der 2 also 23 weitere (bei diesem Umstand spielt übrigens eine wesentliche Rolle, dass Körper im Spiel sind, obwohl der Algorithmus nur seine Einheitengruppe benötigt, die Addition also scheinbar ungenutzt lässt).

Anders ausgedrückt besteht die Einheitengruppe F53* aus allen Potenzen 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16 et cetera bis hin zur Klasse 251 – denn nach dem kleinen Satz von Fermat schließt sich dann der Kreis: 252 = 1. Die Klasse 2 bietet sich gewissermaßen als eine mögliche (nicht die einzige!) Basis an. In diesem Sinne wäre also beispielsweise log2 8 = 3, was vertraut scheint, denn schließlich ist auch in unserem gewohnten „Rechenalltag“ 23 = 8. Bis zum Exponenten 5 bleibt auch alles wie gehabt: Wegen 25 = 32 (auch modulo 53) gilt log2 32 = 5. Danach kommt aber die Reduktion modulo 53 zum Tragen: 26 = 2 · 25 = 64 ≡ 11 modulo 53, sodas hier log2 11 = 6 ist. Wer hätte geahnt, dass in F53* log2 13 = 24 und log2 15 = 12 gilt? Für Kenner ist log2 52 = 26 hingegen nicht weiter verwunderlich.

Wenn man als Modul eine Primzahl p in der Größenordnung von 2048Bit = 22048 wählt, so lässt sich erahnen, dass derlei Rechnungen ziemlich aufwendig werden.

Tabelle 1 zeigt den Logarithmus zur Basis 2 (in der Literatur auch oft Index genannt) der Einheitengruppe F53* des Restklassenkörpers F53 (die 2 erzeugt tatsächlich diese Einheitengruppe).

Was die Kryptografie im Wesentlichen braucht, ist eine Gruppe G (hier die Einheitengruppe), in der die Bestimmung des Logarithmus mit hohem Rechenaufwand verbunden ist: Welcher Exponent x erfüllt die Beziehung a = bx? Weitere Voraussetzung ist, dass sich für jedes gewünschte Rechenergebnis a überhaupt ein solches x finden lässt, mit anderen Worten: Jedes Element a aus der Gruppe G muss in Form einer Potenz von der gewählten Basis b darstellbar sein.

Eine Gruppe, in der diese Bedingung erfüllt ist, nennt man eine zyklische Gruppe mit dem erzeugenden Element b. In einer beliebigen endlichen Gruppe lässt sich eine zyklische Untergruppe finden, indem man blindlings ein Element b der Gruppe auswählt und seine sämtlichen Potenzen heranzieht: Diese bilden nämlich offensichtlich eine Teilgruppe in der gesamten Gruppe; b ist eine Basis (erzeugendes Element) dieser Teilgruppe.

Diffie-Hellmann/ElGamal

Diese rechentechnische Hürde macht sich der Diffie-Hellmann-(DH)-Schlüsselaustausch zunutze, den Whitfield Diffie und Martin Hellmann 1976 (mit Vorarbeiten von Ralph Merkle, daher teils auch als DHM bezeichnet) entwickelt haben. Taher ElGamal hat dieses Verfahren 1985 zum ElGamal-Kryptosystem weiterentwickelt. Der „Digital Signature Algorithm“ (DSA) beruht übrigens ebenfalls auf diesen Voraussetzungen.

Schlüsselerzeugung/-austausch

Voraussetzung für das Verfahren ist eine öffentlich bekannte zyklische Gruppe G der Ordnung n – das heißt eine Gruppe G, die aus n Potenzen eines erzeugenden Elementes g besteht, also G = {1 = g0 = gn, g = g1 , g2 , g3 , g4 , … , gn–1}

Beispiele sind die Einheitengruppen primer Restklassenkörper Fp , die zyklisch von der Ordnung n = ϕ(p) = p – 1 sind. In jeder Gruppe bilden im Übrigen die Potenzen eines Elements g mit endlicher Ordnung eine Untergruppe der Ordnung n = ord(g), die sich dafür heranziehen lässt. Da der Rechenaufwand für die Punkte elliptischer Kurven (siehe unten) vergleichsweise hoch ist, lassen sich mit großem Nutzen zyklische Untergruppen elliptischer Kurven auf diese Weise heranziehen (ECDH, ECDLP …).

Zur Schlüsselerzeugung wählen Alice und Bob je eine geheime Zahl a (bzw. b) größer 1 und kleiner n und errechnen A := ga beziehungsweise B := gb . Die Zahlen a und b dienen den beiden als geheime Schlüssel, A und B werden als öffentlicher Schlüssel für die Kommunikationspartner verfügbar gemacht. Im Zuge des DiffieHellmann-Schlüsselaustauschs errechnet Alice Ba (= gba = gab), Bob hingegen Ab (= gab). Somit haben sich die Kommunikationspartner auf denselben Schlüssel verständigt, ohne diesen je übermittelt zu haben. Eavesdropperin Eve könnte zwar die Werte A und B abfangen. Für eine erfolgreiche Spionage müsste sie jedoch die (geheim gehaltenen) Exponenten a und b ermitteln – genau darin liegt aber das rechentechnische Problem des diskreten Logarithmus (DLP – hier zur Basis g).

Einsatz: Ver- und Entschlüsselung

Eine Nachricht (oder ein Nachrichtenteil) wird mithilfe der Elemente der Gruppe G kodiert – die zu verschlüsselnde Nachricht ist im Folgenden also ein Element x ∈ G. Will Alice eine Nachricht x an Bob verschlüsseln, multipliziert sie in der Gruppe G das Element x mit dem zuvor errechneten gemeinsamen Schlüssel encr(x) := x · Ba = y und sendet dieses Chiffrat an Bob. Bob bestimmt das Reziproke (Inverse) des zuvor errechneten Ab , also das Element A–b = g–ab. Dann multipliziert er das erhaltene Chiffrat y damit und erhält so den Klartext x zurück:

y · g–ab = x · Ba · g–ab = x · gba · g–ab = x

Bedrohung und Bedrohungsminderung

Wenn Eve als „Woman in the Middle“ nicht nur lauscht, sondern aktiv eingreift, indem sie die öffentlichen Schlüssel A und B sowie die übermittelte Kommunikation abfängt, kann sie sich ihrerseits wie ein versteckter Teilnehmer am Kryptosystem verhalten: Sie versendet in beide Richtungen ihren öffentlichen Schlüssel E = ge und hält die Schlüssel A und B zurück. Solange Alice und Bob sich in direkter Verbindung wähnen und E für den Schlüssel des jeweiligen Kommunikationspartners halten, kann Eve die vertrauliche Kommunikation unbemerkt abfangen, entschlüsseln, mitlesen und wieder verschlüsselt weiterleiten.

Denn wenn Alice E für Bobs öffentlichen Schlüssel hält, errechnet sie als Schlüssel Ea und als Chiffrat x · Ea = y‘, das sie vermeintlich an Bob schickt. Hatte Eve die öffentlichen Schlüssel A und B unbemerkt abgefangen, konnte sie Ae = Ea = gea und Be = Eb = geb errechnen. Kann sie Alices Chiffrat y‘ abfangen, ist sie in der Lage, es zu entschlüsseln: y · A–e = x · Ea · A–e = x. An Bob versendet sie die neu chiffrierte Version y‘‘ := x · Be . Bob hält E bekanntlich für Alices öffentlichen Schlüssel und hat damit Eb errechnet – glaubt er, dass y‘‘ von Alice stammt, entschlüsselt er arglos und korrekt y‘‘ · E–b = x · Be · E–b = x.

Zur Bedrohungsminderung müssen Alice und Bob sicherstellen, dass sie tatsächlich denselben Schlüssel Ab = gab = Ba verwenden. Das kann beispielsweise durch Vergleich der Hash-Werte ihrer Rechenergebnisse (Ab bzw. Ba ) auf einem unabhängigen Kommunikationskanal erfolgen – die „Woman-in-the-Middle-Keys“ Ea und Eb wären ja nur dann gleich, wenn zufällig e · (a – b) ≡ 0 mod g ist. Besser noch sollten sich Alice und Bob gegenseitig sicher authentifizieren.

Der Weg zu elliptischen Kurven

Nun lassen sich auf kunstvolle Weise Gruppen bilden, deren rechnerische Hintergründe noch wesentlich weniger durchschaubar sind als die bislang vorgestellten Einheitengruppen der primen Restklassenkörper. Ihre Konstruktion ist mathematisch deutlich aufwendiger, zum Ausgleich erfordern sie aber schon bei kleineren Parametern (sprich kürzeren Schlüssellängen) großen Rechenaufwand bei Angreifern: Die Rede ist von den sogenannten elliptischen Kurven.

Neal Koblitz und Victor S. Miller haben 1986/87 unabhängig voneinander vorgeschlagen, diejenigen Gruppen in der Kryptografie zu verwenden, die elliptische Kurven mit sich bringen. Da, wie im Folgenden erläutert wird, jede elliptische Kurve E sowohl über Q, R, C als auch über jedem Restklassenkörper Fp (also einem für jede Primzahl!) betrachtet werden kann, wird die genutzte Gruppe durch das jeweilige Paar (E, Q), (E, R), (E, C) bzw. (E, Fp ) bestimmt. Somit ergibt sich ein wesentlich größerer Vorrat an Gruppen als durch die alleinige Wahl etwa eines Moduls n.

Vom unendlichen Kontinuum zum endlichen Punktgitter

Im Vorgriff auf die kunstvolle Konstruktion dieser Gruppen soll schon jetzt darauf hingewiesen werden, dass diese sich nicht mehr direkt in den Einheitengruppen der Restklassen befinden. Vielmehr werden sie mithilfe eines Koordinatenkreuzes dargestellt: Die Elemente der Gruppe sind nämlich Punkte einer Ebene, die demnach mithilfe zweier Koordinaten (X|Y) angegeben werden – beide Koordinaten werden einem der bisher vorgestellten Körper entstammen. Dank der Rechenoperationen in diesen Körpern (und weiterer komplexer Überlegungen) wird eine Addition für diese Punkte definiert. Dabei muss man darauf gefasst sein, dass das Aussehen der „Ebene“ von dem Zahlkörper abhängt, den man für ihr Koordinatenkreuz zugrunde legt.

Der augenfälligste Wandel liegt darin begründet, dass die Primkörper Fp im Gegensatz zum Kontinuum der reellen Zahlengerade R nur endlich viele (nämlich p) Elemente haben. Während also das Koordinatenkreuz R × R durch die „vollständige“ zweidimensionale Ebene visualisiert wird, die sich kontinuierlich und endlos in beide Dimensionen erstreckt, wird das Koordinatenkreuz Fp × Fp durch ein quadratisches Gitter mit endlichen Ausmaßen visualisiert, in dem nur p2 Gitterpunkte als mögliche Punkte zur Verfügung stehen. Daher lassen sich Kurven in der Ebene R × R nur dann vollständig darstellen, wenn sie endliche Ausdehnung haben (wie z. B. ein Kreis). Andernfalls erscheinen sie nur in Ausschnitten, wie beispielsweise die Parabel in Abbildung 1 – auch Abbildung 3 gibt nur einen Ausschnitt des unendlichen Gitterpunktnetzes Z × Z wieder. Hingegen zeigen die Abbildungen 2 und 4 das jeweilige Koordinatenkreuz Fp × Fp vollständig.

Annäherung 1: Diskrete Parabeln

Der Wechsel des Rechenbereichs verändert also die Visualisierung entscheidend. Dieser Wandel soll zunächst an bekannten Beispielen demonstriert werden, damit seine Wirkung auf elliptische Kurven weniger „erschreckend“ ausfällt.

Die Gleichung y = x2 dürfte bekannt sein: Im gewohnten Koordinatenkreuz beschreibt sie eine Parabel, die sich aufgrund des Quadrierens nur oberhalb der x-Achse befindet (keine negativen y-Werte) und symmetrisch an der y-Achse gespiegelt ist.

Betrachtet man diese Funktion über einem Primkörper Fp , dann ändert sich die Darstellung grundlegend, wie Abbildung 2 beispielhaft für F29 zeigt: Die „Parabel“ zerfällt in ein Punktgebilde, das sich (bedingt durch die Modulorechnung) innerhalb eines Gitterpunktnetzes endlichen Ausmaßes befindet und kaum mehr an eine bekannte Parabel erinnert (höchstens noch in der Mitte in der Nähe des Nullpunkts). Einziger Trost: Die Symmetrie um die y-Achse bleibt erhalten, weil auch in dieser Rechenwelt unverändert x · x = (−x) · (−x) gilt.

Als Repräsentantensystem für Fp wurde in der Abbildung jenes gewählt, das auch negative Zahlen enthält und dessen Absolutbeträge möglichst klein sind, das also {0, ±1, ±2, ±3, …, ±(p − 1)/2 } umfasst. Darin steckt zwar eine gewisse Willkür, doch ändert eine andere Wahl (bspw. der Repräsentant p − 3 anstelle von −3, also insgesamt {0, 1, 2, …, p − 1}) nichts an den folgenden Beobachtungen. Die Quadranten der Grafiken würden lediglich auf andere Weise angeordnet.

Dass sich im diskreten Falle auch Parabelpunkte „unterhalb“ der x-Achse befinden, ist hierdurch leicht erklärbar und darf nicht überbewertet werden: Schließlich hätte man ja auch solche Repräsentanten für die Restklassen wählen können, die kein Minuszeichen tragen. Die Begriffe „positiv“ und „negativ“ spielen im diskreten Falle der endlichen Körper keine bedeutsame Rolle!

Annäherung 2: Diskrete Kreise

Sind Parabeln womöglich eigentümliche Gebilde und Kreise vielleicht robuster gegen die Zerschlagung der ganzen Zahlen in Restklassen? Einen Kreis mit dem Radius r beschreibt (nach dem Satz von Pythagoras) die Gleichung x2 + y2 = r2 . Wählt man für r verschiedene Radien, so erhält man mehrere, konzentrisch ineinander liegende Kreise.

Abbildung 3 veranschaulicht das in einem endlichen Ausschnitt der eigentlich unendlichen Matrix ganzer Zahlen: In jeder Zelle steht der Wert x2 + y2 , der sich aus den Werten von x und y im Matrixgitter errechnet. Die „x- und y-Achsen“ sind mit einem Rahmen umgeben und enthalten selbst bereits die Quadrate r2 = x2 + 02 = x2 (x-Achse) beziehungsweise r2 = 02 + y2 = y2 (y-Achse).

Die „Diskretisierung“ (durch die Beschränkung auf ganze Zahlen) spiegelt sich unmittelbar in der Verpixelung der farblichen Darstellung wider. Dennoch zeigt sich deutlich eine kreisförmig symmetrische Anordnung der Farben, die aus den Werten für die Quadratsumme (x2 + y2 ) hervorgeht. Vier ausgewählte Kreise zeigen das zugehörige Kontinuum, das entstünde, wenn man mit reellen (statt nur ganzer) Zahlen rechnen würde. Fährt man mit dem Auge diese farbigen Kreise ab, ist zu erkennen, dass es nur wenige diskrete Punkte gibt, die genau auf dem Kreis eines vorgegebenen Radius liegen: So hat beispielsweise die Gleichung x2 + y2 = 45 in jedem Quadranten nur zwei Lösungen in ganzen Zahlen (dunkelblau) – und diese beiden Lösungen gehen lediglich durch Vertauschen von x und y auseinander hervor.

Was bleibt von dieser Grafik, wenn man die Kreisgleichung nun „modulo p“ (mit einer Primzahl p) berechnet, also mit den Restklassen aus einem endlichen Zahlkörper Fp löst? Abbildung 4 illustriert, dass solche Kreise über dem endlichen Körper F29 in zwar schöne, doch gar nicht mehr kreisförmige Punktgebilde zerbröseln. In jeder Zelle steht dort anstelle der ganzen Zahl x2 + y2 die von ihr repräsentierte Restklasse x2 + y2 modulo p (die Summe x2 + y2 der Quadrate der Restklassen x und y).

Solange die Repräsentanten noch klein genug sind, sodass x2 + y2 noch kleiner als p ist, ähnelt die Werteverteilung noch dem gewohnten Kreis: Daher erinnert die Fläche nahe und rings um den zentralen Nullpunkt noch der Matrixdarstellung in Z (Abb. 3). „Weiter außen“ bleibt jedoch vom Kreis nichts Erkennbares übrig: Zellen mit gleichen Werten liegen keineswegs gleich entfernt vom Mittelpunkt. Einziger Trost: Die Symmetrie bleibt auch hier – der quadratischen Terme x2 und y2 wegen – erhalten.

Elliptische Kurven und ihre Gruppenstruktur

Ellipsen („zusammengedrückte“ Kreise) sind zwar Kurven, jedoch zählen sie nicht zu den elliptischen Kurven. Ellipsen sind Kurven zweiter Ordnung: Eine Gerade hat höchstens zwei Schnittpunkte mit einer Ellipse oder tangiert sie in einem Punkt oder lässt sie gänzlich unberührt. Elliptische Kurven sind hingegen sogenannte algebraische Kurven dritter Ordnung, welche (nach Standardisierung) die folgende Gestalt haben:

y² = x³ + ax + b

Ihr Name rührt daher, dass derlei Gleichungen bei der Berechnung von Bogenlängen auf Ellipsen ins Spiel kommen. Mit elliptischen Kurven haben Geraden bis zu drei Schnittpunkte, wie auch die folgenden Grafiken zeigen werden. Die Konstanten a und b unterliegen dabei noch einer Bedingung, damit die elliptische Kurve ausreichend schön und „geschmeidig“ wird (für Interessierte: –4a3 ≠ 27b2, um Singularitäten zu vermeiden).

Interessant ist nun, dass je nachdem, aus welchem Zahlkörper man die Lösungspaare (x|y) für die Gleichung zulässt, ganz andersartige, wenn auch nicht zusammenhangslose Forschungsgebiete entstehen: Infrage kommen auch hier der Zahlkörper R der reellen Zahlen, aber auch der Zahlkörper der komplexen Zahlen C und die nunmehr bekannten Restklassenkörper F_p – es sei nochmals daran erinnert, dass jede Primzahl ein solches, daher auch Primkörper genanntes Gebilde liefert. Mit der Zahl 0 (als Spiegelbild einer „unendlichen“ Primzahl) korrespondiert auf mystische Weise der Körper der rationalen Zahlen (aller ganzzahligen Brüche) Q.

Recht anschaulich ist der „reelle Fall“, in dem die Lösungspunk (x|y) der reellen Zahlenebene R × R entstammen – deshalb soll er auch im Folgenden zur Veranschaulichung dienen, obwohl er kryptografisch irrelevant ist. Denn es ist schön, eine Visualisierung im Hinterkopf zu behalten, bevor nach der Diskretisierung jede Anschauung kollabiert, wie schon anhand von Parabeln und Kreisen ersichtlich wurde.

Ein Punkt P = (x|y) der reellen Zahlenebene ist eben dann eine Lösung, wenn seine Koordinaten x und y die genannte Gleichung einer elliptischen Kurve erfüllen. Die Lösungsmenge („Lösungsmannigfaltigkeit“) ist dann eine schöne Kurve in der Ebene (dass dabei in Wahrheit die sogenannte projektive Ebene betrachtet wird, sei hier nur am Rande erwähnt). Abbildung 5 zeigt typische Formen in Abhängigkeit der Konstanten a und b: links die „vorgelagerte Halbinsel“ (oder „Kleiderbügel“ – aus einem Linienzug) und rechts die „Küste mit vorgelagerter Insel“ (zwei Linienzüge). Das mittlere Bild lässt erahnen, wie der Übergang vom einen zum anderen Typ vonstatten geht, wie also der Kleiderbügel eingeschnürt wird und plötzlich die Insel absondert.

Spezielle Addition von Punkten

Man erkennt: Eine Gerade, festgelegt durch zwei Punkte P und Q auf der Kurve, trifft dieses Gebilde höchstens in einem weiteren, einem dritten Punkt R. Nun soll eine Addition von Punkten, die sich auf dieser Kurve befinden, definiert werden. Doch Vorsicht: Diese Addition ist nicht die koordinatenweise Addition (wie etwa bei Vektoren), sondern eine ganz andersartige Verknüpfung, für welche die Eigenschaften elliptischer Kurven im Verborgenen eine wesentliche Rolle spielen. Man definiert hierzu, dass die Summe dreier Schnittpunkte einer Geraden mit der Kurve stets „null“ sein soll: 0 = P + Q + R. Diese Definition setzt implizit voraus, was nicht selbstverständlich ist: nämlich, dass man den Ausdruck „P + Q + R“ beliebig klammern darf, also (P + Q) + R = P + (Q + R) ist. Außerdem ist noch zu klären, was denn überhaupt unter der Null zu verstehen ist und wie man vom Punkt R zu seinem Inversen –R (= P + Q) gelangen kann – dazu gleich mehr.

Doch zunächst benötigt man noch eine Sonderfallbetrachtung: Wenn die bewusste Gerade einen Punkt P nur tangiert, dann wird diese Berührung als Schnittpunkt von P mit sich selbst, P demnach als zweifacher Summand P + P gedeutet. Diese Festlegung ist durchaus nachvollziehbar: Wenn die zwei Punkte P und Q, die eine Gerade bestimmen, auf der betrachteten Kurve immer näher zusammenrücken, dann verschmelzen sie im Grenzfall zu einem einzelnen Punkt auf der Kurve – dabei wird aus einer Geraden, die zuvor die Kurve zweimal geschnitten hat (Sekante), im Verschmelzungspunkt, in den sich beide Punkte hineinbegeben und deshalb doppelt gezählt werden, eine Tangente.

Einen Punkt P zu sich selbst zu addieren, heißt also, eine Tangente an ihn zu legen, ihn quasi zugleich als P und Q zu deuten und den „dritten“ Schnittpunkt mit der Kurve zu suchen, mit dem die definierende Gleichung P + Q + R = 2 · P + R = 0 gilt. Letztlich ist also der zu R inverse Punkt –R = P + Q = 2 · P zu bestimmen, denn schließlich soll ja eine Gruppenstruktur entstanden sein.

Doch was ist –R, also das Inverse eines Punkts R? Und wo befindet sich die Null (0)? Das kann hier nur angedeutet werden, weil diese Fragestellung mathematisch durch die projektive Ebene geklärt wird. Das Vorgehen lässt sich jedoch illustrativ veranschaulichen: Man nimmt dazu nämlich einen „Punkt O im Unendlichen“ hinzu, um die Null und mit ihrer Hilfe die inversen Punkte zu definieren. Achtung: Die Null der Gruppe (Punkt O) ist nicht der gewohnte Nullpunkt im Zentrum des Koordinatenkreuzes, O ≠ (0|0).

Die „senkrechte“ violette Gerade durch die beiden Punkte R und (im Vorgriff so bezeichnet) –R rechts in Abbildung 6 schneidet offenbar keinen dritten Punkt der Kurve. Sucht man einen dritten Schnittpunkt, kann man diesen sozusagen nur „jenseits endlicher Vorstellungsgrenzen“ finden: in der Utopie des Unendlichen. Dieser Punkt im Unendlichen (vgl. Kasten) oder unendlich ferne Punkt O stellt für die gewünschte Addition die Null dar, ergo gilt 0 = –R + R + O = –R + R + 0. Punkte, die symmetrisch zur x-Achse liegen, sind zueinander invers – ihre Summe ist 0 = O.

Zur Veranschaulichung: Dreht man in Abbildung 6 die Gerade PQR in Q gegen den Uhrzeigersinn, so „enteilt“ R auf der Kurve in Richtung unendlich, während sich P auf –Q zubewegt. Erreicht die Gerade die Senkrechte, „springt“ R dann quasi auf O, den unendlich fernen Punkt.

Man findet im Internet zahlreiche Grafiken und Videos, die diese Punktaddition auf elliptischen Kurven illustrieren. Es gibt auch interaktive Programme, mit denen man auf den Kurven experimentieren kann. Beispielhaft seien der „Elliptic Curve Plotter“ von Stefan Kebekus (https://cplx.vm.uni-freiburg.de/de/ecp-de/) und CrypTool1 (www.cryptool.org – im Menü Einzelverfahren/ Zahlentheorie interaktiv/Punktaddition auf Elliptischen Kurven…) genannt, mit dem auch die hier wiedergegebenen Bilder erzeugt wurden.

Analogon zum DLP

Tatsächlich ist es üblich, die beschriebene Verknüpfung von Punkten als Addition zu schreiben. Zudem ist sie (wie übrigens sämtliche in diesem Beitrag erwähnten Rechenverknüpfungen) sogar kommutativ (P + Q = Q + P), was nicht eben offenkundig ist.

Die Verknüpfung in den Einheitengruppen Fp * der Restklassenkörper Fp wird indessen multiplikativ notiert, da sie ja von der Multiplikation ganzer Zahlen herrührt. Das d-fache Produkt einer Restklasse mit sich selbst wird daher als Potenz notiert bd = b · … · b (d-maliger Faktor). Für den diskreten Logarithmus im Falle der Restklassen galt: Wenn bd = a, dann ist logb a = d.

Da die Verknüpfung von Punkten auf elliptischen Kurven als Addition beschrieben ist, wird die d-fache Verknüpfung eines Punkts mit sich selbst nicht als Potenz sondern als Skalarmultiplikation notiert: d · P = P + … + P (d-maliger Summand – dabei ist d zunächst eine natürliche Zahl). Dennoch ist es üblich, in diesem Zusammenhang die Begrifflichkeit des „Logarithmus“ beizubehalten und daher zu schreiben: Wenn d · P = Q, dann ist logP Q = d. Der Logarithmus liefert hier also die Antwort auf die Frage, wie häufig der Punkt P mit sich selbst addiert werden muss, damit Q als Ergebnis herauskommt – falls das nie passiert, ist der Logarithmus undefiniert.

Nun wäre streng genommen noch zu ergründen, weshalb diese seltsam anmutende Punktaddition assoziativ ist und die Punkte der Kurve auf diese Weise tatsächlich alle weiteren Forderungen an eine (sogar abelsche, also kommutative) Gruppe erfüllen. Die geometrische Addition müsste zudem in ein Formelwerk übertragen werden, um die Gleichungen nutzbar zu machen. All dies muss hier jedoch übergangen werden, da es mathematisch aufwendig ist.

Im Ergebnis stelle man sich vor, dass sich die Koordinaten (xS |yS ) eines Punkts S, der die Summe zweier Punkte P und Q ist (S = P + Q), mithilfe von Gleichungen aus den Koordinaten (xP |yP ) von P und (xQ|yQ) von Q berechnen lassen – wie diese Gleichungen aussehen, möge hier keine Rolle spielen. Wesentlich ist nämlich allein die Tatsache, dass sie die gewohnten Rechenarten enthalten, die sich (wie schon die Gleichung der elliptischen Kurve selbst) in beliebigen Zahlkörpern interpretieren lassen.

Kryptografie braucht endliche Körper

Für die Kryptografie ist der Fall von Interesse, dass die Koordinaten x und y der Lösungspunkte (x|y) in Körpern mit endlich vielen Elementen gesucht werden, also nicht in C, R oder Q, sondern typischerweise in den Galois-Feldern F_p, also den primen Restklassenkörpern.

Man spricht davon, dass man die Kurve (die Gleichung) über dem Körper F_p betrachtet.

An dieser Stelle wäre zu erwähnen, dass sich die bisher vorgestellten Primkörper F_p noch nahezu beliebig vergrößern lassen: Die endlichen Erweiterungen eines F_p lassen sich dabei als mehrdimensionale Räume F_p × F_p × … × F_p über dem Grundkörper F_p auffassen – sie haben eine endliche Dimension n und die Gesamtanzahl der Elemente dieser sogenannten Körpererweiterungen ist dann die Potenz pn . Entsprechend werden diese Körper mit F_p n oder auch mit GF(pn ) bezeichnet.

Tatsächlich finden die Körper GF(2n) in der Kryptografie häufig Anwendung, wie auch der in Teil 1 erwähnten TR 02102-1 des BSI zu entnehmen ist. Ihre Addition ist nämlich besonders einfach – für eine Zahl x aus einem solchen Körper GF(2n) gilt stets: 2 · x = x + x = 0. Für Zahlen x1, x2, …, xn aus diesem Körper errechnet man dann durch bloßes „Ausmultiplizieren“ (x1 + x2 + … + xn)2 = x1 2 + x2 2 + … + xn 2. Das gilt (mit derselben Begründung) auch in den Körpern GF(pn), wenn p an die Stelle der 2 tritt: p · x = 0 und (x1 + x2 + … + xn)p = x1 p + x2 p + … + xn p . Wegen dieser charakteristischen Eigenschaft endlicher Körper GF(pn) nennt man p auch ihre Charakteristik.

Der Vorteil dieser endlichen Körper mit diskreten Elementen besteht (wie eingangs erwähnt) darin, dass die für andere (kontinuierliche oder „dichte“) Rechenbereiche typischen Rundungsfehler entfallen. Der Preis dafür ist offenkundig: Die geometrische Anschauung findet dann nicht mehr im reellen Koordinatensystem R × R der Ebene statt. Vielmehr mutiert das Koordinatensystem zu einem Gitterpunktsystem F_p × F_p, wie es die nachfolgenden Grafiken nutzen.

Die Koordinaten eines Punkts P = (x|y) sind dann also Restklassen und ein Punkt aus dem Gitterpunktsystem F_p × F_p liegt genau dann auf der „Kurve“, wenn seine Koordinaten die Gleichung der elliptischen Kurve E erfüllen. Dies hat bedauerlicherweise zur Folge, dass die Veranschaulichung – wie schon bei Parabel und Kreis – „zerbröselt“: Die „Kurve“ ist kein Linienzug, sondern ein Punktgebilde und „Sekanten“ durch zwei Punkte oder gar „Tangenten“ an einem Punkt sind ihrer geometrischen Erkennbarkeit beraubt. Es stört aber andererseits die Rechnungen nicht, wenn man „heimlich“ die gewohnte Anschauung aus dem Reellen im Hinterkopf beibehält.

Eine Kostprobe soll dennoch mithilfe von Cryptool veranschaulicht werden: Abbildung 7 zeigt die elliptische Kurve y2 = x3 + 2x +3 über dem Galoiskörper F11. Man erkennt das Koordinatensystem, das keine kontinuierliche Ebene mehr andeutet, sondern diskret verteilte Gitterpunkte (x|y) umfasst – die Koordinaten x und y können nur Restklassenwerte von 0 bis 10 annehmen. Die Punkte zeigen an, was von der elliptischen Kurve übrig bleibt, wenn man ihr in dieser argen Weise mitspielt. Immerhin: Die waagerechte Symmetrieachse ist noch immer zu erkennen. Und im Bild gilt P + Q = S oder konkret (4|3) + (3|5) = (8|5). Ob das stimmt, ließe sich nur nachrechnen, wenn man die Gleichungen für die Punktaddition aufstellt, worauf hier ja (des Rechenaufwands wegen) verzichtet wurde.

Bleibt nochmals zu betonen, dass diese Gruppen tatsächlich endlich sind, denn auf der „diskretisierten“ elliptischen Kurve können ja nicht mehr Punkte liegen, als das gesamte Gitterpunktsystem überhaupt anbietet – und schon das sind nur p2 Punkte. Also muss jeder Punkt P eine endliche Ordnung ord(P) haben (denn die Anzahl der verschiedenen Vielfachen eines Punkts muss ja endlich sein – zur Erinnerung: die Ordnung eines Gruppenelements ist hier die kleinste natürliche Zahl n, für die n · P = 0 gilt, da in der additiven Gruppe die 0 das neutrale Element darstellt). Es gibt eine wesentlich schärfere Abschätzung für die Anzahl der Punkte auf einer elliptischen Kurve von Emil Artin und Helmut Hasse (1933), die zeigt, dass die Anzahl der Punkte in der Größenordnung von p liegt (nicht etwa von p2 ).

So wird erneut verständlich, dass man von einem diskreten Logarithmus spricht, denn die Gruppe, in der dieser Logarithmus gebildet wird, besteht ja aus den Punkten der elliptischen „Kurve“: Und die liegen, wie die Abbildungen im Falle der endlichen Körper F zeigen, deutlich getrennt voneinander, nämlich diskret, ebenso wie schon die Elemente der Einheitengruppen F* selbst.

Analog zu dem zuvor beschriebenen Verfahren lässt sich nun auch ein Kryptosystem mit Diffie-HellmannSchlüsselaustausch und ElGamal-Verschlüsselung auf diesen elliptischen Kurven etablieren.

Beispiel: Eine zyklische Kurve mit 28 Punkten

Als Beispiel soll die Gruppe zur Kurve E: y² = x³ + 11x + 20 über dem Restklassenkörper mod 23 dienen, also kurz (E, F₂₃). Sie besteht aus 28 Punkten, die allesamt „Vielfache“ des Punkts P = (10|7) sind. Sein 28-faches (also 28P) ist insbesondere die Null der Gruppe – sie befindet sich jedoch nicht im Gitterpunktsystem, sondern überall außerhalb und „nirgendwo“, eben als jener unendliche ferne Punkt O (in Abbildung 8 durch den überlagerten Kreis im Hintergrund des Gitterpunktsystems angedeutet – wie schon angemerkt, nicht zu verwechseln mit dem Ursprung [Nullpunkt] des Koordinatensystems der Restklassen).

Nochmals: Der gewählte Punkt P erzeugt die gesamte Gruppe G der elliptischen Kurve. Das tut nicht jeder Punkt der Gruppe: Die Vielfachen beispielsweise des Punkts Q := 4 · P sind 8P, 12P, 16P, 20P, 24P und 28P (= 0) – sie bilden also eine kleinere (ebenfalls zyklische) Untergruppe von G mit nur 7 Elementen.

Bemerkenswert ist die Rolle des Punkts 14 · P: Er ist der einzige, dessen y-Koordinate die Nullklasse 0 (mod 23) ist. Wenn man als Repräsentanten der Restklassen wie in Abbildung 8 die Zahlen von −11 bis +11 wählt, dann erhält der Punkt 14P eine zentrale Position auf der Spiegelachse (und seine Verdopplung 28P verschwindet in der unendlichen Weite außerhalb des Gitterpunktsystems). Verbindet man die Punkte ihrer Reihenfolge nach mit Linien, fällt auf, dass auch die Abfolge der Punkte einer Symmetrie folgt.

Die Parameter zur Auswahl einer solchen elliptischen Kurve sind die Primzahl p (für den Primkörper) sowie die beiden Kurvenparameter a und b – und auch die Wahl des „Basispunkts“ P (des erzeugenden Elements der Untergruppe als Basis des Logarithmus) spielt eine Rolle. Auf diese Weise erhält man eine über wältigende Auswahl von diskreten elliptischen Kurven und mit ihnen lauter verschiedene Gruppen. Zwar ist die abstrakte Struktur endlicher abelscher Gruppen sehr gut bekannt, aber wie sie sich konkret auf einer elliptischen Kurve wiederfindet, ist nicht eben leicht zu sehen.

Zahlenbeispiel: Die Elliptische Kurve sepc160k1

Christian Wuthrich hat in verschiedenen Vorträgen einen plastischen Eindruck anhand der Kurve sepc160k1 gegeben [2]: Diese elliptische Kurve wird durch die Gleichung y2 = x3 + 7 (a = 0 und b = 7) über dem Restklassenkörper Fp zur Primzahl

p := 2¹⁶⁰ – 2³² – 21.389 = 1.461.501.637.330.902.918.203. 684.832.716.283.019. 651.637.554.291

bestimmt. Die Anzahl der Punkte auf dieser Kurve (also die Anzahl der Elemente in der Gruppe G) ist nicht gering, sie beträgt

1.461.501.637.330.902.918.203. 686.915.170.869.725. 397.159.163.571 = p + 1 + 2.082.454.586.705.745.521. 609.279 =: q

und ist selbst eine Primzahl! Daher ist auch diese Gruppe zyklisch (so muss sogar jeder ihrer Punkte P ≠ 0 die gesamte Gruppe erzeugen!) und sieht „im Prinzip“ wie die additive Gruppe des Restklassenrings Z_q aus – dieses Wissen hilft aber nicht bei den komplexen Berechnungen in G.

Parameter und Politik

Tatsächlich ist Vorsicht geboten: Mit der Wahl der Parameter kann man – auch bei Wahl augenscheinlich hoher, standardkonformer Werte – „Pech“ haben und gewissermaßen eine Gruppe erwischen, die wenig Sicherheit bietet. Daher hat die rasante Entwicklung der Kryptologie dazu geführt, dass die Erforschung elliptischer Kurven ihre „Unschuld verloren“ hat, in deren sicheren Besitz sie viele Generationen von Zahlentheoretikern gewähnt haben. Der Mathematiker Godfrey Harold Hardy hielt etwa noch 1940 die Zahlentheorie für ein Gebiet, dessen Entrücktheit von jeder gewöhnlichen menschlichen Aktivität sie gentle and clean halten würde (vgl. [3]).

Weniger als ein halbes Jahrhundert später hält Neal Koblitz es für immerhin vorstellbar, dass die US-amerikanische National Security Agency (NSA) die Vorlage von Ergebnissen auf gewissen Gebieten der Zahlentheorie zwecks Durchsicht verlangt, bevor sie veröffentlicht werden (siehe Vorwort von [4]). Tatsächlich hat die Algorithmische Zahlentheorie (sozusagen die praktische, rechnerische Seite der Zahlentheorie) durch die Entwicklungen der letzten Jahrzehnte wesentlichen Auftrieb erhalten.

Um die Brisanz dieser Forschung anzudeuten, sei der ironische Titel eines „White Papers“ zitiert, das von einem Autorenteam um den Forscher Daniel J. Bernstein stammt: ”How to manipulate curve standards: a white paper for the black hat“ [5]. Auch der Artikel „Nach Snowden – Weniger Schlaf für Kryptoforscher“ von Monika Ermert (ein Gespräch mit der Kryptologin Tanja Lange [6]) beleuchtet diesen Aspekt. Detailliertere Ausführungen befinden sich zudem in [7], [8] und [9].

Empfohlene Schlüssellängen im Vergleich

Es mag zu guter Letzt einleuchten, dass die Primzahl p für elliptische Kurven über Fp bei Weitem nicht so hoch gewählt werden muss, wie wenn man eine ElGamalVerschlüsselung direkt in Restklassenkörpern Fp realisiert oder RSA einsetzt. Denn bei den elliptischen Kurven wird schließlich in einer Gruppe gerechnet, deren Punkte (Elemente) mit zwei Koordinaten angegeben werden, die den Restklassenringen entstammen und auf recht komplexe Weise miteinander verknüpft (addiert) werden. Bei RSA hingegen wird unmittelbar in den Restklassenringen gerechnet.

So kann kaum noch überraschen, dass für die Verfahren, die auf elliptischen Kurven beruhen, im Vergleich zu jenen, die (wie RSA) direkt in den Einheitengruppen von Restklassenringen ablaufen, niedrigere Schlüssellängen ausreichend sind, um das gleiche Sicherheitsniveau zu erreichen, wie aus Abbildung 9 hervorgeht.

Bedrohung durch Shors Algorithmen

Im ersten Teil dieses Beitrags wurde der Algorithmus vorgestellt, den Peter W. Shor 1994 in Abschnitt 5 seines Artikels „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer“ [10] beschrieben hat – er löst das Faktorisierungsproblem in polynomieller, also „effizienter“ Zeit, nutzt zwei Quantenregister und wird häufig als „der“ Shor-Algorithmus bezeichnet. In Abschnitt 6 desselben Artikels hat Shor jedoch einen zweiten Algorithmus vorgestellt, der drei Quantenregister nutzt und – unter gleichzeitiger Nutzung des ersten Algorithmus – das Problem des diskreten Logarithmus in effizienter Weise löst. Somit ist auch die Sicherheits-Grundlage von DH(M), ElGamal und ECC durch die Entwicklung hinreichend großer Quantencomputer bedroht.

Wann kommt die Quantum-Supremacy?

Bei allem gebotenen Respekt vor den Umwälzungen, welche die Quantentechnologie mit sich bringt, sobald sie Realität wird, ist doch inzwischen häufig zu lesen, dass sie die klassische „binäre“ Computertechnik nicht gänzlich verdrängen wird.

Die Schwierigkeiten, die mit der Realisierung der Quantencomputer verbunden sind, lassen sich einer Grafik des BSI entnehmen (Abb. 10 aus [11] mit freundlicher Genehmigung des BSI): Die Ansprüche an die Zahl der benötigten Qubits sind hoch, wenn Quantencomputer tatsächlich gegen die aktuellen Kryptoalgorithmen erfolgreich sein wollen. Darüber hinaus benötigt man jedoch auch noch mächtige Verfahren zur Fehlerkorrektur – denn wie die BitÜbertragung im klassischen Fall ist auch die Quantencomputer-Technologie fehlerbehaftet. Doch auch diese Fehlerkorrekturmechanismen scheinen zurzeit noch nicht ausgereift zu sein.

Abbildung 10 zeigt hier zweierlei:

• Die Anforderungen, welche die Berechnung eines diskreten Logarithmus (ECC, blau) beziehungsweise einer Faktorisierung (RSA, rot) bei jeweils „geeigneter“ Schlüssellänge stellen würden (farbige Kurven oben in der Grafik), befinden sich einige Zehnerpotenzen (!) entfernt von dem „gelben Bereich“, in dem sich die Forschung im Herbst 2017 (Zeitpunkt der Studie) bewegt hat. Auch bei zügigen Entwicklungsfortschritten dürfte es also noch eine ganze Weile dauern, in diesen Bereich vorzudringen – die BSI-Studie ging in etwa von einer Verdreifachung der nutzbaren Qubits jedes Jahr aus.
• Spart man Qubits, schnellen die Ansprüche an die Fehlerkorrektur in die Höhe – und umgekehrt (Verlauf der farbigen Kurven). Im Text der Studie heißt es dazu: „Der große Aufwand für Fehlerkorrektur macht es auf absehbare Zeit unwahrscheinlich und vermutlich auch wirtschaftlich uninteressant für akademische und industrielle Labors, einen kryptografisch relevanten Quantencomputer zu realisieren. Wenn jedoch eine große Industrienation ihre Forschungsanstrengungen auf dieses Ziel konzentrieren würde, ähnlich den Manhattan- und ApolloProjekten des 20. Jahrhunderts, so erscheint ein Quantencomputer mit wenigen Millionen physikalischer Qubits, der zumindest in 100 Tagen 2048-Bit RSA brechen kann, erreichbar, wenn auch die physikalische Fehlerrate angemessen sinkt und in einen Bereich von 1:10000 gebracht werden kann.“ [11]

So vielversprechend also die Perspektiven der Quantencomputer erscheinen, so herausfordernd sind doch zugleich die Hürden, die noch zu nehmen sind. Es bleibt spannend, wann die sogenannte Quantum Supremacy, also der Zeitpunkt einer Überlegenheit der Quantentechnologie, erreicht werden wird. Die Schätzungen selbst von Experten bleiben vorsichtig und vage. Ignacio Cirac, Direktor am Max-Planck-Institut für Quantenoptik in Garching, sagte beispielsweise 2015: „Ich bin überzeugt davon, dass sie [die Quantencomputer] gebaut werden, aber es wird vielleicht noch zehn, zwanzig oder sogar fünfzig Jahre brauchen.“ [12]

Fazit

Wieder einmal zeigt sich, wie weit der Weg zwischen theoretischer, visionärer Konzeption und praktischer Umsetzung in die harte Realität ist. Sollte der Zeitpunkt der Quanten-Überlegenheit noch länger auf sich warten lassen, ist dies andererseits kein Grund zur Beunruhigung, solange es für die Probleme des diskreten Logarithmus und der Faktorisierung keine effizienten Algorithmen auf der Grundlage „klassischer“ binärer Computer gibt: Dann nämlich können die Schlüssellängen beliebig weiterwachsen und mit ihnen das Sicherheitsniveau der etablierten Kryptoverfahren, denn die Folge der Primzahlen ist endlos und unerschöpflich (dank sei Euklids ungeheuerlicher Erkenntnis!).

Die im Jahre 2013 größte bekannte Primzahl war p=257 885 161–1 mit 17.425.170 Dezimalstellen. Am zweiten Weihnachtstag 2017 beschenkte Jonathan Pace im Rahmen des GIMPS-Projekts (Great Internet Mersenne Prime Search, www.mersenne.org) die Welt mit der 50. Mersenne’schen Primzahl 277 232 917–1 – sie hat 23.249.425 Dezimalstellen. Und am 7. Dezember 2018 fand Patrick Laroche auf seinem Rechner die 51. Mersenne’sche Primzahl 282 589 933 – 1 mit 24.862.048 Dezimalstellen, also rund anderthalb Millionen Dezimalstellen mehr als die vorige besitzt (siehe auch www.primzahlen.de). Um diese Primzahl ausgedruckt wiederzugeben, bräuchte man ein achtbändiges Werk mit je tausend Seiten pro Band. Vorläufig bleibt den aktuellen Verfahren also noch reichlich „Luft“ nach oben.

Eckart Begemann ist Senior Consultant bei Sopra Steria SE.

Literatur

[1] Eckart Begemann, Morituri te salutant! (1), Warum Quantencomputer heutige asymmetrische Kryptoverfahren bedrohen und wie deren jetziges Sicherheitsniveau begründet ist – ein Ausflug in die Mathematik, 2019# 1, S. 24

[2] Christian Wuthrich, Elliptic Curve Cryptography, Vortragsfolien, Mai 2010, www.maths.nottingham.ac.uk/plp/pmzcw/download/ecc.pdf

[3] Godfrey Harold Hardy, A Mathematician’s Apology (1940), University of Alberta Mathematical Sciences Society, 2005, www.math.ualberta.ca/~mss/misc/A%20Mathematician‘s%20Apology.pdf

[4] Neal Koblitz, A Course in Number Theory and Cryptography, 2nd Edition, Springer, 1994, ISBN 978-0-387-94293-3

[5] Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hülsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, Christine van Vredendaal, How to manipulate curve standards: a white paper for the black hat, September 2015, https://bada55.cr.yp.to/bada55- 20150927.pdf

[6] Monika Ermert, Nach Snowden – Wenig Schlaf für Kryptoforscher, Gespräch mit Tanja Lange, heise Security, September 2014, https://heise.de/-2392236

[7] Ralph-Hardo Schulz, Helmut Witten, Bernhard Esslinger, Rechnen mit Punkten einer elliptischen Kurve, LOG IN 181/182 (2015), Beitrag verfügbar via http://page.mi.fuberlin.de/rhschulz/Artikel_LogIn/Endfassung_LOG_IN_ Elliptische_Kurven.PDF

[8] Dan Shumow, Niels Ferguson, On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng, Vortragsfolien, August 2007, http://rump2007.cr.yp.to/15- shumow.pdf

[9] Marc Fischlin, Hintertüren und Schwächen im kryptografischen Standard SP 800-90A, in: Mitteilungen der Deutsche Mathematiker-Vereinigung, Band 22 (2014), Heft 1, S. 18, online verfügbar unter www.degruyter.com/downloadpdf/j/dmvm.2014.22.issue-1/dmvm-2014- 0012/dmvm-2014-0012.pdf

[10] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Paper, Version 2, Januar 1996, https://arxiv.org/abs/quant-ph/9508027

[11] BSI (Hrsg.), Frank K. Wilhelm, Rainer Steinwandt, Brandon Langenberg, Per J. Liebermann, Anette Messinger, Peter K. Schuhmacher, Entwicklungsstand Quantencomputer, Mai 2018, www.bsi.bund.de/DE/Publikationen/Studien/Quantencomputer/quantencomputer_node.html

[12] Roland Wengenmayr, Mit Quanten ist zu rechnen, in: Max Planck Forschung 2015/4, S. 54, online verfügbar über www.mpg.de/9906844/MPF_2015_4.pdf