djb, Tanja Lange: ECCHacks

Entschuldigung für die technischen Schwierigkeiten, für den wirklich sinnvollen Teil des Vortrags gebe ich nun hier weiter an Tanja.

Hallo, ich bin Tanja und neben mir ist Dan, falls das noch nicht bekannt war.

(Gelächter)

Also wir werden über Crypto und ein paar Elliptic curves reden, und hoffen, dass dies ist eine sanfte Einführung ist

Wenn es zu langweilig ist, naja, es ist spät am Abend, also machen Sie ein kurzes Schläfchen,

wachen Sie ab zu und zu auf und schauen, ob sie noch mitkommen.

Also warum Kryptographie?

Wenn Sie Kryptographie im Internet oder für elektronische Zahlungen verwenden,

dann sehen sie zum Beispiel ein SSL Zertifikat in welchem Kryptographie verwendet wird.

Wenn Sie einen elektronischen Pass oder einen elektronischen Personalausweis haben, welcher Signaturen nutzt, oder

wenn Sie TLS verwenden um vertrauliche Daten zu senden, dann möchten Sie Verschlüsselung nutzen.

Wenn Sie einen SSL-Exchange haben, nutzen sie z.B. RSA, Diffie-Hellmann oder ECDH.

Und um EC, ECDH und ECDSA geht es heute in diesem Vortrag.

Außerdem gibt es noch einen großer Anteil an der Kryptographie, die sogenannte "secret key cryptography".

Das ist wirkliche eine coole Sache, es sie ist viel viel schneller als alles was wir Ihnen heute vorstellen.

Aber sie setzt voraus, dass die beiden Parteien, die miteinander reden möchten sich bereits kennen,

also dass sie bereits einen Schlüsselaustausch durchgeführt haben

Wir werden Ihnen zeigen wie man diesen Schlüsselaustausch durchführt.

Und vielleicht dann im nächsten Jahr, die symmetrische Kryptographie.

Okay, also warum sollte man in public key Kryptographie ECC (elliptic curve cryptography) nutzen

Was hat dazu geführt, dass Personen sich für ECC interessieren?

Die einfache Antwort dafür ist eine Angriffsstrategie namens Index-Calculus.

Nun diese nutzen Sie, wenn Sie den RSA Schlüssel von jemanden faktorisieren,

oder den ursprünglichen nicht-elliptischen Diffie-Hellman knacken, möchten.

Dann nutzten Sie Index-Calculus.

Dies ist eine ausgefallene Nutzung von Mathematik sowie die damit einhergehenden Algorithmen.

Im Endeffekt werden diese immer schneller und schneller,

sodass wir am Ende gar nicht wissen, wie schnell sie einmal sein werden.

Hier ist ein Teil der Geschichte, wann die Algorithmen erfunden wurden:

1975 wurde einer der ersten Index-Calculus Algorithmen, CFRAC,

zum Faktorisieren von großen Zahlen entwickelt.

In 1977, 1982, 1990. 1994 gab es dann alle möglichen Arten von Fortschritten.

Sie haben letztes Jahr von der Cryptoapocalypse gehört.

Und diese ist eine der neusten Fortschritte in Indexcalculus

Es ist zwar nicht relevant für das Knacken von RSA,

aber es ist ein Beispiel dafür, dass die allgemeine Strategie des Index-Calculus

immer weiter verfeinert, hochwertiger und schneller wird.

Das ist nicht die ganze Geschichte.

Wenn man sich die wissenschaftliche Fachliteratur anschaut, dann gibt es dort auch viele Verbesserungen.

Wir sind glücklich, wenn wir doppelt so schnell faktorisieren können,

aber das sind große Schritte, wenn man die Sicherheit von zwei typischen RSA Größenordnungen bedenkt.

Also da ist RSA 1024, was man noch häufig im Internet sehen kann

und da ist RSA 2028, was hoffentlich Ihre Bank nutzt.

Dann sind dort zwei Zeilen mit Nummern...

Entschuldigung

Zwei Spalten mit Nummern, wo Sie sehen können, wie sehr die Sicherheit abgenommen hat.

Also zurück in 1975, der CFRAC Algorithmus würde immer noch 2 hoch 120 Operation brauchen,

um die selbe Arbeit zu machen, welche in vielen Jahren später ein mit Zahlen gefülltes Sieb macht.

Also in den 80er würde nur 2 hoch 80 Operationen notwendig sein.

Daher ist hier ein großer Rückgang vorhanden,

von 120 Operations auf 80.

Und es ist nicht nur eine Verringerung um 40 im Exponenten, es ist deutlich größer,

Es reduziert diesen von 170 auf 112.

Somit ist es nicht nur eine lineare Verringerung im Exponent.

Es ist mehr als eine lineare Verringerung im Exponent.

In '85, als die [unverständlich],

hat Miller elliptic curves als Alternative zu faktorisierungsbasierten Methoden vorgeschlagen,

da Faktorisierung und Diffie-Hellman von den Algorithmen geknackt werden.

Miller sagte: "Nun, ich habe mir dieses neue Prinzip der elliptic curves angesehen,

und es ist extrem unwahrscheinlich, dass eine Index-Calculus Attacke auf die elliptic curves Methode jemals klappen würde.

Also können wir alle die Verbesserungen dieser Methoden ignorieren,

die die Faktorisierung und Diffie-Hellman geschwächt haben."

Um in elliptic curve cryptography sanft einzusteigen, haben wir hier die clock cryptography.

Nun, hier ist Bild von einer Uhr.

Hast du zufällig eine Uhr um sie den Menschen zu zeigen,

falls sie nicht mehr dran gewöhnt sind, wie eine Uhr aussieht?

Also ein rundes Ding.

Wissen Sie, wenn Sie denken dass eine Uhr Ihnen Ziffern nebeneinander anzeigt, hier, so sahen Uhren früher aus.

Für Mathematiker, es ist x^2 + y^2 = 1

Es ist etwas kaputt, deswegen sind wir zu spät.

(schmunzeln)

Die elliptic curves die wir Ihnen später im Vortrag zeigen,

beinhalten nicht die Uhr.

Die clock cryptography ist kein Beispiel für elliptic curve cryptography,

aber sehr, sehr nah dran.

Daher starten wir mit der clock cryptography und wenn Sie damit vertraut sind,

machen wir eine kleine Anpassung und dann haben wir die elliptic curve cryptography.

In Ordnung, also zum Beweis, dass ich den Kindergarten abgeschlossen habe,

hier sind ein paar Punkte auf der Uhr.

Dort oben ist 12 Uhr, so habe ich das gelernt.

Nun ich bin später Mathematikerin geworden und Mathematiker arbeiten gerne mit Koordinaten.

Also 12 Uhr hat die x-Koordinate 0 und die y-Koordinate 1.

Ich weiß, dass die 1 da sein muss, da es die Formel x^2+y^2=1 erfüllen soll.

x^2=0, daher y^2=1 und y=1.

Aber es gibt viel mehr Punkte,

also dort ist 18 Uhr.

Dort haben Sie Frühstück, ähm Lunch.

Das ist die 15 Uhr Marke, da ist die 21 Uhr Marke,

da ist, ... ,oh was ist das?

Das habe ich nicht im Kindergarten gelernt.

So es ist, ähm, halb nach oben dann schauen, wo ist die eins,

dann halb rüber.

Das schaut aus, ähm, wie die 2 Uhr Marke.

Hier wurden die Koordinaten umgedreht.

Nun x = 1/2, also sind wir irgendwo hier drüben,

und dann ins negative, das wäre die 5 Uhr Marke.

Und mehr und mehr Punkte...

Sollte es nicht sanft sein?

Ist es nicht sanft?

[Applaus]

Okay, also...

Hey, hier sind ein paar Punkte die ich noch nicht gesehen habe.

Oh, tut mir leid, ähm, ich glaube wir wollten mehr über Punkte wie diese erzählen.

3/5, 4/5, ich meine, hier muss man richtig komplizierte Mathematik nutzen,

um zu sehen, dass eine Formel (3/5)^2+(4/5)^2=1 ist.

Dies ist ein weiterer Punkt auf der Uhr und es ist nicht ersichtlich,

wie viel Uhr es ist.

Sie müssen wirklich intensiv auf ihre Uhr schauen um das herauszufinden.

Immer am Aussteigen wenn es knifflig wird.

Entschuldigung?

Nun steigst du aus, wenn es es knifflig wird.

Aussteigen wenn es knifflig wird?

[Lachen]

Okay, also willst du wirklich, dass ich das Quadrat, das halbe Quadrat, ...

Nein, nein, ich weiß einfach nicht wo der Punkt ist, aber ich weiß er ist auf der Uhr.

Okay, also du kannst herausfinden, wo der 3/5, 4/5 Punkt ist, im Bezug auf die Uhrzeit.

Sie können es auch etwas komplizierter machen in dem Sie die Uhr parametisieren.

Also wenn Leute Punkte auf der Uhr nehmen,

dann denken sie an eine voranschreitende Zeit.

Also es gibt 2 Uhr, 3 Uhr und das kann addiert werde, und man bekommt 5 Uhr.

Zwei Stunden nach 3 Uhr oder drei Stunden nach 2 Uhr ist 5 Uhr.

Und hier ist ein Bild, das etwa so aussieht, als ob 1:30 plus 2 Uhr so etwas wie 3:30 ergibt.

Also hier sind ein paar Punkte p1, p2 und p3 auf der Uhr.

Und Sie können p1 und p2 addieren, um p3 zu erhalten.

Hier kommt der schreckliche mathematische Teil, den wir gleich verwerfen werden - die Trigonometrie.

Wenn Sie einen Punkt auf der Uhr haben, hat er einen Winkel von Alpha.

Die Zeit von Alpha beginnt bei 12 Uhr, dann ist dieser Punkt x gleich Sinus von Alpha, Y gleich Kosinus Alpha.

Es gab es diese schrecklichen trigonometrischen Formeln für den Sinus der Summe zweier Winkel und den Kosinus von ...

Die Summe von zwei Winkeln und der Sinus von Alpha 1 plus Alpha 2 ist...

Okay, Sinus von Alpha 1, Cosinus von Alpha 2 plus Cosinus von Alpha 1, Sinus von Alpha 2.

Etwas Ähnliches gibt es für den Cosinus.

Sie können Punkte hinzufügen mithilfe der Sinus und Cosinus Funktionen.

Normalerweise überreden wir die Leute, sich der Crypto-Seite zuzuwenden indem wir ihnen sagen:

"Sie können die ganze nichtdiskrete Mathematik vergessen"

"Wir möge diskrete Mathematik, wir sind die diskreten Typen,

also wird es keine Sinus und Cosinus geben."

Okay, lasst uns sie loswerden. Wir wollen keinen Sinus und Cosinus haben.

Eigentlich würden wir gerne mit normalen Uhrzeiten arbeiten.

Sinus 1, Cosinus 2 und so weiter sind einfach meine x- und y-Koordinaten.

Alles, was ich hier gesagt habe, war, dass die x-Koordinate ein Sinus von Alpha ist.

Die y-Koordinate ist der Kosinus von Alpha.

In diesem ganzen Durcheinander mit den Trigonometrieformeln,

kann ich einfach jeden Sinus von Alpha durch das entsprechende x ersetzen.

Und jeder Cosinus von Alpha wird durch das entsprechende y ersetzt.

Dadurch wird dies viel schöner und kürzer.

Keine trigonometrische Additionsformel. Also wenn Ihnen bei der Addition auf der Uhr

Ihnen zwei Punkte x1 y1 und x2 y2, gibt, dann müssen Sie nur die x-Koordinate des ersten Punktes

und die y-Koordinate des zweiten Punktes nehmen und diese multiplizieren.

Nehmen Sie dann die y-Koordinate des ersten Punktes und die x-Koordinate des zweiten Punktes und multiplizieren Sie diese.

Addieren sie das.

Das gibt Sie die neue X-Koordinate. Warum?

Wir können einfach vergessen, woher sie stammt.

Dann machen wir dasselbe mit der Y-Koordinate.

Sie ist das Produkt aus den Y-Koordinaten minus dem Produkt der X-Koordinaten.

Okay.

Hier sind einige Beispiele für die Addition von Uhrzeiten, die wir noch nicht behandelt haben.

Wir haben keinen Computer hier, daher wird dies etwas mühsames Rechnen.

2 Uhr plus 5 Uhr.

Wir erinnern uns, dass dies im Test sein wird.

2 Uhr war diese Quadratwurzel aus 3/4 und 1/2.

Sie hat am Anfang darüber gesprochen.

Und 5 Uhr war 1/2 und minus Quadratwurzel von 3/4.

Wenn Sie das in die Formel einsetzen...

Okay, ich werde es mal versuchen.

x1 ist Quadratwurzel von 3/4.

y1 ist 1/2.

x2 ist 1/2 und y2 ist minus Quadratwurzel von 3/4.

Wenn Sie x1 mit y2 multiplizieren ist, dann ist das die Quadratwurzel von 3/4 multipliziert

mit der minus Quadratwurzel von 3/4, welche minus 3/4 ist.

Dann müsste y1 mal x2, 1/2 mal 1/2 sein, was 1/4 ist.

Addiert man diese, ist es ungefähr minus 1/2.

Führt man eine ähnliche Berechnung durch, erhält man den 2. Teil des Ergebnisses.

Man erkennt, dass 2 Uhr plus 5 Uhr mit diesen Formeln das ist, was Sie wollten, nämlich 7 Uhr.

Ähnliches können Sie mit 5 Uhr plus 9 Uhr machen.

Ich denke, wir werden es überspringen.

Versuchen wir es mit einem anderen Beispiel.

Sie können 3/5 und 4/5 nehmen und sie addieren.

Das bedeutet, dass 2 mal (3/5 mal 4/5) dann 3/5 mal 4/5 plus 3/5 und 4/5 sind.

Fügen Sie dies in die Formeln ein und Sie wissen nicht, wie spät es ist.

Sie erhalten einfach eine Antwort, 24/25 und 7/25

Und Sie können immer mehr Kopien, des Punktes auf den Punkt selbst hinzufügen.

3 mal 3/5, 4/5, das ist also der Punkt plus sich selbst plus sich selbst

Setzen Sie ihn einfach in die Formeln ein und Sie erhalten etwas mit mehr Ziffern.

Wenn Sie immer mehr Kopien hinzufügen, erhalten Sie immer mehr Stellen.

Der Nenner ist nun 625 und er wird immer größer.

Sie können auch versuchen, jeden gewünschten Punkt zu 12 Uhr hinzuzufügen, ohne überhaupt zu wissen, welcher es ist.

12 Uhr mit 0,1 (Koordinaten)

Wenn Sie diese in die Formeln einsetzen, erhalten Sie 12 Uhr plus 3 Uhr ist 3 Uhr.

12 Uhr plus 5 Uhr ist 5 Uhr

12 Uhr plus irgendein Wert ergibt als Ergebnis diesen Wert.

Das ist sofort ersichtlich aus der Formel zur Addition von zwei Punkten.

Ein letztes Beispiel dafür, wie Sie mit dieser Additionsformel arbeiten können.

Sie nehmen beispielsweise 10 Uhr + 2 Uhr. Das sollte 12 Uhr sein.

10 + 2 = 12. Das ist logisch.

Das Gegenteil wäre 10 + 2, wenn man 9 + 3 oder 11 + 1 oder irgendetwas nimmt,

was die gleiche Höhe, die gleiche Y-Koordinate hat, aber die X-Koordinate negativ ist.

Diese ergeben zusammen 12 Uhr.

Sie können einfach versuchen x1 und y1 und minus x1y1 in die Formel einzusetzen.

Versuchen wir das mal:

Angenommen, wir sagen, x2 ist minus x1 und y2 ist y1

und setzten es in die Formel ein.

Sie sehen die erste ähm...

Die erste Koordinate der Antwort, welche ist: x1*y2 = y1

Und y1= -x1*x2... ähm sorry,

x2 ist -x1*y1. Die ergibt im Endeffekt null.

Das ist, was wir für 12 Uhr erwartet haben.

Nächster Teil: y1y2 = y1 mal y1 minus x1*x2, das ist

minus x1 mal minus x1 = x1 im Quadrat,

und x1 im Quadrat + x1 im Quadrat ist gleich 1.

Wir können etwas herumspielen mit Additionen und Multiplikationen.

Diese Formel können wir verwenden, um alle möglichen Punkte zu addieren.

Okay.

Nun wird es noch etwas diskreter.

Wir können den Kreis vergessen der unendlich viele Punkte hat.

Sie können jede reelle Zahl nehmen und einfach Quadratwurzeln ziehen.

Wir machen das mit einem sehr kleinen Menge von Elementen.

Wir machen mit Uhrzeiten über Suchfelder.

Ich beschränke mich jetzt nur auf die Zahlen 0, 1, bis 6.

Das ist also, wofür diese F7 steht.

Ich will diese Zahlen addieren und multiplizieren können.

Wenn ich 2 und 5 multipliziere, ist das ist größer als 10.

Diese Zahl ist größer als die Menge, die ich dort zur Verfügung habe.

Lasse ich nur 6 als größte Zahl zu, gehört 10 nicht zur Menge.

Also werde ich das reduzieren und den Modulus 7 nehmen.

Wir haben einige Python-Schnipsel versprochen.

Wir erfahren nun, wir wir beispielsweise alle diese Elemente finden können.

Wir gehen alle x zwischen 0 und 7 und y zwischen 0 und 7 durch.

Wir überprüfen einfach, ob x mal x plus y mal y = 1 ist.

Ist dies der Fall, drucke ich das Doppelte xy aus.

Dann drücke ich die Eingabetaste und wir erhalten diese Punkte für das Bild.

Wir haben keine bis 6 verwendet, wir möchten die Symmetrie beibehalten.

Wir haben -3 bis + 3 genutzt. -3 ist hier drüber, +3 hier.

+ 3 ist in der y-Richtung und - 3 ist in der y-Richtung

Das ist der Punkt 0,1, also derselbe Punkt, den wir vorher auf der Uhr hatten.

Also ist dies die Uhrzeit.

Es ist der Punkt 2,2

Okay.

Wir verwenden die Uhradditionsfunktion.

Wir zeigen eine Funktion, um Punkte der Uhr hinzuzufügen.

Es ist hilfreich, Plus und Minus bei den Uhrzeiten schreiben zu können,

die diese Reduzierung automatisch durchführen, Mod 7.

In Python können wir einen Plus- und Minus- und Hoch-4 und F7-Klasse einrichten.

Diese sind getrennt, von den

üblichen für Plus-Minus und die Multiplikationen für Ganzzahlen.

Um dies einzurichten gehen Sie bitte wie folgt vor:

Hier ist eine F7-Klasse, einen Integer x liest und ein F7-Element initiiert.

Hierbei handelt es sich um die in den Integer Mod 7.

Wenn Sie F7 von 7 nehmen, wird 7 mod 7 berechnet.

Der Quotient ist 1

Der Rest ist 0

Man fügt 0 in self.int ein.

Dieser Stir-and-Wrapper, eventuell nicht die eleganteste Möglichkeit zum Drucken von Dingen,

gibt aus, dass alles Mod 7 ist.

Wir drucken nur die Ganzzahl aus, die wir bei 7 erhalten.

7 Mod 7 gibt 0 und 10 mod 7,

war das Beispiel von Tanja eben, wo der Rest 3 ergibt.

Und 20 mod 7, subtrahiert man 7, und subtrahiert wieder 7, erhält man eine 6.

Man kann also in diese F7 jeden integer eingeben, den man möchte.

Dafür nehmen wir diesen Integer-Mod7.

Nun können wir F7 einige weitere Funktionen hinzufügen.

Beispielsweise können Sie einen Gleichheitstest durchführen.

Pythons default Gleichheit ist ziemlich dumm.

Das was ich eigentlich tun möchte, ist folgendes:

Ich möchte diese Punkte vergleichen, die den gleichen F7-Wert haben.

Okay.

Nun wurde dieser F7-Typ um eine Gleichheit erweitert.

Sie können sehen, dass F7 von 10 und F7 von 3 gleich sind.

F7 von 0 und F7 von 2 sind nicht gleich.

Wir haben von 0 bis 6 als Möglichkeiten für die Werte einer Variablen ausgedrückt.

Dann folgt die Addition, Subtraktionen und Multiplikation.

Schauen wir uns die Addition an, dann ist der typische Fall.

Sie nehmen zwei a und b.

Dann nehmen Sie eine Integer innerhalb einer Integerrange von 0 bis 6.

Addieren Sie diese auf der Seite b von 0 bis 6.

Sie erhalten 0 bis 12.

Diese geben Sie dann wieder in den F7 Konstruktor ein.

Sie haben jetzt wieder 0 bis 6.

Unten sind einige Beispiele von 2 plus 5 = 0

2 minus 5 ist -3.

Das ist 4.

Wenn Sie in C programmieren, achten Sie auf folgendes:

Der Prozentwert darf den Mod nicht ausführen, den wir mathematisch wollen.

Pythons Prozentwert macht das Richtige und C gibt negative Zahlen aus.

Prozent in Python gibt Ihnen immer 0 bis 6.

Oder 0 bis zu jeder Zahl, die Sie genommen haben.

Ähm

2 mal 5 war wieder das Beispiel von 10, wo Mod 7= 3 ergibt.

Okay.

Jetzt haben wir eine kleine Uhr gesehen.

Da konnte ich einfach alle Elemente zeichnen,

und wir konnten sie durchgehen und ausprobieren.

Alles was Dan mit dem Python-Setup gezeigt hat, da kann ich 7 durch eine größere Zahl ersetzen.

Sagen wir mal 1.000.003, das ist auch eine Primzahl.

Ich gehe hin und definiere eine Addition von Kurvenpunkten.

Das ist genau das, was wir vorhin auf der echten Uhr gemacht haben.

Nun werde ich die Elemente 1.000.003 einfügen.

Ich nehme also meine Punkte und mache x1y2, y1x2 und so weiter.

Dann bekomme ich den Punkt zurück.

Wir machen nun ein Beispiel dazu.

Einer der vielen Punkte, die ich in die x-Koordinate einfüge ist 1000.

Denken Sie daran, dass es aus 1000 aus 1.000.003 ist.

Anschließend überprüfe ich, ob es eine y-Koordinate gibt und dazu passt.

Ja, gibt es grob.

Habe ich also 1000, erhalte ich eine Million im Quadrat und 2 ergibt 4.

Das ist nur 1 größer als die 1.000.003.

Ja, das ist also ein gültiger Punkt.

Jetzt kann ich diesen Punkt übernehmen und addiere ihn zu sich selbst.

Ich setzt einfach p und p in die Addition ein, die 4007 ergibt.

Ich kann es immer und immer wieder zu sich selbst addieren.

Ich addiere immer weiter bis ich am Ende 6 Kopien habe.

Ich füge sie zusammen und habe nun diesen Punkt.

Wenn Sie das sehen, denken Sie natürlich: Warte mal.

Muss ich tatsächlich alle diese 5 Additionen machen?

Nein.

Wenn ich beispielsweise bei p3 aufgehört hätte.

Das ist dreimal der Punkt und addiere dann p3 plus p3

Das sind also 3 Kopien plus weitere 3 Kopien, sind auch 6 Kopien.

Diese beiden Dinge haben das gleich Ergebnis.

Möchte ich das also professioneller machen,

ist hier die Modifikation der Scale.

Okay

Das ist eine rekursive Funktion zur Berechnung von n mal p.

Sie haben einen beliebigen Punkt auf der Uhr p in einem beliebigen Skalar,

Jeden nicht negativen Integer n, den Sie möchten.

Wenn n 0 ist,

dann geben Sie den 12-Uhr-Punkt zurück.

Wenn n = 1 ist, geben Sie den Punkt p einmal zurück,

also p ist p.

Und dann, wenn n gerade ist, dann ändert der Python seine Notation im Laufe leicht.

n // 2 ist der richtige Weg, um eine durch 2 geteilte Integer nehmen.

Und den Rest wegzuwerfen.

So ist n // 2, gerade bei n^2.

Wenn n*2 ist wird rekursiv n mal p berechnet.

Wie zum Beispiel 3 mal p, wenn n gleich 6 ist.

Dann kommt bei (Q,Q) heraus, das n^2 mal p zu verdoppeln.

Man erhält np, wenn n ungerade ist.

Dann ist das n über 2 .

Anschließend nehmen Sie das dann mal p.

Verdoppeln sie das, was n minus 1 mal p ergibt.

Addieren Sie p dazu.

Das heißt, wenn n mod 2 ungleich Null ist, dann addieren Sie p zu q.

Schließlich erhalten Sie n mal p in allen unterschiedlichen Fällen.

Anschließend haben wir für das eine 6stellige Zahl n versucht.

Das wird hier auf der Folie nicht gezeigt.

Es ist geheim und es waren etwa 30 Uhrzeit-Additionen erforderlich.

Das waren nicht sehr viele Multiplikationen, um n mal p zu berechnen.

Das ging sehr schnell.

Es kommt sofort heraus und das ist die Antwort.

Es gibt die x- und y-Koordinaten von n mal p für das geheime n, das es war.

Nun ist es nicht mehr so offensichtlich, wie man herausfinden kann, was n ist.

Sieht man das n mal p, und arbeitet dann rückwärts zum n, dann weiß man, welches p ist.

Sie wissen was n mal p ist.

Sie wissen, dass n nicht zu groß ist.

Okay

Es gibt nur eine Million Möglichkeiten.

Das ist keine wirklich ausgefallene Berechnung.

Es wird allerdings einen Moment dauern, bis es erledigt ist.

Es ist etwas, bei dem der Computer einiges rechnen muss.

Sie können nun vielleicht versuchen, das schneller zu machen.

Allerdings könnten wir dann versuchen, die Zahlen größer zu machen.

Statt 1.000.003 könnten wir immer noch n mal p machen.

Wobei n viel größer ist und die 1.000.003 eine viel größere Primzahl ist.

Hier gibt es also eine kleine Herausforderung.

Sie können nun versuchen herauszufinden, was dieses n ist.

Dies ist schwieriger, als eine SMS an die Telefonnummer zu senden, die gerade nicht funktioniert.

Ooh! ... Gemurmel

Nehmen wir also an, wir machen es viel schwieriger.

Wir machen es sehr schwierig.

Wir haben das Gefühl, dass Sie es für Kryptographie verwenden möchten.

Jemand möchte die Uhrzeit-Kryptographie standardisieren .

Dann beginnen Sie mit der Standardisierung einer großen Primzahl p.

Große Zahl, also keine Million.

So groß mit mehreren Tausend Bits.

Sie können auch folgendes machen:

Sie standardisieren einen Basispunkt.

Diese p auf der vorherigen Folie bedeutet:

Wir geben Ihnen p, wir geben Ihnen n-mal p.

Wir geben Ihnen einfach kein n.

Wir nehmen an, dass Ihnen jemand ein kleines p gibt, das die Primzahl ist.

Dieser Basispunkt P, x- und y-Koordinaten , die auf der Uhr stehen.

Was machen Alice und Bob, wenn sie kommunizieren wollen?

Ich würde gerne etwa an den Bob schicken.

"Ich bin Bob".

Dann wählt Alice, bzw. ich aus:

Mein Geheimnis, a.

Berechne a mal diesen Basispunkt.

Dies ist die Berechnung, die du gerade auf der vorigen Folie gesehen hast.

Sie ist immer noch sichtbar.

Dies ist also genau wie eine logarithmische Zeit von der Größe a.

Anschließend sende ich das an Dan.

Dann denke ich, ich muss etwas berechnen.

Ich nehme mein eigenes großes Geheimnis b, das ich niemandem verraten werde.

Dann berechne ich b mal das gleiche Standard (X,Y)

Ich sende mein b-mal (X,Y) an Alice zurück.

Alles klar.

Jetzt habe ich also sein b mal den Basispunkt.

Er hat mein a mal Basispunkt.

Ich weiß jetzt noch, was mein a war.

Ich nehme nun dieses a und den neuen Punkt, den er mir gerade gesendet hat.

Dann setze ich diesen Punkt in die Skarlarmultiplikation ein.

Ich mache die gleichen Schritte, addiere den Punkt zu sich selbst.

Und den Punkt zu dem Punkt, den er mir geschickt hat.

Dies sind also die gleichen Schritte hier, außer dass dieses p jetzt der Punkt ist, den er mir gesendet hat.

Es ist nicht mehr der Basispunkt.

Auf diese Art und Weise berechne ich a mal b mal p.

Okay.

Nun bekomme ich ihr a mal (X,Y).

Ich nehme mein geheimes b und multipliziere es mit dem a mal (X,Y).

Nun bekomme ich mein b mal a mal den Punkt (X,Y).

Ich habe das gleiche Ergebnis erhalten.

Nun hat sie a* b mal (X,Y) berechnet.

Ich habe b*a mal (X,Y) berechnet.

Das ist dasselbe.

Sie sind beide a mal b Vielfache von (X,Y).

Wir addieren a mal b Kopien von (X,Y).

Nun verwenden wir das geteilte Geheimnis zum Verschlüsseln von Daten.

In Ordnung.

Wir haben auch ein Bild davon.

Auch wenn wir nichts anderes machen.

Und Bob, hier sehen Sie, wie die Nachricht jetzt verbreitet wird.

Sollten Sie der Lauscher sein, wollen Sie herausfinden, was wir haben.

Du kannst nicht sehen, was ich hier mache.

Du kannst nicht sehen, was Dan hier macht.

Du kannst nur sehen, was hierher gesendet wird.

Du weißt, was das kleine p ist und was der Basispunkt ist.

Zumindest ist das ist das, was wir uns wünschen.

Nun gibt es aber einige Vorbehalte:

Verwenden Sie nicht einfach irgendein Primzahl-p.

Viele Auswahlmöglichkeiten von p sind unsicher.

Warnung 2!

Dies ist immer noch die Uhr.

Und wir haben am Anfang gesagt, dass Uhren keine elliptischen Kurven sind.

Nur elliptische Kurven sind gut.

Demnach sind die Uhren eigentlich eigentlich fast das

Gleiche wie "RSA" oder "Finde das Feld".

Wenn Sie etwas finden möchten, das RSA 3072 Bits hat, dann muss Ihre Uhr die Primzahl haben.

Die Uhr muss 1536 haben, also halb so viele Bits wie RSA Zahlen.

Das ist nicht das, was Sie tatsächlich möchten.

Okay.

Dritte Warnung: Timing-Angriffe

Eben haben viele von Ihnen über Bleichenbacher-Angriffe gegen SSL gesprochen.

Viele der Informationen von einem angegriffenen Server oder Client stammen vom Timing.

Der Angreifer sieht sich nicht nur das Abhören der öffentlichen Schlüssel a mal x y und b mal x y an.

Er sieht auch, wie lange Sie für Berechnungen gebraucht haben.

Der Angreifer kann sogar oft sehen,

wie lange Sie für jeden einzelnen Vorgang gebraucht haben.

Die funktioniert, weil es elektromagnetische Emissionen oder Funkemissionen

oder Cache-Effekte auf virtuellen Maschinen gibt.

Diese wirken sich auf andere virtuelle Maschinen aus, die unter demselben Hypervisor

auf derselben physischen Hardware ausgeführt werden.

Sie können dann als Angreifer auf Informationen zugreifen,

wie lange Alice und Bob brauchen.

Sie sehen diese Berechnung nicht wirklich,

aber Sie sehen die physikalischen Auswirkungen dieser Berechnung.

Stellen Sie sich einfach vor, Eves Ohr ist genau hier.

Sie kann hören und sie kann spüren, was die Berechnungen bewirken.

Tatsächliche können Sie das akustische Summen von Ihrer CPU hören,

sofern Sie ein ausreichend gutes Mikrofon daneben platzieren.

Dies hängt auch von den Berechnungen ab, die es ausführt.

Es gibt hier einige echte Beispiele für Timing-Angriffe.

2 von den 3 ausgewählten Beispielen sind ECC Beispiele.

Ein Beispiel davon ist der Lucky-13-Angriff.

Das war nicht gegen ECC. Das ist eine andere Art von Timing-Angriff.

Wir wollen Ihnen die Vorstellung vermitteln, dass Timing-Angriffe wirklich wichtig sind.

Dies ist ein Großteil dessen, was bei echten Kryptographie schief läuft.

Abgesehen von deren Unbrauchbarkeit und anderen kleinen Problemen.

Ähm.

Die Lösung für dieses spezielle Problem und das Timing zu sehen ist folgendes:

Die Berechnungen müssen immer in konstanter Zeit durchgeführt werden.

Abhängig von Ihrem Skalar,

dürfen Sie nicht unterschiedlich viel Zeit aufwenden.

Wenn Sie einfach immer dieser Regel folgen, haben Sie bei jedem Geheimnis bei geheimes Timing mehr.

Der Angreifer erhält nichts.

Ihr gesamtes Timing ist öffentlich.

Selbstverständlich ist es etwas mühsam, so Berechnungen durchzuführen.

Auf diese Weise können Sie es immer tun, aber es verlangsamt die Dinge sehr.

Ich denke, das ist leichter gesagt als getan.

Lasst uns zurück zu Warnung Nr. 2 gehen.

Wir nehmen an, dass konstante Zeit für Berechnungen sich um Warnung Nr. 3 kümmert.

Wir gehen zurück zu Warnung Nr. 2.

Uhren sind nicht elliptisch.

Lasst uns diesen Kreis, diese Uhr, in eine elliptische Kurve verwandeln.

Wir nehmen also den Kreis und drücken ihn nach innen.

Mathematisch führen wir nun einen zusätzlichen Term ein,

statt dass x zum Quadrat plus y zum Quadrat = 1 ist.

Sagen wir, dass x zum Quadrat plus y zum Quadrat = 1- 30 x^2 y^2 ist.

Also ist dieser zusätzliche Term hier die Differenz zwischen einem Kreis und einer Edwards-Kurve.

Oder eine elliptische Kurve.

Diese bestimmte Kurve wird also eine Edwards-Kurve genannt.

Aber es ist ein Beispiel für elliptische Kurven.

Ich möchte nun Punkte hinzufügen.

Wir erinnern uns daran, wie es auf dem Kreis aussah.

Auf dem Kreis hatte ich den neutralen Betrag oben.

Ich behalte das bei.

Sodass das Hinzufügen von irgendetwas zur 12-Uhr-Position nicht an dem Wert ändert .

Der Wert ist hier immer noch derselbe.

Ich habe hier nur p1, p2 und p3 durch diese Formeln hinzugefügt.

Nun funktionieren diese normalerweise nicht auf der elliptischen Kurve.

Der Grund ist, da es dieses - 30 x^2 * y^2 gibt.

Daher müssen wir auch hier unten eine kleine Anpassung vornehmen.

Daher gibt es nun einen Nenner.

Nehmen Sie d = 0 an, dann ändert sich die Formel in den Kreis

Auch in die Additionsformeln ändern den Kreis, denn diese 30 hier ist eine Null.

Sie wird also einfach durch 1 geteilt.

Der Kreis kommt als Sonderfall für diese elliptische Kurve heraus.

Nun nehmen wir minus 30 und haben eine schöne elliptische Kurve.

Die Additionsformeln sind nicht viel schlimmer. Sie sind nur ein kleiner zusätzlicher Term.

Okay

Sie können, wenn Sie eine Primzahl p haben, 7.000.003,

irgendetwas viel größeres nehmen.

Sie können jedes nichtquadratische d nehmen, wie minus 30,

jedes d, das kein Quadrat von irgendetwas Modulo p.

Dies ist etwas, das Sie schnell überprüfen können.

Dann können Sie folgendes aufschreiben:

Die Kurve mit x^2y^2 = 1 plus d.

Das ist eine elliptische Kurve.

Und es ist nur das zusätzliche d als zusätzliche Komplikation.

Wenn Sie clock cryptography verstanden haben,

dann ist diese zusätzliche kleine Komplikation alles,

was Sie für die Elliptische-Kurven-Kryptographie benötigen.

Es gib die Additionsformel, die gerade aus den mathematischen Formeln

aus vorangegangenen Folien übersetzt wurde.

Sie sieht fast genauso aus, wie zuvor.

Außer, dass bei x3 und y3 das d an der Stelle des Nenner haben.

Nun könnten Sie sich über dieses Aussage beklagen.

Warten Sie eine Minute, bevor Sie dividieren.

Sind Sie überhaupt in der Lage zu dividieren?

Was passiert, wenn Sie durch Null dividieren?

Vielleicht funktionieren diese Formeln nicht immer.

Das ist ein wichtiger Punkt, auf den Sie achten müssen.

Achten Sie daraus, dass Sie, wenn Sie durch etwas dividieren, nicht durch Null dividieren dürfen.

Es stellt sich aber heraus, dass die Nenner dort 1+d x1 x2 y1 y2 und 1- d x1 x2 y1 y2

niemals gleich 0 sind.

Diese Formeln sind vollständig.

Sie funktionieren immer.

Ich denke, dass Sie annehmen, dass Formeln immer funktionieren sollten.

Es ist ganz ärgerlich, wenn es Ausnahmefälle gibt.

Aber in der Kryptographie mit elliptischen Kurven gibt es so viele Ausnahmefälle.

Die Menschen machen sich oft Sorgen.

Einer der Gründe, warum wir diese diese Art von elliptischer Kurve mögen,

ist, dass es keine Ausnahmefälle gibt.

Wir bezeichnen das Additionsgesetz als vollständig.

Falls Sie sich ansehen, wie der mathematische Teil des Beweises funktioniert, ist folgendes wichtig:

d war kein Quadrat. Aber auch das ist etwas, das Sie leicht überprüfen können.

Und haben Sie sich erst einmal für ein d entschieden, das nicht quadratisch ist

und das jeder verwenden kann, wird es in den Formeln nie Ausnahmen geben.

Wenn Ihr d - äh - quadratisch ist, dann können Sie sich die gleichen Formeln aufschreiben.

Meistens funktionieren sie, aber es gibt Ausnahmefälle.

Und wir werden noch viel mehr über Ausnahmefälle erfahren.

Und das Ärgerliche daran ist nicht nur, dass sie schwer zu programmieren sind.

Sondern, wenn man irgendwelche Fehler macht, wird es schwierig sein,

diese Fehler zu finden und auf diese Fehler zu testen.

Und wenn ein Angreifer mehr darüber nachdenkt

und ihnen einige Punkte findet, die diese Fehler ausnutzen, bricht das oft echtes ECC.

Es ist also besser, eine Kurve zu nehmen, wo das d kein Quadrat ist.

Dann müssen Sie sich überhaupt keine Sorgen mehr darüber machen.

Okay.

Kurz dazwischen... (schwer verständlich)

Mit über einem finalen Feld (?) jedes zweite d ist kein quadratisches.

Daher ist dies keine große Einschränkung.

Und entfernt nur die Hälfte der Möglichkeiten.

Weiterhin sind Divisionen wirklich langsam.

Wenn Sie die implementieren, die Sie vorher im Python-Skript gesehen haben,

haben wir noch nicht mal Divisionen eingefügt.

Wir haben Sie online, aber es ist so, dass es eine Weile dauert.

Es ist unangenehm.

Es dauert sogar noch länger, wenn Sie sich Sorgen über ständige Zeitbeschränkungen machen.

Also fangen wir an Divisionen loszuwerden.

Das ist so wie "Doktor, Doktor, mein Knie schmerzt" und er sagt dann: "Verwenden Sie es nicht".

Aber mathematisch, hier können wir die Verwendung von Divisionen vermeiden.

Wenn Sie sich daran erinnern, wie Sie mit Brüchen a/b + c/d gearbeitet haben,

dann wissen sie, dass wir sie als Brüche behalten.

Bei einem Bruch multiplizieren Sie einfach die Nenner und

kreuzmuliplizieren die Zähler und dann können sie addieren.

Daher machen wir mit unseren Punkten das Gleiche.

Wir führen eine zusätzliche Koordinate ein, die Z-Koordinate.

Sie ist nur der Nenner.

Anstatt Punkte als (X,Y) zu speichern, speichern wir jetzt (X,Y,Z).

Hierbei bedeutet X und Y, dass das alte x und y, x/z und y/z ist.

Sie können aber auch etwas abenteuerlustiger sein.

Und erzielen dann eine bessere Geschwindigkeit,

wenn Sie eine zusätzliche Koordinate namens t einführen.

T = XY / Z

Sind Sie daran interessiert, wie sie das effizient tun

und tatsächlich computerverifizierte Formeln erhalten?

Dann besuchen Sie bitte die "Explicit Formulas Database" unter dem dortigen Link,

um zu sehen wie man Additionen durchführt.

Okay.

Wir kommen nun zu der Darstellung von Crypto zurück.

Wir ersetzen die Uhr durch eine elliptische Kurve.

Das macht die Formeln etwas komplizierter.

Außerdem muss noch eine zusätzliche Auswahl getroffen werden.

Nicht nur die Primzahl p ist standardisiert, sodass jeder sie verwenden kann.

Standardisieren Sie dieses d, das kein Quadrat ist,

sodass jeder sie verwenden kann.

Es muss eine sichere Wahl sein.

Denken Sie an die Warnung Nr. 1

Es gibt viele unsichere Entscheidungen.

Es gibt viele mögliche Standardkriterien.

Diese müssen überprüft werden, um sicherzustellen,

dass es sich um sichere Entscheidungen für Kurven handelt.

Am Ende des Vortrags werden mehr über Standards sagen.

Alice hat dann wie vorher ihren geheimen Schlüssel und multipliziert diesen mit x, y und

Oh

Ich überspringe, was auf dieser Folie steht.

Auf dieser Folie steht Alice auch Bobs öffentlicher Schlüssel b(x,y) besitzt.

Das hört sich alles so an, wie bei der Uhr.

Alice nimmt jetzt das b(x,y) und

multipliziert es mit a.

Das ergibt a(b(x,y)).

Sie merkt sich dann,

dass a(b(x,y)) das Geheimnis zum Verschlüsseln und Authentifizieren von Daten ist.

Da wir jetzt elliptische Kurven haben,

müssen wir uns keine Sorgen mehr darüber machen, dass eine Indexrechnung alles kaputt macht.

Wir brauchen keine Tausenden von Bits.

Hier sind nun einige tatsächliche reale Größen für elliptische Kurven Kryptographie.

Inklusive ist die gesamte und secret key encryption

und Authentifizierung des öffentlichen Schlüssels.

Sie können eine Primzahl haben, die nur 256 Bit groß ist.

Wir werden später sagen, dass Sie x und y zusammen nur auf 256 Bit reduzieren können.

Das reduziert dann den öffentlichen Schlüssel von Alice a(x,y) um ein Vielfaches.

a(x,y) wird auf nur 32 Bytes reduziert.

Diese wird Alice an Bob senden.

Dann gibt es noch ein paar zusätzliche Dinge, wie eine Nonce, eine Zufallszahl.

Damit Sie nicht jedes Mal, wenn eine Nachricht senden,

diese auf die gleiche Weise verschlüsseln müssen.

Sonst könnte jemand sehen, dass sich die Verschlüsselung wiederholt.

Es gibt es auch einen Authentificator.

Bob kann damit überprüfen, ob das Paket korrekt ist.

Dann erhält Bob sein Paket.

Er sagt: "oh ja, es ist ein Paket von Alice."

Es gibt Alices öffentlichen Schlüssel, wenn Bob den geteilten Schlüssel noch nicht kennt,

dann nimmt Bob sein Geheimnis,

multipliziert es mit dem öffentlichen Schlüssel und erhalt dasselbe b(a(x,y).

Dann führt er die Krytographie mit geheimem Schlüssel durch.

Er verifiziert das eingehende Paket.

Er verifiziert den Authentifikator unter Verwendung der Nonce

und des öffentlichen Schlüssels von Alice.

Er hat zu diesem Zeitpunkt bestätigt, dass das von Alice ist.

Hat Bob noch nie von Alices öffentlichem Schlüssel gehört,

weiß er nicht, wer Alice ist.

Aber er erhält Kontinuität zwischen den unterschiedlichen Nutzungen.

Und fügen Sie dann Zertifikate oder andere öffentliche Schlüsselinfrastruktur hinzu,

wissen Sie tatsächlich, mit wem sie kommunizieren.

Alles worüber wir hier reden,

die ganze public key und secret key Sache, ist so schnell,

dass wir uns es leisten können,

das für jedes einzelne Paket zu machen, das das Internet durchquert.

Gut.

Wir haben Ihnen im Moment noch nicht gesagt, was Sie verwenden sollen.

Hier ist nun ein sicheres Beispiel.

Du bist leise!

Dies ist also ein sicheres Beispiel, das dann nicht beworben werden sollte.

Es ist sein eigenes.

Ähm

Ich kann aber sagen, dass es ein gutes Beispiel ist.

Sollten Sie also eine große Primzahl als Ihre Primzahl nehmen, hat sie 255 Bits.

Es ist eine sehr schöne Primzahl.

Das Berechnungsmodul für diese Primzahl ist schnell.

Sie liegt sehr nahe an einer Zweierpotenz.

Sie führen also diesen Mod aus.

Diese Prozentoperation kann diese Zahl sehr schnell reduzieren.

Dann sieht d ziemlich klein aus.

Hier haben Sie auch eine Edwards -Kurve.

Es gibt eine andere Edwards-Kurve.

Diese nutzt das gleiche d

und fügt dort nur ein Minus ein.

Außerdem fügt man ein Minus vor dem x^2 ein.

Dies ist eine andere Kurve, aber fast die gleiche.

Für jedes (x,y) von zuvor, haben wir nun

die Quadratwurzel von Minus 1 *xy und das gleich y wie zuvor.

Somit ist es nur mit einer kleinen Änderung die erste Kurve.

Außerdem haben wir viele Wege wie man elliptic curves schreibt.

Hier ist eine ganze Liste mit verschiedenen Arten von elliptic curves.

Also das erste was wir Ihnen bereits gezeigt haben,

die Uhr, in der Sie in die Ecken reindrücken, ist eine Edwards-Kurve.

Ich hätte hier gerne einen zusätzlichen Term wie dieses minus 1.

Ich behalte mir hier im Allgemeinen einen Koeffizienten a vor.

Den kann ich dann etwas eingeben.

Äh

Zum Beispiel minus 1.

Das nennt man eine verdrehte Edwards-Kurve.

Es gibt noch ein paar andere Dinge, die man in Lehrbüchern findet.

Diese nennt man Weierstrass-Kurven.

Es gibt auch noch die Montgomery-Kurven.

Diesen kann man sich als Sonderfall von Weierstrass-Kurven vorstellen.

Sie haben eine ähnliche Form wie y^2 = x^3

Hier gibt es einige unterschiedliche Terme.

Wenn Sie eine Kurve haben, können Sie von einem zum anderen und zurück wechseln.

Beispielsweise von einer Montgomery-Kurve zu einer Edward Kurve.

Okay.

Aus historischen Gründen findet man Standards für ECC.

Okay.

Haltet Euch zurück. Das wird schrecklich.

Das sind Weierstrass-Kurven.

Hier ist das Additionsgesetz.

Es zeigt, wie man 2 Punkte auf einer Weierstrasskurve addiert.

Kurze Pause. Zwischenrufe!

Oh, das ist gar nicht so schlecht.

Es gibt 6 verschiedene Fälle.

Wir gehen sie mal durch.

Nein, nein, lasst uns sie nicht durchgehen.

Das ist - äh - wenn Du nur einen Teil davon nimmst.

Dann könnte es so aussehen, als würde es die meiste Zeit funktionieren.

Meistens funktionieren die ersten Formeln.

Solange, bis man etwas Verrücktes wie p + p macht und es dann nicht funktioniert.

Dann gibt es immer mehr Ausnahmefälle.

In einigen dieser Fälle merkt man es zunächst gar nicht.

Un dann versucht man einen Code dafür zu schreiben.

Es geht einfach immer weiter.

Dann versucht man es zu testen und ist sich nicht sicher, ob man alle Tests richtig gemacht hat.

Aber okay.

Das ist das, was man in ECC-Standards findet.

Alles klar.

Schöner als Weierstrass- und Montgomery-Kurven ist eine unserer Lieblingskurven.

Hier sehen Sie die gesamte Arithmetik.

Die Ausnahme ist, dass ich Ihnen nicht gezeigt habe, wie ich den Austausch mit konstanter Zeit durchführen werde.

Hier gibt es ein bedingtes Bit, das x2 mit x3 vertauscht.

Wir können das in konstanter Zeit erledigen.

Ersetzen Sie diese Anweisung durch etwas, das folgendes besagt:

"Es bleibt oder es wird ausgetauscht."

Das ist eine ganze Addition auf Montgomery.

Für jedes Bit machen Sie diese paar Schritte.

Und Sie gehen die 255 Bits durch, die dort angegeben sind.

Dies ist ein weiterer schöner Fall von Arithmetik.

Beachten Sie bitte, dass wir hier nur eine x-Koordinate.

Für die Edwards-Kurve hätten wir x und y.

Es gibt also einige Unterschiede in dem, was wir damit machen.

Wir teilten Ihnen mit, dass wir über Standards sprechen werden.

Woher beziehen Sie Ihre Standards und wie können Sie diese verteidigen?

Sie treten gegen jemanden an, der mit einem Mathematiker antritt.

Mathematiker sind gruselige Menschen.

Sie kennen alle Arten von Angriffen.

Falls Sie diese Angriffe sehen wollen, haben wir am Ende ein paar URLs.

Aber im Grund kennen wir diese Angriffe.

Vereinbaren Sie bestimmte Eigenschaften, die Ihre Kurve haben soll.

Und was diese Standards Ihnen garantieren.

Wenn Sie einen dieser Standards auswählen, ist die Kurve ist für den folgenden Angriff sicher.

Jemand sieht das Ergebnis Ihrer Berechnung.

Er kennt den Basispunkt.

Er kennt Ihren öffentlichen Schlüssel.

Er ist aber nicht in der Lage herauszufinden, was Ihr a oder b war.

Man nennt dies das Problem des elliptischen diskreten Logarithmus.

Und wir haben ganz viele Arbeiten, um die Schwierigkeit zu untersuchen.

Als Mathematiker untersuchen wir, wie schwer es bei einer bestimmten Kurve ist, eine Lösung zu finden.

Um so die elliptische, diskrete Protokoll zu knacken.

Sie möchten beispielsweise, dass Ihr Punkt, wenn Sie ihn mehrmals mit sich selbst addieren,

über eine lange, lange, Zeit verschiedene Punkte ergibt,

bis Sie zum Beispiel wieder zum gleichen Punkt zurück gelangen.

Also z.B. nach l Phasen sind Sie wieder zurück.

Dieses l sollte groß sein, Ich denke z.B. 2 hoch 250 oder etwas anderes großes.

Und ja das sind alle Skripte also ist dies eines der Eigenschaften aber da sind viele weitere.

Okay, lasse wir uns annehmen, dass Sie es implementieren.

Sie nehmen eines der Standards und wieder mal sind sind sie alle ähnlich.

Klar, es gibt Unterschiede im Detail,

aber sie alle beschützen uns.

Und Sie implementieren den Standart...

Und Sie sagen, okay wir sind in Deutschland, wir nehmen die Brainpool Kurven,

da diese in deutschen Pässen verwendet werden.

In Ordnung, also wir nehmen Brainpool P256 t1,

dies gibt Ihnen eine Primzahl, die 256 Bits lang ist.

Außerdem eine Weierstrass-Kurve, y^2 = x^3 - 3x + etwas großes.

Und dann gibt es Ihnen einen Basispunkt (x,y),

und dann schauen Sie darauf und merken:

Oh, alle netten Formeln die vorher genannt wurden, ohne Ausnahmefälle,

wie Edwards und Montgomery, diese Formeln funktionieren nicht bei dieser Kurve.

Wenn Sie eine Kurve haben, die kompatibel mit den Formeln ist,

dann standardisieren Sie diese.

Dann kann jeder Punkt erfolgreich addiert werden und Sie können alle Ausnahmefälle vergessen.

Dafür brauchen Sie eine Kurve die mit den Formeln übereinstimmt,

leider funktioniert diese Kurve nicht mit Edwards und Montgomery,

daher müssen Sie zurück zu den chaotischen Weierstrass Formeln gehen.

Okay, Sie sind sehr vorsichtig und tun genau das was die Formeln aussagen.

Dabei nutzen Sie Testfälle für alles und haben die Weierstrass Konditionen

in allen sechs Fällen richtig implementiert .

Und Sie arbeiten in konstanter Zeit, sodass keine Informationen an Angreifer gegeben werden.

Dann haben sie eine Lösung die schmerzhaft langsam ist,

aber Sie können sich sicher über die Sicherheit sein.

Bis ein Angreifer kommt und sagt:

"Hi, lass uns uns Diffie-Hellmann hier nutzen.

Hier ist mein Punkt."

Okay, ich nehme... Ähm ich glaube ich bin Alice.

Ich habe ein a und nehmen den Punkt, den sie mir gesendet hat a mal.

Dies ist ihr öffentlicher Schlüssel.

Dies ist nicht das originale (x,y),

es ist ein anderes (x', y')

welches sie mir gesendet hat.

Und ich sende zurück mein a(x',y')

Und dann, wenn ich dies korrekt berechnet habe,

dann habe ich nun den Verschlüsselung- Authentifikations-Mechanismus genutzt.

Da mir jemand gesagt hat, dass ich Standard-Mechanismen nutzen soll.

Ich habe Daten verschlüsselt und diese durch das Netzwerk geschickt.

Ich bin im Netzwerk,

ich sehe seine AES-GMC verschlüsselte Nachricht.

Und nun, er weiß nicht,

dass es unabhängig von seinen a,

nicht viele verschiedenen Punkte gibt.

Ich habe ihm keinen Punkt auf der brainpool-Kurve genannt,

nein, ich habe ihm einen Punkt auf einer einfacheren Kurve gerannt.

Zum Beispiel hier, hat es nur fünf.

Die Brainpoolkurve ist viel viel größer,

dies hier ist eine nette Kurve.

Also dieser Punkt hat nur 4999 verschiedene Kopien.

Dies heißt, dass er nicht wirklich ausrechnet, was er denkt.

Ups!

Nun der Grund für diese Möglichkeit ist,

dass im ganzen Chaos der Weierstrass-Kurven, kein a6 existiert.

Also unabhängig davon, ob es das a6 ist als große Zahl für harte Kurven,

oder die 5 die ich eben für leichtere eingesetzt habe.

Es ist egal, der Angreifer nutzt eine der Formeln.

Dann gibt mir das a einen der 4999 verschiedenen Punkte,

woraus ich ein Modulo 4999 entwickeln kann.

Lassen wir uns das wiederholen!

Sie sendet mir einen anderen Punkt.

Hi Dan, hier ist ein anderer Punkt.

Ich nehme das neue (x',y') und berechne es a mal.

Dann sende ich etwas verschlüsseltes zurück mithilfe des geteilten Geheimnisses.

Und nun berechnet sie das gleiche.

Sie hat mir heimlich einen Punkt von einer kleinen Ordnung geschickt,

was ich nie bemerkt habe.

Nun hat sie mein geheimes modulo herausgefunden und nutzt verschiedene Nummern.

Wieder und wieder.

Dies geschieht etwa 20 mal und dann nutzt sie den Chinesischen Restsatz um mein ganzes Geheimnis zu knacken.

Auch wenn nur ein paar Schwachstellen gefunden werden,

ist dies genug um das ganze Sicherheitssystem ernsthaft zu beschädigen.

Wenn dies dann 20 mal passiert, dann habe ich ein echtes Problem.

Nun, was Leute dem häufig entgegnen ist, dass sie sagen:

Oh, ist dir die Fußnote im Standart nicht aufgefallen, welche besagt,

dass wenn du einen Punkt bekommst, du testen sollst, ob dieser auf der Kurve liegt?

Dh. schuld an der Attacke ist die Person, die die Implementierung vornimmt.

Dies ist der Weg, wie wir sichere Systeme erhalten,

wir weisen die Schuld immer dem Implementierer zu.

Das ist super, wenn etwas falsch mit dem System ist,

ist es der Fehler des Implementierers, dass das nicht überprüft wurde.

Applaus

Lassen Sie mich nicht von stir copy anfangen...

Sie sollten die Länge vom String... Sorry, das war falsch

Sie sollten aufpassen, dass dieser Punkt auf der Kurve ist,

Sie sollten aufpassen, dass die richtige Reihenfolge vorliegt.

wegen einer anderen ähnlichen Attacke.

Über die Art und Weise wie Patentgebühren an certicom gezahlt werden...

Okay, ich referiere dazu, wenn Sie einen Telefonanruf bekommen würden.

Wo gesagt wird, dass ein Patent zur Validieren steht...

Statt dem Implementierer die Schuld zuzuweisen, warum sollten wir nicht die Umstände verbessern.

Warum designen wir nicht Kryptographie anders?

Warum designen wir keine anderen Kurven,

sodass es nicht möglich ist bei der Implementierung zu versagen?

Wir wissen wir Implementierer ticken.

Wir sind Implementierer und wissen was wir falsch machen.

Und die Fehler wiederholen sich wieder und wieder.

Also lasst uns uns gegen diese Fehler schützen und ein robustes Design wählen.

Dies heisst für ECC, Sie nehmen das (x,y) was durchs Netzwerk ankommt

und verbieten, dass dieses (x,y) durch das Netzwerk weitergeschickt wird.

Sie haben nur ein x.

Und wenn das y^2 gleich zu etwas ist, dann könnte man, wenn man will,

das kommunizieren.

Sie können ein Bit senden, das angibt ob es plus oder minus die Quadratwurzel

von diesem y ist.

Oder man sendet einfach kein y.

Erinnern Sie sich an die Montgomery Formeln, diese brauchen noch nicht mal y.

So wenn Sie nur ein x senden, dass gibt es deutlich weniger Möglichkeiten für den Angreifer

um Punkte auszusuchen und Sie so zu veralbern wie eben.

Es gibt ein paar mehr Regeln, welche beim Aussuchen der Kurve

und beim Designen des Protokolls beachtet werden können.

Dies heißt, dass Sie als Implementierer leichter arbeiten können.

Der Protokol Designer kann sagen, dass Sie die Skalare a und b,

die Geheimnisse die Sie für Diffie-Hellmann nutzen,

immer multiplizieren sollen mit dem sogenannten Kofaktor der Kurve.

Die ist der Basispunkt der Ordnung l,

es hat l unterschiedliche Vielfache.

Z.B. sind dort vier mal l, oder acht mal l Punkte auf der Kurve,

dann sieht man nur l.

Um für die daraus resultieren Lücke aufzukommen und ausgeklügelteren Attacken zuvorzukommen,

multiplizieren wir die geheimnisse a und b immer mit acht.

Dies beschützt uns komplett vor diesen Attacken

und kann im Protokoll aufgenommen und getestet werden.

Weiterhin kann der Designer der Kurve immer Kurven aussuchen,

die"verdrehungssicher" sind.

Da ist immer ein bisschen Spielraum, wenn jemand einen komprimierten Punkt schickt.

Und diese "Verdrehungssicherheit" sagt etwa aus:

Dieser Spielraum lässt Ihnen die Möglichkeit zwischen verschiedenen Kurven auszusuchen.

Da gibt es die erste Kurve aber auch ihre verwandte Kurve, die "verdrehte Kurve" genannt wird.

Der Designer der Kurve kann sicherstellen, dass beide sicher sind.

Beie haben große Primzahlen, dann ist da ein l und ein verwandtes l

und ein kleiner Kofaktor sowie ein weiterer kleiner Kofaktor.

Wenn der Designer eine der "verdrehungsicheren" Kurven wählt,

bleibt dem Angreifer keine Flexibilität mehr übrig.

Der Angreifer hat dann keine Informationen mehr über Ihr Geheimnis a und b.

So, warum machen wir dies nicht einfach?

Naja, es geschieht in Teilen.

Es gibt bereits eine Bewegung für die nächste Generation von einfachen Standards.

Nächste Generation meint, dass es Kurven geben soll,

bei denen man sich nicht selber verzettelt, wenn man diese

auf die einfachste Weise implementiert.

Das heißt, dass eine einfache Implantation auch eine sichere Implantation sein soll.

Normalerweise, wenn man etwas sicherer gestaltet,

wird es langsamer.

Nun der Bonus in diesem Fall ist, dass es schneller wird.

Bereits in 2010 hat Adam Langley von Google in die TLS mailing list geschrieben:

" Hey Leute, da Kryptographie weiter fortgeschritten ist,

wäre es nicht gut, wenn wir Kurve 25519 als benannte Kurve haben?"

Dann ist nicht viel passiert.

Wir haben daran gearbeitet gute Methoden,

naja zumindest denken wir das,

zum Erstellen von Kurven zu entwicklen.

Naja, dank Snowden im letzten September,

gibt es nun emotionale Reaktionen von Leuten.

Die sagen, da NIST Kurven einen Teil ihrer Vertraulichkeit verloren haben,

und wir denken, vielleicht ist die NSA nicht nur gut,

sollten wir nicht eine neue Bewegung haben?

Zum Glück gibt es viele weitere Leute die sagen:

"Es ist nicht, dass wir paranoid sind, wir wissen nicht ob die NIST Kurven unsicher sind,

aber sie sind garantiert nicht gut zu implementieren."

Wir könnten schneller und sicherer sein.

Dazu gibt es einige Zitate und auch ein Entwurf.

Wenn jemand ein paranoides Sicherheitslevel erreichen will, haben wir hier 41417 Bits.

Ähm, eine SafeCurves Seite und so weiter.

Final, CFRG verändert sich.

Da war ein Typ von der NSA, der ein Co-Leader von CFRG war.

Also CFRG ist eine Kryptogramme Forschungsgruppe von der Internet Engineering Task Force.

Und er NSA co-chair wird weiter dort sein um sie zu unterstützen und zu sagen, wem sie vertrauen sollen.

Nun, ich hatte gehofft dass wir im Guten enden.

Dass wir sagen können, es ist alles gut hier.

Immerhin gibt es einen guten Punkt, Microsoft hat Kurven gewählt...

Wissen Sie, sobald Microsoft in die Diskussion eingreift, ist diese beendet,

Nunja die letzte Seite sollte etwas Nettes sein, aber aktuell geht die Diskussion einfach weiter.

Danke für ihre Aufmerksamkeit!

Applaus

Moderator: "Danke für Euren Vortrag!

Wir haben nur ein paar Minuten für Fragen und Antworten,

daher beeilen sie sich bitte und fragen nur kurze Fragen.

Okay, los gehts!"

Wissen Sie, dass von Attacken oder Schwachstellen in NIST 186-2?

Ja, zum Beispiel, ist NIST P224 nicht verdrehungssicher.

Dies ist das einzig bekannte Problem.

Schauen Sie, wenn Sie sich die Arbeit der ganzen Implentierungen machen

und ganz vorsichtig arbeiten und sich schauen ob ein Punkt auf der Kurve liegt,

und die richtige Ordnung hat, usw.

Wenn Sie eine Menge Arbeit hineinstecken in etwas,

was so langsam und fragil ist und hart zu testen und hart zu implementieren.

Dann können sie etwas sicheres mit den NIST elliptischen Kurven machen.

Ein Schritt in die Zukunft von modernen ECC ist aber etwas zu schaffen,

was schneller und einfacher zu implementieren ist.

Damit sind auch mehr Leute glücklich.

Danke!

Okay, bitte

"Ja, ganz kurze frage, wenn Sie die NSA leiten würden,

könnten Sie Ihren eigenen Standard so beeinflussen, dass Sie ihn knacken könnten?

Und wie würden Sie das machen?"

Naja, die kurze Antwort wäre, dass das Gute bei Standards ist,

dass es viele gibt aus denen man aussuchen kann.

Moderator: "Ist das die Antwort?"

Also die längere Antwort wäre,

dass ich beispielsweise den NC zum französischen Standard (?) wählen könnte.

Es gibt keine Rechtfertigung dafür, welche Kurve ich wähle.

Zuschauer: "Wir kamen Sie auf die Schlüssellänge von 45 Bits,

und woher wissen Sie, dass das sicher ist?

Ist es nur die Abwesenheit von sowas wie Indexcalculus?"

Ja, die Tatsachen, dass IndexCalculus nicht ausgeführt werden kann,

erlaubt ECC mit kleineren Schlüsselgrößen als RSA zu arbeiten.

Und die 256 Bits kommen von Schätzungen,

was die größten Rechnungen sein werden, die in zehn Jahren mit aktueller Technologie

ausgeführt werden können.

Zum Beispiel, mit einem 65 Watt Stromwerk,

würde die größte Rechenleistung nicht ausreichen um 200 Bit elliptic curves zu knacken.

Daher fühlen wir uns mit 256 Bit sicher.

Im Bezug auf die Attacken, die wir kennen, sind die Kurven sicher.

Auf cryp.to (?) können Sie sehen wie viele Operationen notwendig sind um eine 414 Bit Kurve zu knacken.

Wir haben leider keine Zeit mehr,

daher nochmal Danke an die Vortragenden!

Applaus