Einleitung
1994 wurde der Informatiker Peter Shor entdeckt dass, wenn Quantencomputer jemals erfunden würden, sie einen Großteil der Infrastruktur dezimieren würden, die zum Schutz von online geteilten Informationen verwendet wird. Diese beängstigende Möglichkeit hat Forscher dazu veranlasst, neue „Post-Quanten“-Verschlüsselungsschemata zu entwickeln, um so viele Informationen wie möglich davor zu bewahren, in die Hände von Quantenhackern zu fallen.
Anfang dieses Jahres, das National Institute of Standards and Technology enthüllt vier Finalisten bei der Suche nach einem Post-Quanten-Kryptographiestandard. Drei von ihnen verwenden „Gitter-Kryptografie“ – ein Schema, das von Gittern inspiriert ist, regelmäßigen Anordnungen von Punkten im Raum.
Gitterkryptographie und andere Post-Quanten-Möglichkeiten unterscheiden sich in entscheidender Weise von aktuellen Standards. Aber sie alle beruhen auf mathematischer Asymmetrie. Die Sicherheit vieler aktueller Kryptografiesysteme basiert auf Multiplikation und Faktorisierung: Jeder Computer kann schnell zwei Zahlen multiplizieren, aber es könnte Jahrhunderte dauern, eine kryptografisch große Zahl in ihre Hauptbestandteile zu zerlegen. Diese Asymmetrie macht Geheimnisse leicht zu kodieren, aber schwer zu entschlüsseln.
Was Shor in seinem Algorithmus von 1994 enthüllte, war, dass eine Eigenart des Faktorisierens ihn anfällig für Angriffe durch Quantencomputer macht. „Es ist eine sehr spezifische, besondere Sache, die der Quantencomputer leisten kann“, sagte er Katharina Stange, Mathematiker an der University of Colorado, Boulder. Nach Shor hatten Kryptografen also eine neue Aufgabe: Finden Sie eine neue Reihe mathematischer Operationen, die einfach durchzuführen, aber fast unmöglich rückgängig zu machen sind.
Gitterkryptographie ist einer der bisher erfolgreichsten Versuche. Ursprünglich in den 1990er Jahren entwickelt, beruht es auf der Schwierigkeit, Punktsummen zurückzuentwickeln.
Hier ist eine Möglichkeit, die Gitterkryptographie zu beschreiben: Stellen Sie sich vor, Ihr Freund hat ein Gitter, das nur aus einer Reihe von Punkten in einem regelmäßigen, sich wiederholenden Muster auf der ganzen Ebene besteht. Ihr Freund möchte, dass Sie 10 dieser Punkte nennen. Aber er ist schwierig und wird nicht das ganze Gitter zeichnen. Stattdessen listet er nur zwei Punkte auf – den ersten mit einem x-Wert von 101 und a y-Wert von 19, der andere mit Koordinaten [235, 44].
Glücklicherweise ist es einfach, neue Punkte auf einem Gitter zu finden, denn wenn Sie zwei beliebige Punkte auf einem Gitter addieren und subtrahieren, erhalten Sie einen dritten Punkt im selben Gitter. Sie müssen also nur die Punkte addieren, die Ihr Freund Ihnen gegeben hat, oder sie mit ganzen Zahlen multiplizieren und dann addieren, oder eine Kombination aus beidem. Tun Sie dies auf acht verschiedene Arten, und Sie werden in der Lage sein, die Frage Ihres Freundes zu beantworten.
Aber dein Freund ist immer noch nicht zufrieden. Er gibt Ihnen die gleichen zwei Startpunkte und fragt Sie dann, ob der Punkt [2, 1] auf demselben Gitter liegt. Um diese Frage richtig zu beantworten, müssen Sie die Kombination aus [101, 19] und [235, 44] finden, die [2, 1] ergibt. Dieses Problem ist viel schwieriger als das erste, und am Ende werden Sie wahrscheinlich nur raten und prüfen müssen, um die Antwort zu erhalten.* Diese Asymmetrie liegt der Gitterkryptographie zugrunde.
Wenn Sie tatsächlich Gitterkryptografie verwenden möchten, um Informationen auszutauschen, würden Sie Folgendes tun. Stellen Sie sich vor, ein Freund (ein netterer!) möchte Ihnen eine sichere Nachricht senden. Sie beginnen mit einem quadratischen Zahlenraster. Angenommen, es hat zwei Zeilen und zwei Spalten und sieht so aus:
Jetzt kommen Sie mit einem privaten „Schlüssel“, den nur Sie kennen. Nehmen wir in diesem Beispiel an, Ihr privater Schlüssel besteht nur aus zwei Geheimzahlen: 3 und −2. Du multiplizierst die Zahlen in der ersten Spalte mit 3 und die in der zweiten Spalte mit −2. Addieren Sie die Ergebnisse in jeder Zeile, um eine dritte Spalte mit zwei Einträgen zu erhalten.
Kleben Sie die neue Spalte auf das Ende Ihres Rasters. Dieses neue dreispaltige Raster ist Ihr öffentlicher Schlüssel. Teilen Sie es frei!
(Ein reales Szenario wird etwas komplizierter sein. Um Hacker davon abzuhalten, Ihren privaten Schlüssel zu entschlüsseln, müssen Sie Ihrer letzten Spalte ein wenig zufälliges Rauschen hinzufügen. Aber hier werden wir diesen Schritt der Einfachheit halber ignorieren. )
Jetzt verwendet Ihr Freund den öffentlichen Schlüssel, um Ihnen eine Nachricht zu senden. Sie denkt sich selbst zwei geheime Zahlen aus: 2 und 0. Sie multipliziert die Zahlen in der ersten Reihe mit 2 und die in der zweiten Reihe mit 0. Dann addiert sie die Ergebnisse in jeder Spalte, um eine dritte Reihe zu erhalten.
Sie hängt nun die neue Reihe am unteren Rand des Rasters an und schickt sie Ihnen zurück. (Auch hier müsste sie in einem echten System etwas Lärm zu ihrer Reihe hinzufügen.)
Jetzt lesen Sie die Nachricht. Dazu prüfst du, ob die letzte Zeile deines Freundes richtig ist. Wenden Sie Ihren eigenen privaten Schlüssel auf die ersten beiden Einträge ihrer Zeile an. Das Ergebnis sollte mit dem letzten Eintrag übereinstimmen.
Ihr Freund kann Ihnen auch eine Zeile mit einer falschen Zahl in der letzten Spalte senden. Sie weiß, dass diese Zahl nicht mit Ihren Berechnungen übereinstimmt.
Wenn Ihr Freund eine Zeile sendet, in der die letzte Zahl richtig ist, interpretieren Sie dies als 0. Wenn sie eine Zeile sendet, in der die Zahl falsch ist, interpretieren Sie sie als 1. Die Zeile codiert daher eine Einzahl bit: entweder 0 oder 1.
Beachten Sie, dass ein externer Angreifer weder auf Ihren privaten Schlüssel noch auf den Ihres Freundes Zugriff hat. Ohne diese hat der Angreifer keine Ahnung, ob die endgültige Zahl richtig ist oder nicht.
In der Praxis möchten Sie Nachrichten senden, die länger als ein Bit sind. Leute, die beispielsweise eine 100-Bit-Nachricht erhalten möchten, generieren 100 neue Spalten statt nur einer. Dann erstellt der Absender der Nachricht eine einzelne neue Zeile und modifiziert die letzten 100 Einträge, um entweder eine 0 oder eine 1 für jeden Eintrag zu codieren.
Wenn die Gitterkryptographie tatsächlich implementiert wird, wird sie unzählige Nuancen aufweisen, die in diesem Szenario nicht abgedeckt sind. Soll die Nachricht zum Beispiel wirklich vor neugierigen Blicken geschützt sein, muss die Matrix unvorstellbar viele Einträge haben, was das Ganze so unhandlich macht, dass es sich nicht lohnt, es zu verwenden. Um dies zu umgehen, verwenden Forscher Matrizen mit nützlichen Symmetrien, die die Anzahl der Parameter reduzieren können. Darüber hinaus gibt es eine ganze Reihe von Optimierungen, die auf das Problem selbst angewendet werden können, auf die Art und Weise, wie Fehler integriert werden, und mehr.
Natürlich ist es immer möglich, dass jemand einen fatalen Fehler in der Gitterkryptografie findet, so wie Shor es beim Factoring getan hat. Es gibt keine Garantie dafür, dass ein bestimmtes kryptografisches Schema angesichts eines möglichen Angriffs funktioniert. Kryptografie funktioniert, bis sie geknackt wird. Tatsächlich früher in diesem Sommer Ein vielversprechendes Post-Quanten-Kryptographie-Schema wurde geknackt nicht mit einem Quantencomputer, sondern mit einem gewöhnlichen Laptop. Für Stange schafft das gesamte Projekt ein unangenehmes Paradoxon: „Was ich an der Kryptografie so erstaunlich finde, ist, dass wir diese Infrastruktur für die menschliche Rasse in der festen Überzeugung aufgebaut haben, dass unsere Fähigkeiten als Menschen begrenzt sind“, sagte sie. "Es ist so rückständig."
*: Wenn Sie neugierig sind, lautet die Antwort: 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [zurück zum Artikel]
