Elliptic Curve Cryptography < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:17 Fr 21.07.2017 | | Autor: | qsxqsx |
Hi Zusammen,
Lange ist es her als ich das letzte mal hier war. Matheraum hat mich so quasi durchs ganze Studium begleitet. Und jetzt aus Interesse bin ich mal wieder hier. Versuche auch mal wieder andern zu helfen wenn ich was sehe und Zeit habe.
Ich bin nicht gut in Gruppentheorie aber würde doch gerne folgende Zusammenhänge verstehen.
Es geht grundsätzlich um das Verständnis von ECC (Elliptic Curve Cryptography). Es gibt hierzu eine sehr nützliche Seite: ![[]](/images/popup.gif) ECC A Gentle Introduction. Vorneweg interessieren mich folgende Dinge:
- Diskrete (gewählte) Punkte auf der Elliptischen Kurve werden mittels Addition wieder auf diskrete (!) Punkte abgebildet. Wieso erhält sich das? Was für Kurven müssen das sein, dass dies immer gilt?
- Wieso benötigt man im RSA verfahren längere Schlüssellängen für gleiche "Sicherheit"? Die Schwierigkeit die Schlüssel zu knacken in Abhängigkeit der Anzahl Bits (1024 Bit, 2048 Bit, etc.) nimmt bei ECC viel schneller zu als bei RSA. Meine Vermutung ist, dass weil ja die Dichte an Primzahlen für grössere Zahlen abnimmt (Prime Number Theorem PNT), es darum im Verhältnis zur Schlüssellänge weniger Möglichkeiten gibt die man ausprobieren müsste. Also konkreter formuliert weil ja der RSA Modul N = p [mm] \cdot [/mm] q mit p und q als Primzahlen gegeben ist und somit zu knacken gilt. Wird dabei der Bereich N grösser wird gibt es vergleichsweise weniger Zahlen p und q. Beim ECC ist dies ja soviel ich verstanden habe nicht der Fall.
Gegeben zwei Punkte [mm] P:=(x_{P}, y_{P}) [/mm] und [mm] Q:=(x_{Q}, y_{Q}) [/mm] wobei P + Q [mm] \not= [/mm] 0 und P [mm] \not= [/mm] 0 und Q [mm] \not= [/mm] 0. Die Gerade durch P und Q ist dann gegeben als
y := [mm] \big( \bruch{ y_{P} - y_{Q}}{x_{P} - x_{Q}} \big) \cdot [/mm] (x - [mm] x_{P}) [/mm] + [mm] y_{P}
[/mm]
Wenn ich dies nun in die Elliptische Kurve einfüge könnte ich durch die so entstandene Kubische Gleichung die Lösungen erhalten. Die Kurve ist dabei in [mm] \IR^{2} [/mm] gegeben als
[mm] \{(x,y) \in \IR^{2} | y^{2} = x^{3} + a*x + b, 4*a^{3} + 27*b^{2} \not= 0 \} \cup \{ 0 \}
[/mm]
und in [mm] (\IF_{p})^{2} [/mm] (d.h. die Menge aller Integer modulo p, wobei p eine Primzahl grösser gleich 5 ist) ist die Kurve gegeben als
[mm] \{(x,y) \in (\IF_{p})^{2} | \big( y^{2} = x^{3} + a*x + b \big) mod(p), \big( 4*a^{3} + 27*b^{2} \not= 0 \big) mod(p) \} \cup \{ 0 \} [/mm] mit a und b [mm] \in \IF_{p}.
[/mm]
Aber wieso sind die Lösungen diskret? Besser formuliert: wieso bilden elliptische Kurven in [mm] \IF_{p} [/mm] immer noch eine abelsche Gruppe? Das ist sehr verblüffend. Was für sonstige Kurven gibt es die diese Eigenschaft besitzen?
Vielen Dank!
Grüsse
qsxqsx
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:49 Mo 24.07.2017 | | Autor: | felixf |
Moin qsxqsx!
> Lange ist es her als ich das letzte mal hier war. Matheraum
> hat mich so quasi durchs ganze Studium begleitet. Und jetzt
> aus Interesse bin ich mal wieder hier. Versuche auch mal
> wieder andern zu helfen wenn ich was sehe und Zeit habe.
Willkommen zurück :)
> Ich bin nicht gut in Gruppentheorie aber würde doch gerne
> folgende Zusammenhänge verstehen.
>
> Es geht grundsätzlich um das Verständnis von ECC
> (Elliptic Curve Cryptography). Es gibt hierzu eine sehr
> nützliche Seite:
> ECC A Gentle Introduction.
> Vorneweg interessieren mich folgende Dinge:
>
> - Diskrete (gewählte) Punkte auf der Elliptischen Kurve
Apropos: was meinst du mit diskret?
> werden mittels Addition wieder auf diskrete (!) Punkte
> abgebildet. Wieso erhält sich das? Was für Kurven müssen
> das sein, dass dies immer gilt?
Nun, hängt von der Addition ab  Punkte addieren kann man auf abelschen Varietäten. Wenn so eine abelsche Varietät eine Kurve ist, ist es bereits eine elliptische Kurve.
Also: wenn du auf einer projektiven algebraischen Kurve (sprich eine abgeschlossene Kurve im projektiven Raum, die durch Polynomgleichungen definiert wird) Punkte addieren kannst, ist es bereits eine elliptische Kurve. (Das zu Beweisen ist nicht so einfach.)
> - Wieso benötigt man im RSA verfahren längere
> Schlüssellängen für gleiche "Sicherheit"? Die
> Schwierigkeit die Schlüssel zu knacken in Abhängigkeit
> der Anzahl Bits (1024 Bit, 2048 Bit, etc.) nimmt bei ECC
> viel schneller zu als bei RSA. Meine Vermutung ist, dass
> weil ja die Dichte an Primzahlen für grössere Zahlen
> abnimmt (Prime Number Theorem PNT), es darum im Verhältnis
> zur Schlüssellänge weniger Möglichkeiten gibt die man
Nein, damit hat das nichts zu tun. Auch bei grossen Zahlen gibt es immer noch genügend viele Primzahlen.
> ausprobieren müsste. Also konkreter formuliert weil ja der
> RSA Modul N = p [mm]\cdot[/mm] q mit p und q als Primzahlen gegeben
> ist und somit zu knacken gilt. Wird dabei der Bereich N
> grösser wird gibt es vergleichsweise weniger Zahlen p und
> q. Beim ECC ist dies ja soviel ich verstanden habe nicht
> der Fall.
Der Hauptgrund ist folgender:
1. Bei ECC gibt es für allgemeine Kurven nur Algorithmen mit der Laufzeit [mm] $O(n^{1/2})$, [/mm] wenn $n$ die Gruppengrösse ist. Solche Algorithmen gibt es für das diskrete Logarithmusproblem in allen Gruppen (für allgemeine Gruppen von Primzahlordnung kann man sogar beweisen, dass es nicht besser geht), man hat also keine ECC-spezifischen Attacken die besser sind. Diese Algorithmen haben exponentielle Laufzeit (d.h. sie haben Laufzeit [mm] $O(n^\alpha)$ [/mm] für eine Konstante [mm] $\alpha [/mm] > 0$)
2. Bei RSA (und beim DLP in endlichen Körpern) gibt es dagegen Algorithmen mit viel besserer Laufzeit, etwa das allgemeine und spezielle Zahlkörpersieb. Deren Laufzeit ist subexponentiell, d.h. die Laufzeit ist besser als [mm] $O(n^\alpha)$ [/mm] für *jedes* [mm] $\alpha [/mm] > 0$. Den Term für die Laufzeit kannst du gerne auf der Wikipedia-Seite nachlesen :)
Zumindest sorgt das dafür, dass RSA mit 3072 Bits vergleichbar gut/schlecht gelöst werden kann wie ECC mit 256 Bits. ($n$ ist hier [mm] $n_{RSA} \approx 2^{3072}$ [/mm] bzw. [mm] $r_{ECC} \approx 2^{256}$: [/mm] damit ist [mm] $\exp( (64/9)^{1/3} (\log n_{RSA})^{1/3} (\log \log n_{RSA})^{2/3} [/mm] ) [mm] \approx \exp( [/mm] (64/9 [mm] \cdot [/mm] 3072 [mm] \cdot \log [/mm] 2 [mm] \cdot (\log [/mm] 3072 + [mm] \log\log 2)^2)^{1/3} [/mm] ) [mm] \approx \exp(96.165) \approx 2^{138.7}$ [/mm] und [mm] $n_{ECC}^{1/2} \approx 2^{128}$. [/mm] Hier fehlen noch Konstanten etc., aber die Ergebnisse liegen nur einen knappen Faktor 2048 auseinander.)
> Gegeben zwei Punkte [mm]P:=(x_{P}, y_{P})[/mm] und [mm]Q:=(x_{Q}, y_{Q})[/mm]
> wobei P + Q [mm]\not=[/mm] 0 und P [mm]\not=[/mm] 0 und Q [mm]\not=[/mm] 0. Die Gerade
> durch P und Q ist dann gegeben als
>
> y := [mm]\big( \bruch{ y_{P} - y_{Q}}{x_{P} - x_{Q}} \big) \cdot[/mm]
> (x - [mm]x_{P})[/mm] + [mm]y_{P}[/mm]
>
> Wenn ich dies nun in die Elliptische Kurve einfüge könnte
> ich durch die so entstandene Kubische Gleichung die
> Lösungen erhalten. Die Kurve ist dabei in [mm]\IR^{2}[/mm] gegeben
> als
>
> [mm]\{(x,y) \in \IR^{2} | y^{2} = x^{3} + a*x + b, 4*a^{3} + 27*b^{2} \not= 0 \} \cup \{ 0 \}[/mm]
Die Bedingung $4 [mm] a^3 [/mm] + 27 [mm] b^2 \neq [/mm] 0$ kannst du hier rausnehmen, da $a$ und $b$ Konstanten sind.
> und in [mm](\IF_{p})^{2}[/mm] (d.h. die Menge aller Integer modulo
> p, wobei p eine Primzahl grösser gleich 5 ist) ist die
> Kurve gegeben als
>
> [mm]\{(x,y) \in (\IF_{p})^{2} | \big( y^{2} = x^{3} + a*x + b \big) mod(p), \big( 4*a^{3} + 27*b^{2} \not= 0 \big) mod(p) \} \cup \{ 0 \}[/mm]
> mit a und b [mm]\in \IF_{p}.[/mm]
>
> Aber wieso sind die Lösungen diskret? Besser formuliert:
Hängt davon ab was du unter diskret verstehst! Im topologischen Sinne in [mm] $\IR^2$ [/mm] sind die Punkte sicher nicht diskret.
Über [mm] $\IF_p$ [/mm] gibt es nur endlich viele Punkte.
> wieso bilden elliptische Kurven in [mm]\IF_{p}[/mm] immer noch eine
> abelsche Gruppe? Das ist sehr verblüffend. Was für
> sonstige Kurven gibt es die diese Eigenschaft besitzen?
Dass die Punkte eine Gruppe bilden ist alles andere als trivial. Am "einfachsten" kann man sich das überlegen, wenn man einen Haufen algebraische Geometrie verwendet. Das ist aber auch nur dann einfach, wenn man die alg. Geometrie schon gut genug kennt Kurz zusammengefasst zeigt man hier, dass die Divisorklassengruppe (von Grad 0), geschrieben [mm] $Pic^0(K)$, [/mm] gerade den Punkten auf der Kurve entspricht: der Punkt $P$ entspricht der Divisorklasse von $[P] - [mm] [\mathcal{O}]$, [/mm] wobei [mm] $\mathcal{O}$ [/mm] der unendliche Punkt ist. Um zu zeigen, dass diese Abbildung $E(K) [mm] \to Pic^0(K)$ [/mm] eine Bijektion ist, benötigt man den Satz von Riemann-Roch. Und um zu zeigen, dass sie ein Gruppenhomomorphismus ist, muss man ein wenig rechnen.
Eine elementare Einführung findest du in "An Elementary Introduction to Elliptic Curves" von Leonard Charlap und David Robbins; das Dokument kannst du problemlos im Netz finden.
Alternativ kann man die Gruppengesetze auch elementarer beweisen. Also die Existenz vom neutralen Element, von inversen Elementen sowie die Kommutativität sind einfach; schwierig ist vor allem die Assoziativität. Sie kann direkt etwa mit dem Satz von Cayley-Bacharach gezeigt werden.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:26 Di 22.08.2017 | | Autor: | qsxqsx |
Hi Felix
Vielen Dank für deine Antwort ich habe mich schon etwas genauer damit beschäftigt - aber noch keine Zeit deine Anmerkungen tiefer zu verstehen. Habe mich aber sehr gefreut auf deine Antwort. Im Moment ist ja auch ein Paper ("A Solution of the P versus NP Problem" von N. Blum) aufgetaucht, welches mich noch etwas grübeln lässt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:58 Mi 23.08.2017 | | Autor: | felixf |
Hoi qsxqsx
> Vielen Dank für deine Antwort ich habe mich schon etwas
> genauer damit beschäftigt - aber noch keine Zeit deine
> Anmerkungen tiefer zu verstehen. Habe mich aber sehr
> gefreut auf deine Antwort.
Das wiederum freut mich :)
> Im Moment ist ja auch ein Paper
> ("A Solution of the P versus NP Problem" von N. Blum)
> aufgetaucht, welches mich noch etwas grübeln lässt.
Ja, das ist noch interessant, aber schwer zu sagen was da rauskommt :) Vielversprechende Paper gab es in die Richtung (bzw. das Gegenteil) ja schon ab und an mal...
Anyway, eine praktische Relevanz für die Kryptographie hat das ganze eher nicht. Das ist ein rein theoretisches Resultat, denn selbst wenn man einen Algorithmus hätte, der NP-Probleme in polynomieller Zeit lösen kann, so wäre der Grad vom Polynom ziemlich sicher so hoch, dass er ausser bei winzigen Instanzen nicht weiterhelfen würde. Also aus Kryptographie-Praxis-Sicht ist die Frage $P = NP$ nicht wirklich wichtig 
LG Felix
|
|
|
|
