SSH - RSA

[Previous] [Next] [Up] [Contents] [Index]

Rivest Shamir Adleman (RSA) Auszug aus dem Skript zu Inferno (SS 1997)

Asymmetrisches Verfahren zur Übermittlung von Nachrichten:

p, q	große, gleichlange Primzahlen, geheim bei Eva
n = pq	allgemein bekannt
e	Primzahl mod (p-1)(q-1), öffentlicher Schlüssel von Eva, allgemein bekannt
d	privater Schlüssel bei Eva, so daß ed = 1 mod (p-1)(q-1)
	unter Kenntnis von p, q leicht zu berechnen

N	< n, Nachricht von Adam an Eva

Adam an Eva:	N^e mod n
Eva berechnet:	(N^e mod n)^d mod n = N mod n

Es gilt N^ed = N^{1+k(p-1)(q-1)} = N N^k(p-1)(q-1) für irgendeine Konstante k.

Entweder sind N und n teilerfremd, dann ist N^(p-1)(q-1) = 1 mod n nach Euler's Verallgemeinerung des Kleinen Satzes von Fermat, also erhält Eva die Nachricht.

Da N < n ist, kann sonst nur eines von p und q die Zahl N teilen, also zum Beispiel N = u p und N und q sind teilerfremd. Nach dem Kleinen Satz von Fermat ist dann N^q-1 = 1 mod q, also N^k(p-1)(q-1) = 1 + v q, für irgendwelche Konstanten u und v.

Dann ist aber N N^k(p-1)(q-1) = N (1+ v q) = N + v N q = N + v u p q = N mod n, das heißt, auch in diesem Fall erhält Eva die Nachricht. [Mit Dank an B. Hammer...]

[Previous] [Next] [Up] [Contents] [Index]

[Feedback]