Cryptography Reference
In-Depth Information
Beweis.
Wir begründen mit Induktion
i
=
2
i
−
für
i
a
∑
0
b
k
−
(
∗
)
=
=
a
i
0, . . . ,
k
.
0
=
0
b
k
2
0
−
ist der Induktionsanfang klar. Die Behauptung gelte
a
∑
Wegen
a
0
=
a
=
−
für
i
1. Wir erhalten dann:
a
b
k
−
i
a
∑
2
i
−
1
−
2
i
1
=
−
i
=
2
i
−
,
a
b
k
−
i
a
i
−
1
=
0
b
k
−
a
∑
0
b
k
−
=
=
a
i
sodass die Gleichung
gezeigt ist.
Setzt man in der Gleichung
(
∗
)
k
, so folgt sofort die Behauptung in (i).
Die Behauptung in (ii) folgt ebenfalls, da bei der schrittweisen Berechnung von
a
1
,...,
a
k
=
(
∗
)
i
=
a
n
jeweils höchstens zwei Gruppenoperationen durchgeführt we
r-
den, eine Quadrierung und möglicherweise eine Multiplikation.
ImMittel braucht man sogar nur 1.5 log
2
(
n
)
Gruppenoperationen. Der Algorith-
mus ist also linear mit kleinen Konstanten.
Beispiel
Der Sender
P
berechnet mit der schnellen Exponentiation 3
29
in
Z
257
wegen
2
4
2
3
2
2
2
0
,
=
=
+
+
+
e
29
also
b
4
=
1,
b
3
=
1,
b
2
=
1,
b
1
=
0,
b
0
=
1
=
vorteilhaft durch Quadrieren und Multiplizieren. Es ist
a
3:
3
1
a
b
4
a
0
=
=
=
3,
3
1
3
2
a
b
3
a
0
=
=
·
·
=
a
1
27 ,
3
1
27
2
a
b
2
a
1
=
=
·
·
=
a
2
131 ,
3
0
a
b
1
a
2
=
=
·
·
=
a
3
131
199 ,
3
1
199
2
a
b
0
a
3
=
=
·
·
=
a
4
69 .
Es werden dabei 7 Gruppenoperationen durchgeführt, wir fassen diese zusam-
men:
⎛
3
0
⎞
3
1
2
3
1
2
2
3
1
2
3
29
3
1
.
⎝
⎠
=
·
·
·
·
3
0
, dies entspricht einer Multiplikation mit 1,
Man beachte, dass die Operation
·
nicht ausgeführt wird.
