Cryptography Reference
In-Depth Information
aufgestellt werden. Und wegen
n
−
ϕ
(
n
)=
pq
−
(
p
−
1
)(
q
−
1
)=
p
+
q
−
1 gilt:
X
2
X
2
(
X
−
p
)(
X
−
q
)=
−
(
p
+
q
)
X
+
pq
=
−
(
n
−
ϕ
(
n
)+
1
)
X
+
n
.
Damit sind die Nullstellen von
f
die Primzahlen
p
und
q
.
Bemerkung
Kann man
n
in seine Primfaktoren
n
=
pq
zerlegen, so kann man
ϕ
(
n
)=
(
−
)(
−
)
ϕ
(
)
aus
n
berechnen, so
kann man nach Lemma 7.2 die Zahl
n
in ihre Primfaktoren zerlegen. Die beiden
Probleme,
n
zu faktorisieren und
p
1
q
1
berechnen. Und kann man umgekehrt
n
ϕ
(
)
n
zu bestimmen, sind also algorithmisch
äquivalent.
7.2 Der chinesische Restsatz
Um weitere Fragen zur Sicherheit des RSA-Verfahrens klären zu können, brau-
chen wir den sogenannten
chinesischen Restsatz
aus der Zahlentheorie. Dieser
Satz liefert ein Verfahren, effizient Systeme von Kongruenzgleichungen zu lö-
sen. Damit können durch RSA verschlüsselte Geheimtexte unter gewissen Vor-
aussetzungen gebrochen werden. Wir leiten in einem ersten Abschnitt den chi-
nesischen Restsatz her und ziehen dann wichtige Folgerungen für die Euler'sche
ϕ
-Funktion.
7.2.1 Der chinesische Restsatz
Es ist klar, dass das kartesische Produkt
R
=
R
1
×···×
R
n
von Ringen
R
1
,...,
R
n
mit den komponentenweisen Verknüpfungen
(
)+(
)=(
+
+
)
a
1
,...,
a
n
b
1
,...,
b
n
a
1
b
1
,...,
a
n
b
n
und
(
a
1
,...,
a
n
)
·
(
b
1
,...,
b
n
)=(
a
1
b
1
,...,
a
n
b
n
)
für
R
wieder einen Ring bildet.
Wir beschäftigen uns mit der umgekehrten Aufgabenstellung. Man gebe in dem
Ring
(
a
1
,...,
a
n
)
,
(
b
1
,...,
b
n
)
∈
Unterringe
U
1
,...,
U
n
an, sodass
R
=
(
R
,
+
,
·
)
U
1
×···×
U
n
gilt. Wir füh-
(
Z
m
,
+
·
)
∈
N
ren eine solche Zerlegung in ein
direktes Produkt
für den Ring
,
,
m
,
durch.
Lemma 7.3
Für paarweise teilerfremde r
1
,...,
r
n
∈
Z
ist
:
Z
→
Z
×···×
Z
r
n
r
1
···
r
n
r
1
ψ
r
n
Z
)
ein Ringisomorphismus (d. h. bijektiv und ein additiver und multiplikativer Homomor-
phismus).
k
+
r
1
···
r
n
Z
→
(
k
+
r
1
Z
,...,
k
+
