Cryptography Reference
In-Depth Information
7.1.6 Zur Sicherheit von RSA
Wir versetzen uns nun die Lage eines Angreifers
A
:
e
C
=
N
(
n
,
e
)
S
R
A
Ein Angreifer
A
, dem ein Geheimtext
C∈
Z
n
des Senders
S
an den Empfänger
R
in die Hände gerät, erhält den Klartext
N
durch Lösen eines der folgenden
Probleme:
•
Bestimme den geheimen Schlüssel
d
, d. h. die Lösungsmenge der Kongru-
enzgleichung:
eX
≡
1
(
mod
ϕ
(
n
))
.
Dazu muss der Angreifer
ϕ
(
n
)
kennen.
•
Bestimme die
e-te Wurzel
aus
C
in
Z
n
, d. h. die Lösung
N∈
Z
n
der Glei-
chung
X
e
=
C
.
Die Lösung der Gleichung
X
e
=
C
ist auch tatsächlich eindeutig bestimmt, da der
a
e
wegen Lemma 7.1 bijektiv ist, die Po-
Homomorphismus
ι
e
:
Z
n
→
Z
n
,
a
→
tenzabbildung
ι
e
. Damit ist das Ziehen der
e
-ten Wurzel das
Potenzieren mit
d
. Folglich sind die beiden geschilderten Probleme, vor denen
der Angreifer steht, ein und dasselbe Problem.
ι
d
ist das Inverse zu
Beim RSA-Verfahren sind, wie bereits erwähnt, neben dem geheimen Schlüssel
d
auch die Größen
p
,
q
und
ϕ
(
)
geheim zu halten, da ein Angreifer mit einer
dieser drei Größen aus dem öffentlichen Schlüssel
n
den geheimen Schlüssel
d
ermitteln kann. Wir zeigen nun, dass man mit der Kenntnis von
(
n
,
e
)
ϕ
(
)
die Prim-
teiler
p
und
q
von
n
ermitteln kann. Es sind nämlich
p
und
q
die zwei Nullstellen
eines Polynoms vom Grad 2 mit Koeffizienten, die von
n
und
n
ϕ
(
)
abhängen,
und die Nullstellen eines Polynoms vom Grad 2 sind einfach zu bestimmen.
n
Lemma 7.2
Aus n und
ϕ
(
)
n
können p und q als Nullstellen des Polynoms
X
2
f
=
−
(
n
−
ϕ
(
n
)+
1
)
X
+
n
bestimmt werden.
ϕ
(
)
Beweis.
Sind
n
und
n
bekannt, so kann das Polynom
X
2
f
=
−
(
n
−
ϕ
(
n
)+
1
)
X
+
n
∈
Z
[
X
]
