Cryptography Reference
In-Depth Information
als natürliche Zahl
dar, die kleiner ist als jeder im System verwendete Modul
n
. Bei Bedarf identifizieren wir die Zahl
N
N
mit einer Restklasse.
Wir gehen beispielhaft von der folgenden Situation aus: Drei Teilnehmer des
RSA-Verfahrens haben die drei öffentlichen Schlüssel
(
)
(
)
(
)
n
1
,3
,
n
2
,3
,
n
3
,3
, d. h.,
jeder der drei Teilnehmer benutzt das gleiche öffentliche
e
=
3, mit paarweise
N
teilerfremden
n
1
,
n
2
,
n
3
. Wird nun ein und dieselbe Nachricht
bezüglich der
drei öffentlichen Schlüssel
(
n
1
,3
)
,
(
n
2
,3
)
,
(
n
3
,3
)
zu den Geheimtexten
C
1
,
C
2
,
C
3
3
3
3
C
1
=
N
∈
Z
n
1
,
C
2
=
N
∈
Z
n
2
,
C
3
=
N
∈
Z
n
3
, so kann ein
verschlüsselt, d. h.
Angreifer aus den Geheimtexten
C
1
,
C
2
,
C
3
mithilfe des chinesischen Restsatzes
auf die Nachricht
N
schließen, ohne den Schlüssel
d
zu kennen.
Lemma 7.10
Es seien paarweise teilerfremde natürlichen Zahlen n
1
,...,
n
e
,e
∈
N
, gegeben. Für eine
natürliche Zahl a gelte
0
≤
a
<
n
1
,...,
n
e
. Es seien c
1
,...,
c
e
mit
a
e
a
e
c
1
≡
(
mod
n
1
)
,...,
c
e
≡
(
mod
n
e
)
bestimmt. Dann gibt es genau ein c
∈
N
mit
0
≤
c
<
n
1
···
n
e
und c
≡
c
i
(
mod
n
i
)
a
e
.
=
=
für i
1, . . . ,
e. Weiter gilt c
Beweis.
Nach dem chinesischen Restsatz 7.4 ist das Kongruenzensystem
(
∗
)
X
≡
c
1
(
mod
n
1
)
,...,
X
≡
c
e
(
mod
n
e
)
lösbar. Ist
x
eine Lösung des Systems, so ist nach Abschnitt 7.2.2 die Menge
x
+
···
n
e
Z
≤
<
n
1
die Lösungsmenge. Daher gibt es genau eine Lösung
c
mit 0
c
a
e
n
1
···
n
e
. Da außerdem
c
i
≡
(
mod
n
i
)
für
i
=
1, . . . ,
e
gilt, erhalten wir
c
≡
a
e
1,...,
e
. Somit sind
c
und
a
e
beides Lösungen des System
s
(
)
=
mod
n
i
für
i
c
,
a
e
a
e
.
(
∗
)
mit 0
≤
<
n
1
···
n
e
. Es folgt
c
=
Man beachte, dass genau die oben geschilderte Situation vorliegt. Ein Angreifer,
dem die Geheimtexte
e
e
c
1
=
C
1
=
N
∈
Z
n
1
,...,
c
e
=
C
e
=
N
∈
Z
n
e
vorliegen, die ein und dieselbe Nachricht
darstellen und die mit jeweils dem
gleichen Verschlüsselungsexponenten
e
erhalten wurden, kann mit dem chinesi-
schen Restsatz die natürliche Zahl
c
N
a
e
bestimmen, für die gilt
a
=
=
N
. Ent-
scheidend ist, dass
c
eine
e
-te Potenz in
ist. Daher kann man die
e
-te Wurzel
in polynomialer Zeit numerisch ziehen (vgl. auch Aufgabe 8.6). So erhält der An-
greifer die Zahl
a
und damit den Klartext
N
N
.
Bemerkung
Bei diesem Angriff ist es wesentlich, dass
e
Teilnehmer denselben Verschlüsse-
lungsexponenten
e
benutzen. Das ist umso leichter möglich, als
e
eine kleine Zahl
ist, daher der Begriff
Low-Exponent-Angriff
.
In der Frühzeit von RSA wurde
e
=
3 sogar als öffentlicher Exponent für alle
vorgeschlagen.
