Cryptography Reference
In-Depth Information
kann die Gruppenordnung
der zugrunde liegenden Gruppe
G
geheim ge-
halten werden. Man kann dann den Schlüssel
e
zum Verschlüsseln einer Nach-
richt sogar öffentlich machen, ohne den (geheimen) Schlüssel
d
zum Entschlüs-
seln preiszugeben. Damit ist eines der großen Probleme beim Pohlig-Hellman-
Verfahren und allen anderen symmetrischen Verfahren ausgeräumt: der Schlüs-
selaustausch.
|
G
|
6.3 Schnelle Exponentiation
Beim Verfahren von Pohlig-Hellman (und bei vielen anderen kryptografischen
Verfahren) muss man Potenzen in einer Gruppe
G
berechnen. Die Aufgabe lautet:
Für a
bestimme a
n
.
Der naheliegendste Ansatz der sukzessiven Multiplikation basiert auf der übli-
chen Rekursion für Potenzen:
∈
∈
N
G und n
a
n
aa
n
−
1
.
=
1 Gruppenoperationen, um
a
n
zu berechnen. Diese
Methode ist also exponentiell in der Anzahl log
n
der Bits von
n
. Die
schnelle
Exponentiation
basiert auf folgender Rekursion für Potenzen:
−
Dieser Ansatz benötigt
n
⎧
⎨
a
2
2
,
falls
n
gerade,
a
n
=
a
n
−
2
2
⎩
a
,
falls
n
ungerade.
Ein dazu äquivalenter, iterativer Algorithmus benutzt die Binärdarstellung von
n
.
In der englischsprachigen Literatur wird der Algorithmus aus naheliegenden
Gründen oft als
square and multiply
bezeichnet. Der Algorithmus benötigt nur die
Assoziativität der Verknüpfung. Da der Algorithmus häufig in der multiplika-
tiven Halbgruppe von Ringen angewendet wird, formulieren wir ihn gleich für
diesen allgemeinen Fall.
Lemma 6.15
Es sei a ein Element einer Halbgruppe G, und eine Zahl n
∈
N
sei in Binärdarstellung
gegeben:
k
∑
=
0
b
2
n
=
mit
k
=
log
2
n
,
b
∈{
0, 1
}
.
a
b
k
a
b
k
−
i
a
i
−
1
,1
Setze a
0
:
=
=
a und a
i
:
=
≤
i
≤
k. Dann gilt:
a
n
.
a
k
=
(i)
(ii)
Zur Berechnung von a
n
braucht man höchstens
2
k Multiplikationen. Der Algo-
rithmus ist also linear (bezogen auf die Verknüpfung in G).
