Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Der Wettbewerb für Post-Quanten-Kryptographie ist vorbei!
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 112 Zeilen
- Meine sehr verehrten Damen und Herren, ich darf Sie zu unserer heutigen Verleihung begrüßen für den ersten standardisierten asymmetrischen Postquantenverschlüsselungsalgorithmus.
- Herzlichen Glückwunsch, Crystal Skyver! Mit ihm die drei ersten standardisierten digitalen Signaturverfahren, die postquantensicher sind,
- Crystal's Dilithium. Und man sagt die beiden seinen Verwandt, Falcon und Sphinx.
- Applaus bitte! Postquanten-Kryptographie ist ein eigenes Forschungsfeld und am 5.
- Juli hat das NIST, das National Institute for Standardization and Technology, die ersten vier Postquantenalgorithmen veröffentlicht, die jetzt standardisiert sind.
- Ich habe mir länger überlegt, ob und wie ich das hier verpacke, aber dass ich das Thema vorstellen will, dürfte klar sein.
- Immerhin gibt es eine Krypto-Playlist von mir mit über 100 Videos. Dieses Video hier soll aber für alle sein.
- Jeder kann das verstehen, wie beeindruckend das ist und was wir da eigentlich gerade Historisches gemacht haben.
- Wir werden dementsprechend keine Beweise oder genauen Berechnungen machen. Dazu müsste ich selbst vermutlich erst mal ein bisschen mehr Mathe lernen, sondern wir
- wollen verstehen, was genau eigentlich der Hintergrund ist, dass wir solche Verfahren überhaupt brauchen und wie die jetzt eben zustande kamen.
- Was stimmt denn mit den alten Verfahren nicht und wie funktioniert Krypto eigentlich grundlegend? An der Stelle möchte ich nochmal ganz kurz auf unseren Sponsor eingehen.
- Das ist heute wieder GetInIT. Bei GetInIT könnt ihr sehr schnell und einfach einen Job in, natürlich, der IT-Branche finden.
- Die größten Firmen haben ihre Jobangebote auch bei GetInIT hinterlegt. Das Tolle, du musst nichts weiter tun, als dich auf der Plattform anzumelden und dein
- Profil auszufüllen. Hinterlege dort, welche Skills du hast, zum Beispiel agile Softwareentwicklung oder Kanban
- und was dein Werdegang und deine Ziele sind. Anschließend melden sich die Firmen bei dir.
- Der Prozess ist für dich natürlich vollkommen kostenlos und auch mit viel weniger Arbeit verbunden, als wenn du selbst auf die Suche gehen würdest.
- Fangen wir also kurz mit den Grundlagen an. Wie ihr in der Einleitung gehört habt, geht es nur um asymmetrische Verfahren, die hier
- standardisiert wurden. Es gibt aber grob gesagt vier Arten von Kryptoverfahren, die so regelmäßig zum Einsatz kommen.
- Symmetrische und asymmetrische Verschlüsselung, Hashing und digitale Signaturen. Symmetrische Verschlüsselung, zum Beispiel mit AIS, funktioniert so.
- Wir beide wollen kommunizieren und haben denselben Schlüssel und Verschlüsseln genau damit und wir entschlüsseln auch wieder damit.
- Die Dinger sind tatsächlich ziemlich unknackbar mittlerweile. Früher nicht unbedingt.
- Das einzige was man tun kann, ist nämlich den Schlüssel zu knacken. Und selbst das funktioniert im rein kryptografischen Verfahren eigentlich nicht wirklich.
- Das geht nämlich Jahrhunderte. Hashing ist auch ein symmetrisches Verfahren.
- Ihr könnt es euch so vorstellen. Ich packe was in eine Hash-Funktion rein und raus kommt eine Zeichenkette, die immer
- gleich lang ist. Packe ich dasselbe nochmal rein, kommt auch wieder derselbe Kram raus.
- Ändere ich auch nur einen Buchstaben, habe ich keine Ahnung mehr, was das Ergebnis von meiner Hash-Funktion ist oder sein wird.
- Umkehren lässt sich die Berechnung auch absolut nicht. Asymmetrische Verfahren, also Verschlüsselung und Signaturen, sind aber noch viel spannender,
- wie ich finde. Nun hat jeder Teilnehmer, also du und ich, einen öffentlichen und einen privaten Schlüssel.
- Also wir haben zwei Schlüssel. Jeder kann unsere öffentlichen Schlüssel haben und den privaten, den behalten wir nur
- bei uns. Der muss nicht zum Gesprächspartner.
- Nun nimmst du meinen öffentlichen Schlüssel und verschlüsselst damit was, was nur ich entschlüsseln kann.
- Denn ich bin der Einzige, der den privaten Schlüssel hat. Das heißt Verschlüsseln mit dem öffentlichen Schlüssel, Entschlüsseln mit meinem privaten.
- Signaturen sind da ähnlich. Nur mit dem privaten Schlüssel lassen sich Unterschriften erstellen.
- Das heißt, nur ich kann unterschreiben. Sollte ja auch so sein.
- Jeder, der den öffentlichen Schlüssel hat, also du, kann die Signatur prüfen und damit verifizieren, dass ich das Dokument wirklich unterschrieben habe.
- Es ist also asymmetrisch, weil die Schlüssel, die wir nutzen, andere sind. Du nimmst meinen öffentlichen, ich nehme meinen privaten.
- Ich nehme deinen öffentlichen, du deinen privaten. Und hier kommen die Quantencomputer ins Spiel.
- Jedes asymmetrische Verfahren basiert auf einem harten mathematischen Problem. Das prominenteste Beispiel wahrscheinlich die Faktorisierung von Zahlen.
- Nehmen wir die Zahl 15. 5 mal 3 ist 15.
- Das wissen wir. Ein Computer kann das aber nicht effizient berechnen.
- Er muss jede einzelne Primzahl durchgehen und schauen, ob eine Division ohne Rest möglich ist.
- Das heißt 15 durch 2. Ah shit.
- Ist 7,5. Also nicht drin.
- 15 durch 3. Aha, das ist 5.
- Also haben wir keinen Rest. Also haben wir den ersten Primfaktor gefunden.
- Und so weiter und so fort. 5 kommt dann direkt danach.
- Jetzt, deswegen ist natürlich das Beispiel ziemlich langweilig. Es sind ja nur zwei Primzahlen und dabei haben wir Primzahlen 2 und 3 dabei.
- Also nicht wirklich spannend. Sind aber diese Primzahlen mal mehrere tausend Binärstellen lang, wird das auch für einen
- Menschen echt ziemlich unmöglich. Logisch.
- Quantencomputer haben jetzt allerdings ein Feature. Quantencomputer können das leider effizient machen.
- Das heißt, es gibt einen ausführbaren Algorithmus, Shores Algorithmus, um genau aus solchen riesigen Zahlen die Primfaktoren auszulesen.
- Und das zerstört unsere komplette Annahme. Denn wir sagen ja, wir müssen haben, dass das nicht möglich ist.
- Und Quantencomputer machen es möglich. Denn die Primfaktoren sind bei RSA mein privater Schlüssel.
- Das heißt, ich kenne 3 und 5. Und die große Zahl, also in unserem einfachen Beispiel 15, ist mein öffentlicher Schlüssel.
- Das heißt, du kennst 15, ich kenne 3 und 5. Das heißt, ein Quantencomputer könnte technisch gesehen aus meinem öffentlichen Schlüssel
- meinen privaten errechnen. Und damit können wir natürlich nicht mehr von Vertraulichkeit sprechen.
- Denn man kann ja jetzt alles machen. Deswegen brauchen wir kryptografische Verfahren, die auf Annahmen basieren, die wir auch mit
- Quantencomputern nicht brechen können. Und hier wird extrem viel geforscht.
- Gibt es vielleicht einen Algorithmus, der das Diffie-Hellman-Problem bricht? Gibt es einen, der das Diffie-Hellman-Problem auf elliptischen Kurven bricht?
- Was können Quantenrechner überhaupt? All das ist noch nicht ganz fertig erforscht und nicht ganz klar dementsprechend.
- Bislang konnten für einige neue Verfahren keine Algorithmen gefunden werden, die deren Annahmen zerstören.
- Und das gilt für zum Beispiel fehlerkorrigierende Codes, wie ich das zum Beispiel auch in dem Tutorial zum Mac-Elise-Kryptosystem vorgestellt habe.
- Aber auch für kryptologische Hash-Funktionen, multivariate Polynome und supersinguläre elliptische Kurven.
- Und für Gitter. Und genau darauf hat sich das Team hinter Crystals gestürzt.
- Reden wir ganz kurz über den Wettbewerb. Dieser wurde von der amerikanischen Behörde NIST ausgerufen.
- Das ist genau dasselbe Institut, das auch schon die Standardisierung von AES, dem Standard für symmetrische Verschlüsselung, veranstaltet hat.
- Und auch das war ein historischer Prozess für die Kryptographie. Denn dieser Prozess war sehr lang und sehr gründlich.
- 2016 begann der Call for Papers, das heißt Forscher weltweit wurden aufgerufen, ihre quantensicheren Algorithmen einzureichen.
- Egal ob jetzt digitale Signatur oder Verschlüsselung. 2017 hat die NIST mit dem Standardisierungsprozess begonnen, weil abzusehen war, dass ungefähr
- im Jahr 2030 RSA ein Problem haben wird. Es wurden zu all den mathematischen Problemen, die ich oben genannt habe, Vorschläge eingereicht,
- die die Forscher zu einem Paper formuliert hatten. Darunter zum Beispiel 22 asymmetrische Verschlüsselungsalgorithmen nur für das Gitterproblem.
- Das Wunderschöne an diesem Wettbewerb, was ich hier allerdings noch mal kurz hervorheben möchte, beispielsweise Hela 5 und Round 2 wurden noch in der ersten Runde von den Forschern
- zurückgezogen und mit dem Team hinter Round 5 haben die sich dann zusammengesetzt und gemeinsam daran gearbeitet, weil ihre Ideen so ähnlich waren.
- Sie haben also ihre Köpfe zusammengesteckt und aus drei quasi eins gemacht, weil es eine ähnliche Sache war.
- Ähnliches passierte mit den Code basierten Verfahren Lake, Locker und Uroboros R, die gemeinsam in Rollo flossen.
- Nach der ersten Runde durften dann wieder Kryptografen der ganzen Welt ihren Zerstörungstrieb ausleben.
- Jeder einzelne Algorithmus wurde nun auseinandergenommen und angegriffen. Es wurde nach Lücken gesucht und insgesamt wurden 13 Angriffe veröffentlicht.
- Übrigens auch hier wieder, Forscher-Teams waren sowas von international und nur gemeinsam haben die schlauesten Köpfe der Kryptografie Angriffe an den Schemata gefunden.
- Anschließend wurden einige Algorithmen zurückgezogen, angepasst, verbessert und überdacht und übrig blieb am 30. Januar 2019 eine Sammlung aus 17 Verschlüsselungsalgorithmen und 9 Signaturalgorithmen.
- Die gelten als ziemlich sicher. Jetzt durften also wieder Angriffe gesucht werden, aber es wurden zusätzlich noch weitere
- Kriterien beachtet. Vor allem der Overhead wird betrachtet.
- Das heißt, wie groß sind die Schlüssel eigentlich? Immerhin müssen die ja jedes Mal, wenn man eine Website aufruft, übertragen werden.
- Auch mobil. Ein paar Gigabyte an Schlüsseln wären da ziemlich unglücklich.
- Auch wichtig ist, wie schnell die Berechnungen verlaufen. Klar, heutzutage spielt vieles nicht mehr so eine extreme Rolle wie früher, aber trotzdem
- können Verschlüsselungen sehr viel Zeit in Anspruch nehmen. Jeder, der mal eine Datei in VeraCrypt verschoben hat, der weiß, dass das für ein paar Gigabyte
- durchaus dauert. Laufzeit ist also ebenfalls essentiell.
- Beides war ausschlaggebend dafür, dass Crystals Kaiba den Wettbewerb als einziges asymmetrisches Verfahren gewonnen hat.
- Auch bei den Algorithmen zu digitalen Signaturen gewann Crystals Dilithium aufgrund derselben Kriterien.
- Es sollen jedoch noch mehr Algorithmen als Standard festgehalten werden, denn darum ging es bei dem Wettbewerb.
- Sie sollen überall verfügbar sein und leicht einsetzbar. Das ist quasi das, was den Standard ausmacht.
- Zu den weiteren Algorithmen gehört auch Falcon, der kleinere Signaturen erzeugt, was in manchen Szenarien wichtig sein könnte.
- Und zuletzt wird Sphinx Plus genannt, der zwar langsamer ist und mehr Platz braucht, aber dafür nicht wie die anderen Verfahren auf Gittern basiert, sondern auf Hash-Funktionen.
- Das heißt, wird ein Quantenalgorithmus gefunden, der die Gitterannahme bricht, haben wir einen Fallback-Algorithmus für digitale Signaturen, den jeder auch einfach nutzen kann, ohne auch
- nur irgendwas zu implementieren. Was ihr aber vielleicht gemerkt habt, sind Dilithium, Falcon und Sphinx alles nur Signature-Algorithmen.
- Das heißt, für Verschlüsselungen wurde nur ein einziger Algorithmus standardisiert bislang, also auch nur auf Basis von Gittern.
- Deswegen sollen in einer zusätzlichen vierten Runde noch vier weitere Verschlüsselungsalgorithmen standardisiert werden.
- Beaker, klassischer Mac-Elise, und HQC, die alle auf Codes basieren. Und dann noch Psyche, der auf supersingulären elliptischen Kurven basiert.
- Somit sind wir dann auch also da ganz gut aufgestellt. Die Standards sollen bis 2024 fertig sein, wenn es einen besonderen Durchbruch bei der
- Quantencomputerforschung gibt, sogar noch früher. Jetzt wäre die nächste berechtigte Frage, die man haben kann, warum wurde eigentlich
- kein neuer symmetrischer Verschlüsselungsalgorithmus gewählt? Machen wir alles in Zukunft asymmetrisch?
- Und nein, das wird nicht der Fall sein. Tatsächlich hat AIS aber einfach immer noch keinen Angriff gegen sich.
- Es gibt einen einzigen Algorithmus für Quantencomputer, der AIS ein kleines bisschen wehtut. Der Grover-Algorithmus.
- Der Grover-Algorithmus schafft es, die AIS-Schlüssellänge in einem Angriff zu halbieren. Mehr geht aber nach der aktuellen Forschung noch immer nicht.
- Deswegen passiert da einfach folgendes, AIS-Schlüssellänge wird verdoppelt. Selbst mit 256 Bits, die wir heute schon als Standard nutzen, ist also immer noch alles
- sehr gut gesichert. Lediglich die 128 Bit werden mit dem Grover-Algorithmus ein bisschen eng, um noch sicher zu sein.
- Da muss also kaum was passieren, außer dass wir halt den stärkeren Algorithmus benutzen, vielleicht noch einen stärkeren dann als Standard etablieren.
- Und damit sind wir dann auch in der Lage weiterhin Chats, Nachrichten, Mails, Webtraffic und noch vieles mehr sicher zu verschlüsseln.
- Völlig egal, ob es eines Tages Quantencomputer mit 50 Qubits oder 5 Millionen Qubits gibt. Wenn ihr euch für das Thema interessiert, zum McElies-Algorithmus, der ja auch in Zukunft
- noch standardisiert werden soll, hab ich tatsächlich ein Tutorial schon gemacht. Gönnt es euch gerne, ich verlinke es euch in der Endcard.
- Grundsätzlich empfehle ich euch aber erstmal meine Kryptografie-Playlist. Viel Spaß damit!
- Und vor allem auch natürlich danke an die Forscher, die sich da so reingehängt haben. Ohne euch hätten wir wirklich ein Problem.
- Bis zum nächsten Mal. Ciao!
Zum Nachlesen
Post-Quanten-KryptographiePost-Quanten-Kryptographie (englisch post-quantum cryptography, PQC) bezeichnet ein Teilgebiet der Kryptographie, das sich mit kryptographischen Primitiven …
Asymmetrisches KryptosystemAsymmetrisches Kryptosystem (oder Public-Key-Kryptosystem) ist ein Public-Key-Verfahren, das zur Public-Key-Authentifizierung und für digitale Signaturen …
KryptographieSymmetrische Verfahren verwenden wie klassische kryptographische Verfahren einen geheimen Schlüssel pro Kommunikationsbeziehung und für alle Operationen (z. B.
RSA-KryptosystemRSA (Rivest–Shamir–Adleman) ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet …