Cryptography Reference
In-Depth Information
9.3.2 Quadratwurzeln modulo
p
≡
3
(
mod 4
)
b
2
Z
p
,
a
Es sei
p
eine Primzahl kongruent 3 modulo 4. Ist
a
ein Quadrat in
=
∈
Z
p
, so gilt für das Element
a
p
+
1
∈
Z
p
≡
(
)
für ein
b
(wegen
p
3
mod 4
ist
4
+
p
1
∈
N
):
4
p
+
1
p
−
1
p
−
1
a
p
+
1
+
1
=
=
=
=
±
b
2
b
2
b
2
b
b
,
4
p
−
1
p
−
1
da nach dem Satz 6.9 (a) von Euler gilt
o
(
b
2
)
≤
2, d. h.
b
2
=
±
1. Es folgt, dass
das Element
a
p
+
1
∈
Z
p
a
p
:
=
4
±
eine Quadratwurzel des Quadra
te
s
a
modulo
p
ist. Damit sind
a
p
die beiden
(einzigen) Quadratwurzeln von
a
modulo
p
. Man erhält die Wurzeln modulo
einer Primzahl
p
≡
3
(
mod 4
)
somit durch
einfaches
Potenzieren. Das wird das
Rabin-Verfahren vereinfachen.
Bemerkung
Für Primzahlen
p
≡
(
)
5
mod 8
kann man Quadratwurzeln ebenfalls relativ ein-
≡
(
)
fach gewinnen. Im Fall
p
gibt es spezialisierte Algorithmen, wie
etwa den von Tonelli und Shanks. Mehr dazu ist in [7, § 1.5] zu finden.
1
mod 8
9.3.3 Das Verfahren
Das
Rabin-Verfahren
ist ein Public-Key-Verfahren. Der Empfänger
R
gibt seinen
öffentlichen Schlüssel bekannt und behält sich einen geheimen Schlüssel.
Schlüsselerzeugung.
Für die Schlüsselerzeugung geht
R
wie folgt vor:
≡
(
)
=
R
wählt zwei Primzahlen
p
und
q
mit
p
,
q
3
mod 4
und
p
q
.
Es ist
n
=
pq
der öffentliche Schlüssel.
Es ist
(
p
,
q
)
der geheime Schlüssel.
Der Teilnehmer
T
möchte an den Empfänger
R
eine Nachricht senden.
2
C
=
N
T
R
n
=
pq
