Einwegfunktionen

Funktionen, von denen man vermutet, dass es Einweg-Funktionen sind:

die Multiplikation von ganzen Zahlen (Umkehrung: Primfaktorzerlegung)
die ganzzahlige Potenzierung modulo N (Umkehrung: der ganzzahlige Logarithmus)

Leider kann Ihr Browser keine Applets darstellen.

(Das nebenstehende Applet verwendet Java 1.0, daher sind die Zahlen auf 64 Bit beschränkt. Wenn Ihr Browser Java 1.1 unterstützt, können Sie auch größere Zahlen faktorisieren.)

Tragen Sie in das obere Feld eine Zahl ein (dezimal) und drücken Sie die Eingabetaste. Die Primfaktoren der Zahl erscheinen im Feld darunter. Ganz unten wird die benötigte Zeit angezeigt.

Beispiel: 1079797 * 241021933 = 260254760187601
Das Ergebnis ist 15-stellig, lässt sich also in 64-Bit-Arithmetik rasch berechnen. Die Faktorisierung dauert bereits deutlich messbare Zeit.

(Die Zahl ist beim Start des Applets bereits eingetragen. Wenn Ihr Grafiksystem das erlaubt, können sie auch Zahlen mit der Maus selektieren und dann mit "Kopieren und Einfügen" in den Faktorisierer bringen, anstatt sie abzutippen.)

Wenn man die Primfaktoren verraten würde, wäre das Geheimnis natürlich verbraucht. Es gibt aber, wie Tartaglias Geheimnis zeigt, Möglichkeiten, die Kenntnis zu beweisen, ohne das Geheimnis selbst zu verraten. In Zusammenhang mit der Primfaktorisierung hilft hier der "Satz von Carmichael", der Folgendes besagt:

Sei n = pq Primfaktorisierung von n,
cd mod (p-1)(q-1) = 1;
dann gilt für beliebiges a:

(a^c)^d = a^cd = a (mod n)

Solche Zahlen c und d zu finden ist kein Problem, wenn man die Faktorisierung pq kennt. Daher lässt sich die Potenzierung mit c als Verschlüsselung, die Potenzierung mit d als Entschlüsselung gebrauchen. Es handelt sich um den berühmten RSA-Schlüssel, benannt nach den Autoren des Artikels:

Rivest, Shamir, Adleman:
A method of obtaining digital signatures
and public key cryptosystems.
Comm. ACM 1978, 120–126.

F. L. Bauer ("Kryptologie") führt zum RSA-Verfahren aus:

US-Patent 4 405 829 vom 20. September 1983. Im Originalverfahren wird anstelle der Carmichaelschen Funktion die Eulersche Phi-Funktion verwendet. ... Der Satz von Carmichael ist "...a very useful, but often forgotten, generalization of Euler's theorem" (H. Riesel, Prime Numbers and Computer Methods for Factorization. Birkhäuser, Basel 1985). Tatsächlich erwähnen Rivest, Shamir, Adleman ihn nicht...