Cryptography Reference
In-Depth Information
Tab. 4-5: Algorithmus zum Potenzieren, ein Beispiel: a
13
=a
1011
a
1011
Zielwert
a
1
Startwert
a
10
Q
es wurde quadriert
a
100
Q
es wurde quadriert
M a
101
es wurde multipliziert
a
1010
Q
es wurde quadriert
M a
1011
es wurde multipliziert
Wenn der Exponent e eine Länge von l
e
Binärstellen hat, dann sind l
e
1 Quadrierungen und im
Mittel (l
e
1)/2 Multiplikationen erforderlich (für jede Stelle mit dem Wert 1, außer der ersten).
Zahl der Quadrierungen
l
1
e
(4.1-17)
Zahl der Multiplikationen
(Zahl der "1" in e)
)
1
(l
1) / 2
e
Bei einem Exponenten mit 1000 Binärstellen sind damit etwa 1000 bis 2000 Quadrierungen
oder Multiplikationen erforderlich.
4.1.4
Diskreter Logarithmus
36
34
32
30
28
26
24
22
20
18
16
14
Abb. 4-1: Diskrete Exponential-
Funktion.
y = a
x
mod p
y= 2
x
mod 37.
12
10
8
6
4
Der diskrete Logarithmus ermittelt
für einen gegebenen Wert von y
ein gesuchtes x.
2
0
10
14
246
8
12
16
18
20
22
24
26
28
30
32
34
36
