Der Vortrag, wie auch die Ausarbeitung, beschäftigt sich vornehmlich mit Methoden der Kryptographie und im besonderen mit dem Einsatz elliptischer Kurven. Er richtet sich an Studentinnen, Studenten und Professoren der Informatik. Aber natürlich auch an alle anderen Personen die sich für das Thema Kryptographie interessieren.
Inhaltsverzeichnis
Dokument Übersicht
Ein Basiswissen über Mathematische und Kryptographische Verfahren wird allerdings vorausgestzt um relativ zügig zu den elliptischen Kurven überzugehen. Trotzdem sollen zunächst einige Grundbegriffe geklärt werden, damit Author und Leser in etwa das selbe Verständnis haben.
In einem nächsten Abschnitt wird direkt auf asymmetrische Verfahren und den Schlüsselaustausch, nach Diffie-Hellman (DH), sowie das RSA-Verfahren eingegangen.
Bei der Betrachtung elliptischer Kurven soll zunächst ein mathematischer Hintergrund geschaffen werden, bevor auf die Verwendung, Sicherheit und Konstruktion von geeigneten Kurven eingegangen wird. Ein ausführliches Beispiel soll den Kryptographischen Nutzen von elliptischen Kurven verdeutlichen. Zur Abrundung sind die wesentlichen Fakten über elliptische Kurven aufgezählt.
Abschliessend möchte ich die Möglichkeit nutzen meine Motivation für dieses Thema zu Begründen und die wesentlichen Erkenntnisse zusammenfassen.
Grundbegriffe zum Thema
Aus seiner Kindheit mag der Leser den Begriff der Geheimschrift kennen, wo beispielsweise mit "Zaubertinte" auf weisses Papier geschrieben wurde. Ein mit Zaubertinte geschriebenes Schriftstück lies sich nur unter Anwedung einer bestimmten Technik lesen. Die Wissenschaft der Geheimschrift lässt sich in verschiedene Bereiche und Methoden einteilen, die im folgenden erläutert werden sollen. Es wird allerdings kein Anspruch auf Vollständigkeit erhoben, so dass nur wesentliche Dinge herausgestellt werden.
| Code | Cipher | |
| Substitution | Transposition | |
| Steganographie | Kryptographie | |
| Geheimschrift | ||
Auf Basis der Historie lassen sich sofort zwei Arten der Geheimschrift differenzieren. Das ist zum einen die Steganographie und zum anderen die Kryptographie. Beide Worte lassen sich aus dem griechischen ableiten, wobei "graphein" für schreiben steht. Der Unterschied ergibt sich also aus "steganos" (verborgen) und "kryptos" (versteckt). Nun klingen die beiden Übersetzungen ins Deutsche nicht besonders unterschiedlich und bedürfen daher einer kurzen Erklärung.
Verborgen meint das eine Nachricht im Klartext geschrieben wird, diese dann aber für einen potenitellen Angreifer nicht sichtbar ist. Wie zum Beispiel bei der Zaubertinte, oder aber das Schreiben auf Holztafeln, die dann mit Wachs überzogen werden.
Mit versteckt ist gemeint das der Sinn, und das ist ganz wesentlich, einer Nachricht versteckt wird. Das bedeutet die eigentliche Nachricht kann in Feindes Hand gelangen, ergibt aber zunächst keinen Sinn.
Ausprägungen der Kryptographie sind "Code" und "Cipher", welche durch Transposition, also vertauschen, oder Substitution (ersetzen) realisiert sein können. Ein kleines Beispiel soll betrachtet werden:
Nehmen wir an das Code und Cipher durch die Substitutions-Methode realisiert sind. Um einen Code zu erhalten wird der Satz "Attacke bei Nacht" durch das Code-Wort "Jupiter" ersetzt. Eine Cipher wird geschaffen in dem die einzelnen Buchstaben der Worte ersetzt werden. Im Beispiel wird also jeder Buchstabe durch den im Alphabet folgenden Buchstaben ersetzt. Wir erhalten also die Cipher "Buubdjf cfj Obdiu", was doch schon einen sehr "kryptischen" Eindruck macht.
Auffällig ist bei beiden Realisierungen das es sich um symmetrische Verfahren handelt. Die Kommunikationspartner in einem solchen System müssen das gleiche Wissen über Code-Worte oder Ersetzungsalphabete besitzen. Der Austausch dieses Wissens geschieht meist über unsichere Kanäle und wird somit zum Fallstrick der symmetrischen Verfahren. Würde eine Liste mit Code-Worten oder Ersetzungsalphabeten in die Hände eines potentiellen Angreifers fallen, dann wäre eine sichere Kommunikation nicht mehr möglich. Trotzdem wurden symmetrische Verfahren über mehrere tausend Jahre hinweg eingesetzt und sind auch heute noch Bestandteil von vielen Implementierungen Kryptographischer Algorithmen.
Asymmetrische Verfahren
Mitte der 70er Jahre wurde jedoch ein Durchbruch erzielt und das Problem des Schlüsselaustausches konnte mittels asymmetrischer Verfahren gelöst werden. Bevor auf den Einsatz von elliptischen Kurven eingegangen wird, soll zunächst das allgemeine Kommunikationszenario eines asymmetrischen Verfahrens vorgestellt werden. Daran anschliessend ein Beispiel zum sicheren Schlüsselaustausch nach Diffie-Hellman und eines zum RSA Algorithmus.
Zur Beschreibng des Kryptographischen Modells bedienen wir uns der klassischen Akteure "Alice" und "Bob". In der Regel ist es das Ziel von Alice und Bob Nachrichten auszutauschen, ohne das diese von dritten mitgelesen werden können. Weitere Akteure können sein: "Eve", die einen passiven Angreifer darstellt und "Mallory" der ein aktiver Angreifer ist.
Alice und Bob generieren jeweils ein Schlüsselpaar, bestehend aus einem öffentlichen und einem privaten Schlüssel. Die öffentlichen Schlüssel werden ausgetauscht und die privaten müssen geheim bleiben, um die Sicherheit des Systems zu gewährleisten. Beide führen vor und nach dem Schlüsselaustausch verschiedene Berechnungen durch. Abhängig vom Verfahren unterscheiden sich diese Berechnungen natürlich.
Zunächst der Schlüsselaustausch nach Diffie-Hellman:
Alice und Bob verständigen sich, über einen unischeren Kanal auf zwei möglichst grosse Primzahlen a und p, die auch Eve bekannt sein dürfen. Bob wählt einen geheimen Schlüssel Xb und berechnet den dazugehörigen öffentlichen Schlüssel nach folgender Formel: Yb = aXb mod p. Alice geht genauso vor, wählt allerdings einen eigenen geheimen Schlüssel Xaund berechnet den öffentlichen wie folgt: Ya = aXa mod p. Nun können beide die öffentlichen Schlüssel Ya und Yb austauschen und es wird wieder gerechnet. Der Schlüssel Sa (Alice) berechnet sich aus YbXa mod p und Sb (Bob) aus YaXb mod p. Beide Berechnungen führen zum selben Ergebnis - dem geheimen Schlüssel S (Sa = Sb).
Ein Zahlen-Beispiel mit kleinen Werten soll dies verdeutlichen:
| Alice | Bob |
| a=7, p=11 | |
| Xa=3 | Xb=6 |
| Ya=aXa mod p | Yb=aXb mod p |
| Ya=73 mod 11=2 | Yb=76 mod 11=4 |
| Tausche Ya und Yb aus. | |
| Sa=YbXa mod p | Sb=YaXb mod p |
| Sa=43 mod 11=9 | Sb=26 mod 11=9 |
Somit haben wir über einen unsicheren Kanal einen Schlüssel ausgetauscht, der für ein symmetrisches Verfahren als geheimer Schlüssel genutzt werden kann. Die Kenntnis von a, p, Ya und Yb ist für Eve völlig nutzlos, da ohne zutun eines geheimen Schlüssels z. B. die Formel YaXb mod p nicht berechnet werden kann. Sie hat also das Problem der Bestimmung von Xb in YaXb. Darauf wird aber in einem folgenden Abschnitt noch näher eingegangen.
Herauszustellen bleibt die Tatsache das auf die oben beschriebene Weise noch keine (!) Verschlüsselung durchgeführt wurde. Es ist lediglich ein Verfahren um einen symmetrischen Schlüssel über einen unsicheren Kanal auszutauschen. Zugleich war es aber auch Basis für das von Rivest, Shamir und Adleman implementierte RSA-Verfahren, welches zu den asymmetrischen gehört.
RSA ist im folgenden Abschnitt beschrieben:
Wie für alle asymmetrischen Verfahren typisch wird wieder ein paar von Schlüsseln erzeugt. Ein Chiffrierschlüssel, der öffentlich gemacht wird und ein Dechiffrierschlüssel, der geheim bleiben muss. Erzeugt werden diese beiden Schlüssel wie folgt. Man wählt zufällig zwei grosse Primzahlen p und q, die in etwa gleich lang sein sollten und berechnet dann n = p * q.
Wiederum zufällig wählt man einen Chiffrierschlüssel e der relativ prim zu (p-1)(q-1) ist und berechnet den Dechiffrieschlüssel d.
| e * d = 1 mod ((p-1)(q-1)) <=> d = e-1 mod ((p-1)(q-1)) |
Die Verschlüsselung einer Nachricht m geschieht dann nach c = me mod n und die Entschlüsselung m = cd mod n.
Verwendete Werte für p und q sollten so "zufällig wie möglich" gewählt sein und müssen geheim bleiben um die Sicherheit des Verfahrens zu gewährleisten. Zwischen Alice und Bob werden lediglich die öffentlichen Chiffrierschlüssel ausgetauscht.
Ein Zahlen-Beispiel (im Text):
Der Buchstabenfolge "cv" entspricht nach der ASCII-Tabelle das Wort 6376 in hexadezimaler Schreibweise, also 25462 in Dezimaldarstellung. Zur Verschlüsselung dieser Zahl wird ein n gebraucht. Mit p = 223 und q =281 ergibt sich n = p * q = 62663.
Der Chiffrierschlüssel e darf keine gemeinsamen Faktoren mit (p-1)(q-1) = 222 * 280 = 62160 haben. Mit der gewählten Zufallszahl e = 14321 ist dies erfüllt.
Damit ist das Inverse von 14321 mod 62160 zu berechnen und mit Hilfe des euklidschen Algorithmus ergibt sich d = 32801. Dies ist der geheim zu haltende, private Schlüssel, während der öffentliche Schlüssel, bestehend aus n = 62663 und e = 14321 veröffentlicht wird und p und q vergessen werden können.
Es wird wie folgt verschlüsselt: c = 2546214321 mod 62663 = 15571
Zur Entschlüsselung der Nachricht muss man die Potenzierung des Chiffretexts mit dem geheimen Dechiffrierschlüssel, also 32801 durchführen: m = 1557132801 mod 62663 = 25462
Das selbe Beispiel in sechs Schritten:
| 1.) "cv" => 6376[hex] => 25462[dez] |
| 2.) p=223, q=281 => n = p * q = 223 * 281 = 62663 |
| 3.) Zufallszahl e = 14321 wählen |
| 4.) d = e mod (p-1)(q-1) => d = 14321 mod 222 * 280 = 32801 |
| 5.) c = cve mod n => c = 2546214321 mod 62663 = 15571 |
| 6.) m = cd mod n => m = 1557132801 mod 62663 = 25462 ("cv") |
Um die Betrachtung der asymmetrischen Verfahren abzuschliessen sollen noch kurz die verwendeten Probleme beschrieben werden, welche die Verfahren funktionsfähig machen.
Wie im RSA-Beispiel gesehen wird dort das Problem des "Faktorisierens" (IF) angewendet. Wir haben eine gegebene Gleichung n = p * q, wobei p und q prim und/oder groß sind. Das Problem besteht nun in der Bestimmung von p und q, wenn nur n und ein Faktor bekannt sind.
Bei Diffie-Hellman und auch bei RSA kommt desweiteren das Problem des "Diskreten Logarithmus" (DL) zum tragen. Gegeben ist die Gleichung y = gx, mit grossem x und einem allgemein bekannten g. Hier liegt nun das Problem in der Umkehrung der Exponentation, also dem Bestimmen von x.
Elliptische Kurven Kryptographie (ECC)
Der Einsatz von elliptischen Kurven in der Public Key-Kryptographie wurde 1985 unabhängig voneinander von N. Koblitz und V. Miller angeregt. Das Interesse an elliptischen Kurven für kyptographische Zwecke, d. h. an ECC - Elliptic Curve Cryptography hat seitdem stark zugenommen.
Da ECC-Implementationen eine höhere Effizienz besitzen und auch langfristig als sicher gelten, hat auch deren Anwendung zunehmend an Bedeutung gewonnen. Viele infrastrukturelle Probleme, wie z.B. die Schlüsselgenerierung, sind wesentlich eleganter und schneller gelöst, als dies im derzeit eingesetzen RSA-Verfahren der Fall ist. Außerdem ist im Falle der Verwendung von ECC das Problem der wachsenden Schlüssellänge bei steigenden Sicherheitsanforderungen deutlich besser zu handhaben: wo im Falle von RSA über eine Verdopplung der Schlüssellänge nachgedacht werden muss, reichen im Fall von ECC wenige Bit mehr aus, um die Sicherheit des Systems deutlich zu erhöhen.
Der Vorteil beim Einsatz in Kryptosystemen mit elliptischen Kurven liegt in der schnellen Verschlüsselung und der größeren Flexibilität. Ohne Abstriche hinsichtlich der Sicherheit in Kauf zu nehmen, kommt man mit deutlich geringeren Parameterlängen aus. Dies wirkt sich besonders beim Einsatz in Situationen aus, wo Speicher- oder Rechenkapazität knapp sind, wie z.B. bei Smartcards und anderen Small Devices.
Mathematischer Hintergrund der elliptischen Kurven (ECC)
Bevor weiter auf die elliptischen Kurven eingegangen wird, soll noch ein kleiner mathematischer Hintergrund geschaffen werden.
Es ist bekannt, dass im Körper der reellen Zahlen R unendlich viele Elemente existieren. Mit diesen Elementen lassen sich die Grund-Operationen +, -, * und / durchführen.
Ein endlicher Körper F besitzt dieselben Operationen unterscheidet sich aber dadurch, dass die Anzahl der Elemente auf eine bestimmte Menge q begrenzt ist. Dabei ist q eine Primzahlpotenz q = pn. Oft wird der Körper Fpn mit GF(pn) bezeichnet, dabei steht GF für "Galois-Feld". Ein Beispiel ist die Menge {0,1,2,...,14,15,16}, die den Körper F17 bildet.
Eine elliptische Kurve über einem endlichen Körper K ist die Menge der Punkte (x,y) welche z.B. eine Gleichung der Form
| Y2 = X3 + Ax + B |
erfüllt, wobei x, y, A, B Elemente von K sind. Zusammen mit einem speziellen Punkt 0, der "Punkt an Unendlich" genannt wird, bildet eine elliptische Kurve eine Gruppe. Man bezeichnet sie mit E(K) oder kurz mit E, falls der zugrunde liegende Körper bekannt ist. Die zugrundeliegende Operation dieser Gruppe ist die Addition und das Additionsgesetz für elliptische Kurven kann man graphisch folgendermaßen definieren: Seien P=(x1, y1) und Q=(x2, y2) zwei verschiedene Punkte auf der elliptischen Kurve E, dann ist die Summe P + Q graphisch definiert durch
Additionsgesetz für elliptische Kurven
d.h. man legt eine Gerade durch die Punkte P und Q, die die Kurve in genau einem weiteren Punkt R schneidet. Die Summe P + Q ist definiert durch -R d.h. durch die Spiegelung des Punktes R an der x-Achse.
Es gibt drei Spezialfälle:
1.) Falls P = 0 der Punkt an Unendlich ist, dann sei -P wieder 0 und P + Q = Q.
2.) Falls P = -Q, dann bekommt man P + Q = 0.
3.) Falls P = Q, dann nimmt man als Gerade die Tangente an den Punkt P und verfährt wie oben.
Außerdem ist 2 * P = P + P, so dass auch k * P für eine ganze Zahl k definiert ist.
Bemerkung: Die Punktegruppe einer elliptischen Kurve ist eine additive Gruppe, in der sich aber alle Protokolle für die Schreibweise einer multiplikativen Gruppe übertragen lassen: was beim originalen DL-Problem die Bestimmung von x in gx bedeutet ist im Falle der Verwendung der elliptischen Kurven die Berechnung von k in k * P.
Elliptische Kurven lassen sich über beliebigen Körpern definieren. Verwendung in der Kryptographie finden aber nur Kurven über endlichen Körpern. Erfüllt die elliptische Kurve und der zugrunde gelegete Körper geeignete Bedingungen, so lässt sich das Problem des diskreten Logarithmus (DL) in diesem Fall nicht effizient lösen.
Sicherheit von ECC
Die Sicherheit von kryptographischen ECC Systemen basiert auf der Schwierigkeit des DL-Problems in Gruppen von Punkten auf einer elliptischen Kurve.
Gegeben seien eine elliptische Kurve E über Zp, ein Punkt P Element von E(Zp) der Ordnung n und ein Punkt Q Element von E(Zp). Gesucht ist ein d Element von Z mit 0 <= d <= n-1, so dass Q = d * P (unter der Voraussetzung, das man weiß, dass eine solche Darstellung von Q existiert).
Die Forschung im Bereich der elliptischen Kurven wird seit ca. 150 Jahren betrieben. Seit ungefähr 1985 ist bekannt, dass das Eliptische Kurven DL-Problem für die Kryptographie genutzt werden kann. Kein führender Mathematiker hat bis heute eine bemerkenswerte Schwachstelle entdeckt.
Es muss jedoch beobachtet werden, dass es Klassen von ungeeigneten Kurven gibt, und zwar sind sogenannte supersinguläre Kurven, so wie auch sogenannte anomale Kurven nicht geeignet. Die Attacken auf die Letzteren wurden unabhängig von einander von Semaev, Smart, Satoh und Araki, und für den allgemeinen Fall von Rück gefunden.
Ansonsten bietet ein System, das auf elliptischen Kurven mit einem Modulus von 160 Bit basiert, die gleiche kryptographische Sicherheit wie ein RSA-System mit einem 1024 Bit Modulus. Ein 256 Bit ECC-Schlüssel ist mit einer 3072 Bit RSA-Verschlüsselung vergleichbar und eine ECC-Schlüssellänge von 512 Bit bietet dieselbe Sicherheit wie ein utopischer 15000 Bit RSA-Schlüssel.
Verhältnis der Schlüssellängen von RSA zu ECC
Konstruktion geeigneter Kurven
Für die Festsellung, ob eine gegebene elliptische Kurve für den Einsatz innerhalb der Kryptographie geeignet ist, gibt es gewisse Kriterien. Das Wichtigste dabei ist die Anzahl der Punkte auf der Kurve. Diese muss hinreichend groß sein (in der Regel mehr als 2160, was eine Zahl mit fast 50 (!) Dezimalstellen ist) und sollte eine Primzahl sein oder einen entsprechend großen Primteiler enthalten.
Daneben existieren weitere Eigenschaften, welche gewährleisten, dass das aufbauende Kryptosystem die gewünschte Sicherheit bietet. Diese sind in Standards (wie z.B. ANSI X9.62 oder IEEE P1363) festgeschrieben.
Die heutzutage bevorzugte Methode zur Konstruktion besteht in der Berechnung sogenannter "Zufallskurven": dabei werden in einem ersten Schritt die Parameter zufällig gewählt. Der zweite Schritt betsteht in der Berechnung der Punkteanzahl dieser konkreten Kurve. Damit hat man dann alle Informationen zur Verfügung, um die Eignung dieser Kurve beurteilen zu können. Diese beiden Schritte sind dann einfach solange zu wiederholen, bis eine geeignete Kurve gefunden wurde.
Andere Verfahren (neben der Wahl von Zufallskurven) zur Konstruktion von geeigneten Kurven sind die Methode der Komplexen Multiplikation (CM) sowie die Wahl von sogenannten Koblitz-Kurven. Bei letzteren berechnet man die Anzahl der Punkte mittels des Weil-Theorems.
Ein Nachteil der CM-Methode besteht darin, dass man nicht in der Lage ist, den zugrunde liegenden Körper, über dem die Kurve definiert wird, zu fixieren. Dies kann ein Problem darstellen, falls man eine besonders effiziente Arithmetik in diesem Grundkörper verwenden will. Der Grund hierfür ist, dass in dem (zweigeteilten) Algorithmus im ersten Schritt eine Primzahl gesucht wird, so dass sichergestellt ist, dass eine geeignete Kurve über Zp existiert. Erst im zweiten Schritt wird dann die konkrete Gleichung der Kurve konstruiert.
Das zweite (wesentlichere) Problem mit diesem Konstruktionsverfahren ist, dass für die konstruierten Kurven eventuell Angriffsmöglichkeiten bestehen könnten, wie man im Falle anderer Kurven gesehen hat. Deshalb werden bei den in die Berechnung eingehenden Parametern Größenordnungen verwendet, die den ursprünglichen Vorteil (schnellere Konstruktion gegenüber Zufallskurven) zunichte machen können.
Der Nachteil der speziellen Struktur von Kurven trifft im noch größeren Maße auf die Konstruktionsmethoden mit Koblitz-Kurven zu: Dieses sind Kurven, die über einem relativ kleinen Körper definiert werden, deren Punktegruppe aber erst über einem hinreichend großen Erweiterungskörper betrachtet wird.
Will man für spezielle Lösungen einen eigenen Satz domain parameter verwenden, so ist die Erzeugung dieser Werte unter der URL http://www.kurvenfabrik.de möglich. Man kann sich also seine eigene Kurve erstellen lassen.
Für die Erstellung allgemeiner Anwendungen ist dagegen der Gebrauch standardisierter Parametersätze zu empfehlen. NIST (National Institute of Standards), ANSI und andere Standardisierungsgremien haben sich für die verschiedenen Sicherheitsstufen auf Parametersätze geeignet.
Im folgenden eine von der Kurvenfabrik generierten Kurve:
Hier ist Ihre elliptische Kurve!
Die von der kurvenfabrik für Sie generierte Kurve ist y^2 = x^3 + Ax + B
mit
A = 3581901462183317683252070294477823918975914392619269996644
B = 3581901462183317683252070294477823918975914392619269996644
Der zugrundeliegende Körper ist GF(p) mit der Primzahl
p = 4101883650633306469376667499754908362247825865098673035333 (192 Bit)
Die berechnete Ordnung der Punktegruppe ist
n = 4101883650633306469376667499779316855387771751313072666213
Sie enthält den Primteiler
r = 579116709111013196297708245062730037468272165934360111
der Kofaktor ist (n=r*k)
k = 7083
Ein Basispunkt der Kurve (ein Punkt der Untergruppe mit Ordnung r) ist
G = (2484942334974254391630119290311686144029883301277553112389
,1730137169458595444626864615073196633864897306846999149544)
Die Parameter in hexadezimaler Darstellung:
A = 9214cbd2ba0998c21d901f3b2ca82ca7cbad7d734f6fc064
B = 9214cbd2ba0998c21d901f3b2ca82ca7cbad7d734f6fc064
p = a749a9ddc6f0dbac11b809c1688fa7560e0dd1f4ea889845
n = a749a9ddc6f0dbac11b809c1b76de2ce86b7c27cff2f3665
r = 60bd7bb648c1eed2c0c4a3a8a8d1900feb04bd86c662f
k = 1bab
G = (6558022df5e4bb2e3d5de16a040eaf43543fda21f487b545
,468f7991f533b2f60832aca108244a56406c9a585508fbe8)
Die seed-Werte, entstanden durch rekursives Hashen (SHA-1) ihrer Eingabe.
Damit können Sie nach ANSI X9.63 bzw. IEEE P1363 nachprüfen, dass diese
Parameter eigens für Ihre Kurve zufällig gewählt wurden.
Ihre Kurve erfüllt die Anforderungen von ANSI bzw. IEEE für starke,
kryptographisch geeignete Kurven und kann mit Ihrem EC-Krypto-System
verwendet werden.
Die kurvenfabrik (E-Mail: info@kurvenfabrik.de).
Ein ausführliches Beispiel zu ECC
Als Beispiel sei die ElGamal-Verschlüsselung mit elliptischen Kurven im Telegrammstil vorgestellt:
Vorbereitung
- Wähle eine sichere elliptische Kurve E über einem endlichen Körper Fq, n = #E(Fq) sei die Anzahl ihrer Punkte.- Fixiere einen Punkt P aus E(Fq).
Schlüsselerzeugung
- Alice wählt als privaten Schlüssel eine Zufallszahl a < n, Bobs privater Schlüssel ist eine Zufallszahl b < n.- Alice berechnet ihren öffentlichen Schlüssel A = a * P, Bobs öffentlicher Schlüssel ist B = b * P.
Alice chiffriert einen Punkt N für Bob
- Alice wählt eine Zufallszahl k < n.- Alice berechnet R = k * P und S = k * B + N und sendet R und S an Bob.
Bob dechiffriert R und S
- Bob berechnet -b * R + S und erhält den Punkt N.Die Sicherheit des Verfahrens beruht darauf, dass das ECDLP (Elliptic Curve Discrete Logarithm Problem) schwierig zu lösen ist. Das bedeutet: k * P (das k-fache des Punktes P) ist schnell berechenbar, wenn man k und P kennt. Hingegen ist es im Allgemeinen schwierig, k zu ermitteln, wenn nur P und das Ergebnis von k * P bekannt sind. Ist das ECDLP für einen Angreifer nicht lösbar, so kann er aus dem öffentlichen Schlüssel nicht den privaten Schlüssel berechnen.
Alice und Bob können eine Nachricht N austauschen, weil sie ein gemeinsames geheimnis haben: k * b * P. Alice kennt k * B, und Bob kennt b * R. Alice addiert zur Nachricht N das gemeinsame Geheimnis hinzu und Bob zieht es zum entschlüsseln wieder ab.
Ein Angreifer, der R und S abgefangen hat, kennt zwar k * P und b * P, aber da er das Problem des Diskreten Logarithmus für ECC (ECDLP) nicht lösen kann, gelangt er nicht an das gemeinsame Geheimnis k * b * P.
Es bleibt zu klären, wie Alice eine beliebige Nachricht in einen Punkt N auf der elliptischen Kurve verwandelt. Die Nachricht ist ein Bit-Wort. An diesen genügend kurzen Klartext hängt Alice eine bestimmte Anzahl Bits an, zum Beispiel 10 Bits, mit dem Ziel, die x-Koordinate eines Punktes N zu erhalten. Bei jeder Wahl der 10 Bits hat sie dafür eine Fifty-fifty-Chance, weil die Hälfte aller Zahlen eines enlichen Körpers Quadratzahlen sind. Sobald Bob den Punkt N errechnet hat, streicht er von dessen x-Koordinate 10 Bits und erhält die Nachricht.
Alice einigt sich mit Bob, ein Bit (statt zehn) an Nachrichten anzuhängen. Sie möchte die Nachricht "100" (das ist 4 dezimal) verschlüsseln. Im ersten Versuch hängt sie eine "0" an und erhält "1000" (8[dez]). Nun prüft sie, ob x = 8 eine mögliche x-Koordinate ist:
y2 = 83 + 3 * 8 + 5 = 512 + 25 + 5 = 541 = 14 mod 17
Alice hat Pech. Es gibt keinen passenden y-Wert, die Quadratzahlen in F17 sind nämlich {0,1,4,9,16,8,2,15,13}. Nun versucht Alice eine "1" an die Nachricht anzuhängen und erhält "1001" (9[dez]). Sie setzt x = 9 in die Gleichung der elliptischen Kurve ein:
y2 = 93 + 3 * 9 + 5 = 729 + 27 + 5 = 761 = 13 mod 17
Alice hat Glück. 13 ist eine Quadratzahl in F17, nämlich 13 = 92 mod 17. Es gibt noch die zweite Lösung 13 = (-9)2 = 82. Sie hat also die Wahl zwischen y = 8 und y = 9 und entscheidet sich für P = (x,y) = (9,8). Damit hat Alice die Nachricht "100" in den Punkt (9,8) verwandelt. Klassisch wurde als Gruppe zunächst die multiplikative Gruppe Fq* verwendet, wobei Fq ein endlicher Körper mit q Elementen ist. In dieser Gruppe ist das Berechnen diskreter Logarithmen schwierig, allerdings gibt es wie bei RSA immerhin subexponentielle Algorithmen, um das Problem zu lösen, etwa Index Calculus und Zahlkörpersieb.
ECC F@cts
- Eine elliptische Kurve lässt sich ähnlich wie eine sehr
große Zahl für asymmetrische Schlüssel verwenden.
- Das unbefugte Entschlüsseln ungeschützter Daten bei ECC
erfordert wesentlich mehr Rechenaufwand als etwa RSA.
- Zum Verschlüsseln können kleinere Zahlen benutzt werden,
sodass sich das Verfahren auch in PDAs oder auf
Smartcards leicht einsetzen lässt.
Motivation und Zusammenfassung
Natürlich steht hier ganz klar das persönliche Interesse an der Kryptographie im Allgemeinen im Vordergrund. Nicht zuletzt durch Bücher wie "The Code Book" (ISBN 1-85702-889-9) von Simon Singh wuchs meine Begeisterung für die Kryptographie. Singh schafft es in seinem Buch die Kryptographie in eine unglaublich spannende Verbindung mit der Weltgeschichte zu bringen. Kryptographie ist nicht nur reduziert auf die blose Implementierung von Algorithmen sondern hat auch in vielen Fällen das Schicksal einzelner Personen oder ganzer Völker bestimmt.
Antriebsfeder für die Evolution von kryptographischen Systemen war stets der Kampf zwischen "Codemachern" und "Codebrechern". Ausserdem die erkenntnis das es bislang noch kein 100% sicheres Verfahren gibt. Derzeit stellen asymmetrische Verfahren mit elliptischen Kurven sozusagen die Evolutionäre Spitze da. Von daher ist das Interesse an elliptischen Kurven klar begründbar.
Zusätzlicher Aspekt ist meine Arbeit bei Siemens VDO in Wetzlar. Als führender Hesteller von Navigations Systemen und Autoradios sieht man sich dort ständig der Gefährdung durch Software-Piraterie ausgesetzt. Die Implementierung eines Kryptosystems auf den Navigations Systemen (das sind emebedded systems) ist somit gefordert. Die vielen Performance Vorteile von ECC gegenüber RSA sprechen deutlich für eine ECC Implementierung in embedded systems.
aber der Missbrauch einer schwachen Cipher kann einen sehr falschen Eindruck von Sicherheit vermitteln.
Von daher sollte jeder erkannt haben das der Einsatz von starker Kryptographie lohnt. Nicht nur für Firmen und Unternehem sondern auch zum Einsatz im privaten Bereich.
Dabei lösen asymmetrische Verfahren das klassische Problem der Schlüsselverteilung. Mit dem Einsatz von elliptischen Kurven lassen sich die Randbedingungen sehr elegant gestalten. Tortz kurzer Schlüssellängen und geringer Dauer für die Verschlüsselung ist die Sicherheit als sehr hoch (!) zu bewerten.