Quantensichere Algorithmen

Einführung

RSA-Verschlüsselung

RSA ist ein Public-Key-Verschlüsselungsverfahren, das in moderner Netzwerkkommunikation vor allem zum Austausch symmetrischer Schlüssel zum Einsatz kommt. Das Verfahren arbeitet mit Primzahlen. Es beruht auf der Erkenntnis, dass es einfach ist, zwei Primzahlen zu multiplizieren, jedoch sehr rechenaufwändig, das Produkt ohne Informationen über die Primfaktoren in diese zu zerlegen.

Diese Berechnung ist z.B. mit schriftlicher Mulitplikation einfach durchführbar. Für die sogenannte Faktorisierung, die Ermittlung der Primfaktoren 17 und 41 aus 697 existiert jedoch kein effizienter klassischer Algorithmus.

Ist jedoch einer der Faktoren bekannt, so ist der zweite sofort effizient ermittelbar.

Bedrohung durch Quantencomputer

Anders als klassische Algorithmen kann der Shor-Algorithmus - ein Quantenalgorithmus - Zahlen mit geringem Aufwand faktorisieren. Quantencomputer arbeiten statt mit Bits, die die Werte 0 und 1 annehmen können mit Qubits. Diese können Zwischenzustände annehmen und sich verschränken. Der Shoralgorithmus nutzt diesen Umstand aus, indem er den Zustand des Qubitsystems misst und die Messung in eine Funktion einfügt. Das Ergebnis dieser Funktion hängt mit einer großen Wahrscheinlichkeit mit einem Primteiler der Ausgangszahl zusammen.

Im Moment existiert noch kein Quantencomputer, der groß genug ist, um den Shor-Algorithmus auszuführen, die US-amerikanische Behörde für Standardisierung (NIST) schätzt jedoch, dass das in 30 bis 50 Jahren der Fall sein könnte. Ab diesem Zeitpunkt ist das RSA-Verfahren anfällig für Angriffe und es muss eine Alternative gefunden werden. Doch Hacker können schon jetzt verschlüsselte Informationen abgreifen und diese später entschlüsseln. Deshalb muss so schnell wie möglich eine Lösung gefunden werden.