RSA Verschlüsselung - Korrektheit

Zurück zum Hauptartikel über RSA

Wir behaupten: Der RSA-Algorithmus arbeitet korrekt, d. h.: m' = m. Diese Tatsache können wir auch beweisen. Dazu muss ich Ihnen jedoch kurz den Satz von Euler vorstellen. Dieser ist eine Verallgemeinerung des kleinen Satzes von Fermat, der lautet:

Ist n prim und m kein Vielfaches von n, so gilt:

mⁿ⁻¹ mod n = 1

Bei der Eulerschen Verallgemeinerung dieses Satzes gilt:

m^Φ(n) mod n = 1

für die teilerfremden natürlichen Zahlen m und n. Besonders für den RSA-Algorithmus ist der Fall von Bedeutung, in dem n das Produkt der beiden Primzahlen p und q ist:

m^{(p−1)(q−1)} mod pq = 1

Der Beweis von RSA erfolgt in mehreren Schritten. Zunächst machen wir uns klar, dass

c = m^e mod n
m' = c^d mod n = (m^e)^d mod n = m^ed mod n

ist. Die Dechiffrierfunktion von RSA arbeitet genau dann korrekt, wenn

m^ed mod n = m

für alle natürlichen Zahlen m gilt.

1. Schritt. Es gilt:

m^ed mod p − m mod p = 0
(m^ed − m) mod p = 0

Warum ist das so? Wir erinnern uns, dass e und d so gewählt wurden, dass

ed mod Φ(n) = 1

gilt. Daher gibt es auch eine Zahl k mit

ed = 1 + k · Φ(n)

Zur Erläuterung: Durch eine Modulo-Operation erhält man ja nur den Rest, der bei der Division durch eine Zahl anfällt. In diesem Fall ist der Rest 1; addiert man zu diesem Rest das Produkt der Zahlen k und Φ(n), erhält man das Produkt von e und d. Nun wollen wir den Satz von Euler anwenden; dieser erfordert jedoch, dass m und p teilerfremd sind. Dies ist selbstverständlich nicht immer der Fall. Wenn m und p nicht teilerfremd sind, ist p notwendigerweise eine Teiler von m. Das bedeutet:

m mod p = 0

Wenn p ein Teiler von m ist, ist p auch ein Teiler von m^ed. Also gilt:

(m^ed − m) mod p = 0

da p sowohl m^ed als auch m teilt. Wir folgern daraus: Wenn ggT(m, p) ungleich 1 ist, gilt unsere Behauptung in diesem Spezialfall. Wenn m und p teilerfremd sind, besagt der Satz von Euler:

m^Φ(p) mod p = 1

Für Φ(p) = p − 1 ergibt sich nun:

m^ed mod p = m^1+k·Φ(n)
= m · m^k·Φ(n) mod p
= m · m^{k·(p−1)(q−1)} mod p
= m · (m^p−1)^k·q−1 mod p

Zur Erläuterung: Wir haben also ein bisschen umgestellt, so dass wir nun den Satz von Euler direkt auf m^p−1 anwenden können (es ist durchaus erlaubt, innerhalb dieser Klammer eine Modulo-Operation durchzuführen):

= m · (m^p−1 mod p)^k·q−1 mod p
= m · 1^k·(q−1) mod p
= m mod p

Unsere zu Anfang gestellte Behauptung gilt also für alle natürlichen Zahlen m, gleich, ob ggT(m, p) gleich oder ungleich 1 ist.

2. Schritt. Nun erfolgt die Beweisführung für q; da dieser Schritt analog zu Schritt 1 verläuft, sei hier auf eine ausführliche Darstellung verzichtet. Nun fassen wir diese beiden Schritte zusammen.

3. Schritt. Da die beiden Primzahlen p und q die Zahl

z = m^ed − m

teilen (was wir in den beiden vorherigen Schritten bewiesen haben), teilt auch ihr Produkt n die Zahl z. Also gilt:

m^ed mod pq = m
m^ed mod n = m

Somit haben wir die Aussage des Satzes bewiesen: Der Dechiffrieralgorithmus arbeitet korrekt.

Die Ausführungen dieses Beweises stammen zum großen Teil aus dem Buch "Kryptologie" von Albrecht Beutelspacher.

Zurück zum Hauptartikel über RSA