Cryptography Reference
In-Depth Information
Somit ist (4.1-15) insgesamt und damit auch (4.1-14) erfüllt. Der Beweis lässt sich auch füh-
ren, wenn n nur einen oder mehr als zwei Primfaktoren enthalten würde, die paarweise je ver-
schieden sind.
Potenzen mit Periode (n)
Aus (4.1-13) bzw. (4.1-14) ist zu ersehen, dass die Potenzen von a periodisch in (n) sind. Die
Eulersche Phi-Funktion kann deshalb auch als
Periode (n)
: bezeichnet werden. Die Periode
der Potenzen gilt nur für Elemente a, wenn die Kriterien „der Modul enthält nur ungleiche
Primfaktoren“ oder „a und n sind teilerfremd“ erfüllt sind.
4.1.2.4
Beispiele für Euler/RSA
Die Sätze (Theoreme) von Euler und Fermat sollen an weiteren Beispielen illustriert werden.
In Tab. 4-2 ist die Folge der Potenzen aus GF(7) aufgelistet. Der Modul n=p=7 ist eine Prim-
zahl. Man beachte: In der Zeile a
6
stehen für a0 nur Einsen, den Sätzen von Euler und Fermat
entsprechend. Die Zeilen für a
1
und a
7
sind gleich. Es zeigt sich die Periode (p)=p-1=6 der
Potenzen a
i
a
(i)mod (n)
(mod n) nach (4.1-13).
Die Zeile a
5
gibt für a0 die multiplikativ inversen Elemente a
1
an. Entsprechend (4.1-12) ist
a
(n)1
=a
61
a
1
. In Tab. 4-2 ist zu sehen, dass die Eigenschaft multiplikativ inverser Elemente
a
1
·a1 erfüllt ist.
Auf die Jacobi-Funktion in Zeile a
3
wird in Kap. 4.1.5 eingegangen.
Tab. 4-2: Folge der Potenzen, Modul n=7, Elemente a
[0, 6] aus GF(7), Periode (7)=6
a = a
1
0
1
2
3
4
5
6
a
2
0
1
4
2
2
4
1
a
3
Jacobi: a
(p-1)/2
0
1
1
6
1
6
6
a
4
0
1
2
4
4
2
1
a
5
a
-1
a
-1
, multiplikativ invers zu a
0
1
4
5
2
3
6
a
6
Euler/Fermat: a
=a
p-1
=a
6
1
0
1
1
1
1
1
1
a
7
a
7
a
1
, Periode (p)=p-1=6
0
1
2
3
4
5
6
a
8
0
1
4
2
2
4
1
In dem folgenden Beispiel Tab. 4-3 besteht der Modul n=6 aus zwei unterschiedlichen Prim-
faktoren. Es ist (6)=(3·2)=(31)·(21)=2. Die Bedingung für RSA ist erfüllt. Die Periode
a
3
=a
(6)+1
a
1
gilt offensichtlich für alle Elemente a. Der Eulersche Satz a
=a
2
1 ist nur für die
Elemente a=1 und a=5 erfüllt, welche teilerfremd zu n=6 sind.
