Das RSA-Verfahren: Mathematische Grundlagen.

Wir bezeichnen im folgenden mit dem Wort "Zahl" ausschließlich eine nicht-negative ganze Zahl.

Def. 1 : Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch sich selbst und durch 1 ohne Rest teilbar ist.

Ohne Beweis benutzen wir den folgenden

Satz 1: Jede natürliche Zahl größer als 1 läßt sich eindeutig als Produkt von Potenzen von Primzahlen schreiben.

Def. 2 : Eine Zahl a heißt Teiler einer Zahl b (geschrieben: a | b , gelesen: "a ist Teiler von b ", oder kürzer: " a teilt b "), wenn eine Zahl q mit q · b = a existiert.

Die Menge T (a) : = { x | x | a } heißt die Teilermenge von a .

Zwei Zahlen a und b heißen teilerfremd , wenn T(a) Ç T(b) = {1} ist.

Def. 3 : Seien n und m zwei natürliche Zahlen. Dann bezeichnet r := m mod n (gelesen: "m modulo n" den ganzzahligen Rest bei der Division von m durch n . Man sagt auch, r sei die "Reduktion von m modulo n" .

Satz 2 : Addition, Subtraktion und Multiplikation natürlicher Zahlen m und n sind mit ihrer Reduktion modulo einer natürlichen Zahl q vertauschbar:

(m + n) mod q = m mod q + n mod q,

(m n) mod q = m mod q · n mod q usw.

Beweis: folgt aus der Definition.

Satz 3 : Seien a und m teilerfremde natürliche Zahlen, und sei f (m) die Anzahl der zu m teilerfremden Zahlen kleiner gleich m .

Dann gilt

a ^{f (m)} = 1 mod m .

Beweis: Seien die zu m teilerfremden Zahlen r₁ , r₂ , r₃ , ... r_f(m) . Ist a zu m teilerfremd, dann sind dies auch die Zahlen a r₁ , a r₂ , a r₃ , ... a r_f(m) als Produkte von zu m teilerfremden Zahlen. Sie sind auch paarweise inkongruent modulo m , denn aus a r_i = a r_j mod m folgt r_i = r_j mod m . Daher muß jede der Zahlen a r₁ , a r₂ , a r₃ , ... a r_f(m) gleich einer der Zahlen r₁ , r₂ , r₃ , ... r_f(m) kongruent modulo m sein. Multiplikation dieser Gleichungen und Division durch r₁ r₂ r₃ ... r_f(m) liefert die Behauptung.

Satz 4 : Ist eine natürliche Zahl a kein Vielfaches der Primzahl p , dann ist a ^p-1 = 1 mod p .

Beweis: Für eine Primzahl p ist f (p) = p -1, da alle Zahlen unterhalb p teilerfremd zu p sind. Damit wird

a ^p-1 = 1 mod p .

Für jedes natürliche a und für jede Primzahl p folgt damit auch

a ^p = a mod p .

Satz 5 : Seien p und q zwei Primzahlen und n = p · q . Sei x = r mod p und x = r mod q . Dann ist x = r mod n .

Beweis: Aus der Voraussetzung folgt, daß x - r = k p = l q mit ganzen Zahlen k und l sein muß. Nach Satz 1 muß dann aber k ein Vielfaches von q sein und damit

x = r mod p · q = r mod n

gelten.

Satz 6 : Seien p und q zwei Primzahlen und n = p · q . Dann gilt für jedes m £ n und jedes k :

m ^{k (p-1) (q-1) +1} = m mod n .

Beweis: Wenn p kein Teiler von m ist, dann ist nach Satz 4 m ^{p-1 =} 1 mod p . Daraus folgt, da p -1 Teiler von f (n) ist, daß m ^{k (p-1) (q-1) +1} = m mod p ist.

Ist p Teiler von m , dann ist m = 0 mod p und damit trivialerweise m ^{k (p-1) (q-1) +1} = m mod p . Das gleiche gilt, wenn man p durch q ersetzt. Nach Satz 5 gilt also die Behauptung für alle m , insbesondere auch für m £ n .

Korollar: Sei e teilerfremd zu f (n) und d so gewählt, daß e · d = 1 mod f (n) , dann gilt für jedes m £ n :

(m ^e) ^d = m ^{e · d} = m mod n .