Cryptography Reference
In-Depth Information
Die aus Netzen bzw. affinen Ebenen abgeleiteten Authentifikationssystem haben
nicht nur beweisbare Sicherheit, das Sicherheitsniveau ist einstellbar. Soll eine
bestimmte Betrugswahrscheinlichkeit unterschritten werden, muss man nur den
Körper groß genug wählen.
Dabei sind affine Ebenen insofern optimal, als bei vorgegebener Größe der
Schlüsselmenge
K
q
2
die Anzahl der Datensätze mit
q
=
+
1 maximal ist.
Die aus einer affinen Ebene der Form AG
abgeleiteten Authentifikations-
systeme können auch effizient implementiert werden.
(
2,
Z
p
)
5.3.5 Perfekte kartesische Systeme liefern Netze
Interessanterweise gilt auch die Umkehrung: Jedes perfekte kartesische Authen-
tifikationssystem liefert ein Netz. Wir benutzen für solche Authentifikationssys-
teme die in der Definition auf Seite 84 eingeführten Bezeichnungen
K
f
.
(
)
c
und
Lemma 5.6
Es sei
(
P
,
C
,
K
,
f
)
ein kartesisches Authentifikationssystem mit
|
P
| ≥
3
. Setze
G
:
=
{
(
)
∈
}
(
G
)
=
|
|
|
| ≤
K
c
;
c
C
. Dann ist
K
,
ein Netz der Ordnung q
K
, und es gilt
P
q
+
1
. Im Fall
|
P
|
=
q
+
1
ist
(
K
,
G
)
eine affine Ebene.
Beweis.
Es seien
c
,
c
∈
c
. Lemma 5.2 (c) besagt
c
)
| ≤
C
,
c
=
|
K
(
c
)
∩
K
(
1. Das
ist (A1)'.
Für
x
f
K
gilt
G
oder
G
=
=
(
c
)
und
k
∈
:
=
K
(
f
(
x
,
k
))
∩
K
(
c
)=∅
K
(
c
)
(falls
c
)
∈
(
))
(
)
(
k
K
c
, also gibt es eine Parallele zu
K
c
durch
k
. Falls
K
eine weitere
f
f
c
)=∅
c
)=
Parallele zu
K
(
c
)
durch
k
ist, so gilt
K
(
c
)
∩
K
(
, also
(
(
c
)
. Daraus
c
)=
G
und (A2) ist gezeigt.
(
folgt
K
Da jedes
x
∈
P
eine Parallelklasse definiert, gilt (A
3)'
. Damit ist gezeigt, dass
=
|
(
K
,
G
)
ein Netz ist. Aus Lemma 5.4 (d) folgt
q
K
|
, und mit Lemma 5.4 (e)
|
| ≤
+
ergibt sich
P
q
1.
1. Es seie
n
k
,
k
∈
k
und
G
Es gelte nun
|
P
|
=
q
+
K
,
k
=
∈G
eine Gerade durch
k
. Wir zeigen die Existenz von
k
,
k
. Falls
k
∈
G
, sind wir fertig. Andernfalls gibt
es in jeder Parallelklasse eine Gerade
G
i
durch
k
. Diese können nach Lemma 5.4
=
(c) mit
i
0, . . . ,
q
durchnummeriert werden. Ohne Einschränkung gilt
G
0
G
und
G
i
∩
G
=
k
i
. Wegen
|
G
|
=
q
gilt daher
G
=
{
k
1
,...,
k
q
}
. Somit gibt es
i
0
mit
k
=
k
i
0
, und
G
i
0
ist die Verbindungsgerade von
k
und
k
. Das zeigt (A1). Und w
ie
schon erwähnt folgt (A3) aus (A3)'.
Es soll nicht verschwiegen werden, dass diese Systeme auch gravierende Nach-
teile haben. So kann ein Schlüssel nur einmal verwendet werden. In der Tat: Es
seien zu einem Schlüssel
k
K
zwei Nachrichten
G
und
H
bekannt, die mit
k
au-
thentifiziert wurden. In der geometrischen Deutung sind
k
ein Punkt und
G
,
H
Geraden mit
k
∈
∈
G
,
H
. Wegen (A1)' muss also
k
=
G
∩
H
gelten, und der Schlüs-
sel kann von jedem bestimmt werden.
Man beachte die Ähnlichkeit dieser Systeme zum One-Time-Pad: Für jeden neuen
Datensatz muss ein neuer Schlüssel gewählt werden.
