Sei N = p*q (p,q prim), e teilerfremd zu (p-q)*(q-1), d Element der natürlichen Zahlen mit e*d mod (p-1)*(q-1), dann gilt:
x^(e*d) mod N = x mod N für alle x.

Sei p eine Primzahl und a Element der natürlichen Zahlen mit ggT(p, a)=1, dann gilt: a^(p-1) mod p = 1

Es gibt Zahlen x, y Element der rationalen Zahlen mit ggT(a, b) = x*a + y*b (Linearkombination von a und b).

Allg: a>b (oBdA)
a-s_1*b = r_1
b-s_2*r_1 = r_2
r_1-s_3*r_2 = r_3
...
r_(n-2) - s_n * r_(n-1) = r_n (-> ggT)
r_(n-1) - s_(n+1) * r_n = 0

Ziel: r_n = x*a + y*b

r_n = r_(n-2) - s_n * r_(n-1) = 1* r_(n-2) + (-s_n) * r_(n-1) <- r_(n-1) einsetzen
= (-s_n) * r_(n-3) + (1 + s_n * s_(n-1) ) * r_(n-2) <- r_(n-2) einsetzen
..usw..

a*x + b*y = 1
a*x + b*y=1 = a*x mod b

x^(e*d) mod N = x mod N für alle x.

Ein Produkt aus zwei nicht-trivialen natürlichen Zahlen ist immer größer als Eins, wodurch kein Inverses gebildet werden kann. Durch die Verwendung von Modulo kann dieses Problem jedoch umgangen und ein sogenanntes modulares multiplikatives Inverses gefunden werden:

a,b,n aus N
a*b mod n = 1

Jedoch trifft die Gleichung nur für bestimmte natürlichen Zahlen zu. Um nun diese möglichen Zahlen zu errechnen, nimmt man den Satz von Euler zur Hilfe, der lautet:

a^φ(n) mod n = 1

Durch die Umschreibung des Satzes in die Vielfachsummendarstellung entsteht die Gleichung k*φ(n)+1, mit deren Hilfe die Schlüsselinformationen durch Gleichsetzung definiert werden können. e steht hier für encrypt (engl. Verschlüsseln) und d für decrypt (engl. Entschlüsseln):

e*d = k*φ(n)+1


Der Satz von Euler ist allerdings nur eine Verallgemeinerung des Satzes von Fermat, der nur gilt, wenn p eine Primzahl ist:

a^(p-1) mod p = 1

Potenziert man die Kongruenzgleichung mit k und multipliziert danach mit a erhält man:

a^(k(p-1)) mod p=1^k mod p
a^(k(p-1)(*a mod p=1^(k*a) mod p
a^(k(p-1)+1) mod p=1^(k*a) mod p

Wendet man nun den Satz von Fermat auf eine zweite Primzahl q an, lässt sich die enstehende Gleichung mit der vorherigen multiplizieren:

a^(k(p-1)+1) mod q=(1^k)*a mod p
a^(q-1) mod q=1 mod q

a^(k(p-1)(q-1)+1) mod pq =(1^k)*a mod pq

Wenn man nun n aus der Gleichung der Schlüsselinformationen ( e*d=k*φ(n)+1) als das Produkt zweier Primzahlen p und q definiert, kann man sie in die neue Gleichung einsetzten:

e*d = k*φ(n)+1
e*d = k*(p-1)(q-1)+1

a^(k(p-1)(q-1)+1) mod pq=(1^k) *a mod pq
a^(e*d) mod pq= (1^k)*a mod pq

Da 1^k keinen Einfluss auf das Ergebnis hat, kann es als Faktor vernachlässigt werden. Definiert man a nun als numerischen Repräsentanten M eines Buchstabens, erhält man eine Kongruenzgleichung, die einem vollständigen kryptographischem Verfahren entspricht:

M^(e*d) mod pq = M

Aus dieser Gesamtgleichung lassen sich nun die Gleichungen für Ver- und Entschlüsselung ableiten. C entspricht dem Chiffrat, M dem Buchstaben und n dem Produkt aus pq:

C = M^e mod n
M = C^d mod n