Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ecc.c @ 302:973fccb59ea4 ucc-axis-hack

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.dropbear' (head 11034278bd1917bebcbdc69cf53b1891ce9db121) to branch 'au.asn.ucc.matt.dropbear.ucc-axis-hack' (head 10a1f614fec73d0820c3f61160d9db409b9beb46)
author Matt Johnston <matt@ucc.asn.au>
date Sat, 25 Mar 2006 12:59:58 +0000
parents 1b9e69c058d2
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
299:740e782679be 302:973fccb59ea4
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 $ */