www.Primzahlen.de

Praxis

Praktische Anwendungsfälle von Primzahlen

RSA-Verfahren

Fragen  |   zurück

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

Bei Fragen, Anregungen, Vorschlägen, Kritiken und schicken Sie bitte Steffen Hitzemann eine E-Mail (Stevie.H@web.de)



nach oben