- Einleitung
- 1977 entwickelten RONALD L. RIVEST, ADI SHAMIR und LEONARD
ADELMAN ein asymmetrisches Verschlüsselungsverfahren, das
man heute nach den Anfangsbuchstaben ihrer Nachnamen RSA nennt.
Der RSA-Algorithmus erfüllt die folgenden Forderungen:
Der Chiffrier- und der Dechiffrierschlüssel sind verschieden;
außerdem kann der Chiffrierschlüssel öffentlich
sein, während der Dechiffrierschlüssel geheim bleibt.
-
- Grundlagen
- Das RSA-Verfahren basiert auf dem Satz von EULER. Sind m
und n zwei natürlich teilerfremde Zahlen, d.h. ggT(m,n)=1,
dann gilt:
m^Phi(n) mod n = 1.
- Zu einer Primzahl sind alle natürlichen Zahlen r, die
kleiner als p sind, teilerfremd, also ist Phi(p) = p-1. Für
das Produkt zweier Primzahlen p und q ergibt sich somit die
Beziehung:
Phi(pq) = (p-1)(q-1).
- Es sind nämlich die Zahlen 1p, 2p, 3p, ..., (q-1)p;
qp und die Zahlen 1q, 2q, 3q, ..., (p-1)q; pq nicht teilerfremd
mit pq, also ist die Teilermenge von pq T={1p, 2p, 3p, ...,
(q-1)p; 1q, 2q, 3q, ..., (p-1)q; pq} und die Anzahl der Teiler
somit p-1+q-1+1 = p+q-1, woraus sich Phi(pq) = pq-(p+q-1) =
(p-1)(q-1) ergibt.
-
- Schlüsselerzeugung
- Für die Erzeugung vom öffentlichen (Chiffrier-)Schlüssel
und privaten (Dechiffrier-)Schlüssel werden zunächst
zwei "große" Primzahlen p und q, sodass n=pq
> m mit m als zu verschlüsselnder Zahl ist, ausgewählt
und es wird Phi(n) durch die Beziehung Phi(n) = (p-1)(q-1) bestimmt.
Für eine sichere Verschlüsselung sollten die beiden
Primzahlen p und q in einer Größenordnung von mindestens
10^200 liegen. Durch die Formel
cd mod Phi(n) = 1,
- die sich als zweckmäßig erweist, wenn man den
Satz von EULER im Beweis des Verfahrens anwenden
möchte, werden Chiffrierschlüssel c und Dechiffrierschlüssel
d bestimmt. Dazu wird c gewählt, und zwar so, dass die
Bedingung auch zutreffen kann. Folglich müssen c und Phi(n)
teilerfremd sein, häufig wird für c eine Primzahl
gewählt, die größer als Phi(n) ist. Der Schlüssel
d lässt sich dann leicht berechnen:
- cd mod Phi(n) = 1
- cd = 1+k * Phi(n), k e N
- d = (1+k * Phi(n)) / c
- d = (1+k * (p-1)(q-1)) / c.
|
- Es kann eine beliebige natürliche Zahl für k gewählt
werden, allerdings so, dass auch d eine natürliche Zahl
ist. Nun werden n und Chiffrierschlüssel c veröffentlicht,
p und q werden vernichtet.
-
- Ver- und Entschlüsselung
- Da nur Zahlen verschlüsselt werden können, muss
der Klartext m zunächst in eine Zahlenfolge umgewandelt
werden. In der Praxis geschieht dies über den ASCII-Code
(American Standard Code for Information Interchange). Der Geheimtext
g ergibt sich aus folgender Formel:
g = m^c mod n.
- Die Dechiffrierung erfolgt durch
m' = m = g^d mod n.
-
- Beweis von RSA
- Es muss jetzt bewiesen werden, dass das RSA-Verfahren auch
funktioniert und als Verschlüsselungsverfahren dient. Die
Formeln zur Schlüsselerzeugung sowie zur Ver- und Entschlüsselung
wurden natürlich so ausgewählt, dass der Beweis funktioniert.
-
- Arbeitet die Dechiffrierfunktion korrekt?
- Es wird umgeformt:
- g = m^c mod n
- g^d = m^cd mod n (1)
|
- Einsetzen von (1) in m' = g^d mod n:
m' = m^cd mod n
- Die Dechiffrierfunktion arbeitet korrekt, wenn m = m', also
m = m^cd mod n ist. Es wurden c und d so gewählt, dass
die Beziehung cd mod Phi(n) = 1 zutrifft. Es gibt also auch
eine natürliche Zahl k, für die gilt:
cd = 1+k * Phi(n), k e N. (2)
- Jetzt soll der Satz von EULER angewendet werden. Bezogen
auf m und p gilt er, wenn m und p teilerfremd sind. Dies ist
nicht selbstverständlich der Fall, wenn m und p jedoch
nicht teilerfremd sind, ist p ein Teiler von m, also gilt m
mod p = 0. Wenn p Teiler von m ist, ist p auch Teiler von m^cd,
also gilt:
m^cd mod p - m mod p = (m^cd-m) mod p = 0. (3)
- Sind m und p teilerfremd, gilt nach dem Satz von EULER:
m^Phi(p) mod p = 1. (4)
- Weil p prim ist, ist Phi(p)=p-1, also gilt:
- m^cd mod p
- = m^(1+k * Phi(n)) mod p [Einsetzen von (2)]
- = m * m^(k * Phi(n)) mod p
- = m * m^(k * (p-1)(q-1)) mod p
- = m * (m^(p-1))^(k * (q-1)) mod p
- = m * (m^(p-1) mod p)^(k * (q-1)) mod p
- = m * 1^(k * (q-1)) mod p [Anwedung von (4)]
- = m mod p.
|
- Die Umformungen sind nach Regeln der Modulo-Operation korrekt,
also gilt, unabhängig davon, ob m und p teilerfremd sind:
(m^cd-m) mod p = 0. (3)
- Außerdem gilt auch:
(m^cd-m) mod q = 0. (5)
- Die Beweisführung für q erfolgt analog zur Beweisführung
mit p. Sowohl p als auch q teilt m^cd-m, demzufolge teilt auch
pq den Term m^cd-m:
- m^cd-m mod pq = 0
- m^cd mod pq = m mod pq.
|
- Da m kleiner als pq ist, ist m mod pq = m. Somit ist bewiesen,
dass
m^cd mod n = m
- ist und der Dechiffrieralgorithmus korrekt arbeitet.
- Die Sicherheit des RSA-Algorithmus basiert darauf, dass
sich aus den öffentlichen Angaben n, g und c die Nachricht
m nicht unmittelbar bestimmen lässt und die Faktorisierung
von n auf Grund der Größe von p und q sehr lange
dauern würde.
-
- Beispiel
- Als zu verschlüsselnde Nachricht wird m=100 ausgewählt.
Damit n=pq > m ist, werden p=17 und q=23 unter Berücksichtigung
der Bedingung willkürlich ausgewählt. Somit ist n=391
und Phi(n)=352. Für c wird eine Primzahl bestimmt, die
größer als 352 ist, es wird c=359 ausgewählt.
Damit
d = (1+k * (p-1)(q-1)) / c = (1+352k) / 359
- eine natürliche Zahl ist, kann k=154 sein, somit ist
d=151. Jetzt wird m verschlüsselt:
g = m^c mod n = 100^359 mod 391 = 10^718 mod 391 = 127.
- Der Geheimtext ist also 127. Jetzt wird der Text wieder
durch den privaten Schlüssel dechiffriert:
m' = g^d mod n = 127^151 mod 391 = 100 = m.
- Somit erhält man wieder den ursprünglichen Text
und die Ver- und Entschlüsslung war erfolgreich.
-
- Verfasser: Steffen Hitzemann, Nico Kaiser
|