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