Cryptography Reference
In-Depth Information
Beispiel 3.2.3 (Substitutionskryptosysteme). Es sei
X
eine nicht leere endliche Menge.
Das
Substitutionskryptosystem
auf
X
ist das Tupel
(
X,P
X
,X,e,d
)
,wobei
P
X
die Menge
aller Permutationen auf
X
bezeichne und
e
und
d
gegeben seien durch
e
(
x, π
)=
π
(
x
)
für alle
x ∈ X
,
π ∈P
X
,
(3.2.15)
d
(
y,π
)=
π
−
1
(
y
)
für alle
y
∈
X
,
π
∈P
X
.
(3.2.16)
Wie üblich bezeichne
π
−
1
die Umkehrfunktion zu
π
.
Proposition 3.2.2 (Sicherheit der Substitutionskryptosysteme).
Für jede nicht leere
endliche Menge
X
ist das Substitutionskryptosystem auf
X
possibilistisch sicher.
Beweis.
Es seien
x, y
∈
X
beliebig und es sei
π
∈P
X
definiert durch
⎧
⎨
y,
falls
z
=
x
,
x,
falls
z
=
y
,
z,
sonst.
π
(
z
)=
(3.2.17)
⎩
Dann ist tatsächlich
π
∈P
X
und es gilt
e
(
x, π
)=
π
(
x
)=
y
, womit die Behauptun
g
gezeigt ist.
Aus der Definition der possibilistischen Sicherheit lässt sich einfach schließen:
Proposition 3.2.3.
Es sei
S
ein possibilistisch sicheres Kryptosystem. Dann gilt:
|K|≥
|
Y
|≥|
X
|
.
Beweis.
Da jede Chiffre wegen der Dechiffrierbedingung injektiv ist, gilt
|Y |≥|X|
.
Es sei nun
x
0
∈ X
ein beliebiger Klartext. Da
S
possibilistisch sicher ist, gibt es zu
jedem
y
Y
wählen wir ein solches
k
und
bezeichnen es mit
k
y
. Alle diese Schlüssel
k
y
müssen paarweise verschieden sein, da
e
eine
Funktion auf
X
∈
Y
ein
k
∈
K
mit
e
(
x
0
,k
)=
y
. Für jedes
y
∈
×
K
ist. Also gilt
|
K
|≥|
Y
|
.
Insgesamt erhalten wir
|
K
|≥|
Y
|≥|
X
|
.
Wir gewinnen also folgende wichtige Erkenntnis: Um possibilistische Sicherheit garan-
tieren zu können, muss man mindestens so viele Schlüssel wie Klartexte haben! Wollte
man zum Beispiel die Daten auf der Festplatte seines Arbeitsplatzrechners verschlüsseln
- diese Möglichkeit bieten moderne Betriebssysteme - bräuchte man im Durchschnitt für
jede Verschlüsselung eine weitere Festplatte gleicher Kapazität, allein um den Schlüssel
unterzubringen. Das ist natürlich nicht praktikabel. Allerdings bilden Verfahren, die pos-
sibilistische Sicherheit bieten, oder sogar die stärkere informationstheoretische Sicherheit,
wie wir sie in Abschnitt 3.4 kennenlernen werden, wichtige Bausteine in anderen durchaus
praktikablen kryptographischen Verfahren.
3.3
Wiederholung Wahrscheinlichkeitstheorie
Ab dem folgenden Abschnitt werden wir immer wieder auf die Wahrscheinlichkeitstheorie
zurückgreifen. Deshalb werden wir wichtige Begriffe, Sachverhalte und Notationen hier
