1 /* $OpenBSD: math_ec2n.c,v 1.13 2005/04/08 22:32:10 cloder Exp $ */
2 /* $EOM: math_ec2n.c,v 1.9 1999/04/20 09:23:31 niklas Exp $ */
3
4 /*
5 * Copyright (c) 1998 Niels Provos. All rights reserved.
6 * Copyright (c) 1999 Niklas Hallqvist. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /*
30 * This code was written under funding by Ericsson Radio Systems.
31 */
32
33 #include <sys/param.h>
34 #include <stdio.h>
35
36 #include "math_2n.h"
37 #include "math_ec2n.h"
38
39 void
ec2np_init(ec2np_ptr n)40 ec2np_init(ec2np_ptr n)
41 {
42 b2n_init(n->x);
43 b2n_init(n->y);
44 n->inf = 0;
45 }
46
47 void
ec2np_clear(ec2np_ptr n)48 ec2np_clear(ec2np_ptr n)
49 {
50 b2n_clear(n->x);
51 b2n_clear(n->y);
52 }
53
54 int
ec2np_set(ec2np_ptr d,ec2np_ptr n)55 ec2np_set(ec2np_ptr d, ec2np_ptr n)
56 {
57 if (d == n)
58 return 0;
59
60 d->inf = n->inf;
61 if (b2n_set(d->x, n->x))
62 return -1;
63 return b2n_set(d->y, n->y);
64 }
65
66 /* Group */
67
68 void
ec2ng_init(ec2ng_ptr n)69 ec2ng_init(ec2ng_ptr n)
70 {
71 b2n_init(n->a);
72 b2n_init(n->b);
73 b2n_init(n->p);
74 }
75
76 void
ec2ng_clear(ec2ng_ptr n)77 ec2ng_clear(ec2ng_ptr n)
78 {
79 b2n_clear(n->a);
80 b2n_clear(n->b);
81 b2n_clear(n->p);
82 }
83
84 int
ec2ng_set(ec2ng_ptr d,ec2ng_ptr n)85 ec2ng_set(ec2ng_ptr d, ec2ng_ptr n)
86 {
87 if (b2n_set(d->a, n->a))
88 return -1;
89 if (b2n_set(d->b, n->b))
90 return -1;
91 return b2n_set(d->p, n->p);
92 }
93
94 /* Arithmetic functions */
95
96 int
ec2np_right(b2n_ptr n,ec2np_ptr p,ec2ng_ptr g)97 ec2np_right(b2n_ptr n, ec2np_ptr p, ec2ng_ptr g)
98 {
99 b2n_t temp;
100
101 b2n_init(temp);
102
103 /* First calc x**3 + ax**2 + b */
104 if (b2n_square(n, p->x))
105 goto fail;
106 if (b2n_mod(n, n, g->p))
107 goto fail;
108
109 if (b2n_mul(temp, g->a, n)) /* a*x**2 */
110 goto fail;
111 if (b2n_mod(temp, temp, g->p))
112 goto fail;
113
114 if (b2n_mul(n, n, p->x))/* x**3 */
115 goto fail;
116 if (b2n_mod(n, n, g->p))
117 goto fail;
118
119 if (b2n_add(n, n, temp))
120 goto fail;
121 if (b2n_add(n, n, g->b))
122 goto fail;
123
124 b2n_clear(temp);
125 return 0;
126
127 fail:
128 b2n_clear(temp);
129 return -1;
130 }
131
132 int
ec2np_ison(ec2np_ptr p,ec2ng_ptr g)133 ec2np_ison(ec2np_ptr p, ec2ng_ptr g)
134 {
135 int res;
136 b2n_t x, y, temp;
137
138 if (p->inf)
139 return 1;
140
141 b2n_init(x);
142 b2n_init(y);
143 b2n_init(temp);
144
145 /* First calc x**3 + ax**2 + b */
146 if (ec2np_right(x, p, g))
147 goto fail;
148
149 /* Now calc y**2 + xy */
150 if (b2n_square(y, p->y))
151 goto fail;
152 if (b2n_mod(y, y, g->p))
153 goto fail;
154
155 if (b2n_mul(temp, p->y, p->x))
156 goto fail;
157 if (b2n_mod(temp, temp, g->p))
158 goto fail;
159
160 if (b2n_add(y, y, temp))
161 goto fail;
162
163 res = !b2n_cmp(x, y);
164
165 b2n_clear(x);
166 b2n_clear(y);
167 b2n_clear(temp);
168 return res;
169
170 fail:
171 b2n_clear(x);
172 b2n_clear(y);
173 b2n_clear(temp);
174 return -1;
175 }
176
177 int
ec2np_find_y(ec2np_ptr p,ec2ng_ptr g)178 ec2np_find_y(ec2np_ptr p, ec2ng_ptr g)
179 {
180 b2n_t right;
181
182 b2n_init(right);
183
184 if (ec2np_right(right, p, g)) /* Right sight of equation */
185 goto fail;
186 if (b2n_mul_inv(p->y, p->x, g->p))
187 goto fail;
188
189 if (b2n_square(p->y, p->y))
190 goto fail;
191 if (b2n_mod(p->y, p->y, g->p))
192 goto fail;
193
194 if (b2n_mul(right, right, p->y)) /* x^-2 * right */
195 goto fail;
196 if (b2n_mod(right, right, g->p))
197 goto fail;
198
199 if (b2n_sqrt(p->y, right, g->p)) /* Find root */
200 goto fail;
201 if (b2n_mul(p->y, p->y, p->x))
202 goto fail;
203 if (b2n_mod(p->y, p->y, g->p))
204 goto fail;
205
206 b2n_clear(right);
207 return 0;
208
209 fail:
210 b2n_clear(right);
211 return -1;
212 }
213
214 int
ec2np_add(ec2np_ptr d,ec2np_ptr a,ec2np_ptr b,ec2ng_ptr g)215 ec2np_add(ec2np_ptr d, ec2np_ptr a, ec2np_ptr b, ec2ng_ptr g)
216 {
217 b2n_t lambda, temp;
218 ec2np_t pn;
219
220 /* Check for Neutral Element */
221 if (b->inf)
222 return ec2np_set(d, a);
223 if (a->inf)
224 return ec2np_set(d, b);
225
226 if (!b2n_cmp(a->x, b->x) && (b2n_cmp(a->y, b->y) ||
227 !b2n_cmp_null(a->x))) {
228 d->inf = 1;
229 if (b2n_set_null(d->x))
230 return -1;
231 return b2n_set_null(d->y);
232 }
233 b2n_init(lambda);
234 b2n_init(temp);
235 ec2np_init(pn);
236
237 if (b2n_cmp(a->x, b->x)) {
238 if (b2n_add(temp, a->x, b->x))
239 goto fail;
240 if (b2n_add(lambda, a->y, b->y))
241 goto fail;
242 if (b2n_div_mod(lambda, lambda, temp, g->p))
243 goto fail;
244
245 if (b2n_square(pn->x, lambda))
246 goto fail;
247 if (b2n_mod(pn->x, pn->x, g->p))
248 goto fail;
249
250 if (b2n_add(pn->x, pn->x, lambda))
251 goto fail;
252 if (b2n_add(pn->x, pn->x, g->a))
253 goto fail;
254 if (b2n_add(pn->x, pn->x, a->x))
255 goto fail;
256 if (b2n_add(pn->x, pn->x, b->x))
257 goto fail;
258 } else {
259 if (b2n_div_mod(lambda, b->y, b->x, g->p))
260 goto fail;
261 if (b2n_add(lambda, lambda, b->x))
262 goto fail;
263
264 if (b2n_square(pn->x, lambda))
265 goto fail;
266 if (b2n_mod(pn->x, pn->x, g->p))
267 goto fail;
268 if (b2n_add(pn->x, pn->x, lambda))
269 goto fail;
270 if (b2n_add(pn->x, pn->x, g->a))
271 goto fail;
272 }
273
274 if (b2n_add(pn->y, b->x, pn->x))
275 goto fail;
276
277 if (b2n_mul(pn->y, pn->y, lambda))
278 goto fail;
279 if (b2n_mod(pn->y, pn->y, g->p))
280 goto fail;
281
282 if (b2n_add(pn->y, pn->y, pn->x))
283 goto fail;
284 if (b2n_add(pn->y, pn->y, b->y))
285 goto fail;
286
287 EC2NP_SWAP(d, pn);
288
289 ec2np_clear(pn);
290 b2n_clear(lambda);
291 b2n_clear(temp);
292 return 0;
293
294 fail:
295 ec2np_clear(pn);
296 b2n_clear(lambda);
297 b2n_clear(temp);
298 return -1;
299 }
300
301 int
ec2np_mul(ec2np_ptr d,ec2np_ptr a,b2n_ptr e,ec2ng_ptr g)302 ec2np_mul(ec2np_ptr d, ec2np_ptr a, b2n_ptr e, ec2ng_ptr g)
303 {
304 int i, j, bits, start;
305 b2n_t h, k;
306 ec2np_t q, mina;
307
308 if (!b2n_cmp_null(e)) {
309 d->inf = 1;
310 if (b2n_set_null(d->x))
311 return -1;
312 return b2n_set_null(d->y);
313 }
314 b2n_init(h);
315 b2n_init(k);
316 ec2np_init(q);
317 ec2np_init(mina);
318
319 if (ec2np_set(q, a))
320 goto fail;
321
322 /* Create the point -a. */
323 if (ec2np_set(mina, a))
324 goto fail;
325 if (b2n_add(mina->y, mina->y, mina->x))
326 goto fail;
327
328 if (b2n_set(k, e))
329 goto fail;
330 if (b2n_3mul(h, k))
331 goto fail;
332 if (b2n_resize(k, h->chunks))
333 goto fail;
334
335 /*
336 * This is low level but can not be avoided, since we have to do single
337 * bit checks on h and k.
338 */
339 bits = b2n_sigbit(h);
340 if ((bits & CHUNK_MASK) == 1) {
341 start = ((CHUNK_MASK + bits) >> CHUNK_SHIFTS) - 2;
342 bits = CHUNK_BITS;
343 } else {
344 start = ((CHUNK_MASK + bits) >> CHUNK_SHIFTS) - 1;
345 bits = ((bits - 1) & CHUNK_MASK);
346 }
347
348 /*
349 * This is the addition, subtraction method which is faster because
350 * we avoid one out of three additions (mean).
351 */
352 for (i = start; i >= 0; i--)
353 for (j = (i == start ? bits : CHUNK_BITS) - 1; j >= 0; j--)
354 if (i > 0 || j > 0) {
355 if (ec2np_add(q, q, q, g))
356 goto fail;
357 if ((h->limp[i] & b2n_mask[j]) && !(k->limp[i]
358 & b2n_mask[j])) {
359 if (ec2np_add(q, q, a, g))
360 goto fail;
361 } else if (!(h->limp[i] & b2n_mask[j]) &&
362 (k->limp[i] & b2n_mask[j]))
363 if (ec2np_add(q, q, mina, g))
364 goto fail;
365 }
366 EC2NP_SWAP(d, q);
367
368 b2n_clear(k);
369 b2n_clear(h);
370 ec2np_clear(q);
371 ec2np_clear(mina);
372 return 0;
373
374 fail:
375 b2n_clear(k);
376 b2n_clear(h);
377 ec2np_clear(q);
378 ec2np_clear(mina);
379 return -1;
380 }
381