Für wen soll die Seite passen? Alles hier ist kostenlos.

Kostenlos für Ihren Unterricht: Arbeitsblätter, Aufgaben, Texte und Grafiken ohne Rückfrage kopieren, anpassen und an die Klasse weitergeben (Bedingungen).

Im Unterricht ohne Werbung: Unterrichtsansicht Mehr für Lehrkräfte

Magazin · Wissen

Primzahlen im Handy: wie Verschlüsselung funktioniert

Jede verschlüsselte Nachricht und jede Überweisung im Netz stützt sich auf Mathematik, die teils über 2000 Jahre alt ist. Wie zwei Primzahlen ein Geheimnis schützen, lässt sich mit kleinen Zahlen nachrechnen.

Eine Enigma-Verschlüsselungsmaschine im Museum für Wissenschaft und Technik in Mailand
Eine Enigma-Verschlüsselungsmaschine im Museum für Wissenschaft und Technik in Mailand Bild: Alessandro Nassiri, CC BY-SA 4.0 · Wikimedia Commons

Wer eine Nachricht im Messenger schreibt, eine Webseite mit Schloss-Symbol öffnet oder online bezahlt, benutzt Zahlentheorie. Im Hintergrund rechnet das Gerät mit Zahlen, die Hunderte Stellen haben, und mit einer Eigenschaft der Primzahlen, die schon Euklid kannte: Jede Zahl lässt sich auf genau eine Weise in Primfaktoren zerlegen.

Dieser Beitrag erklärt die Grundidee am bekanntesten Verfahren, RSA, mit Zahlen, die man noch im Kopf oder mit dem Taschenrechner nachprüfen kann. Und er erzählt, wie ein Teil der Mathematik, den man lange für völlig nutzlos hielt, zur Grundlage der digitalen Sicherheit wurde.

Das Problem mit dem Schlüssel

Geheimschriften sind uralt. Julius Caesar soll Buchstaben in seinen Briefen um drei Stellen im Alphabet verschoben haben, aus A wurde D, aus B wurde E. Wer die Verschiebung kennt, kann die Nachricht lesen. Alle klassischen Verfahren, bis hin zur Enigma-Maschine des Zweiten Weltkriegs, haben dieselbe Schwäche: Sender und Empfänger brauchen denselben geheimen Schlüssel. Wie bekommt man ihn sicher zum anderen, wenn man ihn noch nie getroffen hat?

Im Internet ist das der Normalfall. Ein Handy hat den Server einer Bank nie getroffen und muss trotzdem eine geheime Verbindung aufbauen, über Leitungen, die jeder mitlesen könnte. Die Lösung wirkt zunächst unmöglich: ein Schloss, das jeder zuschnappen lassen kann, das sich aber nur mit einem Schlüssel öffnen lässt, den nur einer besitzt.

Anzeige

Die Einbahnstraße aus Primzahlen

Eine Primzahl ist nur durch 1 und sich selbst teilbar. Multipliziert man zwei Primzahlen, etwa 61 · 53 = 3233, geht das schnell. Der umgekehrte Weg ist mühsam: Wer nur 3233 kennt, muss Teiler ausprobieren, bis er 53 findet. Bei vierstelligen Zahlen ist das eine Fleißaufgabe, die der Primfaktorzerlegung-Rechner in Sekundenbruchteilen erledigt.

Bei Zahlen mit über 600 Stellen sieht es anders aus. Für sie kennt niemand ein Verfahren, das die Primfaktorzerlegung in vernünftiger Zeit findet. Der bisher größte öffentlich zerlegte Wettbewerbswert stammt vom September 2026: Am 19. September wurden die beiden Primfaktoren der 270-stelligen Zahl RSA-896 veröffentlicht, gerechnet nach Angaben des Forschers auf bis zu 2048 Grafikprozessoren. Gut zwei Wochen zuvor war die 260-stellige Zahl RSA-260 aus einem Wettbewerb von 1991 mit gut 4900 Rechentagen auf Grafikprozessoren in ihre zwei Primfaktoren zerlegt worden. Der Rekord davor stammte von 2020, hatte 250 Stellen und rund 2700 Jahre Rechenzeit eines einzelnen Prozessorkerns gekostet. Übliche RSA-Schlüssel haben 617 Stellen und bleiben nach Einschätzung der Forscher auch damit weit außer Reichweite.

Rechnen wie auf der Uhr

RSA rechnet nicht mit gewöhnlichen Zahlen, sondern mit Resten. Auf einer Uhr ist 9 Uhr plus 5 Stunden nicht 14 Uhr, sondern 2 Uhr: Man rechnet „modulo 12“ und behält nur den Rest nach dem Teilen durch 12. Genauso lässt sich modulo jeder anderen Zahl rechnen. Die Regeln dieses Rechnens beschreibt die Lernseite Modulare Arithmetik.

Entscheidend ist eine Entdeckung von Pierre de Fermat aus dem Jahr 1640, die Leonhard Euler 1763 verallgemeinerte: Potenziert man eine Zahl immer weiter und rechnet dabei modulo einer festen Zahl, kehrt man nach einer bestimmten Anzahl von Schritten zum Ausgangswert zurück. Wie lang dieser Kreislauf ist, lässt sich leicht berechnen, wenn man die Primfaktoren der festen Zahl kennt. Ohne sie ist es so schwer wie das Zerlegen selbst.

RSA im Kleinen

So funktioniert das Verfahren mit den Primzahlen 61 und 53. Echte Schlüssel arbeiten genauso, nur mit viel größeren Zahlen.

  1. Schlüssel erzeugen: Die Empfängerin wählt geheim die Primzahlen p = 61 und q = 53 und berechnet n = 61 · 53 = 3233 und (61 − 1) · (53 − 1) = 3120. Sie wählt die Zahl e = 17 und dazu d = 2753, denn 17 · 2753 = 46.801 lässt beim Teilen durch 3120 den Rest 1.
  2. Veröffentlichen: Der öffentliche Schlüssel ist das Paar (3233, 17). Jeder darf ihn kennen. Die Zahlen 61, 53 und 2753 bleiben geheim.
  3. Verschlüsseln: Ein Absender will die Zahl 65 schicken. Er rechnet 6517 modulo 3233 und erhält 2790. Nur diese Zahl geht über das Netz.
  4. Entschlüsseln: Die Empfängerin rechnet 27902753 modulo 3233 und erhält wieder 65.

Ein Lauscher kennt 3233, 17 und 2790. Um 2753 zu finden, müsste er 3120 kennen, und dafür braucht er die Faktoren 61 und 53. Bei dieser kleinen Zahl gelingt das sofort, bei einer Zahl mit 617 Stellen nach heutigem Wissen nicht. Texte werden vorher in Zahlen umgewandelt, so wie jeder Buchstabe im Computer ohnehin als Zahl gespeichert ist.

Anzeige

Von Euklid bis zum Geheimdienst

Die Bausteine sind alt. Euklid bewies um 300 v. Chr., dass es unendlich viele Primzahlen gibt, sodass der Vorrat an Schlüsseln nie ausgeht. Fermat und Euler fanden im 17. und 18. Jahrhundert die Regeln für Potenzen mit Resten. Carl Friedrich Gauß machte das Rechnen mit Resten 1801 in seinen Disquisitiones Arithmeticae zu einem eigenen Gebiet und führte das Zeichen ≡ ein, das bis heute dafür steht.

Lange galt die Zahlentheorie als reinste und nutzloseste aller Disziplinen. Der englische Mathematiker G. H. Hardy war stolz darauf. In seinem Essay A Mathematician’s Apology von 1940 schrieb er sinngemäß, die echte Mathematik habe keinen Einfluss auf den Krieg, und niemand habe bisher einen kriegerischen Zweck für die Zahlentheorie gefunden. Zur gleichen Zeit knackte Alan Turing in Bletchley Park die Enigma, allerdings mit ganz anderen Mitteln.

Die Wende kam 1976. Whitfield Diffie und Martin Hellman zeigten, dass zwei Parteien über eine offene Leitung einen gemeinsamen Schlüssel vereinbaren können. Ein Jahr später fanden Ron Rivest, Adi Shamir und Leonard Adleman am MIT das Verfahren, das nach ihren Anfangsbuchstaben RSA heißt. Erst 1997 wurde bekannt, dass der Mathematiker Clifford Cocks beim britischen Geheimdienst GCHQ dieselbe Idee schon 1973 gehabt hatte. Sie war als geheim eingestuft.

Heute und morgen

Viele Verbindungen nutzen für den Schlüsseltausch heute nicht mehr RSA, sondern elliptische Kurven. Sie erlauben kürzere Schlüssel bei gleicher Sicherheit. Die Grundidee ist dieselbe: Eine Rechnung, die in eine Richtung leicht und in die andere praktisch unmöglich ist. RSA steckt weiterhin in vielen digitalen Zertifikaten und Signaturen.

Eine echte Bedrohung wären große Quantencomputer. Der Mathematiker Peter Shor zeigte 1994, dass ein solcher Rechner Zahlen schnell zerlegen könnte. Bisher gibt es keinen, der dafür groß genug ist. Vorsorglich veröffentlichte die US-Standardbehörde NIST im August 2024 die ersten Standards für Verfahren, die auch Quantencomputern standhalten sollen. Sie beruhen nicht mehr auf Primzahlen, sondern vor allem auf Aufgaben mit Gittern aus vielen Dimensionen. Die Geschichte der Zahlen im Handy geht also weiter, wie so vieles in der Mathematik des 21. Jahrhunderts.

Quellen und weiterführende Literatur

  • Simon Singh: Geheime Botschaften. Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet, Hanser, München 2000.
  • Albrecht Beutelspacher: Kryptologie, Springer Spektrum, 10. Auflage 2015.
  • R. L. Rivest, A. Shamir, L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21 (1978), S. 120–126 (englisch).
  • G. H. Hardy: A Mathematician’s Apology, Cambridge University Press, Cambridge 1940 (englisch).
  • Wikipedia: RSA-Kryptosystem
Anzeige

Fehler entdeckt oder einen Wunsch? Schreib uns eine kurze Nachricht, wir kümmern uns darum.

Fehler entdeckt oder einen Wunsch?

Deine Nachricht zur Seite „Primzahlen im Handy: wie Verschlüsselung funktioniert“. Die Adresse der Seite schicken wir automatisch mit.

Bitte schreib keine weiteren persönlichen Daten hinein. Mehr dazu im Datenschutz.