chiark / gitweb /
math/pgen.c: Don't free the tester if it's not set up.
[catacomb] / math / ec.c
CommitLineData
b0ab12e6 1/* -*-c-*-
b0ab12e6 2 *
3 * Elliptic curve definitions
4 *
5 * (c) 2001 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
b0ab12e6 9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
45c0fd36 16 *
b0ab12e6 17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
45c0fd36 21 *
b0ab12e6 22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
b0ab12e6 28/*----- Header files ------------------------------------------------------*/
29
30#include "ec.h"
31
32/*----- Trivial wrappers --------------------------------------------------*/
33
34e4f738 34/* --- @ec_samep@ --- *
35 *
36 * Arguments: @ec_curve *c, *d@ = two elliptic curves
37 *
38 * Returns: Nonzero if the curves are identical (not just isomorphic).
39 *
40 * Use: Checks for sameness of curves. This function does the full
41 * check, not just the curve-type-specific check done by the
42 * @sampep@ field operation.
43 */
44
45int ec_samep(ec_curve *c, ec_curve *d)
46{
a02032a3 47 return (c == d || (field_samep(c->f, d->f) &&
48 c->ops == d->ops && EC_SAMEP(c, d)));
34e4f738 49}
50
b0ab12e6 51/* --- @ec_create@ --- *
52 *
53 * Arguments: @ec *p@ = pointer to an elliptic-curve point
54 *
41cb1beb 55 * Returns: The argument @p@.
b0ab12e6 56 *
57 * Use: Initializes a new point. The initial value is the additive
58 * identity (which is universal for all curves).
59 */
60
41cb1beb 61ec *ec_create(ec *p) { EC_CREATE(p); return (p); }
b0ab12e6 62
63/* --- @ec_destroy@ --- *
64 *
65 * Arguments: @ec *p@ = pointer to an elliptic-curve point
66 *
67 * Returns: ---
68 *
69 * Use: Destroys a point, making it invalid.
70 */
71
72void ec_destroy(ec *p) { EC_DESTROY(p); }
73
74/* --- @ec_atinf@ --- *
75 *
76 * Arguments: @const ec *p@ = pointer to a point
77 *
78 * Returns: Nonzero if %$p = O$% is the point at infinity, zero
79 * otherwise.
80 */
81
82int ec_atinf(const ec *p) { return (EC_ATINF(p)); }
83
84/* --- @ec_setinf@ --- *
85 *
86 * Arguments: @ec *p@ = pointer to a point
87 *
41cb1beb 88 * Returns: The argument @p@.
b0ab12e6 89 *
90 * Use: Sets the given point to be the point %$O$% at infinity.
91 */
92
41cb1beb 93ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
b0ab12e6 94
95/* --- @ec_copy@ --- *
96 *
97 * Arguments: @ec *d@ = pointer to destination point
98 * @const ec *p@ = pointer to source point
99 *
41cb1beb 100 * Returns: The destination @d@.
b0ab12e6 101 *
102 * Use: Creates a copy of an elliptic curve point.
103 */
104
41cb1beb 105ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
b0ab12e6 106
bc985cef 107/* --- @ec_eq@ --- *
108 *
109 * Arguments: @const ec *p, *q@ = two points
110 *
111 * Returns: Nonzero if the points are equal. Compares external-format
112 * points.
113 */
114
115int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }
116
41a324a7 117/*----- Standard curve operations -----------------------------------------*/
b0ab12e6 118
34e4f738 119/* --- @ec_stdsamep@ --- *
120 *
121 * Arguments: @ec_curve *c, *d@ = two elliptic curves
122 *
123 * Returns: Nonzero if the curves are identical (not just isomorphic).
124 *
125 * Use: Simple sameness check on @a@ and @b@ curve members.
126 */
127
128int ec_stdsamep(ec_curve *c, ec_curve *d)
a02032a3 129 { return (MP_EQ(c->a, d->a) && MP_EQ(c->b, d->b)); }
34e4f738 130
8823192f 131/* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
b0ab12e6 132 *
133 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
41a324a7 134 * @ec *d@ = pointer to the destination
135 * @const ec *p@ = pointer to a source point
b0ab12e6 136 *
41a324a7 137 * Returns: The destination @d@.
b0ab12e6 138 *
41a324a7 139 * Use: An identity operation if your curve has no internal
140 * representation. (The field internal representation is still
141 * used.)
b0ab12e6 142 */
143
41a324a7 144ec *ec_idin(ec_curve *c, ec *d, const ec *p)
b0ab12e6 145{
146 if (EC_ATINF(p))
147 EC_SETINF(d);
148 else {
149 field *f = c->f;
150 d->x = F_IN(f, d->x, p->x);
151 d->y = F_IN(f, d->y, p->y);
41a324a7 152 mp_drop(d->z); d->z = 0;
153 }
154 return (d);
155}
156
157ec *ec_idout(ec_curve *c, ec *d, const ec *p)
158{
159 if (EC_ATINF(p))
160 EC_SETINF(d);
161 else {
162 field *f = c->f;
163 d->x = F_OUT(f, d->x, p->x);
164 d->y = F_OUT(f, d->y, p->y);
165 mp_drop(d->z); d->z = 0;
b0ab12e6 166 }
41a324a7 167 return (d);
b0ab12e6 168}
169
8823192f 170ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
a02032a3 171 { EC_COPY(d, p); return (d); }
8823192f 172
4edc47b8 173/* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
b0ab12e6 174 *
175 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
41a324a7 176 * @ec *d@ = pointer to the destination
177 * @const ec *p@ = pointer to a source point
b0ab12e6 178 *
41a324a7 179 * Returns: The destination @d@.
b0ab12e6 180 *
41a324a7 181 * Use: Conversion functions if your curve operations use a
182 * projective representation.
b0ab12e6 183 */
184
41a324a7 185ec *ec_projin(ec_curve *c, ec *d, const ec *p)
186{
187 if (EC_ATINF(p))
188 EC_SETINF(d);
189 else {
190 field *f = c->f;
191 d->x = F_IN(f, d->x, p->x);
192 d->y = F_IN(f, d->y, p->y);
193 mp_drop(d->z); d->z = MP_COPY(f->one);
194 }
195 return (d);
196}
197
198ec *ec_projout(ec_curve *c, ec *d, const ec *p)
b0ab12e6 199{
200 if (EC_ATINF(p))
201 EC_SETINF(d);
202 else {
8823192f 203 mp *x, *y, *z, *zz;
b0ab12e6 204 field *f = c->f;
a02032a3 205 if (p->z == f->one) {
206 d->x = F_OUT(f, d->x, p->x);
207 d->y = F_OUT(f, d->y, p->y);
208 } else {
209 z = F_INV(f, MP_NEW, p->z);
210 zz = F_SQR(f, MP_NEW, z);
211 z = F_MUL(f, z, zz, z);
212 x = F_MUL(f, d->x, p->x, zz);
213 y = F_MUL(f, d->y, p->y, z);
214 mp_drop(z);
215 mp_drop(zz);
216 d->x = F_OUT(f, x, x);
217 d->y = F_OUT(f, y, y);
218 }
b0ab12e6 219 mp_drop(d->z);
b0ab12e6 220 d->z = 0;
221 }
41a324a7 222 return (d);
b0ab12e6 223}
224
8823192f 225ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
226{
227 if (EC_ATINF(p))
228 EC_SETINF(d);
a02032a3 229 else if (p->z == c->f->one)
8823192f 230 EC_COPY(d, p);
231 else {
232 mp *z, *zz;
233 field *f = c->f;
234 z = F_INV(f, MP_NEW, p->z);
235 zz = F_SQR(f, MP_NEW, z);
236 z = F_MUL(f, z, zz, z);
237 d->x = F_MUL(f, d->x, p->x, zz);
238 d->y = F_MUL(f, d->y, p->y, z);
239 mp_drop(z);
240 mp_drop(zz);
241 mp_drop(d->z);
242 d->z = MP_COPY(f->one);
243 }
4edc47b8 244 return (d);
8823192f 245}
246
b085fd91 247/* --- @ec_stdsub@ --- *
248 *
249 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
250 * @ec *d@ = pointer to the destination
41cb1beb 251 * @const ec *p, *q@ = the operand points
b085fd91 252 *
253 * Returns: The destination @d@.
254 *
255 * Use: Standard point subtraction operation, in terms of negation
256 * and addition. This isn't as efficient as a ready-made
257 * subtraction operator.
258 */
259
41cb1beb 260ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
b085fd91 261{
262 ec t = EC_INIT;
41cb1beb 263 EC_NEG(c, &t, q);
264 EC_ADD(c, d, p, &t);
b085fd91 265 EC_DESTROY(&t);
266 return (d);
267}
268
41cb1beb 269/*----- Creating curves ---------------------------------------------------*/
270
271/* --- @ec_destroycurve@ --- *
272 *
273 * Arguments: @ec_curve *c@ = pointer to an ellptic curve
274 *
275 * Returns: ---
276 *
277 * Use: Destroys a description of an elliptic curve.
278 */
279
280void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
281
41a324a7 282/*----- Real arithmetic ---------------------------------------------------*/
283
b0ab12e6 284/* --- @ec_find@ --- *
285 *
286 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
287 * @ec *d@ = pointer to the destination point
288 * @mp *x@ = a possible x-coordinate
289 *
290 * Returns: Zero if OK, nonzero if there isn't a point there.
291 *
292 * Use: Finds a point on an elliptic curve with a given x-coordinate.
293 */
294
41a324a7 295ec *ec_find(ec_curve *c, ec *d, mp *x)
b0ab12e6 296{
b0ab12e6 297 x = F_IN(c->f, MP_NEW, x);
41a324a7 298 if ((d = EC_FIND(c, d, x)) != 0)
299 EC_OUT(c, d, d);
8823192f 300 MP_DROP(x);
41a324a7 301 return (d);
b0ab12e6 302}
303
dbfee00a 304/* --- @ec_neg@ --- *
305 *
306 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
307 * @ec *d@ = pointer to the destination point
308 * @const ec *p@ = pointer to the operand point
309 *
310 * Returns: The destination point.
311 *
312 * Use: Computes the negation of the given point.
313 */
314
315ec *ec_neg(ec_curve *c, ec *d, const ec *p)
a02032a3 316 { EC_IN(c, d, p); EC_NEG(c, d, d); return (EC_OUT(c, d, d)); }
dbfee00a 317
b0ab12e6 318/* --- @ec_add@ --- *
319 *
320 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
321 * @ec *d@ = pointer to the destination point
322 * @const ec *p, *q@ = pointers to the operand points
323 *
324 * Returns: ---
325 *
326 * Use: Adds two points on an elliptic curve.
327 */
328
41a324a7 329ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
b0ab12e6 330{
331 ec pp = EC_INIT, qq = EC_INIT;
41a324a7 332 EC_IN(c, &pp, p);
333 EC_IN(c, &qq, q);
b0ab12e6 334 EC_ADD(c, d, &pp, &qq);
41a324a7 335 EC_OUT(c, d, d);
b0ab12e6 336 EC_DESTROY(&pp);
337 EC_DESTROY(&qq);
41a324a7 338 return (d);
b0ab12e6 339}
340
dbfee00a 341/* --- @ec_sub@ --- *
342 *
343 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
344 * @ec *d@ = pointer to the destination point
345 * @const ec *p, *q@ = pointers to the operand points
346 *
347 * Returns: The destination @d@.
348 *
349 * Use: Subtracts one point from another on an elliptic curve.
350 */
351
352ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
353{
432c4e18 354 ec pp = EC_INIT, qq = EC_INIT;
dbfee00a 355 EC_IN(c, &pp, p);
356 EC_IN(c, &qq, q);
bc985cef 357 EC_SUB(c, d, &pp, &qq);
dbfee00a 358 EC_OUT(c, d, d);
359 EC_DESTROY(&pp);
360 EC_DESTROY(&qq);
361 return (d);
362}
363
b0ab12e6 364/* --- @ec_dbl@ --- *
365 *
366 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
367 * @ec *d@ = pointer to the destination point
368 * @const ec *p@ = pointer to the operand point
369 *
370 * Returns: ---
371 *
372 * Use: Doubles a point on an elliptic curve.
373 */
374
41a324a7 375ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
a02032a3 376 { EC_IN(c, d, p); EC_DBL(c, d, d); return (EC_OUT(c, d, d)); }
b0ab12e6 377
8823192f 378/* --- @ec_check@ --- *
379 *
380 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
381 * @const ec *p@ = pointer to the point
382 *
383 * Returns: Zero if OK, nonzero if this is an invalid point.
384 *
385 * Use: Checks that a point is actually on an elliptic curve.
386 */
387
388int ec_check(ec_curve *c, const ec *p)
389{
390 ec t = EC_INIT;
391 int rc;
392
393 if (EC_ATINF(p))
394 return (0);
395 EC_IN(c, &t, p);
396 rc = EC_CHECK(c, &t);
397 EC_DESTROY(&t);
398 return (rc);
399}
400
bc985cef 401/* --- @ec_rand@ --- *
402 *
403 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
404 * @ec *d@ = pointer to the destination point
405 * @grand *r@ = random number source
406 *
407 * Returns: The destination @d@.
408 *
409 * Use: Finds a random point on the given curve.
410 */
411
412ec *ec_rand(ec_curve *c, ec *d, grand *r)
413{
414 mp *x = MP_NEW;
415 do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
416 mp_drop(x);
417 if (grand_range(r, 2)) EC_NEG(c, d, d);
45c0fd36 418 return (EC_OUT(c, d, d));
bc985cef 419}
420
b0ab12e6 421/*----- That's all, folks -------------------------------------------------*/