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