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