Kryptografie: Riesige Primzahlen für sichere Verschlüsselungen finden
Verschlüsselungen wie RSA setzen auf große Primzahlen, um sichere Schlüssel zu erstellen. RSA-Implementierungen nutzen dazu den Miller-Rabin-Primzahltest.
(Bild: Thorsten Hübner)
Kryptologen machen sich die besonderen Eigenschaften von Primzahlen zunutze, um mathematische Probleme zu entwerfen, die selbst Supercomputer nicht lösen können. Eines davon ist das Grundgerüst der asymmetrischen Verschlüsselung RSA. Dafür benötigt man zunächst zwei gigantisch große Primzahlen mit mehr als 300 Dezimalstellen und multipliziert sie miteinander. Das Rätsel besteht nun darin, allein anhand des Ergebnisses die ursprünglichen Primfaktoren zu ermitteln (Primfaktorzerlegung). Aber wie findet RSA eigentlich solch große Primzahlen, um immer neue Rätsel zu generieren?
Da es keine Formel gibt, die alle Primzahlen zuverlässig bestimmt, bleibt nur Ausprobieren übrig. Das Durchrechnen aller Möglichkeiten ist nur bei kleinen Zahlen sinnvoll. Stößt man aber in Bereiche mit mehreren hundert Dezimalstellen vor, dauert simples Probieren zu lange. Dafür haben Kryptologen spezifische Tests entwickelt, die riesige Zahlen rasch auf bekannte Primzahl-Eigenschaften abklopfen. Einer von ihnen ist der Miller-Rabin-Test. Darum geht es im Folgenden.
Die 2048-Bit-Variante von RSA verwendet momentan etwa 300-stellige Primzahlen. Anstatt sie alle nacheinander durchzuspielen, wählt Miller-Rabin zunächst einen Testkandidaten per Zufallsgenerator aus und versucht herauszufinden, ob dieser zusammengesetzt ist oder nicht. Falls ja, wird die nächste 300-stellige Zahl generiert. Falls nein: prima, neue Primzahl gefunden.
Immer mehr Wissen. Das digitale Abo für IT und Technik.
CPU-Guide 2024: Notebook-Prozessoren von AMD, Apple und Intel im Vergleich
Im Test: Zehn USB-SSDs und -Sticks mit 1 oder 2 TByte Speicherplatz
Fujifilm X100VI im Test: Neuauflage der beliebten Edelkompaktkamera
Was Windows 11 Version 24H2 Neues bringt – und was rausfliegt
Elektroauto MG4 Trophy im Test: Bestseller mit Batterie-Upgrade
Karrierewechsel: Warum sich ein Informatikstudium auch für Quereinsteiger lohnt
Immer mehr Wissen. Das digitale Abo für IT und Technik.
CPU-Guide 2024: Notebook-Prozessoren von AMD, Apple und Intel im Vergleich
Im Test: Zehn USB-SSDs und -Sticks mit 1 oder 2 TByte Speicherplatz
Fujifilm X100VI im Test: Neuauflage der beliebten Edelkompaktkamera
Was Windows 11 Version 24H2 Neues bringt – und was rausfliegt
Elektroauto MG4 Trophy im Test: Bestseller mit Batterie-Upgrade