RSA | MathePrisma

RSA

Satz von Euler

Asymmetrie

Einweg

RSA

Knacken

Literatur

Zur einfachen Formulierung des Satzes brauchen wir die Eulersche Funktion.

$\phi(n)$

Für eine natürliche Zahl $n$ ist $\phi(n)$ die Anzahl der natürlichen Zahlen $\le n$ , deren größter gemeinsamer Teiler mit $n$ gleich 1 ist, d.h. die zu $n$ teilerfremd sind. Die Funktion $\phi$ heißt Eulersche Funktion.

Da eine Primzahl $p$ teilerfremd zu allen Zahlen $1, 2, 3, ..., p-1$ ist, gilt:

p prim

Ist $p$ eine Primzahl, so ist

$\phi(p) = p-1 .$

Der Satz von Euler lautet nun:

Satz von Euler

Sind $m$ und $n$ zwei natürliche teilerfremde Zahlen, so gilt

$m^{\phi(n)} \bmod n = 1 .$

Ein interessanter Spezialfall (den man auch zum Beweis der Korrektheit der Entschlüsselung verwenden kann):

p, q prim

Sind $p$ und $q$ zwei (verschiedene) Primzahlen, so ist

$\phi(p\cdot q) = (p-1)(q-1) .$

Ist $m$ teilerfremd zu $p\cdot q$ , so gilt (nach dem Satz von Euler)

$m^{(p-1)(q-1)} \bmod p q = 1 .$