Cryptography Reference
In-Depth Information
Modulo-Operation für den Exponenten
Aus dem Kleinen Satz von Fermat (a
p1
a
0
1) folgt, dass im Exponenten der Wert (p1) be-
liebig oft addiert oder subtrahiert werden darf, ohne die Kongruenz zu verändern. Das heißt,
wir dürfen auf den Exponenten modulo (p1) anwenden:
a
j
a
( j) od (p
1)
(mod p)
für
a
0
und
ggT(p, a)
1
(4.1-11)
Entsprechend folgt verallgemeinernd aus dem Satz von Euler, dass auf den Exponenten die
Operation modulo (n) angewendet werden darf.
Multiplikativ inverses Element a
1
aus a berechnen
Den Satz von Euler kann man nutzen, um für a das multiplikativ inverse Element a
1
zu be-
rechnen. Wenn man (4.1-9) mit a
1
multipliziert, ergibt sich:
1
-
(n ) 1
(4.1-12)
Die Berechnung von a
1
durch Potenzierung von a ist eine Alternative zu dem erweiterten
Euklidischen Algorithmus (Kap. 2.1.3.1). Das Verfahren ist anwendbar, wenn a und n teiler-
fremd sind (n selbst braucht nicht prim sein) und die Faktorisierung des Moduls bekannt ist.
a
a
(mod n)
für
a
0
und
ggT(n, a)
1
4.1.2.3
Sonderfall für RSA
Wenn man (4.1-9) mit i potenziert und dann mit a multipliziert, dann ergibt sich.
a
i
-
(n)1
a
(mod n)
für
a
0
und
ggT(n, a)
1
(4.1-13)
Wir wählen als Modul n=p·q das Produkt von zwei unterschiedlichen Primzahlen pq. Dann
müssen a und n nicht mehr teilerfremd sein. Der Sonderfall für
RSA
lautet:
i
-
(n)1
(a
) mod n
a
für
0
&
a
n
und
n
p q,
p
q
(4.1-14)
Es sind hier für a alle Werte 0a<n zugelassen. Letztere Verallgemeinerung ist noch zu bewei-
sen. Die Form (4.1-14) stellt die Basis für den RSA-Algorithmus dar (Kap. 4.2).
Beweis
Noch zu beweisen ist die Gültigkeit von (4.1-14) für die neuen Bereiche: „a=0“, „a ist Vielfa-
ches von p“ und „a ist Vielfaches von q“. Für den Nachweis formen wir (4.1-14) um in:
i
-
(n)1
a
a
0
(mod n)
für
a
[0, n
1]
und
n
p q,
p
q
(4.1-15)
Für a=0 sind a und alle Potenzen von a gleich 0. Beide Seiten sind damit 0 und (4.1-15) ist
erfüllt (der Fall a=0 ist übrigens bereits für beliebige n in (4.1-13) erfüllt).
Wenn a ein Vielfaches von p ist, dann sind a und alle Potenzen von a modulo p gleich 0. Die
linke Seite von (4.1-15) ist damit durch p teilbar. Der entstehende Rest 0 ist auch durch q teil-
bar. Entsprechendes gilt in gleicher Weise für q. Wenn die linke Seite von (4.1-15) sowohl
durch p als auch durch q teilbar ist, dann ist sie auch durch das Produkt n=p·q teilbar, da p und
q keine gemeinsamen Faktoren haben.
Die Kongruenz in (4.1-15) gilt für beliebige a>0. Die Einschränkung von a auf a
[0, n1] in
(4.1-14) ist notwendig, um die Mehrdeutigkeit der Kongruenz in (4.1-14) auszuschließen.
