Lange galten Primzahlen als zwar skurrile Sonderlinge der Mathematik, aber auch als weitgehend nutzlos. Denn außer für faszinierende Zahlenspiele und Muster schienen sie wenig praktische Anwendung zu haben. Doch mit dem Beginn des Computerzeitalters hat sich das radikal geändert. Denn Primzahlen bilden heute die Basis einer ganz entscheidenden Anwendung im Datenaustausch: der Verschlüsselung von Daten.
Ob wir mit der Kreditkarte einkaufen, eine E-Mail oder Message schicken oder auf andere Weise digitale Daten austauschen – fast immer werden unsere Daten dabei verschlüsselt. In gängigen Verfahren wie der Public-Key-Verschlüsselung dienen dabei extrem große Zahlen als Schlüssel.
Primzahlen als Schlüssel
Grob vereinfacht erklärt: Wenn wir beispielsweise mit einer Kreditkarte online bezahlen, wird diese Zahl – der öffentliche Schlüssel – von unserem Computer genutzt, um unsere Kreditkartennummer und Daten zu verschlüsseln. Das Ergebnis wird über das Internet geschickt. Zum Entschlüsseln wird nicht die gleiche Zahl genutzt – denn das wäre zu unsicher. Stattdessen verwenden die Verfahren einen anderen, geheimen Schlüssel – und dieser besteht aus zwei Primzahlen, die multipliziert die Schlüsselzahl ergeben.
Der Clou daran: Zwar lassen sich große Zahlen durch Primzahlmultiplikation leicht erzeugen, sie aber in ihre Primzahlfaktoren zu zerlegen, ist enorm rechenaufwändig. Im Jahr 2009 benötige ein Netzwerk aus mehreren hundert Computern umgerechnet 2.000 Rechenjahre, um einen Schlüssel mit 232 Stellen zu faktorisieren. Inzwischen werden für die RSA-Kryptoverfahren Zahlen mit 309 Stellen genutzt.
Gefahr durch Quantencomputer?
Doch die Ära der Quantencomputer könnte der Sicherheit der Primzahl-Schlüssel ein Ende machen. Denn bereits 1994 hat der USA-Mathematiker und Informatiker Peter Shor einen Algorithmus für Quantencomputer entwickelt, der die Primfaktoren sehr viel rascher finden könnte. Weil ein Quantencomputer durch die Überlagerung von Zuständen stärker parallel rechnet als klassische Computer, kann er solche Aufgaben schneller bewältigen.
Noch allerdings sind die Quantencomputer nicht komplex genug, um den Shor-Algorithmus auch für große Zahlen umzusetzen. In einem Experiment ist es Wiener Forschern im Jahr 2016 aber schon gelungen, ihn auf einem System aus fünf Quantenbits laufen zu lassen – vier davon rechneten, das fünfte diente als Zwischenspeicher für die Ergebnisse. Mit Hilfe dieses Ansatzes haben sie die Zahl 15 in ihre Primzahl-Faktoren zerlegt.
Natürlich ist dies noch keine Bedrohung für die im Vergleich riesigen Zahlenschlüssel der Kryptografie-Verfahren. Aber das Experiment hat bewiesen, dass der Shor-Algorithmus auf Quantencomputern umsetzbar ist. Und die Entwicklung der Quantensysteme schreitet rapide voran. Es kann daher gut sein, dass die Tage der Primzahl-basierten Verschlüsselungen gezählt sind.
Nadja Podbregar
Stand: 15.06.2018
