Cryptography Reference
In-Depth Information
Es sind also
=
−
=
−
=
•
a
3
1 und
a
3
1
2 die Quadratwurzeln modulo 3 von 16 und
•
a
7
=
4 und
−
a
7
=
−
4
=
3 die Quadratwurzeln modulo 7 von 16.
Mit dem chinesischen Restsatz ermittelt man zu den vier Kombinationen
=(
)
=(
)
=(
)
=(
)
w
1
1, 4
,
w
2
1, 3
,
w
3
2, 4
,
w
4
2, 3
die vier Quadratwurzeln
=
=
=
=
b
1
4,
b
2
10 ,
b
3
11 ,
b
4
17 .
N
Der Klartext
ist also unter den vier Wurzeln 4, 10, 11, 17 zu suchen.
q
genau
(
p
−
1
)(
q
−
1
)
4
Z
pq
mit
p
Wir bemerken noch, dass es wegen Korollar 9.2 in
=
Quadrate gibt, sodass die Geheimtextmenge
umfangreich
ist.
9.3.4 Zur Sicherheit des Rabin-Verfahrens
C∈
Z
n
Ein Angreifer, der einen Geheimtext
abgefangen hat, steht vor dem Pro-
blem, die Quadratwurzeln von
zu bestimmen. Kann er die Zahl
n
faktorisieren,
d. h. die Primzahlen
p
und
q
bestimmen, so kann er ebenso wie der rechtmäßige
Empfänger
R
den Geheimtext
C
C
entschlüsseln. Interessant ist, dass hiervon auch
die Umkehrung gilt.
Lemma 9.3
Es seien p un
d
q verschiedene (ungerade) Prim
z
ahlen und n
p q. Kann man zu je-
dem Quadrat c modulo n eine Quadratwurzel a modulo n bestimmen, so kann man n
faktorisieren.
=
Beweis.
Man wähle zufä
l
lig
ei
ne Zahl
x
∈{
1,...,
n
−
1
}
. Ohne Einschrä
nk
ung
x
2
∈
Z
n
(
)=
=
gelte ggT
x
,
n
1. Zu
c
b
estimme man eine Quadratwurzel
a
mo-
dulo
n
mit
a
∈{
1,...,
n
−
1
}
: Es ist
a
eine der vier Quadratwurzeln modulo
n
von
c
, und es gilt
a
2
x
2
∈
Z
n
⇒
a
2
x
2
=
=
|
(
−
)=(
−
)(
+
)
pq
n
a
x
a
x
.
|
−
|∈{
−
}
Nun gibt es vier Möglichkeiten (beachte, dass
a
x
0, . . . ,
n
1
):
|
−
|
−
⇒
(
−
)=
p
a
x
,
q
a
x
ggT
a
x
,
n
n
,
p
|
a
+
x
,
q
|
a
+
x
⇒
ggT
(
a
−
x
,
n
)=
1,
|
−
|
+
⇒
(
−
)=
p
a
x
,
q
a
x
ggT
a
x
,
n
p
,
p
|
a
+
x
,
q
|
a
−
x
⇒
ggT
(
a
−
x
,
n
)=
q
.
