Cryptography Reference
In-Depth Information
(neuen) Chiffretext zu einem neuen Klartext sendet, dann weiß Eva natürlich, dass der
zum Chiffretext gehörende Klartext nicht einer der
N
0
abgefragten Klartexte sein kann,
aber ansonsten ist jeder der anderen
N
N
0
Klartexte möglich.
Nach diesen Überlegungen wollen wir einen geeigneten (possibilistischen) Sicherheits-
begriff prägen, der weiter unten näher erläutert wird; eine informationstheoretische Vari-
ante soll in Aufgabe 4.9.3 entwickelt werden:
−
Definition 4.1.1 (possibilistische Sicherheit). Ein Kryptosystem
=(
X,K,Y,e,d
)
heißt
possibilistisch sicher im Hinblick auf Szenarium 2,
wenn für jedes
r
,
0
≤ r<|X|
S
,
jede Folge
x
0
,...,x
r
von Klartexten ohne Wiederholungen, jeden Schlüssel
k
und jedes
y ∈ Y \{e
(
x
i
,k
)
ein Schlüssel
k
∈
K
existiert, so dass
e
(
x
i
,k
)=
e
(
x
i
,k
)
für
|
i<r
}
alle
i<r
und
e
(
x
r
,k
)=
y
gilt.
Hinter dieser Definition steckt die folgende Intuition: Eva kann sich beliebige Nach-
richten verschlüsseln lassen, also etwa
x
0
,...,x
r−
1
, und erhält
y
0
,...,y
r−
1
. Nun sendet
Alice den Chiffretext
y
einer
neuen
Nachricht. Dann muss
y ∈ Y \{e
(
x
i
,k
)
| i<r}
gelten. Eva soll nun keine Rückschlüsse auf den zu
y
gehörenden Klartext ziehen können,
d. h., sie soll jeden Klartext für möglich halten außer den Klartexten
x
0
, ...,
x
r−
1
,von
denen sie sowieso weiß, dass sie nicht in Frage kommen. Mit anderen Worten: Für jeden
Klartext
x
r
/
muss es einen Schlüssel
k
geben, für den
e
(
x
i
,k
)=
y
i
für
jedes
i<r
und
e
(
x
r
,k
)=
y
gilt.
Bemerkung
4.1.1 (Zusammenhang mit possibilistischer Sicherheit)
.
Für
r
=0
ergibt sich
in der obigen Definition die possibilistische Sicherheit aus dem letzten Kapitel (siehe
Definition 3.2.2).
∈{
x
0
,...,x
r−
1
}
Wir können nun die Sicherheit der Substitutionskryptosysteme beweisen:
Proposition 4.1.1 (Sicherheit der Substitutionskryptosysteme).
Für jede nicht leere,
endliche Menge
X
ist das Substitutionskryptosystem auf
X
possibilistisch sicher im Hin-
blick auf Szenarium 2.
Beweis.
Es sei
das Substitutionskryptosystem auf einer nicht leeren, endlichen Menge
X
und seien
x
0
,...,x
r
wie in der obigen Definition. Es sei weiterhin
π
ein beliebiger
Schlüssel und
y/
S
. Dann betrachten wir einen Schlüssel
π
für den
π
(
x
i
)=
π
(
x
i
)
für alle
i<r
und
π
(
x
r
)=
y
gilt. Man sieht leicht, dass ein solch
er
Schlüssel in der Tat existiert. Dieser erfüllt die Bedingungen aus der Definition.
∈{
π
(
x
0
)
,...,π
(
x
r−
1
)
}
Andererseits können wir auch zeigen, dass Substitutionskryptosysteme im Wesentli-
chen die einzigen Kryptosysteme sind, die im Hinblick auf den neuen Sicherheitsbegriff
sicher sind:
Proposition 4.1.2.
Es sei
S
=(
X,K,X,e,d
)
ein Kryptosystem, das possibilistisch
sicher ist im Hinblick auf Szenarium 2. Dann gilt
{
e
(
·
,k
)
|
k
∈
K
}
=
P
X
.
Beweis.
Wegen der Dechiffrierbedingung ist klar, dass
{
e
(
·
,k
)
|
k
∈
K
}⊆P
X
gilt.
∈P
X
beliebig. Wir zeigen, dass es einen Schlüssel
k
gibt, für den
e
(
·,k
)=
π
gilt. Es gelte
Es sei nun
π
. Wir konstruieren den Schlüssel
per Induktion mit der folgenden Induktionsbehauptung: Für jedes
i<n
gibt es einen
|X|
=
n
und
X
=
{x
0
,...,x
n−
1
}