Cryptography Reference
In-Depth Information
6
Asymmetrische Verschlüsselung
6.1
Einführung
In diesem Kapitel wenden wir uns der bereits in Abschnitt 2.1 erwähnten asymmetrischen
Verschlüsselung zu. Das Szenarium, das wir nun studieren wollen, unterscheidet sich also
grundlegend von denjenigen, die wir bislang studiert haben.
Szenarium 4.
Alice möchte einem Kommunikationspartner Bob, mit dem sie keinen
geheimen Schlüssel teilt, vertrauliche Nachrichten über einen unsicheren (abhörbaren)
Übertragungsweg zukommen lassen.
Der grundsätzliche Unterschied zu den bisherigen Szenarien ist, dass Alice und Bob
nicht die Möglichkeit haben, sich vorab auf einen geheimen Schlüssel zu einigen. Evtl. ken-
nen sich Alice und Bob nicht einmal und tauschen nun zum ersten Mal Nachrichten aus.
Das ist ein realistisches Szenarium, gerade dann, wenn man an Kommunikation in großen,
offenen Netzwerken, wie z. B. dem Internet, denkt.
Wie bereits in Abschnitt 2.1 beschrieben, kann sich Alice in Szenarium 4 der asymme-
trischen Verschlüsselung bedienen. Dazu verschlüsselt Alice ihre Nachrichten an Bob mit
Bobs
öffentlichem Schlüssel
, welchen sie zum Beispiel in einem öffentlichen Verzeichnis
nachschlagen kann oder den ihr Bob (unverschlüsselt) zuschickt; siehe dazu auch Ab-
schnitt 10.6. Bob entschlüsselt dann die von Alice erhaltenen Chiffretexte mit seinem
privaten Schlüssel
. Genauer sind asymmetrische Kryptoschemen wie folgt definiert.
Definition 6.1.1 (asymmetrisches Kryptoschema). Ein
asymmetrisches Kryptoschema
ist ein Tupel
S
=(
X,K,G,E,D
)
(6.1.1)
bestehend aus einem
Klartextraum
X
,einer
Schlüsselmenge
K
, einem zufallsgesteuerten
Schlüsselgenerierungsalgorithmus
G
:
K
pub
×
K
priv
, einem zufallsgesteuerten
Chiffrieral-
}
∗
und einem deterministischen
Dechiffrieralgorithmus
gorithmus
E
(
x
:
X,k
:
K
pub
):
{
0
,
1
}
∗
, k
:
K
priv
):
}
∗
,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 Bit-
vektoren, das
Schlüsselpaar
genannt und meistens mit
(
k,k
)
bezeichnet wird. Dabei ist
k
ein
öffentlicher
und
k
ein
privater Schlüssel
. Die Menge 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
beschränkt ist durch eine Konstante. Die
Laufzeiten von
E
und
D
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
D
(
y
:
{
0
,
1
{
0
,
1
}
∗
und
(
k,k
)
K
,
die Laufzeiten von
E
(
x, k
)
und
D
(
y,k
)
durch
p
(
|x|
)
bzw.
q
(
|y|
)
beschränkt sind. (Man
beachte, dass die Längen der Schlüssel
k
und
k
durch eine Konstante beschränkt werden
∈
X
,
y
∈{
0
,
1
∈