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 }
 
Search WWH ::




Custom Search