Hallo liebe Steemians,
Nun wird es wirklich spannend... Das Thema der elliptischen Kurven spielt in der Kryptographie eine riesen große Rolle, da viele der ersten Verfahren durch die stetig steigende Rechenkapazität nicht mehr sicher sind und als gebrochen gelten.
Die elliptischen Kurven spielen daher eine sehr große Rolle, auch in verschiedenen Algorithmen der Kryptowährungen.
Daher möchte ich heute versuchen, euch dieses Thema ein bisschen näher zu bringen. Um da jedoch noch tiefer ins Detail zu gehen, würde den Rahmen hier auf Steemit ziemlich sprengen. Wer da näheres Interesse hat, sollte sich dann im www dazu ein bisschen umschauen.
Wer die vorangegangenen Posts nicht mitbekommen hat, kann diese hier nachlesen:
Teil 1: Einleitung & klassische Kryptographie
Teil 2: Modulare Arithmetik
Teil 3: Symmetrische Kryptographie #1
Teil 4: Symmetrische Kryptographie #2
Teil 5: Asymmetrische Kryptographie #1
Teil 6: Asymmetrische Kryptographie #2
Teil 7: Asymmetrische Kryptrographie #3
Elliptische Kurven
Mit elliptischen Kurven (EC) können asymmetrische Kryptosysteme mit den Sicherheitseigenschaften der klassischen Verfahren (RSA, DL-based) erzeugt werden. Der Vorteil von EC liegt dabei in einer deutlich kürzeren Schlüssellänge bei equivalenter Sicherheit. ( ca 160-256 Bit vs 1024-3072 Bit)
Definition Elliptische Kurve
Idee: Anstatt über Zp erzeugen wir eine zyklische endliche Gruppe aus den Punkten x,y auf einer Kurve.
Definition 37: Elliptische Kurve
Eine elliptische Kurve über Zp mit p>3 ist die Menge der Paare x,y ∈Zp, für die gilt:
E: y² ≡ x³+a*x+b mod p
Dazu gehört ein imaginärer Punkt 0 (unendlich). Außerdem gilt a,b ∈Zp und
4 * a³ + 27 * b² ≢ 0 mod p (= Diskreminante)
Gruppenoperationen
Zwei verschiedene Operationen: Punkt-Addition (P+Q=R) & Punkt-Verdopplung (P+P = 2P)
Geometrische Darstellung für die Addition und die Verdopplung
Addition: P+Q = R
1. Gerade durch P und Q bilden
2. Schnittpunkt der Gerade mit Kurve => -R
3. Spiegelung von -R an der x-Achse => R
Verdopplung P + P = 2P
1. Tangente an P
2. Schnittpunkt Tangente mit Kurve => -2P
3. Spiegelung an der x-Achse => 2P
Berechnung über Zp (E: x²≡x³ + ax + b mod p)*
Generell: Die Formel für x3 ≡ s² - x1 - x2 mod p
y3 ≡ s (x1-x3) - y1 mod p
Addition (P+Q=R)
s ≡ (y2-y1) / (x2-x1) mod p (P != Q)
Verdopplung (P+P=2P)
s ≡ (3*x1² +a) / (2*y1) mod p (P = Q)
Weiterhin gilt:
P + 0 = P und 0 = (imaginärer Nullpunkt)
P + (-P) = 0 mit -P = (Xp, p-yp)
Beispiel (E: y² ≡ x³+2x+3 mod 7)
Berechnung aller Punkte der Kurve
1. Zwei Mengen festlegen:
M1 = {x³ + a*x + b mod p, ∀x∈Zp)
M2 = {x² mod p, ∀y∈Zp}
Für alle Werte die aus M1 und M2 gleich sind, bilden die jeweiligen X- & Y-Koordinaten einen Punkt auf E
x= 0 1 2 3 4 5 6
M1 = { 3,6,1,1,5,5,0}
y= 0 1 2 3 4 5 6
M2 = { 0,1,4,2,2,4,1}
=> P0=(6,0), P1=(2,1), P2(3,1), P3(3,6), P4(2,6)
Berechnung P0 + P0 = 2P0
-> (2,1) + (2,1) = ?
s ≡ (3 * x1² + a) / 2y1 mod p
≡ (3 * 2² + 2 / (2*1) mod 7
≡ (3*4 + 2) * (2⁻¹) mod 7
≡ 0 * 4 mod 7
≡ 0
x3 ≡ 0² - 2 - 2 mod 7
≡ -4 mod 7
≡ 3 mod 7
y3 ≡ 0 * (2-3)-1 mod 7
≡ -1 mod 7
≡ 6 mod 7
=> 2P0 = (3,6)
ECDH (Eliptic Curve Diffi-Hellmann)
Die Punkte auf E erzeugen eine zyklische endliche Gruppe.
Definition 38: Diskretes Logarithmusproblem auf eliptischen Kurven (ECDLP)
Über Zp* ist das DLP definiert durch den Logarithmus log_g(A) mod p, also g^? ≡ A mod p.
Bei eliptischen Kurven gibt es ein äquivalentes Problem:
? * P = P + P + .?. + P = A, wobei A und P Punkte auf E sind
Definition 39: Theorem von Hasse
Gegeben: eine eliptische Kurve E mod p
Die Anzahl der Punkte auf E liegt im Intervall:
P + 1 - 2√p <= #E <= p+1 +2√p
Bekannt: E:(Ea, Eb, Ep) und <P> = E
Außerdem K = {2,3,...,#E-1}
Alice (Schlüssel a∈rK) Bob (Schlüssel b∈rK)
A = a * P = (xa,ya) ------------(A)---------------> K_AB = b*A = b*a*P = (xab,yab)
B = b * P = (xb,yb)
K_AB = a*B = a*b*P <------------(B)-----------------
= (xab, yab)
=> Der gemeinsame Schlüssel ist der x- und/oder y-Anteil von K_AB
Ausblick
Im nächsten Teil wird es um Einwegfunktionen gehen.
Dazu gehören auch die Hash-Funktionen, die uns in der Krypto-Szene rund ums Mining und co schonmal auf die Füße gefallen sind.
Ich werde versuchen, auch dazu einen kurzen Überblick & Einblick zu geben
Wie immer danke ich dir für dein Interesse. Wenn du Fragen zu einem Punkt hast, immer raus damit... Aufgrund der Komplexität des Themas ist es schwierig, dass in entsprechendem Umfang zu vermitteln, ohne den Rahmen komplett zu sprengen...
Natürlich bin ich immer froh über entsprechendes Feedback und natürlich auch ein Vote :)