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