RSA: Primzahlen
13 × 17 = 221. Das rechnest du im Kopf. Bekommst du 221 und die Frage, welche zwei Primzahlen das waren, dann musst du probieren: 3? 7? 11? 13, erwischt. Eine Minute Arbeit. Mach Zahlen mit 300 Stellen daraus, und diese Minute wird länger, als das Universum alt ist — während die Multiplikation immer noch im Bruchteil einer Sekunde läuft. Auf dieser Schieflage steht RSA.
Wörter, die du gleich brauchst
- Primzahl
- Eine Zahl, die nur durch 1 und durch sich selbst teilbar ist: 2, 3, 5, 7, 11, 13… Je größer du schaust, desto seltener werden sie, aber sie hören nie auf — das hat schon Euklid bewiesen, vor gut zweitausend Jahren.
- In Faktoren zerlegen
- Eine Zahl auf die Primzahlen zurückführen, aus denen sie aufgebaut ist. 221 wird 13 × 17. Das ist die Rechnung, die RSA unmöglich machen muss.
- Falltürfunktion
- Eine Rechnung, die vorwärts leicht geht und rückwärts unmöglich ist — außer du kennst ein Geheimnis, dann geht es doch. Wie eine Falltür: flott hinein, nicht mehr heraus, außer du weißt, wo die Klinke sitzt.
- OAEP
- Die Auffüllung, die vor dem Verschlüsseln an die Nachricht gesetzt wird: zufällige Bytes nach einem festen Rezept. Ohne diese Auffüllung ergibt dieselbe Nachricht immer denselben Geheimtext, und das ist ein Leck — dasselbe Problem wie ein fehlender IV in Kapitel 4.
Wie es funktioniert, ohne die Formeln
- Dein Computer wählt zwei riesige Primzahlen und hält sie geheim.
- Er multipliziert sie. Dieses Produkt darf jeder sehen; es steckt in deinem öffentlichen Schlüssel.
- Verschlüsseln ist eine Rechnung mit diesem Produkt — Uhrenrechnen, wie in Kapitel 5, aber auf einer Uhr mit Hunderten Stellen als Umfang.
- Entschlüsseln ist dieselbe Art Rechnung, aber dafür brauchst du die zwei Primzahlen selbst. Die hast du, und sonst niemand.
Wer deinen öffentlichen Schlüssel hat, hat also das Produkt. Zum Entschlüsseln muss er es zerlegen. Das geht — in der Theorie. Nur dauert es zu lange, und das ist die ganze Sicherheit. Gar kein Schloss, nur eine Rechnung, die niemand fertig bekommt.
Probier es selbst
Das Schlüsselpaar wird in deinem Browser gemacht und verschwindet, sobald du diesen Tab schließt. Du darfst dir hier ruhig den privaten Schlüssel ansehen: Er ist für diese Seite gemacht und wird für nichts benutzt. Bei einem echten Schlüssel machst du das nie.
- Klick auf Mach ein Schlüsselpaar. Das dauert einen Moment: Dein Computer sucht zwei Primzahlen. Du siehst deinen öffentlichen Schlüssel — diesen Textblock darfst du jedem geben.
- Klick auf Zeig den privaten Schlüssel. Vergleich die zwei Blöcke: Der private ist gut viermal so lang. Darunter stehen p und q, die zwei Primzahlen aus Schritt 1, und das Produkt, das in deinem öffentlichen Schlüssel steckt.
- Klick auf Mit dem öffentlichen Schlüssel verschlüsseln. Der Geheimtext ist immer genau 256 Bytes groß, wie kurz deine Nachricht auch ist.
- Klick auf Mit dem privaten Schlüssel entschlüsseln. Deine Nachricht kommt zurück.
- Füg jetzt einen langen Text ins Nachrichtenfeld ein — ein paar Absätze — und verschlüssle. Es klappt nicht. Lies, warum.
Warum du gegen eine Mauer gelaufen bist
RSA mit einem Schlüssel von 2048 Bit kann nur 190 Bytes verschlüsseln. Das ist keine Einstellung, die du höher drehen kannst: Die Nachricht muss kleiner bleiben als die Zahl, mit der gerechnet wird. Ein größerer Schlüssel hilft kaum und macht alles langsamer. Asymmetrische Verschlüsselung ist also nicht dafür gemacht, Nachrichten damit zu verschicken.
Wofür dann? Für zwei Dinge: jemandem einen frischen AES-Schlüssel schicken, ohne vorher etwas zu vereinbaren, und signieren. Um das Zweite geht es in Kapitel 7.1. Darum, wie alles zusammenkommt, in Kapitel 7.3.
Aber zuerst etwas Schöneres. RSA rechnet mit Primzahlen von 600 Stellen. Es gibt einen eleganteren Weg, der mit viel kleineren Zahlen dasselbe erreicht: rechnen mit Punkten auf einer krummen Linie. Die steckt in deiner eID, in deinem Browser und in Bitcoin. Im nächsten Kapitel darfst du darauf klicken.
Wie groß muss so ein Schlüssel sein
| Schlüssel | Das ist eine Zahl mit | Urteil |
|---|---|---|
| RSA-1024 | 309 Stellen | zu klein, seit Jahren abgeraten |
| RSA-2048 | 617 Stellen | heute der Standard |
| RSA-4096 | 1234 Stellen | großzügiger, und spürbar langsamer |
Diese Langsamkeit ist keine Kleinigkeit. Ein Schlüsselpaar zu machen dauert spürbar lange — du hast es bei der ersten Schaltfläche gemerkt — weil dein Computer suchen muss, bis er zwei Primzahlen findet. Und jede Verdopplung der Schlüssellänge macht die Rechnerei ungefähr achtmal schwerer. Genau darum steigt die Welt auf Kurven um, und das ist Kapitel 6.2.
Das ist Mathematik: Primzahlen als Einbahnstraße
Multiplizieren und Zerlegen sind Umkehrungen voneinander, und trotzdem ist die eine Richtung trivial und die andere unbegehbar. Der beste Algorithmus, den wir zum Zerlegen einer Zahl mit 617 Stellen kennen — das Zahlkörpersieb — wäre auf allen Computern der Welt zusammen länger beschäftigt, als das Universum existiert. Nicht weil es nicht ginge, sondern weil es zu lange dauert.
Und achte darauf, was da steht: der beste Algorithmus, den wir kennen. Niemand hat bewiesen, dass Zerlegen schwer ist. Wird morgen ein schneller Weg gefunden, dann fällt RSA am selben Tag um. Das ist keine Schwarzmalerei, sondern wie das Fach funktioniert: Die Sicherheit des Internets ruht auf Problemen, von denen wir nur wissen, dass sehr viele kluge Leute sie nicht gelöst bekommen haben. Das ist Zahlentheorie, das Fach, das jahrhundertelang „nutzlos, aber schön“ hieß.