Cryptography Reference
In-Depth Information
10.2
Signieren mit RSA: erster Versuch
Es liegt nahe, RSA als Signierschema zu verwenden. Dabei übernimmt der Dechiffrieral-
gorithmus die Aufgabe des Signieralgorithmus und verifiziert wird mit dem Chiffrieral-
gorithmus. In der Tat wurde diese Vorgehensweise bereits von den Erfindern von RSA
vorgeschlagen.
Genauer ist das durch RSA induzierte Signierschema wie folgt definiert.
Definition 10.2.1 (RSA-Signierschema). Es sei
l>
0
gerade. Das
l
-RSA-Signierschema
S
RSA
ist ein Tupel
(
X,K,G,T,V
)
mit
-
K
=
{
((
n, e
)
,
(
n, d
))
|
(
n, p, q, m, e, d
)
ist ein RSA-Tupel mit
|p|
2
=
|
q
|
2
=
l/
2
}
,
-
X
=
{
Z
n
}
(
n,e
)
∈K
pub
,
-
G
erzeugt Schlüsselpaare gemäß dem RSA-Kryptoschema (vgl. Definition 6.4.2),
-
T
(
x,
(
n, d
)) =
x
d
mod
n
für alle
x ∈
Z
n
und
((
n, e
)
,
(
n, d
))
∈ K
,
-
V
(
x, t,
(
n, e
))
gibt
1
aus, wenn
t
e
mod
n
=
x
gilt,
0
sonst.
S
RSA
ein Signierschema im Sinne von Definition 10.1.1 ist. Die
Idee dieses Signierschemas ist, dass jemand, der den privaten Schlüssel
(
n, d
)
nicht kennt,
nicht in der Lage ist (zumindest nicht mit realistischem Aufwand), zu einer Nachricht
x
, die Signatur
x
d
mod
n
zu berechnen. Dies folgt aus der RSA-Annahme (vgl. Annah-
me 6.4.1). Umgekehrt kann jeder leicht mit Hilfe des öffentlichen Schlüssels
(
n, e
)
die
Gültigkeit einer Signatur verifizieren.
Diese Argumentation ist aber leider fehlerhaft. Die RSA-Annahme besagt lediglich,
dass es schwer ist, zu einer
zufällig
gewählten Nachricht
x
das Urbild
x
d
mod
n
zu
berechnen. Für bestimmte Nachrichten
x
kann dies jedoch leicht sein. Für solche Nach-
richten könnte man also leicht eine Signatur berechnen. Zum Beispiel sind
(0
,
0)
und
(1
,
1)
offensichtlich gültige Nachrichten-Signatur-Paare (im Folgenden kurz NSP genannt). All-
gemeiner sieht man leicht, dass der Vorteil des folgenden Fälschers
1
ist; dieser also immer
ein gültiges NSP ausgibt:
Man sieht leicht, dass
}
∗
Wähle
x ∈
Z
n
beliebig
Ausgabe
(
x
e
mod
n, x
)
}
∗
×{
F
(
s,
(
n, e
)):
{
0
,
1
0
,
1
Damit ist klar, dass das Signierschema
S
RSA
völlig unsicher ist. Erlaubt man dem Fäl-
scher zwei Anfragen an das Signierorakel zu stellen, so sind für
S
RSA
sogar universelle
Fälschungen möglich, d. h., zu jeder beliebigen Nachricht kann eine gültige Signatur be-
rechnet werden (vgl. auch Kapitel 7). Dazu nutzt man die sogenannte Multiplikativität
von RSA aus:
x
d
· y
d
mod
n
=(
x · y
)
d
mod
n
. Der folgende Fälscher berechnet zu einer
beliebigen Nachricht
z
∈
Z
n
die zugehörige Signatur.
}
∗
×{
}
∗
F
univ
(
s,
(
n, e
)):
{
0
,
1
0
,
1
Z
n
)
t
1
=
s
(
r
)
t
2
=
s
(
z · r
−
1
mod
n
)
Ausgabe
(
z,t
1
·
r
=
flip
(
t
2
mod
n
)
