 | Public-Key-System benötigt zwei verschiedene Schlüssel zur Ver- und
Entschlüsselung von Nachrichten
 | Schlüssel dürfen nicht auseinander
ableitbar sein |
| immer wieder neue Algorithmen zu dieser Fragestellung das wichtigste und verbreitetste dieser Verfahren:
RSA. |
|
| RSA: Shamir, Adleman und Rivest
| am MIT 1978 |
| für sehr große Zahlen (mehrere hundert Dezimalstellen) Aufwand
für Zerlegung in Primfaktoren extrem hoch |
| für große Zahlen, ob Primzahl |
|
| Exponentiation einer Nachricht H
| mit Schlüssel e |
| reziprokem Wert d=e-1 |
|
|
Ee(H) = He mod m
Dd(He) = (He)d =
H1 = H mod m
|
| Aus m und e kann einfach d berechnet werden, wenn m Primzahl |
|
m=p*q keine Primzahl, viel schwieriger |
| zunächst Primfaktoren von m bestimmen
| zahlentheoretisch
ein schwieriges Problem |
| zeitaufwendig, für große p und q praktisch nicht durchführbar |
|
| Auswahl/Berechnung des Schlüssels folgendermaßen:
| Wählen zweier großer (>100 Stellen) Primzahlen p und q |
| Berechnung von m = p*q und r = KGV [p-1 ; q-1]. |
| Zahl e, zu (p-1) und (q-1) relativ prim |
| Zahl d=e-1,
so dass d´e=1 mod r. |
| Verschlüsselung
 | zu übertragende Information in Blöcke
| als Binärzahlen aufgefasst kleiner als m |
| erhebt Binärzahlen in e-te
Potenz, Arithmetik modulo m |
|
Entschlüsselung analog |
| Blöcke zur d-ten Potenz erheben |
|
|
| Periode k
| Hk+1=H für kleinstes k. |
| aus k und e reziproker Wert d=e-1
einfach bestimmbar |
| Ist m Primzahl, so ist Periode gleich m |
| m keine Primzahl, so ist Berechnung der Periode nur möglich, wenn Primfaktoren von m bekannt |
| Sicherheit beruht darauf,
dass
Primfaktoren nur schwierig bestimmbar |
|
bekanntes zahlentheoretisches Problem, |
| bis heute noch nicht einfach gelöst |
| Sicherheit dieses Verfahrens basiert auf ungelöstem
mathematischen Problem |
|
|
| RSA-Verfahren wurde patentiert
| Patente
mittlerweile ausgelaufen |
| Verfahren frei verfügbar ist |
|
