RSA - Verschlüsselung
Entwickler:
Ronald Rivest (Mitte), Adi Shamir
(Links), Leonard Adleman (Rechts)
Veröffentlichung : 1978
Grundprinzip der RSA – Verschlüsselung:
Bestimmung der Schlüssel:
1. Es werden 2 Primzahlen p und q gewählt, wobei p =|= q
(Je größer die Primzahlen sind, desto sicherer der Schlüssel)
2. Es wird das Produkt N=p*q und q(N)=(p-1)*(q-1) berechnet
3. Es wird eine Zahl e bestimmt, die ungerade, größer als 1, aber kleiner
als q(N) und teilerfremd zu q(N) ist
4. Es wird d = (q(N)*s+1)/e bestimmt, wobei d€|N, s€|N und d=|=e
5. p,q und q(N) werden gelöscht, da sie nicht mehr benötigt werden
-> öffentlicher Schlüssel: N,e
-> privater Schlüssel: d,N
Zahlenbeispiel:
1. Wähle p=3; q=5
2. N=3*5=15; q(N)=2*4=8
3. 8=2*2*2 -> Wähle e=3
4. d=(8*s+1)/e -> Wähle s=4 -> d=11
öffentlicher Schlüssel : N=15, e=3 | privater Schlüssel: N=15, d=11
Der Eulersche Satz

Wählt man 2 positive Primzahlen p und q
mit p =!= q, dann gilt:

m^[s(p-1)(q-1)] MOD n = m

m,n,s € |N mit m <= n
Verschlüsselung:
Geheimtext=(Klartext^e) MOD N
Beispiel:
Klartext: 12130508
Zerlegung in Blöcke, die kleiner als N sind:
12 13 05 08
12^3=´1728
1728/15= 115 Rest 03
13^3= 2197
2197/15= 146 Rest 07
05^3= 125
125/15 = 8
08^3= 512
512/15 = 34 Rest 02
-> Geheimtext : 03070502
Rest 05
Entschlüsselung:
Klartext=(Geheimtext^d) MOD N
Beispiel:
Geheimtext: 03070502
Zerlegung in Blöcke, die kleiner als N sind:
03 07 05 02
03^11=´177147
177147/15
= 11809
Rest 12
07^11= 1977326743 1977326743/15= 131821782 Rest 13
05^11= 48828125
48828125/15
= 3255208
Rest 05
02^11= 2048
2048/15
= 136
Rest 08
-> Klartext : 12130508
Sicherheit der RSA-Verschlüsselung
->
->
->
->
man benötigt d, um den Geheimtext zu entschlüsseln
man kennt N und e durch den öffentlichen Schlüssel
d = (q(N)*s+1)/e d€|N, s€|N -> man benötigt also q(N)
N=p*q -> man müsste also N in seine Primfaktoren p und q
zerlegen
-> je größer man p und q wählt, desto sicherer wird der Schlüssel
Schlüssellängen:
Standart-Sicherheit -> 512 Bit ( Shamir entwickelte Computer, der diesen
in 3 Tagen knacken kann)
Military-Standart -> 1024 Bit
In den USA sind lediglich 512 Bit erlaubt.
aus wikipedia.de:

Es ist aber nicht bewiesen, dass es sich bei der Primfaktorzerlegung um ein
prinzipiell schwieriges Problem handelt. Im Gegenteil, mit dem Quadratischen Sieb
wurden bereits Zahlen mit über 100 Stellen faktorisiert. So gelang es zum Beispiel
Mathematikern der Universität Bonn 2005, im Rahmen eines Wettbewerbs eine
einzelne von den RSA Laboratories vorgegebene 200-stellige Dezimalzahl zu
faktorisieren. Die Faktorisierung begann Ende 2003 und dauerte bis Mai 2005. Unter
anderem kam ein Rechnerverbund von 80 handelsüblichen Rechnern an der
Universität Bonn zum Einsatz. Dies ist noch ein gutes Stück von den mindestens 300
Dezimalstellen heute üblicher Schlüssel entfernt. Im November 2005 zahlten RSA
Laboratories für die Faktorisierung von RSA-640, einer Zahl mit 640 Bits bzw. 193
Dezimalstellen, eine Prämie von 20.000 US-Dollar. Für die Faktorisierung von RSA1024 (309 Dezimalstellen) oder gar RSA-2048 (617 Dezimalstellen) sind 100.000 $
bzw. 200.000 $ ausgelobt. Die wachsende Rechenleistung moderner Computer stellt
für die Sicherheit von RSA kein Problem dar, zumal diese Entwicklung vorhersehbar
ist: Der Nutzer kann bei der Erzeugung seines Schlüsselpaares darauf achten, dass
die zu zerlegende Zahl groß genug ist, um während der Dauer der beabsichtigten
Verwendung nicht berechnet werden zu können.
Anwendungsgebiete:
- Bankwesen ( Verschlüsselung von Geheimzahlen )
- Verschleierung von Pay – TV – Programmen
- Verschlüsselung von Mobilfunknetzen
- Geheimdienste
- Übertragungs-Protokolle: IPSec, TLS, SSH, WASTE
- E-Mail-Verschlüsselung: PGP, S/MIME
- Authentifizierung französischer Telefonkarten
- Kartenzahlung: EMV

RSA - Verschlüsselung