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
Search WWH ::




Custom Search