Cryptography Reference
In-Depth Information
Beispiel:
3
3
=3 (mod 6), da 3=1 (mod (
ϕ
(6))
Mit diesem Satz können wir nun die
a
-te Modulo-Wurzel einer Zahl berechnen.
Gesucht ist zu gegebenem
a
,
b
und
n
eine Zahl
x
, für die gilt:
x
a
=
b
(mod
n
).
Wenn
a
und
(
n
) teilerfremd sind, dann kann man mit dem euklidischen Algo-
rithmus die Zahl
c
=
a
-1
(mod
ϕ
(
n
)) berechnen. Mit dieser Zahl exponieren wir
jetzt beide Seiten der Gleichung:
(
x
a
)
c(mod ϕ (n))
=
b
c(mod ϕ (n))
(mod
n
).
ϕ
Durch die Anwendung des obigen Satzes können wir die rechte Seite vereinfa-
chen:
(
x
a
)
c(mod ϕ (n))
=
b
c
(mod
n
).
Da
a
·
c
= 1 (mod
(
n
)), erhalten wir auf der linken Seite:
x
1(mod ϕ(n))
=
b
c
(mod
n
).
ϕ
Dies ist nach obigem Satz wiederum:
x
=
b
c
(mod
n
)
Nun kennen wir die Zahl
x
, die ja die gesuchte
a
-te Wurzel von
b
ist. Damit
x
existiert, müssen
a
und
ϕ
(
n
) teilerfremd sein. Ist dies der Fall und kennt man
ϕ
(
n
),
so ist die Wurzel problemlos zu berechnen. Dass
(
n
) jedoch oftmals alles andere
als einfach zu berechnen ist, werden Sie im nächsten Kapitel sehen.
ϕ
Gruppen und Körper
In der Mathematik und in der Kryptografie sind solche Werte von
n
besonders
interessant, für die alle Zahlen zwischen 1 und
n
-1 ein inverses Element (mod
n
)
haben. Damit dies der Fall ist, müssen alle Zahlen zwischen 1 und
n
-1 teilerfremd
zu
n
sein. Diese Anforderung ist genau dann erfüllt, wenn
n
eine Primzahl ist (ich
schreibe in einem solchen Fall
p
statt
n
). Ist
p
also eine Primzahl, dann ist jede
Zahl zwischen 0 und
p
-1 durch jede Zahl zwischen 1 und
p
-1 modulo
p
teilbar
(die Division durch 0 ist wie üblich nicht definiert).
Die Zahlen zwischen 1 und
p
-1 bilden mit der Modulo-Multiplikation eine
sogenannte
Gruppe
, die wir als
Z(p,·)
bezeichnen. Eine Gruppe ist in der Mathe-
matik eine Menge, für die folgende Voraussetzungen gegeben sind:
■
Es ist eine Verknüpfung definiert (in diesem Fall ist dies die Modulo-Multipli-
kation). Dass eine Verknüpfung definiert ist, bedeutet, dass man zwei belie-
bige Elemente der Gruppe miteinander verknüpfen kann und dabei stets ein
