[Folie 1]
ECDSA = elliptic curve digital signature algorithm
Bevor wir uns der Frage zuwenden, wie dieser Algorithmus funktioniert, wollen wir uns kurz damit vertraut machen, warum dieses Verfahren für einen Angreifer schwer zu knacken ist.
Grundsätzlich ist für eine elliptische Kurve das Problem, für gegebene Punkte G, Q, die Gleichung
d*G=Q
nach d aufzulösen, schwierig. Kryptographisch heißt dies, wir verstecken unsere geheimen Werte in den Multiplikatoren für die Punkte. Nicht der Punkt ist das Geheimnis, sondern der Multiplikator d.
Was bedeutet überhaupt d*G? Sehr leicht, wir addieren G+G+G+....+G einfach d-mal hintereinander. Das ist, wie beim Potenzieren mod p ebenfalls, nicht die effizienteste Methode. Dem dortigen sukzessiven Quadrieren entspricht bei den elliptischen Kurven (weil die Grundoperation nun "+" heißt) ein sukzessives Verdoppeln (repeated doubling).
Wir gehen nun das hervorragende Dokument ECDSA von Johnson/Menezes/Vanstone durch, das den ECDSA erklärt. Im folgenden beziehen wir uns u.a. auf Abschnitte des Dokuments.
Modell hierfür war natürlich der DSA, wobei man sich die Multiplikationen nun als Additionen denken muss.
Uns interessieren die elliptischen Kurven mod p, die in 4.1 eingeführt werden. Verifizieren Sie das gegebene Beispiel mod 23.
Den Fall F(2^n) (Abschnitt 4.2) besprechen wir in dieser Vorlesung nicht.
Schauen Sie in 5.1 zur Wahl von p und der Anzahl der Punkte n. Im Paper ist n synonym zu |E| und #E zu lesen. Die unter dem früheren Abschnitt Reduktion besprochene Ausnutzung von Teilern von p-1 trifft hier ebenso zu für Teiler von |E|. Daher machen wir dem Angreifer Reduktionen unmöglich, indem wir eine elliptische Kurve E wählen, bei der |E| eine Primzahl ist.
In Abschnitt 5.3 wird von der Domain-Parameter-Generation gesprochen, das betrifft die Variablen
In unserem Spezialfall (|E| Primzahl) ist n=|E| und G irgendein Punkt außer O.
(Folie 2 bzw Abschnitte 5.3 und 6.1 im Dokument)
Wir wollen ein 16-Bit-System aufsetzen und starten daher mit einer 16-Bit-Primzahl p=54037. Durch den Satz von Hasse wissen wir, dass |E| ebenfalls eine 16-Bit-Zahl sein wird, egal wie die Kurvenparameter a, b aussehen. Wir nehmen als Kurve
y^2 = x^3 - 32 mod 54037
Das Zählen von Punkten sollten Sie mit Ihrer eigenen Implementierung hinbekommen, hier sollte
|E|=53623
herauskommen, ebenfalls eine Primzahl.
Wir wählen einen (hier nicht ganz so) zufälligen Punkt. Die x-Koordinate 0 liefert kein passendes y, also probieren wir x=1, erhalten als rechte Seite 54006 mod p, dieses besteht den Quadrattest (siehe README-14).
Die Quadratwurzeln folgen den Regeln p = 5 mod 8 und liefern hier ein y=42442. Also ist G=(1,42442) ein gültiger Punkt auf E.
Als geheimen Schlüssel wählen wir wieder eine zufällige, von allen Angreifern unvorhersagbare Zahl (Empfehlung: /dev/random auf einem nicht gerade frisch gebooteten System). Hier also d unvorhersagbar selbst für die NSA: d=2606.
Erste Aktion ist (entsprechend der Potenzierung im DSA) die Multiplikation des Generatorpunktes mit d.
Q=d*G
Falls Sie es implementiert haben, bitte nachrechnen, es ergibt sich
2606*(1,42442) = (10267,9156)
Der öffentliche Schlüssel ist dann E, G, Q, n, p.
Geheim ist der Parameter d.
Wir sind nun in Abschnitt 7 des Dokuments.
wie beim DSA ist das Signieren mit einer Zufallszahl k parametrisiert.
Unsere "Zufallszahl" vom letzten Jahr war k=2019.
Es ergibt sich k*G=(32724,3370), wobei hier die x-Koordinate schon den ersten Teil der Signatur (r,s) bildet, also r=32724.
Die folgenden Rechnungen können Sie selbst nachvollziehen. Es ist noch eine Anmerkung nötig: wir können nicht mit der Nachricht m in diese Rechnung gehen, diese hat möglicherweise mehrere Megabytes. Stattdessen gehen wir mit dem kurzen Hashwert in die Berechnung, dieser heißt hier e und wird als e=43210 angenommen. Damit ergibt sich die signierte Nachricht, die sich aus Hashwert, r und s zusammensetzt.
Wir sind immer noch in Abschnitt 7 des Dokuments.
Schritt 1 ist wichtig, es ist zu prüfen, dass r, s im Intervall [1,n-1] liegen, sonst sind Attacken denkbar, die r oder s manipulieren, sodass sie in der gleichen Restklasse mod n liegen. Z.B. könnte der Angreifer (Fälscher eines Dokuments) r+n statt r nehmen.
Der Verifizierer berechnet in Schritt 2 den Hashwert, den wir wieder e nennen. Falls die Nachricht nicht manipuliert wurde, ist es der gleiche Hashwert, den der Signierer der Nachricht berechnet hat.
Berechne in Schritt 3 dann w als 1/s mod n, das geht mit dem Euklidischen Algorithmus (siehe README-02).
In Schritt 4 folgen zwei simple Multiplikationen (Achtung: mod n und nicht mod p).
Im letzten Berechnungschritt kommen dann die Punkte der elliptischen Kurve ins Spiel, die als öffentliche Parameter (Public Key) bekannt sind, nämlich G und Q.
Schritt 7 entscheidet über Akzeptanz der Signatur. Der Ergebnispunkt X muss als x-Koordinate den Wert r zeigen. Falls ja, wird die Signatur als gültig betrachtet.