Kryptographie auf Basis elliptischer Kurven

Wie funktionieren​​ Kryptoverfahren​​ auf Basis elliptischer Kurven?

Eine kurze Einführung

Das​​ „diskreter Logarithmus“ Problem

Jede gute Verschlüsselung basiert auf einem Problem. Um etwas sicher verschlüsseln zu können,​​ braucht man ein​​ extrem schwer zu lösendes mathematisches Problem. Ein sogenanntes NP-vollständiges Problem. Um ein solches Problem zu konstruieren modelliert man sich oft eine sogenannte Falltürfunktion, also eine Funktion,​​ in die eine Richtung​​ einfach zu berechnen ist, aber nur schwer umkehrbar ist.​​ Zum Beispiel kann man einfach aus Mehl und Eiern einen Kuchen backen, aus dem Kuchen aber nur schwer die Eier und das Mehl gewinnen.​​ Ein Beispiel für ein solches Problem basierend auf einer Falltürfunktion ist​​ in der Mathematik​​ das Problem des diskreten Logarithmus.

Im Gegensatz zum normalen Logarithmus über den positiven reellen Zahlen wird der diskrete Logarithmus über eine zyklische Gruppe definiert. Die Ausgangsgleichung ist:​​ ax≡m   mod p. Der diskrete Logarithmus fragt nun nach dem x im Exponenten. „Wie hoch muss man a mindestens nehmen,​​ um den Rest m bei Division durch p zu bekommen.“ Die Umkehrfunktion (diskrete Exponentialfunktion) stellt die umgekehrte Frage: “Was ist der Rest (das Ergebnis), den man bekommt, wenn man​​ ax​​ durch (modulo) p rechnet“. Da sich die diskrete Exponentialfunktion offensichtlich leicht berechnen lässt, die Umkehrfunktion (diskreter Logarithmus) aber (vermutlich) nur sehr schwer, liegt hier eine der oben beschriebenen Falltürfunktionen vor, auf dessen Basis sich Kryptosysteme aufbauen lassen. Das Problem über zyklische Gruppen zu logarithmieren wird​​ diskretes Logarithmusproblem genannt. Dieses Problem macht sich z.B.​​ der Deffie​​ Hellman​​ Schlüsselaustausch zu Nutze.​​ 

Deffie Hellman Schlüsselaustausch

Um zunächst eine zyklische Gruppe zu erzeugen,​​ einigen sich Alice und Bob auf eine Primzahl p, die als Modul fungiert. Außerdem einigt man sich auf eine Primitivwurzel g von p oder auf eine Zahl kleiner p die keine Primitivwurzel ist. Diese würde die​​ Sicherheit allerdings mindern.​​ 

Eine natürliche Zahl g​​ heißt Primitivwurzel von p, wenn folgende Bedingung erfüllt ist:

gi mod p :0,1,2,3,…,p-2⟷{1,2,3,…,p-1}

Die Abbildung ist sowohl linkseindeutig (injektiv) als auch rechtstotal (surjektiv) und damit bijektiv. z.B. ist 2 Primitivwurzel von 5 denn:

20 mod 5=1

21 mod 5=2

22 mod 5=4

23 mod 5=3

P und g sind nun öffentlich einsehbar. Nun denkt sich sowohl Alice als auch Bob eine natürliche Zahl (a,b), die kleiner als die Primzahl ist und idealerweise nicht der Primitivwurzel entspricht. Diese bleiben geheim. Alice kennt also Bobs Zahl(b) nicht,​​ und Bob kennt Alice Zahl(a) nicht.

An ein und denselben Schlüssel, den ein Außenstehender, der den Austausch abhört, nicht gelangen kann, kommen sie​​ durch ein bestimmtes Vorgehen:

• Alice berechnet​​ XA=ga mod p, Bob berechnet​​ XB=gb mod p

• Nun​​ schickt​​ Alice​​ XA​​ an Bob und Bob schickt​​ XB​​ an Alice

• Schließlich​​ berechnet​​ Alice​​ den gemeinsamen Schlüssel​​ S=XBamod p ebenso wie Bob​​ S=XAbmod p

Dass dieses Verfahren funktioniert, zeigt sich folgendermaßen:

S=XBamod p=gbamod p=gbamod p=gabmod p=XAbmod p

Ein Abhörer würde nur g, p,​​ XA=ga mod p, XB=gb mod p​​ kennen und steht nun vor dem Problem durch​​ diskretes​​ Logarithmieren entweder an a oder an b zu gelangen. Er muss also das diskrete Logarithmus Problem, zu dem es (vermutlich) kein effektives Lösungsverfahren gibt, lösen.

Elgamal-Verschlüsselung

Die Idee des Deffie Hellmann Schlüsselaustausch kann​​ man​​ nun weiterführen, so dass man ein asymmetrisches Kryptosystem erhält, mit dem man auch ganze Nachrichten codiert versenden kann.

Zunächst einigen sich Alice und Bob erneut auf eine zyklische Gruppe ​​ durch Wahl einer Primzahl und auf eine Primitivwurzel g von p. Nun denken sich beide erneut Zahlen​​ (a,b) unter denselben Bedingungen wie beim Deffie Hellman Schlüsselaustausch. Außerdem berechnet Bob​​ XB=gb mod p

Den öffentlichen Schlüssel berechnet Alice durch​​ XA=ga mod p. a ist ihr privater Schlüssel.

Bob verschlüsselt nun einen Klartext T zum Geheimtext G indem er ​​ G=XAb*T mod p​​ berechnet.​​ ​​ G wird zusammen mit​​ XB​​ an Alice geschickt, die durch​​ T=XB-a*G mod p​​ entschlüsselt. Dass das Verfahren funktioniert, lässt sich durch folgende Umformungen zeigen:

T≡XB-a*G≡XB-a*XAb*T≡gb-a*gab*T≡gab*g-ab* T≡1*T≡T mod p

Ein Abhörer steht nun vor demselben Problem wie beim Schlüsselaustausch.​​ 

Eine Möglichkeit für einen Angreifer ist bei beiden kryptographischen Methoden durch einen​​ „Man in the Middle“​​ Angriff gegeben. Das bedeutet:​​ zwischen den Teilnehmern Alice und Bob befindet sich ein Angreifer Mallory, so dass Alice denkt, Mallory sei Bob, und Bob denkt, Mallory sei Alice. Der Angreifer ist nun in der Lage sowohl mit Alice als auch mit Bob ein Kryptosystem aufzubauen. Jede Nachricht, die einer der beiden Teilnehmer zum jeweils anderen senden will, kommt in Folge dessen zuerst bei Mallory an. Dieser kann die Nachricht natürlich lesen und nun entscheiden, ob die Nachricht unverändert weitergesendet, verändert weitergesendet oder eine gefälschte Antwort zurück an den Absender ​​ gesendet werden soll.​​ 

Elliptische Kurven

Das vorgestellte Verfahren basiert auf der Standardmultiplikation​​ und wird nun durch Definition einer Gruppe auf elliptischen Kurven der Form

y2=x3+a1x+a2

Erweitert.

Addition auf elliptischen Kurven

Man wählt zwei zu addierende Punkte A und B und​​ ‘‘zieht‘‘​​ eine Gerade durch diese Punkte. Der weitere Schnittpunkt mit der Kurve sei -C.​​ Man spiegelt den Punkt -C an der x-Achse und enthält das Ergebnis der Addition C.

Sonderfall:​​ wenn die zu addierenden Punkte​​ identisch​​ sind,​​ legt man eine Tangente an den Punkt und verfährt wie geschildert.

  ​​ ​​ ​​ ​​ ​​ ​​ ​​​​ 

Abb. ​​ 1​​ Addition zweier Punkte A und B veranschaulicht

Man kann durch überprüfen der Gruppen Definition​​ mit Hilfe der Schnittmenge von Gerade und elliptischer Kurve​​ einfach zeigen, dass die gewünschten Eigenschaften​​ erfüllt sind. Die Addition der Punkte​​ P1x1;y1  P2(x2;y2)​​ zu​​ P3(x3;y3)​​ ergibt sich demnach aus:

m=y2-y1x2-x1 mod p

x3=m²-x1-x2 mod p

y3=-y2+mx2-x3 mod p

Für die Addition zweier identischer Punkte gilt entsprechend:

m=3x12+a12y1x1 mod p

x2=m2-2x1 mod p

y2=-y1+mx1-x2 mod p

Die skalare Multiplikation wird nun durch mehrfaches addieren des selben Punktes definiert. Nun wird​​ das Potenzieren​​ durch die elliptische Multiplikation quasi ersetzt.​​ Die Trapdoor liegt nun in der Division auf​​ 

Der elliptische Deffie Hellman Schlüsselaustausch

Mit den elliptischen Kurven lassen sich nun​​ die oben vorgestellten Verfahren, die auf dem diskreten Logarithmusproblem aufbauen,​​ verbessern und elegant praxistauglicher machen.

Zunächst einigen sich Alice und Bob auf eine öffentlich einsehbare Kurve und wählen also die Kurvenparameter a und b sowie eine Primzahl p als Modul. Diese Daten sind öffentlich einsehbar. Außerdem wählen die beiden einen öffentlichen Punkt P, der auf der Kurve liegt. Nun wählt jeder eine geheime natürliche Zahl,​​ die kleiner als die Primzahl ist(Ak,Bk).

An ein und denselben Schlüssel, den ein Außenstehender, der den Austausch abhört, nicht gelangen kann, kommen sie erneut wie folgt:

• Alice berechnet​​ XA=Ak*P, Bob berechnet​​ XB=Bk*P

• Alice schickt​​ XA​​ an Bob und Bob schickt​​ XB​​ an Alice

• Alice berechnet​​ den gemeinsamen Schlüssel​​ S=XB*Ak ebenso wie Bob​​ S=XA*Bk

Beide kennen jetzt den selben Schlüssel:

S=XB*Ak=Bk*P*Ak=Bk*P*Ak=Bk*XA

Will nun jemand den​​ Schlüssel​​ herausfinden, würde er nur die elliptische Kurve, den Punkt P,​​ XA=Ak*P​​ und XB=Bk*P​​ kennen und steht nun vor dem Problem durch diskrete Division auf einer elliptischen Kurve entweder an​​ Ak​​ oder an​​ Bk​​ zu gelangen. Da die Division auf elliptischen Kurven auf das diskrete Logarithmusproblem zurückzuführen ist, ist dieses Problem mindestens so schwierig wie das diskrete Logarithmusproblem, wenn sinnvolle Kryptoparameter gewählt werden. Vermutlich handelt es sich hierbei aber um ein noch schwerer zu lösendes Problem. Bis heute existiert kein Algorithmus,​​ der dieses Problem in​​ polynominaler Laufzeit lösen kann, also in einer Laufzeit, die mit zunehmender Schlüsselgröße sich nicht​​ ‘‘stärker‘‘ als eine Polynomfunktion vergrößert.