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




Custom Search