RSA
(Rivest-Shamir-Adleman)
Schlüsselerzeugung
- Wähle zwei große und starke Primzahlen p,q (z.B. Pollard-p − 1-Methode, o. Miller-Rabin-Test)
- n = p * q
- phi(n) = (p-1) * (q-1)
- Wähle Kpub = e {1,2,...phi(n)-1}, wobei ggT(e, phi(n))=1 (ggT z.B. mit Euklid)
- Berechne Kpriv = d, sd. d * e = 1 mod phi(n) (Inverse, z.B. mit erweitertem Euklid)
Kpub=(e,n) Kpriv=(d)
Verschlüsselung von x
y = x^e mod n (square&multiply)
Entschlüsselung von y
x = y^d mod n (quare&multiply)
Schwierigkeit
Angreifer kennt phi(n) nicht und kann p und q nicht aus n berechnen (Faktorisierungsproblem)
Weiterführende Quellen
- "Das RSA-Kryptosystem und schnelle Exponentiation" aus der hervorragenden Vorlesungsreihe von Christof Paar
- Kryptografie verständlich: Ein Lehrbuch für Studierende und Anwender, Christof Paar, Jan Pelzl Springer Berlin Heidelberg, 2016
- Kryprographie und IT-Sicherheit, Joachim Swoboda, Stephan Spitz, Michael Pramateftakis Vieweg+Teubner Verlag, 2008