Cryptography Reference
In-Depth Information
Ein Angreifer kann durch Beobachtung des Stromverbrauchs (oder anderer phy-
sikalischer Größen) einer Maschine evtl. auf die Bi rdarstellung der Zahl e
schließen. Das ist an der hervorgehobenen Formel für 3 29 gut zu erkennen. Liegt
eine 0 vor braucht es eine Operation, liegt eine 1 vor, braucht es zwei.
Einen solchen Angriff nennt man Seitenkanalangriff . Man sollte dies bei der Im-
plementierung des Algorithmus beachten.
Bemerkung
Ist a invertierbar, so kann man auch a n für n
Z
<
, n
0, bestimmen. Man
) n , benötigt also einen Algorithmus zur Bestimmung von Inver-
sen. Dieser Algorithmus kann - wenn n nicht zu groß ist - teurer sein als die
schnelle Exponentiation.
a 1
rechnet
(
Man beachte, dass es bei einer Implementation vorteilhaft sein kann, eine Qua-
drierfunktion zu benutzen. Quadrieren ist oft effizienter möglich, als einfach
ein Element mit sich selbst zu multiplizieren. Bei der Implementierung dieses
Algorithmus sind eine Reihe von Varianten und Optimierungenmöglich (siehe
z. B. [7]).
Aufgaben
6.1 Begründen Sie Lemma 6.1.
=(
· )
6.2 Es seien a und b Elemente einer endlichen abelschen Gruppe G
G ,
mit
teilerfremden Ordnungen. Zeigen Sie
o
(
ab
)=
o
(
a
)
o
(
b
)
.
6.3 Zeigen Sie, dass zu jedem Teiler d der Ordnung einer endlichen zyklischen
Gruppe genau eine Untergruppe der Ordnung d existiert (vgl. Lemma 6.6).
6.4
In einer Implementierung des Pohlig-Hellman-Verfahrens sei die Primzahl
=
=
p
263 und e
17 gegeben.
(a) Bestimmen Sie d mit ed
1
(
mod p
)
.
(b) Verschlüsseln Sie die Nachrichten a 1
=
5 und a 2
=
11.
(c) Entschlüsseln Sie die erhaltenen Geheimtexte.
(d) Versuchen Sie aus den Klartexten, den Geheimtexten und der Kenntnis von p ,
auf e zu schließen (sehr rechenaufwändig, benutzen Sie ein Computeralgebra-
System). Das gelingt bei a 1 eindeutig, nicht aber bei a 2 - warum?
(e) Warum ist die Wahl der Primzahl dieser Aufgabe besser als die Wahl im Text?
 
Search WWH ::




Custom Search