PMG2224 1/Einführung/Camillo

Wiki-Quelltext dieser Seite.

= Quantensichere Algorithmen =

== Einführung ==

=== Einwegfunktionen ===

Moderne Verschlüsselungsverfahren basieren häufig auf Einwegfunktionen. Das sind Funktionen, die sich einfach berechnen, jedoch schwer umkehren lassen. $17 \cdot 41 = 697$ lässt sich zum Beispiel relativ einfach mit schriftlicher Multiplikation berechnen, während sich die Bestimmung der Faktoren von $697$ als schwierig gestaltet. Die Funktion wird also zur Verschlüsselung der Information verwendet, die Umkehrung entspräche der Entschlüsselung. Der Empfänger verfügt dabei über eine sogenannte Falltür, eine Zusatzinformation (ein Schlüssel) der die Schwierigkeit der Umkehrung erheblich vermindert. Im Beispiel könnte er zum Beispiel den Faktor $17$ kennen und kann nun mit schriftlicher Division den zweiten Faktor ermitteln.

=== Schwächen der üblichen Verschlüsselungsverfahren ===

Übliche Verfahren wie RSA oder Verfahren mit eliptischen Kurven besitzen keine echten Einwegfunktionen. Sie vertrauen nur darauf, dass bis zum jetzigen Zeitpunkt keine effiziente Handlungsvorschrift existiert, um ihre Funktionen umzukehren. Es gibt noch keine bewiesen sichere Einwegfunktion.

== Bedrohung durch Quantencomputer ==

Quantencomputer arbeiten statt mit Bits, die die Werte 0 und 1 annehmen können mit Qubits. Diese können mehrere Zustände gleichzeitig annehmen und sich verschränken und damit mehrere Berechnungen simultan ausführen. Das erlaubt neue Arten von Algorithmen, die schwere Probleme effizient lösen können. Ein Beispiel ist der Shor-Algorithmus, der mit geringem Aufwand Primfaktoren einer Zahl findet. Diese Algorithmen wären in der Lage, Verfahren mit unechten Einwegfunktion anzugreifen. 

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 ein Verfahren mit wirklicher Einwegfunktion gefunden werden.


== Neue Lösungsansätze ==

Um die Suche nach neuen Verschlüsselungsalgorithmen zu beschleunigen, organisierte die NIST 2016 einen Wettbewerb für sichere Algorithmen, die als Ersatz für die gängigen Verfahren infrage kommen. In einem langen Prüfungsprozess haben sich folgende Verfahren herauskristallisiert.

=== Codebasierte Kryptografie ===

Die codebasierte Kryptografie verwendet Methoden aus der Fehlerkorrektur, die zum Beispiel bei der Rekonstruktion von Daten auf einer Festplatte zum Einsatz kommen. Der Nachricht wird mit Fehlern versehen, die schwer zu korrigieren sind, wenn nicht weitere Informationen über die Art der Fehler vorliegen (die Falltür des Systems). Codebasierte Verfahren gehören erwiesenermaßen zu einer höheren Komplexitätsklasse, sind also schwieriger zu knacken. Sie sind auch im Gegensatz zu anderen präsentierten Verfahren relativ schnell ausführbar, benötigen jedoch viel Speicher und haben einen großen Datenaufwand (z.B. Schlüssel mit Größen im Megabytebereich).