Mercurial > dropbear

comparison src/pk/ecc/ecc.c @ 209:39d5d58461d6 libtomcrypt-orig LTC_1.05

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import of libtomcrypt 1.05
author Matt Johnston <matt@ucc.asn.au>
date Wed, 06 Jul 2005 03:53:40 +0000
parents 1c15b283127b
children
comparison
equal deleted inserted replaced
191:1c15b283127b 209:39d5d58461d6
22 */ 22 */
23 23
24 #ifdef MECC 24 #ifdef MECC
25 25
26 /* size of our temp buffers for exported keys */ 26 /* size of our temp buffers for exported keys */
27 #define ECC_BUF_SIZE 160 27 #define ECC_BUF_SIZE 256
28 28
29 /* max private key size */ 29 /* max private key size */
30 #define ECC_MAXSIZE 66 30 #define ECC_MAXSIZE 66
31 31
32 /* This holds the key settings. ***MUST*** be organized by size from smallest to largest. */ 32 /* This holds the key settings. ***MUST*** be organized by size from smallest to largest. */
33 static const struct { 33 static const struct {
34 int size; 34 int size;
35 char *name, *prime, *B, *order, *Gx, *Gy; 35 char *name, *prime, *B, *order, *Gx, *Gy;
36 } sets[] = { 36 } sets[] = {
37 #ifdef ECC160
38 {
39 20,
40 "ECC-160",
41 /* prime */
42 "G00000000000000000000000007",
43 /* B */
44 "1oUV2vOaSlWbxr6",
45 /* order */
46 "G0000000000004sCQUtDxaqDUN5",
47 /* Gx */
48 "jpqOf1BHus6Yd/pyhyVpP",
49 /* Gy */
50 "D/wykuuIFfr+vPyx7kQEPu8MixO",
51 },
52 #endif
53 #ifdef ECC192 37 #ifdef ECC192
54 { 38 {
55 24, 39 24,
56 "ECC-192", 40 "ECC-192",
57 /* prime */ 41 /* prime */
74 { 58 {
75 28, 59 28,
76 "ECC-224", 60 "ECC-224",
77 61
78 /* prime */ 62 /* prime */
79 "400000000000000000000000000000000000BV", 63 "3/////////////////////0000000000000001",
80 64
81 /* B */ 65 /* B */
82 "21HkWGL2CxJIp", 66 "2q1Gg530Ipg/L1CbPGHB2trx/OkYSBEKCZLV+q",
83 67
84 /* order */ 68 /* order */
85 "4000000000000000000Kxnixk9t8MLzMiV264/", 69 "3//////////////////nQYuBZmFXFTAKLSN2ez",
86 70
87 /* Gx */ 71 /* Gx */
88 "jpqOf1BHus6Yd/pyhyVpP", 72 "2t3WozQxI/Vp8JaBbA0y7JLi8H8ZGoWDOHN1qX",
73
89 74
90 /* Gy */ 75 /* Gy */
91 "3FCtyo2yHA5SFjkCGbYxbOvNeChwS+j6wSIwck", 76 "2zDsE8jVSZ+qmYt+RDGtMWMWT7P4JLWPc507uq",
92 }, 77 },
93 #endif 78 #endif
94 #ifdef ECC256 79 #ifdef ECC256
95 { 80 {
96 32, 81 32,
163 0, 148 0,
164 NULL, NULL, NULL, NULL, NULL, NULL 149 NULL, NULL, NULL, NULL, NULL, NULL
165 } 150 }
166 }; 151 };
167 152
168 #if 0
169
170 /* you plug in a prime and B value and it finds a pseudo-random base point */
171 void ecc_find_base(void)
172 {
173 static char *prime = "26959946667150639794667015087019630673637144422540572481103610249951";
174 static char *order = "26959946667150639794667015087019637467111563745054605861463538557247";
175 static char *b = "9538957348957353489587";
176 mp_int pp, p, r, B, tmp1, tmp2, tx, ty, x, y;
177 char buf[4096];
178 int i;
179
180 mp_init_multi(&tx, &ty, &x, &y, &p, &pp, &r, &B, &tmp1, &tmp2, NULL);
181 mp_read_radix(&p, prime, 10);
182 mp_read_radix(&r, order, 10);
183 mp_read_radix(&B, b, 10);
184
185 /* get (p+1)/4 */
186 mp_add_d(&p, 1, &pp);
187 mp_div_2(&pp, &pp);
188 mp_div_2(&pp, &pp);
189
190 buf[0] = 0;
191 do {
192 printf("."); fflush(stdout);
193 /* make a random value of x */
194 for (i = 0; i < 16; i++) buf[i+1] = rand() & 255;
195 mp_read_raw(&x, buf, 17);
196 mp_copy(&x, &tx);
197
198 /* now compute x^3 - 3x + b */
199 mp_expt_d(&x, 3, &tmp1);
200 mp_mul_d(&x, 3, &tmp2);
201 mp_sub(&tmp1, &tmp2, &tmp1);
202 mp_add(&tmp1, &B, &tmp1);
203 mp_mod(&tmp1, &p, &tmp1);
204
205 /* now compute sqrt via x^((p+1)/4) */
206 mp_exptmod(&tmp1, &pp, &p, &tmp2);
207 mp_copy(&tmp2, &ty);
208
209 /* now square it */
210 mp_sqrmod(&tmp2, &p, &tmp2);
211
212 /* tmp2 should equal tmp1 */
213 } while (mp_cmp(&tmp1, &tmp2));
214
215 /* now output values in way that libtomcrypt wants */
216 mp_todecimal(&p, buf);
217 printf("\n\np==%s\n", buf);
218 mp_tohex(&B, buf);
219 printf("b==%s\n", buf);
220 mp_todecimal(&r, buf);
221 printf("r==%s\n", buf);
222 mp_tohex(&tx, buf);
223 printf("Gx==%s\n", buf);
224 mp_tohex(&ty, buf);
225 printf("Gy==%s\n", buf);
226
227 mp_clear_multi(&tx, &ty, &x, &y, &p, &pp, &r, &B, &tmp1, &tmp2, NULL);
228 }
229
230 #endif
231
232 static int is_valid_idx(int n) 153 static int is_valid_idx(int n)
233 { 154 {
234 int x; 155 int x;
235 156
236 for (x = 0; sets[x].size != 0; x++); 157 for (x = 0; sets[x].size != 0; x++);
261 mp_clear_multi(&p->x, &p->y, &p->z, NULL); 182 mp_clear_multi(&p->x, &p->y, &p->z, NULL);
262 XFREE(p); 183 XFREE(p);
263 } 184 }
264 } 185 }
265 186
266 static int ecc_map(ecc_point *P, mp_int *modulus, mp_int *mu) 187 static int ecc_map(ecc_point *P, mp_int *modulus, mp_digit mp)
267 { 188 {
268 mp_int t1, t2; 189 mp_int t1, t2;
269 int err; 190 int err;
270 191
271 if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) { 192 if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) {
272 return CRYPT_MEM; 193 return CRYPT_MEM;
273 } 194 }
274 195
196 /* first map z back to normal */
197 if ((err = mp_montgomery_reduce(&P->z, modulus, mp)) != MP_OKAY) { goto error; }
198
275 /* get 1/z */ 199 /* get 1/z */
276 if ((err = mp_invmod(&P->z, modulus, &t1)) != MP_OKAY) { goto error; } 200 if ((err = mp_invmod(&P->z, modulus, &t1)) != MP_OKAY) { goto error; }
277 201
278 /* get 1/z^2 and 1/z^3 */ 202 /* get 1/z^2 and 1/z^3 */
279 if ((err = mp_sqr(&t1, &t2)) != MP_OKAY) { goto error; } 203 if ((err = mp_sqr(&t1, &t2)) != MP_OKAY) { goto error; }
280 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 204 if ((err = mp_mod(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
281 if ((err = mp_mul(&t1, &t2, &t1)) != MP_OKAY) { goto error; } 205 if ((err = mp_mul(&t1, &t2, &t1)) != MP_OKAY) { goto error; }
282 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 206 if ((err = mp_mod(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
283 207
284 /* multiply against x/y */ 208 /* multiply against x/y */
285 if ((err = mp_mul(&P->x, &t2, &P->x)) != MP_OKAY) { goto error; } 209 if ((err = mp_mul(&P->x, &t2, &P->x)) != MP_OKAY) { goto error; }
286 if ((err = mp_reduce(&P->x, modulus, mu)) != MP_OKAY) { goto error; } 210 if ((err = mp_montgomery_reduce(&P->x, modulus, mp)) != MP_OKAY) { goto error; }
287 if ((err = mp_mul(&P->y, &t1, &P->y)) != MP_OKAY) { goto error; } 211 if ((err = mp_mul(&P->y, &t1, &P->y)) != MP_OKAY) { goto error; }
288 if ((err = mp_reduce(&P->y, modulus, mu)) != MP_OKAY) { goto error; } 212 if ((err = mp_montgomery_reduce(&P->y, modulus, mp)) != MP_OKAY) { goto error; }
289 mp_set(&P->z, 1); 213 mp_set(&P->z, 1);
290 214
291 err = CRYPT_OK; 215 err = CRYPT_OK;
292 goto done; 216 goto done;
293 error: 217 error:
296 mp_clear_multi(&t1, &t2, NULL); 220 mp_clear_multi(&t1, &t2, NULL);
297 return err; 221 return err;
298 222
299 } 223 }
300 224
301
302 /* double a point R = 2P, R can be P*/ 225 /* double a point R = 2P, R can be P*/
303 static int dbl_point(ecc_point *P, ecc_point *R, mp_int *modulus, mp_int *mu) 226 static int dbl_point(ecc_point *P, ecc_point *R, mp_int *modulus, mp_digit mp)
304 { 227 {
305 mp_int t1, t2; 228 mp_int t1, t2;
306 int err; 229 int err;
307 230
308 if ((err = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) { 231 if ((err = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
313 if ((err = mp_copy(&P->y, &R->y)) != MP_OKAY) { goto error; } 236 if ((err = mp_copy(&P->y, &R->y)) != MP_OKAY) { goto error; }
314 if ((err = mp_copy(&P->z, &R->z)) != MP_OKAY) { goto error; } 237 if ((err = mp_copy(&P->z, &R->z)) != MP_OKAY) { goto error; }
315 238
316 /* t1 = Z * Z */ 239 /* t1 = Z * Z */
317 if ((err = mp_sqr(&R->z, &t1)) != MP_OKAY) { goto error; } 240 if ((err = mp_sqr(&R->z, &t1)) != MP_OKAY) { goto error; }
318 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 241 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
319 /* Z = Y * Z */ 242 /* Z = Y * Z */
320 if ((err = mp_mul(&R->z, &R->y, &R->z)) != MP_OKAY) { goto error; } 243 if ((err = mp_mul(&R->z, &R->y, &R->z)) != MP_OKAY) { goto error; }
321 if ((err = mp_reduce(&R->z, modulus, mu)) != MP_OKAY) { goto error; } 244 if ((err = mp_montgomery_reduce(&R->z, modulus, mp)) != MP_OKAY) { goto error; }
322 /* Z = 2Z */ 245 /* Z = 2Z */
323 if ((err = mp_mul_2(&R->z, &R->z)) != MP_OKAY) { goto error; } 246 if ((err = mp_mul_2(&R->z, &R->z)) != MP_OKAY) { goto error; }
324 if (mp_cmp(&R->z, modulus) != MP_LT) { 247 if (mp_cmp(&R->z, modulus) != MP_LT) {
325 if ((err = mp_sub(&R->z, modulus, &R->z)) != MP_OKAY) { goto error; } 248 if ((err = mp_sub(&R->z, modulus, &R->z)) != MP_OKAY) { goto error; }
326 } 249 }
335 if (mp_cmp(&t1, modulus) != MP_LT) { 258 if (mp_cmp(&t1, modulus) != MP_LT) {
336 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; } 259 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
337 } 260 }
338 /* T2 = T1 * T2 */ 261 /* T2 = T1 * T2 */
339 if ((err = mp_mul(&t1, &t2, &t2)) != MP_OKAY) { goto error; } 262 if ((err = mp_mul(&t1, &t2, &t2)) != MP_OKAY) { goto error; }
340 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 263 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
341 /* T1 = 2T2 */ 264 /* T1 = 2T2 */
342 if ((err = mp_mul_2(&t2, &t1)) != MP_OKAY) { goto error; } 265 if ((err = mp_mul_2(&t2, &t1)) != MP_OKAY) { goto error; }
343 if (mp_cmp(&t1, modulus) != MP_LT) { 266 if (mp_cmp(&t1, modulus) != MP_LT) {
344 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; } 267 if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY) { goto error; }
345 } 268 }
354 if (mp_cmp(&R->y, modulus) != MP_LT) { 277 if (mp_cmp(&R->y, modulus) != MP_LT) {
355 if ((err = mp_sub(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; } 278 if ((err = mp_sub(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
356 } 279 }
357 /* Y = Y * Y */ 280 /* Y = Y * Y */
358 if ((err = mp_sqr(&R->y, &R->y)) != MP_OKAY) { goto error; } 281 if ((err = mp_sqr(&R->y, &R->y)) != MP_OKAY) { goto error; }
359 if ((err = mp_reduce(&R->y, modulus, mu)) != MP_OKAY) { goto error; } 282 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
360 /* T2 = Y * Y */ 283 /* T2 = Y * Y */
361 if ((err = mp_sqr(&R->y, &t2)) != MP_OKAY) { goto error; } 284 if ((err = mp_sqr(&R->y, &t2)) != MP_OKAY) { goto error; }
362 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 285 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
363 /* T2 = T2/2 */ 286 /* T2 = T2/2 */
364 if (mp_isodd(&t2)) { 287 if (mp_isodd(&t2)) {
365 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; } 288 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
366 } 289 }
367 if ((err = mp_div_2(&t2, &t2)) != MP_OKAY) { goto error; } 290 if ((err = mp_div_2(&t2, &t2)) != MP_OKAY) { goto error; }
368 /* Y = Y * X */ 291 /* Y = Y * X */
369 if ((err = mp_mul(&R->y, &R->x, &R->y)) != MP_OKAY) { goto error; } 292 if ((err = mp_mul(&R->y, &R->x, &R->y)) != MP_OKAY) { goto error; }
370 if ((err = mp_reduce(&R->y, modulus, mu)) != MP_OKAY) { goto error; } 293 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
371 294
372 /* X = T1 * T1 */ 295 /* X = T1 * T1 */
373 if ((err = mp_sqr(&t1, &R->x)) != MP_OKAY) { goto error; } 296 if ((err = mp_sqr(&t1, &R->x)) != MP_OKAY) { goto error; }
374 if ((err = mp_reduce(&R->x, modulus, mu)) != MP_OKAY) { goto error; } 297 if ((err = mp_montgomery_reduce(&R->x, modulus, mp)) != MP_OKAY) { goto error; }
375 /* X = X - Y */ 298 /* X = X - Y */
376 if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY) { goto error; } 299 if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY) { goto error; }
377 if (mp_cmp_d(&R->x, 0) == MP_LT) { 300 if (mp_cmp_d(&R->x, 0) == MP_LT) {
378 if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY) { goto error; } 301 if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY) { goto error; }
379 } 302 }
388 if (mp_cmp_d(&R->y, 0) == MP_LT) { 311 if (mp_cmp_d(&R->y, 0) == MP_LT) {
389 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; } 312 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
390 } 313 }
391 /* Y = Y * T1 */ 314 /* Y = Y * T1 */
392 if ((err = mp_mul(&R->y, &t1, &R->y)) != MP_OKAY) { goto error; } 315 if ((err = mp_mul(&R->y, &t1, &R->y)) != MP_OKAY) { goto error; }
393 if ((err = mp_reduce(&R->y, modulus, mu)) != MP_OKAY) { goto error; } 316 if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY) { goto error; }
394 /* Y = Y - T2 */ 317 /* Y = Y - T2 */
395 if ((err = mp_sub(&R->y, &t2, &R->y)) != MP_OKAY) { goto error; } 318 if ((err = mp_sub(&R->y, &t2, &R->y)) != MP_OKAY) { goto error; }
396 if (mp_cmp_d(&R->y, 0) == MP_LT) { 319 if (mp_cmp_d(&R->y, 0) == MP_LT) {
397 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; } 320 if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY) { goto error; }
398 } 321 }
405 mp_clear_multi(&t1, &t2, NULL); 328 mp_clear_multi(&t1, &t2, NULL);
406 return err; 329 return err;
407 } 330 }
408 331
409 /* add two different points over Z/pZ, R = P + Q, note R can equal either P or Q */ 332 /* add two different points over Z/pZ, R = P + Q, note R can equal either P or Q */
410 static int add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mp_int *modulus, mp_int *mu) 333 static int add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mp_int *modulus, mp_digit mp)
411 { 334 {
412 mp_int t1, t2, x, y, z; 335 mp_int t1, t2, x, y, z;
413 int err; 336 int err;
414 337
415 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) { 338 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
418 341
419 if ((err = mp_copy(&P->x, &x)) != MP_OKAY) { goto error; } 342 if ((err = mp_copy(&P->x, &x)) != MP_OKAY) { goto error; }
420 if ((err = mp_copy(&P->y, &y)) != MP_OKAY) { goto error; } 343 if ((err = mp_copy(&P->y, &y)) != MP_OKAY) { goto error; }
421 if ((err = mp_copy(&P->z, &z)) != MP_OKAY) { goto error; } 344 if ((err = mp_copy(&P->z, &z)) != MP_OKAY) { goto error; }
422 345
423 /* if Z' != 1 */
424 if (mp_cmp_d(&Q->z, 1) != MP_EQ) {
425 /* T1 = Z' * Z' */ 346 /* T1 = Z' * Z' */
426 if ((err = mp_sqr(&Q->z, &t1)) != MP_OKAY) { goto error; } 347 if ((err = mp_sqr(&Q->z, &t1)) != MP_OKAY) { goto error; }
427 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 348 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
428 /* X = X * T1 */ 349 /* X = X * T1 */
429 if ((err = mp_mul(&t1, &x, &x)) != MP_OKAY) { goto error; } 350 if ((err = mp_mul(&t1, &x, &x)) != MP_OKAY) { goto error; }
430 if ((err = mp_reduce(&x, modulus, mu)) != MP_OKAY) { goto error; } 351 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
431 /* T1 = Z' * T1 */ 352 /* T1 = Z' * T1 */
432 if ((err = mp_mul(&Q->z, &t1, &t1)) != MP_OKAY) { goto error; } 353 if ((err = mp_mul(&Q->z, &t1, &t1)) != MP_OKAY) { goto error; }
433 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 354 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
434 /* Y = Y * T1 */ 355 /* Y = Y * T1 */
435 if ((err = mp_mul(&t1, &y, &y)) != MP_OKAY) { goto error; } 356 if ((err = mp_mul(&t1, &y, &y)) != MP_OKAY) { goto error; }
436 if ((err = mp_reduce(&y, modulus, mu)) != MP_OKAY) { goto error; } 357 if ((err = mp_montgomery_reduce(&y, modulus, mp)) != MP_OKAY) { goto error; }
437 }
438 358
439 /* T1 = Z*Z */ 359 /* T1 = Z*Z */
440 if ((err = mp_sqr(&z, &t1)) != MP_OKAY) { goto error; } 360 if ((err = mp_sqr(&z, &t1)) != MP_OKAY) { goto error; }
441 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 361 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
442 /* T2 = X' * T1 */ 362 /* T2 = X' * T1 */
443 if ((err = mp_mul(&Q->x, &t1, &t2)) != MP_OKAY) { goto error; } 363 if ((err = mp_mul(&Q->x, &t1, &t2)) != MP_OKAY) { goto error; }
444 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 364 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
445 /* T1 = Z * T1 */ 365 /* T1 = Z * T1 */
446 if ((err = mp_mul(&z, &t1, &t1)) != MP_OKAY) { goto error; } 366 if ((err = mp_mul(&z, &t1, &t1)) != MP_OKAY) { goto error; }
447 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 367 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
448 /* T1 = Y' * T1 */ 368 /* T1 = Y' * T1 */
449 if ((err = mp_mul(&Q->y, &t1, &t1)) != MP_OKAY) { goto error; } 369 if ((err = mp_mul(&Q->y, &t1, &t1)) != MP_OKAY) { goto error; }
450 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 370 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
451 371
452 /* Y = Y - T1 */ 372 /* Y = Y - T1 */
453 if ((err = mp_sub(&y, &t1, &y)) != MP_OKAY) { goto error; } 373 if ((err = mp_sub(&y, &t1, &y)) != MP_OKAY) { goto error; }
454 if (mp_cmp_d(&y, 0) == MP_LT) { 374 if (mp_cmp_d(&y, 0) == MP_LT) {
455 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; } 375 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; }
482 402
483 /* if Z' != 1 */ 403 /* if Z' != 1 */
484 if (mp_cmp_d(&Q->z, 1) != MP_EQ) { 404 if (mp_cmp_d(&Q->z, 1) != MP_EQ) {
485 /* Z = Z * Z' */ 405 /* Z = Z * Z' */
486 if ((err = mp_mul(&z, &Q->z, &z)) != MP_OKAY) { goto error; } 406 if ((err = mp_mul(&z, &Q->z, &z)) != MP_OKAY) { goto error; }
487 if ((err = mp_reduce(&z, modulus, mu)) != MP_OKAY) { goto error; } 407 if ((err = mp_montgomery_reduce(&z, modulus, mp)) != MP_OKAY) { goto error; }
488 } 408 }
489 /* Z = Z * X */ 409 /* Z = Z * X */
490 if ((err = mp_mul(&z, &x, &z)) != MP_OKAY) { goto error; } 410 if ((err = mp_mul(&z, &x, &z)) != MP_OKAY) { goto error; }
491 if ((err = mp_reduce(&z, modulus, mu)) != MP_OKAY) { goto error; } 411 if ((err = mp_montgomery_reduce(&z, modulus, mp)) != MP_OKAY) { goto error; }
492 412
493 /* T1 = T1 * X */ 413 /* T1 = T1 * X */
494 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; } 414 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; }
495 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 415 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
496 /* X = X * X */ 416 /* X = X * X */
497 if ((err = mp_sqr(&x, &x)) != MP_OKAY) { goto error; } 417 if ((err = mp_sqr(&x, &x)) != MP_OKAY) { goto error; }
498 if ((err = mp_reduce(&x, modulus, mu)) != MP_OKAY) { goto error; } 418 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
499 /* T2 = T2 * x */ 419 /* T2 = T2 * x */
500 if ((err = mp_mul(&t2, &x, &t2)) != MP_OKAY) { goto error; } 420 if ((err = mp_mul(&t2, &x, &t2)) != MP_OKAY) { goto error; }
501 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 421 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
502 /* T1 = T1 * X */ 422 /* T1 = T1 * X */
503 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; } 423 if ((err = mp_mul(&t1, &x, &t1)) != MP_OKAY) { goto error; }
504 if ((err = mp_reduce(&t1, modulus, mu)) != MP_OKAY) { goto error; } 424 if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY) { goto error; }
505 425
506 /* X = Y*Y */ 426 /* X = Y*Y */
507 if ((err = mp_sqr(&y, &x)) != MP_OKAY) { goto error; } 427 if ((err = mp_sqr(&y, &x)) != MP_OKAY) { goto error; }
508 if ((err = mp_reduce(&x, modulus, mu)) != MP_OKAY) { goto error; } 428 if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY) { goto error; }
509 /* X = X - T2 */ 429 /* X = X - T2 */
510 if ((err = mp_sub(&x, &t2, &x)) != MP_OKAY) { goto error; } 430 if ((err = mp_sub(&x, &t2, &x)) != MP_OKAY) { goto error; }
511 if (mp_cmp_d(&x, 0) == MP_LT) { 431 if (mp_cmp_d(&x, 0) == MP_LT) {
512 if ((err = mp_add(&x, modulus, &x)) != MP_OKAY) { goto error; } 432 if ((err = mp_add(&x, modulus, &x)) != MP_OKAY) { goto error; }
513 } 433 }
522 if (mp_cmp_d(&t2, 0) == MP_LT) { 442 if (mp_cmp_d(&t2, 0) == MP_LT) {
523 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; } 443 if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY) { goto error; }
524 } 444 }
525 /* T2 = T2 * Y */ 445 /* T2 = T2 * Y */
526 if ((err = mp_mul(&t2, &y, &t2)) != MP_OKAY) { goto error; } 446 if ((err = mp_mul(&t2, &y, &t2)) != MP_OKAY) { goto error; }
527 if ((err = mp_reduce(&t2, modulus, mu)) != MP_OKAY) { goto error; } 447 if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY) { goto error; }
528 /* Y = T2 - T1 */ 448 /* Y = T2 - T1 */
529 if ((err = mp_sub(&t2, &t1, &y)) != MP_OKAY) { goto error; } 449 if ((err = mp_sub(&t2, &t1, &y)) != MP_OKAY) { goto error; }
530 if (mp_cmp_d(&y, 0) == MP_LT) { 450 if (mp_cmp_d(&y, 0) == MP_LT) {
531 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; } 451 if ((err = mp_add(&y, modulus, &y)) != MP_OKAY) { goto error; }
532 } 452 }
551 471
552 /* size of sliding window, don't change this! */ 472 /* size of sliding window, don't change this! */
553 #define WINSIZE 4 473 #define WINSIZE 4
554 474
555 /* perform R = kG where k == integer and G == ecc_point */ 475 /* perform R = kG where k == integer and G == ecc_point */
556 static int ecc_mulmod(mp_int *k, ecc_point *G, ecc_point *R, mp_int *modulus) 476 static int ecc_mulmod(mp_int *k, ecc_point *G, ecc_point *R, mp_int *modulus, int map)
557 { 477 {
558 ecc_point *tG, *M[8]; 478 ecc_point *tG, *M[8];
559 int i, j, err; 479 int i, j, err;
560 mp_int mu; 480 mp_int mu;
561 mp_digit buf; 481 mp_digit buf, mp;
562 int first, bitbuf, bitcpy, bitcnt, mode, digidx; 482 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
563 483
564 /* init barrett reduction */ 484 /* init montgomery reduction */
565 if ((err = mp_init(&mu)) != MP_OKAY) { 485 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
566 return mpi_to_ltc_error(err); 486 return CRYPT_INVALID_ARG;
567 } 487 }
568 if ((err = mp_reduce_setup(&mu, modulus)) != MP_OKAY) { 488 if ((err = mp_init(&mu)) != MP_OKAY) {
489 return CRYPT_MEM;
490 }
491 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
569 mp_clear(&mu); 492 mp_clear(&mu);
570 return mpi_to_ltc_error(err); 493 return CRYPT_INVALID_ARG;
571 } 494 }
572 495
573 /* alloc ram for window temps */ 496 /* alloc ram for window temps */
574 for (i = 0; i < 8; i++) { 497 for (i = 0; i < 8; i++) {
575 M[i] = new_point(); 498 M[i] = new_point();
576 if (M[i] == NULL) { 499 if (M[i] == NULL) {
584 507
585 /* make a copy of G incase R==G */ 508 /* make a copy of G incase R==G */
586 tG = new_point(); 509 tG = new_point();
587 if (tG == NULL) { err = CRYPT_MEM; goto done; } 510 if (tG == NULL) { err = CRYPT_MEM; goto done; }
588 511
589 /* tG = G */ 512 /* tG = G and convert to montgomery */
590 if ((err = mp_copy(&G->x, &tG->x)) != MP_OKAY) { goto error; } 513 if ((err = mp_mulmod(&G->x, &mu, modulus, &tG->x)) != MP_OKAY) { goto error; }
591 if ((err = mp_copy(&G->y, &tG->y)) != MP_OKAY) { goto error; } 514 if ((err = mp_mulmod(&G->y, &mu, modulus, &tG->y)) != MP_OKAY) { goto error; }
592 if ((err = mp_copy(&G->z, &tG->z)) != MP_OKAY) { goto error; } 515 if ((err = mp_mulmod(&G->z, &mu, modulus, &tG->z)) != MP_OKAY) { goto error; }
516 mp_clear(&mu);
593 517
594 /* calc the M tab, which holds kG for k==8..15 */ 518 /* calc the M tab, which holds kG for k==8..15 */
595 /* M[0] == 8G */ 519 /* M[0] == 8G */
596 if ((err = dbl_point(G, M[0], modulus, &mu)) != CRYPT_OK) { goto done; } 520 if ((err = dbl_point(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; }
597 if ((err = dbl_point(M[0], M[0], modulus, &mu)) != CRYPT_OK) { goto done; } 521 if ((err = dbl_point(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
598 if ((err = dbl_point(M[0], M[0], modulus, &mu)) != CRYPT_OK) { goto done; } 522 if ((err = dbl_point(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
599 523
600 /* now find (8+k)G for k=1..7 */ 524 /* now find (8+k)G for k=1..7 */
601 for (j = 9; j < 16; j++) { 525 for (j = 9; j < 16; j++) {
602 if ((err = add_point(M[j-9], G, M[j-8], modulus, &mu)) != CRYPT_OK) { goto done; } 526 if ((err = add_point(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; }
603 } 527 }
604 528
605 /* setup sliding window */ 529 /* setup sliding window */
606 mode = 0; 530 mode = 0;
607 bitcnt = 1; 531 bitcnt = 1;
619 } 543 }
620 buf = k->dp[digidx--]; 544 buf = k->dp[digidx--];
621 bitcnt = (int) DIGIT_BIT; 545 bitcnt = (int) DIGIT_BIT;
622 } 546 }
623 547
624 /* grab the next msb from the multiplicand */ 548 /* grab the next msb from the ltiplicand */
625 i = (buf >> (DIGIT_BIT - 1)) & 1; 549 i = (buf >> (DIGIT_BIT - 1)) & 1;
626 buf <<= 1; 550 buf <<= 1;
627 551
628 /* skip leading zero bits */ 552 /* skip leading zero bits */
629 if (mode == 0 && i == 0) { 553 if (mode == 0 && i == 0) {
630 continue; 554 continue;
631 } 555 }
632 556
633 /* if the bit is zero and mode == 1 then we double */ 557 /* if the bit is zero and mode == 1 then we double */
634 if (mode == 1 && i == 0) { 558 if (mode == 1 && i == 0) {
635 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; } 559 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
636 continue; 560 continue;
637 } 561 }
638 562
639 /* else we add it to the window */ 563 /* else we add it to the window */
640 bitbuf |= (i << (WINSIZE - ++bitcpy)); 564 bitbuf |= (i << (WINSIZE - ++bitcpy));
651 } else { 575 } else {
652 /* normal window */ 576 /* normal window */
653 /* ok window is filled so double as required and add */ 577 /* ok window is filled so double as required and add */
654 /* double first */ 578 /* double first */
655 for (j = 0; j < WINSIZE; j++) { 579 for (j = 0; j < WINSIZE; j++) {
656 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; } 580 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
657 } 581 }
658 582
659 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */ 583 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
660 if ((err = add_point(R, M[bitbuf-8], R, modulus, &mu)) != CRYPT_OK) { goto done; } 584 if ((err = add_point(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; }
661 } 585 }
662 /* empty window and reset */ 586 /* empty window and reset */
663 bitcpy = bitbuf = 0; 587 bitcpy = bitbuf = 0;
664 mode = 1; 588 mode = 1;
665 } 589 }
669 if (mode == 2 && bitcpy > 0) { 593 if (mode == 2 && bitcpy > 0) {
670 /* double then add */ 594 /* double then add */
671 for (j = 0; j < bitcpy; j++) { 595 for (j = 0; j < bitcpy; j++) {
672 /* only double if we have had at least one add first */ 596 /* only double if we have had at least one add first */
673 if (first == 0) { 597 if (first == 0) {
674 if ((err = dbl_point(R, R, modulus, &mu)) != CRYPT_OK) { goto done; } 598 if ((err = dbl_point(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
675 } 599 }
676 600
677 bitbuf <<= 1; 601 bitbuf <<= 1;
678 if ((bitbuf & (1 << WINSIZE)) != 0) { 602 if ((bitbuf & (1 << WINSIZE)) != 0) {
679 if (first == 1){ 603 if (first == 1){
682 if ((err = mp_copy(&tG->y, &R->y)) != MP_OKAY) { goto error; } 606 if ((err = mp_copy(&tG->y, &R->y)) != MP_OKAY) { goto error; }
683 if ((err = mp_copy(&tG->z, &R->z)) != MP_OKAY) { goto error; } 607 if ((err = mp_copy(&tG->z, &R->z)) != MP_OKAY) { goto error; }
684 first = 0; 608 first = 0;
685 } else { 609 } else {
686 /* then add */ 610 /* then add */
687 if ((err = add_point(R, tG, R, modulus, &mu)) != CRYPT_OK) { goto done; } 611 if ((err = add_point(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; }
688 } 612 }
689 } 613 }
690 } 614 }
691 } 615 }
692 616
693 /* map R back from projective space */ 617 /* map R back from projective space */
694 err = ecc_map(R, modulus, &mu); 618 if (map) {
619 err = ecc_map(R, modulus, mp);
620 } else {
621 err = CRYPT_OK;
622 }
623
695 goto done; 624 goto done;
696 error: 625 error:
697 err = mpi_to_ltc_error(err); 626 err = mpi_to_ltc_error(err);
698 done: 627 done:
699 del_point(tG); 628 del_point(tG);
700 for (i = 0; i < 8; i++) { 629 for (i = 0; i < 8; i++) {
701 del_point(M[i]); 630 del_point(M[i]);
702 } 631 }
703 mp_clear(&mu);
704 return err; 632 return err;
705 } 633 }
706 634
707 #undef WINSIZE 635 #undef WINSIZE
708 636
754 if ((err = mp_read_radix(&G->y, (char *)sets[i].Gy, 64)) != MP_OKAY) { goto error; } 682 if ((err = mp_read_radix(&G->y, (char *)sets[i].Gy, 64)) != MP_OKAY) { goto error; }
755 mp_set(&G->z, 1); 683 mp_set(&G->z, 1);
756 684
757 /* then we should have G == (order + 1)G */ 685 /* then we should have G == (order + 1)G */
758 if ((err = mp_add_d(&order, 1, &order)) != MP_OKAY) { goto error; } 686 if ((err = mp_add_d(&order, 1, &order)) != MP_OKAY) { goto error; }
759 if ((err = ecc_mulmod(&order, G, GG, &modulus)) != CRYPT_OK) { goto done; } 687 if ((err = ecc_mulmod(&order, G, GG, &modulus, 1)) != CRYPT_OK) { goto done; }
760 if (mp_cmp(&G->x, &GG->x) != 0 || mp_cmp(&G->y, &GG->y) != 0) { 688 if (mp_cmp(&G->x, &GG->x) != 0 || mp_cmp(&G->y, &GG->y) != 0) {
761 err = CRYPT_FAIL_TESTVECTOR; 689 err = CRYPT_FAIL_TESTVECTOR;
762 goto done; 690 goto done;
763 } 691 }
764 } 692 }
853 if ((err = mp_read_radix(&base->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY) { goto error; } 781 if ((err = mp_read_radix(&base->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY) { goto error; }
854 mp_set(&base->z, 1); 782 mp_set(&base->z, 1);
855 if ((err = mp_read_unsigned_bin(&key->k, (unsigned char *)buf, keysize)) != MP_OKAY) { goto error; } 783 if ((err = mp_read_unsigned_bin(&key->k, (unsigned char *)buf, keysize)) != MP_OKAY) { goto error; }
856 784
857 /* make the public key */ 785 /* make the public key */
858 if ((err = ecc_mulmod(&key->k, base, &key->pubkey, &prime)) != CRYPT_OK) { goto LBL_ERR; } 786 if ((err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1)) != CRYPT_OK) { goto LBL_ERR; }
859 key->type = PK_PRIVATE; 787 key->type = PK_PRIVATE;
860 788
861 /* shrink key */ 789 /* shrink key */
862 if ((err = mp_shrink(&key->k)) != MP_OKAY) { goto error; } 790 if ((err = mp_shrink(&key->k)) != MP_OKAY) { goto error; }
863 if ((err = mp_shrink(&key->pubkey.x)) != MP_OKAY) { goto error; } 791 if ((err = mp_shrink(&key->pubkey.x)) != MP_OKAY) { goto error; }
890 { 818 {
891 LTC_ARGCHK(key != NULL); 819 LTC_ARGCHK(key != NULL);
892 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL); 820 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL);
893 } 821 }
894 822
895 static int compress_y_point(ecc_point *pt, int idx, int *result)
896 {
897 mp_int tmp, tmp2, p;
898 int err;
899
900 LTC_ARGCHK(pt != NULL);
901 LTC_ARGCHK(result != NULL);
902
903 if ((err = mp_init_multi(&tmp, &tmp2, &p, NULL)) != MP_OKAY) {
904 return mpi_to_ltc_error(err);
905 }
906
907 /* get x^3 - 3x + b */
908 if ((err = mp_read_radix(&p, (char *)sets[idx].B, 64)) != MP_OKAY) { goto error; } /* p = B */
909 if ((err = mp_expt_d(&pt->x, 3, &tmp)) != MP_OKAY) { goto error; } /* tmp = pX^3 */
910 if ((err = mp_mul_d(&pt->x, 3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = 3*pX^3 */
911 if ((err = mp_sub(&tmp, &tmp2, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp - tmp2 */
912 if ((err = mp_add(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp + p */
913 if ((err = mp_read_radix(&p, (char *)sets[idx].prime, 64)) != MP_OKAY) { goto error; } /* p = prime */
914 if ((err = mp_mod(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp mod p */
915
916 /* now find square root */
917 if ((err = mp_add_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p + 1 */
918 if ((err = mp_div_2d(&tmp2, 2, &tmp2, NULL)) != MP_OKAY) { goto error; } /* tmp2 = (p+1)/4 */
919 if ((err = mp_exptmod(&tmp, &tmp2, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = (x^3 - 3x + b)^((p+1)/4) mod p */
920
921 /* if tmp equals the y point give a 0, otherwise 1 */
922 if (mp_cmp(&tmp, &pt->y) == 0) {
923 *result = 0;
924 } else {
925 *result = 1;
926 }
927
928 err = CRYPT_OK;
929 goto done;
930 error:
931 err = mpi_to_ltc_error(err);
932 done:
933 mp_clear_multi(&p, &tmp, &tmp2, NULL);
934 return err;
935 }
936
937 static int expand_y_point(ecc_point *pt, int idx, int result)
938 {
939 mp_int tmp, tmp2, p;
940 int err;
941
942 LTC_ARGCHK(pt != NULL);
943
944 if ((err = mp_init_multi(&tmp, &tmp2, &p, NULL)) != MP_OKAY) {
945 return CRYPT_MEM;
946 }
947
948 /* get x^3 - 3x + b */
949 if ((err = mp_read_radix(&p, (char *)sets[idx].B, 64)) != MP_OKAY) { goto error; } /* p = B */
950 if ((err = mp_expt_d(&pt->x, 3, &tmp)) != MP_OKAY) { goto error; } /* tmp = pX^3 */
951 if ((err = mp_mul_d(&pt->x, 3, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = 3*pX^3 */
952 if ((err = mp_sub(&tmp, &tmp2, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp - tmp2 */
953 if ((err = mp_add(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp + p */
954 if ((err = mp_read_radix(&p, (char *)sets[idx].prime, 64)) != MP_OKAY) { goto error; } /* p = prime */
955 if ((err = mp_mod(&tmp, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = tmp mod p */
956
957 /* now find square root */
958 if ((err = mp_add_d(&p, 1, &tmp2)) != MP_OKAY) { goto error; } /* tmp2 = p + 1 */
959 if ((err = mp_div_2d(&tmp2, 2, &tmp2, NULL)) != MP_OKAY) { goto error; } /* tmp2 = (p+1)/4 */
960 if ((err = mp_exptmod(&tmp, &tmp2, &p, &tmp)) != MP_OKAY) { goto error; } /* tmp = (x^3 - 3x + b)^((p+1)/4) mod p */
961
962 /* if result==0, then y==tmp, otherwise y==p-tmp */
963 if (result == 0) {
964 if ((err = mp_copy(&tmp, &pt->y) != MP_OKAY)) { goto error; }
965 } else {
966 if ((err = mp_sub(&p, &tmp, &pt->y) != MP_OKAY)) { goto error; }
967 }
968
969 err = CRYPT_OK;
970 goto done;
971 error:
972 err = mpi_to_ltc_error(err);
973 done:
974 mp_clear_multi(&p, &tmp, &tmp2, NULL);
975 return err;
976 }
977
978 /** 823 /**
979 Export an ECC key as a binary packet 824 Export an ECC key as a binary packet
980 @param out [out] Destination for the key 825 @param out [out] Destination for the key
981 @param outlen [in/out] Max size and resulting size of the exported key 826 @param outlen [in/out] Max size and resulting size of the exported key
982 @param type The type of key you want to export (PK_PRIVATE or PK_PUBLIC) 827 @param type The type of key you want to export (PK_PRIVATE or PK_PUBLIC)
983 @param key The key to export 828 @param key The key to export
984 @return CRYPT_OK if successful 829 @return CRYPT_OK if successful
985 */ 830 */
986 int ecc_export(unsigned char *out, unsigned long *outlen, int type, ecc_key *key) 831 int ecc_export(unsigned char *out, unsigned long *outlen, int type, ecc_key *key)
987 { 832 {
988 unsigned long y, z; 833 int err;
989 int cp, err; 834 unsigned char flags[1];
835 unsigned long key_size;
990 836
991 LTC_ARGCHK(out != NULL); 837 LTC_ARGCHK(out != NULL);
992 LTC_ARGCHK(outlen != NULL); 838 LTC_ARGCHK(outlen != NULL);
993 LTC_ARGCHK(key != NULL); 839 LTC_ARGCHK(key != NULL);
994 840
995 /* can we store the static header? */
996 if (*outlen < (PACKET_SIZE + 3)) {
997 return CRYPT_BUFFER_OVERFLOW;
998 }
999
1000 /* type valid? */ 841 /* type valid? */
1001 if (key->type != PK_PRIVATE && type == PK_PRIVATE) { 842 if (key->type != PK_PRIVATE && type == PK_PRIVATE) {
1002 return CRYPT_PK_TYPE_MISMATCH; 843 return CRYPT_PK_TYPE_MISMATCH;
1003 } 844 }
1004 845
1005 /* output type and magic byte */ 846 if (is_valid_idx(key->idx) == 0) {
1006 y = PACKET_SIZE; 847 return CRYPT_INVALID_ARG;
1007 out[y++] = (unsigned char)type; 848 }
1008 out[y++] = (unsigned char)sets[key->idx].size; 849
1009 850 /* we store the NIST byte size */
1010 /* output x coordinate */ 851 key_size = sets[key->idx].size;
1011 OUTPUT_BIGNUM(&(key->pubkey.x), out, y, z);
1012
1013 /* compress y and output it */
1014 if ((err = compress_y_point(&key->pubkey, key->idx, &cp)) != CRYPT_OK) {
1015 return err;
1016 }
1017 out[y++] = (unsigned char)cp;
1018 852
1019 if (type == PK_PRIVATE) { 853 if (type == PK_PRIVATE) {
1020 OUTPUT_BIGNUM(&key->k, out, y, z); 854 flags[0] = 1;
1021 } 855 err = der_encode_sequence_multi(out, outlen,
1022 856 LTC_ASN1_BIT_STRING, 1UL, flags,
1023 /* store header */ 857 LTC_ASN1_SHORT_INTEGER, 1UL, &key_size,
1024 packet_store_header(out, PACKET_SECT_ECC, PACKET_SUB_KEY); 858 LTC_ASN1_INTEGER, 1UL, &key->pubkey.x,
1025 *outlen = y; 859 LTC_ASN1_INTEGER, 1UL, &key->pubkey.y,
1026 860 LTC_ASN1_INTEGER, 1UL, &key->k,
1027 return CRYPT_OK; 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;
1028 } 873 }
1029 874
1030 /** 875 /**
1031 Import an ECC key from a binary packet 876 Import an ECC key from a binary packet
1032 @param in The packet to import 877 @param in The packet to import
1034 @param key [out] The destination of the import 879 @param key [out] The destination of the import
1035 @return CRYPT_OK if successful, upon error all allocated memory will be freed 880 @return CRYPT_OK if successful, upon error all allocated memory will be freed
1036 */ 881 */
1037 int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key) 882 int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key)
1038 { 883 {
1039 unsigned long x, y, s; 884 unsigned long key_size;
1040 int err; 885 unsigned char flags[1];
886 int err;
1041 887
1042 LTC_ARGCHK(in != NULL); 888 LTC_ARGCHK(in != NULL);
1043 LTC_ARGCHK(key != NULL); 889 LTC_ARGCHK(key != NULL);
1044
1045 /* check length */
1046 if ((3+PACKET_SIZE) > inlen) {
1047 return CRYPT_INVALID_PACKET;
1048 }
1049
1050 /* check type */
1051 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_ECC, PACKET_SUB_KEY)) != CRYPT_OK) {
1052 return err;
1053 }
1054 890
1055 /* init key */ 891 /* init key */
1056 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != MP_OKAY) { 892 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != MP_OKAY) {
1057 return CRYPT_MEM; 893 return CRYPT_MEM;
1058 } 894 }
1059 895
1060 y = PACKET_SIZE; 896 /* find out what type of key it is */
1061 key->type = (int)in[y++]; 897 if ((err = der_decode_sequence_multi(in, inlen,
1062 s = (unsigned long)in[y++]; 898 LTC_ASN1_BIT_STRING, 1UL, &flags,
1063 899 LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
1064 for (x = 0; (s > (unsigned long)sets[x].size) && (sets[x].size != 0); x++);
1065 if (sets[x].size == 0) {
1066 err = CRYPT_INVALID_KEYSIZE;
1067 goto error; 900 goto error;
1068 } 901 }
1069 key->idx = (int)x; 902
1070 903
1071 /* type check both values */ 904 if (flags[0] == 1) {
1072 if ((key->type != PK_PUBLIC) && (key->type != PK_PRIVATE)) { 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) {
1073 err = CRYPT_INVALID_PACKET; 933 err = CRYPT_INVALID_PACKET;
1074 goto error; 934 goto error;
1075 } 935 }
1076 936
1077 /* is the key idx valid? */ 937 /* set z */
1078 if (is_valid_idx(key->idx) != 1) {
1079 err = CRYPT_INVALID_PACKET;
1080 goto error;
1081 }
1082
1083 /* load x coordinate */
1084 INPUT_BIGNUM(&key->pubkey.x, in, x, y, inlen);
1085
1086 /* load y */
1087 x = (unsigned long)in[y++];
1088 if ((err = expand_y_point(&key->pubkey, key->idx, (int)x)) != CRYPT_OK) {
1089 goto error;
1090 }
1091
1092 if (key->type == PK_PRIVATE) {
1093 /* load private key */
1094 INPUT_BIGNUM(&key->k, in, x, y, inlen);
1095 }
1096
1097 /* eliminate private key if public */
1098 if (key->type == PK_PUBLIC) {
1099 mp_clear(&key->k);
1100 }
1101
1102 /* z is always 1 */
1103 mp_set(&key->pubkey.z, 1); 938 mp_set(&key->pubkey.z, 1);
1104 939
940 /* we're good */
1105 return CRYPT_OK; 941 return CRYPT_OK;
1106 error: 942 error:
1107 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL); 943 mp_clear_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL);
1108 return err; 944 return err;
1109 } 945 }
1110 946
1111 /** 947 /**
1112 Create an ECC shared secret between two keys 948 Create an ECC shared secret between two keys
1113 @param private_key The private ECC key 949 @param private_key The private ECC key
1114 @param public_key The public key 950 @param public_key The public key
1115 @param out [out] Destination of the shared secret 951 @param out [out] Destination of the shared secret (Conforms to EC-DH from ANSI X9.63)
1116 @param outlen [in/out] The max size and resulting size of the shared secret 952 @param outlen [in/out] The max size and resulting size of the shared secret
1117 @return CRYPT_OK if successful 953 @return CRYPT_OK if successful
1118 */ 954 */
1119 int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key, 955 int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
1120 unsigned char *out, unsigned long *outlen) 956 unsigned char *out, unsigned long *outlen)
1121 { 957 {
1122 unsigned long x, y; 958 unsigned long x;
1123 ecc_point *result; 959 ecc_point *result;
1124 mp_int prime; 960 mp_int prime;
1125 int err; 961 int err;
1126 962
1127 LTC_ARGCHK(private_key != NULL); 963 LTC_ARGCHK(private_key != NULL);
1132 /* type valid? */ 968 /* type valid? */
1133 if (private_key->type != PK_PRIVATE) { 969 if (private_key->type != PK_PRIVATE) {
1134 return CRYPT_PK_NOT_PRIVATE; 970 return CRYPT_PK_NOT_PRIVATE;
1135 } 971 }
1136 972
973 if (is_valid_idx(private_key->idx) == 0) {
974 return CRYPT_INVALID_ARG;
975 }
976
1137 if (private_key->idx != public_key->idx) { 977 if (private_key->idx != public_key->idx) {
1138 return CRYPT_PK_TYPE_MISMATCH; 978 return CRYPT_PK_TYPE_MISMATCH;
1139 } 979 }
1140 980
1141 /* make new point */ 981 /* make new point */
1147 if ((err = mp_init(&prime)) != MP_OKAY) { 987 if ((err = mp_init(&prime)) != MP_OKAY) {
1148 del_point(result); 988 del_point(result);
1149 return mpi_to_ltc_error(err); 989 return mpi_to_ltc_error(err);
1150 } 990 }
1151 991
1152 if ((err = mp_read_radix(&prime, (char *)sets[private_key->idx].prime, 64)) != MP_OKAY) { goto error; } 992 if ((err = mp_read_radix(&prime, (char *)sets[private_key->idx].prime, 64)) != MP_OKAY) { goto error; }
1153 if ((err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime)) != CRYPT_OK) { goto done1; } 993 if ((err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime, 1)) != CRYPT_OK) { goto done1; }
1154 994
1155 x = (unsigned long)mp_unsigned_bin_size(&result->x); 995 x = (unsigned long)mp_unsigned_bin_size(&prime);
1156 y = (unsigned long)mp_unsigned_bin_size(&result->y); 996 if (*outlen < x) {
1157
1158 if (*outlen < (x+y)) {
1159 err = CRYPT_BUFFER_OVERFLOW; 997 err = CRYPT_BUFFER_OVERFLOW;
1160 goto done1; 998 goto done1;
1161 } 999 }
1162 *outlen = x+y; 1000 zeromem(out, x);
1163 if ((err = mp_to_unsigned_bin(&result->x, out)) != MP_OKAY) { goto error; } 1001 if ((err = mp_to_unsigned_bin(&result->x, out + (x - mp_unsigned_bin_size(&result->x)))) != MP_OKAY) { goto error; }
1164 if ((err = mp_to_unsigned_bin(&result->y, out+x)) != MP_OKAY) { goto error; } 1002
1165 1003 err = CRYPT_OK;
1166 err = CRYPT_OK; 1004 *outlen = x;
1167 goto done1; 1005 goto done1;
1168 error: 1006 error:
1169 err = mpi_to_ltc_error(err); 1007 err = mpi_to_ltc_error(err);
1170 done1: 1008 done1:
1171 mp_clear(&prime); 1009 mp_clear(&prime);
1190 #include "ecc_sys.c" 1028 #include "ecc_sys.c"
1191 1029
1192 #endif 1030 #endif
1193 1031
1194 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 $ */