projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Normal basis support (translates to poly basis internally). Rewrite
[u/mdw/catacomb] / ec.c
1 /* -*-c-*-
2 *
3 * $Id: ec.c,v 1.9 2004/04/01 21:28:41 mdw Exp $
4 *
5 * Elliptic curve definitions
6 *
7 * (c) 2001 Straylight/Edgeware
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of Catacomb.
13 *
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
28 */
29
30 /*----- Revision history --------------------------------------------------*
31 *
32 * $Log: ec.c,v $
33 * Revision 1.9 2004/04/01 21:28:41 mdw
34 * Normal basis support (translates to poly basis internally). Rewrite
35 * EC and prime group table generators in awk, so that they can reuse data
36 * for repeated constants.
37 *
38 * Revision 1.8 2004/04/01 12:50:09 mdw
39 * Add cyclic group abstraction, with test code. Separate off exponentation
40 * functions for better static linking. Fix a buttload of bugs on the way.
41 * Generally ensure that negative exponents do inversion correctly. Add
42 * table of standard prime-field subgroups. (Binary field subgroups are
43 * currently unimplemented but easy to add if anyone ever finds a good one.)
44 *
45 * Revision 1.7 2004/03/27 17:54:11 mdw
46 * Standard curves and curve checking.
47 *
48 * Revision 1.6 2004/03/23 15:19:32 mdw
49 * Test elliptic curves more thoroughly.
50 *
51 * Revision 1.5 2004/03/21 22:52:06 mdw
52 * Merge and close elliptic curve branch.
53 *
54 * Revision 1.4.4.2 2004/03/20 00:13:31 mdw
55 * Projective coordinates for prime curves
56 *
57 * Revision 1.4.4.1 2003/06/10 13:43:53 mdw
58 * Simple (non-projective) curves over prime fields now seem to work.
59 *
60 * Revision 1.4 2003/05/15 23:25:59 mdw
61 * Make elliptic curve stuff build.
62 *
63 * Revision 1.3 2002/01/13 13:48:44 mdw
64 * Further progress.
65 *
66 * Revision 1.2 2001/05/07 17:29:44 mdw
67 * Treat projective coordinates as an internal representation. Various
68 * minor interface changes.
69 *
70 * Revision 1.1 2001/04/29 18:12:33 mdw
71 * Prototype version.
72 *
73 */
74
75 /*----- Header files ------------------------------------------------------*/
76
77 #include "ec.h"
78
79 /*----- Trivial wrappers --------------------------------------------------*/
80
81 /* --- @ec_samep@ --- *
82 *
83 * Arguments: @ec_curve *c, *d@ = two elliptic curves
84 *
85 * Returns: Nonzero if the curves are identical (not just isomorphic).
86 *
87 * Use: Checks for sameness of curves. This function does the full
88 * check, not just the curve-type-specific check done by the
89 * @sampep@ field operation.
90 */
91
92 int ec_samep(ec_curve *c, ec_curve *d)
93 {
94 return (field_samep(c->f, d->f) && c->ops == d->ops && EC_SAMEP(c, d));
95 }
96
97 /* --- @ec_create@ --- *
98 *
99 * Arguments: @ec *p@ = pointer to an elliptic-curve point
100 *
101 * Returns: The argument @p@.
102 *
103 * Use: Initializes a new point. The initial value is the additive
104 * identity (which is universal for all curves).
105 */
106
107 ec *ec_create(ec *p) { EC_CREATE(p); return (p); }
108
109 /* --- @ec_destroy@ --- *
110 *
111 * Arguments: @ec *p@ = pointer to an elliptic-curve point
112 *
113 * Returns: ---
114 *
115 * Use: Destroys a point, making it invalid.
116 */
117
118 void ec_destroy(ec *p) { EC_DESTROY(p); }
119
120 /* --- @ec_atinf@ --- *
121 *
122 * Arguments: @const ec *p@ = pointer to a point
123 *
124 * Returns: Nonzero if %$p = O$% is the point at infinity, zero
125 * otherwise.
126 */
127
128 int ec_atinf(const ec *p) { return (EC_ATINF(p)); }
129
130 /* --- @ec_setinf@ --- *
131 *
132 * Arguments: @ec *p@ = pointer to a point
133 *
134 * Returns: The argument @p@.
135 *
136 * Use: Sets the given point to be the point %$O$% at infinity.
137 */
138
139 ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
140
141 /* --- @ec_copy@ --- *
142 *
143 * Arguments: @ec *d@ = pointer to destination point
144 * @const ec *p@ = pointer to source point
145 *
146 * Returns: The destination @d@.
147 *
148 * Use: Creates a copy of an elliptic curve point.
149 */
150
151 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
152
153 /* --- @ec_eq@ --- *
154 *
155 * Arguments: @const ec *p, *q@ = two points
156 *
157 * Returns: Nonzero if the points are equal. Compares external-format
158 * points.
159 */
160
161 int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }
162
163 /*----- Standard curve operations -----------------------------------------*/
164
165 /* --- @ec_stdsamep@ --- *
166 *
167 * Arguments: @ec_curve *c, *d@ = two elliptic curves
168 *
169 * Returns: Nonzero if the curves are identical (not just isomorphic).
170 *
171 * Use: Simple sameness check on @a@ and @b@ curve members.
172 */
173
174 int ec_stdsamep(ec_curve *c, ec_curve *d)
175 {
176 return (MP_EQ(c->a, d->a) && MP_EQ(c->b, d->b));
177 }
178
179 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
180 *
181 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
182 * @ec *d@ = pointer to the destination
183 * @const ec *p@ = pointer to a source point
184 *
185 * Returns: The destination @d@.
186 *
187 * Use: An identity operation if your curve has no internal
188 * representation. (The field internal representation is still
189 * used.)
190 */
191
192 ec *ec_idin(ec_curve *c, ec *d, const ec *p)
193 {
194 if (EC_ATINF(p))
195 EC_SETINF(d);
196 else {
197 field *f = c->f;
198 d->x = F_IN(f, d->x, p->x);
199 d->y = F_IN(f, d->y, p->y);
200 mp_drop(d->z); d->z = 0;
201 }
202 return (d);
203 }
204
205 ec *ec_idout(ec_curve *c, ec *d, const ec *p)
206 {
207 if (EC_ATINF(p))
208 EC_SETINF(d);
209 else {
210 field *f = c->f;
211 d->x = F_OUT(f, d->x, p->x);
212 d->y = F_OUT(f, d->y, p->y);
213 mp_drop(d->z); d->z = 0;
214 }
215 return (d);
216 }
217
218 ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
219 {
220 EC_COPY(d, p);
221 return (d);
222 }
223
224 /* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
225 *
226 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
227 * @ec *d@ = pointer to the destination
228 * @const ec *p@ = pointer to a source point
229 *
230 * Returns: The destination @d@.
231 *
232 * Use: Conversion functions if your curve operations use a
233 * projective representation.
234 */
235
236 ec *ec_projin(ec_curve *c, ec *d, const ec *p)
237 {
238 if (EC_ATINF(p))
239 EC_SETINF(d);
240 else {
241 field *f = c->f;
242 d->x = F_IN(f, d->x, p->x);
243 d->y = F_IN(f, d->y, p->y);
244 mp_drop(d->z); d->z = MP_COPY(f->one);
245 }
246 return (d);
247 }
248
249 ec *ec_projout(ec_curve *c, ec *d, const ec *p)
250 {
251 if (EC_ATINF(p))
252 EC_SETINF(d);
253 else {
254 mp *x, *y, *z, *zz;
255 field *f = c->f;
256 z = F_INV(f, MP_NEW, p->z);
257 zz = F_SQR(f, MP_NEW, z);
258 z = F_MUL(f, z, zz, z);
259 x = F_MUL(f, d->x, p->x, zz);
260 y = F_MUL(f, d->y, p->y, z);
261 mp_drop(z);
262 mp_drop(zz);
263 mp_drop(d->z);
264 d->x = F_OUT(f, x, x);
265 d->y = F_OUT(f, y, y);
266 d->z = 0;
267 }
268 return (d);
269 }
270
271 ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
272 {
273 if (EC_ATINF(p))
274 EC_SETINF(d);
275 else if (d->z == c->f->one)
276 EC_COPY(d, p);
277 else {
278 mp *z, *zz;
279 field *f = c->f;
280 z = F_INV(f, MP_NEW, p->z);
281 zz = F_SQR(f, MP_NEW, z);
282 z = F_MUL(f, z, zz, z);
283 d->x = F_MUL(f, d->x, p->x, zz);
284 d->y = F_MUL(f, d->y, p->y, z);
285 mp_drop(z);
286 mp_drop(zz);
287 mp_drop(d->z);
288 d->z = MP_COPY(f->one);
289 }
290 return (d);
291 }
292
293 /* --- @ec_stdsub@ --- *
294 *
295 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
296 * @ec *d@ = pointer to the destination
297 * @const ec *p, *q@ = the operand points
298 *
299 * Returns: The destination @d@.
300 *
301 * Use: Standard point subtraction operation, in terms of negation
302 * and addition. This isn't as efficient as a ready-made
303 * subtraction operator.
304 */
305
306 ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
307 {
308 ec t = EC_INIT;
309 EC_NEG(c, &t, q);
310 EC_FIX(c, &t, &t);
311 EC_ADD(c, d, p, &t);
312 EC_DESTROY(&t);
313 return (d);
314 }
315
316 /*----- Creating curves ---------------------------------------------------*/
317
318 /* --- @ec_destroycurve@ --- *
319 *
320 * Arguments: @ec_curve *c@ = pointer to an ellptic curve
321 *
322 * Returns: ---
323 *
324 * Use: Destroys a description of an elliptic curve.
325 */
326
327 void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
328
329 /*----- Real arithmetic ---------------------------------------------------*/
330
331 /* --- @ec_find@ --- *
332 *
333 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
334 * @ec *d@ = pointer to the destination point
335 * @mp *x@ = a possible x-coordinate
336 *
337 * Returns: Zero if OK, nonzero if there isn't a point there.
338 *
339 * Use: Finds a point on an elliptic curve with a given x-coordinate.
340 */
341
342 ec *ec_find(ec_curve *c, ec *d, mp *x)
343 {
344 x = F_IN(c->f, MP_NEW, x);
345 if ((d = EC_FIND(c, d, x)) != 0)
346 EC_OUT(c, d, d);
347 MP_DROP(x);
348 return (d);
349 }
350
351 /* --- @ec_neg@ --- *
352 *
353 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
354 * @ec *d@ = pointer to the destination point
355 * @const ec *p@ = pointer to the operand point
356 *
357 * Returns: The destination point.
358 *
359 * Use: Computes the negation of the given point.
360 */
361
362 ec *ec_neg(ec_curve *c, ec *d, const ec *p)
363 {
364 EC_IN(c, d, p);
365 EC_NEG(c, d, d);
366 return (EC_OUT(c, d, d));
367 }
368
369 /* --- @ec_add@ --- *
370 *
371 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
372 * @ec *d@ = pointer to the destination point
373 * @const ec *p, *q@ = pointers to the operand points
374 *
375 * Returns: ---
376 *
377 * Use: Adds two points on an elliptic curve.
378 */
379
380 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
381 {
382 ec pp = EC_INIT, qq = EC_INIT;
383 EC_IN(c, &pp, p);
384 EC_IN(c, &qq, q);
385 EC_ADD(c, d, &pp, &qq);
386 EC_OUT(c, d, d);
387 EC_DESTROY(&pp);
388 EC_DESTROY(&qq);
389 return (d);
390 }
391
392 /* --- @ec_sub@ --- *
393 *
394 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
395 * @ec *d@ = pointer to the destination point
396 * @const ec *p, *q@ = pointers to the operand points
397 *
398 * Returns: The destination @d@.
399 *
400 * Use: Subtracts one point from another on an elliptic curve.
401 */
402
403 ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
404 {
405 ec pp = EC_INIT, qq = EC_INIT;
406 EC_IN(c, &pp, p);
407 EC_IN(c, &qq, q);
408 EC_SUB(c, d, &pp, &qq);
409 EC_OUT(c, d, d);
410 EC_DESTROY(&pp);
411 EC_DESTROY(&qq);
412 return (d);
413 }
414
415 /* --- @ec_dbl@ --- *
416 *
417 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
418 * @ec *d@ = pointer to the destination point
419 * @const ec *p@ = pointer to the operand point
420 *
421 * Returns: ---
422 *
423 * Use: Doubles a point on an elliptic curve.
424 */
425
426 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
427 {
428 EC_IN(c, d, p);
429 EC_DBL(c, d, d);
430 return (EC_OUT(c, d, d));
431 }
432
433 /* --- @ec_check@ --- *
434 *
435 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
436 * @const ec *p@ = pointer to the point
437 *
438 * Returns: Zero if OK, nonzero if this is an invalid point.
439 *
440 * Use: Checks that a point is actually on an elliptic curve.
441 */
442
443 int ec_check(ec_curve *c, const ec *p)
444 {
445 ec t = EC_INIT;
446 int rc;
447
448 if (EC_ATINF(p))
449 return (0);
450 EC_IN(c, &t, p);
451 rc = EC_CHECK(c, &t);
452 EC_DESTROY(&t);
453 return (rc);
454 }
455
456 /* --- @ec_rand@ --- *
457 *
458 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
459 * @ec *d@ = pointer to the destination point
460 * @grand *r@ = random number source
461 *
462 * Returns: The destination @d@.
463 *
464 * Use: Finds a random point on the given curve.
465 */
466
467 ec *ec_rand(ec_curve *c, ec *d, grand *r)
468 {
469 mp *x = MP_NEW;
470 do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
471 mp_drop(x);
472 if (grand_range(r, 2)) EC_NEG(c, d, d);
473 return (EC_OUT(c, d, d));
474 }
475
476 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)