Cryptography Reference
In-Depth Information
1.5 Kryptosysteme
Unter einem
kryptografischen System,
kurz
Kryptosystem,
verstehen wir ein
Tupel
(
)
P
,
C
,
K
,
f
,
g
mit nichtleeren Mengen
P
,
C
,
K
und Abbildungen
f
:
P
×
K
→
C
und
g
:
C
×
K
→
P
mit der Eigenschaft:
k
∈
,
k
)=
(
∗
)
∀
∈
∃
(
(
)
∈
k
K
K
:
g
f
x
,
k
x
für alle
x
P
.
K
bzw.
k
∈
∈
Setzt man für
k
K
.,
k
)
=
(
)
→
=
(
→
f
k
:
f
.,
k
:
P
C
bzw.
g
k
:
g
:
C
P
,
so können wir die Eigenschaft
(
∗
)
auch schreiben als:
k
∈
(
∗
)
∀
k
∈
K
∃
K
:
g
k
◦
f
k
=
id
P
.
Es heißen
•
P
die
Klartextmenge
(
P
wie
plain text
),
•
C
die
Geheimtextmenge
(
C
wie
cipher text
),
•
K
die
Schlüsselmenge
(
K
wie
key
),
•
f
Verschlüsselungsfunktion,
•
g
Entschlüsselungsfunktion.
(
∗
)
Die Bedingung
besagt, dass jeder durch einen Schlüssel
k
verschlüsselte Klar-
text durch einen Schlüssel
k
entschlüsselt werden kann. Außerdem ist die Be-
dingung
g
k
◦
bekanntlich gleichwertig zur Injektivität der Abbil-
dung
f
k
bzw. zur Surjektivität der Abbildung
g
k
f
k
=
id
P
in
(
∗
)
(vgl. Aufgabe 1.2). Folglich gilt
|
P
| ≤ |
C
|
.
Bemerkung
Manchmal lassen wir die Abbildung
g
weg und nennen ein Viertupel
(
P
,
C
,
K
,
f
)
∈
ein Kryptosystem, wenn die Abbildungen
f
k
für alle
k
K
injektiv sind. Die In-
jektivität von
f
k
gewährleistet nämlich die Existenz einer surjektiven Abbildung
g
k
→
P
mit
g
k
◦
f
k
=
:
C
id
P
.
Beispiel
Die
Caesar-Chiffre
über dem Alphabet
Z
q
mit
q
Buchstaben ist ein Kryptosys-
=
Z
q
=
Z
q
die Schlüssel-
tem. Es ist
P
C
die Klartext- und Geheimtextmenge,
menge, und für jedes
k
∈
Z
q
ist durch
Z
q
→
Z
q
,
w
1
w
2
···
f
k
:
w
)
→
(
w
1
+
k
)(
w
2
+
k
)
···
(
w
)
+
k
)
(
w
(
w
eine Verschlüsselungsfunktion gegeben. Die Entschlüsselungsfunktion
g
k
ist ge-
geben durch die Abbildung
g
k
=
f
=
f
q
−
k
.
−
k