RSA (hb)

Mathematische Grundlagen zum RSA - Verfahren (nach Rivest 1977)

		Ort	öffentlich (public)	private	Beispiel
1.	p , q wählen (prim)	Empfänger		x	p = 3, q = 5
2.	N = pq ("Modulus")	Empfänger	x		15
3.	e wählen ("encrypt exponent")	Empfänger	x		e = 3, verwendbar gemäß (p-1)(q-1) = 8 = 222
4.	d berechnen ("decrypt exponent") wofür gilt: ed=1mod(p-1)(q-1)	Empfänger		x	mit X = 4 ist d = (4(3-1)(5-1)+1)/3 = 11
5.	Übertragen des "Public Key" (N, e) vom Empfänger an Sender
6.	M ... Message im Klartext	Sender		x	M = 12
7.	C = M^e mod N ... verschlüsselte Nachricht	Sender	x		C = 12³/15 = 155 Rest 3 = 3
8.	Übertragen der verschlüsselten Nachricht vom Sender an Empfänger
9.	M = C^d mod N ... entschlüsselte Nachricht	Empfänger		x	M = 03¹¹/15 = 11809 Rest 12 = 12

Anmerkung zu "e":

e < N
e darf keine gemeinsamen Faktoren mit dem Produkt (p-1)(q-1) haben
e muss ungerade sein, braucht aber keine Primzahl zu sein

Anmerkung zu "d":

Der Ausdruck "ed=1mod(p-1)(q-1)" ist wie folgt zu lesen: "ed wird durch ((p-1)(q-1)) so geteilt, dass Rest 1 bleibt"
einfachste Ermittlung mittels d= (X(p-1)(q-1)+1)/e , wobei für X so lange eine beliebige Zahl eingesetzt wird bis d eine ganze Zahl ergibt
sollte nicht gleich sein wie e, denn dann wäre der Public Key (N, d) gleich dem Secret Key (N, e)

Anmerkung zu "M":

M < N

Siehe auch Diffie-Hellman