Cryptography Reference
In-Depth Information
Da jeder dieser vier Fälle mit der gleichen Wahrscheinlichkeit eintritt, ist
=
(
−
)
d
ggT
a
x
,
n
mit einer Wahrscheinlichkeit von 0.5 ein echter Teiler von
n
. Nach
r
Runden ist
die Zahl
n
also mit der Wahrscheinlichkeit von 1
r
−
(
)
1/2
in ihre Primfaktore
n
zerlegt.
Damit ist begründet, dass die beiden Probleme,
•
n
zu faktorisieren und
•
Quadratwurzeln modulo
n
zu bestimmen,
(probabilistisch) algorithmisch äquivalent sind.
Bemerkung
Das Rabin-Verfahren kann durch einen
Chosen-Cipher-Text
-Angriff gebrochen
werden.
E
in Angreifer
A
wählt ein
x
∈{
1, . . . ,
n
−
1
}
und lässt d
en
Geheim-
x
2
von
R
entschlüsseln. Dabei erhält
A
die Quadratwurzel
a
modulo
n
von
R
als mutmaßlichen Klartext zurück. Wie im Beweis zu Lemma 9.3 bestimmt
nun
A
mit einer Wahrscheinlichkeit von 0.5 einen Primteiler von
n
, indem er den
ggT der Zahlen
n
und
a
C
=
text
x
bestimmt. Wiederholt
A
den Angriff nur oft genug,
so erhält
A
die Primfaktoren
p
und
q
. Auch wegen dieses Angriffs ist das Rabin-
Verfahren für die Praxis nicht relevant.
−
Aufgaben
9.1
Der Empfänger
E
erhält den ElGam
a
l-
Ch
iffretext
(
B
,
c
)=(
6, 6
)
. Der öffent-
(
)=(
)
liche Schlüssel von
E
ist
p
,
g
,
A
13, 2, 11
. Bestimmen Sie den zugehörigen
Klartext.
=
589 ein öffen
tlich
er Schlüssel beim Rabin-Verfahren. Bestimmen
Sie aus dem Geheimtext
9.2
Es sei
n
C
=
442 alle möglichen Klartexte.
=
124573 der öffentliche Schlüssel beim Ra
bin
-Verfahren. Ein An-
greifer lässt bei einem
Chosen-Cipher-Text
-
Angriff
den Text 113
2
entschlüsseln und
erhält dabei den mutmaßlichen Klartext 110459 zurück. Bestimmen Sie hiermit
die Primfaktorzerlegung von
n
.
9.3
Es ist
n