3 * $Id: ec.h,v 1.4.4.3 2004/03/21 22:39:46 mdw Exp $
5 * Elliptic curve definitions
7 * (c) 2001 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.4.4.3 2004/03/21 22:39:46 mdw
34 * Elliptic curves on binary fields work.
36 * Revision 1.4.4.2 2004/03/20 00:13:31 mdw
37 * Projective coordinates for prime curves
39 * Revision 1.4.4.1 2003/06/10 13:43:53 mdw
40 * Simple (non-projective) curves over prime fields now seem to work.
42 * Revision 1.4 2003/05/15 23:25:59 mdw
43 * Make elliptic curve stuff build.
45 * Revision 1.3 2002/01/13 13:48:44 mdw
48 * Revision 1.2 2001/05/07 17:29:44 mdw
49 * Treat projective coordinates as an internal representation. Various
50 * minor interface changes.
52 * Revision 1.1 2001/04/29 18:12:33 mdw
64 /*----- Header files ------------------------------------------------------*/
69 /*----- Data structures ---------------------------------------------------*/
71 /* --- An elliptic curve representation --- */
73 typedef struct ec_curve
{
74 const struct ec_ops
*ops
; /* Curve operations */
75 field
*f
; /* Underlying field structure */
78 /* --- An elliptic curve point --- */
81 mp
*x
, *y
; /* Point coordinates */
82 mp
*z
; /* Common denominator (or null) */
85 /* --- A factor for simultaneous multiplication --- */
87 typedef struct ec_mulfactor
{
88 ec base
; /* The point */
89 mp
*exp
; /* The exponent */
92 /* --- Elliptic curve operations --- *
94 * All operations (apart from @destroy@ and @in@) are guaranteed to be
95 * performed on internal representations of points. Moreover, the second
96 * argument to @add@ and @mul@ is guaranteed to be the output of @in@ or
100 typedef struct ec_ops
{
101 void (*destroy
)(ec_curve */
*c*/
);
102 ec
*(*in
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
103 ec
*(*out
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
104 ec
*(*fix
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
105 ec
*(*find
)(ec_curve */
*c*/
, ec */
*d*/
, mp */
*x*/
);
106 ec
*(*neg
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
107 ec
*(*add
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, const ec */
*q*/
);
108 ec
*(*sub
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, const ec */
*q*/
);
109 ec
*(*dbl
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
110 int (*check
)(ec_curve */
*c*/
, const ec */
*p*/
);
113 #define EC_IN(c, d, p) (c)->ops->in((c), (d), (p))
114 #define EC_OUT(c, d, p) (c)->ops->out((c), (d), (p))
115 #define EC_FIX(c, d, p) (c)->ops->fix((c), (d), (p))
117 #define EC_FIND(c, d, x) (c)->ops->find((c), (d), (x))
118 #define EC_NEG(c, d, x) (c)->ops->neg((c), (d), (x))
119 #define EC_ADD(c, d, p, q) (c)->ops->add((c), (d), (p), (q))
120 #define EC_SUB(c, d, p, q) (c)->ops->sub((c), (d), (p), (q))
121 #define EC_DBL(c, d, p) (c)->ops->dbl((c), (d), (p))
122 #define EC_CHECK(c, p) (c)->ops->check((c), (p))
124 /*----- Simple memory management things -----------------------------------*/
126 /* --- @ec_create@ --- *
128 * Arguments: @ec *p@ = pointer to an elliptic-curve point
130 * Returns: The argument @p@.
132 * Use: Initializes a new point. The initial value is the additive
133 * identity (which is universal for all curves).
136 #define EC_INIT { MP_NEW, MP_NEW, MP_NEW }
138 #define EC_CREATE(p) do { \
140 _p->x = _p->y = _p->z = MP_NEW; \
143 extern ec
*ec_create(ec */
*p*/
);
145 /* --- @ec_destroy@ --- *
147 * Arguments: @ec *p@ = pointer to an elliptic-curve point
151 * Use: Destroys a point, making it invalid.
154 #define EC_DESTROY(p) do { \
156 if (!EC_ATINF(_p)) { \
159 if (_p->z) MP_DROP(_p->z); \
163 extern void ec_destroy(ec */
*p*/
);
165 /* --- @ec_atinf@ --- *
167 * Arguments: @const ec *p@ = pointer to a point
169 * Returns: Nonzero if %$p = O$% is the point at infinity, zero
173 #define EC_ATINF(p) ((p)->x == MP_NEW || (p)->x == MP_NEWSEC)
175 extern int ec_atinf(const ec */
*p*/
);
177 /* --- @ec_setinf@ --- *
179 * Arguments: @ec *p@ = pointer to a point
181 * Returns: The argument @p@.
183 * Use: Sets the given point to be the point %$O$% at infinity.
186 #define EC_SETINF(p) do { \
188 if (!EC_ATINF(_p)) { \
191 if (_p->z) MP_DROP(_p->z); \
192 _p->x = _p->y = _p->z = MP_NEW; \
198 extern ec
*ec_setinf(ec */
*p*/
);
200 /* --- @ec_copy@ --- *
202 * Arguments: @ec *d@ = pointer to destination point
203 * @const ec *p@ = pointer to source point
205 * Returns: The destination @d@.
207 * Use: Creates a copy of an elliptic curve point.
210 #define EC_COPY(d, p) do { \
212 const ec *_p = (p); \
216 _d->x = _d->y = _d->z = MP_NEW; \
218 _d->x = MP_COPY(_p->x); \
219 _d->y = MP_COPY(_p->y); \
220 _d->z = _p->z ? MP_COPY(_p->z) : MP_NEW; \
225 extern ec
*ec_copy(ec */
*d*/
, const ec */
*p*/
);
227 /*----- Interesting arithmetic --------------------------------------------*/
229 /* --- @ec_find@ --- *
231 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
232 * @ec *d@ = pointer to the destination point
233 * @mp *x@ = a possible x-coordinate
235 * Returns: The destination if OK, or null if no point was found.
237 * Use: Finds a point on an elliptic curve with a given
238 * x-coordinate. If there is no point with the given
239 * %$x$%-coordinate, a null pointer is returned and the
240 * destination is left invalid.
243 extern ec
*ec_find(ec_curve */
*c*/
, ec */
*d*/
, mp */
*x*/
);
245 /* --- @ec_neg@ --- *
247 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
248 * @ec *d@ = pointer to the destination point
249 * @const ec *p@ = pointer to the operand point
251 * Returns: The destination point.
253 * Use: Computes the negation of the given point.
256 extern ec
*ec_neg(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
258 /* --- @ec_add@ --- *
260 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
261 * @ec *d@ = pointer to the destination point
262 * @const ec *p, *q@ = pointers to the operand points
264 * Returns: The destination @d@.
266 * Use: Adds two points on an elliptic curve.
269 extern ec
*ec_add(ec_curve */
*c*/
, ec */
*d*/
,
270 const ec */
*p*/
, const ec */
*q*/
);
272 /* --- @ec_sub@ --- *
274 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
275 * @ec *d@ = pointer to the destination point
276 * @const ec *p, *q@ = pointers to the operand points
278 * Returns: The destination @d@.
280 * Use: Subtracts one point from another on an elliptic curve.
283 extern ec
*ec_sub(ec_curve */
*c*/
, ec */
*d*/
,
284 const ec */
*p*/
, const ec */
*q*/
);
286 /* --- @ec_dbl@ --- *
288 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
289 * @ec *d@ = pointer to the destination point
290 * @const ec *p@ = pointer to the operand point
292 * Returns: The destination @d@.
294 * Use: Doubles a point on an elliptic curve.
297 extern ec
*ec_dbl(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
299 /* --- @ec_check@ --- *
301 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
302 * @const ec *p@ = pointer to the point
304 * Returns: Zero if OK, nonzero if this is an invalid point.
306 * Use: Checks that a point is actually on an elliptic curve.
309 extern int ec_check(ec_curve */
*c*/
, const ec */
*p*/
);
311 /* --- @ec_mul@, @ec_imul@ --- *
313 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
314 * @ec *d@ = pointer to the destination point
315 * @const ec *p@ = pointer to the generator point
316 * @mp *n@ = integer multiplier
318 * Returns: The destination @d@.
320 * Use: Multiplies a point by a scalar, returning %$n p$%. The
321 * @imul@ variant uses internal representations for argument
325 extern ec
*ec_mul(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, mp */
*n*/
);
326 extern ec
*ec_imul(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, mp */
*n*/
);
328 /* --- @ec_mmul@, @ec_immul@ --- *
330 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
331 * @ec *d@ = pointer to the destination point
332 * @const ec_mulfactor *f@ = pointer to vector of factors
333 * @size_t n@ = number of factors
335 * Returns: The destination @d@.
337 * Use: Does simultaneous point multiplication. The @immul@ variant
338 * uses internal representations for arguments and result.
341 extern ec
*ec_mmul(ec_curve */
*c*/
, ec */
*d*/
,
342 const ec_mulfactor */
*f*/
, size_t /*n*/);
343 extern ec
*ec_immul(ec_curve */
*c*/
, ec */
*d*/
,
344 const ec_mulfactor */
*f*/
, size_t /*n*/);
346 /*----- Standard curve operations -----------------------------------------*/
348 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
350 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
351 * @ec *d@ = pointer to the destination
352 * @const ec *p@ = pointer to a source point
354 * Returns: The destination @d@.
356 * Use: An identity operation if your curve has no internal
357 * representation. (The field internal representation is still
361 extern ec
*ec_idin(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
362 extern ec
*ec_idout(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
363 extern ec
*ec_idfix(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
365 /* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
367 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
368 * @ec *d@ = pointer to the destination
369 * @const ec *p@ = pointer to a source point
371 * Returns: The destination @d@.
373 * Use: Conversion functions if your curve operations use a
374 * projective representation.
377 extern ec
*ec_projin(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
378 extern ec
*ec_projout(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
379 extern ec
*ec_projfix(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
381 /* --- @ec_stdsub@ --- *
383 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
384 * @ec *d@ = pointer to the destination
385 * @const ec *p, *q@ = the operand points
387 * Returns: The destination @d@.
389 * Use: Standard point subtraction operation, in terms of negation
390 * and addition. This isn't as efficient as a ready-made
391 * subtraction operator.
394 extern ec
*ec_stdsub(ec_curve */
*c*/
, ec */
*d*/
,
395 const ec */
*p*/
, const ec */
*q*/
);
397 /*----- Creating curves ---------------------------------------------------*/
399 /* --- @ec_destroycurve@ --- *
401 * Arguments: @ec_curve *c@ = pointer to an ellptic curve
405 * Use: Destroys a description of an elliptic curve.
408 extern void ec_destroycurve(ec_curve */
*c*/
);
410 /* --- @ec_prime@, @ec_primeproj@ --- *
412 * Arguments: @field *f@ = the underlying field for this elliptic curve
413 * @mp *a, *b@ = the coefficients for this curve
415 * Returns: A pointer to the curve.
417 * Use: Creates a curve structure for an elliptic curve defined over
418 * a prime field. The @primeproj@ variant uses projective
419 * coordinates, which can be a win.
422 extern ec_curve
*ec_prime(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
423 extern ec_curve
*ec_primeproj(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
425 /* --- @ec_bin@, @ec_binproj@ --- *
427 * Arguments: @field *f@ = the underlying field for this elliptic curve
428 * @mp *a, *b@ = the coefficients for this curve
430 * Returns: A pointer to the curve.
432 * Use: Creates a curve structure for an elliptic curve defined over
433 * a binary field. The @binproj@ variant uses projective
434 * coordinates, which can be a win.
437 extern ec_curve
*ec_bin(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
438 extern ec_curve
*ec_binproj(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
440 /*----- That's all, folks -------------------------------------------------*/