AG-Vortrag im WS 2000/01 Die XTR

AG-Vortrag im WS 2000/01
Die XTR-Gruppe∗
(erster Teil des Vortrags)
Roger Fischlin
Universität Frankfurt
5. Januar 2001
Zusammenfassung
Auf dem diskreten Logarithmus basierende, kryptographische Verfahren verwenden
zumeist zyklischen Untergruppen von Z∗p oder elliptische Kurven. Lenstra und Verheul
[XTR] schlagen die Wahl einer Untergruppe hgi von F∗p6 (die in keinen der Unterkörper
einzubetten ist) vor, wobei die Elemente g n ∈ Fp6 durch die Spur (Trace) Tr(g n ) ∈
Fp2 dargestellt werden. Diese Darstellung ist um ein Drittel kompakter und steigert die
Effizienz um den Faktor 3 durch Verwenden der Arithmetik in Fp2 statt in Fp6 .
1
Einführung
1.1
Fp6 und seine Unterkörper
Betrachten wir den endlichen Körper Fp6 . Dieser hat folgende Unterkörper:
• Fp = x ∈ Fp6 xp = x
2
• Fp2 = x ∈ Fp6 xp = x
3
• Fp3 = x ∈ Fp6 xp = x .
6
• Fp6 = x ∈ Fp6 xp = x .
Für alle x, y gilt (x + y)p = xp + y p in Fp6 , insbesondere
p
xap + xbp = xa + xb
für beliebige Exponenten a, b ∈ Z. Zu x ∈ Fp6 ist die Spur (Trace) über Fp2 erklärt als:
2
4
Tr(x) = x + xp + xp ∈ Fp2
∗
A.K. Lenstra und E.R. Verheul: The XTR Public Key System, Crypto 2000, Springer Lecture Notes
in Computer Science, Band 1880, Seiten 1–19, 2000.
1
Obwohl x aus Fp6 , liegt die Spur im Unterkörper Fp2 , denn:
2
2
4 p2
2
4
6 Tr(x)p = x + xp + xp
= xp + xp + |{z}
xp = Tr(x).
=x
p2
p4
Spur ist die Summe von x und
Zu x ∈ Fp6 heißen x und x die Konjugierten über Fp2 . DieP
seiner Konjugierten. Ist x Nullstelle eines Polynoms F (X) = i fi X i ∈ Fp2 [X], so sind auch
2
4
die Konjugierten xp und xp Nullstellen dieses Polynoms:
X
p2 X
X
2
2
2 i
2 i
i
p2
p2
fip xp =
fi xp = F xp .
=
fi x
0 = 0 = F (x) =
i
i
i
Spur und Konjugierte beziehen sich jeweils auf einen Unterkörper. Für das XTR-System
betrachten wir nur Spuren und Konjugierte über Fp2 , weshalb wir kurz von Spur und Konjugierten sprechen.
1.2
Untergruppen von F∗p6
Für die (zyklische) Einheitengruppe F∗p6 gilt1
|F∗p6 | = p6 − 1 = (p − 1)(p + 1)(p2 + p + 1)(p2 − p + 1).
Untergruppen von F∗p6
• deren Ordnung p − 1 teilt, können in Fp ,
• deren Ordnung p + 1 teilt, können in Fp2 und Untergruppen
• deren Ordnung p2 + p + 1 teilt, können in Fp3
eingebettet werden, denn |Fp2 | = p2 −1 = (p+1)(p−1) und |Fp3 | = p3 −1 = (p2 +p+1)(p−1).
Untergruppen primer Ordnung q|p2 − p + 1 mit q > 6 lassen sich hingegen in keinen echten
Unterkörper von Fp6 einbetten [L97].
1.3
Herkunft der Bezeichnung XTR“
”
XTR ist die kurze Schreibweise für das gleichlautende ECSTR, welches seinerseits die Abkürzung
für
Efficient and Compact Subgroup Trace Representation
ist. Weil die Autoren aufgrund der Effizienz XTR als Alternative zu elliptischen Kurven
betrachten, heißt es gerüchteweise, ECSTR stände für
Elliptic Curves Soon To Retire.
Als Anspielung die Kritik von Menezes und Vanstone [MV00] (Universität Waterloo, Kanada),
die weiterhin elliptische Kurven als bessere Wahl betrachten, verwendet Lenstra auf einer
Vortragsfolie die Überschrift
Evil Canadians Surely Take Revenge,
Weitere Interpretationen der Abkürzung ECSTR sind (noch?) nicht bekannt.
1
Die Zerlegung folgt aus der bekannten Faktorisierung des 6-ten Kreisteilungspolynoms ausgewertet an der
Stelle p.
2
2
Darstellung der Elemente einer Untergruppe
2.1
Grundlagen
Sei p ≡ 2 (mod 3) eine Primzahl derart, dass p2 − p + 1 einen Primfaktor q > 6 hat. Sei
g ∈ F∗p6 ein Element der Ordnung q, nach Wahl von p und q ist die Untergruppe hgi in keinem
echten Unterkörper von Fp6 enthalten. Wir operieren nicht unmittelbar mit den Elementen
hgi ⊆ Fp6 , sondern mit deren Spuren über Fp2 , weshalb wir eine Darstellung der Elemente
von Fp2 benötigen.
Die Restklasse p mod 3 erzeugt die Gruppe Z∗3 (da p ≡ 2 (mod 3)), so dass die beiden
Nullstellen α, αp des Polynoms (X 3 − 1)/(X − 1) = X 2 + X + 1 eine optimale Normalbasis
von Fp2 über Fp bilden. Weil αp = αp mod 3 = α2 ist, kann x ∈ Fp2 geschrieben werden als
x = x1 α + x2 αp = x1 α + x2 α2
mit x1 , x2 ∈ Fp . Das Element t ∈ Fp hat bezüglich der optimalen Normalbasis α, α2 die
Darstellung t = −tα − tα2 , denn wegen α2 + α + 1 = 0 gilt 1 = −α − α2 .
Lemma 2.1.1. Seien x, y, z ∈ Fp2 mit p ≡ 2 (mod 3). Dann gilt:
i) die Berechnung von xp ist ohne Multiplikationen,
ii) die Berechnung von x2 ist mit 2 Multiplikationen,
iii) die Berechnung von xy ist mit 3 Multiplikationen und
iv) die Berechnung von xz − yz p ist mit 4 Multiplikationen
über Fp möglich (Additionen nicht mitgezählt).
Beweis. Seien x = x1 α + x2 α2 , y = y1 α + y2 α2 und z = z1 α + z2 α2 . Um xp zu berechnen,
sind lediglich die beiden Koeffizienten x1 und x2 zu vertauschen:
p
2
xp = x1 α + x2 αp = xp1 αp + xp2 αp = x2 α + x1 αp = x2 α + x1 α2
Betrachten wir die Multiplikation:
xy = x1 α + x2 α2 y1 α + y2 α2
= x1 y1 α2 + x1 y2 α3 + x2 y1 α3 + x2 y2 α4
= (x1 y2 + x2 y1 ) +x2 y2 α + x1 y1 α2
|
{z
}
∈Fp
Wegen x1 y2 + x2 y1 = −(x1 y2 + x2 y1 )α − (x1 y2 + x2 y1 )α2 folgt:
xy = x2 y2 − (x1 y2 + x2 y1 ) α + x1 y1 − (x1 y2 + x2 y1 ) α2
(1)
Um das Produkt xy zu berechnen, genügen drei Multiplikationen über Fp , nämlich x1 y1 , x2 y2
und (x1 + x2 )(y1 + y2 ), denn:
x1 y2 + x2 y1 = (x1 + x2 )(y1 + y2 ) − x1 y1 − x2 y2 .
3
Zum Quadrieren von x sind zwei Multiplikationen über Fp ausreichend, da nach Gleichung
(1) mit y := x gilt:
x2 = x22 − 2x1 x2 α + x21 − 2x1 x2 α2
= x2 (x2 − 2x1 )α + x1 (x1 − 2x1 )α2
= x2 (x2 − x1 − x1 )α + x1 (x1 − x2 − x1 )α2 .
Um xz − yz p zu berechnen, greifen wir auf Gleichung (1) zurück, wobei z p = z2 α + z1 α2 :
xz − yz p = x2 z2 − (x1 z2 + x2 z1 ) α + x1 z1 − (x1 z2 + x2 z1 ) α2
= y2 z1 − (y1 z1 + y2 z2 ) α − y1 z2 − (y1 z1 + y2 z2 ) α2
= x2 z2 − x1 z2 − x2 z1 − y2 z1 + y1 z1 + y2 z2 α
+ x1 z1 − x1 z2 − x2 z1 − y1 z2 + y1 z1 + y2 z2 α2
= z1 (y1 − x2 − y2 ) + z2 (x2 − x1 + y2 ) α
+ z1 (x1 − x2 + y1 ) + z2 (y2 − x1 − y1 α2
Die Berechnung von xz − yz p ist mit 4 Multiplikationen über Fp möglich.
Die Spur-Darstellung basiert auf den Operationen aus Lemma 2.1.1. Die Diskreten-LogVerfahren in der Gruppe F∗p6 verwenden folgende Operationen:
Lemma 2.1.2. Seien x, y, z ∈ Fp6 mit p ≡ 2 (mod 3) und a, b ∈ [1, p). Setzt man den
Aufwand zum Quadrieren mit 80% einer Multiplikation an, gilt für die besten, bekannten
Verfahren:2
i) die Berechnung von x2 benötigt 14, 4 Multiplikationen,
ii) die Berechnung von xy benötigt 18 Multiplikationen,
iii) die Berechnung von xa benötigt im Durchschnitt 23, 4 · log2 a Multiplikationen und
iv) die Berechnung von xa y b benötigt im Durchschnitt 27, 9 · log2 max{a, b} Multiplikationen
über Fp (Additionen nicht mitgezählt).
2.2
Spur
Sei g ∈ F∗p6 eine Element, dessen Ordnung q ein Teiler von p2 − p + 1 sei. Modulo p2 − p + 1
gilt
p2 ≡ p − 1
p5 ≡ 1 − p
p3 ≡ p2 − p ≡ −1
p6 ≡ 1
4
2
p ≡ (p − 1) ≡ −p,
2
4
so dass die Konjugierten über Fp2 von g gleich g p = g p−1 und g p = g −p sind:
2
4
Tr(g) = g + g p + g p = g + g p−1 + g −p
3
5
Tr(g)p = g p + g p + g p = g p + g −1 + g 1−p .
2
Die Durchschnittswerte beziehen sich auf die Exponenten a, b.
4
(2)
Lemma 2.2.1. Die Ordnung von g teile p2 − p + 1. Die Wurzeln des Polynoms
X 3 − Tr(g)X 2 + Tr(g)p X − 1
(3)
sind g und seine Konjugierten, d.h. die Nullstellen sind g, g p−1 und g −p .
Beweis. Wir vergleichen die Koeffizienten von (3) mit denen des normierten Polynoms
X − g X − g p−1 X − g −p .
(4)
Das Absolutglied ist g · g p−1 · g −p = g 1+p−1−p = g 0 = 1 und der X-Koeffizient
g · g p−1 + g · g −p + g p−1 · g −p = g p + g 1−p + g −1 = Tr(g)p .
Der X 2 -Koeffizient von (4) ist g + g p−1 + g −p = Tr(g), so dass (3) und (4) gleich sind.
Mit der gleichen Technik wie im Beweis zu Lemma 2.2.1 kann man zeigen, dass allgemein
für alle n ∈ Z die Wurzeln des Polynoms
F (Tr(g n ), X) := X 3 − Tr(g n )X 2 + Tr(g n )p X − 1 ∈ Fp2 [X]
die Konjugierten von g n sind. Die Spur Tr(g n ) ∈ Fp2 liefert eine kompakte Darstellung der
Konjugierten von g n ∈ Fp6 . Um diese kompakte Spur-Darstellung für kryptographische Anwendungen zu nutzen, entwickeln wir im weiteren einen effizienten Algorithmus, der Tr(g n )
aus Tr(g) und n berechnet. Umgekehrt, da Polynome über Körpern effizient zu faktorisieren
sind, liefern die Nullstellen von F (Tr(g n ), X) die Werte g n und seine Konjugierten.
2.3
Das Polynom F (c, X)
Wir betrachten Polynome der Form X 3 − cX 2 + cp X + 1 für beliebige c ∈ Fp2 :
Def inition 2.3.1 (Polynom F (c, X), cn ). Zu c ∈ Fp2 sei
F (c, X) := X 3 − cX 2 + cp X − 1 ∈ Fp2 [X]
und h0 , h1 , h2 ∈ Fp6 die (nicht notwendigerweise paarweise verschiedenen) Nullstellen. Zu
n ∈ Z schreiben wir
cn := hn0 + hn1 + hn2 ∈ Fp6
für die Summe der n-ten Potenzen der Wurzeln.
Weil die Nullstellen von F (Tr(g n ), X) gerade g n und seine Konjugierten sind (beweisen wir
formal in Lemma 2.3.4.i)), gilt für c := Tr(g), dass cn = Tr(g n ).
Lemma 2.3.2. Sei c ∈ Fp2 . Dann für F (c, X) und seine Wurzeln h0 , h1 , h2 :
i) c0 = 3, c1 = c.
ii) h0 · h1 · h2 = 1.
iii) hn0 · hn1 + hn0 · hn2 + hn1 · hn2 = c−n für alle n ∈ Z.
5
−p
iv) Mit hj ist auch h−p
j eine Nullstelle von F (c, X), d.h. F (c, hj ) = 0 für j = 0, 1, 2.
v) c−n = cnp = cpn für alle n ∈ Z.
vi) Entweder sind die Ordnungen von h0 , h1 , h2 größer als 3 und teilen p2 − p + 1 oder
sämtliche Wurzeln h0 , h1 , h2 liegen in Fp2 .
vii) cn ∈ Fp2 für alle n ∈ Z.
Aus Punkt vi) folgt unmittelbar:
Bemerkung 2.3.3. Das Polynom F (c, X) ∈ Fp2 [X] ist genau dann irreduzibel, wenn die
Ordnungen seiner Wurzeln größer als 3 sind und p2 − p + 1 teilen.
Beweis zu Lemma 2.3.2. Es gilt:
F (c, X) = X 3 − cX 2 + cp X − 1 = (X − h0 )(X − h1 )(X − h2 ).
(5)
i) Es gilt c0 = h00 + h01 + h02 = 1 + 1 + 1 = 3. Die Identität c = c1 folgt aus (5), denn der
X 2 -Koeffizient von (X − h0 )(X − h1 )(X − h2 ) ist h0 + h1 + h2 = c1 .
ii) Das Absolutglied von (X − h0 )(X − h1 )(X − h2 ) ist gleich h0 · h1 · h2 , also h0 · h1 · h2 = 1.
iii) Wegen h0 · h1 · h2 = 1 gilt:
c−n = c−n · (h0 · h1 · h2 )n
−n
−n
· hn0 · hn1 · hn2
= h−n
0 + h 1 + h2
= hn1 · hn2 + hn0 · hn2 + hn0 · hn1 .
iv) Wegen F (c, 0) = −1 sind die Nullstellen h0 , h1 , h2 ungleich Null und die Inversen h−1
j
2
existieren. Aus F (c, hj ) = 0 erhält man, da für c ∈ Fp2 gilt cp = c:
3p
p 2p
p2 p
0 = F (c, hj )p = h3p
h−3p
− ch2p + cp hpj − 1 .
j − c hj + c hj − 1 = −hj
j
|
{z
}
=F c,h−p
j )
v) Aus Punkt iv) folgt, dass o.B.d.A. einer der folgenden Fälle vorliegt:
• hj = h−p
j für j = 0, 1, 2.
−p
−p
• h0 = h−p
0 , h1 = h2 und h2 = h1 .
−p
−p
• h0 = h−p
1 , h1 = h2 und h2 = h0 .
P
P −n
In allen drei Situationen ist j hnp
j hj , und es gilt:
j =
cpn
=
X
2
j=0
hnj
p
=
X
2
hnp
j
j=0
= cnp =
X
2
h−n
j
j=0
vi) Betrachte die Fallunterscheidung aus dem vorherigen Beweis:
6
= c−n .
• Aus hj = h−p
folgt hp+1
= 1. Die Wurzeln h0 , h1 , h2 liegen in Fp2 , denn für
j
j
j = 0, 1, 2 gilt:
2
(p+1)(p−1)+1
hpj = hj
= 1(p−1) · hj = hj
−p
−p
• Im Fall h0 = h−p
0 , h1 = h2 und h2 = h1 sind die Wurzeln h0 , h1 , h2 in Fp2 , denn:
2
hp0 = h0
2
hp1 = hp2 = h1
2
hp2 = hp1 = h2 ,
−p
−p
• Es gelte h0 = h−p
1 , h1 = h2 und h2 = h0 . Aus
2
2 −p+1
−p
−p
p
1 = h0 · h1 · h2 = h0 · h−p
· h−p
2 · h0 = h0 · h 0
0 = h0
folgt ord(h0 )|p2 −p+1. Dies gilt ebenfalls für die Ordnungen von h1 und h2 . Betrachten wir die Situation, eine der Ordnungen sei maximal drei, o.B.d.A. ord(h0 ) ≤ 3.
Weil p2 −p+1 ungerade, ist die Ordnung ord(h0 ) ungleich 2. Folglich gilt ord(h0 )|3.
Nach Wahl von p ≡ 2 (mod 3) ist p2 − 1 ≡ 0 (mod 3). Somit ord(h0 )|p2 − 1 und
h0 liegt im Unterkörper Fp2 . Dann liegen auch die beiden anderen Wurzeln h1 , h2
in Fp2 , denn aus der Voraussetzungen hp0 = h1 und hp1 = h2 erhalten wir:
2
3
2
3
hp1 = hp0 = hp0 = h1
hp2 = hp1 = hp1 = h2
Die Ordnung von h0 , h1 , h2 teilen p2 − p + 1. Ist eine dieser Ordnungen maximal
drei, liegen alle Wurzeln in Fp2 .
vii) Liegt eine der Wurzeln h0 , h1 , h2 im Unterkörper Fp2 , dann gilt nach Punkt vi), dass
h0 , h1 , h2 ∈ Fp2 , und wir erhalten cn = hn0 + hn1 + hn2 ∈ Fp2 . Im anderen Fall ist F (c, X)
2
4
irreduzibel über Fp2 und die Wurzeln sind h0 , hp0 , hp0 . Es folgt:
2
4
cn = hn0 + hn1 + hn2 = hn0 + (hn0 )p + (hn0 )p = Tr(hn0 ) ∈ Fp2 .
Damit ist Lemma 2.3.2 bewiesen.
Lemma 2.3.4. Es gilt:
i) Für alle n ∈ Z sind die Wurzeln von F (cn , X) n-te Potenzen der Wurzeln von F (c, X),
also F (cn , hnj ) = 0 für j = 0, 1, 2.
ii) Für alle u, v ∈ Z gilt: cu+v = cu cv − cpv · cu−v + cu−2v .
iii) Genau dann ist F (c, X) reduzibel, wenn cp+1 ∈ Fp .
Beweis. Es gilt:
7
i) Wir zeigen, dass F (cn , X) gleich dem Polynom
X − hn0 X − hn1 X − hn2
(6)
ist. Das Absolutglied ist gleich (hn0 · hn1 · hn2 ) = (h0 h1 h2 )n = 1. Der X 2 -Koeffizient von
(6) lautet hn0 + hn1 + hn2 = cn . Der X-Koeffizient entspricht nach Punkten iii) und v) von
Lemma 2.3.2:
hn0 · hn1 + hn0 · hn2 + hn1 · hn2 = c−n = cpn ,
so dass F (c, X) gleich (6) ist.
ii) Aus i) gilt für j = 0, 1, 2
2v
p v
0 = F (cv , huj ) = h3v
j − cv hj + cv hj − 1,
p v
u−2v
2v
liefert:
und wir erhalten h3v
j = cv hj − cv hj + 1. Multiplikation mit hj
hu+v
= cv huj − cpv hu−v
+ hu−2v
.
j
j
j
Wegen cn = hn0 + hn1 + hn2 erhalten wir die Behauptung durch Addition der drei Gleichungen für j = 0, 1, 2.
iii) Angenommen, F (c, X) sei reduzibel, d.h. mindestens eine der Nullstellen h0 , h1 , h2 liegt
in Fp2 . Nach Aussage v) von Lemma 2.3.2 liegen dann sämtliche Nullstellen in Fp2 .
Wegen
(p+1)p
hj
(p2 −1)+p+1
= hj
= hp+1
j
gilt hp+1
∈ Fp für j = 0, 1, 2 und wir erhalten cp+1 = hp+1
+ hp+1
+ hp+1
∈ Fp . Für die
0
1
2
j
p
Rückrichtung sei cp+1 ∈ Fp2 . Dann gilt cp+1 ∈ Fp und 1 ist eine Wurzel des Polynoms
F (cp+1 , X) = X 3 − cp+1 X 2 + cp+1 X − 1.
Aus Punkt i) wissen wir, dass die Wurzeln von F (cp+1 , X) (p + 1)-te Potenzen der
Wurzeln von F (c, X) sind, so dass F (c, X) eine Wurzel hat, deren Ordnung p + 1 und
somit p2 − 1 = (p + 1)(p − 1) teilt. Diese Wurzel liegt in Fp2 und F (c, X) ist reduzibel.
Korollar 2.3.5. Für alle n ∈ Z kann man aus c, cn−1 und cn+1
i) c2n = c2n − 2cpn mit 2 Multiplikationen in Fp und
ii) cn+2 = c · cn+1 − cp · cn + cn−1 sowie cn−2 = cn+1 − c · cn + cp · cn−1 ,
iii) c2n−1 = cn−1 · cn − cp · cpn + cpn+1
iv) c2n+1 = cn+1 · cn − c · cpn + cpn−1
mit jeweils 4 Multiplikationen in Fp berechnen.
8
Beweis. Nach Lemma 2.3.2.v) gilt c−u = cpu und nach Lemma 2.3.4.ii)
cu+v = cu cv − cpv · cu−v + cu−2v
(7)
für alle u, v ∈ Z. Aus Lemma 2.3.2.i) wissen wir c0 = 3 und c1 = c. Die Behauptung i) folgt
mit u := v := n aus Gleichung (7):
c2n = cn cn − cpn c0 + c−n = c2n − 3cpn + cpn = c2n − 2cpn .
Mit u := n + 1 und v := 1 erhalten wir aus (7) den ersten Teil der Behauptung ii):
cn+2 = cn+1 c1 + cp1 cn + cn−1 = cn+1 c + cp cn + cn−1 .
Für den zweiten Teil der Aussage ersetze n durch n − 1 und löse die Gleichung nach cn−2 auf.
Behauptung iii) folgt aus (7) mit u := n − 1 und v := n:
c2n−1 = cn−1 cn + cpn c−1 + c−1−n = cn−1 cn + cp cpn + cpn+1
Die Behauptung iv) erhalten wir (7) mit u := n + 1 und v := n:
c2n+1 = cn+1 cn + cpn c1 + c1−n = cn−1 cn + ccpn + cpn−1
Die Anzahl der Multiplikationen ist eine direkte Konsequenz aus Lemma 2.1.1. Um cn−1 aus
c, cn und cn+1 zu berechnen, wende ii) an.
Def inition 2.3.6 (Sn (c)). Zu c ∈ Fp2 setze Sn (c) := cn−1 , cn , cn+1 ∈ F3p2 .
Nach Lemma 2.3.2 und Korollar 2.3.5 gilt:
S0 (c) = [c−1 , c0 , c1 ] = cp , 3, c
S1 (c) = [c0 , c1 , c2 ]
= 3, c, c2 − 2cp
S2 (c) = [c1 , c2 , c3 ]
= c, c2 − 2cp , cc2 + cp+1 + 3
Um Sn (c) für gegebenes c und n zu berechnen, wende Algorithmus 2.3.7:
Algorithmus 2.3.7 (Berechne von Sn (c) gegeben c, n).
1) IF n < 0 THEN berechne S−n (c) und wende Lemma 2.3.2.v), c−n = cpn , an.
2) IF n ∈ {0, 1, 2} THEN gib Sn (c) direkt aus (Gleichungen (8)).
3) IF (n ungerade) THEN m := n ELSE m := n − 1.
4) Sei m = 2m + 1 und S m (c) := Sm (c).
5) Setze k := 1. Berechne S 2k (c) = S3 (c) nach Korollar 2.3.5.ii) mit Hilfe von S2 (c).
P
6) Sei m = ri=0 mj 2j mit m ∈ {0, 1} und mr = 1.
7) FOR j = r − 1, r − 2, . . . , 0 DO
/* Wir kennen S k (c) = c2k , c2k+1 , c2k+2 . */
9
(8)
(a) IF mj = 0 THEN berechne S 2k (c) = c4k , c4k+1 , c4k+2 aus S k (c). Verwende Korollar 2.3.5.i) für c4k und c4k+2 sowie Korollar 2.3.5.iii) für c4k+1 . Setze k := 2k.
(b) IF mj = 1 THEN berechne S 2k+1 (c) = c4k+2 , c4k+3 , c4k+4 aus S k (c). Verwende
Korollar 2.3.5.i) für c4k+2 und c4k+4 sowie Korollar 2.3.5.iv) für c4k+3 . Setze k :=
2k + 1.
END for
/* Es gilt k = m und Sm (c) = S k (c) */
8) IF (n gerade) THEN verwende Sm (c) = [cm−1 , cm , cm+1 ] um Sm+1 (c) = [cm , cm+1 , cm+2 ]
nach Korollar 2.3.5.ii) zu berechnen. Setze m := m + 1.
9) Gib Sn (c) = Sm (c) aus.
Für den Korrektheitsbeweis des Algorithmus’ 2.3.7 weist man induktiv die SchleifenInvariante nach. Aus Korollar 2.3.5 erhalten wir:
Theorem 2.3.8. Aus der Summe c der Wurzeln von F (c, x) kann man die Summe cn der
n-ten Potenzen der Wurzeln mit 8 · log2 n Multiplikationen in Fp berechnen.
Bemerkung 2.3.9. Betrachten wir die Fallunterscheidung in der Schleife. Im Gegensatz
zu den bekannten Verfahren zum Berechnen von Potenzen, ist hier das Vorgehen in beiden
Fällen sehr ähnlich. Dies legt die Vermutung nah, dass der Algorithmus weniger anfällig gegen
Timing-Attacken und Power-Differential-Analysis (PDA) ist.
2.4
Rechnen mit der Spur
Nach Lemma 2.2.1 und Lemma 2.3.4.i) ist Tr(g n ) die Summe cn der n-ten Potenzen der
Wurzeln des Polynoms F (Tr(g), X). Wegen ord(g) = q gilt cn = c(n mod q) . Algorithmus 2.3.7
bestimmt
Sn (Tr(g)) = Tr(g n−1 ), Tr(g n ), Tr(g n+1 )
in 8 · log2 (n mod q) Multiplikationen in Fp . Zum Vergleich: Die besten, bekannten Verfahren
benötigen zum Berechnen von g n im Durchschnitt 23, 4 · log2 q Multiplikationen. Die Bestimmung von Tr(g n ) ist damit um den Faktor 3 schneller, ebenso belegt die Spur Tr(g n ) ∈ Fp2
nur ein Drittel der Bits von g n ∈ Fp6 .
Für die Übertragung der Identifikationsschema auf die XTR-Gruppe entwickeln wir im
folgenden einen effizienten Algorithmus, um aus a, b und Tr(g k ) (für unbekanntes k) die Spur
von g a · g ka zu berechnen.
Def inition 2.4.1 (Matrizen An (c), Mn (c)). Zu c ∈ Fp2 definiere die 3 × 3-Matrizen


0 0 1
A(c) := 1 0 −cp 
0 1
c


cn−2 cn−1 cn
Mn (c) := cn−1 cn cn+1 
cn cn+1 cn+2
über Fp2 mit cn aus Definition 2.3.1.
10
Mit Hilfe von Lemma i).2.3.2 und der Rechenregeln aus Korollar 2.3.5 erhalten wir:

  p p

c−2 c−1 c0
c2 c
3
M0 (c) = c−1 c0 c1  = cp 3 c 
c0
c1 c2
3 c c2
Unabhängig von c gilt det A(c) = 1, die Inverse ist
 p
c
A(c)−1 := −c
1
(9)
gegeben durch:

1 0
0 1 .
0 0
Vergleichen wir die Matrizen Mn (c) und Mn+1 (c):




cn−2 cn−1 cn
cn−1 cn cn+1
Mn (c) = cn−1 cn cn+1 
Mn+1 (c) =  cn cn+1 cn+2 
cn cn+1 cn+2
cn+1 cn+2 cn+3
Beim Übergang von n auf n + 1 wird die zweite Spalte zur ersten, die dritte zur mittleren
und die dritte Spalte ergibt sich aus den folgenden Identitäten nach Korollar 2.3.5.ii):
cn+1 = c · cn − cp · cn−1 + cn
cn+2 = c · cn+1 − cp · cn + cn−1
cn+3 = c · cn+2 − cp · cn+1 + cn
Genau diese Transformationen bewirkt die Multiplikation mit A(c), also Mn+1 (c) = Mn (c) ·
A(c). Da A(c) invertierbar ist, gilt Mn−1 (c) = Mn (c) · A(c)−1 . Weil Sn (c) die mittlere Zeile
von Mn (c) ist, gilt:
Mn+1 (c) = Mn (c) · A(c)
Sn+1 (c) = Sn (c) · A(c)
Mn−1 (c) = Mn (c) · A(c)−1
Sn−1 (c) = Sn (c) · A(c)−1 .
Induktiv folgt:
Lemma 2.4.2. Für alle m, n ∈ Z gilt:
Sn (c) = Sm (c) · A(c)n−m
Mn (c) = Mm (c) · A(c)n−m .
Da cn das mittlere Element des Vektors Sn (c) ist, gilt ferner:
Korollar 2.4.3. Bezeichne C(·) die mittlere Spalte einer 3 × 3-Matrix. Dann gilt:
cn = Sm (c) · C A(c)n−m .
Aus dieser Identität folgt, dass man gegeben e ∈ Z, c und Sk (c) (für ein unbekanntes k)
ck+e berechnen kann, denn
ck+e = Sk (c) · C A(c)e .
Für unsere Anwendungen suchen wir ein effizientes Verfahren, um die Potenzen von A(c) für
c = Tr(g) zu berechnen.
11
Lemma 2.4.4. Es gilt für die Matrix M0 (c) aus (9):
det M0 (c) = c2(p+1) + 18cp+1 − 4 c3p + c3 ∈ Fp .
Sofern invertierbar, ist die Inverse gegeben durch:


2c2 − 6cp
2c2p + 3c − cp+2
cp+1 − 9
1
2c2p + 3c − cp+2 (c2 − 2cp )p+1 − 9 (2c2p + 3c − cp+2 )p 
M0 (c)−1 =
det M0 (c)
cp+1 − 9
(2c2p + 3c − cp+2 )p
(2c2 − 6cp )p
Beweis. Man überzeuge sich durch Nachrechnen (unter Berücksichtigung von Lemma 2.3.2.v)
2
und Korollar 2.3.5, dass die angegebene Determinante und Inverse korrekt sind. Wegen cp = c
stimmt die Determinante mit ihrer p-ten Potenz überein
2
2
2
det M0 (c)p = c2(p +p) + 18cp +p − 4 c3p + c3p
= c2(1+p) + 18c1+p − 4 c3 + c3p
= det M0 (c)
und liegt im Unterkörper Fp .
Aus Lemma 2.4.2 erhalten wir A(c)n = M0 (c)−1 · Mn (c). Aus dieser Identität werden
wir einen Algorithmus zur Berechnung der Potenzen von A(Tr(g)) aufbauen. Dazu muss
sichergestellt sein, dass die Matrix M0 (Tr(g))−1 invertierbar ist.
Lemma 2.4.5. Es gilt:
2
det M0 (Tr(g)) = Tr(g p+1 )p − Tr(g p+1 ) 6= 0.
.
Beweis. M0 (Tr(g)) (vergleiche (9)) ist das Produkt einer Matrix und seiner Transponierten:
 −1 −p2
g
g

1
M0 (Tr(g)) = 1
2
g
gp
4   −1
g
g −p
2


1
· g −p
4
4
g −p
gp

1 g
2
1 gp  .
4
1 gp
Die Determinante der Matrix ist Tr(g p+1 )p − Tr(g p+1 ) (folglich auch die der Transponierten).
Die beiden Behauptungen sind unter Beachtung der Rechenregeln (2) leicht nachzurechnen.
Lemma 2.4.6. Aus Tr(g) und Sn (Tr(g)) ist A(Tr(g))n mit einer kleinen, konstanten Anzahl
von Operationen in Fp2 zu berechnen.
Beweis. Sei c := Tr(g). Aus Sn (c) = cn−1 , cn , cn+1 berechne mit Hilfe von Korollar 2.3.5.ii)
cn±2 . Mit den Werten aus Sn (c) ergibt dies die Einträge der Matrix Mn (c). Aus
A(c)n = M0 (c)−1 · Mn (c)
und den beiden Lemma 2.4.4 und 2.4.5 folgt die Behauptung.
12
Korollar 2.4.7. Es gilt:
C A(Tr(g)n = M0 (Tr(g))−1 · Sn (Tr(g))T .
Algorithmus 2.4.8 (Berechne von Tr(g a · g bk ) gegeben Tr(g), Sk (Tr(g)) und a, b ∈ [1, q)).
1) e := ab−1 mod q.
2) Bestimme mit Algorithmus 2.3.7 Se (Tr(g)).
3) Bestimme C A(Tr(g))e mit Hilfe von Korollar 2.4.7 aus Tr(g) und Se (Tr(g)).
4) Bestimme mit Hilfe von Korollar 2.4.3 Tr(g e+k ) = Sk (Tr(g)) · C A(Tr(g))e .
5) Bestimme mit Algorithmus 2.3.7 Sb Tr(g e+k ) .
6) Gib Tr(g (e+k)b ) = Tr(g a · g bk ) aus.
Die Laufzeit des Verfahrens 2.4.8 wird dominiert
von den beiden Aufrufen des Algorithmus’
2.3.7 zur Berechnung Se (Tr(g)) und Sb Tr(g e+k ) . Nach Theorem 2.3.8 können wir die Anzahl
der Multiplikationen in Fp mit 8 · log2 e und 8 · log2 b nach oben abschätzen:
−1
Theorem 2.4.9. Zu Tr(g), M0 Tr(g)
und Sk (Tr(g)) = Tr(g k−1 ), Tr(g k ), Tr(g k+1 ) für
ein unbekanntes k kann man die Spur Tr(g a · g bk ) von g a · g bk mit
8 · log2 (ab−1 mod q) + 8 · log2 b + 34
Multiplikationen in Fp berechnen.
13
3
Wahl der Parameter
3.1
Wahl des endlichen Körpers und der Gruppenordnung
3.2
Wahl der Untergruppe
3.3
Sicherheitsparameter
4
Kryptographische Anwendungen
4.1
XTR-Diffie-Hellman
4.2
XTR-ElGamal
4.3
XTR-Nyberg-Rueppel-Unterschriften
4.4
Vergleich mit RSA und elliptischen Kurven
5
Sicherheit
5.1
Diskreter Logarithmus in Fpt
5.2
XTR
Literatur
[MV00]
A. Menezes und S. Vanstone: ECSTR (XTR): Ellitpic Curve Singular Trace
Representation, Rump-Session Crypto 2000.
[L97]
A.K. Lenstra: Using Cyclotomic Polynomials to Construct Efficient Discrete
Logarithmic Cryptosystems over Finite Fields, ACISP ’97, Springer Lecture Notes
in Computer Science, Band 1270, Seiten 127–138, 1997. 2000. Erhätlich auf [Web].
[XTR]
A.K. Lenstra und E.R. Verheul: The XTR Public Key System, Crypto 2000,
Springer Lecture Notes in Computer Science, Band 1880, Seiten 1–19, 2000.
Erhätlich auf [Web].
[Web]
Web-Site www.ecstr.com.
14