projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Projective coordinates for prime curves
[u/mdw/catacomb] / ec.c
1 /* -*-c-*-
2 *
3 * $Id: ec.c,v 1.4.4.2 2004/03/20 00:13:31 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.4.4.2 2004/03/20 00:13:31 mdw
34 * Projective coordinates for prime curves
35 *
36 * Revision 1.4.4.1 2003/06/10 13:43:53 mdw
37 * Simple (non-projective) curves over prime fields now seem to work.
38 *
39 * Revision 1.4 2003/05/15 23:25:59 mdw
40 * Make elliptic curve stuff build.
41 *
42 * Revision 1.3 2002/01/13 13:48:44 mdw
43 * Further progress.
44 *
45 * Revision 1.2 2001/05/07 17:29:44 mdw
46 * Treat projective coordinates as an internal representation. Various
47 * minor interface changes.
48 *
49 * Revision 1.1 2001/04/29 18:12:33 mdw
50 * Prototype version.
51 *
52 */
53
54 /*----- Header files ------------------------------------------------------*/
55
56 #include "ec.h"
57 #include "ec-exp.h"
58
59 /*----- Trivial wrappers --------------------------------------------------*/
60
61 /* --- @ec_create@ --- *
62 *
63 * Arguments: @ec *p@ = pointer to an elliptic-curve point
64 *
65 * Returns: The argument @p@.
66 *
67 * Use: Initializes a new point. The initial value is the additive
68 * identity (which is universal for all curves).
69 */
70
71 ec *ec_create(ec *p) { EC_CREATE(p); return (p); }
72
73 /* --- @ec_destroy@ --- *
74 *
75 * Arguments: @ec *p@ = pointer to an elliptic-curve point
76 *
77 * Returns: ---
78 *
79 * Use: Destroys a point, making it invalid.
80 */
81
82 void ec_destroy(ec *p) { EC_DESTROY(p); }
83
84 /* --- @ec_atinf@ --- *
85 *
86 * Arguments: @const ec *p@ = pointer to a point
87 *
88 * Returns: Nonzero if %$p = O$% is the point at infinity, zero
89 * otherwise.
90 */
91
92 int ec_atinf(const ec *p) { return (EC_ATINF(p)); }
93
94 /* --- @ec_setinf@ --- *
95 *
96 * Arguments: @ec *p@ = pointer to a point
97 *
98 * Returns: The argument @p@.
99 *
100 * Use: Sets the given point to be the point %$O$% at infinity.
101 */
102
103 ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
104
105 /* --- @ec_copy@ --- *
106 *
107 * Arguments: @ec *d@ = pointer to destination point
108 * @const ec *p@ = pointer to source point
109 *
110 * Returns: The destination @d@.
111 *
112 * Use: Creates a copy of an elliptic curve point.
113 */
114
115 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
116
117 /*----- Standard curve operations -----------------------------------------*/
118
119 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
120 *
121 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
122 * @ec *d@ = pointer to the destination
123 * @const ec *p@ = pointer to a source point
124 *
125 * Returns: The destination @d@.
126 *
127 * Use: An identity operation if your curve has no internal
128 * representation. (The field internal representation is still
129 * used.)
130 */
131
132 ec *ec_idin(ec_curve *c, ec *d, const ec *p)
133 {
134 if (EC_ATINF(p))
135 EC_SETINF(d);
136 else {
137 field *f = c->f;
138 d->x = F_IN(f, d->x, p->x);
139 d->y = F_IN(f, d->y, p->y);
140 mp_drop(d->z); d->z = 0;
141 }
142 return (d);
143 }
144
145 ec *ec_idout(ec_curve *c, ec *d, const ec *p)
146 {
147 if (EC_ATINF(p))
148 EC_SETINF(d);
149 else {
150 field *f = c->f;
151 d->x = F_OUT(f, d->x, p->x);
152 d->y = F_OUT(f, d->y, p->y);
153 mp_drop(d->z); d->z = 0;
154 }
155 return (d);
156 }
157
158 ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
159 {
160 EC_COPY(d, p);
161 return (d);
162 }
163
164 /* --- @ec_projin@, @ec_projout@ --- *
165 *
166 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
167 * @ec *d@ = pointer to the destination
168 * @const ec *p@ = pointer to a source point
169 *
170 * Returns: The destination @d@.
171 *
172 * Use: Conversion functions if your curve operations use a
173 * projective representation.
174 */
175
176 ec *ec_projin(ec_curve *c, ec *d, const ec *p)
177 {
178 if (EC_ATINF(p))
179 EC_SETINF(d);
180 else {
181 field *f = c->f;
182 d->x = F_IN(f, d->x, p->x);
183 d->y = F_IN(f, d->y, p->y);
184 mp_drop(d->z); d->z = MP_COPY(f->one);
185 }
186 return (d);
187 }
188
189 ec *ec_projout(ec_curve *c, ec *d, const ec *p)
190 {
191 if (EC_ATINF(p))
192 EC_SETINF(d);
193 else {
194 mp *x, *y, *z, *zz;
195 field *f = c->f;
196 z = F_INV(f, MP_NEW, p->z);
197 zz = F_SQR(f, MP_NEW, z);
198 z = F_MUL(f, z, zz, z);
199 x = F_MUL(f, d->x, p->x, zz);
200 y = F_MUL(f, d->y, p->y, z);
201 mp_drop(z);
202 mp_drop(zz);
203 mp_drop(d->z);
204 d->x = F_OUT(f, x, x);
205 d->y = F_OUT(f, y, y);
206 d->z = 0;
207 }
208 return (d);
209 }
210
211 ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
212 {
213 if (EC_ATINF(p))
214 EC_SETINF(d);
215 else if (d->z == c->f->one)
216 EC_COPY(d, p);
217 else {
218 mp *z, *zz;
219 field *f = c->f;
220 z = F_INV(f, MP_NEW, p->z);
221 zz = F_SQR(f, MP_NEW, z);
222 z = F_MUL(f, z, zz, z);
223 d->x = F_MUL(f, d->x, p->x, zz);
224 d->y = F_MUL(f, d->y, p->y, z);
225 mp_drop(z);
226 mp_drop(zz);
227 mp_drop(d->z);
228 d->z = MP_COPY(f->one);
229 }
230 return (d);
231 }
232
233 /* --- @ec_stdsub@ --- *
234 *
235 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
236 * @ec *d@ = pointer to the destination
237 * @const ec *p, *q@ = the operand points
238 *
239 * Returns: The destination @d@.
240 *
241 * Use: Standard point subtraction operation, in terms of negation
242 * and addition. This isn't as efficient as a ready-made
243 * subtraction operator.
244 */
245
246 ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
247 {
248 ec t = EC_INIT;
249 EC_NEG(c, &t, q);
250 EC_FIX(c, &t, &t);
251 EC_ADD(c, d, p, &t);
252 EC_DESTROY(&t);
253 return (d);
254 }
255
256 /*----- Creating curves ---------------------------------------------------*/
257
258 /* --- @ec_destroycurve@ --- *
259 *
260 * Arguments: @ec_curve *c@ = pointer to an ellptic curve
261 *
262 * Returns: ---
263 *
264 * Use: Destroys a description of an elliptic curve.
265 */
266
267 void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
268
269 /*----- Real arithmetic ---------------------------------------------------*/
270
271 /* --- @ec_find@ --- *
272 *
273 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
274 * @ec *d@ = pointer to the destination point
275 * @mp *x@ = a possible x-coordinate
276 *
277 * Returns: Zero if OK, nonzero if there isn't a point there.
278 *
279 * Use: Finds a point on an elliptic curve with a given x-coordinate.
280 */
281
282 ec *ec_find(ec_curve *c, ec *d, mp *x)
283 {
284 x = F_IN(c->f, MP_NEW, x);
285 if ((d = EC_FIND(c, d, x)) != 0)
286 EC_OUT(c, d, d);
287 MP_DROP(x);
288 return (d);
289 }
290
291 /* --- @ec_neg@ --- *
292 *
293 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
294 * @ec *d@ = pointer to the destination point
295 * @const ec *p@ = pointer to the operand point
296 *
297 * Returns: The destination point.
298 *
299 * Use: Computes the negation of the given point.
300 */
301
302 ec *ec_neg(ec_curve *c, ec *d, const ec *p)
303 {
304 EC_IN(c, d, p);
305 EC_NEG(c, d, d);
306 return (EC_OUT(c, d, d));
307 }
308
309 /* --- @ec_add@ --- *
310 *
311 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
312 * @ec *d@ = pointer to the destination point
313 * @const ec *p, *q@ = pointers to the operand points
314 *
315 * Returns: ---
316 *
317 * Use: Adds two points on an elliptic curve.
318 */
319
320 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
321 {
322 ec pp = EC_INIT, qq = EC_INIT;
323 EC_IN(c, &pp, p);
324 EC_IN(c, &qq, q);
325 EC_ADD(c, d, &pp, &qq);
326 EC_OUT(c, d, d);
327 EC_DESTROY(&pp);
328 EC_DESTROY(&qq);
329 return (d);
330 }
331
332 /* --- @ec_sub@ --- *
333 *
334 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
335 * @ec *d@ = pointer to the destination point
336 * @const ec *p, *q@ = pointers to the operand points
337 *
338 * Returns: The destination @d@.
339 *
340 * Use: Subtracts one point from another on an elliptic curve.
341 */
342
343 ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
344 {
345 ec pp, qq;
346 EC_IN(c, &pp, p);
347 EC_IN(c, &qq, q);
348 EC_SUB(c, d, &qq, &qq);
349 EC_OUT(c, d, d);
350 EC_DESTROY(&pp);
351 EC_DESTROY(&qq);
352 return (d);
353 }
354
355 /* --- @ec_dbl@ --- *
356 *
357 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
358 * @ec *d@ = pointer to the destination point
359 * @const ec *p@ = pointer to the operand point
360 *
361 * Returns: ---
362 *
363 * Use: Doubles a point on an elliptic curve.
364 */
365
366 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
367 {
368 EC_IN(c, d, p);
369 EC_DBL(c, d, d);
370 return (EC_OUT(c, d, d));
371 }
372
373 /* --- @ec_check@ --- *
374 *
375 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
376 * @const ec *p@ = pointer to the point
377 *
378 * Returns: Zero if OK, nonzero if this is an invalid point.
379 *
380 * Use: Checks that a point is actually on an elliptic curve.
381 */
382
383 int ec_check(ec_curve *c, const ec *p)
384 {
385 ec t = EC_INIT;
386 int rc;
387
388 if (EC_ATINF(p))
389 return (0);
390 EC_IN(c, &t, p);
391 rc = EC_CHECK(c, &t);
392 EC_DESTROY(&t);
393 return (rc);
394 }
395
396 /* --- @ec_imul@, @ec_mul@ --- *
397 *
398 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
399 * @ec *d@ = pointer to the destination point
400 * @const ec *p@ = pointer to the generator point
401 * @mp *n@ = integer multiplier
402 *
403 * Returns: The destination @d@.
404 *
405 * Use: Multiplies a point by a scalar, returning %$n p$%. The
406 * @imul@ variant uses internal representations for argument
407 * and result.
408 */
409
410 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
411 {
412 ec t = EC_INIT;
413
414 EC_COPY(&t, p);
415 if (t.x && (n->f & MP_BURN))
416 t.x->f |= MP_BURN;
417 MP_SHRINK(n);
418 EC_SETINF(d);
419 if (MP_LEN(n) == 0)
420 ;
421 else {
422 if (n->f & MP_NEG)
423 EC_NEG(c, &t, &t);
424 if (MP_LEN(n) < EXP_THRESH)
425 EXP_SIMPLE(*d, t, n);
426 else
427 EXP_WINDOW(*d, t, n);
428 }
429 EC_DESTROY(&t);
430 return (d);
431 }
432
433 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
434 {
435 EC_IN(c, d, p);
436 ec_imul(c, d, d, n);
437 return (EC_OUT(c, d, d));
438 }
439
440 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)