Cryptography Reference
In-Depth Information
7.2.4 Optimierung des Entschlüsselns mit dem chinesischen Restsatz
Erhält der Empfänger
R
den Geheimtext
c
pq
, so entschlüsselt
dieser den Geheimtext mit seinem geheimen Schlüssel
d
zu dem Klartext
=
C∈
Z
n
,
n
=
N
, in-
d
C
=
N
Z
n
bildet. Dabei bestimmt
R
die kleinste positive
dem er die Pote
n
z
in
Zahl
a
∈
N
mit
a
=
N
:
c
d
≡
(
)
.
Die Zahl
n
ist beim RSA-Verfahren üblicherweise mindestens 1024 Bit lang, daher
ist diese Rechnung sehr aufwändig. Mithilfe des chinesischen Restsatzes können
wir das Entschlüsseln effizienter gestalten:
a
mod
n
Berechne die kleinsten positiven Zahlen
a
p
,
a
q
mit
c
d
und
c
d
≡
(
)
≡
(
)
a
p
mod
p
a
q
mod
q
.
Bestimme mit dem Lösungsverfahren für Systeme von Kongruenzgleichun-
gen die kleinste positive Lösung
x
des Systems
X
≡
a
p
(
mod
p
)
und
X
≡
a
q
(
mod
q
)
.
Die Lösung
x
liefert den Klartext, d. h.
x
=
N
.
Denn:
Aus
x
≡
a
p
(
mod
p
)
und
x
≡
a
q
(
mod
q
)
folgt
c
d
c
d
≡
(
)
≡
(
)
x
mod
p
und
x
mod
q
,
c
d
u
n
d
q
c
d
, wegen der Teilerfremdheit von
p
und
q
und daher gilt
p
|
x
−
|
x
−
c
d
,d.h.
x
c
d
d
=
|
−
=
=
C
=
N
folgt
n
pq
x
.
Bemerkung
Ist
n
eine
k
-Bit-Zahl, so haben
p
und
q
etwa
k
/2 Bit. Modulo
n
kostet das Ent-
schlüsseln
Ck
2
cCk
3
,
c
,
C
(
)(
)=
∈
R
>
0
, 1.5
≤
≤
2,
Grundoperationen. Nach den Lemmata 6.15 und 4.3 sind nämlich bei der schnel-
len Exponentiation
ck
Multiplikationen, die je
Ck
2
Grundoperationen (
C
eine
Konstante) benötigen, durchzuführen. Die Abschätzung für
c
ergibt sich aus der
Bemerkung gleich im Anschluss an den Beweis von Lemma 6.15.
Dechiffriert man nun wie geschildert mit dem chinesischen Restsatz, so sind zwei
Potenzen modulo
p
und
q
zu bilden, die Kosten dafür sind
2
c
k
2
ck
c
C
k
2
2
cC
k
3
4
=
,
Grundoperationen. Dabei haben wir das Anwenden des chinesischen Restsatzes
vernachlässigt, weil er - wie der euklidische Algorithmus -
O
k
2
(
)
Laufzeit hat.
Durch diese (grobe) Analyse erhalten wir, dass das Entschlüsseln einer Nachricht
mit dem chinesischen Restsatz um etwa den Faktor 4 schneller ist.
