Würfelglück
Miller-Rabin-Test: Primzahlen per Zufall bestimmen
Verschlüsselungen wie RSA setzen auf große Primzahlen, um sichere Schlüssel zu erstellen. Es ist aber gar nicht so leicht, Primzahlen in der geeigneten Größenordnung zu finden. Daher benutzen RSA-Implementierungen den Miller-Rabin-Primzahltest. Wir erklären, wie der Test funktioniert, und liefern dazu ein Python-Programm.
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 [1]. 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) [2]. 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.