Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ecc.c @ 285:1b9e69c058d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
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 #include "tomcrypt.h"
18
19 /**
20 @file ecc.c
21 ECC Crypto, Tom St Denis
22 */
23
24 #ifdef MECC
25
26 /* size of our temp buffers for exported keys */
27 #define ECC_BUF_SIZE 256
28
29 /* max private key size */
30 #define ECC_MAXSIZE 66
31
32 /* This holds the key settings. ***MUST*** be organized by size from smallest to largest. */
33 static const struct {
34 int size;
35 char *name, *prime, *B, *order, *Gx, *Gy;
36 } sets[] = {
37 #ifdef ECC192
38 {
39 24,
40 "ECC-192",
41 /* prime */
42 "/////////////////////l//////////",
43
44 /* B */
45 "P2456UMSWESFf+chSYGmIVwutkp1Hhcn",
46
47 /* order */
48 "////////////////cTxuDXHhoR6qqYWn",
49
50 /* Gx */
51 "68se3h0maFPylo3hGw680FJ/2ls2/n0I",
52
53 /* Gy */
54 "1nahbV/8sdXZ417jQoJDrNFvTw4UUKWH"
55 },
56 #endif
57 #ifdef ECC224
58 {
59 28,
60 "ECC-224",
61
62 /* prime */
63 "3/////////////////////0000000000000001",
64
65 /* B */
66 "2q1Gg530Ipg/L1CbPGHB2trx/OkYSBEKCZLV+q",
67
68 /* order */
69 "3//////////////////nQYuBZmFXFTAKLSN2ez",
70
71 /* Gx */
72 "2t3WozQxI/Vp8JaBbA0y7JLi8H8ZGoWDOHN1qX",
73
74
75 /* Gy */
76 "2zDsE8jVSZ+qmYt+RDGtMWMWT7P4JLWPc507uq",
77 },
78 #endif
79 #ifdef ECC256
80 {
81 32,
82 "ECC-256",
83 /* Prime */
84 "F////y000010000000000000000////////////////",
85
86 /* B */
87 "5h6DTYgEfFdi+kzLNQOXhnb7GQmp5EmzZlEF3udqc1B",
88
89 /* Order */
90 "F////y00000//////////+yvlgjfnUUXFEvoiByOoLH",
91
92 /* Gx */
93 "6iNqVBXB497+BpcvMEaGF9t0ts1BUipeFIXEKNOcCAM",
94
95 /* Gy */
96 "4/ZGkB+6d+RZkVhIdmFdXOhpZDNQp5UpiksG6Wtlr7r"
97 },
98 #endif
99 #ifdef ECC384
100 {
101 48,
102 "ECC-384",
103 /* prime */
104 "//////////////////////////////////////////x/////00000000003/"
105 "////",
106
107 /* B */
108 "ip4lf+8+v+IOZWLhu/Wj6HWTd6x+WK4I0nG8Zr0JXrh6LZcDYYxHdIg5oEtJ"
109 "x2hl",
110
111 /* Order */
112 "////////////////////////////////nsDDWVGtBTzO6WsoIB2dUkpi6MhC"
113 "nIbp",
114
115 /* Gx and Gy */
116 "geVA8hwB1JUEiSSUyo2jT6uTEsABfvkOMVT1u89KAZXL0l9TlrKfR3fKNZXo"
117 "TWgt",
118
119 "DXVUIfOcB6zTdfY/afBSAVZq7RqecXHywTen4xNmkC0AOB7E7Nw1dNf37NoG"
120 "wWvV"
121 },
122 #endif
123 #ifdef ECC521
124 {
125 65,
126 "ECC-521",
127 /* prime */
128 "V///////////////////////////////////////////////////////////"
129 "///////////////////////////",
130
131 /* B */
132 "56LFhbXZXoQ7vAQ8Q2sXK3kejfoMvcp5VEuj8cHZl49uLOPEL7iVfDx5bB0l"
133 "JknlmSrSz+8FImqyUz57zHhK3y0",
134
135 /* Order */
136 "V//////////////////////////////////////////+b66XuE/BvPhVym1I"
137 "FS9fT0xjScuYPn7hhjljnwHE6G9",
138
139 /* Gx and Gy */
140 "CQ5ZWQt10JfpPu+osOZbRH2d6I1EGK/jI7uAAzWQqqzkg5BNdVlvrae/Xt19"
141 "wB/gDupIBF1XMf2c/b+VZ72vRrc",
142
143 "HWvAMfucZl015oANxGiVHlPcFL4ILURH6WNhxqN9pvcB9VkSfbUz2P0nL2v0"
144 "J+j1s4rF726edB2G8Y+b7QVqMPG",
145 },
146 #endif
147 {
148 0,
149 NULL, NULL, NULL, NULL, NULL, NULL
150 }
151 };
152
153 static int is_valid_idx(int n)
154 {
155 int x;
156
157 for (x = 0; sets[x].size != 0; x++);
158 if ((n < 0) || (n >= x)) {
159 return 0;
160 }
161 return 1;
162 }
163
164 static ecc_point *new_point(void)
165 {
166 ecc_point *p;
167 p = XMALLOC(sizeof(ecc_point));
168 if (p == NULL) {
169 return NULL;
170 }
171 if (mp_init_multi(&p->x, &p->y, &p->z, NULL) != MP_OKAY) {
172 XFREE(p);
173 return NULL;
174 }
175 return p;
176 }
177
178 static void del_point(ecc_point *p)
179 {
180 /* prevents free'ing null arguments */
181 if (p != NULL) {
182 mp_clear_multi(&p->x, &p->y, &p->z, NULL);
183 XFREE(p);
184 }
185 }
186
187 static int ecc_map(ecc_point *P, mp_int *modulus, mp_digit mp)
188 {
189 mp_int t1, t2;
190 int err;
191
192 if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) {
193 return CRYPT_MEM;
194 }
195
196 /* first map z back to normal */
197 if ((err = mp_montgomery_reduce(&P->z, modulus, mp)) != MP_OKAY) { goto error; }
198
199 /* get 1/z */
200 if ((err = mp_invmod(&P->z, modulus, &t1)) != MP_OKAY) { goto error; }
201
202 /* get 1/z^2 and 1/z^3 */
203 if ((err = mp_sqr(&t1, &t2)) != MP_OKAY) { goto error; }
204 if ((err = mp_mod(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
205 if ((err = mp_mul(&t1, &t2, &t1)) != MP_OKAY) { goto error; }
206 if ((err = mp_mod(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
207
208 /* multiply against x/y */
209 if ((err = mp_mul(&P->x, &t2, &P->x)) != MP_OKAY) { goto error; }
210 if ((err = mp_montgomery_reduce(&P->x, modulus, mp)) != MP_OKAY) { goto error; }
211 if ((err = mp_mul(&P->y, &t1, &P->y)) != MP_OKAY) { goto error; }
212 if ((err = mp_montgomery_reduce(&P->y, modulus, mp)) != MP_OKAY) { goto error; }
213 mp_set(&P->z, 1);
214
215 err = CRYPT_OK;
216 goto done;
217 error:
218 err = mpi_to_ltc_error(err);
219 done:
220 mp_clear_multi(&t1, &t2, NULL);
221 return err;
222
223 }
224
225 /* double a point R = 2P, R can be P*/
226 static int dbl_point(ecc_point *P, ecc_point *R, mp_int *modulus, mp_digit mp)
227 {
228 mp_int t1, t2;
229 int err;
230
231 if ((err = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
232 return mpi_to_ltc_error(err);
233 }
234
235 if ((err = mp_copy(&P->x, &R->x)) != MP_OKAY) { goto error; }
236 if ((err = mp_copy(&P->y, &R->y)) != MP_OKAY) { goto error; }
237 if ((err = mp_copy(&P->z, &R->z)) != MP_OKAY) { goto error; }
238
239 /* t1 = Z * Z */
240 if ((err = mp_sqr(&R->z, &t1)) != MP_OKAY) { goto error; }
241 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
242 /* Z = Y * Z */
243 if ((err = mp_mul(&R->z, &R->y, &R->z)) != MP_OKAY) { goto error; }
244 if ((err = mp_montgomery_reduce(&R->z, modulus, mp)) != MP_OKAY) { goto error; }
245 /* Z = 2Z */
246 if ((err = mp_mul_2(&R->z, &R->z)) != MP_OKAY) { goto error; }
247 if (mp_cmp(&R->z, modulus) != MP_LT) {
248 if ((err = mp_sub(&R->z, modulus, &R->z)) != MP_OKAY) { goto error; }
249 }
250
251 /* T2 = X - T1 */
252 if ((err = mp_sub(&R->x, &t1, &t2)) != MP_OKAY) { goto error; }
253 if (mp_cmp_d(&t2, 0) == MP_LT) {
254 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
255 }
256 /* T1 = X + T1 */
257 if ((err = mp_add(&t1, &R->x, &t1)) != MP_OKAY) { goto error; }
258 if (mp_cmp(&t1, modulus) != MP_LT) {
259 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
260 }
261 /* T2 = T1 * T2 */
262 if ((err = mp_mul(&t1, &t2, &t2)) != MP_OKAY) { goto error; }
263 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
264 /* T1 = 2T2 */
265 if ((err = mp_mul_2(&t2, &t1)) != MP_OKAY) { goto error; }
266 if (mp_cmp(&t1, modulus) != MP_LT) {
267 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
268 }
269 /* T1 = T1 + T2 */
270 if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) { goto error; }
271 if (mp_cmp(&t1, modulus) != MP_LT) {
272 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
273 }
274
275 /* Y = 2Y */
276 if ((err = mp_mul_2(&R->y, &R->y)) != MP_OKAY) { goto error; }
277 if (mp_cmp(&R->y, modulus) != MP_LT) {
278 if ((err = mp_sub(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
279 }
280 /* Y = Y * Y */
281 if ((err = mp_sqr(&R->y, &R->y)) != MP_OKAY) { goto error; }
282 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
283 /* T2 = Y * Y */
284 if ((err = mp_sqr(&R->y, &t2)) != MP_OKAY) { goto error; }
285 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
286 /* T2 = T2/2 */
287 if (mp_isodd(&t2)) {
288 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
289 }
290 if ((err = mp_div_2(&t2, &t2)) != MP_OKAY) { goto error; }
291 /* Y = Y * X */
292 if ((err = mp_mul(&R->y, &R->x, &R->y)) != MP_OKAY) { goto error; }
293 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
294
295 /* X = T1 * T1 */
296 if ((err = mp_sqr(&t1, &R->x)) != MP_OKAY) { goto error; }
297 if ((err = mp_montgomery_reduce(&R->x, modulus, mp)) != MP_OKAY) { goto error; }
298 /* X = X - Y */
299 if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY) { goto error; }
300 if (mp_cmp_d(&R->x, 0) == MP_LT) {
301 if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY) { goto error; }
302 }
303 /* X = X - Y */
304 if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY) { goto error; }
305 if (mp_cmp_d(&R->x, 0) == MP_LT) {
306 if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY) { goto error; }
307 }
308
309 /* Y = Y - X */
310 if ((err = mp_sub(&R->y, &R->x, &R->y)) != MP_OKAY) { goto error; }
311 if (mp_cmp_d(&R->y, 0) == MP_LT) {
312 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
313 }
314 /* Y = Y * T1 */
315 if ((err = mp_mul(&R->y, &t1, &R->y)) != MP_OKAY) { goto error; }
316 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
317 /* Y = Y - T2 */
318 if ((err = mp_sub(&R->y, &t2, &R->y)) != MP_OKAY) { goto error; }
319 if (mp_cmp_d(&R->y, 0) == MP_LT) {
320 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
321 }
322
323 err = CRYPT_OK;
324 goto done;
325 error:
326 err = mpi_to_ltc_error(err);
327 done:
328 mp_clear_multi(&t1, &t2, NULL);
329 return err;
330 }
331
332 /* add two different points over Z/pZ, R = P + Q, note R can equal either P or Q */
333 static int add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mp_int *modulus, mp_digit mp)
334 {
335 mp_int t1, t2, x, y, z;
336 int err;
337
338 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
339 return mpi_to_ltc_error(err);
340 }
341
342 if ((err = mp_copy(&P->x, &x)) != MP_OKAY) { goto error; }
343 if ((err = mp_copy(&P->y, &y)) != MP_OKAY) { goto error; }
344 if ((err = mp_copy(&P->z, &z)) != MP_OKAY) { goto error; }
345
346 /* T1 = Z' * Z' */
347 if ((err = mp_sqr(&Q->z, &t1)) != MP_OKAY) { goto error; }
348 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
349 /* X = X * T1 */
350 if ((err = mp_mul(&t1, &x, &x)) != MP_OKAY) { goto error; }
351 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
352 /* T1 = Z' * T1 */
353 if ((err = mp_mul(&Q->z, &t1, &t1)) != MP_OKAY) { goto error; }
354 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
355 /* Y = Y * T1 */
356 if ((err = mp_mul(&t1, &y, &y)) != MP_OKAY) { goto error; }
357 if ((err = mp_montgomery_reduce(&y, modulus, mp)) != MP_OKAY) { goto error; }
358
359 /* T1 = Z*Z */
360 if ((err = mp_sqr(&z, &t1)) != MP_OKAY) { goto error; }
361 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
362 /* T2 = X' * T1 */
363 if ((err = mp_mul(&Q->x, &t1, &t2)) != MP_OKAY) { goto error; }
364 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
365 /* T1 = Z * T1 */
366 if ((err = mp_mul(&z, &t1, &t1)) != MP_OKAY) { goto error; }
367 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
368 /* T1 = Y' * T1 */
369 if ((err = mp_mul(&Q->y, &t1, &t1)) != MP_OKAY) { goto error; }
370 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
371
372 /* Y = Y - T1 */
373 if ((err = mp_sub(&y, &t1, &y)) != MP_OKAY) { goto error; }
374 if (mp_cmp_d(&y, 0) == MP_LT) {
375 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; }
376 }
377 /* T1 = 2T1 */
378 if ((err = mp_mul_2(&t1, &t1)) != MP_OKAY) { goto error; }
379 if (mp_cmp(&t1, modulus) != MP_LT) {
380 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
381 }
382 /* T1 = Y + T1 */
383 if ((err = mp_add(&t1, &y, &t1)) != MP_OKAY) { goto error; }
384 if (mp_cmp(&t1, modulus) != MP_LT) {
385 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
386 }
387 /* X = X - T2 */
388 if ((err = mp_sub(&x, &t2, &x)) != MP_OKAY) { goto error; }
389 if (mp_cmp_d(&x, 0) == MP_LT) {
390 if ((err = mp_add(&x, modulus, &x)) != MP_OKAY) { goto error; }
391 }
392 /* T2 = 2T2 */
393 if ((err = mp_mul_2(&t2, &t2)) != MP_OKAY) { goto error; }
394 if (mp_cmp(&t2, modulus) != MP_LT) {
395 if ((err = mp_sub(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
396 }
397 /* T2 = X + T2 */
398 if ((err = mp_add(&t2, &x, &t2)) != MP_OKAY) { goto error; }
399 if (mp_cmp(&t2, modulus) != MP_LT) {
400 if ((err = mp_sub(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
401 }
402
403 /* if Z' != 1 */
404 if (mp_cmp_d(&Q->z, 1) != MP_EQ) {
405 /* Z = Z * Z' */
406 if ((err = mp_mul(&z, &Q->z, &z)) != MP_OKAY) { goto error; }
407 if ((err = mp_montgomery_reduce(&z, modulus, mp)) != MP_OKAY) { goto error; }
408 }
409 /* Z = Z * X */
410 if ((err = mp_mul(&z, &x, &z)) != MP_OKAY) { goto error; }
411 if ((err = mp_montgomery_reduce(&z, modulus, mp)) != MP_OKAY) { goto error; }
412
413 /* T1 = T1 * X */
414 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; }
415 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
416 /* X = X * X */
417 if ((err = mp_sqr(&x, &x)) != MP_OKAY) { goto error; }
418 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
419 /* T2 = T2 * x */
420 if ((err = mp_mul(&t2, &x, &t2)) != MP_OKAY) { goto error; }
421 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
422 /* T1 = T1 * X */
423 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; }
424 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
425
426 /* X = Y*Y */
427 if ((err = mp_sqr(&y, &x)) != MP_OKAY) { goto error; }
428 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
429 /* X = X - T2 */
430 if ((err = mp_sub(&x, &t2, &x)) != MP_OKAY) { goto error; }
431 if (mp_cmp_d(&x, 0) == MP_LT) {
432 if ((err = mp_add(&x, modulus, &x)) != MP_OKAY) { goto error; }
433 }
434
435 /* T2 = T2 - X */
436 if ((err = mp_sub(&t2, &x, &t2)) != MP_OKAY) { goto error; }
437 if (mp_cmp_d(&t2, 0) == MP_LT) {
438 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
439 }
440 /* T2 = T2 - X */
441 if ((err = mp_sub(&t2, &x, &t2)) != MP_OKAY) { goto error; }
442 if (mp_cmp_d(&t2, 0) == MP_LT) {
443 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
444 }
445 /* T2 = T2 * Y */
446 if ((err = mp_mul(&t2, &y, &t2)) != MP_OKAY) { goto error; }
447 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
448 /* Y = T2 - T1 */
449 if ((err = mp_sub(&t2, &t1, &y)) != MP_OKAY) { goto error; }
450 if (mp_cmp_d(&y, 0) == MP_LT) {
451 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; }
452 }
453 /* Y = Y/2 */
454 if (mp_isodd(&y)) {
455 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; }
456 }
457 if ((err = mp_div_2(&y, &y)) != MP_OKAY) { goto error; }
458
459 if ((err = mp_copy(&x, &R->x)) != MP_OKAY) { goto error; }
460 if ((err = mp_copy(&y, &R->y)) != MP_OKAY) { goto error; }
461 if ((err = mp_copy(&z, &R->z)) != MP_OKAY) { goto error; }
462
463 err = CRYPT_OK;
464 goto done;
465 error:
466 err = mpi_to_ltc_error(err);
467 done:
468 mp_clear_multi(&t1, &t2, &x, &y, &z, NULL);
469 return err;
470 }
471
472 /* size of sliding window, don't change this! */
473 #define WINSIZE 4
474
475 /* perform R = kG where k == integer and G == ecc_point */
476 static int ecc_mulmod(mp_int *k, ecc_point *G, ecc_point *R, mp_int *modulus, int map)
477 {
478 ecc_point *tG, *M[8];
479 int i, j, err;
480 mp_int mu;
481 mp_digit buf, mp;
482 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
483
484 /* init montgomery reduction */
485 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
486 return CRYPT_INVALID_ARG;
487 }
488 if ((err = mp_init(&mu)) != MP_OKAY) {
489 return CRYPT_MEM;
490 }
491 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
492 mp_clear(&mu);
493 return CRYPT_INVALID_ARG;
494 }
495
496 /* alloc ram for window temps */
497 for (i = 0; i < 8; i++) {
498 M[i] = new_point();
499 if (M[i] == NULL) {
500 for (j = 0; j < i; j++) {
501 del_point(M[j]);
502 }
503 mp_clear(&mu);
504 return CRYPT_MEM;
505 }
506 }
507
508 /* make a copy of G incase R==G */
509 tG = new_point();
510 if (tG == NULL) { err = CRYPT_MEM; goto done; }
511
512 /* tG = G and convert to montgomery */
513 if ((err = mp_mulmod(&G->x, &mu, modulus, &tG->x)) != MP_OKAY) { goto error; }
514 if ((err = mp_mulmod(&G->y, &mu, modulus, &tG->y)) != MP_OKAY) { goto error; }
515 if ((err = mp_mulmod(&G->z, &mu, modulus, &tG->z)) != MP_OKAY) { goto error; }
516 mp_clear(&mu);
517
518 /* calc the M tab, which holds kG for k==8..15 */
519 /* M[0] == 8G */
520 if ((err = dbl_point(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; }
521 if ((err = dbl_point(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
522 if ((err = dbl_point(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
523
524 /* now find (8+k)G for k=1..7 */
525 for (j = 9; j < 16; j++) {
526 if ((err = add_point(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; }
527 }
528
529 /* setup sliding window */
530 mode = 0;
531 bitcnt = 1;
532 buf = 0;
533 digidx = k->used - 1;
534 bitcpy = bitbuf = 0;
535 first = 1;
536
537 /* perform ops */
538 for (;;) {
539 /* grab next digit as required */
540 if (--bitcnt == 0) {
541 if (digidx == -1) {
542 break;
543 }
544 buf = k->dp[digidx--];
545 bitcnt = (int) DIGIT_BIT;
546 }
547
548 /* grab the next msb from the ltiplicand */
549 i = (buf >> (DIGIT_BIT - 1)) & 1;
550 buf <<= 1;
551
552 /* skip leading zero bits */
553 if (mode == 0 && i == 0) {
554 continue;
555 }
556
557 /* if the bit is zero and mode == 1 then we double */
558 if (mode == 1 && i == 0) {
559 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
560 continue;
561 }
562
563 /* else we add it to the window */
564 bitbuf |= (i << (WINSIZE - ++bitcpy));
565 mode = 2;
566
567 if (bitcpy == WINSIZE) {
568 /* if this is the first window we do a simple copy */
569 if (first == 1) {
570 /* R = kG [k = first window] */
571 if ((err = mp_copy(&M[bitbuf-8]->x, &R->x)) != MP_OKAY) { goto error; }
572 if ((err = mp_copy(&M[bitbuf-8]->y, &R->y)) != MP_OKAY) { goto error; }
573 if ((err = mp_copy(&M[bitbuf-8]->z, &R->z)) != MP_OKAY) { goto error; }
574 first = 0;
575 } else {
576 /* normal window */
577 /* ok window is filled so double as required and add */
578 /* double first */
579 for (j = 0; j < WINSIZE; j++) {
580 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
581 }
582
583 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
584 if ((err = add_point(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; }
585 }
586 /* empty window and reset */
587 bitcpy = bitbuf = 0;
588 mode = 1;
589 }
590 }
591
592 /* if bits remain then double/add */
593 if (mode == 2 && bitcpy > 0) {
594 /* double then add */
595 for (j = 0; j < bitcpy; j++) {
596 /* only double if we have had at least one add first */
597 if (first == 0) {
598 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
599 }
600
601 bitbuf <<= 1;
602 if ((bitbuf & (1 << WINSIZE)) != 0) {
603 if (first == 1){
604 /* first add, so copy */
605 if ((err = mp_copy(&tG->x, &R->x)) != MP_OKAY) { goto error; }
606 if ((err = mp_copy(&tG->y, &R->y)) != MP_OKAY) { goto error; }
607 if ((err = mp_copy(&tG->z, &R->z)) != MP_OKAY) { goto error; }
608 first = 0;
609 } else {
610 /* then add */
611 if ((err = add_point(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; }
612 }
613 }
614 }
615 }
616
617 /* map R back from projective space */
618 if (map) {
619 err = ecc_map(R, modulus, mp);
620 } else {
621 err = CRYPT_OK;
622 }
623
624 goto done;
625 error:
626 err = mpi_to_ltc_error(err);
627 done:
628 del_point(tG);
629 for (i = 0; i < 8; i++) {
630 del_point(M[i]);
631 }
632 return err;
633 }
634
635 #undef WINSIZE
636
637 /**
638 Perform on the ECC system
639 @return CRYPT_OK if successful
640 */
641 int ecc_test(void)
642 {
643 mp_int modulus, order;
644 ecc_point *G, *GG;
645 int i, err, primality;
646
647 if ((err = mp_init_multi(&modulus, &order, NULL)) != MP_OKAY) {
648 return mpi_to_ltc_error(err);
649 }
650
651 G = new_point();
652 GG = new_point();
653 if (G == NULL || GG == NULL) {
654 mp_clear_multi(&modulus, &order, NULL);
655 del_point(G);
656 del_point(GG);
657 return CRYPT_MEM;
658 }
659
660 for (i = 0; sets[i].size; i++) {
661 #if 0
662 printf("Testing %d\n", sets[i].size);
663 #endif
664 if ((err = mp_read_radix(&modulus, (char *)sets[i].prime, 64)) != MP_OKAY) { goto error; }
665 if ((err = mp_read_radix(&order, (char *)sets[i].order, 64)) != MP_OKAY) { goto error; }
666
667 /* is prime actually prime? */
668 if ((err = is_prime(&modulus, &primality)) != CRYPT_OK) { goto done; }
669 if (primality == 0) {
670 err = CRYPT_FAIL_TESTVECTOR;
671 goto done;
672 }
673
674 /* is order prime ? */
675 if ((err = is_prime(&order, &primality)) != CRYPT_OK) { goto done; }
676 if (primality == 0) {
677 err = CRYPT_FAIL_TESTVECTOR;
678 goto done;
679 }
680
681 if ((err = mp_read_radix(&G->x, (char *)sets[i].Gx, 64)) != MP_OKAY) { goto error; }
682 if ((err = mp_read_radix(&G->y, (char *)sets[i].Gy, 64)) != MP_OKAY) { goto error; }
683 mp_set(&G->z, 1);
684
685 /* then we should have G == (order + 1)G */
686 if ((err = mp_add_d(&order, 1, &order)) != MP_OKAY) { goto error; }
687 if ((err = ecc_mulmod(&order, G, GG, &modulus, 1)) != CRYPT_OK) { goto done; }
688 if (mp_cmp(&G->x, &GG->x) != 0 || mp_cmp(&G->y, &GG->y) != 0) {
689 err = CRYPT_FAIL_TESTVECTOR;
690 goto done;
691 }
692 }
693 err = CRYPT_OK;
694 goto done;
695 error:
696 err = mpi_to_ltc_error(err);
697 done:
698 del_point(GG);
699 del_point(G);
700 mp_clear_multi(&order, &modulus, NULL);
701 return err;
702 }
703
704 void ecc_sizes(int *low, int *high)
705 {
706 int i;
707 LTC_ARGCHK(low != NULL);
708 LTC_ARGCHK(high != NULL);
709
710 *low = INT_MAX;
711 *high = 0;
712 for (i = 0; sets[i].size != 0; i++) {
713 if (sets[i].size < *low) {
714 *low = sets[i].size;
715 }
716 if (sets[i].size > *high) {
717 *high = sets[i].size;
718 }
719 }
720 }
721
722 /**
723 Make a new ECC key
724 @param prng An active PRNG state
725 @param wprng The index of the PRNG you wish to use
726 @param keysize The keysize for the new key (in octets from 20 to 65 bytes)
727 @param key [out] Destination of the newly created key
728 @return CRYPT_OK if successful, upon error all allocated memory will be freed
729 */
730 int ecc_make_key(prng_state *prng, int wprng, int keysize, ecc_key *key)
731 {
732 int x, err;
733 ecc_point *base;
734 mp_int prime;
735 unsigned char *buf;
736
737 LTC_ARGCHK(key != NULL);
738
739 /* good prng? */
740 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
741 return err;
742 }
743
744 /* find key size */
745 for (x = 0; (keysize > sets[x].size) && (sets[x].size != 0); x++);
746 keysize = sets[x].size;
747
748 if (keysize > ECC_MAXSIZE || sets[x].size == 0) {
749 return CRYPT_INVALID_KEYSIZE;
750 }
751 key->idx = x;
752
753 /* allocate ram */
754 base = NULL;
755 buf = XMALLOC(ECC_MAXSIZE);
756 if (buf == NULL) {
757 return CRYPT_MEM;
758 }
759
760 /* make up random string */
761 if (prng_descriptor[wprng].read(buf, (unsigned long)keysize, prng) != (unsigned long)keysize) {
762 err = CRYPT_ERROR_READPRNG;
763 goto LBL_ERR2;
764 }
765
766 /* setup the key variables */
767 if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, &prime, NULL)) != MP_OKAY) {
768 err = mpi_to_ltc_error(err);
769 goto LBL_ERR;
770 }
771 base = new_point();
772 if (base == NULL) {
773 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, &prime, NULL);
774 err = CRYPT_MEM;
775 goto LBL_ERR;
776 }
777
778 /* read in the specs for this key */
779 if ((err = mp_read_radix(&prime, (char *)sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
780 if ((err = mp_read_radix(&base->x, (char *)sets[key->idx].Gx, 64)) != MP_OKAY) { goto error; }
781 if ((err = mp_read_radix(&base->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY) { goto error; }
782 mp_set(&base->z, 1);
783 if ((err = mp_read_unsigned_bin(&key->k, (unsigned char *)buf, keysize)) != MP_OKAY) { goto error; }
784
785 /* make the public key */
786 if ((err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1)) != CRYPT_OK) { goto LBL_ERR; }
787 key->type = PK_PRIVATE;
788
789 /* shrink key */
790 if ((err = mp_shrink(&key->k)) != MP_OKAY) { goto error; }
791 if ((err = mp_shrink(&key->pubkey.x)) != MP_OKAY) { goto error; }
792 if ((err = mp_shrink(&key->pubkey.y)) != MP_OKAY) { goto error; }
793 if ((err = mp_shrink(&key->pubkey.z)) != MP_OKAY) { goto error; }
794
795 /* free up ram */
796 err = CRYPT_OK;
797 goto LBL_ERR;
798 error:
799 err = mpi_to_ltc_error(err);
800 LBL_ERR:
801 del_point(base);
802 mp_clear(&prime);
803 LBL_ERR2:
804 #ifdef LTC_CLEAN_STACK
805 zeromem(buf, ECC_MAXSIZE);
806 #endif
807
808 XFREE(buf);
809
810 return err;
811 }
812
813 /**
814 Free an ECC key from memory
815 @param key The key you wish to free
816 */
817 void ecc_free(ecc_key *key)
818 {
819 LTC_ARGCHK(key != NULL);
820 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL);
821 }
822
823 /**
824 Export an ECC key as a binary packet
825 @param out [out] Destination for the key
826 @param outlen [in/out] Max size and resulting size of the exported key
827 @param type The type of key you want to export (PK_PRIVATE or PK_PUBLIC)
828 @param key The key to export
829 @return CRYPT_OK if successful
830 */
831 int ecc_export(unsigned char *out, unsigned long *outlen, int type, ecc_key *key)
832 {
833 int err;
834 unsigned char flags[1];
835 unsigned long key_size;
836
837 LTC_ARGCHK(out != NULL);
838 LTC_ARGCHK(outlen != NULL);
839 LTC_ARGCHK(key != NULL);
840
841 /* type valid? */
842 if (key->type != PK_PRIVATE && type == PK_PRIVATE) {
843 return CRYPT_PK_TYPE_MISMATCH;
844 }
845
846 if (is_valid_idx(key->idx) == 0) {
847 return CRYPT_INVALID_ARG;
848 }
849
850 /* we store the NIST byte size */
851 key_size = sets[key->idx].size;
852
853 if (type == PK_PRIVATE) {
854 flags[0] = 1;
855 err = der_encode_sequence_multi(out, outlen,
856 LTC_ASN1_BIT_STRING, 1UL, flags,
857 LTC_ASN1_SHORT_INTEGER, 1UL, &key_size,
858 LTC_ASN1_INTEGER, 1UL, &key->pubkey.x,
859 LTC_ASN1_INTEGER, 1UL, &key->pubkey.y,
860 LTC_ASN1_INTEGER, 1UL, &key->k,
861 LTC_ASN1_EOL, 0UL, NULL);
862 } else {
863 flags[0] = 0;
864 err = der_encode_sequence_multi(out, outlen,
865 LTC_ASN1_BIT_STRING, 1UL, flags,
866 LTC_ASN1_SHORT_INTEGER, 1UL, &key_size,
867 LTC_ASN1_INTEGER, 1UL, &key->pubkey.x,
868 LTC_ASN1_INTEGER, 1UL, &key->pubkey.y,
869 LTC_ASN1_EOL, 0UL, NULL);
870 }
871
872 return err;
873 }
874
875 /**
876 Import an ECC key from a binary packet
877 @param in The packet to import
878 @param inlen The length of the packet
879 @param key [out] The destination of the import
880 @return CRYPT_OK if successful, upon error all allocated memory will be freed
881 */
882 int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key)
883 {
884 unsigned long key_size;
885 unsigned char flags[1];
886 int err;
887
888 LTC_ARGCHK(in != NULL);
889 LTC_ARGCHK(key != NULL);
890
891 /* init key */
892 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != MP_OKAY) {
893 return CRYPT_MEM;
894 }
895
896 /* find out what type of key it is */
897 if ((err = der_decode_sequence_multi(in, inlen,
898 LTC_ASN1_BIT_STRING, 1UL, &flags,
899 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
900 goto error;
901 }
902
903
904 if (flags[0] == 1) {
905 /* private key */
906 key->type = PK_PRIVATE;
907 if ((err = der_decode_sequence_multi(in, inlen,
908 LTC_ASN1_BIT_STRING, 1UL, flags,
909 LTC_ASN1_SHORT_INTEGER, 1UL, &key_size,
910 LTC_ASN1_INTEGER, 1UL, &key->pubkey.x,
911 LTC_ASN1_INTEGER, 1UL, &key->pubkey.y,
912 LTC_ASN1_INTEGER, 1UL, &key->k,
913 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
914 goto error;
915 }
916 } else {
917 /* public key */
918 /* private key */
919 key->type = PK_PUBLIC;
920 if ((err = der_decode_sequence_multi(in, inlen,
921 LTC_ASN1_BIT_STRING, 1UL, flags,
922 LTC_ASN1_SHORT_INTEGER, 1UL, &key_size,
923 LTC_ASN1_INTEGER, 1UL, &key->pubkey.x,
924 LTC_ASN1_INTEGER, 1UL, &key->pubkey.y,
925 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
926 goto error;
927 }
928 }
929
930 /* find the idx */
931 for (key->idx = 0; sets[key->idx].size && (unsigned long)sets[key->idx].size != key_size; ++key->idx);
932 if (sets[key->idx].size == 0) {
933 err = CRYPT_INVALID_PACKET;
934 goto error;
935 }
936
937 /* set z */
938 mp_set(&key->pubkey.z, 1);
939
940 /* we're good */
941 return CRYPT_OK;
942 error:
943 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL);
944 return err;
945 }
946
947 /**
948 Create an ECC shared secret between two keys
949 @param private_key The private ECC key
950 @param public_key The public key
951 @param out [out] Destination of the shared secret (Conforms to EC-DH from ANSI X9.63)
952 @param outlen [in/out] The max size and resulting size of the shared secret
953 @return CRYPT_OK if successful
954 */
955 int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
956 unsigned char *out, unsigned long *outlen)
957 {
958 unsigned long x;
959 ecc_point *result;
960 mp_int prime;
961 int err;
962
963 LTC_ARGCHK(private_key != NULL);
964 LTC_ARGCHK(public_key != NULL);
965 LTC_ARGCHK(out != NULL);
966 LTC_ARGCHK(outlen != NULL);
967
968 /* type valid? */
969 if (private_key->type != PK_PRIVATE) {
970 return CRYPT_PK_NOT_PRIVATE;
971 }
972
973 if (is_valid_idx(private_key->idx) == 0) {
974 return CRYPT_INVALID_ARG;
975 }
976
977 if (private_key->idx != public_key->idx) {
978 return CRYPT_PK_TYPE_MISMATCH;
979 }
980
981 /* make new point */
982 result = new_point();
983 if (result == NULL) {
984 return CRYPT_MEM;
985 }
986
987 if ((err = mp_init(&prime)) != MP_OKAY) {
988 del_point(result);
989 return mpi_to_ltc_error(err);
990 }
991
992 if ((err = mp_read_radix(&prime, (char *)sets[private_key->idx].prime, 64)) != MP_OKAY) { goto error; }
993 if ((err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime, 1)) != CRYPT_OK) { goto done1; }
994
995 x = (unsigned long)mp_unsigned_bin_size(&prime);
996 if (*outlen < x) {
997 err = CRYPT_BUFFER_OVERFLOW;
998 goto done1;
999 }
1000 zeromem(out, x);
1001 if ((err = mp_to_unsigned_bin(&result->x, out + (x - mp_unsigned_bin_size(&result->x)))) != MP_OKAY) { goto error; }
1002
1003 err = CRYPT_OK;
1004 *outlen = x;
1005 goto done1;
1006 error:
1007 err = mpi_to_ltc_error(err);
1008 done1:
1009 mp_clear(&prime);
1010 del_point(result);
1011 return err;
1012 }
1013
1014 /**
1015 Get the size of an ECC key
1016 @param key The key to get the size of
1017 @return The size (octets) of the key or INT_MAX on error
1018 */
1019 int ecc_get_size(ecc_key *key)
1020 {
1021 LTC_ARGCHK(key != NULL);
1022 if (is_valid_idx(key->idx))
1023 return sets[key->idx].size;
1024 else
1025 return INT_MAX; /* large value known to cause it to fail when passed to ecc_make_key() */
1026 }
1027
1028 #include "ecc_sys.c"
1029
1030 #endif
1031
1032
1033
1034 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc.c,v $ */
1035 /* $Revision: 1.20 $ */
1036 /* $Date: 2005/06/14 20:42:28 $ */