Cryptography Reference
In-Depth Information
7.3 RSA und das Faktorisierungsproblem *
=
Es seien in diesem Abschnitt stets
n
pq
mit verschiedenen Primzahlen
p
,
q
und Zahlen
e
,
d
so gewählt, dass ggT
er-
füllt sind. Kurz: Es seien
n
,
p
,
q
,
e
,
d
wie beim RSA-Verfahren gegeben. Ohne
Einschränkung setzen wir
e
(
e
,
ϕ
(
n
)) =
1 und
ed
≡
1
(
mod
ϕ
(
n
))
1 der geheime Schlüs-
sel, und das wäre auch jedem Angreifer klar. Wir begründen, dass die beiden
Probleme, nämlich
=
1 voraus; es wäre sonst
d
=
•
die Zahl
n
in seine Primfaktoren
p
und
q
zu zerlegen und
•
die Bestimmung von
d
aus dem öffentlichen Schlüssel
(
n
,
e
)
,
algorithmisch äquivalent sind (siehe Seite 64). Dazu werden wir jeweils einen
polynomialen Algorithmus angeben, der das eine auf das andere Problem zu-
rückführt.
Das
Faktorisierungsproblem
wird seit vielen Jahrhunderten als ein
schwieriges
Pro-
blem angesehen, d. h., man vermutet, dass es nicht in der Komplexitätsklasse
P
liegt. Ist das der Fall, dann ist es auch
schwierig
, den geheimen Schlüssel
d
aus
dem öffentlichen Schlüssel
zu bestimmen.
Man erkennt, dass die Sicherheit von RSA eng mit der Schwierigkeit der Faktori-
sierung ganzer Zahlen verknüpft ist.
(
n
,
e
)
7.3.1 Kenntnis von
p
und
q
liefert
d
(
)
Bekannt ist der öffentliche Schlüssel
. Wenn man die Zahl
n
faktorisieren
kann, d. h., wenn man die Primzahlen
p
und
q
mit
n
n
,
e
=
pq
bestimmen kann, so
erhält man hieraus den geheimen Schlüssel
d
wie der legitime Anwender.
Bestimme zuerst
ϕ
(
n
)=(
p
−
1
)(
q
−
1
)
.
≡
(
ϕ
(
))
Löse die Kongruenz
eX
1
mod
n
.
Die Lösung
d
mit 1
≤
d
≤
ϕ
(
n
)
ist der geheime Schlüssel.
Im nächsten Abschnitt zeigen wir die Umkehrung: Kennt man den geheimen
Schlüssel
d
, so erhält man aus dem öffentlichen Schlüssel
(
)
n
,
e
die Faktorisie-
rung
n
=
pq
von
n
.
7.3.2 Kenntnis von
d
liefert
p
und
q
Wir schicken demwesentlichen Ergebnis einen Hilfssatz voran. Wir schreiben für
Zahlen
a
,
m
∈
Z
mit ggT
(
a
,
m
)=
1 im Folgenden
o
(
a
)
mod
m
für die Ordnung von
Z
∈
Z
m
.
a
=
a
+
m