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

Die Idee, Computer irgendwann auf der Grundlage quantenmechanischer Prinzipien zu bauen, hat der Physiker Richard Feynman bereits 1982 in den Ring geworfen. Drei Jahre später lieferte eine Arbeit von David Deutsch mit der QuantenTuringmaschine ein theoretisches Modell für Quantenrechner und zeigte, dass es Probleme gibt, die man damit effizienter lösen kann als mit klassischen Verfahren [4]. Seither hat sich sowohl in wissenschaftlichen als auch kommerziellen Labors viel getan, es gibt neue Beweise für die Leistungsfähigkeit der Quantencomputer [5,6] und schon 2016 hat IBM eine 5-Qubit-Maschine online genommen – aber wann hinreichend große programmierbare Systeme existieren werden, um der heute verbreitet eingesetzten asymmetrischen Kryptografie tatsächlich den Todesstoß zu versetzen, ist weiterhin unklar.

Manche Schätzungen sagen, das könne noch zehn oder mehr Jahre dauern (vgl. [2]) – schon von daher lohnt es sich also, die mathematische Basis für die Sicherheit der heutigen Algorithmen noch einmal genauer zu betrachten. Außerdem ist hierbei zu erkennen, wie und warum die „Quantenbedrohung“ zuschlagen könnte. Denn die Forschung intensiviert sich: In einem Manifest vom Mai 2016 (http://qurope.eu/manifesto) unterstützten mehr als 3400 Vertreter aus Wissenschaft und Wirtschaft ein „Flaggschiff-Programm für die Quantentechnologie“ der EU, das im Oktober 2018 mit einer Laufzeit von zehn Jahren und einem Budget von 1 Milliarde Euro gestartet ist (https://qt.eu). Als Langzeitziel (>10 Jahre) ist dort sogar die Entwicklung eines „universal quantum computer able to demonstrate the resolution of a problem that, with current techniques on a supercomputer, would take longer than the age of the universe“ aufgeführt [7].

Halbwertszeit läuft

Spezialisierte Einsatzzwecke dürften naturgemäß deutlich früher zu realisieren sein – so mehren sich auch die mahnenden Stimmen in Sachen Kryptografie: Das BSI erwähnt in seiner jüngsten Ausgabe der „Technischen Richtlinie BSI TR02102 Kryptographische Verfahren:

Empfehlungen und Schlüssellängen“ [8] das Wort „Quantencomputer“ 19-mal – jedes Mal mit Blick auf die umwälzenden Änderungen, die diese Technologie mit sich brächte, sobald sie hinreichend ausgereift wäre. Am deutlichsten wird die folgende Aussage: „Überdies würden alle in dieser Richtlinie empfohlenen asymmetrischen Verschlüsselungsverfahren unsicher werden, falls es zu erheblichen Fortschritten bei der Entwicklung von Quantencomputern käme.“ In der deutschen Zusammenfassung einer englischsprachigen BSI-Studie zum „Entwicklungsstand Quantencomputer“ [9] heißt es: „Diese Quantenprozessoren erlauben die Entwicklung und Evaluation von Quantenalgorithmen, sind aber noch in keiner Anwendung klassischen Rechnern überlegen. Führende Entwickler rechnen aber damit, dass dieser als QuantumSupremacy bezeichnete Schnittpunkt in wenigen Jahren erreicht wird.“

Viele vertraute Kryptoalgorithmen müssen also als „angezählt“ gelten – und zwar diejenigen, die auf dem sogenannten diskreten Logarithmus- oder auf dem Faktorisierungs-Problem beruhen, allem voran also die guten alten asymmetrischen Verfahren wie RSA und Diffie-Hellmann/ElGamal. Der vorliegende Artikel will die Mathematik, die bei diesen Algorithmen eine Rolle spielt, ein wenig greifbarer machen. Er befasst sich jedoch weder mit kryptoanalytischen Fragen noch mit Quantenkryptografie (siehe [1]), über deren Fortschritte erst jüngst wieder berichtet wurde (siehe [10]), noch mit Post-Quantum-Kryptografie (wie etwa mit dem McElieceKryptosystem, siehe auch [2,3]). Für Fragen der Standardisierung, Montgomery-Kurven sowie -Arithmetik sei beispielsweise auf [11] verwiesen.

Was ist sicher?

Bevor es um einzelne Algorithmen geht, soll noch kurz geklärt werden, wie hoch bei den Empfehlungen des BSI [8] eigentlich die Messlatte liegt: Was bedeutet dabei „sicher“? Dass Empfehlungen über Schlüssellängen und geeignete Parameter überhaupt erforderlich sind, liegt daran, dass die betrachteten Verfahren (bspw. RSA und elliptische Kurven – ECC) nicht „informationstheoretisch sicher“ sind. Bei dem Versuch, ein informationstheoretisch sicheres Kryptoverfahren zu brechen, würde ein Angreifer allein schon daran scheitern, dass ihm zu wenig Information vorliegt: Das Chiffrat samt den Informationen über den eingesetzten Algorithmus liefern dann keinerlei Hilfe bei dem Versuch zu entschlüsseln.

Ein informationstheoretisch sicheres Kryptoverfahren gibt so wenig (nämlich gar keine auswertbare) Information preis, dass es für einen Angreifer völlig gleichgültig ist, ob er diese Information nutzen will oder aber nur durch „Raten“ versucht, den Klartext zu erlangen. Die vorliegenden Informationen erhöhen seine Erfolgschancen nicht – die zur Verfügung stehende Rechenleistung spielt dabei keine Rolle. Die A-priori-Wahrscheinlichkeitsverteilung aller (sinnvoll) möglichen beziehungsweise die Wahrscheinlichkeit bestimmter Klartexte wird durch die Kenntnis des Chiffrats nicht verändert.

Dies ist aber bei den in Rede stehenden Verfahren keineswegs der Fall. Im Prinzip weiß jeder Angreifer, was zu tun ist: Im Falle von RSA muss man etwa „lediglich“ den berüchtigten Modul, der häufig mit n bezeichnet wird, in seine beiden Primfaktoren (p und q) zerlegen. Solche Aufgaben haben viele von uns schon einmal in der Schule gelöst – und bekanntlich ist es nur eine Frage der zur Verfügung stehenden Zeit (und Geduld), bis einem das gelingt.

Je mehr Rechenschritte man benötigt, um diese Aufgabe zu lösen, desto länger dauert es. Und genau hier wird die Messlatte für das gewünschte Sicherheitsniveau kryptografischer Verfahren angesetzt: Gemessen wird es in Bit, wobei „k Bit“ per Definition für 2k steht. Die Vorgabe des BSI lautet: Das Sicherheitsniveau soll mindestens 100 Bit betragen – für den Vorhersagezeitraum nach Ende 2022 werden 120 Bit empfohlen.

Dabei gilt die Festlegung: Ein kryptografisches Verfahren erreicht ein Sicherheitsniveau von „k Bit“, wenn mit jedem Angriff gegen das Verfahren, der sein Sicherheitsziel mit hoher Erfolgswahrscheinlichkeit bricht, Kosten verbunden sind, die zu 2k Berechnungen der Verschlüsselungsfunktion einer effizienten Blockchiffre (z. B. AES) äquivalent sind (vgl. Glossar von [8]).

RSA-Algorithmus

Die Hürde, die der hinlänglich bekannte Rivest-Shamir-Adleman-(RSA)-Algorithmus von 1977 der klassischen Computertechnik in den Weg legt, um Informationen zu schützen, ist das rechenaufwendige Faktorisierungsproblem. Es gibt Nerd-T-Shirts, die den Algorithmus in etwa so zusammenfassen:

n := p · q finde e und d mit e · d ≡ 1 mod ((p − 1) · (q − 1)) dann ist (xe)d ≡ x mod n

Mit der Eulerschen phiFunktion ϕ lässt sich dabei abkürzend schreiben:

ϕ(n) = (p − 1) · (q − 1)

Im Grunde handelt es sich dabei lediglich um eine gescheite Nutzung des sogenannten Chinesischen Restsatzes (vermutlich aus dem 3. Jhd. aus „Sun Zis Handbuch der Arithmetik“) im Verein mit dem kleinen Fermat’schen Satz. Um die Begrifflichkeit dieser Beziehungen zu verstehen, scheint ein kleiner Exkurs in die Zahlentheorie zu den sogenannten Restklassenringen unausweichlich.

„Wochentagsarithmetik“ mit Restklassen mod 7

Zu jeder natürlichen (also zu jeder positiven ganzen) Zahl m kann man sogenannte Restklassenringe definieren. Als Beispiel wird häufig das Rechnen mit Uhrzeiten herangezogen: Dann hat die Zahl m den Wert 12 (beim Blick auf das traditionelle Ziffernblatt) oder – bei 24-stündiger Zeitangabe – den Wert m = 24.

Hier soll einmal der Wert m = 7 gewählt werden – eine Anwendung dafür wäre der Zyklus der Wochentage. In Abbildung 1 sind „alle“ ganzen Zahlen der Reihe nach spaltenweise eingetragen, wobei nur sieben Zeilen zur Verfügung stehen. Das bewirkt, dass alle diejenigen Zahlen, die bei euklidischer Division durch 7 denselben Rest lassen, in einer Zeile nebeneinander stehen – sie werden daher (wie die Schüler einer Klasse) zu einer sogenannten Restklasse zusammengefasst. So, wie beim Zeit- und Raum-Management einer Schule die einzelnen Schüler nur marginal interessieren, hantiert man auch hier mit der ganzen Klasse – man „projiziert“ jede ganze Zahl auf ihre Teilbarkeitseigenschaften bei Teilung durch 7, verzichtet also auf die volle Information (nämlich das Wissen um die ursprüngliche Zahl) und interessiert sich nur noch für den Rest bei Division durch 7.

Die Klasse, in der die Zahl 3 „sitzt“, bezeichnet man dann beispielsweise mit einer fett gedruckten 3 und meint damit die gesamte Menge aller Zahlen, die mit der 3 zusammen in einer Tabellenzeile stehen. So gesehen ergibt sich die Gleichheit 3 = 10 – was schlicht besagt, dass die Zahlen 3 und 10 in derselben Tabellenzeile stehen, also bei Division durch 7 denselben Rest lassen.

Die Zahlen 3 oder 10 nennt man dabei einen Repräsentanten für ihre Klasse. Anders als in Kirche, Politik und Wirtschaft sind alle Klassenmitglieder repräsentabel, dürfen also als Repräsentanten auftreten. Allerdings eignen sich manche zum (Kopf-)Rechnen besser als andere – in Abbildung 1 sind sie hellgelb hinterlegt

Die Gleichheit von Restklassen (bzw. Kongruenz zugehöriger Repräsentanten) wird auch gerne so notiert:  3 ≡ 10 mod 7

Denn tatsächlich darf man nicht aus dem Blick verlieren, dass diese Gleichheit „modulo 7“ besteht, sich also auf den Modul m = 7 bezieht. Hätte die Tabelle eine andere Zeilenzahl, enthielten die Tabellenzeilen andere Zahlen und es läge eine andere Klassenaufteilung vor – und damit ein anderer Gegenstand der Betrachtung: Jede Zahl m liefert einen eigenen Gegenstand, andersartige Klassen und andersartige Gleichheiten von Klassen, andere Kongruenzen.

Den in Rede stehenden Modul m muss man also stets im Blick behalten. Daher sollte man ihn stets dazuschreiben – entweder in „klassischer Notation“

3 ≡ 10 mod 7 oder als 3 =7 10

Beispielsweise gilt ja die Gleichung 6 · 6 = 1 nicht für einen beliebigen Modul m, sondern nur für m gleich 5, 7 oder 35: Modulo 5 ist ja 6 = 1, sodass die Gleichung lediglich 1 · 1 = 1 bedeutet. Modulo 7 gilt hingegen 6 = –1, sodass sie hier (–1) · (–1) = 1 paraphrasiert. Mit diesen Repräsentanten notiert gilt das allerdings für jeden Modul, wie man durch Ausmultiplizieren nachrechnen kann:

( –1) · (–1) ≡ (m – 1) · (m – 1) = m2 – 2m + 1 = m · (m–2) + 1 ≡ 1 mod m

Rechnen mit Restklassen

Wesentlich ist nun, dass gewöhnliche Gleichungen ganzer Zahlen x beim Übergang zu ihren Restklassen x gültig bleiben (sog. Homomorphie). Beispielsweise gilt gleichermaßen

3 + 17 · 13 = 224 wie 3 + 17 · 13 = 224

Allerdings ist Letzteres dann keine Gleichung ganzer Zahlen mehr, sondern eine Gleichung zwischen Restklassen. Und in denen darf man auch kleinere Repräsentanten aussuchen, um die Gleichung zu „vereinfachen“ – mit m = 7 beispielsweise

3 + 3 · (–1) =0

Mit dieser Rechenmethode kann man beispielsweise sehr leicht Wochentage bestimmen: Angenommen, das Kick-off eines Projekts fand an einem Mittwoch (3) statt und nachfolgend gab es alle 13 Tage eine Telko: Auf welchen Wochentag fällt die 17. Telko? Antwort (entspr. obiger Gleichungen): auf einen Sonntag (0).

Macht man sich klar, dass für die Wochentagsberechnung (modulo 7) für ein gewöhnliches Jahr 365 = 1 gilt (366 = 2 bei Schaltjahren) und für Monate entsprechende Gleichungen (31 = 3 etc.), dann lässt sich im Kopf recht leicht ausrechnen, auf welchen Wochentag der 11. Juni 2020 fällt: 2 (1. Jan. 2019 = Dienstag) + 3 (+10 Tage) – 3 (3+0+3+2+3 für Jan.–Mai) + 2 (1 Schaltjahr) = 4 (Donnerstag)

Auch die Teilbarkeitsregeln aus grauer Schulzeit, die mithilfe von Quersummen formuliert werden, basieren auf dem Rechnen mit Restklassen: Eine Zahl ist durch 3 (bzw. 11) teilbar, wenn ihre Quersumme (bzw. alternierende Quersumme) durch 3 (bzw. 11) teilbar ist.

Dank der Homomorphie lässt sich mit den Restklassen („Tabellenzeilen“) in gewohnter Weise rechnen, genauer gesagt: Sie lassen sich addieren und multiplizieren und diese beiden Rechenarten (Verknüpfungen) vertragen sich sogar: Denn für beliebige Restklassen x, y, z gilt (x + y) · z = x · z + y · z – „Ausmultiplizieren“ und „Ausklammern“ bleiben nach dem Distributivgesetz erlaubt.

Die Addition hat dabei die Besonderheit, dass es ein neutrales Element, nämlich die Null (0) gibt, deren Addition jede Klasse unverändert lässt: x + 0 = x. Darüber hinaus gibt es zu jeder Klasse x eine inverse Klasse (–x), sodass die Summe beider gerade die Nullklasse ergibt: x + (–x) = x + (m – x) = m = 0 (mod m)

Da die Addition zudem assoziativ (x + (y + z) = (x + y) + z) ist, bilden die Restklassen bezüglich der Addition mit ihrem neutralen Element (Nullklasse) eine sogenannte Gruppe.

Auch die Multiplikation verfügt über ein neutrales Element, das „nichts tut“: 1 · x = x = x · 1. Allerdings ist, wie Beispiele im Folgenden zeigen werden, keineswegs sichergestellt, dass jedes Element ein Inverses (Reziprokes) x–1 bezüglich der Multiplikation besitzt, für das gilt

x · x–1 = 1 = x–1 · x

Bezüglich der Multiplikation bilden die Restklassen also im Allgemeinen keine Gruppe. Rechengebilde mit einer Addition und einer Multiplikation, für die das Distributivgesetz gilt und die eine additive (kommutative) Gruppe bilden und deren Multiplikation eine Eins (neutrales Element der Multiplikation) besitzt, nennt man Ringe. Man spricht daher vom Restklassenring zum Modul m.

Im Wochentage-Beispiel ist das der „Restklassenring modulo 7“. Wer die Tabelle aus Abbildung 1 ausschneidet und zu einer Rolle formt (gemäß dem Zirkelpfeil an der Seite), wird entdecken, dass alle ganzen Zahlen auf einem spiralförmigen Band angeordnet sind. Von der Seite betrachtet ergibt sich damit tatsächlich ein Ring, in dem alle Restklassen in einer Flucht stehen. Dieser Restklassenring wird in der technischen Richtlinie des BSI mit Z7 , allgemein mit Zm (Restklassenring modulo m) bezeichnet.

Nun muss man gewappnet sein, dass in diesen Restklassenringen ungewöhnliche Dinge passieren können. Das lässt sich etwa anhand der roten Nullen in der Multiplikationstafel für m = 12 (Abb. 2) verdeutlichen: So kann im Restklassenring modulo 12 (Z12) die Multiplikation zweier von Null verschiedener Zahlen trotzdem Null ergeben: 3 · 4 = 12 = 0 (mod 12) – ebenso 2 · 6 = 0 (mod 12). Das liegt offenkundig daran, dass die Zahl 12 keine Primzahl ist, sondern eine zusammengesetzte Zahl, die sich in Faktoren zerlegen lässt. Jeder „nicht-triviale“ Teiler von 12 (und auch alle Vielfache solcher Teiler) repräsentiert einen sogenannten Nullteiler in Z12.

Wenn also an den Modul m keine weiteren Anforderungen gestellt werden, erhält man „ungewöhnliche“ Rechengebilde. Wenn aber der Modul m außer sich selbst und der 1 keine weiteren (positiven, versteht sich) Teiler hat – mit anderen Worten: wenn der Modul eine Primzahl ist –, dann kehrt „ein wenig“ mehr Normalität ein: Die Restklassenringe Zp sind ganz besondere Objekte und werden deshalb auch mit dem Symbol Fp bezeichnet. Sie haben nämlich keine Nullteiler – mehr noch: In diesen primen Restklassenringen besitzt jede Klasse x ein Inverses (auch „Reziprokes“ genannt, x–1), mit dem das Produkt die Eins ergibt, also x · x–1 = 1 (in Fp = Zp mit einer Primzahl p).

In diesen primen Restklassenringen gibt es daher auch eine uneingeschränkte Division (eine Art „Bruchrechnung“) – allerdings mit der bekannten Ausnahme: Die Null kann niemals ein Reziprokes besitzen, weil sie ja jede Klasse annulliert: 0 · x = 0 (daran ist übrigens das Distributivgesetz schuld).

Einige Beispiele für die bisher gesammelten Erkenntnisse laute:

• In einem nicht-primen Restklassenring wie Z12 wird man keine „Zahl“ (keine Klasse) x finden, für die 3 · x = 1 gilt – einen „Bruch“ 1/3 gibt es in Z12 also nicht.
• Das hindert aber einzelne Klassen nicht daran, ein Reziprokes zu besitzen – in Z12 etwa 5 und 7, und zwar sich selbst: 5 · 5 = 25 = 1 mod 12 und 7 · 7 = 49 = 1 mod 12 (wobei 7 = –5 gilt).
• In Z34 wären 5 und 7 hingegen zueinander reziprok: 5 · 7 = 35 = 1 mod 34. Dasselbe gilt (also) auch in Z17. Allerdings haben 2 und 17 in Z34 keine Reziproken, wohl aber die 2 in Z17 (nämlich die 9). Die 17 repräsentiert (wie jede ungerade Zahl) in Z2 bereits selbst die Einsklasse.
• Im Restklassenring modulo 7 (Z7 ) hingegen gilt 3 · 5 = 15 = 1 mod 7, sodass dort die 5 die Rolle des Bruchs 1/3 übernehmen kann. Indem man modulo 7 rechnet, könnte man es sich (cum grano salis) so klarmachen: 1/3 = (1+2·7)/3 = 15/3 = 5 mod 7
• Allein die Division durch Null ist und bleibt ein Tabu (undefiniert)!
• In Z13 gilt 6 · 11 = 66 = 1 mod 13

Uneingeschränkte Division bedeutet: Für jede Restklasse a aus Zp , die nicht gleich 0 ist, gibt es zu einer beliebig gewählten Klasse b eine Klasse x mit a · x = b.

Dass dies tatsächlich zutrifft, lässt sich so einsehen: Für verschiedene Klassen x und y aus Zp müssen die Rechenergebnisse a · x und a · y verschieden sein, solange a ≠ 0. Wären zwei Rechenergebnisse gleich (a · x = a · y), so folgt 0 = a · x – a · y = a · (x – y) – das erzwingt aber (der Nullerteilerfreiheit in primen Restklassenringen wegen) die Gleichheit x – y = 0, also x = y.

Wenn man also mit x durch den gesamten Restklassenring Zp mit seinen p verschiedenen Klassen „spaziert“, dann müssen die Rechenergebnisse a · x auch sämtlich voneinander verschieden sein. Da es aber nur p verschiedene Klassen gibt, kommt man bei diesem Spaziergang bei jeder Klasse vorbei, auch bei einer beliebig vorgegebenen Klasse b. Das dabei beteiligte x ist die gesuchte Lösung und mithin das „Rechenergebnis“ der Division (des Quotienten) b/a.

Im Falle b = 1 ist die Lösung x gerade das Reziproke von a. Somit werden durch das Bruchsymbol in diesem Umfeld keine neuen, gebrochenen Zahlen eingeführt (mit 1/3 also nicht etwa eine Zahl, die zwischen 0 und 1 liegt), sondern lediglich eine schon existierende Restklasse bezeichnet – im Falle von 1/3 eben die durch 5 repräsentierte Restklasse, die den Kehrwert zur 3 bildet.

Ringe und Körper – mal nicht als Piercing

Wenn eine (kommutative) Addition und Multiplikation definiert sind, sodass die gewohnten Rechenregeln (Ausmultiplizieren bzw. Ausklammern, sprich Distributivgesetz) gelten, und eine uneingeschränkte Subtraktion existiert, dann spricht man – wie bereits erwähnt – von einem Ring. Ist darüber hinaus auch die Division uneingeschränkt möglich (mit Ausnahme durch die Null, versteht sich), so spricht man im Deutschen von einem Körper, im Englischen von einem Field. Daher erklärt sich die Bezeichnung Fp für die besonderen Restklassenringe, die dann auch Restklassenkörper heißen und von grundlegender Bedeutung in der Zahlentheorie sind.

Denn die Primzahlen bilden gewissermaßen das „Periodensystem der Elemente“ in der Arithmetik – zusammen mit der Null. Doch die bloßen Primzahlen – seltsame Geistwesen – finden erst in ihren jeweiligen Primkörpern eine leibhaftige Inkarnation. Dabei sollte man die Null (als ein Symbol für den „unendlich fernen Punkt“) in dieses merkwürdige Periodensystem der Arithmetik einbeziehen:

Wenn man nämlich mit p die unendliche Menge der Primzahlen in aufsteigender Richtung durchgeht (p also laufend größer wird), dann erhält die anfangs eingeführte Tabelle immer mehr Zeilen und die Differenz zwischen zwei benachbarten Zahlen innerhalb einer Zeile wird immer größer. Man könnte sagen, dass demnach die Anzahl der Spalten dadurch im gleichen Maße kleiner werden müsste – das macht aber bei unendlich vielen Spalten für uns endliche Wesen keinen merklichen Unterschied: Auch ein Anteil des Unendlichen ist noch immer unendlich.

Dennoch mag man sich vorstellen, dass die Primzahl p „im unendlich Fernen“ überraschenderweise den Restklassenring modulo 0 liefert, und dieser ist mit Z identisch: Jede Zahl sitzt allein in ihrer eigenen Restklasse, denn die euklidische Division durch Null (x = q · 0 + r) liefert zwar keinen eindeutigen Quotienten q, weshalb sie ja auch undefiniert bleibt, aber der Rest r ist nichtsdestoweniger eindeutig, nämlich stets gleich x, da x = q · 0 + x. In jeder Restklasse sitzt also nur ein Repräsentant – die Zahl selbst.

In der Tabelle bedeutet das, dass die Tabellenzeilen (Restklassen) nicht mehr unendlich viele Zahlen enthalten, sondern nur eine Zahl, die nur sich selbst repräsentiert. Es gibt dann also mit einem Mal nur noch eine Spalte und sämtliche ganzen Zahlen sind in diese eingetragen, ausgehend von der Mitte (0) in positive und negative Richtung. Die ganzen Zahlen Z bilden (im Gegensatz zu den Primzahlkörpern Fp ) „freiwillig“ keinen Körper: Sie müssen erst mithilfe der gewöhnlichen Brüche zum Körper Q der rationalen Zahlen vervollständigt werden. Daher übernimmt Q die Rolle des Körpers an der Stelle0 (in diesem Zusammenhang auch „der unendlich ferne Punkt“ oder die „unendliche Primstelle“ genannt) – ähnlich wie es die Primzahlkörper Fp für jede Primzahl p tun. Diese eigentümliche Art, im Unendlichen einen Punkt hinzuzunehmen, wird uns bei den Erklärungen zu elliptischen Kurven in Teil 2 dieses Beitrags wieder begegnen.

Die Restklassenkörper Fp heißen übrigens auch Galois-Körper oder -Felder – zu Ehren des Mathematikers Evariste Galois: Leben und Werk des durch einen Bauchdurchschuss im Alter von nur 20 Jahren verblichenen französischen Mathematikers des 19.Jahrhunderts eignen sich durchaus für eine dramatische Oper, sind allerdings auch legendenumwoben.

Nehmen wir wieder Kurs auf RSA: Sind p und q zwei Primzahlen, so lassen sich die beiden Restklassenkörper Fp und Fq betrachten und jeweils Paare (m, n) von Restklassen bilden, wobei m eine Restklasse modulo p und n eine Restklassen modulo q sei. Entsprechendes macht man bei der Beschreibung von Punkten oder Vektoren der zweidimensionalen Ebene mit zwei Koordinaten, in der man Vektoren koordinatenweise addiert. Im hier betrachteten Fall stammen die beiden Koordinaten zwar aus verschiedenen Wertebereichen, doch das behindert nicht das koordinatenweise Rechnen. Das entstehende Gebilde bezeichnet man mit dem kartesischen Produkt der Körper

Fp × F

In diesem Rechengebilde lassen sich Addition und Multiplikation koordinatenweise durchführen, sodass wir einen neuen Ring erhalten! Doch ist er wirklich neu?

Der Chinesische Restsatz

Der Chinesische Restsatz (CRS) besagt, dass dieses Gebilde im Prinzip nichts anderes ist als der bereits bekannte Restklassenring modulo (p · q), also Zpq. Wenn also n = p · q ist, dann kann man den Restklassenring Zn als das „kartesische Produkt“ der beiden Restklassenkörper Fp und Fq auffassen: Zn = Fp × F

Weil das so ist, sind auch die sogenannten Einheitengruppen dieser beiden Ringe „im Prinzip“ miteinander identifizierbar: Dabei besteht die Gruppe R* der Einheiten eines Ringes R (per Definition) aus allen seinen Elementen x (Zahlen, Klassen oder was auch immer), zu denen ein Reziprokes 1/x existiert. Wenn also in der Einheitengruppe R* eines Ringes nur die Null aussortiert ist (denn Division durch Null ist stets tabu), dann ist R schon ein Körper – Nullteiler hingegen können niemals Einheiten sein. Bei Zn = Fp × Fq sind die Nullteiler genau jene Paare (m, n), in denen eine der beiden Koordinaten 0 ist (oder gar beide) – alle übrigen Paare (von Restklassen) sind Einheiten.

In Z12 beispielsweise besteht diese Einheitengruppe (wie im Beispiel gezeigt) nur aus den vier Restklassen 1, –1, 5 (= –7) und 7 (= –5), das heißt: Z12* = {1, –1, 5, 7} – das sind gerade alle Zahlen, die teilerfremd zum Modul 12 sind. In der Multiplikationstafel für m = 12 (Abb. 2) erkennt man: Es sind genau die Spalten und Zeilen der Restklassen, in denen keine rote Null steht. Für Musikfreaks sei am Rande angemerkt: Das ist auch der „Grund“, weshalb neben der chromatischen Skala (also jeweils genau eine Taste auf- oder abwärts) allein der Quintenzirkel (jede siebte Taste aufwärts bzw. fünfte Taste abwärts) alle zwölf Klaviertasten komplett ausschöpft – Ganztonskala, Großterz- und Kleinterzzirkel tun dies indessen nicht.

Sobald der Modul m eine Primzahl ist, besteht die Einheitengruppe von Zm aus allen Klassen mit alleiniger Ausnahme der Nullklasse, also: Fp * = {1, 2, 3, 4, …, p–1}.

Die Anzahl der Elemente der Einheitengruppe von Zm bezeichnet man mit der Eulerschen phi-Funktion: ϕ(m) = #(Zm*) – für Primzahlen gilt also ϕ(p) = p – 1.

Wenn nun n = p · q, dann zeigt der Chinesische Restsatz, dass ϕ(n) = #Zpq* = #(Fp * × Fq *) = #(Fp *) × #(Fq *) = ϕ(p) · ϕ(q) = (p – 1) · (q – 1)

Kleiner Satz von Fermat / Satz von Euler

Nun gibt es eine wichtige Tatsache, die als der (kleine) Satz von Euler-Fermat bekannt ist: Für jede Restklasse x aus der Einheitengruppe eines Restklassenringes Zm gilt die bemerkenswerte Gleichung xϕ(m) = 1. Also hat man für eine beliebige ganze Zahl k die Beziehung x1+k·ϕ(m) = x·(xϕ(m) )k = x·1k = x – speziell also xp ≡ x mod p, was der kleine Satz von Fermat ist.

Somit wird verständlich, dass der Chinesische Restsatz und der Satz von Euler-Fermat begründen, weshalb gilt: wenn g ≡ 1 mod (ϕ(n)), dann xg = x in Zn

Also gilt für Zahlen e und d, deren Produkt e · d in die Rolle des g schlüpft: wenn e · d ≡ 1 mod (ϕ(n)), dann xe·d = x in Zn Und das ist letztlich genau der Aufdruck der Nerd-T-Shirts!

Schlüsselerzeugung und Bereitstellung des öffentlichen Teils

Voraussetzung für die Nutzung des RSA-Verfahrens ist eine natürliche Zahl n, die in nur zwei Primfaktoren zerfällt: n = p · q. Diese Primfaktorzerlegung bleibt aber verdeckt! Damit sind auch die Zahlen ϕ(n) = ϕ(p) · ϕ(q) = (p – 1) · (q – 1) unbekannt, die nur während der Schlüsselerzeugung genutzt werden. n fällt für jede Schlüsselerzeugung höchstwahrscheinlich verschieden aus, wenn man hinreichend große Primzahlen sucht. Gerechnet wird jeweils in der Einheitengruppe Zn *, die durch n als Teil des öffentlichen Schlüssels bestimmt ist. Nach dem CRS gilt: Zn * = Zp * × Zq *

Bobs Zertifikat besteht neben n aus zwei weiteren Zahlen d und e, für die gilt:

e · d ≡ 1 mod ((p – 1) · (q – 1))

Das Paar (n, e) bildet den öffentlichen Schlüssel (Public Key); d fungiert als Bobs geheimer Schlüssel (Private Key).

Die Exponenten d und e ermöglichen allerdings bei ungünstiger Wahl kryptoanalytische Angriffe (bspw. die „Wiener Attack“ durch Kettenbruchentwicklung) – daher müssen sie in Abhängigkeit von n „geeignet“ gewählt werden. Nach von Gathen [12] ist es in bestimmten Branchen gebräuchlich, für den öffentlichen Exponenten e die fünfte Fermat-Zahl 216 + 1 = 65537 zu wählen (die übrigens zusammen mit 65539 ein Primzahlzwillingspaar bildet, vgl. www.primzahlen.de). Dass dies eine Primzahl ist und die Größenordnung von n deutlich höher ausfällt, stellt im Übrigen sicher, dass sich für Bobs geheimen Schlüssel ein dazu passendes d mit der gewünschten Eigenschaft auch wirklich finden lässt.

Das BSI empfiehlt, bei einem Einsatzzeitraum bis Ende 2022 für den Modul n eine Länge von mindestens 2000 Bit zu wählen (über 600 Dezimalstellen), um das allgemein angestrebte Sicherheitsniveau von 100 Bit zu erreichen. Für den öffentlichen Exponenten e wird bei dieser Schlüssellänge die folgende Bedingung gefordert:

216 + 1 ≤ e ≤ 21824 −1

Für einen Einsatzzeitraum über das Jahr 2022 hinaus wird eine Länge von 3000 Bit empfohlen (über 900 Dezimalstellen).

Einsatz: Ver- und Entschlüsselung

Ist Alice im Besitz von Bobs öffentlichem Schlüssel (n, e), so ist dadurch geklärt, in welcher Gruppe G eine Nachricht (oder ein Nachrichtenblock) an Bob kodiert wird, nämlich in der (multiplikativ notierten) Gruppe G = Zn*. Zur Verschlüsselung potenziert Alice das Element x (den Klartext) mit Bobs öffentlichem Exponenten e (y = encr(x) := xe ) und sendet dieses Chiffrat y an Bob (vgl. Abb. 3)

Bob potenziert das erhaltene Chiffrat y in G mit seinem geheimen Exponenten d und erhält so den ursprünglichen Klartextblock x zurück:

yd = (xe )d = xe·d = x denn e · d ≡ 1 mod (ϕ(n))

Hybridverfahren und Signaturen

In der Praxis kombiniert man aus Effizienzgründen symmetrische und asymmetrische Verfahren: Die eigentliche Nachricht wird mit einem symmetrischen Schlüssel chiffriert. Lediglich dieser (ja vergleichsweise kurze) Schlüssel wird mithilfe von RSA verschlüsselt und der Nachricht beigefügt.

Aufgrund der Kommutativität (xe·d = xd·e) lässt sich das Verfahren auch „gespiegelt“ anwenden: Nur Bob kann mit seinem geheimen Schlüssel eine Nachricht z := xd erstellen. Mithilfe des öffentlichen Exponenten e kann aber potenziell jeder diese Nachricht wieder entschlüsseln. An die Stelle der Vertraulichkeit tritt damit die Verbindlichkeit: Jeder, dem die Entschlüsselung der Nachricht z mit Bobs öffentlichem Schlüssel e gelingt, kann sich ziemlich sicher sein, dass sie tatsächlich von Bob selbst stammt, weil (mit allergrößter Wahrscheinlichkeit) nur er den zu e gehörigen Exponenten d besitzt. Gleichwohl erhöht der Einsatz verschiedener Schlüsselpaare für Verschlüsselung und Signatur an dieser Stelle die Sicherheit.

Bedrohung: Faktorisierung von n

Die zu einem RSA-Schlüsselpaar gehörende Zahl e und der Modul n sind als öffentlicher Schlüssel bekannt. Wer nun imstande ist, n in seine Primfaktoren p und q zu zerlegen, die nach der Schlüsselerzeugung ja „vergessen“ wurden, kann auch ein zu e passendes d finden und mithin Nachrichten entschlüsseln. Die praktische und effiziente Durchführung der Primfaktorzerlegung – mit anderen Worten das Faktorisierungsproblem – ist also die rechentechnische Hürde, mit welcher der RSA-Algorithmus Informationen schützt!

Eigentlich würde es schon genügen, eine Zahl d mit der obigen Eigenschaft e · d ≡ 1 mod (ϕ(n)) zu finden – die Zerlegung des Moduls n in seine Primfaktoren könnte man sich dann ersparen. Dazu wäre es natürlich hilfreich, eine Zahl mit der Eigenschaft g ≡ 1 mod (ϕ(n)) zu kennen, denn dies hätte ja die Gleichung xg = x in Zn zur Folge, die letztlich zur Entschlüsselung verhilft. Wäre ϕ(n) dem Angreifer bekannt, so könnte er mit g = ϕ(n) + 1 beginnen. Da aber ϕ(n) unbekannt ist, hilft dieser Gedanke zunächst nicht weiter.

Shor-Algorithmus

Die Suche nach einer Zahl r mit xr = 1 in Zn weist dennoch in eine interessante Richtung: Die kleinste Zahl mit dieser Eigenschaft wird die Ordnung von x in Zn * genannt und mit ord(x) bezeichnet. Damit besagt der kleine Satz von Fermat-Euler, dass für jedes x aus Zn die Zahl ϕ(n) ein Vielfaches von ord(x) ist.

Z24* (aber auch in Z12*, Z6 *, Z4 * und Z8 *) ist beispielsweise ord(5) = 2 = ord(7), weil ja 5 · 5 = 1 = 7 · 7. Die Bestimmung der Ordnung einer Zahl x in den Restklassen modulo n bildet einen wesentlichen Schritt im ShorAlgorithmus, der dazu dienen kann, die Primfaktoren einer beliebigen Zahl n zu identifizieren. Dieser bereits 1994 von Peter Shor in einer ersten Version publizierte Algorithmus [13] kann die rechentechnische Hürde der Primfaktorzerlegung (Faktorisierung) effizient – nämlich in nur polynomieller Laufzeit – überwinden und folglich den Nutzen des RSA-Algorithmus empfindlich gefährden.

Eine wesentliche Komponente dieses Algorithmus ist allerdings eine probabilistische „Quantenkomponente“, die sich nur mit einem Quantencomputer implementieren lässt – und von IBM schon 2001 tatsächlich in einem 7-Qubit-Quantencomputer implementiert wurde [14]. Die benötigte Quantenkomponente ermittelt (nach genügend vielen Iterationen mit asymptotisch wachsender Wahrscheinlichkeit) mithilfe einer Quanten-FourierTransformation bei vorgegebener natürlicher Zahl n zu einer gegebenen Zahl x (1 < x < n) die Ordnung ord(x) der Restklasse x in Zn .

Um diese Aufgabe in Zn lösen zu können, benötigt der Quantencomputer allerdings log(n) Qubits. Die Systemvoraussetzungen des IBM-Experiments von 2001 setzten daher enge Grenzen und zaubern Securityfachleuten ein Schmunzeln ins Gesicht: Das n, das IBM in Primfaktoren zerlegt hat, war n = 15. Doch wer zuletzt lacht, lacht am besten …

Der Rest des Shor-Algorithmus ist klassisch (siehe Abb. 4): Sein Ziel ist es, sogenannte nicht-triviale Teiler von n zu finden, also Teiler x, die zwischen 1 und n liegen (1 < x < n). Es ist klar, dass man auf dieses Weise n iterativ in seine Primteiler zerlegen kann.

Das Ziel, Teiler von n zu finden, ist jedoch hoch gehängt – zumal, wenn n nur wenige Primteiler besitzt. Beispielsweise müsste man dann für die Zahl n = 1 125 897 758 834 689 genau einen der beiden einzigen Primteiler treffen – das sind übrigens p = 524 287 (219–1, die von Pietro Cataldi im Jahre 1588 entdeckte, damals größte bekannte Primzahl) und q = 2 147 483 647 (231–1, die von Leonhard Euler im Jahr 1772 entdeckte, damals größte bekannte Primzahl).

Die Suche nach einem Primteiler gleicht also in diesem (für RSA paradigmatischen, wenn auch viel zu klein skalierten) Beispiel der Suche nach zwei Nadeln im Heuhaufen, nämlich den beiden Primzahlen p (Cataldi, 1588) und q (Euler, 1772) unterhalb von n = p · q.

Um Teiler von n zu finden, genügt es jedoch, in einem ersten Schritt eine Zahl m zu finden, die gemeinsame (nicht-triviale, versteht sich) Teiler mit n hat – eine Zahl also, die nicht teilerfremd zu n ist. Dann nämlich lässt sich mithilfe des Euklidischen Algorithmus (Division mit Rest, in polynomieller Zeit!) in einem zweiten Schritt das Ziel erreichen, indem man den größten gemeinsamen Teiler ggT(m,n) bestimmt – und dieser ist ja insbesondere auch ein Teiler von n. Rekursiv eingesetzt liefert der Shor-Algorithmus also die Primfaktoren von n und stellt mithin eine (effiziente) Lösung des Faktorisierungsproblems dar.

An diesem Beispiel sei noch verdeutlicht, wie sehr die Effizienz durch die Suche nach einem derartigen m im ersten Schritt erhöht wird: Denn statt eine von zwei möglichen Nadeln im riesigen Heuhaufen finden zu müssen, gibt es nun wesentlich mehr Kandidaten, nämlich n − ϕ(n) = n − (p − 1) · (q − 1) = n − (n – p – q + 1) = p + q − 1 = 219 · (1+212) − 3 = 2 148 007 933, die zu den beiden wesentlichen Nadeln (Primfaktoren) führen. Diese Zahl ist zwar im Verhältnis zur Größe des Heuhaufens (dem Modul n) immer noch sehr klein, aber doch erheblich größer als zwei – und im ersten Schritt eine davon zu finden, genügt letztlich, um (nach einem gangbaren weiteren Schritt) ans Ziel zu gelangen, nämlich die beiden Primteiler p und q von n zu bestimmen.

Der Shor-Algorithmus wurde hier vorgestellt, weil er im Hinblick auf den Zeitpunkt der QuantumSupremacy von Interesse und sein klassischer Anteil gut zu verstehen ist. Es soll aber nicht verschwiegen werden, dass es weitere Angriffsstrategien zur Faktorisierung von Zahlen gibt – beispielsweise den Angriff nach Johan Håstad (www.nada.kth.se/-johanh) sowie den (p–1)-Algorithmus oder Pollard-rho-Algorithmus von John Pollard (https:// sites.google.com/site/jmptidcott2).

Eckart Begemann ist Senior Consultant bei Sopra Steria SE.

Literatur

[1] Ulrich Seyfarth, Quantenkryptografie, Akademisches Hirngespinst oder bald schon verbreitete Realität?,  <kes>2017#4, S. 16

[2] Leonie Bruckert, Jörn-Marc Schmidt, Post-Quanten-Kryptografie, Sicherheit in Zeiten des Quantencomputers, <kes> 2018#1, S. 54

[3] Stefan-Lukas Gazdag, Daniel Loebenberger, Post-Quanten-Signaturen, <kes>2018#1, S. 60

[4] Johannes Köbler, Olaf Beyersdorf, Von der Turingmaschine zum Quantencomputer – ein Gang durch die Geschichte der Komplexitätstheorie, in: Wolfgang Reisig, Johann-Christoph Freytag (Hrsg.), Informatik, Aktuelle Themen im historischen Kontext, Springer, Mai 2006, ISBN 978-3-540-32742-4, Paper online verfügbar unter www.informatik.hu-berlin.de/de/forschung/gebiete/algorithmenII/Publikationen/Papers/turing.pdf

[5] IBM, Scientists Prove a Quantum Computing Advantage over Classical, IBM Research Blog, Oktober 2018, www.ibm.com/blogs/research/2018/10/quantum-advantage-2/

[6] Sergey Bravyi, David Gosset, Robert König, Quantum advantage with shallow circuits, Science Vol. 362 (2018) Issue 6412, S. 308, Paper verfügbar via https://arxiv.org/abs/1704.00690

[7] European Union, Quantum Manifesto, A New Era of Technology, Mai 2016, https://qt.eu/app/uploads/2018/04/93056_Quantum-Manifesto_WEB.pdf

[8] BSI, Kryptographische Verfahren: Empfehlungen und Schlüssellängen, BSI-TR 02102-1 Version 2018-02, Mai 2018,  https://www.bsi.bund.de/DE/Publikationen/TechnischeRichtlinien/tr02102/index_htm.html

[9] 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

[10] Norbert Lossau, Die Geburtsstunde des Quanten-Internets, Welt+, Dezember 2018, www.welt.de/wissenschaft/plus185437084/Quanteninternet-Durchbruchfuer-die-abhoersichere-Kommunikation.html

[11] 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.fu-berlin.de/rhschulz/Artikel_LogIn/Endfassung_LOG_IN_Elliptische_Kurven.PDF

[12] Joachim von zur Gathen, Cryptoschool, Basic and advanced cryptographic methods with complete underpinnings, Springer, 2015, ISBN 978-3-662-48423-4

[13] 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

[14] IBM, IBM’s Test-Tube Quantum Computer Makes History, First Demonstration of Shor‘s Historic Factoring Algorithm, Pressemitteilung, Dezember 2001, www.ibm.com/press/us/en/pressrelease/965.wss