comparison ecc.c @ 0:d7da3b1e1540 libtomcrypt

put back the 0.95 makefile which was inadvertently merged over
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:21:40 +0000
parents
children 5d99163f7e32
comparison
equal deleted inserted replaced
-1:000000000000 0:d7da3b1e1540
1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, [email protected], http://libtomcrypt.org
10 */
11
12 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
13 *
14 * All curves taken from NIST recommendation paper of July 1999
15 * Available at http://csrc.nist.gov/cryptval/dss.htm
16 */
17
18 #include "mycrypt.h"
19
20 #ifdef MECC
21
22 /* This holds the key settings. ***MUST*** be organized by size from smallest to largest. */
23 static const struct {
24 int size;
25 char *name, *prime, *B, *order, *Gx, *Gy;
26 } sets[] = {
27 #ifdef ECC160
28 {
29 20,
30 "ECC-160",
31 /* prime */
32 "G00000000000000000000000007",
33 /* B */
34 "1oUV2vOaSlWbxr6",
35 /* order */
36 "G0000000000004sCQUtDxaqDUN5",
37 /* Gx */
38 "jpqOf1BHus6Yd/pyhyVpP",
39 /* Gy */
40 "D/wykuuIFfr+vPyx7kQEPu8MixO",
41 },
42 #endif
43 #ifdef ECC192
44 {
45 24,
46 "ECC-192",
47 /* prime */
48 "/////////////////////l//////////",
49
50 /* B */
51 "P2456UMSWESFf+chSYGmIVwutkp1Hhcn",
52
53 /* order */
54 "////////////////cTxuDXHhoR6qqYWn",
55
56 /* Gx */
57 "68se3h0maFPylo3hGw680FJ/2ls2/n0I",
58
59 /* Gy */
60 "1nahbV/8sdXZ417jQoJDrNFvTw4UUKWH"
61 },
62 #endif
63 #ifdef ECC224
64 {
65 28,
66 "ECC-224",
67
68 /* prime */
69 "400000000000000000000000000000000000BV",
70
71 /* B */
72 "21HkWGL2CxJIp",
73
74 /* order */
75 "4000000000000000000Kxnixk9t8MLzMiV264/",
76
77 /* Gx */
78 "jpqOf1BHus6Yd/pyhyVpP",
79
80 /* Gy */
81 "3FCtyo2yHA5SFjkCGbYxbOvNeChwS+j6wSIwck",
82 },
83 #endif
84 #ifdef ECC256
85 {
86 32,
87 "ECC-256",
88 /* Prime */
89 "F////y000010000000000000000////////////////",
90
91 /* B */
92 "5h6DTYgEfFdi+kzLNQOXhnb7GQmp5EmzZlEF3udqc1B",
93
94 /* Order */
95 "F////y00000//////////+yvlgjfnUUXFEvoiByOoLH",
96
97 /* Gx */
98 "6iNqVBXB497+BpcvMEaGF9t0ts1BUipeFIXEKNOcCAM",
99
100 /* Gy */
101 "4/ZGkB+6d+RZkVhIdmFdXOhpZDNQp5UpiksG6Wtlr7r"
102 },
103 #endif
104 #ifdef ECC384
105 {
106 48,
107 "ECC-384",
108 /* prime */
109 "//////////////////////////////////////////x/////00000000003/"
110 "////",
111
112 /* B */
113 "ip4lf+8+v+IOZWLhu/Wj6HWTd6x+WK4I0nG8Zr0JXrh6LZcDYYxHdIg5oEtJ"
114 "x2hl",
115
116 /* Order */
117 "////////////////////////////////nsDDWVGtBTzO6WsoIB2dUkpi6MhC"
118 "nIbp",
119
120 /* Gx and Gy */
121 "geVA8hwB1JUEiSSUyo2jT6uTEsABfvkOMVT1u89KAZXL0l9TlrKfR3fKNZXo"
122 "TWgt",
123
124 "DXVUIfOcB6zTdfY/afBSAVZq7RqecXHywTen4xNmkC0AOB7E7Nw1dNf37NoG"
125 "wWvV"
126 },
127 #endif
128 #ifdef ECC521
129 {
130 65,
131 "ECC-521",
132 /* prime */
133 "V///////////////////////////////////////////////////////////"
134 "///////////////////////////",
135
136 /* B */
137 "56LFhbXZXoQ7vAQ8Q2sXK3kejfoMvcp5VEuj8cHZl49uLOPEL7iVfDx5bB0l"
138 "JknlmSrSz+8FImqyUz57zHhK3y0",
139
140 /* Order */
141 "V//////////////////////////////////////////+b66XuE/BvPhVym1I"
142 "FS9fT0xjScuYPn7hhjljnwHE6G9",
143
144 /* Gx and Gy */
145 "CQ5ZWQt10JfpPu+osOZbRH2d6I1EGK/jI7uAAzWQqqzkg5BNdVlvrae/Xt19"
146 "wB/gDupIBF1XMf2c/b+VZ72vRrc",
147
148 "HWvAMfucZl015oANxGiVHlPcFL4ILURH6WNhxqN9pvcB9VkSfbUz2P0nL2v0"
149 "J+j1s4rF726edB2G8Y+b7QVqMPG",
150 },
151 #endif
152 {
153 0,
154 NULL, NULL, NULL, NULL, NULL, NULL
155 }
156 };
157
158 #if 0
159
160 /* you plug in a prime and B value and it finds a pseudo-random base point */
161 void ecc_find_base(void)
162 {
163 static char *prime = "26959946667150639794667015087019630673637144422540572481103610249951";
164 static char *order = "26959946667150639794667015087019637467111563745054605861463538557247";
165 static char *b = "9538957348957353489587";
166 mp_int pp, p, r, B, tmp1, tmp2, tx, ty, x, y;
167 char buf[4096];
168 int i;
169
170 mp_init_multi(&tx, &ty, &x, &y, &p, &pp, &r, &B, &tmp1, &tmp2, NULL);
171 mp_read_radix(&p, prime, 10);
172 mp_read_radix(&r, order, 10);
173 mp_read_radix(&B, b, 10);
174
175 /* get (p+1)/4 */
176 mp_add_d(&p, 1, &pp);
177 mp_div_2(&pp, &pp);
178 mp_div_2(&pp, &pp);
179
180 buf[0] = 0;
181 do {
182 printf("."); fflush(stdout);
183 /* make a random value of x */
184 for (i = 0; i < 16; i++) buf[i+1] = rand() & 255;
185 mp_read_raw(&x, buf, 17);
186 mp_copy(&x, &tx);
187
188 /* now compute x^3 - 3x + b */
189 mp_expt_d(&x, 3, &tmp1);
190 mp_mul_d(&x, 3, &tmp2);
191 mp_sub(&tmp1, &tmp2, &tmp1);
192 mp_add(&tmp1, &B, &tmp1);
193 mp_mod(&tmp1, &p, &tmp1);
194
195 /* now compute sqrt via x^((p+1)/4) */
196 mp_exptmod(&tmp1, &pp, &p, &tmp2);
197 mp_copy(&tmp2, &ty);
198
199 /* now square it */
200 mp_sqrmod(&tmp2, &p, &tmp2);
201
202 /* tmp2 should equal tmp1 */
203 } while (mp_cmp(&tmp1, &tmp2));
204
205 /* now output values in way that libtomcrypt wants */
206 mp_todecimal(&p, buf);
207 printf("\n\np==%s\n", buf);
208 mp_tohex(&B, buf);
209 printf("b==%s\n", buf);
210 mp_todecimal(&r, buf);
211 printf("r==%s\n", buf);
212 mp_tohex(&tx, buf);
213 printf("Gx==%s\n", buf);
214 mp_tohex(&ty, buf);
215 printf("Gy==%s\n", buf);
216
217 mp_clear_multi(&tx, &ty, &x, &y, &p, &pp, &r, &B, &tmp1, &tmp2, NULL);
218 }
219
220 #endif
221
222
223
224
225 static int is_valid_idx(int n)
226 {
227 int x;
228
229 for (x = 0; sets[x].size != 0; x++);
230 if ((n < 0) || (n >= x)) {
231 return 0;
232 }
233 return 1;
234 }
235
236 static ecc_point *new_point(void)
237 {
238 ecc_point *p;
239 p = XMALLOC(sizeof(ecc_point));
240 if (p == NULL) {
241 return NULL;
242 }
243 if (mp_init_multi(&p->x, &p->y, NULL) != MP_OKAY) {
244 XFREE(p);
245 return NULL;
246 }
247 return p;
248 }
249
250 static void del_point(ecc_point *p)
251 {
252 /* prevents free'ing null arguments */
253 if (p != NULL) {
254 mp_clear_multi(&p->x, &p->y, NULL);
255 XFREE(p);
256 }
257 }
258
259 /* double a point R = 2P, R can be P*/
260 static int dbl_point(ecc_point *P, ecc_point *R, mp_int *modulus, mp_int *mu)
261 {
262 mp_int s, tmp, tmpx;
263 int err;
264
265 if ((err = mp_init_multi(&s, &tmp, &tmpx, NULL)) != MP_OKAY) {
266 return mpi_to_ltc_error(err);
267 }
268
269 /* s = (3Xp^2 + a) / (2Yp) */
270 if ((err = mp_mul_2(&P->y, &tmp)) != MP_OKAY) { goto error; } /* tmp = 2*y */
271 if ((err = mp_invmod(&tmp, modulus, &tmp)) != MP_OKAY) { goto error; } /* tmp = 1/tmp mod modulus */
272 if ((err = mp_sqr(&P->x, &s)) != MP_OKAY) { goto error; } /* s = x^2 */
273 if ((err = mp_reduce(&s, modulus, mu)) != MP_OKAY) { goto error; }
274 if ((err = mp_mul_d(&s,(mp_digit)3, &s)) != MP_OKAY) { goto error; } /* s = 3*(x^2) */
275 if ((err = mp_sub_d(&s,(mp_digit)3, &s)) != MP_OKAY) { goto error; } /* s = 3*(x^2) - 3 */
276 if (mp_cmp_d(&s, 0) == MP_LT) { /* if s < 0 add modulus */
277 if ((err = mp_add(&s, modulus, &s)) != MP_OKAY) { goto error; }
278 }
279 if ((err = mp_mul(&s, &tmp, &s)) != MP_OKAY) { goto error; } /* s = tmp * s mod modulus */
280 if ((err = mp_reduce(&s, modulus, mu)) != MP_OKAY) { goto error; }
281
282 /* Xr = s^2 - 2Xp */
283 if ((err = mp_sqr(&s, &tmpx)) != MP_OKAY) { goto error; } /* tmpx = s^2 */
284 if ((err = mp_reduce(&tmpx, modulus, mu)) != MP_OKAY) { goto error; } /* tmpx = tmpx mod modulus */
285 if ((err = mp_sub(&tmpx, &P->x, &tmpx)) != MP_OKAY) { goto error; } /* tmpx = tmpx - x */
286 if ((err = mp_submod(&tmpx, &P->x, modulus, &tmpx)) != MP_OKAY) { goto error; } /* tmpx = tmpx - x mod modulus */
287
288 /* Yr = -Yp + s(Xp - Xr) */
289 if ((err = mp_sub(&P->x, &tmpx, &tmp)) != MP_OKAY) { goto error; } /* tmp = x - tmpx */
290 if ((err = mp_mul(&tmp, &s, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp * s */
291 if ((err = mp_submod(&tmp, &P->y, modulus, &R->y)) != MP_OKAY) { goto error; } /* y = tmp - y mod modulus */
292 if ((err = mp_copy(&tmpx, &R->x)) != MP_OKAY) { goto error; } /* x = tmpx */
293
294 err = CRYPT_OK;
295 goto done;
296 error:
297 err = mpi_to_ltc_error(err);
298 done:
299 mp_clear_multi(&tmpx, &tmp, &s, NULL);
300 return err;
301 }
302
303 /* add two different points over Z/pZ, R = P + Q, note R can equal either P or Q */
304 static int add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mp_int *modulus, mp_int *mu)
305 {
306 mp_int s, tmp, tmpx;
307 int err;
308
309 if ((err = mp_init(&tmp)) != MP_OKAY) {
310 return mpi_to_ltc_error(err);
311 }
312
313 /* is P==Q or P==-Q? */
314 if (((err = mp_neg(&Q->y, &tmp)) != MP_OKAY) || ((err = mp_mod(&tmp, modulus, &tmp)) != MP_OKAY)) {
315 mp_clear(&tmp);
316 return mpi_to_ltc_error(err);
317 }
318
319 if (mp_cmp(&P->x, &Q->x) == MP_EQ)
320 if (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &tmp) == MP_EQ) {
321 mp_clear(&tmp);
322 return dbl_point(P, R, modulus, mu);
323 }
324
325 if ((err = mp_init_multi(&tmpx, &s, NULL)) != MP_OKAY) {
326 mp_clear(&tmp);
327 return mpi_to_ltc_error(err);
328 }
329
330 /* get s = (Yp - Yq)/(Xp-Xq) mod p */
331 if ((err = mp_sub(&P->x, &Q->x, &tmp)) != MP_OKAY) { goto error; } /* tmp = Px - Qx mod modulus */
332 if (mp_cmp_d(&tmp, 0) == MP_LT) { /* if tmp<0 add modulus */
333 if ((err = mp_add(&tmp, modulus, &tmp)) != MP_OKAY) { goto error; }
334 }
335 if ((err = mp_invmod(&tmp, modulus, &tmp)) != MP_OKAY) { goto error; } /* tmp = 1/tmp mod modulus */
336 if ((err = mp_sub(&P->y, &Q->y, &s)) != MP_OKAY) { goto error; } /* s = Py - Qy mod modulus */
337 if (mp_cmp_d(&s, 0) == MP_LT) { /* if s<0 add modulus */
338 if ((err = mp_add(&s, modulus, &s)) != MP_OKAY) { goto error; }
339 }
340 if ((err = mp_mul(&s, &tmp, &s)) != MP_OKAY) { goto error; } /* s = s * tmp mod modulus */
341 if ((err = mp_reduce(&s, modulus, mu)) != MP_OKAY) { goto error; }
342
343 /* Xr = s^2 - Xp - Xq */
344 if ((err = mp_sqr(&s, &tmp)) != MP_OKAY) { goto error; } /* tmp = s^2 mod modulus */
345 if ((err = mp_reduce(&tmp, modulus, mu)) != MP_OKAY) { goto error; }
346 if ((err = mp_sub(&tmp, &P->x, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp - Px */
347 if ((err = mp_sub(&tmp, &Q->x, &tmpx)) != MP_OKAY) { goto error; } /* tmpx = tmp - Qx */
348
349 /* Yr = -Yp + s(Xp - Xr) */
350 if ((err = mp_sub(&P->x, &tmpx, &tmp)) != MP_OKAY) { goto error; } /* tmp = Px - tmpx */
351 if ((err = mp_mul(&tmp, &s, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp * s */
352 if ((err = mp_submod(&tmp, &P->y, modulus, &R->y)) != MP_OKAY) { goto error; } /* Ry = tmp - Py mod modulus */
353 if ((err = mp_mod(&tmpx, modulus, &R->x)) != MP_OKAY) { goto error; } /* Rx = tmpx mod modulus */
354
355 err = CRYPT_OK;
356 goto done;
357 error:
358 err = mpi_to_ltc_error(err);
359 done:
360 mp_clear_multi(&s, &tmpx, &tmp, NULL);
361 return err;
362 }
363
364 /* size of sliding window, don't change this! */
365 #define WINSIZE 4
366
367 /* perform R = kG where k == integer and G == ecc_point */
368 static int ecc_mulmod(mp_int *k, ecc_point *G, ecc_point *R, mp_int *modulus)
369 {
370 ecc_point *tG, *M[8];
371 int i, j, err;
372 mp_int mu;
373 mp_digit buf;
374 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
375
376 /* init barrett reduction */
377 if ((err = mp_init(&mu)) != MP_OKAY) {
378 return mpi_to_ltc_error(err);
379 }
380 if ((err = mp_reduce_setup(&mu, modulus)) != MP_OKAY) {
381 mp_clear(&mu);
382 return mpi_to_ltc_error(err);
383 }
384
385 /* alloc ram for window temps */
386 for (i = 0; i < 8; i++) {
387 M[i] = new_point();
388 if (M[i] == NULL) {
389 for (j = 0; j < i; j++) {
390 del_point(M[j]);
391 }
392 mp_clear(&mu);
393 return CRYPT_MEM;
394 }
395 }
396
397 /* make a copy of G incase R==G */
398 tG = new_point();
399 if (tG == NULL) { err = CRYPT_MEM; goto done; }
400
401 /* tG = G */
402 if ((err = mp_copy(&G->x, &tG->x)) != MP_OKAY) { goto error; }
403 if ((err = mp_copy(&G->y, &tG->y)) != MP_OKAY) { goto error; }
404
405 /* calc the M tab, which holds kG for k==8..15 */
406 /* M[0] == 8G */
407 if ((err = dbl_point(G, M[0], modulus, &mu)) != CRYPT_OK) { goto done; }
408 if ((err = dbl_point(M[0], M[0], modulus, &mu)) != CRYPT_OK) { goto done; }
409 if ((err = dbl_point(M[0], M[0], modulus, &mu)) != CRYPT_OK) { goto done; }
410
411 /* now find (8+k)G for k=1..7 */
412 for (j = 9; j < 16; j++) {
413 if ((err = add_point(M[j-9], G, M[j-8], modulus, &mu)) != CRYPT_OK) { goto done; }
414 }
415
416 /* setup sliding window */
417 mode = 0;
418 bitcnt = 1;
419 buf = 0;
420 digidx = k->used - 1;
421 bitcpy = bitbuf = 0;
422 first = 1;
423
424 /* perform ops */
425 for (;;) {
426 /* grab next digit as required */
427 if (--bitcnt == 0) {
428 if (digidx == -1) {
429 break;
430 }
431 buf = k->dp[digidx--];
432 bitcnt = (int) DIGIT_BIT;
433 }
434
435 /* grab the next msb from the multiplicand */
436 i = (buf >> (DIGIT_BIT - 1)) & 1;
437 buf <<= 1;
438
439 /* skip leading zero bits */
440 if (mode == 0 && i == 0) {
441 continue;
442 }
443
444 /* if the bit is zero and mode == 1 then we double */
445 if (mode == 1 && i == 0) {
446 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; }
447 continue;
448 }
449
450 /* else we add it to the window */
451 bitbuf |= (i << (WINSIZE - ++bitcpy));
452 mode = 2;
453
454 if (bitcpy == WINSIZE) {
455 /* if this is the first window we do a simple copy */
456 if (first == 1) {
457 /* R = kG [k = first window] */
458 if ((err = mp_copy(&M[bitbuf-8]->x, &R->x)) != MP_OKAY) { goto error; }
459 if ((err = mp_copy(&M[bitbuf-8]->y, &R->y)) != MP_OKAY) { goto error; }
460 first = 0;
461 } else {
462 /* normal window */
463 /* ok window is filled so double as required and add */
464 /* double first */
465 for (j = 0; j < WINSIZE; j++) {
466 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; }
467 }
468
469 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
470 if ((err = add_point(R, M[bitbuf-8], R, modulus, &mu)) != CRYPT_OK) { goto done; }
471 }
472 /* empty window and reset */
473 bitcpy = bitbuf = 0;
474 mode = 1;
475 }
476 }
477
478 /* if bits remain then double/add */
479 if (mode == 2 && bitcpy > 0) {
480 /* double then add */
481 for (j = 0; j < bitcpy; j++) {
482 /* only double if we have had at least one add first */
483 if (first == 0) {
484 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; }
485 }
486
487 bitbuf <<= 1;
488 if ((bitbuf & (1 << WINSIZE)) != 0) {
489 if (first == 1){
490 /* first add, so copy */
491 if ((err = mp_copy(&tG->x, &R->x)) != MP_OKAY) { goto error; }
492 if ((err = mp_copy(&tG->y, &R->y)) != MP_OKAY) { goto error; }
493 first = 0;
494 } else {
495 /* then add */
496 if ((err = add_point(R, tG, R, modulus, &mu)) != CRYPT_OK) { goto done; }
497 }
498 }
499 }
500 }
501 err = CRYPT_OK;
502 goto done;
503 error:
504 err = mpi_to_ltc_error(err);
505 done:
506 del_point(tG);
507 for (i = 0; i < 8; i++) {
508 del_point(M[i]);
509 }
510 mp_clear(&mu);
511 return err;
512 }
513
514 #undef WINSIZE
515
516 int ecc_test(void)
517 {
518 mp_int modulus, order;
519 ecc_point *G, *GG;
520 int i, err, primality;
521
522 if ((err = mp_init_multi(&modulus, &order, NULL)) != MP_OKAY) {
523 return mpi_to_ltc_error(err);
524 }
525
526 G = new_point();
527 GG = new_point();
528 if (G == NULL || GG == NULL) {
529 mp_clear_multi(&modulus, &order, NULL);
530 del_point(G);
531 del_point(GG);
532 return CRYPT_MEM;
533 }
534
535 for (i = 0; sets[i].size; i++) {
536 #if 0
537 printf("Testing %d\n", sets[i].size);
538 #endif
539 if ((err = mp_read_radix(&modulus, (char *)sets[i].prime, 64)) != MP_OKAY) { goto error; }
540 if ((err = mp_read_radix(&order, (char *)sets[i].order, 64)) != MP_OKAY) { goto error; }
541
542 /* is prime actually prime? */
543 if ((err = is_prime(&modulus, &primality)) != CRYPT_OK) { goto done; }
544 if (primality == 0) {
545 err = CRYPT_FAIL_TESTVECTOR;
546 goto done;
547 }
548
549 /* is order prime ? */
550 if ((err = is_prime(&order, &primality)) != CRYPT_OK) { goto done; }
551 if (primality == 0) {
552 err = CRYPT_FAIL_TESTVECTOR;
553 goto done;
554 }
555
556 if ((err = mp_read_radix(&G->x, (char *)sets[i].Gx, 64)) != MP_OKAY) { goto error; }
557 if ((err = mp_read_radix(&G->y, (char *)sets[i].Gy, 64)) != MP_OKAY) { goto error; }
558
559 /* then we should have G == (order + 1)G */
560 if ((err = mp_add_d(&order, 1, &order)) != MP_OKAY) { goto error; }
561 if ((err = ecc_mulmod(&order, G, GG, &modulus)) != CRYPT_OK) { goto done; }
562 if (mp_cmp(&G->x, &GG->x) != 0 || mp_cmp(&G->y, &GG->y) != 0) {
563 err = CRYPT_FAIL_TESTVECTOR;
564 goto done;
565 }
566 }
567 err = CRYPT_OK;
568 goto done;
569 error:
570 err = mpi_to_ltc_error(err);
571 done:
572 del_point(GG);
573 del_point(G);
574 mp_clear_multi(&order, &modulus, NULL);
575 return err;
576 }
577
578 void ecc_sizes(int *low, int *high)
579 {
580 int i;
581 _ARGCHK(low != NULL);
582 _ARGCHK(high != NULL);
583
584 *low = INT_MAX;
585 *high = 0;
586 for (i = 0; sets[i].size != 0; i++) {
587 if (sets[i].size < *low) {
588 *low = sets[i].size;
589 }
590 if (sets[i].size > *high) {
591 *high = sets[i].size;
592 }
593 }
594 }
595
596 int ecc_make_key(prng_state *prng, int wprng, int keysize, ecc_key *key)
597 {
598 int x, err;
599 ecc_point *base;
600 mp_int prime;
601 unsigned char buf[128];
602
603 _ARGCHK(key != NULL);
604
605 /* good prng? */
606 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
607 return err;
608 }
609
610 /* find key size */
611 for (x = 0; (keysize > sets[x].size) && (sets[x].size != 0); x++);
612 keysize = sets[x].size;
613
614 if (sets[x].size == 0) {
615 return CRYPT_INVALID_KEYSIZE;
616 }
617 key->idx = x;
618
619 /* make up random string */
620 if (prng_descriptor[wprng].read(buf, (unsigned long)keysize, prng) != (unsigned long)keysize) {
621 return CRYPT_ERROR_READPRNG;
622 }
623
624 /* setup the key variables */
625 if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->k, &prime, NULL)) != MP_OKAY) {
626 return mpi_to_ltc_error(err);
627 }
628 base = new_point();
629 if (base == NULL) {
630 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->k, &prime, NULL);
631 return CRYPT_MEM;
632 }
633
634 /* read in the specs for this key */
635 if ((err = mp_read_radix(&prime, (char *)sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
636 if ((err = mp_read_radix(&base->x, (char *)sets[key->idx].Gx, 64)) != MP_OKAY) { goto error; }
637 if ((err = mp_read_radix(&base->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY) { goto error; }
638 if ((err = mp_read_unsigned_bin(&key->k, (unsigned char *)buf, keysize)) != MP_OKAY) { goto error; }
639
640 /* make the public key */
641 if ((err = ecc_mulmod(&key->k, base, &key->pubkey, &prime)) != CRYPT_OK) { goto done; }
642 key->type = PK_PRIVATE;
643
644 /* shrink key */
645 if ((err = mp_shrink(&key->k)) != MP_OKAY) { goto error; }
646 if ((err = mp_shrink(&key->pubkey.x)) != MP_OKAY) { goto error; }
647 if ((err = mp_shrink(&key->pubkey.y)) != MP_OKAY) { goto error; }
648
649 /* free up ram */
650 err = CRYPT_OK;
651 goto done;
652 error:
653 err = mpi_to_ltc_error(err);
654 done:
655 del_point(base);
656 mp_clear(&prime);
657 #ifdef CLEAN_STACK
658 zeromem(buf, sizeof(buf));
659 #endif
660 return err;
661 }
662
663 void ecc_free(ecc_key *key)
664 {
665 _ARGCHK(key != NULL);
666 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->k, NULL);
667 }
668
669 static int compress_y_point(ecc_point *pt, int idx, int *result)
670 {
671 mp_int tmp, tmp2, p;
672 int err;
673
674 _ARGCHK(pt != NULL);
675 _ARGCHK(result != NULL);
676
677 if ((err = mp_init_multi(&tmp, &tmp2, &p, NULL)) != MP_OKAY) {
678 return mpi_to_ltc_error(err);
679 }
680
681 /* get x^3 - 3x + b */
682 if ((err = mp_read_radix(&p, (char *)sets[idx].B, 64)) != MP_OKAY) { goto error; } /* p = B */
683 if ((err = mp_expt_d(&pt->x, 3, &tmp)) != MP_OKAY) { goto error; } /* tmp = pX^3 */
684 if ((err = mp_mul_d(&pt->x, 3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = 3*pX^3 */
685 if ((err = mp_sub(&tmp, &tmp2, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp - tmp2 */
686 if ((err = mp_add(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp + p */
687 if ((err = mp_read_radix(&p, (char *)sets[idx].prime, 64)) != MP_OKAY) { goto error; } /* p = prime */
688 if ((err = mp_mod(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp mod p */
689
690 /* now find square root */
691 if ((err = mp_add_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p + 1 */
692 if ((err = mp_div_2d(&tmp2, 2, &tmp2, NULL)) != MP_OKAY) { goto error; } /* tmp2 = (p+1)/4 */
693 if ((err = mp_exptmod(&tmp, &tmp2, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = (x^3 - 3x + b)^((p+1)/4) mod p */
694
695 /* if tmp equals the y point give a 0, otherwise 1 */
696 if (mp_cmp(&tmp, &pt->y) == 0) {
697 *result = 0;
698 } else {
699 *result = 1;
700 }
701
702 err = CRYPT_OK;
703 goto done;
704 error:
705 err = mpi_to_ltc_error(err);
706 done:
707 mp_clear_multi(&p, &tmp, &tmp2, NULL);
708 return err;
709 }
710
711 static int expand_y_point(ecc_point *pt, int idx, int result)
712 {
713 mp_int tmp, tmp2, p;
714 int err;
715
716 _ARGCHK(pt != NULL);
717
718 if ((err = mp_init_multi(&tmp, &tmp2, &p, NULL)) != MP_OKAY) {
719 return CRYPT_MEM;
720 }
721
722 /* get x^3 - 3x + b */
723 if ((err = mp_read_radix(&p, (char *)sets[idx].B, 64)) != MP_OKAY) { goto error; } /* p = B */
724 if ((err = mp_expt_d(&pt->x, 3, &tmp)) != MP_OKAY) { goto error; } /* tmp = pX^3 */
725 if ((err = mp_mul_d(&pt->x, 3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = 3*pX^3 */
726 if ((err = mp_sub(&tmp, &tmp2, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp - tmp2 */
727 if ((err = mp_add(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp + p */
728 if ((err = mp_read_radix(&p, (char *)sets[idx].prime, 64)) != MP_OKAY) { goto error; } /* p = prime */
729 if ((err = mp_mod(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp mod p */
730
731 /* now find square root */
732 if ((err = mp_add_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p + 1 */
733 if ((err = mp_div_2d(&tmp2, 2, &tmp2, NULL)) != MP_OKAY) { goto error; } /* tmp2 = (p+1)/4 */
734 if ((err = mp_exptmod(&tmp, &tmp2, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = (x^3 - 3x + b)^((p+1)/4) mod p */
735
736 /* if result==0, then y==tmp, otherwise y==p-tmp */
737 if (result == 0) {
738 if ((err = mp_copy(&tmp, &pt->y) != MP_OKAY)) { goto error; }
739 } else {
740 if ((err = mp_sub(&p, &tmp, &pt->y) != MP_OKAY)) { goto error; }
741 }
742
743 err = CRYPT_OK;
744 goto done;
745 error:
746 err = mpi_to_ltc_error(err);
747 done:
748 mp_clear_multi(&p, &tmp, &tmp2, NULL);
749 return err;
750 }
751
752 int ecc_export(unsigned char *out, unsigned long *outlen, int type, ecc_key *key)
753 {
754 unsigned long y, z;
755 int cp, err;
756
757 _ARGCHK(out != NULL);
758 _ARGCHK(outlen != NULL);
759 _ARGCHK(key != NULL);
760
761 /* can we store the static header? */
762 if (*outlen < (PACKET_SIZE + 3)) {
763 return CRYPT_BUFFER_OVERFLOW;
764 }
765
766 /* type valid? */
767 if (key->type != PK_PRIVATE && type == PK_PRIVATE) {
768 return CRYPT_PK_TYPE_MISMATCH;
769 }
770
771 /* output type and magic byte */
772 y = PACKET_SIZE;
773 out[y++] = (unsigned char)type;
774 out[y++] = (unsigned char)sets[key->idx].size;
775
776 /* output x coordinate */
777 OUTPUT_BIGNUM(&(key->pubkey.x), out, y, z);
778
779 /* compress y and output it */
780 if ((err = compress_y_point(&key->pubkey, key->idx, &cp)) != CRYPT_OK) {
781 return err;
782 }
783 out[y++] = (unsigned char)cp;
784
785 if (type == PK_PRIVATE) {
786 OUTPUT_BIGNUM(&key->k, out, y, z);
787 }
788
789 /* store header */
790 packet_store_header(out, PACKET_SECT_ECC, PACKET_SUB_KEY);
791 *outlen = y;
792
793 return CRYPT_OK;
794 }
795
796 int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key)
797 {
798 unsigned long x, y, s;
799 int err;
800
801 _ARGCHK(in != NULL);
802 _ARGCHK(key != NULL);
803
804 /* check length */
805 if ((3+PACKET_SIZE) > inlen) {
806 return CRYPT_INVALID_PACKET;
807 }
808
809 /* check type */
810 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_ECC, PACKET_SUB_KEY)) != CRYPT_OK) {
811 return err;
812 }
813
814 /* init key */
815 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->k, NULL) != MP_OKAY) {
816 return CRYPT_MEM;
817 }
818
819 y = PACKET_SIZE;
820 key->type = (int)in[y++];
821 s = (unsigned long)in[y++];
822
823 for (x = 0; (s > (unsigned long)sets[x].size) && (sets[x].size != 0); x++);
824 if (sets[x].size == 0) {
825 err = CRYPT_INVALID_KEYSIZE;
826 goto error;
827 }
828 key->idx = (int)x;
829
830 /* type check both values */
831 if ((key->type != PK_PUBLIC) && (key->type != PK_PRIVATE)) {
832 err = CRYPT_INVALID_PACKET;
833 goto error;
834 }
835
836 /* is the key idx valid? */
837 if (is_valid_idx(key->idx) != 1) {
838 err = CRYPT_INVALID_PACKET;
839 goto error;
840 }
841
842 /* load x coordinate */
843 INPUT_BIGNUM(&key->pubkey.x, in, x, y, inlen);
844
845 /* load y */
846 x = (unsigned long)in[y++];
847 if ((err = expand_y_point(&key->pubkey, key->idx, (int)x)) != CRYPT_OK) {
848 goto error;
849 }
850
851 if (key->type == PK_PRIVATE) {
852 /* load private key */
853 INPUT_BIGNUM(&key->k, in, x, y, inlen);
854 }
855
856 /* eliminate private key if public */
857 if (key->type == PK_PUBLIC) {
858 mp_clear(&key->k);
859 }
860
861 return CRYPT_OK;
862 error:
863 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->k, NULL);
864 return err;
865 }
866
867 int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
868 unsigned char *out, unsigned long *outlen)
869 {
870 unsigned long x, y;
871 ecc_point *result;
872 mp_int prime;
873 int err;
874
875 _ARGCHK(private_key != NULL);
876 _ARGCHK(public_key != NULL);
877 _ARGCHK(out != NULL);
878 _ARGCHK(outlen != NULL);
879
880 /* type valid? */
881 if (private_key->type != PK_PRIVATE) {
882 return CRYPT_PK_NOT_PRIVATE;
883 }
884
885 if (private_key->idx != public_key->idx) {
886 return CRYPT_PK_TYPE_MISMATCH;
887 }
888
889 /* make new point */
890 result = new_point();
891 if (result == NULL) {
892 return CRYPT_MEM;
893 }
894
895 if ((err = mp_init(&prime)) != MP_OKAY) {
896 del_point(result);
897 return mpi_to_ltc_error(err);
898 }
899
900 if ((err = mp_read_radix(&prime, (char *)sets[private_key->idx].prime, 64)) != MP_OKAY) { goto error; }
901 if ((err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime)) != CRYPT_OK) { goto done1; }
902
903 x = (unsigned long)mp_unsigned_bin_size(&result->x);
904 y = (unsigned long)mp_unsigned_bin_size(&result->y);
905
906 if (*outlen < (x+y)) {
907 err = CRYPT_BUFFER_OVERFLOW;
908 goto done1;
909 }
910 *outlen = x+y;
911 if ((err = mp_to_unsigned_bin(&result->x, out)) != MP_OKAY) { goto error; }
912 if ((err = mp_to_unsigned_bin(&result->y, out+x)) != MP_OKAY) { goto error; }
913
914 err = CRYPT_OK;
915 goto done1;
916 error:
917 err = mpi_to_ltc_error(err);
918 done1:
919 mp_clear(&prime);
920 del_point(result);
921 return err;
922 }
923
924 int ecc_get_size(ecc_key *key)
925 {
926 _ARGCHK(key != NULL);
927 if (is_valid_idx(key->idx))
928 return sets[key->idx].size;
929 else
930 return INT_MAX; /* large value known to cause it to fail when passed to ecc_make_key() */
931 }
932
933 #include "ecc_sys.c"
934
935 #endif
936
937