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: axm   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:

TXB-a*GXB-a*XAb*Tgb-a*gab*Tgab*g-ab* T1*TT 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.

C:\Users\Benedikt\Documents\Schule-Q2\bes Lernleistung\bilder\add2p1.JPG         C:\Users\Benedikt\Documents\Schule-Q2\bes Lernleistung\bilder\add2p2.JPG

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.