Cryptography Reference
In-Depth Information
10
Asymmetrische Authentifizierungsverfahren:
Digitale Signaturen
10.1
Einführung: Definition und Sicherheit
Die grundsätzliche Funktionsweise von digitalen Signaturen haben wir bereits in Kapitel 7
besprochen. Wir gehen deshalb direkt zur Definition von Signierschemen über.
Definition 10.1.1 (Signierschema). Ein
Signierschema
ist ein Tupel
S
=(
X,K,G,T,V
)
,
}
∗
,einer
Schlüsselmenge
K
, einem zu-
fallsgesteuerten
Schlüsselgenerierungsalgorithmus
G
:
K
pub
× K
priv
, einem zufallsgesteu-
erten
Signieralgorithmus
T
(
x
:
X, k
:
K
priv
):
bestehend aus einem
Nachrichtenraum
X
⊆{
0
,
1
}
∗
{
0
,
1
und einem deterministischen
Vali-
}
∗
,k
:
K
pub
):
dieralgorithmus
V
(
x
:
X, t
:
,wobei
K
,
K
pub
und
K
priv
wie folgt
definiert sind:
K
ist die Menge der von
G
gelieferten Ausgaben. Jedes Element von
K
ist ein Paar von Bitvektoren, das
Schlüsselpaar
genannt und, wie üblich, meistens mit
(
k,k
)
bezeichnet wird. Dabei ist
k
ein
öffentlicher
und
k
ein
privater Schlüssel
. Die Men-
ge der öffentlichen Schlüssel wird mit
K
pub
, die Menge der privaten Schlüssel mit
K
priv
bezeichnet.
Wir verlangen, dass die Laufzeit von
G
durch eine Konstante nach oben beschränkt ist.
Die Laufzeiten von
T
und
V
sollen polynomiell beschränkt sein in der Länge der Eingaben,
d. h., es existieren Polynome
p
und
q
, so dass, für alle
x
{
0
,
1
{
0
,
1
}
}
∗
und
(
k,k
)
K
,
die Laufzeiten von
T
(
x, k
)
und
V
(
x, t,k
)
durch
p
(
|x|
)
bzw.
q
(
|x|
+
|t|
)
beschränkt sind.
(Man beachte, dass die Längen der Schlüssel
k
und
k
durch eine Konstante beschränkt
werden können.)
Ein Signierschema
∈
X
,
t
∈{
0
,
1
∈
S
muss des Weiteren folgende
Korrektheitseigenschaft
erfüllen:
V
(
x, T
α
(
x, k
)
,k
)=1
X
,
(
k,k
)
p
(
|x|
)
.
für alle
x
∈
∈
K
und
α
∈{
0
,
1
}
X
k
}
k∈K
pub
von Nach-
richtenräumen betrachten, da dieser vom verwendeten öffentlichen Schlüssel abhängen
kann.
Wir werden den Nachrichtenraum
X
auch häufig als Familie
{
Die Sicherheit digitaler Signaturen ist, wie es bereits die Erläuterungen in Kapitel 7
vermuten lassen, sehr ähnlich zur Sicherheit von MACs definiert.
Definition 10.1.2 (Fälscher für digitale Signaturen). Ein
Fälscher für ein Signiersche-
ma
S
=(
X,K,G,T,V
)
ist ein zufallsgesteuerter Algorithmus
F
(
s
:
X →{
0
,
1
}
∗
,k
:
K
pub
):
X ×{
0
,
1
}
∗
,