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. Dabei werden Effekte von Quantencomputern genutzt, die den einzelnen Bits erlauben, nicht nur 0 oder 1 anzuzeigen, sondern ebenso Zwischenzustände einzunehmen. Im Moment existiert noch kein Quantencomputer, der groß genug ist, um den Shor-Algorithmus auszuführen, die US-amerikanische Behörde für Informationssicherheit 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. Damit eine solche auch getestet und für die Nutzung umgesetzt werden kann, ist ein großer Vorlauf notwendig, deshalb muss schon jetzt nach neuen Verfahren gesucht werden.