Zahlen, bitte! Von unbescholtenen und teuflischen Primzahlen
Primzahlen sind ein Grundbaustein vieler Verschlüsselungsverfahren. Nachdem Experten kürzlich gezinkte Primzahlen entwickelt haben, die dem Zinker das Knacken erleichtern, stellt sich die Frage, wo man unbescholtene Primzahlen herbekommt.
Moderne Verschlüsselungsverfahren beruhen im Kern auf mathematischen Problemen, für die man keine einfache Lösung kennt. Sie sind so lange sicher, bis ein Angreifer über genügend Rechenleistung verfügt, um sie "mit Gewalt" zu knacken – oder bis ein findiger Denker einen mathematischen Kniff findet.
Ein solches mathematisches Problem ist der diskrete Logarithmus: Wählt man eine große Primzahl p und einen Grundwert g, dann ist ga mod p einfach zu berechnen, aber der Rückweg von ga zu a nur mit extremem Rechenaufwand zu bewältigen. Auf der Schwierigkeit dieses Problems gründet sich unter anderem der weit verbreitete Diffie-Hellman-Schlüsseltausch, der beim Verbindungsaufbau mit einer HTTPS-verschlüsselten Website zum Einsatz kommt.
Die Sicherheit des Verfahrens steht und fällt mit der Qualität der großen Primzahl. Es gibt nämlich Primzahlen, für die der diskrete Logarithmus nicht genügend schwierig zu berechnen ist. Außerdem macht die Forschung Fortschritte. So zeigte Anfang Oktober ein Forscherteam von der University of Pennsylvania und der Université de Lorraine die Möglichkeit auf, die Verschlüsselung mit gezinkten Primzahlen zu schwächen.
Gezinkte Primzahlen
Das funktioniert vereinfacht ausgedrückt so: Für manche Primzahlen gibt es einen schnelleren Algorithmus für die Berechnung des diskreten Logarithmus, der aber zur Primzahl passende geheime Zutaten benötigt. Wer die Verschlüsselung schwächen will, sucht sich die geheimen Zutaten aus und erzeugt eine dazu passende Primzahl. Dieser kann nach heutigem Kenntnisstand niemand ansehen, dass es dazu die geheimen Zutaten gibt. Wenn es also gelingt, diese Primzahl für Verschlüsselung in Umlauf zu bringen, kann der Besitzer der geheimen Zutaten die Verschlüsselung knacken.
Und hier wird es spannend: Woher weiß man, dass eine Primzahl nicht gezinkt ist, wenn man es ihr doch beweisbar nicht ansehen kann? Ein möglicher Weg ist, sie einfach selbst zu erzeugen – als Betreiber eines Web-Servers könnte man das tun und wäre sich dann selbst sicher. Aber wie macht man anderen glaubwürdig, dass sie sich auf die Unbescholtenheit einer Primzahl verlassen können?
Unbescholtene Primzahlen
(Bild: xkcd )
Der allgemein anerkannte Weg dafür ist, die Entstehung der Primzahl nachvollziehbar zu machen. Idealerweise ist die Primzahl einfach eine Zufallszahl, aber echten Zufall könnte keiner nachträglich beweisen. Daher verwendet man ein pseudo-zufälliges Verfahren: Ausgehend von einem Startwert (seed) erzeugt ein komplizierter, aber dokumentierter und nachvollziehbarer Algorithmus die Primzahl. Den Startwert selbst wählt man zufällig und veröffentlicht ihn zusammen mit der Primzahl. Das macht glaubwürdig, dass die Primzahl nicht gezinkt ist, denn der Pseudo-Zufalls-Algorithmus macht es praktisch unmöglich, zu einer gewünschten Primzahl einen Startwert zu finden. Dafür ist er absichtlich kompliziert konstruiert unter Verwendung einer kryptografischen Hash-Funktion. Jeder kann sich aber von der Unbescholtenheit einer Primzahl überzeugen, indem er ausgehend vom veröffentlichten Startwert den Pseudo-Zufalls-Algorithmus anwendet.
Nachvollziehbare Zufälligkeit der Parameter bürgt also für die Sicherheit von Kryptosystemem, ist aber längst nicht überall gegeben. So haben laut den oben zitierten Forschern sowohl Frankreich als auch China elliptische Kurven für die Verschlüsselung standardisiert, ohne die Herkunft der Parameter zu rechtfertigen. RFC 5114 beschreibt einge Parametersätze für den Diffie-Hellman-Schlüsseltausch, deren Entstehung ebenfalls nicht nachvollziehbar dokumentiert ist.
Guter Leumund
Es gibt noch eine andere Idee, für eine Primzahl zu bürgen: Eine dokumentierte Herleitung aus einer Zahl, die über jeden Zweifel erhaben ist. Die mathematischen Konstanten e und π haben in dieser Hinsicht einen wirklich guten Leumund, denn die kann sich keiner ausgedacht haben, um ein Kryptosystem zu knacken.
Die "Oakley Groups" sind eine Sammlung von Primzahlen, die sich auf nachvollziehbare Weise aus den Nachkommastellen von π ableiten und sind seit Jahrzehnten in anerkannte Kryptostandards wie SSH und IKE (IPSec) eingebaut. Der Entwurf des TLS-1.3-Standards lässt für den Diffie-Hellman-Schlüsseltausch nur noch fünf sichere Primzahlen mit 2048 bis 8196 Bit zu, die sich aus der unbestechlichen Zahl e herleiten.
Teuflische Primzahlen
(Bild: J.A.S. Collin de Plancy, Dictionnaire Infernal, Paris : E. Plon, 1863)
Und was ist mit der Primzahl 1000000000000066600000000000001? Sie ist offensichtlich teuflisch und sollte vielleicht gerade deshalb als unbescholten gelten. Der Autor Clifford A. Pickover hat sie als Belphegor's prime number bezeichnet, nach einem der sieben Höllenfürsten der christlichen Mythologie. Sie ist für Krypto-Zwecke allerdings viel zu klein. Aber es gibt auch größere Primzahlen dieser Bauart. Die nächste lautet
100000000000000000000000000000
000000000000066600000000000000
00000000000000000000000000001
mit jeweils 42 Nullen links und rechts vom Biest, weitere haben 506, 608, 2472, 2623 und 28291 Nullen. Ob darunter nun eine für Krypto-Zwecke teuflisch gut geeignete Primzahl ist, müsste die Fachwelt vielleicht mal untersuchen. (bo)
