Cryptography Reference
In-Depth Information
DSA leitet sich in seiner Art vom ElGamal-Kryptoschema ab. Im Gegensatz zum RSA-
Kryptoschema, aus dem sich, wie wir gesehen haben, leicht ein Signierschema gewinnen
lässt, unterscheiden sich DSA und das ElGamal-Kryptoschema aber gravierend.
Definition 10.5.1 (DSA). Das
DSA-Signierschema
S
DSA
mit Bitlänge 1024 und Hash-
funktion
H
ist das Tupel
(
X,K,G,T,V
)
, wobei die Komponenten wie folgt definiert
sind:
-
X
=
Definitionsbereich von
H
.
-
G
ist ein zufallsgesteuerter Algorithmus mit konstanter Laufzeit, der ein Schlüssel-
paar wie folgt erzeugt:
1. Wähle zufällige Primzahlen
p
und
q
mit
2
1023
<p<
2
1024
,
2
159
<q<
2
160
,
q
1)
,aber
q
2
|
1)
.
2. Wähle Generator
g
der (eindeutig bestimmten) Untergruppe von
|
(
p
−
(
p
−
Z
p
mit Ord-
nung
q
.
3. Wähle
a
∈
Z
q
zufällig.
4. Berechne
h
=
g
a
mod
p
.
5. Der öffentliche Schlüssel ist
(
p, q, g, h
)
und der private Schlüssel ist
(
p, q, g, a
)
.
-
K
ist die Menge der von
G
ausgegebenen Schlüsselpaare.
- Die Signatur
T
(
x,
(
p, q, g, a
))
für
x ∈ X
und
((
p, q, g, h
)
,
(
p, q, g, a
))
∈ K
wird wie
folgt berechnet:
1. Wähle
k ∈
Z
q
zufällig.
2.
r
=(
g
k
mod
p
)
mod
q
.
3.
s
=(
H
(
x
)+
a
k
−
1
mod
q
.
·
r
)
·
4. Ausgabe
(
r, s
)
.
4
-
V
(
x,
(
p, q, g, h
)
,
(
r, s
))
mit
x
∈
Z
q
∈
X
,
((
p, q, g, h
)
,
(
p, q, g, a
))
∈
K
und
r, s
ist wie
folgt definiert:
1.
u
1
=
H
(
x
)
· s
−
1
mod
q
.
2.
u
2
=
r
s
−
1
mod
q
.
3. Ausgabe
1
, falls
r
=(
g
u
1
·
·
h
u
2
mod
p
)
mod
q
,und
0
sonst.
In Aufgabe 10.7.9 soll gezeigt werden, dass
S
DSA
ein Signierschema im Sinne von
Definition 10.1.1 ist. Die Sicherheit von
S
DSA
beruht auf der Annahme, dass es schwer
ist, den diskreten Logarithmus zu berechnen (siehe Definition 6.5.6). Leider gibt es aber
unter dieser Annahme keinen Beweis für die Sicherheit dieses Schemas, auch nicht, falls
man zusätzlich annimmt, dass
H
ein Zufallsorakel ist. Allerdings gilt DSA bis heute als
sicher; zumindest wurde noch kein schwerwiegender Angriff gefunden.
10.6
Zertifikate und Public-Key-Infrastrukturen
Die asymmetrische Verschlüsselung war dadurch motiviert, dass sie das Problem der
Schlüsselverteilung und -explosion löst (siehe Abschnitt 2.1): Mit Hilfe der asymmetri-
schen Verschlüsselung kann man (sogar einem bisher fremden) Kommunikationspartner
eine vertrauliche Nachricht schicken, indem man die Nachricht mit dem öffentlichen
Schlüssel des Kommunikationspartners verschlüsselt. Dieser kann die Nachricht dann mit
4 Für den unwahrscheinlichen Fall, dass
r
=0
oder
s
=0
gilt, wird die Signatur nochmals berechnet.
