Cryptography Reference
In-Depth Information
■
Zwei Punkte legen eine Gerade eindeutig fest.
Die Gleichung einer Geraden lautet
y
=
ax
+
b
.
■
Drei Punkte legen eine Parabel eindeutig fest.
Die Gleichung einer Parabel lautet
y
=
ax
2
+
bx
+
c
.
■
Vier Punkte legen eine Kubik eindeutig fest.
Die Gleichung einer Kubik lautet
y
=
ax
3
+
bx
2
+
cx
+
d
.
■
m
Punkte legen eine Polynom-Kurve der Ordnung
m
-1 eindeutig fest.
Die Gleichung einer Polynom-Kurve der Ordnung
m
-1 lautet
y
=
a
m-1
x
m-1
+...+
a
2
x
2
+
a
1
x
+
a
0
.
Das Secret-Sharing nach Shamir sieht vor, dass von
n
Beteiligten jeder einen
Punkt auf einer Polynom-Kurve der Ordnung
m
-1 erhält. Wenn
m
der
n
Personen
ihre Punkte zur Verfügung stellen, dann lässt sich die Kurve rekonstruieren.
Dadurch ist ein
m
-aus-
n
-Prinzip gegeben. Das Shamir-Verfahren legt fest, dass
der Schlüssel als Wert
a
0
in die Gleichung eingeht. Die Werte für
a
1
,
a
2
usw. sind
beliebig. Zu den Punkten, die auf die
n
Personen verteilt werden, darf nicht der
Punkt (0,
a
0
) gehören, da dieser den Schlüssel preisgibt.
Betrachten wir ein Beispiel. Der zu verteilende Schlüssel sei die Zahl 10, und
es sei ein 3-aus-5-Prinzip gewünscht. Wir benötigen also eine Polynom-Kurve
zweiten Grades mit
a
0
=10. Folgende Gleichung beschreibt eine solche:
y
=2
x
2
-5
x
+10
Nun brauchen wir fünf Punkte auf dieser Kurve, beispielsweise (1,7), (2,8),
(3,13), (4,22) und (5,35). Diese fünf Punkte werden auf fünf Personen verteilt.
Wenn nun die erste, die dritte und die vierte Person ihre Punkte zusammenlegen,
dann können sie folgende Gleichungen bilden:
a
2
+
a
1
+
a
0
= 7
9
a
2
+ 3
a
1
+
a
0
= 13
16
a
2
+
4
a
1
+
a
0
= 22
Es ist nicht schwierig, dieses Gleichungssystem zu lösen und den Wert von
a
0
zu
ermitteln. Dieser beträgt 10 und ist der gesuchte Schlüssel. In der Praxis werden
diese Berechnungen modulo einer Primzahl durchgeführt, da die Zahlen sonst zu
groß werden (
a
0
kann beispielsweise 128 Bit lang sein). Die verwendete Primzahl
muss größer als der Wert von
a
0
(also als der Schlüssel) sein.
24.1.6
Schlüsselwechsel
Es versteht sich von selbst, dass Alice und Bob nicht für unbegrenzte Zeit densel-
ben geheimen Schlüssel verwenden sollten. Die Frage ist jedoch, wie oft ein
Schlüsselwechsel sinnvoll ist. Viele kryptografische Protokolle sehen vor, dass
Alice und Bob für jede Kommunikation einen neuen Sitzungsschlüssel verwen-
