Post-Quanten-Kryptographie als neuer Standard / Sudo Null IT News

Das Aufkommen eines ausreichend leistungsfähigen Quantencomputers wird herkömmliche kryptografische Werkzeuge irrelevant machen, daher befinden sie sich bereits in der Entwicklung Post-Quanten-Algorithmen für die Kapselung von Schlüsseln und elektronischen Signaturen. Sie basieren auf grundlegend anderen mathematischen Problemen, die auch für Quantenprozessoren rechentechnisch schwierig bleiben werden. Solche Forschungsarbeiten wurden in den letzten Jahren sowohl in Russland als auch im Ausland immer aktiver.

Im Juni übergaben Spezialisten der russischen Firma Kryptonit dem Technischen Komitee für Standardisierung „Cryptographic Information Protection“ (TK26) von Rosstandart ein Paket mit Dokumenten zu dem von ihnen entwickelten Elektronische Post-Quanten-Signatur (ES) “Hagebutte” (siehe mehr darüber. Artikel “Von Stern bis Hagebutte: Wie sich EDS in der Post-Quanten-Ära verändern wird”).

Die Stabilität dieser Regelung basiert auf Problem der Decodierung eines zufälligen linearen Codes, was rechnerisch schwierig ist. Mit anderen Worten, das Signaturschema basierte auf fehlerkorrigierenden Codes. Sie werden häufig in der Telekommunikation verwendet, und ihre Eigenschaften sind gut untersucht.

Das Dokumentenpaket umfasste eine Beschreibung der Schaltung, eine theoretische Begründung für ihre Stabilität, eine Begründung für die Wahl der Parameter sowie eine Modellimplementierung. Jetzt werden die besten Code-Experten Russlands mehrere Monate lang mit der Überprüfung und Diskussion der übertragenen Materialien beschäftigt sein. Wenn die Prüfungen erfolgreich bestanden werden, könnte das Rosehip-Schema der erste Post-Quanten-Kryptographiestandard in Russland werden. Darauf haben wir allen Grund, schließlich wurde der Artikel mit seiner Begründung bereits zur Veröffentlichung in der von Scopus und Web of Science begutachteten Zeitschrift Applied Discrete Mathematics angenommen. Die Veröffentlichung des Artikels ist für September dieses Jahres geplant.

Im Westen begannen ähnliche Arbeiten früher und werden in größerem Umfang durchgeführt. Das American National Institute of Standards and Technology (NIST) hat Anfang Juli 2022 die dritte Stufe des 2016 gestarteten Wettbewerbs für Post-Quantum Key Encapsulation und Electronic Signature Schemes abgeschlossen.

In der ersten Runde wurden 69 Algorithmen eingereicht. Von diesen erreichten nur 3 ES-Schemata das Finale: Zwei davon, CRYSTALS-Dilithium und Falcon, basieren auf ganzzahligen Gittern, und das dritte, SPHINCS+, basiert auf Hash-Funktionen. Signaturschemata für fehlerkorrigierende Codes wurden nicht in das Finale aufgenommen.

Dies liegt höchstwahrscheinlich daran, dass die wissenschaftliche Gemeinschaft zu Beginn des Wettbewerbs (2016) noch keine klare Vorstellung davon hatte, was genau eine elektronische Signatur auf Codes sein sollte. Aus diesem Grund wurden in allen für den Wettbewerb vorgeschlagenen Optionen kritische Fehler gefunden, und die entsprechenden Arbeiten schafften es nicht einmal in die zweite Runde des Wettbewerbs.

„Bei der Arbeit an unserem Signaturschema haben wir uns entschieden, uns nicht auf NIST zu konzentrieren, sondern unseren eigenen Weg zu gehen. Auch bei ihm läuft nicht alles so glatt – die Größe der Signatur wird in Hunderten von Kilobyte gemessen. Aber auf der anderen Seite gibt es keine Fragen zur Sicherheit des Systems – da sind wir uns sicher.“– erklärt Viktoria Vysotskaya, Forscherin im Kryptographielabor der Firma Kryptonit.

Das Hagebuttenschema hat eine Reihe von wesentlichen Vorteilen, die es von anderen unterscheiden. Dazu gehört die geringe Größe des öffentlichen Schlüssels, was den Austausch von Schlüsseln beschleunigt und den Datenverkehr reduziert. Nach diesem Parameter übertrifft “Hagebutte” alle Unterschriften auf den Balken. Am wichtigsten war, dass die Stabilität des Schemas vollständig gerechtfertigt war und der Beweis nur auf der Grundlage jener mathematischen Probleme erstellt wurde, die sich bereits als schwierig erwiesen haben.

Das Gleiche gilt nicht für die elektronischen Signaturen, die es bis ins Finale des NIST-Wettbewerbs geschafft haben. Daher wird eine strenge Begründung für die Resistenz nur in den CRYSTALS-Dilithium- und SPHINCS+-Schemata gegeben. Aber auch sie beruhen auf der Annahme der Komplexität einer Reihe von Problemen, deren Komplexität nicht bewiesen ist. Von allen Finalisten ist der SPHINCS+-Algorithmus am schwierigsten zu implementieren und auch am langsamsten. Dieser Algorithmus wurde jedoch als Backup-Option belassen, da er der einzige ist, der auf einer anderen mathematischen Grundlage aufgebaut ist – basierend auf Hash-Funktionen, nicht auf Gittern.

Zusätzlich zu elektronischen Signaturschemata schaffte es ein wichtiges Kapselungsschema, CRYSTALS-Kyber, ins NIST-Finale. Es bietet einen sicheren Schlüsselkapselungsmechanismus, der auf asymmetrischer Verschlüsselung und Fujisaki-Okamoto-Transformation basiert. Als Vorteile nannte die Jury relativ kleine Verschlüsselungsschlüssel, die einfach auszutauschen sind, sowie eine hohe Geschwindigkeit. Gleichzeitig basiert sein Beweis auf Annahmen über die Komplexität von Problemen, die sich nicht als schwierig erwiesen haben.

Die Abkürzung CRYSTALS steht für „Cryptographic Package for Algebraic Lattices“. Der bestehende Konsens unter Mathematikern besteht darin, dass mit zunehmender Dimension der Gitter die zur Lösung dieser Probleme erforderliche Zeit exponentiell ansteigt. Daher gelten Probleme auf Gittern als resistent gegen Angriffe mit einem klassischen Computer. Die Frage der Resistenz gegen Quantenangriffe bleibt jedoch offen.

Vier weitere wichtige Verkapselungsschemata wurden von den Jurymitgliedern zur weiteren Prüfung überlassen. Darunter basiert ein Schema auf Isogenien (SIKE) und drei auf Fehlerkorrekturcodes (McEliece, BIKE und HQC).

Im Rahmen der Arbeit von TK26 entwickelt die Firma Kryptonit ein inländisches Analogon des Schlüsselkapselungsschemas auf der Grundlage von Fehlerkorrekturcodes. Das Schema wird die vielversprechendsten Lösungen verwenden, deren Analoga in den ausgewählten Schemata des NIST-Wettbewerbs vorgeschlagen werden.

NIST-Führungskräfte erwarten, bis 2025 einen Entwurf für einen Post-Quanten-Kryptographiestandard vorzulegen. Russische Spezialisten sind bereit, es in ungefähr demselben Zeitrahmen und mit einer strengeren Begründung für die Stabilität jedes Algorithmus zu entwickeln.

Wie anerkannt Entwickler von drei der vier Algorithmen, die es ins Finale geschafft haben, Peter Schwabe: „Einige Leute zweifeln an der Arbeit von NIST, weil sie befürchten, dass die Behörde Verschlüsselungsmethoden auf Anweisung der NSA standardisieren und dem amerikanischen Geheimdienst Hintertüren lassen könnte.. Wir wissen mit Sicherheit, dass dies in der Vergangenheit bereits geschehen ist. An der Verifizierung der für den Wettbewerb vorgeschlagenen Algorithmen sind nun jedoch nicht nur NIST-Spezialisten beteiligt, sondern die gesamte globale Kryptografie-Community.“.

Similar Posts

Leave a Reply

Your email address will not be published.