www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGruppe, Ring, KörperElliptic Curve Cryptography
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Gruppe, Ring, Körper" - Elliptic Curve Cryptography
Elliptic Curve Cryptography < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Elliptic Curve Cryptography: Idee, Tipp, Unterstützung
Status: (Frage) beantwortet Status 
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: []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

        
Bezug
Elliptic Curve Cryptography: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Elliptic Curve Cryptography: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Elliptic Curve Cryptography: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]