Cryptography Reference
In-Depth Information
Aufgrund der Multiplikativität von RSA ist klar, dass
F
univ
eine gültige Signatur für
z
ausgibt. Mit großer Wahrscheinlichkeit werden zudem
r
und
z · r
−
1
mod
n
von
z
verschieden sein (falls
z
=0
gilt), so dass die Berechnung von
F
univ
zulässig ist, d. h.,
z
wurde nicht von
F
univ
an das Signierorakel geschickt. (Für den Fall
z
=0
wissen wir, dass
0
die Signatur zu
z
ist.) Der genaue Vorteil von
F
univ
soll in Aufgabe 10.7.1 bestimmt
werden.
10.3
Signierschemen basierend auf Hashfunktionen
Ein beliebter Ansatz, um praktikable Signierschemen auf Nachrichten beliebiger Länge
zu erhalten, ist Hash-then-Sign. Dieser Ansatz funktioniert analog zum entsprechenden
Ansatz für MACs (vgl. Abschnitt 9.4): Zunächst wird zur zu signierenden Nachrichten
ein Hashwert berechnet, anschließend wird der Hashwert signiert.
Zur Umsetzung dieses Ansatzes benötigen wir natürlich ein Signierschema, dass auf
Nachrichten (zumindest) fester Länge arbeitet. Auf dieses Problem werden wir am Ende
dieses Abschnitts eingehen. Wir nehmen zunächst an, dass wir ein solches Signierschema
gegeben haben.
Wir fassen den Hash-then-Sign-Ansatz in folgender Definition präzise. Der wesentliche
Unterschied zum Hash-then-MAC-Ansatz ist, dass nun der Schlüssel für die Hashfunktion
nicht geheim bleibt, sondern Teil des öffentichlichen Schlüssels wird, da die Hashfunktion
zur Validierung einer Signatur benötigt wird. Damit ist aber einem Fälscher die verwen-
dete Hashfunktion bekannt, was höhere Sicherheitsanforderungen an die verwendeten
Familien von Hashfunktionen stellen wird.
Definition 10.3.1 (Hash-then-Sign). Es sei
h
k
}
k∈K
H
eine Familie von Hash-
funktionen mit Hashbreite
n
und Definitionsbereich
D
. Weiter sei
p
:
{
0
,
1
}
H
=
{
n
r
,
→{
0
,
1
}
für
r
≥
n
, eine injektive Funktion und
S
=(
X,K
S
,G,T,V
)
ein Signierschema mit
r
{
0
,
1
}
⊆
X
. Dann ist das Signierschema HashSign
[
H
,p,
S
]
gegeben durch
]=(
X
,K
,G
,T
,V
)
,
HashSign
[
H
,p,
S
wobei die einzelnen Komponenten wie folgt definiert sind:
-
X
=
D
.
- Der Schlüsselerzeugungsalgorithmus
G
ist:
G
:
K
1.
Wähle Index für Hashfunktion
k
h
=
flip
(
K
H
)
2.
Erzeuge Schlüsselpaar für das Basis-Signierschema
(
k,k
)=
G
()
3.
Ausgabe des Schlüsselpaars
gib
((
k
h
,k
)
,
(
k
h
, k
))
zurück
Dabei bezeichnet
K
die Menge der von
G
gelieferten Schlüsselpaare; wie üblich
bezeichnen im Folgenden,
K
pub
und
K
priv
die zugehörigen Mengen von öffentlichen
und privaten Schlüsseln.
