Das RSA-Kryptosystem ist ein asymmetrisches Kryptosystem, wessen Sicherheit auf der Primfaktorzerlegung großer Zahlen berhuht.
Es wurde 1977 von Rivest, Shamir, Adlemen entwickelt.
- Bob wählt sich zwei Primzahlen p und q (umso größer umso sicherer)
- berechnen von n = p ⋅ q
→ n ist Teil des public und privat key
- Eularische Phi Funktion von n bestimmen φ(n) = (p-1)(q-1)
→ φ(n) berechnet die Anzahl an teilerfremden Zahlen
- Exponenten e wählen, welcher Teil des public key ist
→ e ist eine Teilerfremde Zahl zu φ(n) und 1 < e < φ(n)
- Euklidischer Algorithmus (größter gemeinamer Teiler) wird angewendet: ggT(e,φ(n)) = 1
→ der ggT muss gleich 1 ergeben
- Privaten schlüssel d bestimmen, welcher Teil des privat key ist, mit dem erweitertem euklidischem Algorithmus: d ⋅ e ≡ 1 mod(φ(n))
Endprodukt:
public key = (e, n)
private key = (d, n)
c = me mod(n)
m für message
m = cd mod(n)
p= 61
q = 53
p ⋅ q = n
n = 3233
φ(n) = 3120
e wählen
e = 17
d bestimmen
d ⋅ e = 1 mod(3120)
d ⋅ 17 = 1 mod(3120)
d = 2753
Verschlüsseln
m=65
c = me mod(n)
c = 6517 mod 3233
Entschlüsseln
m= cd mod(n)
m= 27902753 mod (3233)
https://youtu.be/M_zNKdBZHOw?si=C5JQoqJvHiJY6Rkv