Mathematik und Geheimnisse

Verschlüsselung, Primzahlen, elliptische Kurven, Gitter und Codes

Vortrag anläßlich der Hamburger Universitätstage am 16.11.1999 von Rolf Berndt (unter Mitwirkung von Florian Berndt)

Es geht natürlich darum, den komplizierten Titel zu erläutern, also, um die Übermittlung von Nachrichten oder – wie heute immer öfter gesagt – Informationen. Dabei werden hier insbesondere zwei Gesichtspunkte verfolgt

Nur ein dazu autorisierter Empfänger soll die übermittelte Botschaft lesen können. Stichworte: Ver- und Entschlüsselung.
Der zu übermittelnde Text soll so „kodiert“ werden, daß das Ergebnis möglichst unempfindlich ist gegen Fehler bei der Übertragung. Stichwort: Irrtum korrigierende Codes.

Beide Gesichtspunkte hatten schon immer besonders in der Diplomatie und beim Militär eine hohe Bedeutung, die aber jetzt im Zeichen der Informationsgesellschaft glücklicherweise noch ganz allgemein eine wirtschaftliche Dimension bekommen hat. Dabei gibt es neben und im Verein mit technischen Fragen aber auch interessante und geheimnisvolle rein mathematische Probleme, über die ich hier zumindest in Teilen berichten möchte. Und zwar tangiert das Thema verschiedene Gebiete in der Mitte und am Rande der Mathematik, nämlich (nach Bauer [Ba] S.3) Zahlentheorie, Gruppentheorie, Kombinatorik, Logik, Komplexitätstheorie, Ergodentheorie und Informationstheorie. Außeracht gelassen wird hierbei ein dritter Gesichtspunkt, nämlich der der Autorisierung einer übermittelten Nachricht, die dem Empfänger die Möglichkeit gibt zu erkennen, daß sie tatsächlich von dem von ihm vermuteten Absender kommt. Diese Problematik gewinnt zunehmende Bedeutung und wird mit ähnlichen Überlegungen angegangen wie der hier als erste aufgeführte Gesichtspunkt.

2

true

Inhalt

Zur Kryptologie und ihrer Geschichte

Statt Definitionen wird hier zur Einstimmung zunächst ein konkretes Beispiel gegeben.

Die Goldkäfer-Geschichte von Edgar Allen Poe

In einer seiner Kurzgeschichten, „The Goldbug“, beschreibt E. A. Poe 1843 als Ich-Erzähler seine Bekanntschaft mit dem fast als Einsiedler lebenden Legrand, der allein mit seinem schwarzen Diener auf einer einsamen Insel an den Küste Neuenglands wohnt. Eines Abends berichtet Legrand dem Erzähler, der bei ihm vor dem Lagerfeuer zu Gast ist, von einem sonderlichen Fund, den er tagsüber gemacht hat: einen goldenen Käfer. Zur näheren Beschreibung malt Legrand diesen Käfer. Der Erzähler glaubt in der Zeichnung jedoch mehr einen Totenkopf als einen Käfer zu erkennen und in einem Streit über die Malkünste Legrands endet der Abend. Einige Wochen später wird der Erzähler von Legrands aufgebrachtem Diener gebeten, ihm auf die Insel zu folgen. Legrand sei wie besessen und wolle ihn unbedingt sehen. Auf der Insel angekommen überredet Legrand seinen Gast, an einer nächtlichen Wanderung teilzunehmen. Ohne Erklärung rüstet Legrand alle mit Schaufeln und Laternen aus und nimmt den Goldkäfer, an einer Schnur hängend, mit sich. Wie eine Wünschelrute läßt er diese vor sich her baumeln und weist seinen zwei Begleitern schließlich den Weg zu einem auffallenden Baum. Hier angekommen bittet er seinen Diener, auf den Baum zu klettern. Der Diener, der seinen Herren immer noch für verrückt hält, ist umso überraschter, auf dem Baum einen Totenkopf zu finden. Nun bittet Legrand seinen Diener, den Goldkäfer durch das linke Auge des Totenkopfes herabzulassen. Von diesem Punkt aus nimmt Legrand maß und bittet seine Begleiter, ihm beim Graben zu helfen. Nach Stunden ungeduldiger Suche stoßen sie schließlich auf Gebeine - und eine schwere Truhe, gefüllt mit Gold und Edelsteinen...
Als der Schatz geborgen ist, löst Legrand das Rätsel, wie er zu diesem Schatz geführt wurde: Das Pergament, auf dem er das Bild des Goldkäfers beim letzten Besuch des Erzählers gemalt hatte, hatte er am selben Tag am Strand gefunden. Erst durch den Kontakt mit der Wärme des Lagerfeuers hatten sich auf dem Papier die Umrisse eines Totenkopfes gezeigt und nach längerer Bemühung hatte Legrand noch einen Text, unterzeichnet mit einer Ziege, dem Pictogramm des berühmten Piraten Kapitän Kidd zum Erscheinen gebracht. Dieser Text bestand jedoch nur aus 203 kryptischen Zeichen.
Erst durch genaue Analyse der Häufigkeit und Struktur der Zeichen und dem schrittweisen Entschlüsseln gelang es Legrand in dem kurzen Text die Wegbeschreibung zu dem Goldschatz zu erkennen.

Und zwar sah der Text so aus:

$53‡‡†305))6*;4826)4‡.)4‡);806*;48†8¶60))85;1‡(;:‡*8†83(88)5*†
;46(;88*96*?;8)$$*‡(;485);5*†2:*‡(;4956*2(5*—4)8¶8*;4069285);)
6†8)4‡‡;1(‡9;48081;8:8‡1;48†$$85;4)485†528806*81(‡9;48;(88;4(‡?3
4;48)4‡;161;:188;‡?;$

Legrand schloß aus der Assoziation Kidd und Ziege, daß es sich hier nicht um einen spanischen oder französischen sondern um einen englischen Text handeln müßte. Im Englischen ist das „e“ der häufigste Buchstabe und „the“ das häufigste Wort aus drei Buchstaben. Im Text kommt nun das Symbol 8 am häufigsten vor (nämlich 33 mal) und die Kombination ;48 (nämlich 7 mal). Mit Hilfe dieser und ähnlicher Schlußfolgerungen gelang Legrand schließlich die Entschlüsselung der Botschaft:

„A good glass in the Bishop's hostel in the Devil's seat – forty-one degrees and thirteen minutes – northeast and by north – main branch seventh limb east side – shoot from the left eye of the death's-head – a bee-line from the tree through the shot fifty feet out.“

Einige Begriffe

In der Wissenschaft „um die Geheimnisse“, der Kryptologie, steckt das griechische Wort „Kryptos“ = versteckt. Sie unterteilt sich heute in Kryptographie und Kryptoanalyse, wobei sich die Kryptographie mit den Methoden der Verschlüsselung beschäftigt und die Kryptoanalyse mit denen der unberechtigten(!) Entschlüsselung sowie mit Verfahren zur Sicherung gegen eine solche. Zusammen mit der meist erforderlichen Übermittlung der Nachricht kann dies in folgendem Schema veranschaulicht werden. (s. Ebeling [Eb] S.5)

$\begin{array}{lcr}
& \mbox{Verschlüsselung} & & & & \mbox{Entschlüsselung}\\
a & &f(a) & \mbox{Informationskanal} & \tilde f(a) & & a'\\
& \mbox{Kodierung} & & & & \mbox{Dekodierung} \end{array}
$

Die Nachricht $a$ sei aus einem Raum $V∗$, sie besteht aus Wörtern, die wiederum aus Buchstaben $a_{i}∈V$ bestehen (etwa den Buchstaben des deutschen Alphabets). Die Verschlüsselung oder Kodierung verwandelt die einzelnen Buchstaben (der Einfachheit halber, es können auch ganze Wörter genommen werden) in Elemente $f(a)$ einer (möglicherweise) neuen Menge $C$, die aus irgendwelchen Symbolen, also etwa aus Ziffern, wieder aus Buchstaben oder Morsezeichen bestehen mag. Die so abgebildeten Nachrichten $a$ mögen dann in einer Menge $C∗$ landen. Die derart verschlüsselten Nachrichten $f(a)$ werden dann etwa per Post, Telegraph, Funk oder Internet übertragen. Dies wird hier durch den Übergang $f(a) \mapsto \tilde f(a)$ symbolisiert. Zuletzt geht es darum, dies $\tilde f(a)$ wieder zu entschlüsseln und daraus wieder einen Text $a'$ zu machen, der (etwa) aus Buchstaben aus $V$ besteht. Als eine Variante des Problems der Kryptographie, eine Nachricht für einen nicht autorisierten unleserlich zu machen, gibt es die Steganographie („steganos“=verdeckt), bei der es um die Kunst geht, das Vorhandensein einer Nachricht selbst zu verbergen. Dass sich Kryptographie und Steganographie auch gut ergänzen können, haben wir in Poe's Geschichte eben gesehen: Die Verwendung unsichtbarer Schrift, die erst bei Wärmeeinwirkung sichtbar wird (Milch und Zwiebelsaft soll das schaffen), ist eine klassische Methode der Steganographie. Die Symbole wiederum bilden eine sogenannte monoalphabetische Geheimschrift, die dann von Legrand einer Kryptoanalyse unterzogen wird.

Zur Geschichte

Die Wörter „cryptographia“ sowie „cryptologia“ werden (s. [Ba] S.23) John Wilkins (1641) zugeschrieben, einem der Gründer der Royal Society in England, das Wort „cryptography“ Thomas Browne (1658), einem Arzt und Schriftsteller, das Wort „steganographia“ dem Mönch Johannes Trithemius (1508).
Viel größere Verwendung als in der Belletristik – wie in Poe's Geschichte – fanden Kryptographie und -analyse natürlich im Rahmen der Diplomatie und der Nachrichtendienste, besonders im Kriegsfall. Bauers Buch „Decrypted Secrets“ [Ba] ist voll von Beispielen und bisweilen tragikomischen Geschichten. Als Abriß davon sei hier nur berichtet, daß die Benutzung von Geheimschriften bis ins Altertum zurückreicht. In der Bibel ist in Passagen eine Hebräische Geheimschrift „atbash“ zu finden, die auf der Umkehrung des Alphabets beruht. So wird in Jeremia 25,26 das Wort Babel verschlüsselt zu Sheshak (s. [Bi] p.325, in meiner Lutherbibel steht allerdings sesach.).

Berühmt geworden ist die von Caesar benutzte Verschlüsselung: sie beruhte auf der Ersetzung eines jeden Buchstabens einer Nachricht durch den im Alphabet viertnächsten Buchstaben, also etwa

auto → EYXS

In Europa wird der Ursprung für das erneute Aufkommen von Geheimschriften in der italienischen Renaissance gesehen. Von dem italienischen Architekten L.B. Alberti wurde die sogenannte polyalphabetische Verschlüsselung, das Grundprinzip aller modernen Verschlüsselungen, erdacht. Verbreitet hat diese Methode der französische Diplomat Blaise de Vignière. Er entwarf eine Tabelle, anhand derer ein Text per Schlüsselwort verschlüsselt werden konnte. Statt eines festen Wertes, wie bei Caesar, wird der jeweilige Wert eines Buchstabens im Schlüsselwort addiert. Wäre das Schlüsselwort etwa Banane, wird der erste Buchstabe im Text um zwei Stellen im Alphabet verschoben (b=2), der nächste um einen (a=1), der dritte um 14 (=n) usw., also etwa

auto → CVKP

Auf demselben Prinzip basiert auch die im zweiten Weltkrieg berühmt gewordene deutsche elektrische Verschlüsselungsmaschine Enigma (vgl. [Ba]). Durch polyalphabetische Algorithmen wurde der verschlüsselte Text für Kryptoanalysten schwer zu entschlüsseln. Alte Verschlüsselungen konnten recht einfach durch linguistische Untersuchungen, die zum Beispiel auf die Häufigkeit der Buchstaben und Silben zurückgreifen, entschlüsselt werden. Diese Methoden entsprechen denen, die Forscher anwenden, um Sprachen des Altertums zu entziffern, so wie es etwa Champollion tat um die Hieroglyphenschrift auf dem Rosette-Stein zu entziffern. Lesenswert dazu scheint mir auch das Buch von Coe [Co] über die Entschlüsselung der Maya-Schrift. Noch unentschlüsselt ist der Text auf der Phaistos-Scheibe (vgl. [Ba]).

Polyalphabetische Verschlüsselungen sind da empfindlicher. Aber auch für die Entschlüsselungen wurden Maschinen erdacht, oder es wurde bisweilen einfach das Schlüsselwort oder bei mehreren Schlüsselwörtern die Abfolge der Wörter abgefangen. So wurden die prinzipiell sehr sicheren Enigma-Verbindungen ab 1942 fast ausnahmslos abgehört. Viel mehr dazu und zu weiteren Verschlüsselungsverfahren, die etwa auf Permutationen beruhen, ist bei Bauer [Ba] zu finden.

Asymmetrische Verschlüsselung: das RSA-Verfahren

Schlüsselwörter sind generell eine Schwachstelle in klassischen Kryptoverfahren. Fallen sie in die Hände des Gegners, ist jede Geheimhaltung verloren. Erst 1978 wurde die nach den Autoren Ronald L. Rivest, Adi Shamir und Leonard M. Adleman „RSA“ benannte Methode einer asymmetrischen Verschlüsselung erfunden. Sie beruht auf der mysteriösen Tatsache, daß es relativ leicht ist, bestimmte mathematische Operationen durchzuführen, jedoch unverhältnismäßig schwer, diese umzukehren. Grundlage dieses Verfahrens ist der Vorgang der Multiplikation zweier mindestens hundertstelliger Primzahlen. Aus dem Produkt wird eine Zahl generiert, die als „öffentlicher Schlüssel“ allgemein bekannt gemacht wird. Die Asymmetrie liegt darin, daß mit diesem öffentlichen Schlüssel nur ver- aber nicht entschlüsselt wird. Entschlüsselt wird Hilfe der Ausgangsprimzahlen, die der Empfänger der Nachricht als „privaten Schlüssel“ zur Verfügung haben muß. Prinzipiell steckt hier in dem öffentlichen Schlüssel eine Angriffsstelle für Codebrecher. Aber selbst heutzutage ist die Leistung von Supercomputern bei dem Stand der derzeitigen mathematischen Forschung noch ungenügend, um eine Zerlegung einer mit gewissen Vorsichtsmaßnahmen gewählten 300-stelligen Zahl in Primfaktoren in vernünftiger Zeit zu ermöglichen. Darüber mehr im nächsten Abschnitt. Hier soll nun zunächst Wolfart [Wo] S.110 ff folgend das RSA Verfahren etwas genauer beschrieben werden.

Vorbemerkungen zur elementaren Zahlentheorie

Es bezeichne

$\mathbb{N} = \{ 1,2,3,\ldots \}$ die Gesamtheit der natürlichen Zahlen

$\mathbb{N}_0 = N \cup \{0\} = \{0,1,2,\ldots \}$ die Gesamtheit der natürlichen Zahlen

$\mathbb{Z} = \{0,\pm 1,\pm 2,\ldots \}$ den Ring der ganzen Zahlen.

$\mathbb{Q} = \{m/n, m, n \in \mathbb{Z},n \neq 0\}$ den Körper der rationalen Zahlen.

In $\mathbb{N}$ und $\mathbb{N}_0$ sind beliebige Additionen und Multiplikationen ausführbar, in $\mathbb{Z}$ noch zusätzlich Subtraktionen und in $\mathbb{Q}$ überdies Divisionen durch Elemente $q \in \mathbb{Q},\, q \neq 0$. Für ein $m \in \mathbb{N}$ bezeichne

$\mathbb{Z}/m = \{\bar 0, \bar 1,\ldots, \overline {m-1}\}$

den „Ring der Reste bei Division durch $m$“. Hier werden zwei Elemente $\bar a$ und $\bar b$ addiert und multipliziert, indem jeweils $a$ und $b$ addiert resp. multipliziert werden und jeweils die (kleinsten) Divisionsreste bei Division durch $m$ als Bild bekommen, also etwa für $m=5$

$\bar 2 + \bar 3 =\bar 0 \;und\; \bar 2 \cdot \bar 3 =\bar 1$

Eine kleine Überlegung ergibt, dass $\mathbb{Z}/m$ genau dann sogar ein Körper ist, wenn $m$ eine Primzahl ist. Primzahlen werden meist mit $p$ enannt und es wird auch geschrieben

$\mathbb{Z}/p = \mathbb{F}_p \;oder\; = GF(p).$

Über diese Körper mit $p$ Elementen hinaus gibt es noch weitere endliche Körper $\mathbb{F}_p = GF(p)$, deren Elementzahl sich dann stets als eine Primzahlpotenz erweist, die meist als $q=p^5$ geschrieben wird.

Für die Begründung dieser und der Aussagen, die im Folgenden gebraucht werden, kann jedes Buch über Zahlentheorie genommen werden, also etwa Wolfart [Wo]. Zur Einstimmung ist aber besonders empfehlenswert F. Ischebeck: „Einladung zur Zahlentheorie“ [Is].

$\mathbb{Z}/m$ kann auch verstanden werden als Ring der Restklassen $a+ m\mathbb{Z}$ also gewisser Teilmengen von $\mathbb{Z}$ mit den Rechenregeln, die darauf von $\mathbb{Z}$ wie eben beschrieben induziert werden. Dabei bedeutet dann für $a,b \in \mathbb{Z}$ und $m \in \mathbb{N}$

$a \equiv b \quad mod \; m$

genau, daß $a$ und $b$ bei der Division durch $m$ denselben Rest haben oder, äquivalent, daß $m$ ein Teiler von $(a-b)$ ist, also $m | a - b$. Hier bezeichnet $m | n$, daß $m$ ein Teiler von $n$ ist, also ein l in $ \mathbb{Z}$ existiert mit $n=ml$. $m \nmid n$ besagt , daß eben $m$ kein Teiler von $n$ ist. In der elementaren Zahlentheorie zentral ist die folgende Aussage, die auf Pierre de Fermat (1640) zurückgeht und auch der „kleine Fermatsche Satz“ genannt wird (s. [Wo] S.35).

Für alle $a \in \mathbb{Z}$ und $p$ gilt

$a^p \equiv b \quad mod \;p.$

Weiter wird noch gebraucht die Eulersche $\varphi$-Funktion (s.[Wo] S.19), die die Anzahl der primen Restklassen $a+m\mathbb{Z}$ mit $a \nmid m$ zählt. Es ist

$\begin{array}{ccc} f: \varphi(m)=m & \prod & (1-1/p) \\ & p\; prim & \\ & p \nmid m & \end{array}$

also insbesondere, wenn $p$ und $q$ Primzahlen sind

$\varphi (m)=p-1 \; und \; \varphi(pq)=(p-1)(q-1).$

In Verallgemeinerung des kleinen Fermatschen Satzes gilt noch (dies wird meist als Übungsaufgabe gestellt (s.[K1] S.93)): Es seien

$n=pq$, $p$ und $q$ verschiedene Primzahlen

und

$d, e \in \mathbb{N} \; mit \; de \equiv 1 \quad mod \; \varphi(n).$

Dann gilt für alle $a \in \mathbb{Z}$

$a^{de} \equiv a \quad mod \; n.$

Das RSA-Verfahren

Das Verfahren geht nun nach folgendem Schema. Jeder Benutzer $B$

berechnet $n=pq$ und \varphi(n)=(p-1)(q-1),
wählt zwei ganze Zahlen $d$ und $e$ zwischen 1 und $\varphi(n)$, die zu $\varphi(n)$ teilerfremd sind und die Bedingung $de \equiv 1 \quad mod \; \varphi(n)$ erfüllen
macht $K_0=(n,e)$ als öffentlichen Schlüssel bekannt, und
verbirgt $K_1=(n,d)$ als geheimen Schlüssel.

Falls nun ein Benutzer $A$ eine Nachricht $a_0$ übermitteln will, wird er diese in Buchstabengruppen (etwa zu je vier) zerlegen und diesen Buchstabengruppen jeweils Elemente $\bar a$ aus $\mathbb{Z}/n\mathbb{Z}$ zuordnen (als Zahlen $a$ zwischen 0 und $n$-1). Der Verschlüsselungsprozess ist die Abbildung

\begin{array}{ccc} f: \mathbb{Z}/n & \to & \mathbb{Z}/n \\ \bar a & \to & \overline{a^e} \\ \end{array}

wobei $\overline {a^e}$ wieder durch Zahlen zwischen 0 und $n$-1 geschrieben wird. Der Entschlüsselungsprozeß besteht darin, dass $B$ aus dem ihm übermittelten $\overline {a^e}$ die Potenz $(\bar {a^e})^d$ bildet und damit nach dem Satz am Ende des vorigen Abschnitts das Element $\bar a$ ewinnt, das wieder in Zahlen zwischen 0 und $n$-1 geschrieben die Rückübersetzung in den Buchstabentext erlaubt, der übermittelt werden sollte. Aus [Ba] S.179 wird das folgende Beispiel reproduziert (das natürlich kleinere Zahlen verwendet und statt mit der Eulerschen $\varphi$-Funktion die nur unwesentlich abgeänderte $\psi$-Funktion von Carmichael verwendet $(\psi(p \cdot q)=$ kleinstes gemeinsames Vielfaches von $p$-1 und $q$-1)):

Es sei

$p=47, \; q=59, also\; n=pq=2773 \; und \; \psi(q)=1334.$

Weiter wird $e$=17 und $d$=157 gewählt. Der Verschlüsselungsschritt ist dann

$b=f(a) \equiv a^{17} \quad mod \;2773$

der durch sukzessives Potenzieren in der Form

$((((a^2 \; mod \; 2773)^2 \; mod \; 2773)^2 \; mod \; 2772)^2 \; mod \; 2773)a \; mod \; 2773$

ausgeführt werden kann. Der Entschlüsselungsschritt ist

$g(b) \equiv b^{175} \quad mod \; 2773.$

Werden nun das Leerzeichen $\bigsqcup$ sowie die Buchstaben des Alphabets $a, b, c,\ldots$ in Ziffernpaare $00, 01, 02,\ldots,26$ verwandelt, können wegen $2626 < 2773$ Buchstabenpaaren eindeutig kleinste Reste $mod 2773$ zugeordnet werden. Die Botschaft

$errare \bigsqcup humanum \bigsqcup est$

wird dabei zur Zahlenkombination

$0518 \; 1810 \; 1805 \; 0008 \; 2113 \; 0114 \; 2113 \; 0005 \; 1920$

mit der Verschlüsselung

$1787 \; 2003 \; 2423 \; 0596 \; 0340 \; 1684 \; 0340 \; 0508 \; 2109.$

Die Verschlüsselung kann aus dem öffentlichen Schlüssel erraten werden (durch einen „kryptoanalytische Angriff“), wenn der geheime Schlüssel, also die Zahl $d$ erraten wird. Dies ist nicht schwer, wenn die Zerlegung von $n$ in die Primzahlen $p$ und $q$ gelingt. Als Sicherungsmaßnahmen dagegen gelten

$p$ und $q$ werden sehr groß gewählt
$p$ und $q$ werden nicht aus irgendeiner Primzahltabelle gewählt
$p$ und $q$ unterscheiden sich sowohl als Dezimalzahlen als auch als binäre Zahlen um einige Stellen. Sonst kann nämlich eventuell mit Fermats Idee $n=pq=\left (\frac{p+q}2 \right)^2-\left (\frac{p-q}2 \right)^2$ leichter auf $p$ und $q$ geschlossen werden. Es gibt verschiedene Angriffsmethoden. Die für die Mathematik am interessantesten erscheinende soll nun diskutiert werden.

Faktorisierung großer Zahlen und elliptische Kurven

Eines der großen Probleme der Zahlentheorie ist die Frage, wie Primzahlen erzeugt werden können. Dazu gibt es viel Literatur, (von der hier nur Zagiers Aufsatz [Za] erwähnt werde), obwohl das Problem natürlich auch für die RSA-Methode von Bedeutung ist. Es soll nun nur auf das (damit zusammenhängende) Problem eingegangen werden, wie die beiden Primfaktoren $p$ und $q$ bestimmt werden können, wenn $n$ als Produkt $n=pq$ zweier unbekannter Primzahlen gegeben ist. Falls ein Verfahren zur Faktorisierung großer Zahlen gefunden wird, wird das RSA-Verfahren natürlich wertlos.

Es ist eines der großen Geheimnisse der Mathematik, daß bei zunächst rein zahlentheoretisch aussehenden Fragestellungen zunächst nicht zur Zahlentheorie gehöriges Objekte zum Einwirken gebracht werden können, nämlich die elliptischen Kurven.

Vorbemerkungen über elliptische Kurven

Bücher zu diesem Gegenstand gibt es viele. Hier seien als Referenz nur der Aufsatz von H. Kraft [Kr], das Buch von Brieskorn und Knörrer [BK] sowie die einschlägigen Kapitel in [Wo] und [K1] sowie [K2] genannt, wo viele weitere Angaben zu finden sind.

lassische Objekte, die leider immer weniger Platz im Schulstoff zu behalten scheinen, sind die Kegelschnitte, also die Kurven im $\mathbb{R}^2$ mit den folgenden Normalformen:

\begin{array}{ll} \{(x,y) \in \mathbb{R}^2, x^2/a^2+y^2/b^2-1=0\} & Ellipse \\ \{(x,y) \in \mathbb{R}^2, x^2/a^2-y^2/b^2-1=0\} & Hyperbel \\ \{(x,y) \in \mathbb{R}^2, x^2-4ay=0\} & Parabel \end{array}

wobei hier $a$ und $b$ von Null verschiedene reelle Zahlen sind. Dies sind also Kurven, die als Nullstellenmenge quadratischer Polynome $f(x,y)$ beschrieben sind. Wird hier nur ein kleiner Schritt weiter gemacht, so tauchen die elliptischen Kurven auf, die allerdings gleich als Nullstellenmengen im Komplexen betrachtet werden. Auch hier gibt es Normalformen, und zwar heißt

$E_0=(\mathbb{C})=\{(x,y) \in \mathbb{C}^2, f(x,y)=y^2-\alpha \prod_{i=1}^3(x-\alpha_i)=0\}$

eine affine, elliptische Kurve, falls $\alpha \neq 0$ und die $\alpha_1, \alpha_2, \alpha_3 \in \mathbb{C}$ paarweise verschieden sind. Es ist dies also eine durch ein Polynom 3. Grades in $x,y$ gegebene Kurve. Dabei müssen Bedingungen erfüllt sein, die sichern, dass die Kurve in einem geometrisch zu verstehenden Sinne überall glatt ist. Zu diesen komplexen Punktmengen gehören bisweilen recht aussagekräftige reelle Bilder. Z. B. diskutiert Kraft [Kr] die Kurve mit der Gleichung

$y^2=x^3 - 25x$

und dem Bild

Abbildung: R. Berndt; mathematische Darstellung einer Kryptoellipse

Das Bild erweckt den Anschein, als ob die Kurve aus zwei unzusammenhängenden Stücken besteht. Das ist aber nur im Reellen der Fall.

Die eben diskutierte Kurve wird noch durch einen unendlichen Punkt $(\infty,\infty)=0$ vervollständigt, also $E:=E_0 \cup 0$ und heißt nun elliptische Kurve. Dieser Name kommt nicht etwa von ihrer geometrischen Gestalt im Reellen, sondern daher, dass Funktionen, die im Komplexen in natürlicher Weise auf $E$ definierbar sind, sogenannte elliptische Funktionen, eine entscheidende Rolle spielen bei der Berechnung der Bogenlänge von Ellipsen.

s ist von ganzem großen Interesse für die Mathematik, hier – wie übrigens auch bei den anfangs benannten Quadriken – nach rationalen sowie ganzen Punkten zu suchen, also nach Paaren $(x,y) \in \mathbb{Q}^2$ bzw. $\mathbb{Z}^2$ mit $f(x,y)=0$. Von hier ist es nur ein kleiner Schritt, nach Lösungen in $(\mathbb{Z}/m)^2$ zu fragen, also nach Zahlen $(x,y) \in \mathbb{Z}^2$ mit $f(x,y) \equiv 0 \quad mod \; m$

Die überragende inner- und außermathematische Bedeutung der elliptischen Kurven liegt nun darin, dass auf der Menge $E(K)$ der Punkte einer elliptischen Kurve mit Koordinaten in einem Körper $K(= \mathbb{R}, \mathbb{C}, \mathbb{Q}$ oder $\mathbb{F}_q$ eine kommutative Gruppenstruktur eingeführt werden kann. Das geht, abgesehen von dem trivialen Fall der Geraden, nur für elliptische Kurven. Die die Gruppenstruktur vermittelnde Verknüpfung läßt sich geometrisch verstehen: Für zwei verschiedene Punkte $P,Q \in E$ wird als Summe $P+Q$ er Punkt genommen, der sich ergibt, indem eine Gerade $g$ durch $P$ und $Q$ gelegt wird und der dritte Schnittpunkt $R$ dieser Geraden $g$ mit $E$ an der x-Achse gespiegelt wird (s. Skizze). Das läuft darauf hinaus, dass der Punkt 0 im Unendlichen das neutrale Element der Gruppe ist.

Eine nicht zu schwere Rechnung zeigt, dass für $y^2=x^3+ax+b$ und $P=(x_1,y_1), Q=(x_2,y_2)$ der Punkt $P+Q=(x_3,y_3)$ die Koordinaten hat

$x_3=\left (\frac{y_2-y_1}{x_2-x_1} \right)^2-x_1-x_2; \quad y_3=-y_1 + \left (\frac{y_2-y_1}{x_2-x_1} \right)(x_1-x_3) \quad falls \; P\neq Q$

und

$x_3=\left (\frac{3x^2_1+a}{2y_1} \right)^2 - 2x_1 \quad y_3=-y_1 + \left (\frac{3x^2_1+a}{2y_1} \right)(x_1-x_3) \quad falls \; P = Q$

Dabei ist für $y_1=0$ sowie $x_2=x_1$ der Punkt $0=(\infty,\infty)$ zu verwenden. Der inverse Punkt $(-P)$ wird dann notwendig durch die Koordinaten $(x_1,-y_1)$ beschrieben und die maximal drei Punkte mit $y=0$ sind zu sich selbst invers, also von der Ordnung 2. Die Gruppenaxiome sind nicht schwer nachzurechnen mit Ausnahme des Assoziativgesetzes, dessen Beweis einen schönen geometrischen Satz benutzt, nämlich den Satz von Bézout über die Anzahl der Schnittpunkte zweier algebraischer Kurven.

Elliptische Kurven über endlichen Körpern

Faktorisierung mit Hilfe elliptischer Kurven

Lenstra hat einen Faktorisierungsalgorithmus entworfen, der diese elliptischen Kurven benutzt. Angenommen n sei eine große natürliche Zahl, die nicht durch 2 und 3 teilbar ist und von der vermutet werde, dass sie einen Primfaktor $p$ besitzt. Nun kann nicht in $E(\mathbb{F}_p)$ gerechnet werden, wenn $p$ nicht bekannt ist. Allerdings gibt es für $p | n$ einen Ringhomomorphismus

\begin{array}{ccc} f: \mathbb{Z}/n & \to & \mathbb{Z}/p \\ a+n\mathbb{Z} & \longmapsto & a+p\mathbb{Z}\;, \\ \end{array}

und es kann versucht werden, zunächst mit $\mathbb{Z} \; mod \; n$ zu rechnen. Solange es sich um Additionen und Multiplikationen handelt, ist das ohne weiteres erlaubt. Das einzige Problem besteht darin, dass in den Additions- und Verdoppelungsformeln für die Punkte auf $E$ durch die Nenner $x_1-x_2$ bzw. $2y_1$ dividiert wird. In $\mathbb{Z}/n$ ist diese Division genau dann durchführbar, wenn diese Nenner zu $n$ teilerfremd sind. Die Berechnungen von $mP$ für $m \in \mathbb{N}$ und $P \in E$ scheitern also genau dann, wenn ein größter gemeinsamer Teiler von $n$ und $x_1-x_2$ oder $2y_1$ gefunden wird. Wenn dieser nicht zufällig gerade gleich $n$ ist, ist aber ein nicht trivialer Faktor von $n$ gefunden. Auf Faktor und Kofaktor wird dann ein Primzahltest angewandt und das Verfahren gegebenenfalls wiederholt.

Diese ziemlich vagen Bemerkungen lassen sich zu einem praktikablen Verfahren verdichten, bei dem es natürlich genauer darum geht, mit welchen elliptischen Kurven und Punkten gearbeitet werden soll. Für das sich dabei unter gewissen weiteren Annahmen ergebende Verfahren ergibt sich eine mittlere Laufzeit von

$e^{\sqrt{(1 + \sigma(n) (\log n \log \log n) )}},$

wobei $\sigma$ eine Funktion ist mit $\lim_{n \to \infty} \sigma(n)=0$

Seit 1990 ist von Pollard eine andere Faktorisierungsmethode, das Zahlkörpersieb entwickelt worden, das asymptotisch schneller ist als Lenstras Verfahren. (für Zahlen $n$ mit 512 bits gilt das RSA-Verfahren damit als unbrauchbar !). Die elliptischen Kurven sind aber auch in diesem Zusammenhang noch nicht aus dem Blickfeld.

Ein Kryptosystem zu einer elliptischen Kurve

Das Problem des diskreten Logarithmus

Gitter und Codes

Neben dem bisher diskutierten Problem der nicht autorisierten Entschlüsselung von Nachrichten und dem hier beiseitegelassenen der Autorisierung einer Nachricht gibt es noch das, daß Nachrichten bei der Übertragung (unbeabsichtigt) beschädigt werden können.

Dem kann entgegengewirkt werden dadurch, daß die Nachricht bzw. die sie tragenden Ziffern, Symbole oder was immer vor der Übertragung so redundant gemacht werden, daß bei eventuellen kleinen Beschädigungen der Kern noch genügend Information behält. Im Prinzip könnte dies dazu führen, die Nachricht einfach mehrfach zu übertragen, was natürlich die Kosten in ungewünschter Weise erhöht. Eine hier entscheidende neue Idee ist 1948 von R. W. Hamming von den Bell Telephone Laboratories ins Spiel gebracht worden. Das hier wieder ganz Wunderbare ist, daß eine systematische Weiterführung dieser Idee, die unter der Bezeichnung „Gitter und Codes“ läuft, wieder in die Nähe der elliptischen Kurven führt. Dies ist schon ganz vordergründig zu begreifen: Eine komplexe elliptische Kurve $E(\mathbb{C})$ ist in einem hier nicht zu präzisierendem Sinne isomorph zu einem Torus T, der entsteht, indem in $\mathbb{C} \backsimeq \mathbb{R}^2$ die Ränder gegenüberliegender Seiten einer Gittermasche identifiziert werden (s. Skizze)

Das Gitter entspricht dem Torus, einer elliptischen Kurve

Abbildung: R. Berndt; schematische Darstellung des Kryptomappings

Codes

Die folgenden Grundbegriffe sind der Darstellung in Ebeling [Eb] entnommen. (Verwiesen sei dabei aber auch auf die Bücher [Wi] und [LG].) Dabei wird angeknüpft an die in 2.1 eingeführten endlichen Körper $\mathbb{F}_p$, deren Elemente jetzt der Einfachheit halber ohne die früher gebrauchten Querstriche geschrieben werden, also

$\mathbb{F}_p$=\{0,1,ldots,p-1\}.$

Ein (linearer) Kode der Länge $n$ ist dann einfach ein linearer Unterraum $C$ von $\mathbb{F}^n_p$. Für $p =2$ heißt der Kode binär, für $p =3$ ternär usw. Ein Element von $C$ wird Kodewort genannt. Der Kodierungsprozess ist eine lineare Abbildung

\begin{array}{cccc} f: & \mathbb{F}_2 & \to & C=\{(0,0,0),(1,1,1)\} \subset \mathbb{F}^3_2 \\ & 0 & \mapsto & (0,0,0)= \omega_0 \\ & 1 & \mapsto & (1,1,1)= \omega_1 \end{array}

Falls nun etwa $\omega_0$ bei der Übermittelung zu $\omega'_0 =(0,1,0 \notin C)$ wird, kann der Empfänger vernünftigerweise vermuten, dass die übertragene Botschaft $\omega_0=(0,0,0)$ sein sollte. Dass dies hier auf eine Verdreifachung der ursprünglichen Nachricht hinausläuft und damit zu einer unangenehm großen Verteuerung, ist offenbar und wird durch folgende Begriffsbildungen quantifiziert und (zum Teil) behoben:

Es bezeichne für einen linearen Unterraum $C \subset \mathbb{F}^n_p$

$x=(x_1,\ldots,x_n) \in \mathbb{F}^n_p$ ein „Codewort“

$w (x):=$ die Anzahl der Komponenten $x_i \neq 0$, das „Gewicht“ von $x$

$d(x,y):=w(x,y)$ den „Hamming-Abstand“ von $x,y \in \mathbb{F}^n_p, d:=\min\{d(x,y),x,y \in C\}$ den „Minimalabstand“,

$M:= \vert C \vert =p^k$ die Anzahl der Elemente von $C$ und $R = k/ n$ die „Informationsrate“. $C$ heißt dann ein $[n,k,d]$-Code.

Beispiel: Der oben angegebene Code ist ein [3,1,3]-Code mit Informationsrate $R =1/3$. Bei diesem Beispiel kann schon mal die allgemeine Aussage nachgeprüft werden, dass ein Code mit Minimalabstand $d \; t$ Fehler korrigieren kann mit $t$ fixiert durch

\begin{array}{ccccc} d & = & (2t+1) & d & ungerade \\ & = & 2(t+1) & d & gerade \end{array}

Daraus entsteht nun leicht die Aufgabe, Codes mit möglichst großem Minimalabstand $d$ aber (aus Kostengründen) möglichst kleiner Wortlänge zu suchen, also genauer mit möglichst großer Informationsrate $R$.

Nach seinem Initiator heißt nun der folgende binäre [7,4,3]-Code Hamming-Code $C_H$. Es sei

\begin{array}{ccccc} f & : & \mathbb{F^4_2} & \to & C_H\subset \mathbb{F}^7_2 \\ & & (x_1,x_2,x_3,x_4) & \mapsto & (x_1,\ldots,x_7) \end{array}

wobei zu vorgegebenen $x_1,\ldots,x_4$ die Elemente $x_5,x_6,x_7 \in \mathbb{F}_2$ so zu bestimmen sind, dass die Summe der Elemente in jedem Kreis gleich 0 ist.

Abbildung: R. Berndt; mathematische Darstellung von Kryptokreisen

$C_H$ hat dann die Informationsrate $R =4/7$. Die zur Konstruktion von $C_H$ verwandte Bedingung kann auch mit Hilfe der Inzidenzmatrix des $\mathbb{P}_2(\mathbb{F}_2)$ gedeutet werden (s.[Eb] S.10).

$C_H$ wird zu dem „erweiterten Hamming-Code“ $\tilde{C}_H=I(C_H)$ ausgedehnt mit Hilfe der Abbildung

\begin{array}{ccc} I:\mathbb{F}^7_2 & \longrightarrow & \mathbb{F}^8_2 \\ (x_1,\ldots,x_7) & \mapsto & (x_1,\ldots,x_7,\sum\limits_{i=1}^{7}x_i). \end{array}

Dies ist dann ein [8,4,4]-Code.

Von Codes zu Gittern

Gitter waren schon lange, bevor ein Zusammenhang mit den Codes bemerkt wurde, ein Gegenstand mathematischer Forschung mit mannigfachen Anwendungen, etwa in der Kristallographie. Es gibt dafür verschiedene Definitionen. Für unseren Zweck heißt eine Teilmenge $\Gamma$ von $\mathbb{R}^n$ ein Gitter in $\mathbb{R}^n$ genau dann, wenn eine Basis $(e_1,\ldots,e_n)$ des $\mathbb{R}^n$ gibt mit

$\Gamma = \mathbb{Z}_{e_1} \oplus \; \ldots \; \oplus \mathbb{Z}e_n,$

d. h. einfach, dass $\Gamma$ aus allen ganzzahligen Linearkombinationen der Vektoren $(e_1,\ldots,e_n)$ besteht. Das von den üblichen Einheitsvektoren $ e_1=(1,0,\ldots,0)\ldots e_n=(0,\ldots,0,1)$ aufgespannte Gitter $\Gamma =\mathbb{Z}^n$ heißt das „Standardgitter“. In dem Beispiel am Anfang des Abschnitts 4 ist

$\Gamma =\mathbb{Z}1 \oplus \mathbb{Z}(x,y) \quad mit \quad x\neq0,y >0.$

Gitter lassen sich nun noch auf mannigfache Weise spezifizieren und die so spezifizierten Gitter dann klassifizieren. So wird $\Gamma$ zugeordnet die Matrix $A(\Gamma) = A =(_{jk})$, gebildet aus den Skalarprodukten

$a_{jk}=e_j \cdot e_k$

der Basisvektoren $(e_1,\ldots,e_n)$.

Ein Gitter heißt ganz, falls für alle $x,y \in \Gamma$ die Skalarprodukte $x \cdot y \in \mathbb{Z}$ sind, d. h. auch, falls $A$ eine Matrix aus ganzen Zahlen ist.

Ein ganzes Gitter $\Gamma$ heißt gerade, falls für alle $x \in \Gamma$ gilt $x \cdot x \equiv 0 mod 2$, d. h. falls in $A$ alle Diagonalelemente gerade sind.

Das Standardgitter $\Gamma_0=\mathbb{Z}^n$ hat als Matrix $A(\Gamma_0)$ die Einheitsmatrix $E_n$, ist also ganz, aber nicht gerade.

Die Reduktion $mod2$ gibt einen Gruppenhomomorphismus

$\rho:\mathbb{Z}^n \longrightarrow (\mathbb{Z}/2)^n=\mathbb{F}^n_2.$

Falls $C$ ein $[n,k,d]$-Code ist, also ein Unterraum $C \subset \mathbb{F}^n_2$, gilt $\mathbb{F}^n_2/C \backsimeq \mathbb{F}^{n-k}_2$. $C$ ist damit eine Untergruppe in $\mathbb{F}^n_2$ vom Index $2^{n-k}$ und das Urbild $\rho^{-1}(C)$ von $C$ in $\mathbb{Z}^n$ wird auch als Untergruppe vom Index $2^{n-k}$ von $\mathbb{Z}^n$ erkannt. $\rho^{-1}(C)$ ist eine freie abelsche Gruppe vom Rang $n$ und deshalb ein Gitter in $\mathbb{R}^n$.

$\Gamma_c:=(1/\sqrt{2})\rho^{-1}(C)$

wird als das dem Code zugeordnete Gitter genommen. Als Beispiel: Zum erweiterten Hamming-Code $\tilde{C}_H$ gehört auf diese Weise das Gitter $\Gamma_{\tilde{C}_H}$ in $\mathbb{R}^8$ mit der Basis $(e_1,\ldots,e_n)$ für $e_1=f_1,e_2=f_2-f_1,e_3=f_3-f_2,e_4=f_4-f_3,e_5=f_5-f_4,e_6=f_6-f_5,e_7=f_7-f_6$ und

\begin{array}{ccc} f(1) & = & 1/Sqrt(2) (0,1,1,0,1,0,0,1) \\ f(2) & = & 1/Sqrt(2) (0,0,1,1,0,1,0,1) \\ f(3) & = & 1/Sqrt(2) (0,0,0,1,1,0,1,1) \\ f(4) & = & 1/Sqrt(2) (1,0,0,0,1,1,0,1) \\ f(5) & = & 1/Sqrt(2) (0,1,0,0,0,1,1,1) \\ f(6) & = & 1/Sqrt(2) (1,0,1,0,0,0,1,1) \\ f(7) & = & 1/Sqrt(2) (1,1,0,1,0,0,0,1) \\ e(8) & = & 1/Sqrt(2) (-1,-1,0,0,1,0,-1,0) \end{array}

Obwohl das den Rahmen dieses Textes endgültig sprengt, sei noch erwähnt, dass zu diesem Gitter ein (Witt-)Coxeter-Dynkin Diagramm vom Typ $E_8$ gehört, nämlich

\begin{array}{ccc} e(1) --- e(2) --- e(3) --- e(4) --- e(5) --- e(6) --- e(7) \\ 1 \\ e(8) \end{array}

Solche Diagramme spielen im Zusammenhang mit den „Wurzelgittern“ eine zentrale Rolle bei der Frage der Klassifikation einfacher Lie-Algebren und „klassischer Gruppen“. Umgekehrt kann von Gittern gewissen Typs auf mögliche Codes geschlossen werden und diese werden dann damit klassifiziert. Als Beispiel ([Eb], S. 103) kommt u. a. heraus: Es gibt mehr als 17.000 inäquivalente selbstduale binäre Codes der Länge 40.

Schlussbemerkungen

In diesem Text sind nur Fragen angesprochen, bei denen mathematische Theorie aus dem Bereich der Zahlentheorie, der Funktionentheorie und der algebraischen Kurven und Gruppen zum Tragen kommt. Fragen, die nahe beim Computer oder im Bereich der Technik der Übertragung von Nachrichten liegen, sind ausgespart, was aber nicht bedeutet, daß diese hier als uninteressant oder bedeutungslos angesehen werden. Auch die vielfältigen wirtschaftlichen, juristischen und allgemein gesellschaftlichen Probleme, die hier naheliegen, fanden leider unter der Überschrift keinen Platz.

Literatur

Ba – Bauer, F. L.: Decrypted Secrets. Methods and Maxims of Cryptology Springer, Berlin 1997
Bi – La Bible, Ancient Testament II. Editions Gallimard 1959
BK – Brieskorn, E., Knörrer, H.: Ebene algebraische Kurven Birkhäuser, Basel 1981
Co – Coe, M. D.: Das Geheimnis der Mayaschrift. Ein Code wird entschlüsselt Rowohlt, Reinbek 1995
Eb – Ebeling, W.: Lattices and Codes. Vieweg, Braunschweig/Wiesbaden 1994
Is – Ischebeck, F: Einladung zur Zahlentheorie BI Wissenschaftsverlag, Mannheim 1992
Kr – Kraft, H.: Algebraische Kurven und diophantische Gleichungen. In ,,Lebendige Zahlen“. Birkhäuser, Basel 1981
K1 – Koblitz, N.: A Course in Number Theory and Cryptography. Springer, New York 1987
K2 – Koblitz, N.: Algebraic Aspects of Cryptography. Springer 1998
LG – van Lint, J. H., van der Geer, G.: Introduction to Coding Theory and Algebraic Geometry. DMV Seminar, Birkhäuser, Basel 1988
P – Poe, E. A.: Der Goldkäfer. In: Erzählungen. Winkler, München 1993
Wi – Willems, W.: Codierungstheorie. De Gruyter, Berlin 1999
Wo – Wolfart, J.: Einführung in die Zahlentheorie und Algebra Vieweg, Braunschweig/Wiesbaden 1996
Za – Zagier, D.: Die ersten 50 Millionen Primzahlen. In ,,Lebendige Zahlen“. Birkhäuser, Basel 1981