Sooo … da ich mal ein bisschen von den Stoff meiner Prüfungen abschalten, aber zugleich nicht untätig des Nächtens am Rechner sitzen wollte, hat mich die Schreibwut gepackt – oder so. ;)
Er000r hatte vor längerer Zeit mal angefragt, ob ich nichtmal was über ECC schreiben mag und nunja, genau dies geschieht jetzt hiermit. :)
Ich probiere das ganze so verständlich wie möglich zu halten – auch für Leute, die bisher keine größere Bindung zur Mathematik haben.
Also fangen wir an:
01 – Einleitung
Zunächst sollte einmal die Frage geklärt werden, worum es sich eigentlich bei der Elliptic Curve Cryptography handelt. Es handelt sich hierbei nicht um ein diskretes Verschlüsselungsverfahren, sondern um ein asymmetrisches Kryptosystem – also ein Ansatz, wie asymmetrische Verschlüsselungverfahren realisiert werden können.
02 – Kurzüberblick: Assymetrische Verschlüsselung
Die Sicherheit eines asymmetrischen Kryptosystems beruht aus Sicht der Angreifer auf ein mathematisches Problem – an dieser Stelle möchte ich allerdings ein wenig ausholen und das Grundprinzip assymetrischer Kryptosysteme metaphorisch erläutern :
Zwei Kommunikationspartner -in der Kryptologie standardisiert Alice und Bob genannt- besitzen je einen öffentlichen und einen privaten Schlüssel. Will Alice Bob eine Nachricht schicken, verschlüsselt sie diese mit Bobs öffentlichen Schlüssel und jener kann die Nachricht mit seinen privaten Schlüssel entschlüsseln. Damit dies möglich wird, werden mathematische Funktionen gebraucht, die eine Art Hintertürchen besitzen. Die Nachricht wird mit einer solchen Funktion verschlüsselt, wobei der öffentliche Schlüssel der Hauptparameter der Funktion ist.
Mit dem Hintertürchen, welche dem privaten Schlüssel entspricht und welche dem Angreifer nicht bekannt ist, lässt sich diese Funktion rückgängig machen und aus dem verschlüsselten Text ergibt sich wieder die eigentliche Nachricht.
Das mathematische Problem für den Angreifer ist es hierbei, dieses Hintertürchen zu finden beziehungsweise zu berechnen. Die Funktion für die Verschlüsselung muss also letztlich so gewählt sein, dass sich mithilfe des öffentlichen Schlüssels keinerlei brauchbaren Informationen über den privaten Schlüssel ergeben.
Quelle : back2hack © by nSinus-R
[spoiler]
03 – Mathematische Grundlagen
Falls es nun bei dem Einen oder Anderen die Frage auftut: „Warum brauchen wir Mathe, wir übertragen doch Texte“, möchte ich hierzu ganz knapp eine Antwort geben. Die rede ist von digitalier Kommunikation, de facto werden also Bits, Nullen und Einsen, also ZAHLEN verschickt, wodurch es möglich wird, durch „einfaches“ hin- und herrechnen zu ver- und entschlüsseln – ist das nicht einfach phantastisch? ;)
Nun gut, kommen wir nun zu den eigentlichen mathematischen Grundlagen von ECC:
Wie der Name schon vermuten lässt, hat es irgendwas mit Elliptischen Kurven zu tun.
Eine elliptische Kurve ist eine Punktemenge, die sich aus der Gleichung
y^2 = x^3 + ax + b
ergibt. Das ganze könnte dann z.B. (auf einem Graphen aufgetragen und somit visualisiert) so aussehen:
Damit das eigentliche Rechnen hier überhaupt erst möglich wird, weist man zunächst nach, dass es sich beim Rechnen über der elliptischen Kurve um eine Gruppe handelt, wobei die sich aus der Kurve ergebenden Punkte die Menge ist, mit der gerechnet wird.
04 – Gruppenheorie
Ein mathematische Gruppe besteht aus einer Menge, mit dessen Elementen gerechnet wird, und einer Rechenoperationen oder Verknüpfung genannt. Diese Rechenoperation kann Addition genannt werden, muss aber nicht zwangsweise wie die Addition aus dem Schulunterricht definiert sein, sondern kann eine ganz eigene, „neuartige“ Rechenvorschrift sein.
Um einen abelsche Gruppe nachzuweisen müssen folgende drei Kriterien erfüllt sein:
a) Es herrscht Assoziativität: Hintereinanderreihung von der Rechenoperation der Gruppe ist egal.
a+(b+c) = (a+b)+c
b) Es herrscht Kommutativität: Die Reihenfolge der Elemente bei einer Rechenoperation ist egal.
a+b = b+a
c) Es existiert ein neutrales Element: Es gibt ein universelles Element, welches bei einer Verknüpfung mit jedem anderen Element den Wert von diesem nicht beeinflusst:
a+n =a
d) Es existiert ein inverses für jedes Element: Für jedes Element existiert ein jeweiliges inverses Element. Durch die Verknüpfung der beiden ergibt sich das neutrale Element:
a+a^-1 = n
e) Die Gruppe ist abgeschlossen: Bei der Verknüpfung zweier Elemente der Menge kommt immer ein Element raus, dass auch innerhalb der Menge liegt.
Bei einer Halbgruppe müssen nur die Axiome a und e erfüllt sein.
05 – Nachweis der algebraischen Struktur bei Elliptischen Kurven
Nachdem nun geklärt ist, was wir beweisen müssen um zu zeigen, dass es sich bei der Menge der Punkte bei einer elliptischen Kurve um eine Gruppe handelt, vollbringen wir doch einfach den Nachweis. Zur Vereinfachung benutze ich die Ziffern und Buchstaben aus 04, um zu verdeutlichen, was gerade überhaupt nachgewiesen wird. Als Anmerkung sei noch gesagt, dass ich den Nachweis nicht mathematisch im eigentlichen Sinne durchführe, sondern lediglich probiere die Verknüpfungen und die Erfüllung der Axiome verständlich zu erklären.
Nachweis: Addition mit Mengenelementen einer elliptischen Kurve ist eine Abelsche Gruppe
Wir definieren die Addition zweier Elemente aus unserer Menge als Spiegelung des dritten Schnittpunktes der sich aus a und b ergebenden Gerade mit der elliptischen Kurve an der X-Achse. Da beim ersten Lesen des Satzes vielleicht ein „lulwhat?-Effekt“ vorliegt, hier nun eine Grafik und ein paar Erklärungen:
P und Q sind unsere Elemente a und b aus der Menge, also zwei Punkte auf der elliptschen Kurve. Mithilfe von zwei Punkten lässt sich eine gerade Konstruieren und aufgrund der Form einer elliptischen Kurve ergibt sich genau ein dritter Punkt auf eben dieser, -R genannt. Spiegeln wir nun -R an der X-Achse, erhalten wir R und unsere Definition P+Q=R ist visuell sichtbar erfüllt.
Es ist relativ offnsichtlich, das Kommutativgesetz (#b) und das Axiom der Abgeschlossenheit (#e) erfüllt ist. Mit ein wenig drüber nachdenken (oder selbst zeichnen) sieht man auch, dass das Assoziativitätsgesetz(#a) erfüllt ist – mathematisch würde sich das über Gleichsetzungsverfahren nachweisen lassen.
Der dritte Schnittpunkt existiert natürlich nur, wenn P und Q (nicht so wie R und -R) nicht die selbe X-Koordinate haben. Dies machen wir uns zu nutze, um die beiden anderen Axiome zu erfüllen. Als neutrales Element nehmen wir den fiktiven Punkt P0 in unsere Menge mit auf, der den Wert eines Punktes nicht beeinflusst (#c)
Das Inverse Element ist jeweils der zweite Punkt auf der Kurve mit der selben x-Koordinate. Da die elliptische Kurve an der x-Achse symmetrisch ist, hat jedes Element also ein inverses Element (#d).
Da nach unserer obigen Rechenvorschrift -R+R nicht rechnerisch lösbar ist, definieren wir -a+a bzw -R+R=P0 und alle Axiome bezüglich der Addition sind erfüllt. :)
Rechnerisch mit herkömmlichen Rechenregeln ergibt sich R folgenderweise:
Steigung der Geraden PQ: s = (Py – Qy) / (Px – Qx)
x-Koordinate von R: Rx = s² – Px–Py
y-Koordinate von R: Ry = -Py + s (Px – Rx)
Zusätzlicher Nachweis: Die Multiplikationen mit Mengenelementen ist eine Halbgruppe
Wer aufgepasst hat wird feststellen, dass oben gar nicht der Fall P+P betrachtet wurde, also die Addition eines Elementes mit sich selbst. Dies ist nach obiger Rechenvorschrift ebenfalls nicht lösbar, also was tun?
Nun, wir machen uns das zu Nutze, um die Multiplikation zu definieren, wobei 2*p = P+P entspricht. Dies nennt sich Skalare Multiplikation und sollte aus der Vektorrechnung weitesgehend bekannt sein. Multipliziert man einen Vektor v mit 4, erhöht sich deren Länge um ein vierfaches, es gilt also 4*v = v+v+v+v.
Um auf der elliptischen Kurve nun einen zweiten Punkt 2P (=P+P) zu erhalten, benötigen wir wieder eine Gerade mit genau einem weiteren Schnittpunkt auf der elliptischen Kurve. Diese erhalten wir mit der Tangente durch P. Wie auch oben ist der sich ergebende -2P und die Spiegelung an der x-Achse 2P. Durch das „vermischen“ dieser skalaren Multiplikation mit der „normalen“ Addition auf elliptischen Kurven lässt sich jeder beliebiger Multiplikationsfaktor darstellen.
Beispielsweise gilt so: 3P = (2P)+P oder 4P = 2*(2*P).
Man sieht auch hier wieder, dass dies eine abgeschlossene Operation ist (#e).
Assoziativität(#a) ergibt sich aus der Eigenschaft, dass es sich eigentlich um Addition handelt.
Errechnen lässt sich 2P wie folgt:
Steigung der Tangente durch P: s = (3*(Px²) + a) / (2*Py)
x-Koordinate von R: Rx = s² – 2*Px
y-Koordinate von R: Ry = -Py + s (Px – Rx)
06 – Elliptische Kurven über endliche Körper
Bisher haben wir uns elliptische Kurven über einen unendlichen Körper, beispielsweise den der, angeschaut. Für die Kryptographie jedoch werden mathematisch betrachtet seit jeher endliche Körper genutzt und so ist es auch hier der Fall.
Aus der obigen Gleichung y^2 = x^3 + ax + b, welche elliptische Kurven über den Körper der reellen Zahlen ergab, ergibt sich nun:
(y^2) mod p = (x^3 + ax + b) mod p
Um effizient mit dem Rechner arbeiten zu können, bietet es sich zudem an keinen Körper mit stetigen, sondern mit diskreten Werten zu verwenden. Ein beispiel wären die natürlichen Zahlen von 0-22, also N23. Das ganze sieht dann nicht mehr so „hübsch“ aus wie die vorherigen Kurven, dennoch lässt sich die Symmetrie an einer x-Achse bei 11,5(=23/2) erkennen:
Nun haben wir eine elliptische Kurve über einen endlichen Körper mit diskreten Werten abgebildet, wodurch viel Rechenzeit und Ressourcen eingespart wird. Der Preis der endlichen Menge ist es, dass BruteForce-Attacken auf das Kryptosystem ermöglicht werden, daher muss die Menge groß genug sein, um solche Attacken ineffizient zu gestalten.
07 – Nutzen für die Kryptographie
Nun bleibt immer noch die Frage: Was nützt das ganze nun?
Ich erwähnte einleitend bereits, dass asymmetrische Kryptoverfahren auf ein schwer berechenbares Problem beruhen, wenn nicht alle Parameter, also die geheimen Schlüssel bekannt sind.
RSA beispielsweise nutzt das Faktorisierungsproblem: Es ist schwer zu bestimmen, welche Faktoren für die Erzeugung einer Zahl N tatsächlich genommen wurden.
Bei elliptische Kurven gibt es jedoch Probleme, die in herkömmlicher Mathematik einfach zu lösen wären.
Ein Problem, dass auch durch ECC Anwendung findet ist das Problem, des diskreten Logarithmus bei endlichen Körpern:
a^x mod p = m
Aus den gegebenen Parametern a, m und p das Unbekannte x zurückzurechnen, ist – sobald p ausreichend groß wird ein schwer lösbares Problem – schon in herkömmlicher Mathematik. Dieses Problem wird sich z.B. beim Diffie-Hellman-Schlüsselaustausch zu nutze gemacht.
Wesentlich schwerer erweist sich jedoch dieses Problem auf „unseren“ elliptischen Kurven, auch wenn hier anstatt der Exponation der oben erwähnten skalaren Multiplikation bedient wird.
Der große Vorteil an ECC ist, dass durch die erhebliche Erschwerung bei dem Lösen eines Problems die Anforderung an die Schlüsselgröße sinkt.
So reichen z.B. 235 Bit bei ECC um ungefähr die gleiche Sicherheit wie bei RSA mit 2304 Bit zu erzielen.
So, ich hoffe das ganze war einigermaßen verständlich und findet Anklang bei dem ein oder anderen, wenn ich Lust und Zeit finde kann ich ja auch mal ein paar Verfahren, die auf ECC basieren vorstellen.
[/spoiler]
