Cryptography Reference
In-Depth Information
Falls 2
β
gilt, so folgt 2
|
α
und damit analog zum obigen Fall:
a
k
g
k
)
α
)
mod
p
<
g
k
a
k
(
)
mod
p
=
((
(
)
mod
p
=
(
)
mod
q
.
o
o
o
o
a
k
a
k
)
mod
q
.
Die Wahrscheinlichkeit dafür, dass man nach
r
Iterationen (bei zufälliger Wahl
von
a
) einen Faktor von
n
gefunden hat, ist also größer als 1
(
)
mod
p
=
(
In jedem Fall gilt also
o
o
1
−
2
r
. Nach 10 Ite-
rationen hat man mit einer Wahrscheinlichkeit von mehr als 99.9 Prozent einen
Faktor von
n
bestimmt.
Tatsächlich erhält man mit dieser Methode nur
sehr wahrscheinlich
eine Faktori-
sierung der Zahl
n
. Aber die Wahrscheinlichkeit ist beliebig groß, man muss nur
hinreichend oft iterieren. Einen Algorithmus, der mit beliebig hoher Wahrschein-
lichkeit ein richtiges Ergebnis liefert, nennen wir
probabilistisch.
Bemerkung
Ein probabilistischer Algorithmus kann auf zwei Weisen scheitern:
•
Er findet
kein
Ergebnis oder
•
er liefert ein
falsches
Ergebnis
- beides mit kleiner Wahrscheinlichkeit.
Wir halten fest:
Korollar 7.9
Aus n, e und d können p und q in polynomialer Zeit ermittelt werden.
Wir haben begründet, dass die beiden Probleme,
(
)
•
d
aus
n
,
e
zu bestimmen und
•
n
zu faktorisieren,
gleich schwer zu lösen sind. Weil das Problem, eine Zahl
n
zu faktorisieren, schon
seit Jahrhunderten als ein
schwieriges
Problem in der Mathematik erachtet wird
(evtl. nicht in der Komplexitätsklasse
P
liegt), haben wir hiermit gezeigt, dass
das Berechnen des geheimen Schlüssels
d
aus dem öffentlichen Schlüssel
)
beim RSA-Verfahren ebenfalls als
schwierig
anzusehen ist. Es ist aber bisher nicht
gelungen zu zeigen, dass das Brechen des RSA-Verfahrens äquivalent zum Fak-
torisieren von
n
ist - man kann ja eventuell ohne Kenntnis von
d
entschlüsseln.
Aber es wird vermutet, dass dem nicht so ist.
(
n
,
e
Bemerkung
Man sagt genauer, dass die beiden Probleme probabilistisch algorithmisch äqui-
valent sind. Nach [17] gibt es einen
deterministischen,
d. h. nicht probabilisti-
schen polynomialen Algorithmus, der aus der Kenntnis von
d
eine Faktorisierung
von
n
errechnet. Daher sind die beiden Probleme algorithmisch äquivalent.
