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.

(laughter)

Also das hier ist über Crypto und ein paar Elliptic curves, daher hoffen wir 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 es noch verständlich ist

Also warum Cryptography?

Wenn Sie Crypto im Internet verwenden oder für elektronische Zahlungen

Dann sehen sie zum Beispiel ein SSL Zertifikat in welchem Crypto verwendet wird.

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

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

Wenn Sie also 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 Crypto, der secret key cryptography.

Das ist wirkliche eine coole Sache, es ist viel viel schneller als alles worüber wir Ihnen heute erzählen.

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

dass sie bereits einen Schlüsselaustausch durchgeführt haben

Wir werden Ihnen zeigen wie man den Schlüsselaustausch

und anschließend die symmetrische Crypto ausführt

Das wir vielleicht nächstes Jahr passieren

Okay, also warum sollte man in public key crypto ECC nutzen

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

Die einfache Antwort dafür ist eine Angriffstrategie namens Indexcalculus.

Nun dies ist, wenn Sie die RSA Schlüssel von jemand indem faktorisieren wollen,

wenn Sie von jemanden den ursprünglichen nicht-elliptischen Diffie-Hellman von jemanden knacken möchten,

dann nutzten Sie Indexculculus

Dies sind ausgefallene Mathematik sowie die damit einhergehenden Algorithmen.

Im Endeffekt wird es immer schneller und schneller,

sodass wir am Ende gar nicht wissen, wie schnell es einmal sein wird

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

1975 wurde einer der ersten Indexcalculus Algorithmen, CFRAC entwickelt,

zum Faktorisieren von großen Zahlen.

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

Sie haben letztes Jahr von der Cryptoapocalypse gehört.

Und dies 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 Indexcalculus

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 200 bis 120 Operation brauchen,

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

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

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

von 120 Operations zu 80.

Und es ist nicht nur eine Verringerung um 40 des Exponent, 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

Also Faktorisierung oder Diffie-Hellman würde 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 Indexcalculus Attacke auf die Methode der elliptic curver jemand klappen würde.

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

welche Faktorisierung und Diffie-Hellman so geschwächt haben."

Um in elliptic curve cryptography sanft einzusteigen, ist hier die clock cryptograpy

Nun, hier ist Bild von der Uhr

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

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

Also ein rundes Ding.

Wissen Sie, wenn Sie denken dass eine Uhr Ihnen Ziffern nebeneinander zeigt, 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 Ihnen später im Vortrag zeigen,

beinhalten nicht die Uhr.

Die Uhr 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 ist das elliptic curve cryptography.

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

sind hier ein paar Punkte auf der Uhr.

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

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

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

Ich weiß, dass die eins 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 die 6 Uhr Marke.

Dort haben Sie Frühstück oder Lunch.

Das ist die 3 Uhr Marke, da ist die 9 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,

Das hier ist eine Art des Umdrehens der Koordinaten

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 klar,

welche Zeit Marke 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 er Uhr.

Okay, also Sie können herausfinden, wo der 3/5, 4/5 Punkt ist.

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 sind das ein paar Punkte p1, p2 und p3 auf der Uhr

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 also den Punkt auf der Uhr machen wollen, 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.

Mit diesen Sinus- und Cosinus-Formeln überreden wir die Leute, sich der Krypta-Seite zuzuwenden.

Wir sagen ihnen: "Sie können die ganze nichtdiskrete Mathematik vergessen, die wir mögen."

"Wir sind die diskreten Typen, also wird es keine geben."

Sinus und Cosinus wandern so gut herum, dass wir sie loswerden.

Wir wollen keinen Sinus-Cosinus haben.

Eigentlich würden wir gerne mit normalen Taktzahlen arbeiten, was ich mit Sinus 1, Cosinus 2 und so weiter habe.

Das sind einfach so 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.

Jeder Cosinus von Alpha wird durch das entsprechende y ersetzt.

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

Keine trigonometrische Additionsformel, also Addition auf der Uhr.

Jemand gibt Ihnen 2 Punkte x1 y1 und x2 y2.

Sie müssen nur die x-Spalte der ersten nehmen, den Punkt der y-Koordinate des zweiten und diese multiplizieren.

Nehmen Sie die Y-Koordinate des ersten Punkts x an der Ecke des zweiten Punkts und multiplizieren Sie diese und addieren Sie diese dann.

Wir können einfach vergessen, woher es kommt.

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 Uhrausgabe, die wir immer noch nicht haben.

Lassen Sie den Computer hier mithelfen, damit das Rechnen etwas mühsamer wird.

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, dann werde ich 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 das die Quadratwurzel von 3/4 multipliziert mit der minus Quadratwurzel von 3/4

Das ist minus 3/4

Dann klingt das y1 x2 wie 1/2 mal 1/2, 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 abs 4/5 nehmen und es zu sich selbst addieren.

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

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

Sie erhalten einfach eine Antwort aus den 24/25 und 7/25

Und Sie können immer mehr Kopien davon hinzufügen.

Zeigen Sie auf sich selbst.

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 Ziffern.

Im Nenner gibt es 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, was es ist.

12 Uhr mit 0,1

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

12 Uhr plus 5 Uhr ist 5 Uhr

12 Uhr plus irgendein Wert ergibt irgendein Wert.

Das ist sofort ersichtlich aus der Formel zur Addition von 2 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, wo es die gleiche Höhe und die gleich Y-Koordinate hat, aber die X-Koordinate negativ ist.

Das ergibt zusammen 12 Uhr.

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

Versuchen wir mal folgendes:

Angenommen, sie setzen x2 - x1 und y2y1 in die Formel ein.

Sie sehen die erste Coolness.

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

Dann ist x2=-y1. Die ergibt im Endeffekt null.

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

Nächster Teil: y1y2 = y1 mal y1 minus x1x2

minus x1 mal minus x1 = x1 im Quadrat

y1 im Quadrat + x1 im Quadrat = 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 Satz von Elementen.

Wir machen Takte über Suchfelder.

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

Das ist also, wofür diese F7 steht.

Es sollen auch diese Zahlen hinzugefügt werden, die ich multiplizieren möchte.

Ich multipliziere 2 und 5 und 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.

Ich werde i reduzieren und das Restmodul 7 annehmen.

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 oder 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 Null-Tilde verwendet. 6, wir möchten die Symmetrie beibehalten.

Von -3 bis + 3.

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

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

Also ist dies der Uhrpunkt.

Es ist das Suchfeld zwei zwei

Okay.

Wir verwenden die Uhradditionsfunktion.

Wir zeigen eine Funktion, um Punkte hinzuzufügen, die Uhr über den Walzen.

Es ist hilfreich, Plus und Minus und Zeiten schreiben zu können ,

die diese Reduzierung automatisch durchführen, Mod 7.

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

Diese sind getrennt.

Das ist das Übliche für Plus-Minus und die Zeiten für Ganzzahlen.

Um dies einzurichten gehen Sie bitte wie folgt vor:

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

Hierbei handelt es sich um die in der Ganzzahl 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

Beispielsweise der Tatsache, 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 subtrahiere ich eine 7, subtrahiere wieder 7 und man erhält eine 6.

Man kann also in diese F7 jede ganze Zahl eingeben, die man möchte.

Nehmen Sie sich diesen Integer-Mod7.

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

Beispielsweise können Sie einen Gleichheitstest durchführen.

Pythons Standardgleichheit ist ziemlich dumm.

Sagen Sie ihm, dass das was ich eigentlich tun möchte folgendes ist:

Ich möchte diese Punkt-Int-Teile vergleichen, die der F7-Wert hat.

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 Multiplikation.

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

Sie nehmen zwei a und b, die hereinkommen.

Dann nehmen Sie eine Ganzzahl innerhalb einer Ganzzahl 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 das ist C.

Ich gebe Dir negative Zahlen.

Prozent in Python gibt Dir immer 0 bis 6.

Oder 0 bis zu jeder Zahl, die Du genommen hast.

Ähm

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

Okay.

Jetzt haben wir eine kleine Uhr gesehen.

Her könnte ich einfach alle Elemente zeichnen, wo es durch 49 Elemente laufen könnte.

Alles was Dan mit dem Python-Setup gezeigt hat, kann ich durch 7 oder 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 modernen Elemente 1.000.003 einfügen.

Ich nehme also meine Punkte und mache x1 y2 y1 x1 x2 und so weiter.

Dann komme ich zum 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 1000 sind, mehrere Millionen 3.

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

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

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

Ja, das ist 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 Du das siehst, denkst Du natürlich: Warte mal.

Muss ich tatsächlich alle diese 5 Ergänzungen machen?

Nein.

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

Da ist dreimal ein Punkt und addiert dann p3 plus p3

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

Für mich eben diese beiden Dinge das Gleiche.

Möchte ich das also professioneller machen, zeige ich, wie ich den Skala definieren würde.

Okay

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

Sie haben einen beliebigen Taktpunkt p in einem beliebigen Skalar.

Jede ganze Zahl n, die Sie möchten .

Sie nehmen das n, wenn es 0 ist.

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

Wenn es 1 ist, geben Sie den Punkt p einmal zurück.

p ist p

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

Schrägstrich Schrägstrich ist der richtige Weg, um eine durch 2 geteilte ganze Zahl nehmen.

Und den Rest wegzuwerfen, so dass n Schrägstrich 2 ist, wenn n gerade ist.

Das ist genau, wenn n über 2 ist und dies rekursiv n über 2 mal p berechnet.

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

Dann tastet aus q Komma q heraus, um das n über 2 mal p zu verdoppeln.

Man erhält np, wenn n ungerade ist.

Dann ist das n über 2 gut.

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 Taktadditionen erforderlich.

Dabei 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.

Wissen Sie, 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 durch einiges tuckern 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.

Wenn 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 Kryptographische verwenden möchten.

Jemand möchte die Taktkryptographie standardisieren .

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

Große Zahl, aber 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, ass 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 Warp schicken.

"Ich bin Bob".

Dann wählt Alice aus.

Mein Geheimnis ist 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 l von a.

Anschließend sende ich das an n.

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-Komma-y.

Ich sende mein b-mal x-Komma-y über Dallas 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 die Basis am neuen Punkt, den er mir gerade gesendet hat.

Dann setze ich diesen Punkt in die Skarlarmultiplikation ein.

Ich mache die gleichen Schritte genauso gut am Punkt zu sich selbst.

Und manchmal am 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.

Dies 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 Komma y.

Ich nehme mein geheimes b und multipliziere es mit dem a mal x Komma y.

Nun bekomme ich mein b mal a mal den Punkt x Komma 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 a gemeinsames Geheimnis zum Verschlüsseln von Daten.

In Ordnung.

Wir haben auch ein Bild davon.

Nur 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.

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!

Zweitens: 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 ziemlich gut.

Sollte es um die Sicherheit gehen, ist es das Gleiche wir "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 Bleichenbahcer-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.

Das haben sie gemacht, 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 alle möglichen Informationen zugreifen, die Alice und Bob brauchen.