Mercurial > dropbear

comparison ecc.c @ 0:d7da3b1e1540 libtomcrypt

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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