-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathweil_descent.html
269 lines (231 loc) · 7.56 KB
/
weil_descent.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
<html>
<head>
<title>Weil Descent Page</title>
</head>
<BODY background="back4.jpg"
TEXT="#ffffff"
LINK="#ffff00"
VLINK="#00ff00"
>
<h1>Weil Descent Page</h1>
This page is devoted to the new technique of Weil descent
as described in the papers:
<ul>
<li>A cryptographic application of Weil descent,
by S.D. Galbraith and N.P. Smart.
Proceedings Cryptography and Coding, Springer LNCS 1746, pp 191-200. (1999)
<li>
Constructive and Destructive Facets of Weil Descent on Elliptic Curves,
by P. Gaudry, F. Hess and N.P. Smart.
<li>
Two topics in hyperelliptic cryptography,
by F. Hess, G. Seroussi and N.P. Smart.
<li>
<a href="http://cacr.math.uwaterloo.ca/techreports/2000/corr2000-48.ps">
Analysis of the Weil Descent Attack of Gaudry, Hess and Smart</a>
by A. Menezes and M. Qu.
<li>
How secure are elliptic curves over composite extension fields?
by N.P. Smart.
<li>
<a href="http://eprint.iacr.org/2001/041/">
Solving Elliptic Curve Discrete Logarithm Problems Using Weil Descent</a>
by M. Jacobson, A. Menezes and A. Stein
<li>
Limitations of constructive Weil descent,
by S.D. Galbraith.
<li>
Weil descent of Jacobians, by S.D. Galbraith.
<li>
<a href="http://eprint.iacr.org/2001/054/">
Extending the GHS Weil Descent Attack</a>
by S.D. Galbraith, F. Hess and N.P. Smart.
<li>Analysis of the GHS Weil descent attack on the ECDLP
over characteristic two finite fields of composite degree
by M. Maurer, A. Menezes and E. Teske.
</ul>
Weil descent is a technique in the area of elliptic curve cryptography.
Elliptic curve cryptography is a public key technique which allows
for the use of cryptography in applications which are constrained by
bandwidth, CPU time or memory.
This not only includes small devices but also large overworked servers
trying to deal with heavy traffic loads generated by e-commerce applications.
<hr>
The main paper by Gaudry, Hess and Smart (GHS) can be summarized
by the following: <p>
Let E denote an elliptic curve over a field, K, of q^n elements where
q is a power of two. <p>
Then there exists a hyperelliptic curve, H, of genus
<center>
2^{m-1} or 2^{m-1}-1
</center>
defined over the field, k, of q elements such that there is a computable
group homomorphism
<center>
E(K) ----> Jac_H(k)
</center>
The number m is a "magic number" which controls how hard or easy it is
to use this approach. See the above paper for a more detailed description. <p>
This is ofcourse all a bit mathematical and hence we explain this in more
down to earth terms below.
There are essentially two ways to interpret this result, one
constructively and one destructively.
<hr>
<h2>Destructive Implications</h2>
One can map the discrete logarithm problem from the elliptic curve
over to the hyperelliptic curve. <p>
Hence if the genus is about the size of n and this is not too large
then this can give reduced security. <p>
<h3>Solution</h3>
One should always use either a field with a prime number of elements
or use a field of the form 2^p, where p is a prime. <p>
In other words you should deploy systems which are <b>standards
compliant</b>. Following the standards layed down by
<a href="http://www.secg.org/">SECG</a> is probably the best approach.
After all these standards have been developed by the worlds leading
experts in the area of the elliptic curve cryptography. <p>
<h3>Koblitz Curves</h3>
It should be noted that over any field Koblitz curves are resistent to
the above attack (since for Koblitz curves the number m will always
be equal to one) as it is described in the GHS work. <p>
Recent work of Frey and his students has extended the GHS work to
Koblitz curves.
Hence, Koblitz curves also only be used over fields of the form
2^p, where p is a prime. <p>
<hr>
<h2>Constructive Implications</h2>
The work also allows us to construct hyperelliptic curves of
small genus with known group order.
Hence one can now deploy hyperelliptic cryptosystems.
For example consider the field of 2^131 elements defined by the
polynomial
<center>
t^131 + t^8 + t^3+t^2 + 1=0.
</center>
Over this field we define the hyperelliptic curve of genus two
<center>
Y^2 + H(X) Y = F(X)
</center>
where
<center>
<table>
<tr>
<td> H(X) = </td>
<td> 531DF454AD40EFDC0D6CAE356D574810F X^2 </td>
</tr>
<tr>
<td> </td>
<td> + 3561FA9336C3CA3F080AB1FEE1F789636 X </td>
</tr>
<tr>
<td> </td>
<td> + 2D82C28316120279E55BF01B0AD476DC5, </td>
</tr>
</table>
</center>
and
<center>
<table>
<tr>
<td> F(X) = </td>
<td> 138BE9EF56BA5C72A8CE09AA4C3590B9 X^5
+ DB308DD57C16D90670C4A311DB298F43 X^4
</td>
</tr>
<tr>
<td> </td>
<td> + 4FEB32114979B67F1CF2D5B73B57ABCAE X^3
+ 63A3FD1EB41F004DD75D7E1E485C07AA4 X^2
</td>
</tr>
<tr>
<td> </td>
<td> + 5593CEF38C79C53D1B7A7B81AAF39E4D0 X
+ 57D20BB08FC9578EB750D98A07C6D94AB.
</td>
</tr>
</table>
</center>
This curve has group order
<center>
7410693711188236507108543040556026102606669553107633893031957930119262165819774
</center>
which is two times a prime.
<hr>
<h2>Weil Descent Program</h2>
A <a href="http://www.math.tu-berlin.de/~kant/kash.html">KASH</a>
program is now available which given an elliptic curve
with various points on it will not only produce the associated
hyperelliptic curve but will also map the point over to the
Jacobian of the hyperelliptic curve. <p>
The code is <a href="weilres.g">here</a>. <p>
There is a <b>special version</b> of KASH to use with this program:
<a href="ftp://ftp.math.tu-berlin.de/pub/algebra/Kant/Kash/kash22.wd.sol2.tgz">
ftp://ftp.math.tu-berlin.de/pub/algebra/Kant/Kash/kash22.wd.sol2.tgz</a>. <p>
This new version of KASH means that one can map places of the various
function fields around much faster.
Alas this only works on Solaris machines at the moment.
Other users will need to use the standard slower version of KASH.<p>
To switch this option on change the sixth line of <b>weilres.g</b>
from
<pre>
KashVersionIsWD := false;
</pre>
to
<pre>
KashVersionIsWD := true;
</pre>
To see how to use this function see the following
excerpt from the code: <br>
<pre>
AlffWeilRestriction := function(arg)
#
# Given an elliptic function field E: y^2 + xy + x^3 + ax^2 + b
# n and and optionally some places of degree one, return the
# hyperelliptic curve in the Weil restriction and the image of
# the given places.
#
# Calling is AlffWeilRestriction(E, n [, p1, p2, p3, ... , reduce] ).
#
# Returns F or [ F, D1, D2, D3, ... ] such that e.g. if (p2-p3) = m*(p1-p3)
# then (D1-D3) = m*(D2-D3). The pi may not be over x=0 or x=infty, which
# makes a translation of the origin necessary.
#
# reduce is true or false. If it is false no reduction is done at the
# end and results (especially point mapping) are obtained faster but also
# "uglier".
#
# Program contains some special assumptions making the trafos easier,
# they may fail. Should be no problem in general.
#
</pre>
Note the code is completely unsupported and may not work on some
installations of KASH.
Hopefully one day we will convert it to work with Magma.
<hr>
<h2>Other Resources</h2>
A number of other people are working on this topic:
<ul>
<li>
<a href="http://www.exp-math.uni-essen.de/zahlentheorie/people/frey.html">
G. Frey</a> set the whole ball rolling with a talk at Waterloo University.
<ol>
<li><a href="http://cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps">
Slides</a> from the talk at Waterloo.
<li>
<a href="http://www.exp-math.uni-essen.de/zahlentheorie/preprints/nna1.ps">
Applications of Arithmetical Geometry to Cryptographic Constructions
</a>
</ol>
<li> S. Galbraith
<li> P. Gaudry
<li> F. Hess
<li> M. Jacobson
<li> A. Menezes
<li> E. Teske
<li> A. Stein
</ul>
<hr>
Nigel Smart<p>
</body>
</html>