Cryptography Reference
In-Depth Information
Es bleibt, die Dechiffrierbedingung aus Definition 6.1.1 zu überprüfen. Das folgende
Lemma zeigt, dass diese Bedingung in der Tat erfüllt ist.
Lemma 6.4.1.
Es sei
(
n, p, q, m, e, d
)
ein RSA-Tupel. Dann gilt
D
(
E
(
x,
(
n, e
))
,
(
n, d
)) =
x
für alle
x ∈
Z
n
.
Beweis.
Wir müsssen zeigen, dass
(
x
e
)
d
mod
n
=
x
(6.4.1)
für alle
x
∈
Z
n
gilt. Wir führen eine Fallunterscheidung durch und beginnen mit dem
Fall
x ∈
Z
n
. Dann gilt zunächst:
(
x
e
)
d
mod
n
=
x
ed
mod
n
(*
=
x
ed
mod
m
mod
n
(**
=
x
1
=
x,
(6.4.2)
|
Z
n
|
wobei (*) aus (6.3.1) folgt und der Tatsache, dass
m
=
ist. Wir erhalten (**) aus
der Voraussetzung
e
·
d
mod
m
=1
.
∈
Z
n
unterscheiden wir die folgenden drei Fälle:
x
=0
;
x
Für
x/
=0
und
p
|
x
;
x
=0
und
q
x
.
Der Fall
x
=0
ist trivial. Die beiden anderen Fälle sind symmetrisch zueinander, so
dass wir uns auf
x
|
x
beschränken können.
Wir benutzen den Chinesischen Restsatz (Satz 6.3.1) und zwar mit
a
=
p
und
b
=
q
(nach Annahme sind
p
und
q
verschiedene Primzahlen, so dass die Voraussetzungen des
Satzes erfüllt sind). Es sei
h
der Isomorphismus aus dem Chinesischen Restsatz. Dann
ist
h
(
x
)=(0
,y
)
,mit
y
=
x
mod
q
. Es gilt
y
=0
und
p
|
∈
Z
q
wegen
p
|
x
und
x
=0
.Analogzu
Z
q
:
(6.4.2) erhalten wir nun in
(
y
e
)
d
mod
q
=
y
ed
mod
q
=
y
ed
mod
q−
1
mod
q
(*
=
y
(
ed
mod
m
) mod
q−
1
mod
q
=
y
1
=
y,
(6.4.3)
wobei wir in (*) nutzen, dass für alle
c ∈
Z
und alle
a, b ≥
1
mit
a | b
gilt:
c
mod
a
=
(
c
mod
b
)
mod
a
.
Aus (6.4.3) ergibt sich nun in
Z
p
×
Z
q
:
((0
,y
)
e
)
d
=(0
,y
)
, wobei die Exponentiation als
Opertionen im Ring
Z
p
×
Z
q
betrachtet wird. Dies überträgt sich, nach dem Chinesische
n
Restsatz, in den Ring
Z
n
,was
(
x
e
)
d
mod
n
=
x
liefert.
S
RSA
ein deterministisches Kryptoschema. Gemäß Satz 6.2.1 ist
S
RSA
somit unsicher. RSA ist auch aus einem anderen Grund als asymmetrisches Krypto-
schema ungeeignet: Das Jacobi-Symbol des Klartextes überträgt sich auf den Chiffretext.
Der Chiffretext liefert also (nicht-triviale) Information über den Klartext. Dies wird im
folgenden Lemma präzisiert, in dem die am Ende von Abschnitt 3.3 eingeführte Notation
verwendet wird.
Offensichtlich ist
Lemma 6.4.2 (Jacobi-Symbol und RSA).
Es sei
(
n, p, q, m, e, d
)
ein RSA-Tupel. Dann