Mathematik: ECC - Elliptic Curves Cryptography
Released by matroid on Mo. 11. September 2006 19:49:15 [Statistics]
Written by Gockel - 3998 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)
\geo ebene(160,160) noaxis() xy(-1,2) nolabel() punktform(.) makro(Schloss,\ replace() nolabel() punktform(.) \ konst(breite,%3) konst(hoehe,%3*1.5) \ konst(A_x,%1) konst(A_y,%2-hoehe/3) \ konst(B_x,%1+0.1*breite) konst(B_y,%2-hoehe/3) \ konst(C_x,%1+0.1*breite) konst(C_y,%2-hoehe/3.75) \ konst(D_x,%1+0.2*breite) konst(D_y,%2-hoehe/3.75) \ konst(E_x,%1+0.2*breite) konst(E_y,%2-hoehe/3) \ konst(F_x,%1+0.5*breite) konst(F_y,%2-hoehe/3.75) \ konst(G_x,%1+0.8*breite) konst(G_y,%2-hoehe/3) \ konst(H_x,%1+0.8*breite) konst(H_y,%2-hoehe/3.75) \ konst(I_x,%1+0.9*breite) konst(I_y,%2-hoehe/3.75) \ konst(J_x,%1+0.9*breite) konst(J_y,%2-hoehe/3) \ konst(K_x,%1+breite) konst(K_y,%2-hoehe/3) \ konst(L_x,%1+breite) konst(L_y,%2-hoehe) \ konst(M_x,%1) konst(M_y,%2-hoehe) \ konst(N_x,%1+0.5*breite) konst(N_y,%2-0.5*hoehe) \ konst(Q_x,%1+0.4*breite) konst(Q_y,%2-2/3*hoehe) \ konst(R_x,%1+0.6*breite) konst(R_y,%2-2/3*hoehe) \ konst(Radius,0.1*breite) \ p(A_x,A_y,A) p(B_x,B_y,B) p(C_x,C_y,C) p(D_x,D_y,D) \ p(E_x,E_y,E) p(F_x,F_y,F) p(G_x,G_y,G) p(H_x,H_y,H) \ p(I_x,I_y,I) p(J_x,J_y,J) p(K_x,K_y,K) p(L_x,L_y,L) \ p(M_x,M_y,M) p(N_x,N_y,N) k(N,Radius,k,hide) \ p(k,240,O) p(k,300,P) p(Q_x,Q_y,Q) p(R_x,R_y,R) \ color(%4) \ s(A,B) s(B,C) s(D,E) s(E,G) s(G,H) s(I,J) s(J,K) \ s(K,L) s(L,M) s(M,A) b(F,H,D) b(F,I,C) b(N,P,O) \ s(P,R) s(R,Q) s(Q,O) \ fill(B_x,N_y,%5) \ insert() \ ) p(-0.5,1.5,E1) p(1.5,1.5,E2) p(1.5,-0.5,E3) p(-0.5,-0.5,E4) fill(E1,E2,E3,E4,E0FFFF) color(aquamarine) s(E3,E4) s(E4,E1) #s(E1,E2) s(E2,E3) color(FFA500) pen(2) param(xx,-0.7,0.3,0.001) param(yy, 0.3,0.7,0.001) plot( sqrt((x-0.5)*x*(x+0.5))+2*x) plot(-sqrt((x-0.5)*x*(x+0.5))+2*x) kurve(xx, sqrt((xx-0.5)*xx*(xx+0.5))+2*xx) kurve(xx,-sqrt((xx-0.5)*xx*(xx+0.5))+2*xx) kurve(yy, sqrt((yy-0.5)*yy*(yy+0.5))+2*yy) kurve(yy, sqrt((yy-0.5)*yy*(yy+0.5))+2*yy) color(000000) pen(1) p(0,1,A) p(0,-1,B) g(A,B) p(1,0,C) p(-1,0,D) g(C,D) Schloss(-0.75,0,0.6,000088,dddddd) \geooff \geoprint()

ECC - Elliptic Curves Cryptography

Wie versprochen, möchte ich nach dem Gruppengesetz elliptischer Kurven nun die hervorstechendste Anwendung elliptischer Kurven in der Praxis vorstellen: Die Verwendung in der Kryptographie. Insbesondere gehe ich dabei auf Schlüsselaustausch, asymmetrische Ver- und Entschlüsselung sowie Signierung mit Hilfe von elliptischen Kurven ein.

Inhalt


Einführung

Ich werde in diesem Artikel sehr "universelle" Verfahren für drei der wesentlichen Grundaufgaben der Kryptographie vorstellen, die in der Praxis aber oft auf die elliptischen Kurven spezialisiert werden. Es soll dabei um ganz wesentliche Bestandteile des verschlüsselten Informationsaustausch gehen: Die Beschaffung eines geheimen Schlüssels für symmetrische Verfahren, Verschlüsselung mit öffentlichem Schlüssel und Signierung von Daten. Viele kryptographische Verfahren basieren auf "asymmetrischen" Problemstellungen, so genannten Einweg- und Trapdoor-Einwegfunktionen. Eine Funktion f heißt dabei Einwegfunktion, wenn 1.) y=f(x) effizient aus x berechnet werden kann und 2.) zu einem gegebenen y nicht mit vertretbarem Aufwand ein passendes Urbild gefunden werden kann. "Effizient" meint dabei in 1.), dass es einen deterministischen Algorithmus gibt, der y in Polynomialzeit aus x berechnet. Im Gegensatz dazu darf sich die Operation auch mit einem probabilistischen Algorithmus nicht in Polynomialzeit umkehren lassen. (Am besten auch dann nicht, wenn man statt des Worst-Case den Average-Case betrachtet, denn auf den kommt es in der Praxis ja an.) Es gibt viele Funktionen, von denen man vermutet, sie seien Einwegfunktionen. Solche verwendet man z.B. bei Hashalgorithmen. Die tatsächliche Existenz einer solchen Funktion hat allerdings bisher niemand nachweisen können. (Ein solcher Beweis hätte übrigens die Ungleichheit von P und NP unmittelbar zur Folge) Zum Beispiel wird vermutet, dass die Multiplikation von Primzahlen eine solche Einwegfunktion ist, denn die Multiplikation als solche ist sehr schnell durchführbar, während für die Zerlegung in Primfaktoren bisher kein Algorithmus mit vertretbarer Laufzeit bekannt ist. Interessant wird es für Verschlüsselungen bei den so genannten Trapdoor-Einwegfunktion. Dies sind Funktionen, die bei Kenntnis einer Zusatzinformation eben doch die effiziente Umkehrung ermöglichen. Eine solche tritt bei vielen Public-Key-Verfahren auf. Beliebter Vertreter dieser Spezies ist das RSA-Verfahren, das darauf basiert, dass die Exponentiation modulo n sehr effizient machbar ist, während das Berechnen einer Wurzel praktisch undurchführbar ist, es sei denn man kennt den privaten zweiten Exponenten, mit dem die Entschlüsselung erfolgt. (Ein wenig detaillierter habe ich die Verschlüsselung mit RSA schon einmal in einem früheren Artikel beschrieben: Starke Pseudoprimzahlen)

Das Problem des diskreten Logarithmus

Die vier Algorithmen, die ich nun vorstellen werde, machen von einem ähnlichen Problem Gebrauch. Es geht dabei um das Diskreter-Logarithmus-Problem (abgekürzt DLP) In seiner allgemeinen Formulierung ist das DLP folgende Problemstellung: Man hat die zyklische Gruppe \G=\<\g\> \(inklusive des Erzeugers \g\) sowie ein Element \y\el\G gegeben. Das Problem besteht nun darin, einen Exponenten k\el\IZ zu finden, so dass \y=\g^k gilt. \(Da man meistens endliche Gruppen betrachtet, geht es genau genommen nur um die Bestimmung von k modulo abs(\G)\) Für bestimmte Gruppen ist dies sehr einfach zu erledigen: Wenn man z.B. die Untergruppe \<2\> von (\IQ^x, opimg(*)) betrachtet, dann liefert eine Anwendung des binären Logarithmus effizient die gesuchte Lösung. Auch in den "Prototypen" der zyklischen Gruppen (\IZ_n, opimg(+)) ist das Problem sehr einfach, da man einfach eine Division mod n durchführen muss. Diese Gruppen eignen sich also nicht für kryptographische Zwecke. Doch schon, wenn man die multiplikativen Gruppen der endlichen Körper \IF_q^x betrachtet, wird das Problem ungleich schwieriger. In der Tat lässt sich das DLP in diesen Gruppen nur mit einem ähnlich hohem Aufwand lösen, wie man ihn zur Faktorisierung natürlicher Zahlen braucht. Für uns von besonderer Bedeutung sind aber natürlich die Punktgruppen elliptischer Kurven über endlichen Körpern. Sie sind zwar i.A. nicht selbst zyklisch, aber man kann einfach ein Element auswählen und die von ihm erzeugte Untergruppe betrachten. Wenn man die Kurve und diese Untergruppe geschickt wählt, dann ist das DLP für diese Konstellation mit keinem bekannten Algorithmus vernünftig lösbar. Aus diesem Grund sind elliptische Kurven und die Verfahren, die auf dem DLP beruhen, vom kryptographischen Standpunkt so interessant: Ein diskreter Logarithmus lässt sich bei geeigneter Wahl der Punktgruppe nämlich sogar noch schwerer berechnen als die Faktorisierung einer Zahl. Das führt zu dem, was ich einleitend schon erwähnte: Für die gleiche Sicherheitsstufe braucht ein Algorithmus, der auf Faktorisierung beruht, ungleich größere Zahlen als ein Algorithmus, der auf dem DLP in elliptischen Kurven beruht. Ein weiterer wichtiger Grund, elliptische Kurven zu verwenden, ist der Grund, dass die Gruppenoperation relativ schnell ausgeführt werden kann. Eine Gruppe ist klarerweise nur dann von praktischem Nutzen, wenn nur das Brechen einer Verschlüsselung oder eines anderen Verfahrens praktisch nicht machbar ist, während das Anwenden des Verfahrens effizient sein muss. Woran aber liegen diese Unterschiede zwischen den einzelnen Gruppen? Ein elementarer Satz der Gruppentheorie sagt uns doch eigentlich, dass alle zyklischen Gruppen derselben Mächtigkeit zueinander isomorph sind. Wieso sind trotzdem verschiedene Vertreter derselben Isomorphieklasse mal mehr und mal weniger geeignet für kryptographische Anwendungen? Die Antwort liegt in der Art dieses Isomorphismus: Es ist nämlich genau der diskrete Logarithmus, der diesen Isomorphismus zu den "Prototypen" Z bzw. Z/nZ darstellt. Wie schwer das DLP in einer Gruppe G zu lösen ist, hängt also davon ab, ob man diesen Isomorphismus in eine effizient berechenbare Form bringen kann. Und genau das ist in vielen Gruppen noch niemandem gelungen. Es ist also der vielzitierte Unterschied zwischen Theorie und Praxis, der das DLP wirklich interessant macht.

Schlüsseltausch nach Diffie-Hellman

Zunächst soll es nun um den Schlüsselaustausch nach Diffie-Hellmann gehen. Dies ist ein simples Protokoll, welches es zwei Gesprächspartnern, die traditionellerweise mit A(lice) und B(ob) bezeichnen werden, ermöglicht, über einen öffentlichen Kanal (der also u.U. abgehört werden könnte) derart Informationen austauschen, dass sie danach beide ein und denselben "Wert" haben, aus dem sie einen gemeinsamen Schlüssel für eine geschützte Kommunikation ermitteln können. Das Vorgehen ist dabei das Folgende: \ll(1)A und B verständigen sich öffentlich über eine Gruppe \<\g\> \ll(2)Sowohl A als auch B wählen geheime Zufallszahlen a bzw. b und berechnen \k_A=\g^a bzw. \k_B=\g^b. \ll(3)Diese Werte \k_A bzw. \k_B schicken sie sich gegenseitig. \ll(4)A berechnet aus den ihr bekannten Werten \k_B^a und B berechnet analog \k_A^b. Wegen \k_B^a=(\g^b)^a=\g^(a*b)=(\g^a)^b=\k_A^b erhalten sie beide dasselbe Gruppenelement, während ein eventueller Lauscher nur \g, \g^a und \g^b kennt. Dieses Gruppenelement kann nun auf eine vorher festgelegte Weise dazu benutzt werden, um einen gemeinsamen Schlüssel für eine symmetrische Verschlüsselungsmethode zu finden. Kann also in der zyklischen Gruppe das DLP effizient gelöst werden, dann kann man auch effizient den geheimen Schlüssel von A und B ermitteln. Wenn man hingegen eine "gute" Gruppe findet, dann sind die Aussichten für den eventuellen Lauscher, den geheimen Schlüssel zu finden, sehr entmutigend. Diese Fragestellung, ob es möglich ist, aus den drei öffentlichen Werten, den Schlüssel zu ermitteln, heißt auch Diffie-Hellmann-Problem. Die einzige bekannte Möglichkeit, es zu lösen, ist eben genau die Anwendung des diskreten Logarithmus. Solange man also eine Gruppe findet, in der das DLP praktisch nicht zu lösen ist, ist man mit Diffie-Hellmann auf der sicheren Seite. Selbst das schwächere Diffie-Hellmann-Entscheidungsproblem, bei dem es nur darum geht, zu überprüfen, ob eine geratene Lösung die richtige ist, ist in vielen Gruppen (z.B. in endlichen Körpern) bisher nicht ohne diskreten Logarithmus vernünftig lösbar. (Wobei hier die endlichen Körper im Vorteil sind. Zumindest dieses Entscheidungsproblem ist nämlich bei einigen Klassen von elliptischen Kurven sehr effizient lösbar)

Public-Key-Verschlüsselung nach ElGamal

Während das Diffie-Hellmann-Protokoll dazu dient, zwei Kommunikationspartnern einen gemeinsamen Schlüssel für eine symmetrische Verschlüsselung zu beschaffen, wird das nun folgende Protokoll eine asymmetrische Verschlüsselung bereit stellen, d.h. ein Public-Key-Verfahren, welches genau wie Diffie-Hellmann auf dem DLP beruht. Benannt ist dieses Protokoll nach dem US-amerikanischen Kryptologen Taher ElGamal (der oft auch Tahir al-Dschamal geschrieben wird) Prinzipiell gibt es drei Stufen des Protokolls (wie üblich sind unsere beiden gesprächigen Kryptographen mit A(lice) und B(ob) bezeichnet): I. Erzeugung des Schlüssels für A \ll(1)A wählt eine endliche, zyklische Gruppe \G=\<\g\> \ll(2)Sie wählt zufällig eine ganze Zahl x\el\ {2,..., abs(\G)-2} und berechnet \y:=\g^x \ll(3)A hat nun (\G,\g,\y) als öffentlichen und x als privaten Schlüssel II. Verschlüsselung einer Botschaft für A von B: \ll(1)B besorgt sich den öffentlichen Schlüssel von A und stellt seine Nachricht als ein Element \m\el\G dar. \ll(2)Er wählt eine zufällige ganze Zahl k\el\ {2,..., abs(\G)-2} und berechnet \a:=\g^k sowie \b:=\m*\y^k \ll(3)B überträgt A die Werte \a und \b III. Entschlüsselung der Botschaft \ll(1)A berechnet mit Hilfe ihres privaten Schlüssels x einfach \m=\b*(\a^x)^(-1) Dies funktioniert deshalb, weil \b*(\a^x)^(-1)=\m*\y^k*(\g^k)^(-x)=\m*(\g^x)^k*(\g^k)^(-x)=\m*\g^xk*(\g^xk)^(-1)=\m ist. Der ElGamal-Algorithmus hat wesentliche Vorteile gegenüber anderen asymmetrischen Verfahren: Dadurch, dass man eine zufällige Zahl k zur Verschlüsselung verwendet, hängt der chiffrierte Text im Idealfall nicht mehr vorhersehbar vom Klartext ab: Der gleiche Klartext kann mit demselben Schlüssel viele verschiedene Chiffretexte ergeben. Dadurch können Angriffe, die mit gewähltem Klartext arbeiten, unwirksam gemacht werden. Ebenso werden statistische Angriffe unbrauchbar, da die Verteilung des Chiffretextes einer Gleichverteilung angenähert wird. Nur wenn das Problem des diskreten Logarithmus in G praktisch lösbar ist, ist es bisher möglich, die Verschlüsselung zu brechen. Das heißt aber wie im letzten Abschnitt, dass lediglich kein anderes Verfahren bekannt ist, die Verschlüsselung zu knacken, ohne das DLP zu lösen. In der Praxis ist das aber natürlich völlig ausreichend.

Signierung nach ElGamal und mit ECDSA

Neben der reinen Verschlüsselung von Daten ist eine der Hauptanwendungen der Kryptographie natürlich auch das Sicherstellen der Authentizität von gesendeten Daten. Man braucht also ein Verfahren, mit dem Alice überprüfen kann, ob ihre empfangene Nachricht tatsächlich von Bob stammt. Manchmal ist es möglich, die asymmetrische Verschlüsselung und die Signierung in einem Algorithmus zu kombinieren (z.B. beim RSA-Public-Key-Verfahren ist dies denkbar). Ich werde aber zwei eigenständige und allgemeine Signierungsprotokolle vorstellen, die mit jeder Verschlüsselungsmethode genutzt werden können: Die Signierung nach ElGamal und den Elliptic Curves Digital Signature Algorithmus (abgekürzt ECDSA)

ElGamal Signatur-Algorithmus

Dieser Algorithmus läuft ebenfalls in drei Schritten ab: I. Erzeugung des Schlüssels für B \ll(1)B wählt wieder eine endliche, zyklische Gruppe \G=\<\g\> mit N Elementen. N wird üblicherweise so gewählt, dass es einige sehr große Primfaktoren hat oder am besten selbst prim ist. \ll(2)Außerdem wählt er eine Funktion f: \G->\IZ, die die Eigenschaft hat, dass die einzelnen Urbilder nur sehr wenige Gruppenelemente enthalten. \ll(3)Ebenfalls wählt er wieder eine Zahl x\el\ {2,..., N-2} und berechnet \y=\g^x \ll(4)B veröffentlicht den Schlüssel (\G,\g,\y,f). Sein privater Schlüssel ist wie gehabt x. II. Signieren einer Nachricht von B für A \ll(1)B stellt die Nachricht als ganze Zahl m dar \(Hashfunktionen sind in diesem Zusammenhang üblich, da sie die Größe von m beschränken\) \ll(2)B wählt eine zufällige Zahl k mit ggT(k,N)=1 und ermittelt \r=\g^k. \ll(3)Schießlich wird s==k^(-1)(m-x*f(\r)) (mod N) berechnet. Falls s==0 ist, so wird das mit einem neuen k noch einmal versucht. \ll(4)Die Signatur ist dann (m,\r,s) III. Verifizieren der Signatur durch A \ll(1)A hat Kenntnis von (m,\r,s) und dem öffentlichen Schlüssel (\G,\g,\y,f) von B \ll(2)Sie berechnet \nue_1=\y^array(f(\r))*\r^s sowie \nue_2=\g^m. \ll(3)Ist \nue_1=\nue_2 so akzeptiert A die Signatur als korrekt. Zunächst untersuchen wir, warum dies funktioniert, d.h. wieso bei einer korrekt signierten Nachricht tatsächlich \nue_1=\nue_2 ist: Ist (m,\r,s) eine korrekte Signatur, so gilt k*s=m-x*f(\r)+hN für ein h\el\IZ. Daraus folgt: \align\nue_1=\y^array(f(\r))*\r^s =(\g^x)^array(f(\r))*(\g^k)^s =\g^(x*f(\r))*\g^(k*s) =\g^(x*f(\r)+m-x*f(\r)+hN) =\g^m*(\g^N)^h =\nue_2*1 Die zweite Frage, die sich aufdrängt, ist natürlich, was für eine Funktion f denn da verwendet werden soll. ElGamal hat seine Verfahren zunächst für die multiplikativen Gruppen der endlichen Körper entwickelt. Wenn man dann z.B. die Gruppe \IF_p^x als Ausgangspunkt hat, dann bietet sich für f die kanonische Abbildung nach {1,...,p-1} an, die aus jeder Restklasse den passenden Repräsentanten auswählt. Wenn stattdessen \Gamma eine Untergruppe einer elliptischen Kurve E(\IF_p) ist, dann ist (u,v)\mapsto\ u eine übliche Wahl für f. Welche Funktion man letzten Endes benutzt, ist zunächst egal. Aus Sicherheitsgründen sollte jedoch die oben genannte Bedingung sichergestellt werden, dass nicht allzu viele Gruppenelemente dasselbe Bild unter f haben. Im Beispiel \IF_p^x wäre f z.B. injektiv, im Beispiel der elliptische Kurven hätten höchstens zwei Punkte dasselbe Bild unter f. Außerdem muss sich f natürlich auch effizient auswerten lassen, sonst würde das Verfahren seinen praktischen Nutzen verlieren. Die nächste Fragestellung ist die nach der Sicherheit des Verfahrens: Ist es dem Außenstehenden C(harles) möglich, fremde Nachrichten mit Bobs Signatur zu versehen? Um dies zu tun, müsste C ein Tripel (m,\r,s) erzeugen, dass \y^array(f(\r))*\r^s=\g^m erfüllt. Bekannt sind ihm dazu nur Bobs öffentlicher Schlüssel (\G,\g,\y,f) sowie die Nachricht m. C könnte also ein \r festsetzen und versuchen, ein dazu passendes s zu finden. Dazu müsste er die Gleichung \r^s=\g^m*\y^(-f(\r)) nach s auflösen können, er müsste also einen diskreten Logarithmus bestimmen. Nach unserer Generalannahme, dass dies praktisch nicht machbar ist, fällt dieser Weg weg. Ein anderer Weg wäre es, s festzulegen und ein passendes Gruppenelement \r zu finden. Dazu müsste die Gleichung \y^array(f(\r))*\r^s=\g^m nach \r aufgelöst werden. Es wird allgemein angenommen, dass dieses Problem mindestens genauso schwer ist, wie das Problem des diskreten Logarithmus, wenn nicht noch schwerer. Sicher ist das allerdings nicht, da diese Frage noch nicht vollständig untersucht wurde. Jetzt kommt auch die Bedingung ins Spiel, dass das Bild von f nicht wesentlich kleiner als \Gamma selbst ist. Wäre im(f) nämlich sehr klein, so könnte C alle möglichen Bilder f(\r_i) durchprobieren, die Gleichung \r^s=\g^m*y^(-f(\r_i)) nach \r auflösen und prüfen, ob f(\r_i)=f(\r) ist. Je kleiner im(f) ist, desto wahrscheinlicher ist dann, schnell einen Treffer zu landen und so eine gültige Signatur (m,\r,s) zu produzieren. Da man sich ja oBdA alle Exponenten modulo N=abs(\G) reduziert denken kann, muss die Wahl von f eigentlich noch weiter eingeschränkt werden. Auch die Gruppenordnung N darf nicht allzu beliebig sein, da sonst noch weitere Angriffe möglich wären, wenn N eine ungünstige Primfaktorzerlegung hat. Daher wählt man meist solche Untergruppen, die deren Ordnung große Primfaktoren hat oder selbst prim ist. Es ist auch noch offen, ob es vielleicht ein Verfahren gibt, \r und s zugleich zu bestimmen. Bisher ist es aber niemandem gelungen und deshalb wird das Signatur\-Verfahren nach ElGamal auch als sicher angesehen.

ECDSA

Ein zweiter, dem ElGamal-Verfahren, sehr ähnlicher Signaturalgorithmus ist der Elliptic Curves Digital Signature Algorithmus - abgekürzt ECDSA -, der eine Abwandlung des klassischen Digital Signature Algorithmus (DSA) für die Benutzung mit elliptischen Kurven darstellt. Wie auch die ElGamal-Protokolle wurde der DSA nämlich zunächst für endliche Körper definiert. I. Erzeugung des Schlüssels für B \ll(1)B wählt eine \(ausnahmsweise multiplikativ geschriebene\) elliptische Kurve E(\IF_p), deren Ordnung gleich l*q ist, wobei q eine große Primzahl ist und l eine kleine Zahl. \ll(2)B wählt einen Punkt \g\el\ E(\IF_p) der Ordnung q und wie gewohnt eine zufällige Zahl x und berechnet daraus \y=\g^x. \ll(3)Die Information (E,p,t,\g,\y) werden öffentlich gemacht, x wird geheim gehalten. II. Signierung einer Nachricht für A von B \ll(1)B stellt seine Nachricht wie gehabt als natürliche Zahl m dar. \ll(2)Er wählt zufällig eine Zahl k\el{2,...,q-2} und berechnet das Gruppenelement \r=\g^k=(u,v)\el\IF_p^2 \ll(3)Daraus berechnet er s==k^(-1)(m+xu) (mod q). Falls s==0, so wählt B einfach ein neues k und versucht es nochmal. \ll(4)Die Signatur ist wieder (m,\r,s). III. Verifizierung der Nachricht durch A \ll(1)A berechnet b_1==s^(-1)*m (mod q) und b_2==s^(-1)*u (mod q) \ll(2)Sie berechnet weiterhin \r||'=\g^(b_1)*\y^(b_2) \ll(3)Die Signatur wird akzeptiert, wenn \r||'=\r ist. Wir können uns auch hier durch eine winzige Rechnung davon überzeugen, dass der Algorithmus bei einer gültigen Signatur perfekt funktioniert. Dann gilt nämlich: \r||'=\g^(b_1)*\y^(b_2) =\g^(s^(-1)*m)*(\g^x)^(s^(-1)*u) =\g^(s^(-1)*m+x*s^(-1)*u) =\g^(s^(-1)*(m+xu)) =\g^k =\r Die Sicherheit von ECDSA ist vergleichbar mit der des ElGamal-Signatur-Algorithmus, da ein Angreifer vor denselben Problemen stehen würde. Der wesentlichste Unterschied liegt in der Effizienz: Für die Verifizierung einer Nachricht benötigt Alice beim ElGamal-Verfahren drei Exponentiationen, beim ECDSA-Verfahren nur zwei, die sich auch noch etwas effizienter als normal gestalten lassen. Da dies der rechenaufwändigste Schritt ist, ist jede Verbesserung willkommen in der Praxis.

Index Calculus

Jetzt möchte ich kurz noch den tieferen Grund besprechen, wieso elliptische Kurven gegenüber der zweiten großen Klasse von kryptographisch verwendbaren Gruppen - den multiplikativen Gruppen der endlichen Körper - so sehr im Vorteil sind. Das liegt am so genannten Index-Calculus-Algorithmus, der es in endlichen Körpern erlaubt, das Problem des diskreten Logarithmus etwas effizienter zu lösen als in anderen Gruppen. Ich deute kurz an, wie der Algorithmus über \IF_p funktioniert. Gegeben ist wie gewohnt ein erzeugendes Element \g von \IF_p^x und ein weiteres Element \y\el\IF_p^x. Gesucht ist eine ganze Zahl k mit \y=\g^k. Wesentlicher Grundstein ist, dass die Abbildung des diskreten Logarithmus auch in endlichen Gruppen aus Produkten Summen macht: log_\g\.(xy)==\log_\g\.(x)+log_\g\.(y)$(mod$p-1) Dies wird im Algorithmus ausgenutzt, um \log_\g\.(b) für ganz bestimmte b\el\G zu bestimmen und daraus schließlich log_\g\.(\y) zu ermitteln. \ll(1)Man wählt eine so genannte Faktorbasis B, die die Primzahlen bis zu einer gewissen Grenze enthält. \ll(2)Man berechnet verschiedene Potenzen \g^k und versucht, je einen Repräsentanten in ein Produkt aus Elementen von B zu faktorisieren. Anhand einer solchen "B\-Zerlegung" erhält man eine lineare Gleichung für die diskreten Logarithmen der Elemente aus B. \ll(3)Wenn man genügend solcher Gleichungen zusammen hat, kann man mittels linearer Algebra die diskreten Logarithmen der Element von B ausrechnen. \ll(4)Danach versucht man \y oder ein Vielfaches von \y ebenfalls in Primfaktoren aus B zu zerlegen. Gelingt dies, so erhält man eine lineare Gleichung für log_\g\.(\y), in der nur die inzwischen bekannten Werte log_\g\.(b) für b\el\ B vorkommen. Zunächst ein Beispiel, um das Wirkungsprinzip zu verdeutlichen: Sei p=401, \g==6 (mod p) und \y==214 (mod p). \ll(1)Wir wählen B={2,3} \ll(2)Indem wir \g^k für k=1,2,3,... berechnen und jeweils versuchen, die Ergebnisse zu faktorisieren, erhalten wir folgende Gleichungen: \ll()\g^1==2^1*3^1 (mod 401) \ll()\g^15==2^0*3^5 (mod 401) \ll(3)Umformuliert sind das die Gleichungen: \ll()1==1*L_2+1*L_3 (mod 400) \ll()15==0*L_2+5*L_3 (mod 400) \ll()Wobei L_b die Abkürzung für log_\g\.(b) sei. Dies ist ein ganz normales lineares Gleichungssystem, das wir relativ einfach lösen können. Dabei erhalten wir nach einer Probe der verschiedenen Möglichkeiten \(da 5 und 15 Nullteiler in \IZ_400 sind, gibt es mehr als eine Lösung\): \ll()L_2==238 (mod 400) \ll()L_3==163 (mod 400) \ll(4)Wir können nun mit Hilfe der Relation 2*\y==428==3^3$(mod$401) den diskreten Logarithmus finden: log_\g\.(2)+\log_\g\.(\y)==3*log_\g\.(3)$(mod$400) => log_\g\.(\y)==251$(mod$400) Insgesamt hat der Algorithmus eine Laufzeit von etwa O(exp(sqrt(2*ln p*ln ln p))). Damit ist er allgemein verwendbaren Algorithmen deutlich überlegen, denn diese haben bisher eine Laufzeit von O(sqrt(p))=O(exp(1/2*ln p). Der wichtigste Effizienzfaktor am Index-Calculus-Algorithmus ist dabei die Wahl von B. Wählt man B kleiner, sinkt die Wahrscheinlichkeit, B-faktorisierbare Körperelemente und nützliche Relationen zwischen ihnen zu finden. Wählt man B größer, steigt die Laufzeit des Algorithmus jedoch dramatisch an. Man kann den Algorithmus auf offensichtliche Weise auf beliebige endliche Körper übertragen, denn diese sind ja in den meisten Fällen als Quotienten von Polynomringen realisiert. Da man auch in Polynomringen eine eindeutige Primfaktorzerlegung hat, funktioniert das Verfahren auch dort. Man muss in B dann auch die Primelemente des Polynomrings zulassen (d.h. die irreduziblen Polynome). Der Punkt ist aber, dass der Index-Calculus-Algorithmus unbedingt die Möglichkeit zur Faktorisierung unbedingt benötigt. So etwas wie eine Primfaktorzerlegung ist in allgemeinen Gruppen aber nicht gegeben. Der Algorithmus lässt sich also nicht weiter ausdehnen. Vor allem lässt er sich nicht auf elliptische Kurven umschreiben und dort bleiben einem Angreifer im Idealfall nur die wesentlich langsameren, allgemeinen Verfahren.

Abschluss

Die vielfältigen Möglicheiten, das diskrete-Logarithmus-Problem zu kryptographischen Zwecken zu benutzen, werden in der Praxis vor allem über endlichen Körpern und elliptischen Kurven eingesetzt. Wie wir gesehen haben, sind elliptische Kurven aber heutzutage deutlich im Vorteil gegenüber den endlichen Körpern. Ich hoffe ich konnte euch diese Anwendungen und Vorteile elliptischer Kurven etwas näher bringen. Ich danke meiner Testleserin susi0815 ganz herzlich für ihre Unterstützung. Wenn ihr weiterhin Interesse habt, werde ich vielleicht noch eine dritte Fortsetzung schreiben, um die zahlentheoretischen Anwendungen elliptischer Kurven wie Primfaktorzerlegungen und Primalitätsbeweise vorzustellen. log_mfg(Gockel)

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfpdf-Datei zum Artikel öffnen, 260 KB, vom 03.10.2006 13:13:29, bisher 3413 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Algebraische Kurven :: Algorithmen :: Elliptische Kurven :: Kryptographie :: Theoretische Informatik :: Angewandte Mathematik :: Informatik :
ECC - Elliptic Curves Cryptography [von Gockel]  
Die Fortsetzung des Artikel über das Gruppengesetz elliptischer Kurven behandelt die Anwendungen der elliptischen Kurven in der Kryptographie. Speziell wird auf Diffie-Hellmann, ElGamal (Verschlüsselung und Signatur) sowie ECDSA eingegangen.
Desweiteren finden sich hier Erläuterungen zum Problem des diskreten Logarithmus' und zum Index-Calculus-Algorithmus.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 3998
 
Aufrufstatistik des Artikels
Insgesamt 65 externe Seitenaufrufe zwischen 2012.02 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com11.5%1.5 %
https://google.ch11.5%1.5 %
http://google.de4467.7%67.7 %
http://google.com46.2%6.2 %
http://search.newtabking.com34.6%4.6 %
http://google.ch46.2%6.2 %
https://google.com34.6%4.6 %
http://www.ecosia.org11.5%1.5 %
https://www.ecosia.org11.5%1.5 %
http://google.at23.1%3.1 %
http://www.bing.com11.5%1.5 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.10.19 01:21viewtopic.php?topic=206582

Häufige Aufrufer in früheren Monaten
Insgesamt 32 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2014-2015 (13x)http://google.de/url?sa=t&rct=j&q=
201205-05 (6x)http://google.de/url?sa=t&rct=j&q=mathe online ecc verschlüsselung
201204-04 (5x)http://google.de/url?sa=t&rct=j&q=ecc key größen
201202-02 (4x)http://google.de/url?sa=t&rct=j&q=ecc kombinieren faktorisiereung
2013-2018 (4x)http://google.com/url?sa=t&rct=j&q=

[Top of page]

"Mathematik: ECC - Elliptic Curves Cryptography" | 10 Comments
The authors of the comments are responsible for the content.

Re: ECC - Elliptic Curves Cryptography
von: KingGeorge am: Mo. 11. September 2006 21:55:18
\(\begingroup\)Hallo Gockel, das ist jetzt zwar "off Topic", aber machst du noch was anderes außer Artikel zu schreiben ? 😉 lg Georg\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Gockel am: Mo. 11. September 2006 22:00:56
\(\begingroup\)Ja natürlich: Mich drüber beschweren, dass das Artikelschreiben so schleppend voran geht :D\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: matroid am: Mo. 11. September 2006 22:16:19
\(\begingroup\)Alles hat seine Zeit, ... ... Artikelschreiben hat seine Zeit, ... und ich bewundere immer die Vollständigkeit und gleichzeitige Verständlichkeit von Gockels Artikeln. Um so schreiben zu können, muß man über die Dinge echt nachgedacht haben, und danach kann man es so schreiben, daß es dem Leser leichter wird, man den Leser da abholt, wo er steht - um ihn mit dem Artikel weiterzubringen. Gockels Artikel haben die Eigenart, daß sie genau sind, aber dem Leser trotzdem vermitteln, wozu man das so und so macht. Das macht Gockel immer sehr, sehr gut. Gruß Matroid\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Wauzi am: Di. 12. September 2006 22:54:16
\(\begingroup\)Hallo Gockel, hochinteressant und trotz aller fachlichen Tiefe leicht zu lesen. Für mich war der Artikel absolutes Neuland, ich hatte bis dato nicht mal gewußt, daß elliptische Kurven zur Verschlüsselung genutzt werden können. Wieder eine Wissenlücke gefüllt. Gespannt bin ich jetzt schon auf den dritten Teil, der mich naturgemäß inhaltlich sehr interessiert. Und eines muß ich (berufsbedingt) unbedingt noch loswerden: Einen Stoff auf diese Art aufzubereiten, mit Hinweisen, Motivationen, Anwendungsideen sowie Nah- und Fernzielen, gehört schon zu den gehobeneren Weihen der Didaktik. Wauzi\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Ex_Mitglied_40174 am: Di. 03. April 2007 21:28:07
\(\begingroup\)Hallo Gockel, Vielen Dank für deinen Artikel - Komplimente hast du ja schon bekommen, deshalb möchte ich mich einfach bei dir bedanken. Ich hatte vorher auch nicht viel Ahnung von Verschlüsselung mittels elliptischer Kurven, trotz kurzen Scripts in der Hand... Die Glühbirne über mir ging erst beim Lesen des Artikels an. Wieviel Zeit und Mühe hast du denn für diesen Artikel aufgewendet?? Und wo hast du das ganze Wissen her? Nochmals vielen Dank für die Hilfe! Ich schreibe gerade Facharbeit über Kryptologie und bin in diesem Zusammenhang auch über die Anwendung elliptischer Kurven gestolpert, womit ich bis jetzt nicht allzuviel anfangen konnte. Genauso hilfreich für mich war übrigens auch dein Artikel über Kurvenintegrale. Ich glaub, ich schau öfter mal vorbei... :D Ganz liebe Grüße und Respekt Die, bei der jetzt die Glühbirne brennt\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Gockel am: Di. 03. April 2007 21:46:32
\(\begingroup\)Hi Der-die-Glühbirne-scheint 😉 Danke für das Lob. Das Wissen habe ich mir aus dem Internet und einigen Büchern zusammengesucht, darunter diese beiden: reviews.php?op=showcontent&id=286 reviews.php?op=showcontent&id=130 Wieviel Zeit ich gebraucht habe, weiß ich nicht mehr genau. Ich habe irgendwann nach dem ersten EC-Artikel angefangen, diesen hier zu schreiben. Ich schätze mal, ich habe irgendwas zwischen zwei und drei Wochen gebraucht (wobei ich natürlich nicht jeden Tag daran gesessen habe). mfg Gockel. P.S.: Einen Artikel über Kurvenintegrale hab ich nie geschrieben. Meinst du vielleicht den Artikel, den pendragon302 dazu geschrieben hat?\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Ex_Mitglied_40174 am: Mi. 04. April 2007 21:55:49
\(\begingroup\)Hallo Gockel, ja, du hast Recht; ich meine wirklich den Artikel von pentragon302. Wie ich da auf dich komme, weiß ich gerade gar nicht mehr. Da war mein Kopf wohl voller elliptischer Kurven... Übrigens nett von dir, dass du auch auf feed-back antwortest. Noch eine Frage: Kennst du dich auch mit Computern so gut aus? Kannst du Programmieren? Ich will das nämlich unbedingt lernen - für Facharbeit und einfach so zum Spaß - aber mir fehlt die Info, wo ich ein gutes Buch dazu herbekommen könnte, möglichst mit Titel "Programmieren für Dummies" oder so. Du musst die Frage aber auch nicht beantworten; gehört ja eigentlich streng genommen nicht ins Forum. Nur, wenn du gerade einen Buchtitel weißt, vielleicht. Also dann will ich dich nicht weiter vom Artikel-Verfassen abhalten Liebe Grüße Antonia (Die, bei der jetzt die Glühbirne brennt... 😉 )\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Gockel am: Do. 05. April 2007 18:56:39
\(\begingroup\)Hi Antonia. Ich kann zwar einigermaßen Programmieren, habe das aber by-doing erlernt und nicht aus Büchern. Aber schau doch mal in unsere Bücherecke: reviews.php Da gibt es ein paar Buchempfehlungen von anderen MPler zum Thema. mfg Gockel.\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Ex_Mitglied_40174 am: Fr. 06. April 2007 19:55:15
\(\begingroup\)Hallo Gockel, Vielen Dank. Ich schau mal. Liebe Grüße\(\endgroup\)
 

Re: ECC - Elliptic Curves Cryptography
von: Gockel am: Do. 01. März 2012 23:13:26
\(\begingroup\)Ein Update zum aktuellen Stand der Sicherheitslage. Das DLP über elliptischen Kurven ist heute nicht mehr so sicher, wie es 2006 war. Schon lange bekannt war, dass es Ausnahmekurven gibt, für die schnellere Algorithmen existieren (supersinguläre Kurven). Das war aber sehr einfach zu vermeiden. Ende 2009 ist aber ein Algorithmus veröffentlicht worden (und in Kürze wird eine Verbesserung veröffentlicht werden), der das DLP unabhängig von der konkreten Kurve schneller als bisher lösen kann - vorausgesetzt der endliche Körper, über dem die Rechnungen ausgeführt werden, hat eine geeignete Größe. In der Tat stimmt meine Aussage aus 2006, es gäbe keinen Index-Calculus-Algorithmus für elliptische Kurve heute nicht mehr, denn die neuen Algorithmen sind in der Tat Verallgemeinerungen des Index-Calculus auf elliptische Kurven. Ganz konkret wird in [1] etwa folgendes Resultat bewiesen: \frameon Seien 0[1] C. Diem. On the discrete logarithm problem in elliptic curves. [2] C. Diem. On the discrete logarithm problem in elliptic curves II. (Preprint)\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]