Cryptography Reference
In-Depth Information
Verschlüsselung.
Der Teilnehmer
T
geht für die Chiffrierung seines Klartextes
N
wie folgt vor:
T
besorgt sich den öffentlichen Schlüssel
n
von
R
.
Z
n
dar, d. h.
N∈
Z
n
.
T
stellt seinen Klartext
N
als Element von
2
in
Z
n
.
T
berechnet den Geheimtext
C
=
N
C
T
sendet
an
R
.
C∈
Z
n
wegen
n
=
=
Man beachte, dass der Geheimtext
pq
,
p
q
, nach Lemma
Z
n
h
a
t. Der Klartext
9.1 vier Quadratwurzeln i
n
ist eine dieser vier Wurzeln.
Die vier Quadratwurzeln
b
1
,...,
b
4
modul
o
n
erhält man mit dem chinesischen
Restsatz aus den Quadratwurzeln
w
1
,...,
w
4
modulo
p
und modulo
q
(vgl. die
Bemerkung auf Seite 174). Und die Quadratwurzeln modulo
p
und modulo
q
sind einfach zu bestimmen, da
p
und
q
kongruent 3 modulo 4 sind.
N
Entschlüsselung.
Der Empfänger
R
geht zur Entschlüsselung des von
T
erhal-
tenen Geheimtextes
C
wie folgt vor:
+
+
1
p
1
q
∈
Z
p
und
a
q
=
C
∈
Z
q
=
C
±
R
b
erechnet
a
p
und erhält mit
a
p
und
4
4
±
C
a
q
die vier Quadratwurzeln von
modulo
p
und
q
.
±
R
ermittelt mit dem chinesischen Restsatz aus den vier Quad
r
atwur
ze
ln
a
p
±
C
C
modulo
p
und
a
q
modulo
q
von
die vier Quadratwurzeln
b
1
,...,
b
4
von
modulo
n
(vgl. die Bemerkung zu Lemma 9.1):
(
)
→
(
−
)
→
(
−
)
→
(
−
−
)
→
a
p
,
a
q
b
1
,
a
p
,
a
q
b
2
,
a
p
,
a
q
b
3
,
a
p
,
a
q
b
4
.
N
R
entscheidet, welche der vier Wurzeln
b
1
,...,
b
4
der Klartext
ist.
Bemerkung
Die Entschlüsselung liefert neben einem richtigen drei falsche Ergebnisse. Das ist
ein entscheidender Nachteil des Rabin-Verfahrens. Man könnte die Entschlüsse-
lung eindeutig machen, indem man nur Klartexte mit einer bestimmten Struk-
tur zulässt. Aber dadurch würde dann das Rabin-Verfahren nicht mehr algorith-
misch äquivalent zum Faktorisierungsproblem sein (siehe Abschnitt 9.3.4).
Beispiel
Es seien
p
=
=
=
3 und
q
7. Damit ist
n
2
1 d
er öffentliche Schlüssel von
R
. Der
∈
Z
21
senden und berechnet dazu
Teilnehmer
T
will an
R
die Nachricht
N
=
10
10
2
C
=
=
=
100
16 .
R
erhält von
T
den Geheimtext
C
=
16 und ermittelt mittels der (geheimen) Prim-
zahlen
p
=
3 und
q
=
7 die vier Quadratwurzeln von 16 modulo 21; es gilt:
+
+
p
1
q
1
16
2
∈
Z
3
∈
Z
7
16
4
=
16
=
1
und 16
4
=
=
4
.
