Cryptography Reference
In-Depth Information
5.2.1 Möglichkeiten zum Betrug
Gegeben ist ein Authentifikationssystem
. Die
Betrugswahrschein-
lichkeit
p
ist die Wahrscheinlichkeit, mit der ein Angreifer eine als gültig an-
zuerkennende Nachricht einspielen kann. Wir unterscheiden zwei Typen von Be-
trugsversuchen, die einem Angreifer zur Verfügung stehen.
(
P
,
K
,
C
,
f
)
•
Substitution:
Eine Nachricht wird abgefangen und durch eine eigene er-
setzt.
•
Impersonation:
Eine eigene Nachricht wird eingespielt.
1
≥
Natürlich gilt für die Betrugswahrscheinlichkeit
p
, weil ein Angreifer ver-
suchen kann, den Schlüssel zu erraten. Tatsächlich ist die Situation viel schlechter.
Das ist der Inhalt des folgenden Satzes.
|
K
|
Satz 5.1
(Gilbert, MacWilliams, Sloane)
Es sei
ein (nicht notwendig kartesisches) Anthentifikationssystemmit gleich-
verteilter Schlüsselwahl. Für die Betrugswahrscheinlichkeit p gilt
(
P
,
C
,
K
,
f
)
1
≥
p
.
|
K
|
∈
Beweis.
Bei der Impersonation hat der Angreifer mit der Nachricht
c
C
Erfolg,
wenn der benutzte Schlüssel in
K
(
c
)
liegt. Für die Betrugswahrscheinlichkeit gilt
demnach für jedes
c
∈
C
:
≥
|
(
)
|
K
c
p
.
|
K
|
Bei der Substitution sei
c
∈
C
die beobachtete gültige Nachricht. Daher muss der
(
)
Schlüssel in
K
c
liegen, und wir erhalten die Abschätzung
1
p
≥
.
|
K
(
c
)
|
Wir kombinieren die beiden Resultate zu
≥
|
K
(
c
)
|
1
1
p
2
·
)
|
=
,
(
|
K
|
|
K
c
|
K
|
und der Satz ist bewiesen.
Ein Authentifikationssystem
(
P
,
K
,
C
,
f
)
heißt
p
erfe
kt
, wenn die Betrugswahr-
1/
=
|
|
scheinlichkeit
p
minimal ist, d. h. wenn
p
.
Bevor wir Beispiele von perfekten Authentifikationssystemen angeben, ziehen
wir aus dem Beweis des Satzes von Gilbert, MacWilliams und Sloane einige Fol-
gerungen.
K
Korollar 5.2
In einem perfekten, kartesischen Authentifikationssystem
(
P
,
C
,
K
,
f
)
gilt:
