3 * $Id: ec.h,v 1.3 2002/01/13 13:48:44 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.3 2002/01/13 13:48:44 mdw
36 * Revision 1.2 2001/05/07 17:29:44 mdw
37 * Treat projective coordinates as an internal representation. Various
38 * minor interface changes.
40 * Revision 1.1 2001/04/29 18:12:33 mdw
52 /*----- Header files ------------------------------------------------------*/
57 /*----- Data structures ---------------------------------------------------*/
59 /* --- An elliptic curve representation --- */
61 typedef struct ec_curve
{
62 const struct ec_ops
*ops
; /* Curve operations */
63 field
*f
; /* Underlying field structure */
66 /* --- An elliptic curve point --- */
69 mp
*x
, *y
; /* Point coordinates */
70 mp
*z
; /* Common denominator (or null) */
73 /* --- A factor for simultaneous multiplication --- */
75 typedef struct ec_mulfactor
{
76 ec base
; /* The point */
77 ec
*exp
; /* The exponent */
80 /* --- Elliptic curve operations --- */
82 typedef struct ec_ops
{
83 void (*destroy
)(ec_curve */
*c*/
);
84 ec
*(*in
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
85 ec
*(*out
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
86 ec
*(*find
)(ec_curve */
*c*/
, ec */
*d*/
, mp */
*x*/
);
87 ec
*(*neg
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
88 ec
*(*add
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, const ec */
*q*/
);
89 ec
*(*sub
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, const ec */
*q*/
);
90 ec
*(*dbl
)(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
93 #define EC_IN(c, d, p) (c)->ops->in((c), (d), (p))
94 #define EC_OUT(c, d, p) (c)->ops->in((c), (d), (p))
96 #define EC_FIND(c, d, x) (c)->ops->find((c), (d), (x))
97 #define EC_NEG(c, d, x) (c)->ops->neg((c), (d), (x))
98 #define EC_ADD(c, d, p, q) (c)->ops->add((c), (d), (p), (q))
99 #define EC_SUB(c, d, p, q) (c)->ops->sub((c), (d), (p), (q))
100 #define EC_DBL(c, d, p) (c)->ops->dbl((c), (d), (p))
102 /*----- Simple memory management things -----------------------------------*/
104 /* --- @ec_create@ --- *
106 * Arguments: @ec *p@ = pointer to an elliptic-curve point
108 * Returns: The argument @p@.
110 * Use: Initializes a new point. The initial value is the additive
111 * identity (which is universal for all curves).
114 #define EC_INIT { MP_NEW, MP_NEW, MP_NEW }
116 #define EC_CREATE(p) do { \
118 _p->x = _p->y = _p->z = MP_NEW; \
121 extern ec
*ec_create(ec */
*p*/
);
123 /* --- @ec_destroy@ --- *
125 * Arguments: @ec *p@ = pointer to an elliptic-curve point
129 * Use: Destroys a point, making it invalid.
132 #define EC_DESTROY(p) do { \
134 if (!EC_ATINF(_p)) { \
137 if (_p->z) MP_DROP(_p->z); \
141 extern void ec_destroy(ec */
*p*/
);
143 /* --- @ec_atinf@ --- *
145 * Arguments: @const ec *p@ = pointer to a point
147 * Returns: Nonzero if %$p = O$% is the point at infinity, zero
151 #define EC_ATINF(p) ((p)->x == MP_NEW || (p)->x == MP_NEWSEC)
153 extern int ec_atinf(const ec */
*p*/
);
155 /* --- @ec_setinf@ --- *
157 * Arguments: @ec *p@ = pointer to a point
159 * Returns: The argument @p@.
161 * Use: Sets the given point to be the point %$O$% at infinity.
164 #define EC_SETINF(p) do { \
166 if (!EC_ATINF(_p)) { \
169 if (_p->z) MP_DROP(_p->z); \
170 _p->x = _p->y = _p->z = MP_NEW; \
176 extern ec
*ec_setinf(ec */
*p*/
);
178 /* --- @ec_copy@ --- *
180 * Arguments: @ec *d@ = pointer to destination point
181 * @const ec *p@ = pointer to source point
183 * Returns: The destination @d@.
185 * Use: Creates a copy of an elliptic curve point.
188 #define EC_COPY(d, p) do { \
190 const ec *_p = (p); \
194 _d->x = _d->y = _d->z = MP_NEW; \
196 _d->x = MP_COPY(_p->x); \
197 _d->y = MP_COPY(_p->y); \
198 _d->z = _p->z ? MP_COPY(_p->z) : MP_NEW; \
203 extern ec
*ec_copy(ec */
*d*/
, const ec */
*p*/
);
205 /*----- Interesting arithmetic --------------------------------------------*/
209 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
210 * @ec *d@ = pointer to the destination point
211 * @const ec *p@ = pointer to the source point
213 * Returns: The destination point.
215 * Use: Converts a point to internal representation.
218 extern ec
*ec_in(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
220 /* --- @ec_out@ --- *
222 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
223 * @ec *d@ = pointer to the destination point
224 * @const ec *p@ = pointer to the source point
226 * Returns: The destination point.
228 * Use: Converts a point to external representation.
231 extern ec
*ec_out(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
233 /* --- @ec_find@ --- *
235 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
236 * @ec *d@ = pointer to the destination point
237 * @mp *x@ = a possible x-coordinate
239 * Returns: The destination if OK, or null if no point was found.
241 * Use: Finds a point on an elliptic curve with a given
242 * x-coordinate. If there is no point with the given
243 * %$x$%-coordinate, a null pointer is returned and the
244 * destination is left invalid.
247 extern ec
*ec_find(ec_curve */
*c*/
, ec */
*d*/
, mp */
*x*/
);
249 /* --- @ec_neg@ --- *
251 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
252 * @ec *d@ = pointer to the destination point
253 * @const ec *p@ = pointer to the operand point
255 * Returns: The destination point.
257 * Use: Computes the negation of the given point.
260 extern ec
*ec_neg(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
262 /* --- @ec_add@ --- *
264 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
265 * @ec *d@ = pointer to the destination point
266 * @const ec *p, *q@ = pointers to the operand points
268 * Returns: The destination @d@.
270 * Use: Adds two points on an elliptic curve.
273 extern ec
*ec_add(ec_curve */
*c*/
, ec */
*d*/
,
274 const ec */
*p*/
, const ec */
*q*/
);
276 /* --- @ec_sub@ --- *
278 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
279 * @ec *d@ = pointer to the destination point
280 * @const ec *p, *q@ = pointers to the operand points
282 * Returns: The destination @d@.
284 * Use: Subtracts one point from another on an elliptic curve.
287 extern ec
*ec_sub(ec_curve */
*c*/
, ec */
*d*/
,
288 const ec */
*p*/
, const ec */
*q*/
);
290 /* --- @ec_dbl@ --- *
292 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
293 * @ec *d@ = pointer to the destination point
294 * @const ec *p@ = pointer to the operand point
296 * Returns: The destination @d@.
298 * Use: Doubles a point on an elliptic curve.
301 extern ec
*ec_dbl(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
303 /* --- @ec_mul@, @ec_imul@ --- *
305 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
306 * @ec *d@ = pointer to the destination point
307 * @const ec *p@ = pointer to the generator point
308 * @mp *n@ = integer multiplier
310 * Returns: The destination @d@.
312 * Use: Multiplies a point by a scalar, returning %$n p$%. The
313 * @imul@ variant uses internal representations for argument
317 extern ec
*ec_mul(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, mp */
*n*/
);
318 extern ec
*ec_imul(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
, mp */
*n*/
);
320 /* --- @ec_mmul@, @ec_immul@ --- *
322 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
323 * @ec *d@ = pointer to the destination point
324 * @const ec_mulfactor *f@ = pointer to vector of factors
325 * @size_t n@ = number of factors
327 * Returns: The destination @d@.
329 * Use: Does simultaneous point multiplication. The @immul@ variant
330 * uses internal representations for arguments and result.
333 extern ec
*ec_mmul(ec_curve */
*c*/
, ec */
*d*/
,
334 const ec_mulfactor */
*f*/
, size_t /*n*/);
335 extern ec
*ec_immul(ec_curve */
*c*/
, ec */
*d*/
,
336 const ec_mulfactor */
*f*/
, size_t /*n*/);
338 /*----- Standard curve operations -----------------------------------------*/
340 /* --- @ec_idin@, @ec_idout@ --- *
342 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
343 * @ec *d@ = pointer to the destination
344 * @const ec *p@ = pointer to a source point
346 * Returns: The destination @d@.
348 * Use: An identity operation if your curve has no internal
349 * representation. (The field internal representation is still
353 extern ec
*ec_idin(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
354 extern ec
*ec_idout(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
356 /* --- @ec_projin@, @ec_projout@ --- *
358 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
359 * @ec *d@ = pointer to the destination
360 * @const ec *p@ = pointer to a source point
362 * Returns: The destination @d@.
364 * Use: Conversion functions if your curve operations use a
365 * projective representation.
368 extern ec
*ec_projin(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
369 extern ec
*ec_projout(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
371 /* --- @ec_stdsub@ --- *
373 * Arguments: @ec_curve *c@ = pointer to an elliptic curve
374 * @ec *d@ = pointer to the destination
375 * @const ec *a, *b@ = the operand points
377 * Returns: The destination @d@.
379 * Use: Standard point subtraction operation, in terms of negation
380 * and addition. This isn't as efficient as a ready-made
381 * subtraction operator.
384 extern ec
*ec_stdsub(ec_curve */
*c*/
, ec */
*d*/
, const ec */
*p*/
);
386 /*----- Creating curves ---------------------------------------------------*/
388 /* --- @ec_destroycurve@ --- *
390 * Arguments: @ec_curve *c@ = pointer to an ellptic curve
394 * Use: Destroys a description of an elliptic curve.
397 extern void ec_destroycurve(ec_curve */
*c*/
);
399 /* --- @ec_prime@, @ec_primeproj@ --- *
401 * Arguments: @field *f@ = the underyling field for this elliptic curve
402 * @mp *a, *b@ = the coefficients for this curve
404 * Returns: A pointer to the curve.
406 * Use: Creates a curve structure for an elliptic curve defined over
407 * a prime field. The @primeproj@ variant uses projective
408 * coordinates, which can be a win.
411 extern ec_curve
*ec_prime(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
412 extern ec_curve
*ec_primeproj(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
414 /* --- @ec_bin@ --- *
416 * Arguments: @field *f@ = the underlying field for this elliptic curve
417 * @mp *a, *b@ = the coefficients for this curve
419 * Returns: A pointer to the curve.
421 * Use: Creates a curve structure for a non-supersingular elliptic
422 * curve defined over a binary field.
425 extern ec_curve
*ec_bin(field */
*f*/
, mp */
*a*/
, mp */
*b*/
);
427 /*----- That's all, folks -------------------------------------------------*/