< Return to Video

djb, Tanja Lange: ECCHacks

  • 0:09 - 0:15
    Entschuldigung für die technischen Schwierigkeiten, für den wirklich sinnvollen Teil des Vortrags gebe ich nun hier weiter an Tanja.
  • 0:15 - 0:19
    Hallo, ich bin Tanja und neben mir ist Dan, falls das noch nicht bekannt war.
  • 0:19 - 0:21
    (Gelächter)
  • 0:21 - 0:27
    Also wir werden über Crypto und ein paar Elliptic curves reden, und hoffen, dass dies ist eine sanfte Einführung ist
  • 0:27 - 0:29
    Wenn es zu langweilig ist, naja, es ist spät am Abend, also machen Sie ein kurzes Schläfchen,
  • 0:29 - 0:33
    wachen Sie ab zu und zu auf und schauen, ob sie noch mitkommen.
  • 0:33 - 0:35
    Also warum Kryptographie?
  • 0:35 - 0:39
    Wenn Sie Kryptographie im Internet oder für elektronische Zahlungen verwenden,
  • 0:39 - 0:43
    dann sehen sie zum Beispiel ein SSL Zertifikat in welchem Kryptographie verwendet wird.
  • 0:43 - 0:47
    Wenn Sie einen elektronischen Pass oder einen elektronischen Personalausweis haben, welcher Signaturen nutzt, oder
  • 0:47 - 0:53
    wenn Sie TLS verwenden um vertrauliche Daten zu senden, dann möchten Sie Verschlüsselung nutzen.
  • 0:53 - 1:00
    Wenn Sie einen SSL-Exchange haben, nutzen sie z.B. RSA, Diffie-Hellmann oder ECDH.
  • 1:00 - 1:06
    Und um EC, ECDH und ECDSA geht es heute in diesem Vortrag.
  • 1:06 - 1:10
    Außerdem gibt es noch einen großer Anteil an der Kryptographie, die sogenannte "secret key cryptography".
  • 1:10 - 1:14
    Das ist wirkliche eine coole Sache, es sie ist viel viel schneller als alles was wir Ihnen heute vorstellen.
  • 1:14 - 1:19
    Aber sie setzt voraus, dass die beiden Parteien, die miteinander reden möchten sich bereits kennen,
  • 1:19 - 1:22
    also dass sie bereits einen Schlüsselaustausch durchgeführt haben
  • 1:22 - 1:23
    Wir werden Ihnen zeigen wie man diesen Schlüsselaustausch durchführt.
  • 1:23 - 1:30
    Und vielleicht dann im nächsten Jahr, die symmetrische Kryptographie.
  • 1:30 - 1:35
    Okay, also warum sollte man in public key Kryptographie ECC (elliptic curve cryptography) nutzen
  • 1:36 - 1:39
    Was hat dazu geführt, dass Personen sich für ECC interessieren?
  • 1:40 - 1:44
    Die einfache Antwort dafür ist eine Angriffsstrategie namens Index-Calculus.
  • 1:44 - 1:47
    Nun diese nutzen Sie, wenn Sie den RSA Schlüssel von jemanden faktorisieren,
  • 1:47 - 1:51
    oder den ursprünglichen nicht-elliptischen Diffie-Hellman knacken, möchten.
  • 1:51 - 1:52
    Dann nutzten Sie Index-Calculus.
  • 1:53 - 1:55
    Dies ist eine ausgefallene Nutzung von Mathematik sowie die damit einhergehenden Algorithmen.
  • 1:55 - 1:58
    Im Endeffekt werden diese immer schneller und schneller,
  • 1:58 - 2:01
    sodass wir am Ende gar nicht wissen, wie schnell sie einmal sein werden.
  • 2:01 - 2:04
    Hier ist ein Teil der Geschichte, wann die Algorithmen erfunden wurden:
  • 2:04 - 2:08
    1975 wurde einer der ersten Index-Calculus Algorithmen, CFRAC,
  • 2:08 - 2:10
    zum Faktorisieren von großen Zahlen entwickelt.
  • 2:10 - 2:15
    In 1977, 1982, 1990. 1994 gab es dann alle möglichen Arten von Fortschritten.
  • 2:15 - 2:18
    Sie haben letztes Jahr von der Cryptoapocalypse gehört.
  • 2:18 - 2:22
    Und diese ist eine der neusten Fortschritte in Indexcalculus
  • 2:22 - 2:25
    Es ist zwar nicht relevant für das Knacken von RSA,
  • 2:25 - 2:29
    aber es ist ein Beispiel dafür, dass die allgemeine Strategie des Index-Calculus
  • 2:29 - 2:36
    immer weiter verfeinert, hochwertiger und schneller wird.
  • 2:36 - 2:38
    Das ist nicht die ganze Geschichte.
  • 2:38 - 2:42
    Wenn man sich die wissenschaftliche Fachliteratur anschaut, dann gibt es dort auch viele Verbesserungen.
  • 2:42 - 2:44
    Wir sind glücklich, wenn wir doppelt so schnell faktorisieren können,
  • 2:44 - 2:50
    aber das sind große Schritte, wenn man die Sicherheit von zwei typischen RSA Größenordnungen bedenkt.
  • 2:50 - 2:53
    Also da ist RSA 1024, was man noch häufig im Internet sehen kann
  • 2:53 - 2:57
    und da ist RSA 2028, was hoffentlich Ihre Bank nutzt.
  • 2:57 - 2:59
    Dann sind dort zwei Zeilen mit Nummern...
  • 2:59 - 3:01
    Entschuldigung
  • 3:01 - 3:04
    Zwei Spalten mit Nummern, wo Sie sehen können, wie sehr die Sicherheit abgenommen hat.
  • 3:04 - 3:11
    Also zurück in 1975, der CFRAC Algorithmus würde immer noch 2 hoch 120 Operation brauchen,
  • 3:11 - 3:15
    um die selbe Arbeit zu machen, welche in vielen Jahren später ein mit Zahlen gefülltes Sieb macht.
  • 3:15 - 3:18
    Also in den 80er würde nur 2 hoch 80 Operationen notwendig sein.
  • 3:18 - 3:19
    Daher ist hier ein großer Rückgang vorhanden,
  • 3:19 - 3:20
    von 120 Operations auf 80.
  • 3:20 - 3:25
    Und es ist nicht nur eine Verringerung um 40 im Exponenten, es ist deutlich größer,
  • 3:25 - 3:30
    Es reduziert diesen von 170 auf 112.
  • 3:30 - 3:33
    Somit ist es nicht nur eine lineare Verringerung im Exponent.
  • 3:33 - 3:35
    Es ist mehr als eine lineare Verringerung im Exponent.
  • 3:35 - 3:46
    In '85, als die [unverständlich],
  • 3:46 - 3:52
    hat Miller elliptic curves als Alternative zu faktorisierungsbasierten Methoden vorgeschlagen,
  • 3:52 - 3:57
    da Faktorisierung und Diffie-Hellman von den Algorithmen geknackt werden.
  • 3:57 - 4:01
    Miller sagte: "Nun, ich habe mir dieses neue Prinzip der elliptic curves angesehen,
  • 4:01 - 4:09
    und es ist extrem unwahrscheinlich, dass eine Index-Calculus Attacke auf die elliptic curves Methode jemals klappen würde.
  • 4:09 - 4:14
    Also können wir alle die Verbesserungen dieser Methoden ignorieren,
  • 4:14 - 4:20
    die die Faktorisierung und Diffie-Hellman geschwächt haben."
  • 4:20 - 4:30
    Um in elliptic curve cryptography sanft einzusteigen, haben wir hier die clock cryptography.
  • 4:30 - 4:33
    Nun, hier ist Bild von einer Uhr.
  • 4:33 - 4:35
    Hast du zufällig eine Uhr um sie den Menschen zu zeigen,
  • 4:35 - 4:37
    falls sie nicht mehr dran gewöhnt sind, wie eine Uhr aussieht?
  • 4:37 - 4:39
    Also ein rundes Ding.
  • 4:39 - 4:44
    Wissen Sie, wenn Sie denken dass eine Uhr Ihnen Ziffern nebeneinander anzeigt, hier, so sahen Uhren früher aus.
  • 4:44 - 4:47
    Für Mathematiker, es ist x^2 + y^2 = 1
  • 4:47 - 4:49
    Es ist etwas kaputt, deswegen sind wir zu spät.
  • 4:49 - 4:50
    (schmunzeln)
  • 4:50 - 4:55
    Die elliptic curves die wir Ihnen später im Vortrag zeigen,
  • 4:55 - 4:57
    beinhalten nicht die Uhr.
  • 4:57 - 5:01
    Die clock cryptography ist kein Beispiel für elliptic curve cryptography,
  • 5:01 - 5:03
    aber sehr, sehr nah dran.
  • 5:03 - 5:07
    Daher starten wir mit der clock cryptography und wenn Sie damit vertraut sind,
  • 5:07 - 5:11
    machen wir eine kleine Anpassung und dann haben wir die elliptic curve cryptography.
  • 5:11 - 5:15
    In Ordnung, also zum Beweis, dass ich den Kindergarten abgeschlossen habe,
  • 5:15 - 5:17
    hier sind ein paar Punkte auf der Uhr.
  • 5:17 - 5:20
    Dort oben ist 12 Uhr, so habe ich das gelernt.
  • 5:20 - 5:25
    Nun ich bin später Mathematikerin geworden und Mathematiker arbeiten gerne mit Koordinaten.
  • 5:25 - 5:32
    Also 12 Uhr hat die x-Koordinate 0 und die y-Koordinate 1.
  • 5:32 - 5:40
    Ich weiß, dass die 1 da sein muss, da es die Formel x^2+y^2=1 erfüllen soll.
  • 5:40 - 5:42
    x^2=0, daher y^2=1 und y=1.
  • 5:42 - 5:43
    Aber es gibt viel mehr Punkte,
  • 5:43 - 5:45
    also dort ist 18 Uhr.
  • 5:45 - 5:49
    Dort haben Sie Frühstück, ähm Lunch.
  • 5:49 - 5:53
    Das ist die 15 Uhr Marke, da ist die 21 Uhr Marke,
  • 5:53 - 5:55
    da ist, ... ,oh was ist das?
  • 5:55 - 5:59
    Das habe ich nicht im Kindergarten gelernt.
  • 5:59 - 6:03
    So es ist, ähm, halb nach oben dann schauen, wo ist die eins,
  • 6:03 - 6:06
    dann halb rüber.
  • 6:06 - 6:07
    Das schaut aus, ähm, wie die 2 Uhr Marke.
  • 6:07 - 6:10
    Hier wurden die Koordinaten umgedreht.
  • 6:10 - 6:15
    Nun x = 1/2, also sind wir irgendwo hier drüben,
  • 6:15 - 6:18
    und dann ins negative, das wäre die 5 Uhr Marke.
  • 6:18 - 6:21
    Und mehr und mehr Punkte...
  • 6:21 - 6:22
    Sollte es nicht sanft sein?
  • 6:22 - 6:26
    Ist es nicht sanft?
  • 6:26 - 6:32
    [Applaus]
  • 6:32 - 6:34
    Okay, also...
  • 6:34 - 6:36
    Hey, hier sind ein paar Punkte die ich noch nicht gesehen habe.
  • 6:36 - 6:40
    Oh, tut mir leid, ähm, ich glaube wir wollten mehr über Punkte wie diese erzählen.
  • 6:40 - 6:44
    3/5, 4/5, ich meine, hier muss man richtig komplizierte Mathematik nutzen,
  • 6:44 - 6:47
    um zu sehen, dass eine Formel (3/5)^2+(4/5)^2=1 ist.
  • 6:47 - 6:50
    Dies ist ein weiterer Punkt auf der Uhr und es ist nicht ersichtlich,
  • 6:50 - 6:51
    wie viel Uhr es ist.
  • 6:51 - 6:53
    Sie müssen wirklich intensiv auf ihre Uhr schauen um das herauszufinden.
  • 6:53 - 6:54
    Immer am Aussteigen wenn es knifflig wird.
  • 6:54 - 6:55
    Entschuldigung?
  • 6:55 - 6:57
    Nun steigst du aus, wenn es es knifflig wird.
  • 6:57 - 6:58
    Aussteigen wenn es knifflig wird?
  • 6:58 - 7:01
    [Lachen]
  • 7:01 - 7:04
    Okay, also willst du wirklich, dass ich das Quadrat, das halbe Quadrat, ...
  • 7:04 - 7:09
    Nein, nein, ich weiß einfach nicht wo der Punkt ist, aber ich weiß er ist auf der Uhr.
  • 7:09 - 7:13
    Okay, also du kannst herausfinden, wo der 3/5, 4/5 Punkt ist, im Bezug auf die Uhrzeit.
  • 7:13 - 7:20
    Sie können es auch etwas komplizierter machen in dem Sie die Uhr parametisieren.
  • 7:20 - 7:25
    Also wenn Leute Punkte auf der Uhr nehmen,
  • 7:25 - 7:28
    dann denken sie an eine voranschreitende Zeit.
  • 7:28 - 7:31
    Also es gibt 2 Uhr, 3 Uhr und das kann addiert werde, und man bekommt 5 Uhr.
  • 7:31 - 7:33
    Zwei Stunden nach 3 Uhr oder drei Stunden nach 2 Uhr ist 5 Uhr.
  • 7:33 - 7:39
    Und hier ist ein Bild, das etwa so aussieht, als ob 1:30 plus 2 Uhr so etwas wie 3:30 ergibt.
  • 7:39 - 7:42
    Also hier sind ein paar Punkte p1, p2 und p3 auf der Uhr.
  • 7:42 - 7:45
    Und Sie können p1 und p2 addieren, um p3 zu erhalten.
  • 7:45 - 7:52
    Hier kommt der schreckliche mathematische Teil, den wir gleich verwerfen werden - die Trigonometrie.
  • 7:52 - 7:59
    Wenn Sie einen Punkt auf der Uhr haben, hat er einen Winkel von Alpha.
  • 7:59 - 8:06
    Die Zeit von Alpha beginnt bei 12 Uhr, dann ist dieser Punkt x gleich Sinus von Alpha, Y gleich Kosinus Alpha.
  • 8:06 - 8:14
    Es gab es diese schrecklichen trigonometrischen Formeln für den Sinus der Summe zweier Winkel und den Kosinus von ...
  • 8:14 - 8:17
    Die Summe von zwei Winkeln und der Sinus von Alpha 1 plus Alpha 2 ist...
  • 8:17 - 8:22
    Okay, Sinus von Alpha 1, Cosinus von Alpha 2 plus Cosinus von Alpha 1, Sinus von Alpha 2.
  • 8:22 - 8:24
    Etwas Ähnliches gibt es für den Cosinus.
  • 8:24 - 8:29
    Sie können Punkte hinzufügen mithilfe der Sinus und Cosinus Funktionen.
  • 8:29 - 8:33
    Normalerweise überreden wir die Leute, sich der Crypto-Seite zuzuwenden indem wir ihnen sagen:
  • 8:33 - 8:37
    "Sie können die ganze nichtdiskrete Mathematik vergessen"
  • 8:37 - 8:39
    "Wir möge diskrete Mathematik, wir sind die diskreten Typen,
  • 8:39 - 8:42
    also wird es keine Sinus und Cosinus geben."
  • 8:42 - 8:49
    Okay, lasst uns sie loswerden. Wir wollen keinen Sinus und Cosinus haben.
  • 8:49 - 8:52
    Eigentlich würden wir gerne mit normalen Uhrzeiten arbeiten.
  • 8:52 - 9:02
    Sinus 1, Cosinus 2 und so weiter sind einfach meine x- und y-Koordinaten.
  • 9:02 - 9:06
    Alles, was ich hier gesagt habe, war, dass die x-Koordinate ein Sinus von Alpha ist.
  • 9:06 - 9:09
    Die y-Koordinate ist der Kosinus von Alpha.
  • 9:09 - 9:12
    In diesem ganzen Durcheinander mit den Trigonometrieformeln,
  • 9:12 - 9:18
    kann ich einfach jeden Sinus von Alpha durch das entsprechende x ersetzen.
  • 9:18 - 9:20
    Und jeder Cosinus von Alpha wird durch das entsprechende y ersetzt.
  • 9:20 - 9:24
    Dadurch wird dies viel schöner und kürzer.
  • 9:24 - 9:27
    Keine trigonometrische Additionsformel. Also wenn Ihnen bei der Addition auf der Uhr
  • 9:27 - 9:35
    Ihnen zwei Punkte x1 y1 und x2 y2, gibt, dann müssen Sie nur die x-Koordinate des ersten Punktes
  • 9:35 - 9:38
    und die y-Koordinate des zweiten Punktes nehmen und diese multiplizieren.
  • 9:38 - 9:43
    Nehmen Sie dann die y-Koordinate des ersten Punktes und die x-Koordinate des zweiten Punktes und multiplizieren Sie diese.
  • 9:43 - 9:44
    Addieren sie das.
  • 9:44 - 9:48
    Das gibt Sie die neue X-Koordinate. Warum?
  • 9:48 - 9:53
    Wir können einfach vergessen, woher sie stammt.
  • 9:53 - 9:56
    Dann machen wir dasselbe mit der Y-Koordinate.
  • 9:56 - 10:00
    Sie ist das Produkt aus den Y-Koordinaten minus dem Produkt der X-Koordinaten.
  • 10:00 - 10:02
    Okay.
  • 10:02 - 10:07
    Hier sind einige Beispiele für die Addition von Uhrzeiten, die wir noch nicht behandelt haben.
  • 10:07 - 10:11
    Wir haben keinen Computer hier, daher wird dies etwas mühsames Rechnen.
  • 10:11 - 10:12
    2 Uhr plus 5 Uhr.
  • 10:12 - 10:14
    Wir erinnern uns, dass dies im Test sein wird.
  • 10:14 - 10:17
    2 Uhr war diese Quadratwurzel aus 3/4 und 1/2.
  • 10:17 - 10:18
    Sie hat am Anfang darüber gesprochen.
  • 10:18 - 10:21
    Und 5 Uhr war 1/2 und minus Quadratwurzel von 3/4.
  • 10:21 - 10:23
    Wenn Sie das in die Formel einsetzen...
  • 10:23 - 10:25
    Okay, ich werde es mal versuchen.
  • 10:25 - 10:26
    x1 ist Quadratwurzel von 3/4.
  • 10:26 - 10:28
    y1 ist 1/2.
  • 10:28 - 10:33
    x2 ist 1/2 und y2 ist minus Quadratwurzel von 3/4.
  • 10:33 - 10:38
    Wenn Sie x1 mit y2 multiplizieren ist, dann ist das die Quadratwurzel von 3/4 multipliziert
  • 10:38 - 10:41
    mit der minus Quadratwurzel von 3/4, welche minus 3/4 ist.
  • 10:41 - 10:46
    Dann müsste y1 mal x2, 1/2 mal 1/2 sein, was 1/4 ist.
  • 10:46 - 10:49
    Addiert man diese, ist es ungefähr minus 1/2.
  • 10:49 - 10:53
    Führt man eine ähnliche Berechnung durch, erhält man den 2. Teil des Ergebnisses.
  • 10:53 - 10:57
    Man erkennt, dass 2 Uhr plus 5 Uhr mit diesen Formeln das ist, was Sie wollten, nämlich 7 Uhr.
  • 10:57 - 11:01
    Ähnliches können Sie mit 5 Uhr plus 9 Uhr machen.
  • 11:01 - 11:04
    Ich denke, wir werden es überspringen.
  • 11:04 - 11:07
    Versuchen wir es mit einem anderen Beispiel.
  • 11:07 - 11:09
    Sie können 3/5 und 4/5 nehmen und sie addieren.
  • 11:09 - 11:15
    Das bedeutet, dass 2 mal (3/5 mal 4/5) dann 3/5 mal 4/5 plus 3/5 und 4/5 sind.
  • 11:15 - 11:20
    Fügen Sie dies in die Formeln ein und Sie wissen nicht, wie spät es ist.
  • 11:20 - 11:24
    Sie erhalten einfach eine Antwort, 24/25 und 7/25
  • 11:24 - 11:28
    Und Sie können immer mehr Kopien, des Punktes auf den Punkt selbst hinzufügen.
  • 11:28 - 11:33
    3 mal 3/5, 4/5, das ist also der Punkt plus sich selbst plus sich selbst
  • 11:33 - 11:38
    Setzen Sie ihn einfach in die Formeln ein und Sie erhalten etwas mit mehr Ziffern.
  • 11:38 - 11:41
    Wenn Sie immer mehr Kopien hinzufügen, erhalten Sie immer mehr Stellen.
  • 11:41 - 11:44
    Der Nenner ist nun 625 und er wird immer größer.
  • 11:44 - 11:51
    Sie können auch versuchen, jeden gewünschten Punkt zu 12 Uhr hinzuzufügen, ohne überhaupt zu wissen, welcher es ist.
  • 11:51 - 11:53
    12 Uhr mit 0,1 (Koordinaten)
  • 11:53 - 11:57
    Wenn Sie diese in die Formeln einsetzen, erhalten Sie 12 Uhr plus 3 Uhr ist 3 Uhr.
  • 11:57 - 11:58
    12 Uhr plus 5 Uhr ist 5 Uhr
  • 11:58 - 12:01
    12 Uhr plus irgendein Wert ergibt als Ergebnis diesen Wert.
  • 12:01 - 12:06
    Das ist sofort ersichtlich aus der Formel zur Addition von zwei Punkten.
  • 12:06 - 12:10
    Ein letztes Beispiel dafür, wie Sie mit dieser Additionsformel arbeiten können.
  • 12:10 - 12:14
    Sie nehmen beispielsweise 10 Uhr + 2 Uhr. Das sollte 12 Uhr sein.
  • 12:14 - 12:17
    10 + 2 = 12. Das ist logisch.
  • 12:17 - 12:24
    Das Gegenteil wäre 10 + 2, wenn man 9 + 3 oder 11 + 1 oder irgendetwas nimmt,
  • 12:24 - 12:27
    was die gleiche Höhe, die gleiche Y-Koordinate hat, aber die X-Koordinate negativ ist.
  • 12:27 - 12:29
    Diese ergeben zusammen 12 Uhr.
  • 12:29 - 12:33
    Sie können einfach versuchen x1 und y1 und minus x1y1 in die Formel einzusetzen.
  • 12:33 - 12:35
    Versuchen wir das mal:
  • 12:35 - 12:38
    Angenommen, wir sagen, x2 ist minus x1 und y2 ist y1
  • 12:38 - 12:40
    und setzten es in die Formel ein.
  • 12:40 - 12:41
    Sie sehen die erste ähm...
  • 12:41 - 12:48
    Die erste Koordinate der Antwort, welche ist: x1*y2 = y1
  • 12:48 - 12:54
    Und y1= -x1*x2... ähm sorry,
  • 12:54 - 13:00
    x2 ist -x1*y1. Die ergibt im Endeffekt null.
  • 13:00 - 13:02
    Das ist, was wir für 12 Uhr erwartet haben.
  • 13:02 - 13:10
    Nächster Teil: y1y2 = y1 mal y1 minus x1*x2, das ist
  • 13:10 - 13:15
    minus x1 mal minus x1 = x1 im Quadrat,
  • 13:15 - 13:22
    und x1 im Quadrat + x1 im Quadrat ist gleich 1.
  • 13:22 - 13:25
    Wir können etwas herumspielen mit Additionen und Multiplikationen.
  • 13:25 - 13:28
    Diese Formel können wir verwenden, um alle möglichen Punkte zu addieren.
  • 13:28 - 13:29
    Okay.
  • 13:29 - 13:31
    Nun wird es noch etwas diskreter.
  • 13:31 - 13:35
    Wir können den Kreis vergessen der unendlich viele Punkte hat.
  • 13:35 - 13:38
    Sie können jede reelle Zahl nehmen und einfach Quadratwurzeln ziehen.
  • 13:38 - 13:41
    Wir machen das mit einem sehr kleinen Menge von Elementen.
  • 13:41 - 13:44
    Wir machen mit Uhrzeiten über Suchfelder.
  • 13:44 - 13:49
    Ich beschränke mich jetzt nur auf die Zahlen 0, 1, bis 6.
  • 13:49 - 13:53
    Das ist also, wofür diese F7 steht.
  • 13:53 - 13:57
    Ich will diese Zahlen addieren und multiplizieren können.
  • 13:57 - 14:03
    Wenn ich 2 und 5 multipliziere, ist das ist größer als 10.
  • 14:03 - 14:06
    Diese Zahl ist größer als die Menge, die ich dort zur Verfügung habe.
  • 14:06 - 14:10
    Lasse ich nur 6 als größte Zahl zu, gehört 10 nicht zur Menge.
  • 14:10 - 14:14
    Also werde ich das reduzieren und den Modulus 7 nehmen.
  • 14:14 - 14:17
    Wir haben einige Python-Schnipsel versprochen.
  • 14:17 - 14:22
    Wir erfahren nun, wir wir beispielsweise alle diese Elemente finden können.
  • 14:22 - 14:27
    Wir gehen alle x zwischen 0 und 7 und y zwischen 0 und 7 durch.
  • 14:27 - 14:31
    Wir überprüfen einfach, ob x mal x plus y mal y = 1 ist.
  • 14:31 - 14:35
    Ist dies der Fall, drucke ich das Doppelte xy aus.
  • 14:35 - 14:38
    Dann drücke ich die Eingabetaste und wir erhalten diese Punkte für das Bild.
  • 14:38 - 14:45
    Wir haben keine bis 6 verwendet, wir möchten die Symmetrie beibehalten.
  • 14:45 - 14:51
    Wir haben -3 bis + 3 genutzt. -3 ist hier drüber, +3 hier.
  • 14:51 - 14:55
    + 3 ist in der y-Richtung und - 3 ist in der y-Richtung
  • 14:55 - 15:02
    Das ist der Punkt 0,1, also derselbe Punkt, den wir vorher auf der Uhr hatten.
  • 15:02 - 15:04
    Also ist dies die Uhrzeit.
  • 15:04 - 15:07
    Es ist der Punkt 2,2
  • 15:07 - 15:10
    Okay.
  • 15:10 - 15:12
    Wir verwenden die Uhradditionsfunktion.
  • 15:12 - 15:19
    Wir zeigen eine Funktion, um Punkte der Uhr hinzuzufügen.
  • 15:19 - 15:25
    Es ist hilfreich, Plus und Minus bei den Uhrzeiten schreiben zu können,
  • 15:25 - 15:27
    die diese Reduzierung automatisch durchführen, Mod 7.
  • 15:27 - 15:32
    In Python können wir einen Plus- und Minus- und Hoch-4 und F7-Klasse einrichten.
  • 15:32 - 15:34
    Diese sind getrennt, von den
  • 15:34 - 15:38
    üblichen für Plus-Minus und die Multiplikationen für Ganzzahlen.
  • 15:38 - 15:39
    Um dies einzurichten gehen Sie bitte wie folgt vor:
  • 15:39 - 15:46
    Hier ist eine F7-Klasse, einen Integer x liest und ein F7-Element initiiert.
  • 15:46 - 15:53
    Hierbei handelt es sich um die in den Integer Mod 7.
  • 15:53 - 15:57
    Wenn Sie F7 von 7 nehmen, wird 7 mod 7 berechnet.
  • 15:57 - 16:01
    Der Quotient ist 1
  • 16:01 - 16:03
    Der Rest ist 0
  • 16:03 - 16:05
    Man fügt 0 in self.int ein.
  • 16:05 - 16:08
    Dieser Stir-and-Wrapper, eventuell nicht die eleganteste Möglichkeit zum Drucken von Dingen,
  • 16:08 - 16:11
    gibt aus, dass alles Mod 7 ist.
  • 16:11 - 16:15
    Wir drucken nur die Ganzzahl aus, die wir bei 7 erhalten.
  • 16:15 - 16:20
    7 Mod 7 gibt 0 und 10 mod 7,
  • 16:20 - 16:23
    war das Beispiel von Tanja eben, wo der Rest 3 ergibt.
  • 16:23 - 16:26
    Und 20 mod 7, subtrahiert man 7, und subtrahiert wieder 7, erhält man eine 6.
  • 16:26 - 16:31
    Man kann also in diese F7 jeden integer eingeben, den man möchte.
  • 16:31 - 16:32
    Dafür nehmen wir diesen Integer-Mod7.
  • 16:32 - 16:38
    Nun können wir F7 einige weitere Funktionen hinzufügen.
  • 16:38 - 16:41
    Beispielsweise können Sie einen Gleichheitstest durchführen.
  • 16:41 - 16:44
    Pythons default Gleichheit ist ziemlich dumm.
  • 16:44 - 16:47
    Das was ich eigentlich tun möchte, ist folgendes:
  • 16:47 - 16:52
    Ich möchte diese Punkte vergleichen, die den gleichen F7-Wert haben.
  • 16:52 - 16:53
    Okay.
  • 16:53 - 16:57
    Nun wurde dieser F7-Typ um eine Gleichheit erweitert.
  • 16:57 - 17:00
    Sie können sehen, dass F7 von 10 und F7 von 3 gleich sind.
  • 17:00 - 17:03
    F7 von 0 und F7 von 2 sind nicht gleich.
  • 17:03 - 17:09
    Wir haben von 0 bis 6 als Möglichkeiten für die Werte einer Variablen ausgedrückt.
  • 17:09 - 17:14
    Dann folgt die Addition, Subtraktionen und Multiplikation.
  • 17:14 - 17:18
    Schauen wir uns die Addition an, dann ist der typische Fall.
  • 17:18 - 17:20
    Sie nehmen zwei a und b.
  • 17:20 - 17:24
    Dann nehmen Sie eine Integer innerhalb einer Integerrange von 0 bis 6.
  • 17:24 - 17:26
    Addieren Sie diese auf der Seite b von 0 bis 6.
  • 17:26 - 17:28
    Sie erhalten 0 bis 12.
  • 17:28 - 17:30
    Diese geben Sie dann wieder in den F7 Konstruktor ein.
  • 17:30 - 17:33
    Sie haben jetzt wieder 0 bis 6.
  • 17:33 - 17:36
    Unten sind einige Beispiele von 2 plus 5 = 0
  • 17:36 - 17:39
    2 minus 5 ist -3.
  • 17:39 - 17:40
    Das ist 4.
  • 17:40 - 17:43
    Wenn Sie in C programmieren, achten Sie auf folgendes:
  • 17:43 - 17:46
    Der Prozentwert darf den Mod nicht ausführen, den wir mathematisch wollen.
  • 17:46 - 17:49
    Pythons Prozentwert macht das Richtige und C gibt negative Zahlen aus.
  • 17:49 - 17:52
    Prozent in Python gibt Ihnen immer 0 bis 6.
  • 17:52 - 17:54
    Oder 0 bis zu jeder Zahl, die Sie genommen haben.
  • 17:54 - 17:55
    Ähm
  • 17:55 - 18:00
    2 mal 5 war wieder das Beispiel von 10, wo Mod 7= 3 ergibt.
  • 18:00 - 18:02
    Okay.
  • 18:02 - 18:04
    Jetzt haben wir eine kleine Uhr gesehen.
  • 18:04 - 18:06
    Da konnte ich einfach alle Elemente zeichnen,
  • 18:06 - 18:09
    und wir konnten sie durchgehen und ausprobieren.
  • 18:09 - 18:15
    Alles was Dan mit dem Python-Setup gezeigt hat, da kann ich 7 durch eine größere Zahl ersetzen.
  • 18:15 - 18:18
    Sagen wir mal 1.000.003, das ist auch eine Primzahl.
  • 18:18 - 18:22
    Ich gehe hin und definiere eine Addition von Kurvenpunkten.
  • 18:22 - 18:26
    Das ist genau das, was wir vorhin auf der echten Uhr gemacht haben.
  • 18:26 - 18:30
    Nun werde ich die Elemente 1.000.003 einfügen.
  • 18:30 - 18:36
    Ich nehme also meine Punkte und mache x1y2, y1x2 und so weiter.
  • 18:36 - 18:38
    Dann bekomme ich den Punkt zurück.
  • 18:38 - 18:41
    Wir machen nun ein Beispiel dazu.
  • 18:41 - 18:46
    Einer der vielen Punkte, die ich in die x-Koordinate einfüge ist 1000.
  • 18:46 - 18:49
    Denken Sie daran, dass es aus 1000 aus 1.000.003 ist.
  • 18:49 - 18:54
    Anschließend überprüfe ich, ob es eine y-Koordinate gibt und dazu passt.
  • 18:54 - 18:57
    Ja, gibt es grob.
  • 18:57 - 19:03
    Habe ich also 1000, erhalte ich eine Million im Quadrat und 2 ergibt 4.
  • 19:03 - 19:06
    Das ist nur 1 größer als die 1.000.003.
  • 19:06 - 19:08
    Ja, das ist also ein gültiger Punkt.
  • 19:08 - 19:12
    Jetzt kann ich diesen Punkt übernehmen und addiere ihn zu sich selbst.
  • 19:12 - 19:17
    Ich setzt einfach p und p in die Addition ein, die 4007 ergibt.
  • 19:17 - 19:25
    Ich kann es immer und immer wieder zu sich selbst addieren.
  • 19:25 - 19:30
    Ich addiere immer weiter bis ich am Ende 6 Kopien habe.
  • 19:30 - 19:33
    Ich füge sie zusammen und habe nun diesen Punkt.
  • 19:33 - 19:36
    Wenn Sie das sehen, denken Sie natürlich: Warte mal.
  • 19:36 - 19:38
    Muss ich tatsächlich alle diese 5 Additionen machen?
  • 19:38 - 19:39
    Nein.
  • 19:39 - 19:42
    Wenn ich beispielsweise bei p3 aufgehört hätte.
  • 19:42 - 19:48
    Das ist dreimal der Punkt und addiere dann p3 plus p3
  • 19:48 - 19:52
    Das sind also 3 Kopien plus weitere 3 Kopien, sind auch 6 Kopien.
  • 19:52 - 19:54
    Diese beiden Dinge haben das gleich Ergebnis.
  • 19:54 - 19:59
    Möchte ich das also professioneller machen,
  • 19:59 - 20:02
    ist hier die Modifikation der Scale.
  • 20:02 - 20:03
    Okay
  • 20:03 - 20:07
    Das ist eine rekursive Funktion zur Berechnung von n mal p.
  • 20:07 - 20:10
    Sie haben einen beliebigen Punkt auf der Uhr p in einem beliebigen Skalar,
  • 20:10 - 20:18
    Jeden nicht negativen Integer n, den Sie möchten.
  • 20:18 - 20:19
    Wenn n 0 ist,
  • 20:19 - 20:21
    dann geben Sie den 12-Uhr-Punkt zurück.
  • 20:21 - 20:23
    Wenn n = 1 ist, geben Sie den Punkt p einmal zurück,
  • 20:23 - 20:24
    also p ist p.
  • 20:24 - 20:28
    Und dann, wenn n gerade ist, dann ändert der Python seine Notation im Laufe leicht.
  • 20:28 - 20:34
    n // 2 ist der richtige Weg, um eine durch 2 geteilte Integer nehmen.
  • 20:34 - 20:37
    Und den Rest wegzuwerfen.
  • 20:37 - 20:40
    So ist n // 2, gerade bei n^2.
  • 20:40 - 20:43
    Wenn n*2 ist wird rekursiv n mal p berechnet.
  • 20:43 - 20:46
    Wie zum Beispiel 3 mal p, wenn n gleich 6 ist.
  • 20:46 - 20:51
    Dann kommt bei (Q,Q) heraus, das n^2 mal p zu verdoppeln.
  • 20:51 - 20:57
    Man erhält np, wenn n ungerade ist.
  • 20:57 - 20:59
    Dann ist das n über 2 .
  • 20:59 - 21:01
    Anschließend nehmen Sie das dann mal p.
  • 21:01 - 21:05
    Verdoppeln sie das, was n minus 1 mal p ergibt.
  • 21:05 - 21:06
    Addieren Sie p dazu.
  • 21:06 - 21:10
    Das heißt, wenn n mod 2 ungleich Null ist, dann addieren Sie p zu q.
  • 21:10 - 21:13
    Schließlich erhalten Sie n mal p in allen unterschiedlichen Fällen.
  • 21:13 - 21:17
    Anschließend haben wir für das eine 6stellige Zahl n versucht.
  • 21:17 - 21:19
    Das wird hier auf der Folie nicht gezeigt.
  • 21:19 - 21:24
    Es ist geheim und es waren etwa 30 Uhrzeit-Additionen erforderlich.
  • 21:24 - 21:27
    Das waren nicht sehr viele Multiplikationen, um n mal p zu berechnen.
  • 21:27 - 21:28
    Das ging sehr schnell.
  • 21:28 - 21:30
    Es kommt sofort heraus und das ist die Antwort.
  • 21:30 - 21:34
    Es gibt die x- und y-Koordinaten von n mal p für das geheime n, das es war.
  • 21:34 - 21:39
    Nun ist es nicht mehr so offensichtlich, wie man herausfinden kann, was n ist.
  • 21:39 - 21:43
    Sieht man das n mal p, und arbeitet dann rückwärts zum n, dann weiß man, welches p ist.
  • 21:43 - 21:45
    Sie wissen was n mal p ist.
  • 21:45 - 21:47
    Sie wissen, dass n nicht zu groß ist.
  • 21:47 - 21:48
    Okay
  • 21:48 - 21:50
    Es gibt nur eine Million Möglichkeiten.
  • 21:50 - 21:51
    Das ist keine wirklich ausgefallene Berechnung.
  • 21:51 - 21:53
    Es wird allerdings einen Moment dauern, bis es erledigt ist.
  • 21:53 - 21:57
    Es ist etwas, bei dem der Computer einiges rechnen muss.
  • 21:57 - 21:59
    Sie können nun vielleicht versuchen, das schneller zu machen.
  • 21:59 - 22:01
    Allerdings könnten wir dann versuchen, die Zahlen größer zu machen.
  • 22:01 - 22:04
    Statt 1.000.003 könnten wir immer noch n mal p machen.
  • 22:04 - 22:07
    Wobei n viel größer ist und die 1.000.003 eine viel größere Primzahl ist.
  • 22:07 - 22:09
    Hier gibt es also eine kleine Herausforderung.
  • 22:09 - 22:11
    Sie können nun versuchen herauszufinden, was dieses n ist.
  • 22:11 - 22:15
    Dies ist schwieriger, als eine SMS an die Telefonnummer zu senden, die gerade nicht funktioniert.
  • 22:15 - 22:18
    Ooh! ... Gemurmel
  • 22:18 - 22:21
    Nehmen wir also an, wir machen es viel schwieriger.
  • 22:21 - 22:23
    Wir machen es sehr schwierig.
  • 22:23 - 22:24
    Wir haben das Gefühl, dass Sie es für Kryptographie verwenden möchten.
  • 22:24 - 22:28
    Jemand möchte die Uhrzeit-Kryptographie standardisieren .
  • 22:28 - 22:31
    Dann beginnen Sie mit der Standardisierung einer großen Primzahl p.
  • 22:31 - 22:34
    Große Zahl, also keine Million.
  • 22:34 - 22:37
    So groß mit mehreren Tausend Bits.
  • 22:37 - 22:39
    Sie können auch folgendes machen:
  • 22:39 - 22:40
    Sie standardisieren einen Basispunkt.
  • 22:40 - 22:41
    Diese p auf der vorherigen Folie bedeutet:
  • 22:41 - 22:44
    Wir geben Ihnen p, wir geben Ihnen n-mal p.
  • 22:44 - 22:46
    Wir geben Ihnen einfach kein n.
  • 22:46 - 22:49
    Wir nehmen an, dass Ihnen jemand ein kleines p gibt, das die Primzahl ist.
  • 22:49 - 22:54
    Dieser Basispunkt P, x- und y-Koordinaten , die auf der Uhr stehen.
  • 22:54 - 22:57
    Was machen Alice und Bob, wenn sie kommunizieren wollen?
  • 22:57 - 23:01
    Ich würde gerne etwa an den Bob schicken.
  • 23:01 - 23:02
    "Ich bin Bob".
  • 23:02 - 23:05
    Dann wählt Alice, bzw. ich aus:
  • 23:05 - 23:06
    Mein Geheimnis, a.
  • 23:06 - 23:08
    Berechne a mal diesen Basispunkt.
  • 23:08 - 23:11
    Dies ist die Berechnung, die du gerade auf der vorigen Folie gesehen hast.
  • 23:11 - 23:12
    Sie ist immer noch sichtbar.
  • 23:12 - 23:16
    Dies ist also genau wie eine logarithmische Zeit von der Größe a.
  • 23:16 - 23:19
    Anschließend sende ich das an Dan.
  • 23:19 - 23:22
    Dann denke ich, ich muss etwas berechnen.
  • 23:22 - 23:25
    Ich nehme mein eigenes großes Geheimnis b, das ich niemandem verraten werde.
  • 23:25 - 23:28
    Dann berechne ich b mal das gleiche Standard (X,Y)
  • 23:28 - 23:31
    Ich sende mein b-mal (X,Y) an Alice zurück.
  • 23:31 - 23:32
    Alles klar.
  • 23:32 - 23:35
    Jetzt habe ich also sein b mal den Basispunkt.
  • 23:35 - 23:37
    Er hat mein a mal Basispunkt.
  • 23:37 - 23:39
    Ich weiß jetzt noch, was mein a war.
  • 23:39 - 23:45
    Ich nehme nun dieses a und den neuen Punkt, den er mir gerade gesendet hat.
  • 23:45 - 23:47
    Dann setze ich diesen Punkt in die Skarlarmultiplikation ein.
  • 23:47 - 23:52
    Ich mache die gleichen Schritte, addiere den Punkt zu sich selbst.
  • 23:52 - 23:55
    Und den Punkt zu dem Punkt, den er mir geschickt hat.
  • 23:55 - 23:59
    Dies sind also die gleichen Schritte hier, außer dass dieses p jetzt der Punkt ist, den er mir gesendet hat.
  • 23:59 - 24:01
    Es ist nicht mehr der Basispunkt.
  • 24:01 - 24:04
    Auf diese Art und Weise berechne ich a mal b mal p.
  • 24:04 - 24:06
    Okay.
  • 24:06 - 24:09
    Nun bekomme ich ihr a mal (X,Y).
  • 24:09 - 24:12
    Ich nehme mein geheimes b und multipliziere es mit dem a mal (X,Y).
  • 24:12 - 24:16
    Nun bekomme ich mein b mal a mal den Punkt (X,Y).
  • 24:16 - 24:20
    Ich habe das gleiche Ergebnis erhalten.
  • 24:20 - 24:23
    Nun hat sie a* b mal (X,Y) berechnet.
  • 24:23 - 24:25
    Ich habe b*a mal (X,Y) berechnet.
  • 24:25 - 24:26
    Das ist dasselbe.
  • 24:26 - 24:29
    Sie sind beide a mal b Vielfache von (X,Y).
  • 24:29 - 24:31
    Wir addieren a mal b Kopien von (X,Y).
  • 24:31 - 24:34
    Nun verwenden wir das geteilte Geheimnis zum Verschlüsseln von Daten.
  • 24:34 - 24:35
    In Ordnung.
  • 24:35 - 24:36
    Wir haben auch ein Bild davon.
  • 24:36 - 24:38
    Auch wenn wir nichts anderes machen.
  • 24:38 - 24:40
    Und Bob, hier sehen Sie, wie die Nachricht jetzt verbreitet wird.
  • 24:40 - 24:44
    Sollten Sie der Lauscher sein, wollen Sie herausfinden, was wir haben.
  • 24:44 - 24:47
    Du kannst nicht sehen, was ich hier mache.
  • 24:47 - 24:48
    Du kannst nicht sehen, was Dan hier macht.
  • 24:48 - 24:51
    Du kannst nur sehen, was hierher gesendet wird.
  • 24:51 - 24:54
    Du weißt, was das kleine p ist und was der Basispunkt ist.
  • 24:54 - 24:58
    Zumindest ist das ist das, was wir uns wünschen.
  • 24:58 - 25:00
    Nun gibt es aber einige Vorbehalte:
  • 25:00 - 25:04
    Verwenden Sie nicht einfach irgendein Primzahl-p.
  • 25:04 - 25:06
    Viele Auswahlmöglichkeiten von p sind unsicher.
  • 25:06 - 25:08
    Warnung 2!
  • 25:08 - 25:11
    Dies ist immer noch die Uhr.
  • 25:11 - 25:13
    Und wir haben am Anfang gesagt, dass Uhren keine elliptischen Kurven sind.
  • 25:13 - 25:15
    Nur elliptische Kurven sind gut.
  • 25:15 - 25:17
    Demnach sind die Uhren eigentlich eigentlich fast das
  • 25:17 - 25:19
    Gleiche wie "RSA" oder "Finde das Feld".
  • 25:19 - 25:28
    Wenn Sie etwas finden möchten, das RSA 3072 Bits hat, dann muss Ihre Uhr die Primzahl haben.
  • 25:28 - 25:33
    Die Uhr muss 1536 haben, also halb so viele Bits wie RSA Zahlen.
  • 25:33 - 25:35
    Das ist nicht das, was Sie tatsächlich möchten.
  • 25:35 - 25:40
    Okay.
  • 25:40 - 25:42
    Dritte Warnung: Timing-Angriffe
  • 25:42 - 25:48
    Eben haben viele von Ihnen über Bleichenbacher-Angriffe gegen SSL gesprochen.
  • 25:48 - 25:54
    Viele der Informationen von einem angegriffenen Server oder Client stammen vom Timing.
  • 25:54 - 26:00
    Der Angreifer sieht sich nicht nur das Abhören der öffentlichen Schlüssel a mal x y und b mal x y an.
  • 26:00 - 26:04
    Er sieht auch, wie lange Sie für Berechnungen gebraucht haben.
  • 26:04 - 26:07
    Der Angreifer kann sogar oft sehen,
  • 26:07 - 26:11
    wie lange Sie für jeden einzelnen Vorgang gebraucht haben.
  • 26:11 - 26:14
    Die funktioniert, weil es elektromagnetische Emissionen oder Funkemissionen
  • 26:14 - 26:18
    oder Cache-Effekte auf virtuellen Maschinen gibt.
  • 26:18 - 26:22
    Diese wirken sich auf andere virtuelle Maschinen aus, die unter demselben Hypervisor
  • 26:22 - 26:23
    auf derselben physischen Hardware ausgeführt werden.
  • 26:23 - 26:28
    Sie können dann als Angreifer auf Informationen zugreifen,
  • 26:28 - 26:30
    wie lange Alice und Bob brauchen.
  • 26:30 - 26:33
    Sie sehen diese Berechnung nicht wirklich,
  • 26:33 - 26:35
    aber Sie sehen die physikalischen Auswirkungen dieser Berechnung.
  • 26:35 - 26:38
    Stellen Sie sich einfach vor, Eves Ohr ist genau hier.
  • 26:38 - 26:43
    Sie kann hören und sie kann spüren, was die Berechnungen bewirken.
  • 26:43 - 26:46
    Tatsächliche können Sie das akustische Summen von Ihrer CPU hören,
  • 26:46 - 26:48
    sofern Sie ein ausreichend gutes Mikrofon daneben platzieren.
  • 26:48 - 26:50
    Dies hängt auch von den Berechnungen ab, die es ausführt.
  • 26:50 - 26:52
    Es gibt hier einige echte Beispiele für Timing-Angriffe.
  • 26:52 - 26:56
    2 von den 3 ausgewählten Beispielen sind ECC Beispiele.
  • 26:56 - 26:59
    Ein Beispiel davon ist der Lucky-13-Angriff.
  • 26:59 - 27:02
    Das war nicht gegen ECC. Das ist eine andere Art von Timing-Angriff.
  • 27:02 - 27:05
    Wir wollen Ihnen die Vorstellung vermitteln, dass Timing-Angriffe wirklich wichtig sind.
  • 27:05 - 27:08
    Dies ist ein Großteil dessen, was bei echten Kryptographie schief läuft.
  • 27:08 - 27:10
    Abgesehen von deren Unbrauchbarkeit und anderen kleinen Problemen.
  • 27:10 - 27:11
    Ähm.
  • 27:11 - 27:18
    Die Lösung für dieses spezielle Problem und das Timing zu sehen ist folgendes:
  • 27:18 - 27:22
    Die Berechnungen müssen immer in konstanter Zeit durchgeführt werden.
  • 27:22 - 27:24
    Abhängig von Ihrem Skalar,
  • 27:24 - 27:27
    dürfen Sie nicht unterschiedlich viel Zeit aufwenden.
  • 27:27 - 27:34
    Wenn Sie einfach immer dieser Regel folgen, haben Sie bei jedem Geheimnis bei geheimes Timing mehr.
  • 27:34 - 27:36
    Der Angreifer erhält nichts.
  • 27:36 - 27:37
    Ihr gesamtes Timing ist öffentlich.
  • 27:37 - 27:40
    Selbstverständlich ist es etwas mühsam, so Berechnungen durchzuführen.
  • 27:40 - 27:43
    Auf diese Weise können Sie es immer tun, aber es verlangsamt die Dinge sehr.
  • 27:43 - 27:46
    Ich denke, das ist leichter gesagt als getan.
  • 27:46 - 27:50
    Lasst uns zurück zu Warnung Nr. 2 gehen.
  • 27:50 - 27:54
    Wir nehmen an, dass konstante Zeit für Berechnungen sich um Warnung Nr. 3 kümmert.
  • 27:54 - 27:55
    Wir gehen zurück zu Warnung Nr. 2.
  • 27:55 - 27:57
    Uhren sind nicht elliptisch.
  • 27:57 - 28:01
    Lasst uns diesen Kreis, diese Uhr, in eine elliptische Kurve verwandeln.
  • 28:01 - 28:06
    Wir nehmen also den Kreis und drücken ihn nach innen.
  • 28:06 - 28:09
    Mathematisch führen wir nun einen zusätzlichen Term ein,
  • 28:09 - 28:12
    statt dass x zum Quadrat plus y zum Quadrat = 1 ist.
  • 28:12 - 28:18
    Sagen wir, dass x zum Quadrat plus y zum Quadrat = 1- 30 x^2 y^2 ist.
  • 28:18 - 28:26
    Also ist dieser zusätzliche Term hier die Differenz zwischen einem Kreis und einer Edwards-Kurve.
  • 28:26 - 28:28
    Oder eine elliptische Kurve.
  • 28:28 - 28:31
    Diese bestimmte Kurve wird also eine Edwards-Kurve genannt.
  • 28:31 - 28:33
    Aber es ist ein Beispiel für elliptische Kurven.
  • 28:33 - 28:37
    Ich möchte nun Punkte hinzufügen.
  • 28:37 - 28:39
    Wir erinnern uns daran, wie es auf dem Kreis aussah.
  • 28:39 - 28:43
    Auf dem Kreis hatte ich den neutralen Betrag oben.
  • 28:43 - 28:45
    Ich behalte das bei.
  • 28:45 - 28:48
    Sodass das Hinzufügen von irgendetwas zur 12-Uhr-Position nicht an dem Wert ändert .
  • 28:48 - 28:50
    Der Wert ist hier immer noch derselbe.
  • 28:50 - 28:56
    Ich habe hier nur p1, p2 und p3 durch diese Formeln hinzugefügt.
  • 28:56 - 29:01
    Nun funktionieren diese normalerweise nicht auf der elliptischen Kurve.
  • 29:01 - 29:06
    Der Grund ist, da es dieses - 30 x^2 * y^2 gibt.
  • 29:06 - 29:09
    Daher müssen wir auch hier unten eine kleine Anpassung vornehmen.
  • 29:09 - 29:11
    Daher gibt es nun einen Nenner.
  • 29:11 - 29:18
    Nehmen Sie d = 0 an, dann ändert sich die Formel in den Kreis
  • 29:18 - 29:23
    Auch in die Additionsformeln ändern den Kreis, denn diese 30 hier ist eine Null.
  • 29:23 - 29:25
    Sie wird also einfach durch 1 geteilt.
  • 29:25 - 29:29
    Der Kreis kommt als Sonderfall für diese elliptische Kurve heraus.
  • 29:29 - 29:33
    Nun nehmen wir minus 30 und haben eine schöne elliptische Kurve.
  • 29:33 - 29:38
    Die Additionsformeln sind nicht viel schlimmer. Sie sind nur ein kleiner zusätzlicher Term.
  • 29:38 - 29:41
    Okay
  • 29:41 - 29:47
    Sie können, wenn Sie eine Primzahl p haben, 7.000.003,
  • 29:47 - 29:48
    irgendetwas viel größeres nehmen.
  • 29:48 - 29:54
    Sie können jedes nichtquadratische d nehmen, wie minus 30,
  • 29:54 - 29:58
    jedes d, das kein Quadrat von irgendetwas Modulo p.
  • 29:58 - 30:00
    Dies ist etwas, das Sie schnell überprüfen können.
  • 30:00 - 30:03
    Dann können Sie folgendes aufschreiben:
  • 30:03 - 30:05
    Die Kurve mit x^2y^2 = 1 plus d.
  • 30:05 - 30:09
    Das ist eine elliptische Kurve.
  • 30:09 - 30:13
    Und es ist nur das zusätzliche d als zusätzliche Komplikation.
  • 30:13 - 30:15
    Wenn Sie clock cryptography verstanden haben,
  • 30:15 - 30:18
    dann ist diese zusätzliche kleine Komplikation alles,
  • 30:18 - 30:21
    was Sie für die Elliptische-Kurven-Kryptographie benötigen.
  • 30:21 - 30:25
    Es gib die Additionsformel, die gerade aus den mathematischen Formeln
  • 30:25 - 30:27
    aus vorangegangenen Folien übersetzt wurde.
  • 30:27 - 30:28
    Sie sieht fast genauso aus, wie zuvor.
  • 30:28 - 30:33
    Außer, dass bei x3 und y3 das d an der Stelle des Nenner haben.
  • 30:33 - 30:35
    Nun könnten Sie sich über dieses Aussage beklagen.
  • 30:35 - 30:38
    Warten Sie eine Minute, bevor Sie dividieren.
  • 30:38 - 30:40
    Sind Sie überhaupt in der Lage zu dividieren?
  • 30:40 - 30:42
    Was passiert, wenn Sie durch Null dividieren?
  • 30:42 - 30:44
    Vielleicht funktionieren diese Formeln nicht immer.
  • 30:44 - 30:47
    Das ist ein wichtiger Punkt, auf den Sie achten müssen.
  • 30:47 - 30:51
    Achten Sie daraus, dass Sie, wenn Sie durch etwas dividieren, nicht durch Null dividieren dürfen.
  • 30:51 - 31:03
    Es stellt sich aber heraus, dass die Nenner dort 1+d x1 x2 y1 y2 und 1- d x1 x2 y1 y2
  • 31:03 - 31:04
    niemals gleich 0 sind.
  • 31:04 - 31:07
    Diese Formeln sind vollständig.
  • 31:07 - 31:08
    Sie funktionieren immer.
  • 31:08 - 31:11
    Ich denke, dass Sie annehmen, dass Formeln immer funktionieren sollten.
  • 31:11 - 31:12
    Es ist ganz ärgerlich, wenn es Ausnahmefälle gibt.
  • 31:12 - 31:18
    Aber in der Kryptographie mit elliptischen Kurven gibt es so viele Ausnahmefälle.
  • 31:18 - 31:20
    Die Menschen machen sich oft Sorgen.
  • 31:20 - 31:24
    Einer der Gründe, warum wir diese diese Art von elliptischer Kurve mögen,
  • 31:24 - 31:26
    ist, dass es keine Ausnahmefälle gibt.
  • 31:26 - 31:28
    Wir bezeichnen das Additionsgesetz als vollständig.
  • 31:28 - 31:35
    Falls Sie sich ansehen, wie der mathematische Teil des Beweises funktioniert, ist folgendes wichtig:
  • 31:35 - 31:38
    d war kein Quadrat. Aber auch das ist etwas, das Sie leicht überprüfen können.
  • 31:38 - 31:41
    Und haben Sie sich erst einmal für ein d entschieden, das nicht quadratisch ist
  • 31:41 - 31:44
    und das jeder verwenden kann, wird es in den Formeln nie Ausnahmen geben.
  • 31:44 - 31:52
    Wenn Ihr d - äh - quadratisch ist, dann können Sie sich die gleichen Formeln aufschreiben.
  • 31:52 - 31:56
    Meistens funktionieren sie, aber es gibt Ausnahmefälle.
  • 31:56 - 31:59
    Und wir werden noch viel mehr über Ausnahmefälle erfahren.
  • 31:59 - 32:03
    Und das Ärgerliche daran ist nicht nur, dass sie schwer zu programmieren sind.
  • 32:03 - 32:06
    Sondern, wenn man irgendwelche Fehler macht, wird es schwierig sein,
  • 32:06 - 32:08
    diese Fehler zu finden und auf diese Fehler zu testen.
  • 32:08 - 32:10
    Und wenn ein Angreifer mehr darüber nachdenkt
  • 32:10 - 32:15
    und ihnen einige Punkte findet, die diese Fehler ausnutzen, bricht das oft echtes ECC.
  • 32:15 - 32:19
    Es ist also besser, eine Kurve zu nehmen, wo das d kein Quadrat ist.
  • 32:19 - 32:21
    Dann müssen Sie sich überhaupt keine Sorgen mehr darüber machen.
  • 32:21 - 32:21
    Okay.
  • 32:21 - 32:23
    Kurz dazwischen... (schwer verständlich)
  • 32:23 - 32:26
    Mit über einem finalen Feld (?) jedes zweite d ist kein quadratisches.
  • 32:26 - 32:27
    Daher ist dies keine große Einschränkung.
  • 32:27 - 32:29
    Und entfernt nur die Hälfte der Möglichkeiten.
  • 32:29 - 32:33
    Weiterhin sind Divisionen wirklich langsam.
  • 32:33 - 32:38
    Wenn Sie die implementieren, die Sie vorher im Python-Skript gesehen haben,
  • 32:38 - 32:40
    haben wir noch nicht mal Divisionen eingefügt.
  • 32:40 - 32:43
    Wir haben Sie online, aber es ist so, dass es eine Weile dauert.
  • 32:43 - 32:44
    Es ist unangenehm.
  • 32:44 - 32:47
    Es dauert sogar noch länger, wenn Sie sich Sorgen über ständige Zeitbeschränkungen machen.
  • 32:47 - 32:49
    Also fangen wir an Divisionen loszuwerden.
  • 32:49 - 32:52
    Das ist so wie "Doktor, Doktor, mein Knie schmerzt" und er sagt dann: "Verwenden Sie es nicht".
  • 32:52 - 32:57
    Aber mathematisch, hier können wir die Verwendung von Divisionen vermeiden.
  • 32:57 - 33:02
    Wenn Sie sich daran erinnern, wie Sie mit Brüchen a/b + c/d gearbeitet haben,
  • 33:02 - 33:04
    dann wissen sie, dass wir sie als Brüche behalten.
  • 33:04 - 33:06
    Bei einem Bruch multiplizieren Sie einfach die Nenner und
  • 33:06 - 33:07
    kreuzmuliplizieren die Zähler und dann können sie addieren.
  • 33:07 - 33:10
    Daher machen wir mit unseren Punkten das Gleiche.
  • 33:10 - 33:15
    Wir führen eine zusätzliche Koordinate ein, die Z-Koordinate.
  • 33:15 - 33:17
    Sie ist nur der Nenner.
  • 33:17 - 33:22
    Anstatt Punkte als (X,Y) zu speichern, speichern wir jetzt (X,Y,Z).
  • 33:22 - 33:30
    Hierbei bedeutet X und Y, dass das alte x und y, x/z und y/z ist.
  • 33:30 - 33:32
    Sie können aber auch etwas abenteuerlustiger sein.
  • 33:32 - 33:35
    Und erzielen dann eine bessere Geschwindigkeit,
  • 33:35 - 33:38
    wenn Sie eine zusätzliche Koordinate namens t einführen.
  • 33:38 - 33:39
    T = XY / Z
  • 33:39 - 33:42
    Sind Sie daran interessiert, wie sie das effizient tun
  • 33:42 - 33:44
    und tatsächlich computerverifizierte Formeln erhalten?
  • 33:44 - 33:47
    Dann besuchen Sie bitte die "Explicit Formulas Database" unter dem dortigen Link,
  • 33:47 - 33:49
    um zu sehen wie man Additionen durchführt.
  • 33:49 - 33:51
    Okay.
  • 33:51 - 33:56
    Wir kommen nun zu der Darstellung von Crypto zurück.
  • 33:56 - 33:59
    Wir ersetzen die Uhr durch eine elliptische Kurve.
  • 33:59 - 34:02
    Das macht die Formeln etwas komplizierter.
  • 34:02 - 34:04
    Außerdem muss noch eine zusätzliche Auswahl getroffen werden.
  • 34:04 - 34:07
    Nicht nur die Primzahl p ist standardisiert, sodass jeder sie verwenden kann.
  • 34:07 - 34:10
    Standardisieren Sie dieses d, das kein Quadrat ist,
  • 34:10 - 34:12
    sodass jeder sie verwenden kann.
  • 34:12 - 34:14
    Es muss eine sichere Wahl sein.
  • 34:14 - 34:16
    Denken Sie an die Warnung Nr. 1
  • 34:16 - 34:17
    Es gibt viele unsichere Entscheidungen.
  • 34:17 - 34:19
    Es gibt viele mögliche Standardkriterien.
  • 34:19 - 34:21
    Diese müssen überprüft werden, um sicherzustellen,
  • 34:21 - 34:23
    dass es sich um sichere Entscheidungen für Kurven handelt.
  • 34:23 - 34:25
    Am Ende des Vortrags werden mehr über Standards sagen.
  • 34:25 - 34:35
    Alice hat dann wie vorher ihren geheimen Schlüssel und multipliziert diesen mit x, y und
  • 34:35 - 34:36
    Oh
  • 34:36 - 34:37
    Ich überspringe, was auf dieser Folie steht.
  • 34:37 - 34:42
    Auf dieser Folie steht Alice auch Bobs öffentlicher Schlüssel b(x,y) besitzt.
  • 34:42 - 34:45
    Das hört sich alles so an, wie bei der Uhr.
  • 34:45 - 34:48
    Alice nimmt jetzt das b(x,y) und
  • 34:48 - 34:51
    multipliziert es mit a.
  • 34:51 - 34:53
    Das ergibt a(b(x,y)).
  • 34:53 - 34:56
    Sie merkt sich dann,
  • 34:56 - 34:59
    dass a(b(x,y)) das Geheimnis zum Verschlüsseln und Authentifizieren von Daten ist.
  • 34:59 - 35:03
    Da wir jetzt elliptische Kurven haben,
  • 35:03 - 35:07
    müssen wir uns keine Sorgen mehr darüber machen, dass eine Indexrechnung alles kaputt macht.
  • 35:07 - 35:08
    Wir brauchen keine Tausenden von Bits.
  • 35:08 - 35:12
    Hier sind nun einige tatsächliche reale Größen für elliptische Kurven Kryptographie.
  • 35:12 - 35:15
    Inklusive ist die gesamte und secret key encryption
  • 35:15 - 35:16
    und Authentifizierung des öffentlichen Schlüssels.
  • 35:16 - 35:20
    Sie können eine Primzahl haben, die nur 256 Bit groß ist.
  • 35:20 - 35:27
    Wir werden später sagen, dass Sie x und y zusammen nur auf 256 Bit reduzieren können.
  • 35:27 - 35:33
    Das reduziert dann den öffentlichen Schlüssel von Alice a(x,y) um ein Vielfaches.
  • 35:33 - 35:35
    a(x,y) wird auf nur 32 Bytes reduziert.
  • 35:35 - 35:37
    Diese wird Alice an Bob senden.
  • 35:37 - 35:41
    Dann gibt es noch ein paar zusätzliche Dinge, wie eine Nonce, eine Zufallszahl.
  • 35:41 - 35:42
    Damit Sie nicht jedes Mal, wenn eine Nachricht senden,
  • 35:42 - 35:45
    diese auf die gleiche Weise verschlüsseln müssen.
  • 35:45 - 35:48
    Sonst könnte jemand sehen, dass sich die Verschlüsselung wiederholt.
  • 35:48 - 35:49
    Es gibt es auch einen Authentificator.
  • 35:49 - 35:53
    Bob kann damit überprüfen, ob das Paket korrekt ist.
  • 35:53 - 35:56
    Dann erhält Bob sein Paket.
  • 35:56 - 35:59
    Er sagt: "oh ja, es ist ein Paket von Alice."
  • 35:59 - 36:02
    Es gibt Alices öffentlichen Schlüssel, wenn Bob den geteilten Schlüssel noch nicht kennt,
  • 36:02 - 36:04
    dann nimmt Bob sein Geheimnis,
  • 36:04 - 36:08
    multipliziert es mit dem öffentlichen Schlüssel und erhalt dasselbe b(a(x,y).
  • 36:08 - 36:10
    Dann führt er die Krytographie mit geheimem Schlüssel durch.
  • 36:10 - 36:12
    Er verifiziert das eingehende Paket.
  • 36:12 - 36:15
    Er verifiziert den Authentifikator unter Verwendung der Nonce
  • 36:15 - 36:16
    und des öffentlichen Schlüssels von Alice.
  • 36:16 - 36:20
    Er hat zu diesem Zeitpunkt bestätigt, dass das von Alice ist.
  • 36:20 - 36:22
    Hat Bob noch nie von Alices öffentlichem Schlüssel gehört,
  • 36:22 - 36:24
    weiß er nicht, wer Alice ist.
  • 36:24 - 36:27
    Aber er erhält Kontinuität zwischen den unterschiedlichen Nutzungen.
  • 36:27 - 36:30
    Und fügen Sie dann Zertifikate oder andere öffentliche Schlüsselinfrastruktur hinzu,
  • 36:30 - 36:32
    wissen Sie tatsächlich, mit wem sie kommunizieren.
  • 36:32 - 36:35
    Alles worüber wir hier reden,
  • 36:35 - 36:37
    die ganze public key und secret key Sache, ist so schnell,
  • 36:37 - 36:39
    dass wir uns es leisten können,
  • 36:39 - 36:41
    das für jedes einzelne Paket zu machen, das das Internet durchquert.
  • 36:41 - 36:42
    Gut.
  • 36:42 - 36:46
    Wir haben Ihnen im Moment noch nicht gesagt, was Sie verwenden sollen.
  • 36:46 - 36:48
    Hier ist nun ein sicheres Beispiel.
  • 36:48 - 36:50
    Du bist leise!
  • 36:50 - 36:54
    Dies ist also ein sicheres Beispiel, das dann nicht beworben werden sollte.
  • 36:54 - 36:55
    Es ist sein eigenes.
  • 36:55 - 36:56
    Ähm
  • 36:56 - 36:57
    Ich kann aber sagen, dass es ein gutes Beispiel ist.
  • 36:57 - 37:00
    Sollten Sie also eine große Primzahl als Ihre Primzahl nehmen, hat sie 255 Bits.
  • 37:00 - 37:02
    Es ist eine sehr schöne Primzahl.
  • 37:02 - 37:05
    Das Berechnungsmodul für diese Primzahl ist schnell.
  • 37:05 - 37:07
    Sie liegt sehr nahe an einer Zweierpotenz.
  • 37:07 - 37:09
    Sie führen also diesen Mod aus.
  • 37:09 - 37:13
    Diese Prozentoperation kann diese Zahl sehr schnell reduzieren.
  • 37:13 - 37:16
    Dann sieht d ziemlich klein aus.
  • 37:16 - 37:20
    Hier haben Sie auch eine Edwards -Kurve.
  • 37:20 - 37:22
    Es gibt eine andere Edwards-Kurve.
  • 37:22 - 37:23
    Diese nutzt das gleiche d
  • 37:23 - 37:25
    und fügt dort nur ein Minus ein.
  • 37:25 - 37:29
    Außerdem fügt man ein Minus vor dem x^2 ein.
  • 37:29 - 37:32
    Dies ist eine andere Kurve, aber fast die gleiche.
  • 37:32 - 37:38
    Für jedes (x,y) von zuvor, haben wir nun
  • 37:38 - 37:42
    die Quadratwurzel von Minus 1 *xy und das gleich y wie zuvor.
  • 37:42 - 37:45
    Somit ist es nur mit einer kleinen Änderung die erste Kurve.
  • 37:45 - 37:49
    Außerdem haben wir viele Wege wie man elliptic curves schreibt.
  • 37:49 - 37:53
    Hier ist eine ganze Liste mit verschiedenen Arten von elliptic curves.
  • 37:53 - 37:56
    Also das erste was wir Ihnen bereits gezeigt haben,
  • 37:56 - 38:00
    die Uhr, in der Sie in die Ecken reindrücken, ist eine Edwards-Kurve.
  • 38:00 - 38:05
    Ich hätte hier gerne einen zusätzlichen Term wie dieses minus 1.
  • 38:05 - 38:08
    Ich behalte mir hier im Allgemeinen einen Koeffizienten a vor.
  • 38:08 - 38:09
    Den kann ich dann etwas eingeben.
  • 38:09 - 38:10
    Äh
  • 38:10 - 38:11
    Zum Beispiel minus 1.
  • 38:11 - 38:13
    Das nennt man eine verdrehte Edwards-Kurve.
  • 38:13 - 38:17
    Es gibt noch ein paar andere Dinge, die man in Lehrbüchern findet.
  • 38:17 - 38:18
    Diese nennt man Weierstrass-Kurven.
  • 38:18 - 38:21
    Es gibt auch noch die Montgomery-Kurven.
  • 38:21 - 38:25
    Diesen kann man sich als Sonderfall von Weierstrass-Kurven vorstellen.
  • 38:25 - 38:28
    Sie haben eine ähnliche Form wie y^2 = x^3
  • 38:28 - 38:30
    Hier gibt es einige unterschiedliche Terme.
  • 38:30 - 38:35
    Wenn Sie eine Kurve haben, können Sie von einem zum anderen und zurück wechseln.
  • 38:35 - 38:39
    Beispielsweise von einer Montgomery-Kurve zu einer Edward Kurve.
  • 38:39 - 38:41
    Okay.
  • 38:41 - 38:48
    Aus historischen Gründen findet man Standards für ECC.
  • 38:48 - 38:48
    Okay.
  • 38:48 - 38:50
    Haltet Euch zurück. Das wird schrecklich.
  • 38:50 - 38:52
    Das sind Weierstrass-Kurven.
  • 38:52 - 38:54
    Hier ist das Additionsgesetz.
  • 38:54 - 38:56
    Es zeigt, wie man 2 Punkte auf einer Weierstrasskurve addiert.
  • 38:56 - 39:02
    Kurze Pause. Zwischenrufe!
  • 39:02 - 39:04
    Oh, das ist gar nicht so schlecht.
  • 39:04 - 39:05
    Es gibt 6 verschiedene Fälle.
  • 39:05 - 39:07
    Wir gehen sie mal durch.
  • 39:07 - 39:08
    Nein, nein, lasst uns sie nicht durchgehen.
  • 39:08 - 39:11
    Das ist - äh - wenn Du nur einen Teil davon nimmst.
  • 39:11 - 39:13
    Dann könnte es so aussehen, als würde es die meiste Zeit funktionieren.
  • 39:13 - 39:16
    Meistens funktionieren die ersten Formeln.
  • 39:16 - 39:19
    Solange, bis man etwas Verrücktes wie p + p macht und es dann nicht funktioniert.
  • 39:19 - 39:21
    Dann gibt es immer mehr Ausnahmefälle.
  • 39:21 - 39:23
    In einigen dieser Fälle merkt man es zunächst gar nicht.
  • 39:23 - 39:26
    Un dann versucht man einen Code dafür zu schreiben.
  • 39:26 - 39:27
    Es geht einfach immer weiter.
  • 39:27 - 39:30
    Dann versucht man es zu testen und ist sich nicht sicher, ob man alle Tests richtig gemacht hat.
  • 39:30 - 39:32
    Aber okay.
  • 39:32 - 39:35
    Das ist das, was man in ECC-Standards findet.
  • 39:35 - 39:37
    Alles klar.
  • 39:37 - 39:42
    Schöner als Weierstrass- und Montgomery-Kurven ist eine unserer Lieblingskurven.
  • 39:42 - 39:44
    Hier sehen Sie die gesamte Arithmetik.
  • 39:44 - 39:50
    Die Ausnahme ist, dass ich Ihnen nicht gezeigt habe, wie ich den Austausch mit konstanter Zeit durchführen werde.
  • 39:50 - 39:53
    Hier gibt es ein bedingtes Bit, das x2 mit x3 vertauscht.
  • 39:53 - 39:56
    Wir können das in konstanter Zeit erledigen.
  • 39:56 - 39:59
    Ersetzen Sie diese Anweisung durch etwas, das folgendes besagt:
  • 39:59 - 40:01
    "Es bleibt oder es wird ausgetauscht."
  • 40:01 - 40:04
    Das ist eine ganze Addition auf Montgomery.
  • 40:04 - 40:07
    Für jedes Bit machen Sie diese paar Schritte.
  • 40:07 - 40:10
    Und Sie gehen die 255 Bits durch, die dort angegeben sind.
  • 40:10 - 40:14
    Dies ist ein weiterer schöner Fall von Arithmetik.
  • 40:14 - 40:18
    Beachten Sie bitte, dass wir hier nur eine x-Koordinate.
  • 40:18 - 40:21
    Für die Edwards-Kurve hätten wir x und y.
  • 40:21 - 40:23
    Es gibt also einige Unterschiede in dem, was wir damit machen.
  • 40:23 - 40:27
    Wir teilten Ihnen mit, dass wir über Standards sprechen werden.
  • 40:27 - 40:31
    Woher beziehen Sie Ihre Standards und wie können Sie diese verteidigen?
  • 40:31 - 40:34
    Sie treten gegen jemanden an, der mit einem Mathematiker antritt.
  • 40:34 - 40:37
    Mathematiker sind gruselige Menschen.
  • 40:37 - 40:39
    Sie kennen alle Arten von Angriffen.
  • 40:39 - 40:41
    Falls Sie diese Angriffe sehen wollen, haben wir am Ende ein paar URLs.
  • 40:41 - 40:43
    Aber im Grund kennen wir diese Angriffe.
  • 40:43 - 40:52
    Vereinbaren Sie bestimmte Eigenschaften, die Ihre Kurve haben soll.
  • 40:52 - 40:54
    Und was diese Standards Ihnen garantieren.
  • 40:54 - 41:00
    Wenn Sie einen dieser Standards auswählen, ist die Kurve ist für den folgenden Angriff sicher.
  • 41:00 - 41:02
    Jemand sieht das Ergebnis Ihrer Berechnung.
  • 41:02 - 41:04
    Er kennt den Basispunkt.
  • 41:04 - 41:06
    Er kennt Ihren öffentlichen Schlüssel.
  • 41:06 - 41:09
    Er ist aber nicht in der Lage herauszufinden, was Ihr a oder b war.
  • 41:09 - 41:12
    Man nennt dies das Problem des elliptischen diskreten Logarithmus.
  • 41:12 - 41:17
    Und wir haben ganz viele Arbeiten, um die Schwierigkeit zu untersuchen.
  • 41:17 - 41:22
    Als Mathematiker untersuchen wir, wie schwer es bei einer bestimmten Kurve ist, eine Lösung zu finden.
  • 41:22 - 41:24
    Um so die elliptische, diskrete Protokoll zu knacken.
  • 41:24 - 41:29
    Sie möchten beispielsweise, dass Ihr Punkt, wenn Sie ihn mehrmals mit sich selbst addieren,
  • 41:29 - 41:33
    über eine lange, lange, Zeit verschiedene Punkte ergibt,
  • 41:33 - 41:37
    bis Sie zum Beispiel wieder zum gleichen Punkt zurück gelangen.
  • 41:37 - 41:39
    Also z.B. nach l Phasen sind Sie wieder zurück.
  • 41:39 - 41:46
    Dieses l sollte groß sein, Ich denke z.B. 2 hoch 250 oder etwas anderes großes.
  • 41:46 - 41:50
    Und ja das sind alle Skripte also ist dies eines der Eigenschaften aber da sind viele weitere.
  • 41:50 - 41:54
    Okay, lasse wir uns annehmen, dass Sie es implementieren.
  • 41:54 - 41:58
    Sie nehmen eines der Standards und wieder mal sind sind sie alle ähnlich.
  • 41:58 - 41:59
    Klar, es gibt Unterschiede im Detail,
  • 41:59 - 42:01
    aber sie alle beschützen uns.
  • 42:01 - 42:03
    Und Sie implementieren den Standart...
  • 42:03 - 42:07
    Und Sie sagen, okay wir sind in Deutschland, wir nehmen die Brainpool Kurven,
  • 42:07 - 42:09
    da diese in deutschen Pässen verwendet werden.
  • 42:09 - 42:12
    In Ordnung, also wir nehmen Brainpool P256 t1,
  • 42:12 - 42:15
    dies gibt Ihnen eine Primzahl, die 256 Bits lang ist.
  • 42:15 - 42:21
    Außerdem eine Weierstrass-Kurve, y^2 = x^3 - 3x + etwas großes.
  • 42:21 - 42:24
    Und dann gibt es Ihnen einen Basispunkt (x,y),
  • 42:24 - 42:26
    und dann schauen Sie darauf und merken:
  • 42:26 - 42:30
    Oh, alle netten Formeln die vorher genannt wurden, ohne Ausnahmefälle,
  • 42:30 - 42:36
    wie Edwards und Montgomery, diese Formeln funktionieren nicht bei dieser Kurve.
  • 42:36 - 42:39
    Wenn Sie eine Kurve haben, die kompatibel mit den Formeln ist,
  • 42:39 - 42:41
    dann standardisieren Sie diese.
  • 42:41 - 42:44
    Dann kann jeder Punkt erfolgreich addiert werden und Sie können alle Ausnahmefälle vergessen.
  • 42:44 - 42:47
    Dafür brauchen Sie eine Kurve die mit den Formeln übereinstimmt,
  • 42:47 - 42:52
    leider funktioniert diese Kurve nicht mit Edwards und Montgomery,
  • 42:52 - 42:56
    daher müssen Sie zurück zu den chaotischen Weierstrass Formeln gehen.
  • 42:56 - 43:00
    Okay, Sie sind sehr vorsichtig und tun genau das was die Formeln aussagen.
  • 43:00 - 43:05
    Dabei nutzen Sie Testfälle für alles und haben die Weierstrass Konditionen
  • 43:05 - 43:06
    in allen sechs Fällen richtig implementiert .
  • 43:06 - 43:13
    Und Sie arbeiten in konstanter Zeit, sodass keine Informationen an Angreifer gegeben werden.
  • 43:13 - 43:17
    Dann haben sie eine Lösung die schmerzhaft langsam ist,
  • 43:17 - 43:20
    aber Sie können sich sicher über die Sicherheit sein.
  • 43:20 - 43:26
    Bis ein Angreifer kommt und sagt:
  • 43:26 - 43:27
    "Hi, lass uns uns Diffie-Hellmann hier nutzen.
  • 43:27 - 43:28
    Hier ist mein Punkt."
  • 43:28 - 43:31
    Okay, ich nehme... Ähm ich glaube ich bin Alice.
  • 43:31 - 43:40
    Ich habe ein a und nehmen den Punkt, den sie mir gesendet hat a mal.
  • 43:40 - 43:42
    Dies ist ihr öffentlicher Schlüssel.
  • 43:42 - 43:44
    Dies ist nicht das originale (x,y),
  • 43:44 - 43:46
    es ist ein anderes (x', y')
  • 43:46 - 43:47
    welches sie mir gesendet hat.
  • 43:47 - 43:49
    Und ich sende zurück mein a(x',y')
  • 43:49 - 43:53
    Und dann, wenn ich dies korrekt berechnet habe,
  • 43:53 - 44:01
    dann habe ich nun den Verschlüsselung- Authentifikations-Mechanismus genutzt.
  • 44:01 - 44:02
    Da mir jemand gesagt hat, dass ich Standard-Mechanismen nutzen soll.
  • 44:02 - 44:05
    Ich habe Daten verschlüsselt und diese durch das Netzwerk geschickt.
  • 44:05 - 44:08
    Ich bin im Netzwerk,
  • 44:08 - 44:11
    ich sehe seine AES-GMC verschlüsselte Nachricht.
  • 44:11 - 44:13
    Und nun, er weiß nicht,
  • 44:13 - 44:17
    dass es unabhängig von seinen a,
  • 44:17 - 44:20
    nicht viele verschiedenen Punkte gibt.
  • 44:20 - 44:22
    Ich habe ihm keinen Punkt auf der brainpool-Kurve genannt,
  • 44:22 - 44:25
    nein, ich habe ihm einen Punkt auf einer einfacheren Kurve gerannt.
  • 44:25 - 44:26
    Zum Beispiel hier, hat es nur fünf.
  • 44:26 - 44:28
    Die Brainpoolkurve ist viel viel größer,
  • 44:28 - 44:29
    dies hier ist eine nette Kurve.
  • 44:29 - 44:34
    Also dieser Punkt hat nur 4999 verschiedene Kopien.
  • 44:34 - 44:39
    Dies heißt, dass er nicht wirklich ausrechnet, was er denkt.
  • 44:39 - 44:40
    Ups!
  • 44:40 - 44:44
    Nun der Grund für diese Möglichkeit ist,
  • 44:44 - 44:47
    dass im ganzen Chaos der Weierstrass-Kurven, kein a6 existiert.
  • 44:47 - 44:53
    Also unabhängig davon, ob es das a6 ist als große Zahl für harte Kurven,
  • 44:53 - 44:56
    oder die 5 die ich eben für leichtere eingesetzt habe.
  • 44:56 - 44:59
    Es ist egal, der Angreifer nutzt eine der Formeln.
  • 44:59 - 45:06
    Dann gibt mir das a einen der 4999 verschiedenen Punkte,
  • 45:06 - 45:10
    woraus ich ein Modulo 4999 entwickeln kann.
  • 45:10 - 45:12
    Lassen wir uns das wiederholen!
  • 45:12 - 45:14
    Sie sendet mir einen anderen Punkt.
  • 45:14 - 45:16
    Hi Dan, hier ist ein anderer Punkt.
  • 45:16 - 45:20
    Ich nehme das neue (x',y') und berechne es a mal.
  • 45:20 - 45:24
    Dann sende ich etwas verschlüsseltes zurück mithilfe des geteilten Geheimnisses.
  • 45:24 - 45:29
    Und nun berechnet sie das gleiche.
  • 45:29 - 45:32
    Sie hat mir heimlich einen Punkt von einer kleinen Ordnung geschickt,
  • 45:32 - 45:33
    was ich nie bemerkt habe.
  • 45:33 - 45:38
    Nun hat sie mein geheimes modulo herausgefunden und nutzt verschiedene Nummern.
  • 45:38 - 45:39
    Wieder und wieder.
  • 45:39 - 45:46
    Dies geschieht etwa 20 mal und dann nutzt sie den Chinesischen Restsatz um mein ganzes Geheimnis zu knacken.
  • 45:46 - 45:49
    Auch wenn nur ein paar Schwachstellen gefunden werden,
  • 45:49 - 45:52
    ist dies genug um das ganze Sicherheitssystem ernsthaft zu beschädigen.
  • 45:52 - 45:58
    Wenn dies dann 20 mal passiert, dann habe ich ein echtes Problem.
  • 45:58 - 46:02
    Nun, was Leute dem häufig entgegnen ist, dass sie sagen:
  • 46:02 - 46:06
    Oh, ist dir die Fußnote im Standart nicht aufgefallen, welche besagt,
  • 46:06 - 46:10
    dass wenn du einen Punkt bekommst, du testen sollst, ob dieser auf der Kurve liegt?
  • 46:10 - 46:15
    Dh. schuld an der Attacke ist die Person, die die Implementierung vornimmt.
  • 46:15 - 46:17
    Dies ist der Weg, wie wir sichere Systeme erhalten,
  • 46:17 - 46:19
    wir weisen die Schuld immer dem Implementierer zu.
  • 46:19 - 46:22
    Das ist super, wenn etwas falsch mit dem System ist,
  • 46:22 - 46:24
    ist es der Fehler des Implementierers, dass das nicht überprüft wurde.
  • 46:24 - 46:27
    Applaus
  • 46:27 - 46:30
    Lassen Sie mich nicht von stir copy anfangen...
  • 46:30 - 46:34
    Sie sollten die Länge vom String... Sorry, das war falsch
  • 46:34 - 46:37
    Sie sollten aufpassen, dass dieser Punkt auf der Kurve ist,
  • 46:37 - 46:40
    Sie sollten aufpassen, dass die richtige Reihenfolge vorliegt.
  • 46:40 - 46:41
    wegen einer anderen ähnlichen Attacke.
  • 46:41 - 46:45
    Über die Art und Weise wie Patentgebühren an certicom gezahlt werden...
  • 46:45 - 46:50
    Okay, ich referiere dazu, wenn Sie einen Telefonanruf bekommen würden.
  • 46:50 - 46:56
    Wo gesagt wird, dass ein Patent zur Validieren steht...
  • 46:56 - 47:03
    Statt dem Implementierer die Schuld zuzuweisen, warum sollten wir nicht die Umstände verbessern.
  • 47:03 - 47:05
    Warum designen wir nicht Kryptographie anders?
  • 47:05 - 47:07
    Warum designen wir keine anderen Kurven,
  • 47:07 - 47:11
    sodass es nicht möglich ist bei der Implementierung zu versagen?
  • 47:11 - 47:14
    Wir wissen wir Implementierer ticken.
  • 47:14 - 47:16
    Wir sind Implementierer und wissen was wir falsch machen.
  • 47:16 - 47:21
    Und die Fehler wiederholen sich wieder und wieder.
  • 47:21 - 47:26
    Also lasst uns uns gegen diese Fehler schützen und ein robustes Design wählen.
  • 47:26 - 47:32
    Dies heisst für ECC, Sie nehmen das (x,y) was durchs Netzwerk ankommt
  • 47:32 - 47:35
    und verbieten, dass dieses (x,y) durch das Netzwerk weitergeschickt wird.
  • 47:35 - 47:37
    Sie haben nur ein x.
  • 47:37 - 47:42
    Und wenn das y^2 gleich zu etwas ist, dann könnte man, wenn man will,
  • 47:42 - 47:43
    das kommunizieren.
  • 47:43 - 47:46
    Sie können ein Bit senden, das angibt ob es plus oder minus die Quadratwurzel
  • 47:46 - 47:49
    von diesem y ist.
  • 47:49 - 47:51
    Oder man sendet einfach kein y.
  • 47:51 - 47:54
    Erinnern Sie sich an die Montgomery Formeln, diese brauchen noch nicht mal y.
  • 47:54 - 48:01
    So wenn Sie nur ein x senden, dass gibt es deutlich weniger Möglichkeiten für den Angreifer
  • 48:01 - 48:07
    um Punkte auszusuchen und Sie so zu veralbern wie eben.
  • 48:07 - 48:11
    Es gibt ein paar mehr Regeln, welche beim Aussuchen der Kurve
  • 48:11 - 48:14
    und beim Designen des Protokolls beachtet werden können.
  • 48:14 - 48:18
    Dies heißt, dass Sie als Implementierer leichter arbeiten können.
  • 48:18 - 48:25
    Der Protokol Designer kann sagen, dass Sie die Skalare a und b,
  • 48:25 - 48:27
    die Geheimnisse die Sie für Diffie-Hellmann nutzen,
  • 48:27 - 48:31
    immer multiplizieren sollen mit dem sogenannten Kofaktor der Kurve.
  • 48:31 - 48:34
    Die ist der Basispunkt der Ordnung l,
  • 48:34 - 48:35
    es hat l unterschiedliche Vielfache.
  • 48:35 - 48:39
    Z.B. sind dort vier mal l, oder acht mal l Punkte auf der Kurve,
  • 48:39 - 48:41
    dann sieht man nur l.
  • 48:41 - 48:44
    Um für die daraus resultieren Lücke aufzukommen und ausgeklügelteren Attacken zuvorzukommen,
  • 48:44 - 48:47
    multiplizieren wir die geheimnisse a und b immer mit acht.
  • 48:47 - 48:50
    Dies beschützt uns komplett vor diesen Attacken
  • 48:50 - 48:54
    und kann im Protokoll aufgenommen und getestet werden.
  • 48:54 - 48:59
    Weiterhin kann der Designer der Kurve immer Kurven aussuchen,
  • 48:59 - 49:01
    die"verdrehungssicher" sind.
  • 49:01 - 49:04
    Da ist immer ein bisschen Spielraum, wenn jemand einen komprimierten Punkt schickt.
  • 49:04 - 49:07
    Und diese "Verdrehungssicherheit" sagt etwa aus:
  • 49:07 - 49:12
    Dieser Spielraum lässt Ihnen die Möglichkeit zwischen verschiedenen Kurven auszusuchen.
  • 49:12 - 49:16
    Da gibt es die erste Kurve aber auch ihre verwandte Kurve, die "verdrehte Kurve" genannt wird.
  • 49:16 - 49:21
    Der Designer der Kurve kann sicherstellen, dass beide sicher sind.
  • 49:21 - 49:24
    Beie haben große Primzahlen, dann ist da ein l und ein verwandtes l
  • 49:24 - 49:28
    und ein kleiner Kofaktor sowie ein weiterer kleiner Kofaktor.
  • 49:28 - 49:31
    Wenn der Designer eine der "verdrehungsicheren" Kurven wählt,
  • 49:31 - 49:34
    bleibt dem Angreifer keine Flexibilität mehr übrig.
  • 49:34 - 49:39
    Der Angreifer hat dann keine Informationen mehr über Ihr Geheimnis a und b.
  • 49:39 - 49:42
    So, warum machen wir dies nicht einfach?
  • 49:42 - 49:44
    Naja, es geschieht in Teilen.
  • 49:44 - 49:48
    Es gibt bereits eine Bewegung für die nächste Generation von einfachen Standards.
  • 49:48 - 49:51
    Nächste Generation meint, dass es Kurven geben soll,
  • 49:51 - 49:53
    bei denen man sich nicht selber verzettelt, wenn man diese
  • 49:53 - 49:54
    auf die einfachste Weise implementiert.
  • 49:54 - 49:57
    Das heißt, dass eine einfache Implantation auch eine sichere Implantation sein soll.
  • 49:57 - 50:01
    Normalerweise, wenn man etwas sicherer gestaltet,
  • 50:01 - 50:02
    wird es langsamer.
  • 50:02 - 50:04
    Nun der Bonus in diesem Fall ist, dass es schneller wird.
  • 50:04 - 50:09
    Bereits in 2010 hat Adam Langley von Google in die TLS mailing list geschrieben:
  • 50:09 - 50:13
    " Hey Leute, da Kryptographie weiter fortgeschritten ist,
  • 50:13 - 50:18
    wäre es nicht gut, wenn wir Kurve 25519 als benannte Kurve haben?"
  • 50:18 - 50:19
    Dann ist nicht viel passiert.
  • 50:19 - 50:24
    Wir haben daran gearbeitet gute Methoden,
  • 50:24 - 50:26
    naja zumindest denken wir das,
  • 50:26 - 50:28
    zum Erstellen von Kurven zu entwicklen.
  • 50:28 - 50:31
    Naja, dank Snowden im letzten September,
  • 50:31 - 50:35
    gibt es nun emotionale Reaktionen von Leuten.
  • 50:35 - 50:39
    Die sagen, da NIST Kurven einen Teil ihrer Vertraulichkeit verloren haben,
  • 50:39 - 50:42
    und wir denken, vielleicht ist die NSA nicht nur gut,
  • 50:42 - 50:44
    sollten wir nicht eine neue Bewegung haben?
  • 50:44 - 50:46
    Zum Glück gibt es viele weitere Leute die sagen:
  • 50:46 - 50:50
    "Es ist nicht, dass wir paranoid sind, wir wissen nicht ob die NIST Kurven unsicher sind,
  • 50:50 - 50:55
    aber sie sind garantiert nicht gut zu implementieren."
  • 50:55 - 50:57
    Wir könnten schneller und sicherer sein.
  • 50:57 - 51:02
    Dazu gibt es einige Zitate und auch ein Entwurf.
  • 51:02 - 51:08
    Wenn jemand ein paranoides Sicherheitslevel erreichen will, haben wir hier 41417 Bits.
  • 51:08 - 51:18
    Ähm, eine SafeCurves Seite und so weiter.
  • 51:18 - 51:21
    Final, CFRG verändert sich.
  • 51:21 - 51:25
    Da war ein Typ von der NSA, der ein Co-Leader von CFRG war.
  • 51:25 - 51:29
    Also CFRG ist eine Kryptogramme Forschungsgruppe von der Internet Engineering Task Force.
  • 51:29 - 51:37
    Und er NSA co-chair wird weiter dort sein um sie zu unterstützen und zu sagen, wem sie vertrauen sollen.
  • 51:37 - 51:41
    Nun, ich hatte gehofft dass wir im Guten enden.
  • 51:41 - 51:42
    Dass wir sagen können, es ist alles gut hier.
  • 51:42 - 51:47
    Immerhin gibt es einen guten Punkt, Microsoft hat Kurven gewählt...
  • 51:47 - 51:50
    Wissen Sie, sobald Microsoft in die Diskussion eingreift, ist diese beendet,
  • 51:50 - 51:53
    Nunja die letzte Seite sollte etwas Nettes sein, aber aktuell geht die Diskussion einfach weiter.
  • 51:53 - 52:05
    Danke für ihre Aufmerksamkeit!
  • 52:05 - 52:18
    Applaus
  • 52:18 - 52:20
    Moderator: "Danke für Euren Vortrag!
  • 52:20 - 52:24
    Wir haben nur ein paar Minuten für Fragen und Antworten,
  • 52:24 - 52:36
    daher beeilen sie sich bitte und fragen nur kurze Fragen.
  • 52:36 - 52:38
    Okay, los gehts!"
  • 52:38 - 52:50
    Wissen Sie, dass von Attacken oder Schwachstellen in NIST 186-2?
  • 52:50 - 52:58
    Ja, zum Beispiel, ist NIST P224 nicht verdrehungssicher.
  • 52:58 - 53:02
    Dies ist das einzig bekannte Problem.
  • 53:02 - 53:05
    Schauen Sie, wenn Sie sich die Arbeit der ganzen Implentierungen machen
  • 53:05 - 53:10
    und ganz vorsichtig arbeiten und sich schauen ob ein Punkt auf der Kurve liegt,
  • 53:10 - 53:12
    und die richtige Ordnung hat, usw.
  • 53:12 - 53:14
    Wenn Sie eine Menge Arbeit hineinstecken in etwas,
  • 53:14 - 53:18
    was so langsam und fragil ist und hart zu testen und hart zu implementieren.
  • 53:18 - 53:21
    Dann können sie etwas sicheres mit den NIST elliptischen Kurven machen.
  • 53:21 - 53:27
    Ein Schritt in die Zukunft von modernen ECC ist aber etwas zu schaffen,
  • 53:27 - 53:29
    was schneller und einfacher zu implementieren ist.
  • 53:29 - 53:33
    Damit sind auch mehr Leute glücklich.
  • 53:33 - 53:34
    Danke!
  • 53:34 - 53:36
    Okay, bitte
  • 53:36 - 53:39
    "Ja, ganz kurze frage, wenn Sie die NSA leiten würden,
  • 53:39 - 53:44
    könnten Sie Ihren eigenen Standard so beeinflussen, dass Sie ihn knacken könnten?
  • 53:44 - 53:45
    Und wie würden Sie das machen?"
  • 53:45 - 53:50
    Naja, die kurze Antwort wäre, dass das Gute bei Standards ist,
  • 53:50 - 53:57
    dass es viele gibt aus denen man aussuchen kann.
  • 53:57 - 54:00
    Moderator: "Ist das die Antwort?"
  • 54:00 - 54:04
    Also die längere Antwort wäre,
  • 54:04 - 54:08
    dass ich beispielsweise den NC zum französischen Standard (?) wählen könnte.
  • 54:08 - 54:15
    Es gibt keine Rechtfertigung dafür, welche Kurve ich wähle.
  • 54:18 - 54:22
    Zuschauer: "Wir kamen Sie auf die Schlüssellänge von 45 Bits,
  • 54:22 - 54:24
    und woher wissen Sie, dass das sicher ist?
  • 54:24 - 54:28
    Ist es nur die Abwesenheit von sowas wie Indexcalculus?"
  • 54:28 - 54:32
    Ja, die Tatsachen, dass IndexCalculus nicht ausgeführt werden kann,
  • 54:32 - 54:37
    erlaubt ECC mit kleineren Schlüsselgrößen als RSA zu arbeiten.
  • 54:37 - 54:41
    Und die 256 Bits kommen von Schätzungen,
  • 54:41 - 54:47
    was die größten Rechnungen sein werden, die in zehn Jahren mit aktueller Technologie
  • 54:47 - 54:48
    ausgeführt werden können.
  • 54:48 - 54:52
    Zum Beispiel, mit einem 65 Watt Stromwerk,
  • 54:52 - 54:56
    würde die größte Rechenleistung nicht ausreichen um 200 Bit elliptic curves zu knacken.
  • 54:56 - 54:59
    Daher fühlen wir uns mit 256 Bit sicher.
  • 54:59 - 55:06
    Im Bezug auf die Attacken, die wir kennen, sind die Kurven sicher.
  • 55:06 - 55:15
    Auf cryp.to (?) können Sie sehen wie viele Operationen notwendig sind um eine 414 Bit Kurve zu knacken.
  • 55:17 - 55:19
    Wir haben leider keine Zeit mehr,
  • 55:20 - 55:22
    daher nochmal Danke an die Vortragenden!
  • 55:22 - 55:26
    Applaus
Title:
djb, Tanja Lange: ECCHacks
Description:

more » « less
Video Language:
English
Duration:
55:38

German subtitles

Revisions Compare revisions