Mathlog· Über das Blog· Blogroll· RSS· Kontakt
Blog durchsuchen
Profil

퀘 스 너 틸 로 wohnt in Seoul und arbeitet über
geometrische Topologie.

Letzte Einträge
Kommentare
Blogroll
Blogverzeichnis - Blog Verzeichnis bloggerei.de Mathlog - Blogged

komplette Blogroll » 

Kategorien
Archiv

« vorheriger Beitrag  · nächster Beitrag »

04.12.09 · 11:59 Uhr

Topologie von Flächen XCIV

Kategorie: Naturwissenschaften  ·  Kommentare: 11

Elliptische Kurven - "Defending Our Nation, Securing The Future".

Wir hatten ja in der Kryptographie-Reihe schon darüber geschrieben, daß die National Security Agency (Motto: "Defending Our Nation. Securing the Future.") Verschlüsselung im Internet in den nächsten 10 Jahren auf Elliptische-Kurven-Kryptographie umstellen will.nsaelliptic.png

Elliptische Kurven über den komplexen (oder reellen) Zahlen werden dabei aber nicht zum Einsatz kommen. Warum? Letztlich, weil diese sich als Torus darstellen lassen.

Zunächst: elliptische Kurven sind Kurven mit der Gleichung y2=x3+ax+b für geeignete Zahlen a,b (und zusätzlich noch einem "Punkt im Unendlichen"), cf. TvF 92.

chp_elliptic.jpg
D.Rogalski

Auf elliptischen Kurven ist eine "Addition" anhand der folgenden Bilder definiert:

ECClines.png
die Gerade durch 2 Punkte schneidet die Kurve in einem 3. Punkt, dessen Spiegelbild ist (per Definition) die Summe der ersten beiden Punkte.
("P+Q" ist also nicht R, sondern das Spiegelbild von R an der x-Achse. Im Bild oben ist (2,5)+(-2,3)=(1/4,-33/8).)
Nullelement dieser Addition ist per Definition der Punkt im Unendlichen, inverses Element ist jeweils das Spiegelbild an der x-Achse (Bild in der Mitte rechts).
Analog: wenn man das Doppelte eines Punktes definieren will (Bild rechts Mitte), nimmt man die Tangente an den Punkt, deren zweiter Schnittpunkt mit der Kurve wird an der x-Achse gespiegelt.


In der Kryptographie nutzt man aus, daß es einfacher ist ng=g+g+...+g zu berechnen als umgekehrt, wenn ng bekannt ist, daraus n zu bestimmen. (Genau funktioniert der Diffie-Hellman-Schlüsselaustausch wie folgt: Der Sender merkt sich eine Zahl a und schickt ag an den den Empfänger, der Empfänger merkt sich eine Zahl b und schickt bg an den Sender, beide können jetzt abg=bag berechnen und verwenden im weiteren abg als gemeinsamen Schlüssel. Dieser Schlüssel ist sicher, weil er nie über das Netz übertragen wurde, und weil es für einen Hacker, der ag und bg abgefangen hat, schwierig ist, daraus a und b zu berechnen.)

Damit mit einer elliptischen Kurve sicher verschlüsselt werden kann, braucht man also: es gibt kein effizientes Verfahren, um n zu berechnen, wenn man P und nP kennt.
(D.h. man kann das Diskreter-Logarithmus-Problem auf der elliptischen Kurve nicht effizient lösen.)

Letzte Woche hatten wir aber erwähnt, daß jede (komplexe) elliptische Kurve E das Bild von einem Torus C/L ist. Die Abbildung C/L-->E ist gegeben durch z-->(p(z),p'(z)/2). (p(z) ist die Weierstraß-Funktion des Gitters.)

Es gibt eine "Additionsformel" für die p-Funktion, d.h. eine Formel für p(z1+z2), die letztlich gerade besagt, daß die Addition komplexer Zahlen in C/L genau der oben durch Bilder definierten Addition von Punkten der elliptischen Kurve E entspricht.

Wenn man weiß, wie sich eine elliptische Kurve als Torus C/L schreiben läßt, dann kann man damit leicht die Diffie-Hellmann-Entschlüsselung knacken: wenn man zwei komplexe Zahlen z und nz (modulo des Gitters L) gegeben hat, erfolgt die Berechnung einfach durch Division komplexer Zahlen.

Komplexe elliptische Kurven werden also bei der 'Verteidigung der Heimat und Sicherung der Zukunft' nicht mitmachen dürfen. Das bleibt elliptischen Kurven über endlichen Körpern vorbehalten.
Tatsächlich hat die NSA eine relativ kleine Liste elliptischer Kurven (nämlich 15, davon 10 über binären Körpern und 5 über Primkörpern), die verwendet werden sollen. Ein pikantes Detail am Rande: auf viele Eigenschaften von elliptischen Kurven gibt es Patente von Unternehmen oder Privatpersonen, die NSA mußte für einige der vorgeschlagenen Kurven zunächst eine Lizenz erwerben. (Einzelheiten hier, vorletzter Absatz.)

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 88, Teil 90, Teil 91, Teil 92, Teil 93

 

Autor: Thilo· 11 Kommentare· Permalink· Trackback-URL

Tags: · · · · · · ·

Weitere Artikel bei Mathlog

Weitere Artikel auf ScienceBlogs

Kommentare (11)

Kommentar-Direktlink schlappohr· 04.12.09 · 17:38 Uhr

Hast Du nicht "Bild in der Mitte" und "Bild rechts" vertauscht? Die Tangente bei der Punktverdopplung von Q ist im mittleren Bild zu sehen.

Interessant, dass die Amis Lizenzen von einer *kanadischen* Firma kaufen mussten, um ihre Future zu securen...

Author Profile Page Thilo Kuessner· 04.12.09 · 17:43 Uhr

Klar, danke, ist jetzt korrigiert.

Kommentar-Direktlink Redfox· 05.12.09 · 01:12 Uhr

Ein pikantes Detail am Rande: auf viele Eigenschaften von elliptischen Kurven gibt es Patente von Unternehmen oder Privatpersonen, die NSA mußte für einige der vorgeschlagenen Kurven zunächst eine Lizenz erwerben.
Mein Lieblingszitat dazu, vom guten Gutmann:
"ECC curves are divided into three groups, weak curves, inefficient curves, and curves patented by Certicom" -- Peter Gutmann, 10 Aug, 2001.

Kommentar-Direktlink anomous· 05.12.09 · 10:56 Uhr

"Der Sender merkt sich eine Zahl a und schickt ag an den den Empfänger, der Empfänger merkt sich eine Zahl b und schickt bg an den Sender, beide können jetzt abg=bag berechnen und verwenden im weiteren abg als gemeinsamen Schlüssel. Dieser Schlüssel ist sicher, weil er nie über das Netz übertragen wurde, und weil es für einen Hacker, der ag und bg abgefangen hat, schwierig ist, daraus a und b zu berechnen"

Aber woher wissen den die beiden welches g zu benutzen ist?

Author Profile Page Thilo Kuessner· 05.12.09 · 11:38 Uhr

@ anomous:
Die elliptische Kurve und auch das zu verwendende g sind "öffentlich bekannt", d.h. sie werden einfach über das Netz übertragen. Geheim sind nur a, b und dann eben der gemeinsame Schlüssel abg.

Kommentar-Direktlink Hans Brandl· 05.12.09 · 15:19 Uhr

Die NSA hat eine komplette Familie von kryptographischen Funktionen der nächsten Generation standardisiert ( http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography)
Suite A ist dabei für den behördeninternen Einsatz , Suite B für den Einsatz in der Wirtschaft und bei Privatleuten gedacht). Bei der Definition dieser Verfahren zum Einsatz im Behörden-Bereich (auch public to gov) hat es sich die NSA sehr einfach gemacht und einfach eine Sammellizenz von Certicom erworben.
Für den kommerziellen Einsatz (bei dem sich inzwischen die Suite B Verfahren als zukünftige de-facto Standards durchgesetzt haben) haben die Industrie und auch die nichtamerikanische Cryptobehörden nochmals intensiv nachgedacht (Die Lizenzen für zb. 100 Mio. Crypto-Chipkarten pro Jahr für e-Banking oder 200 Mio. Trusted Platform Module (TPM) für Trusted Computing wären z.B. einfach nicht bezahlbar gewesenen ) und damit sind einige der NSA-Vorschläge (ECQMV) jetzt aus der Suite B verschwunden.
Übrigens auch das BSI in Deutschland war da sehr aktiv mit alternativen Beiträgen.
EC ist inzwischen auch einer der Standardalgorithmen für den internationalen elektronischen Pass, wieviele solcher Pässe wird es wohl in Zukunft geben?
Wer es noch nicht wusste: Cryptographie ist inzwischen eine Anwendnung mathematischer Verfahren von erheblicher wirtschaftlicher Bedeutung mit der Millionen von Euro umgesetzt werden!

Kommentar-Direktlink anomous· 06.12.09 · 05:21 Uhr

"und weil es für einen Hacker, der ag und bg abgefangen hat, schwierig ist, daraus a und b zu berechnen"
"Die elliptische Kurve und auch das zu verwendende g sind "öffentlich bekannt", d.h. sie werden einfach über das Netz übertragen. Geheim sind nur a, b und dann eben der gemeinsame Schlüssel abg."

OK, jetzt mal Hirn einschalten und nachdenken warum ich die Frage gestellt habe, gelle. Danach antworten.

Kommentar-Direktlink rolak· 06.12.09 · 06:26 Uhr

ok.. einschalten, hochfahren, grübeln, Kaffeedoping, Moment noch, hmm: Weil Nikolaus ist?

Author Profile Page Thilo Kuessner· 06.12.09 · 11:28 Uhr

Ich verstehe die Frage auch nicht recht. Also konkret: Sie besuchen die Webseite eines Online-Händlers und wollen dort Ihre Daten eingeben. Der Computer des Online-Händlers benutzt eine bestimmte elliptische Kurve E und einen bestimmten Punkt P (und überträgt diese an Ihren Rechner). Außerdem generiert er zufällig eine Zahl b, die nicht übertragen wird. Ihr Rechner generiert zufällig eine Zahl a, die ebenfalls nicht übertragen wird. Ihr Rechner schickt jetzt aP=P+...+P (a-fache Summe) an das Online-Kaufhaus und dessen Recher schickt bP=P+...+P (b-fache Summe) an Ihren Rechner. Weil Ihr Rechner jetzt a und bP kennt, kann er abP berechnen. Entsprechend kann der Rechner des Kaufhauses baP berechnen, was dasselbe ist.
abP ist dann der gemeinsame Schlüssel auf den sich Kaufhaus und Kunde geeinigt haben und mit dem die eigentlichen Daten dann mit AES verschlüsselt werden.

Ein Hacker kennt eventuell P, aP und bP. Um den Schlüssel abP berechnen zu können, müßte er a und b berechnen. Das Problem, aus aP bzw. bP a oder b zu berechnen, heißt Diskreter-Logarithmus-Problem und ist für viele elliptische Kurven zu aufwändig. http://de.wikipedia.org/wiki/Diskreter_Logarithmus

Kommentar-Direktlink rank zero· 17.12.09 · 07:18 Uhr

[Gehört unter XCV, dort aber derzeit keine Kommentare möglich (bug bei Einbindung der Filme?)]

Die Menge aller elliptischer Kurven bezeichnet man als Modulraum.

Nein.

"Modulraum" ist eine allgemein in der Mathematik übliche Bezeichnung für eine Menge von mathematischen Objekten "modulo" einer Äquivalenzrelation.

Das korrigiert zwar den falschen ersten Satz (es fällt wohl auch dem Laien auf, dass es hier plötzlich nicht mehr die Menge, sondern Äquivalenzklassen davon sind), andererseits ist der Satz für sich genommen sogar noch falscher, also:

Nein.

Die Theorie solcher Modulräume heißt Geometrische Invariantentheorie.

Das korrigiert wiederum den falschen vorhergehenden Satz - und wieder fällt wohl auch dem Laien auf, nun von "solchen" Modulräumen die Rede ist, obwohl doch "allgemein" "solche" Objekte Modulräume heißen sollen. Gibt es etwa doch andere?

Davon abgesehen, setzt die GIT natürlich eine sehr spezielle Struktur der Äquivalenzrelation voraus, also wieder:

Nein.

(Ich weiß, dass es sehr schwierig ist, hier allgemeinverständlich und einigermaßen präzise zu sein. Aber die drei Sätze tun wirklich weh.)

Kommentar-Direktlink Thilo· 17.12.09 · 12:03 Uhr

Ja, die mathematik-philosophische Frage, wann zwei mathematische Objekte gleich sind.
Ist der Rn der einzige n-dimensionale (reelle) Vektorraum? Oder gibt es viele n-dimensionale Vektorräume, die alle zum Rn isomorph sind?
Analog: sind zwei elliptische Kurven gleich, wenn sie isomorph sind oder gibt es unterschiedliche isomorphe elliptische Kurven?
Darüber sollte ich vielleicht auch mal einen Beitrag schreiben.
Die beiden Videos zeigen den "Modulraum" bestimmter Polynome, und H2/SL(2,Z) ist dann die Menge der (Isomorphieklassen) elliptischer Kurven. Den Unterschied hätte ich wohl tatsächlich noch stärker betonen sollen.
"Ich weiß, dass es sehr schwierig ist, hier allgemeinverständlich und einigermaßen präzise zu sein." Das Schöne im Internet ist ja, daß man für die präzisen Definitionen immer einfach auf die jeweiligen Wikipedia-Artikel verlinken kann und die nicht jedesmal noch mal mit copy/paste herüberholen muß.

Kommentar schreiben

Netiquette·AGB

 

Blogticker
ScienceBlogs.com

mehr auf www.scienceblogs.com »

© by ScienceBlogs.de · 2008