Ashley Mills
cyassl re-port with cellular comms, PSK test
Dependencies: VodafoneUSBModem_bleedingedge2 mbed-rtos mbed-src
Embed:
(wiki syntax)
Show/hide line numbers
ecc.c
00001 /* ecc.c 00002 * 00003 * Copyright (C) 2006-2012 Sawtooth Consulting Ltd. 00004 * 00005 * This file is part of CyaSSL. 00006 * 00007 * CyaSSL is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU General Public License as published by 00009 * the Free Software Foundation; either version 2 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * CyaSSL is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 00020 */ 00021 00022 00023 #ifdef HAVE_CONFIG_H 00024 #include <config.h> 00025 #endif 00026 00027 /* in case user set HAVE_ECC there */ 00028 #include <cyassl/ctaocrypt/settings.h> 00029 00030 #ifdef HAVE_ECC 00031 00032 #include <cyassl/ctaocrypt/ecc.h> 00033 #include <cyassl/ctaocrypt/asn.h> 00034 #include <cyassl/ctaocrypt/error.h> 00035 00036 00037 /* map 00038 00039 ptmul -> mulmod 00040 00041 */ 00042 00043 #define ECC112 00044 #define ECC128 00045 #define ECC160 00046 #define ECC192 00047 #define ECC224 00048 #define ECC256 00049 #define ECC384 00050 #define ECC521 00051 00052 00053 00054 /* This holds the key settings. ***MUST*** be organized by size from 00055 smallest to largest. */ 00056 00057 const ecc_set_type ecc_sets[] = { 00058 #ifdef ECC112 00059 { 00060 14, 00061 "SECP112R1", 00062 "DB7C2ABF62E35E668076BEAD208B", 00063 "659EF8BA043916EEDE8911702B22", 00064 "DB7C2ABF62E35E7628DFAC6561C5", 00065 "09487239995A5EE76B55F9C2F098", 00066 "A89CE5AF8724C0A23E0E0FF77500" 00067 }, 00068 #endif 00069 #ifdef ECC128 00070 { 00071 16, 00072 "SECP128R1", 00073 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF", 00074 "E87579C11079F43DD824993C2CEE5ED3", 00075 "FFFFFFFE0000000075A30D1B9038A115", 00076 "161FF7528B899B2D0C28607CA52C5B86", 00077 "CF5AC8395BAFEB13C02DA292DDED7A83", 00078 }, 00079 #endif 00080 #ifdef ECC160 00081 { 00082 20, 00083 "SECP160R1", 00084 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF", 00085 "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45", 00086 "0100000000000000000001F4C8F927AED3CA752257", 00087 "4A96B5688EF573284664698968C38BB913CBFC82", 00088 "23A628553168947D59DCC912042351377AC5FB32", 00089 }, 00090 #endif 00091 #ifdef ECC192 00092 { 00093 24, 00094 "ECC-192", 00095 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", 00096 "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1", 00097 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831", 00098 "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012", 00099 "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811", 00100 }, 00101 #endif 00102 #ifdef ECC224 00103 { 00104 28, 00105 "ECC-224", 00106 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001", 00107 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4", 00108 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D", 00109 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21", 00110 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34", 00111 }, 00112 #endif 00113 #ifdef ECC256 00114 { 00115 32, 00116 "ECC-256", 00117 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", 00118 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B", 00119 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551", 00120 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296", 00121 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5", 00122 }, 00123 #endif 00124 #ifdef ECC384 00125 { 00126 48, 00127 "ECC-384", 00128 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF", 00129 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF", 00130 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973", 00131 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7", 00132 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F", 00133 }, 00134 #endif 00135 #ifdef ECC521 00136 { 00137 66, 00138 "ECC-521", 00139 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 00140 "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00", 00141 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409", 00142 "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66", 00143 "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650", 00144 }, 00145 #endif 00146 { 00147 0, 00148 NULL, NULL, NULL, NULL, NULL, NULL 00149 } 00150 }; 00151 00152 00153 ecc_point* ecc_new_point(void); 00154 void ecc_del_point(ecc_point* p); 00155 int ecc_map(ecc_point*, mp_int*, mp_digit*); 00156 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R, 00157 mp_int* modulus, mp_digit* mp); 00158 int ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus, 00159 mp_digit* mp); 00160 00161 00162 /* helper for either lib */ 00163 static int get_digit_count(mp_int* a) 00164 { 00165 if (a == NULL) 00166 return 0; 00167 00168 return a->used; 00169 } 00170 00171 /* helper for either lib */ 00172 static unsigned long get_digit(mp_int* a, int n) 00173 { 00174 if (a == NULL) 00175 return 0; 00176 00177 return (n >= a->used || n < 0) ? 0 : a->dp[n]; 00178 } 00179 00180 00181 /** 00182 Add two ECC points 00183 P The point to add 00184 Q The point to add 00185 R [out] The destination of the double 00186 modulus The modulus of the field the ECC curve is in 00187 mp The "b" value from montgomery_setup() 00188 return MP_OKAY on success 00189 */ 00190 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R, 00191 mp_int* modulus, mp_digit* mp) 00192 { 00193 mp_int t1; 00194 mp_int t2; 00195 mp_int x; 00196 mp_int y; 00197 mp_int z; 00198 int err; 00199 00200 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL) 00201 return ECC_BAD_ARG_E; 00202 00203 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) { 00204 return err; 00205 } 00206 00207 /* should we dbl instead? */ 00208 err = mp_sub(modulus, &Q->y, &t1); 00209 00210 if (err == MP_OKAY) { 00211 if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) && 00212 (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) && 00213 (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) { 00214 mp_clear(&t1); 00215 mp_clear(&t2); 00216 mp_clear(&x); 00217 mp_clear(&y); 00218 mp_clear(&z); 00219 00220 return ecc_projective_dbl_point(P, R, modulus, mp); 00221 } 00222 } 00223 00224 if (err == MP_OKAY) 00225 err = mp_copy(&P->x, &x); 00226 if (err == MP_OKAY) 00227 err = mp_copy(&P->y, &y); 00228 if (err == MP_OKAY) 00229 err = mp_copy(&P->z, &z); 00230 00231 /* if Z is one then these are no-operations */ 00232 if (err == MP_OKAY) { 00233 if (get_digit_count(&Q->z)) { 00234 /* T1 = Z' * Z' */ 00235 err = mp_sqr(&Q->z, &t1); 00236 if (err == MP_OKAY) 00237 err = mp_montgomery_reduce(&t1, modulus, *mp); 00238 00239 /* X = X * T1 */ 00240 if (err == MP_OKAY) 00241 err = mp_mul(&t1, &x, &x); 00242 if (err == MP_OKAY) 00243 err = mp_montgomery_reduce(&x, modulus, *mp); 00244 00245 /* T1 = Z' * T1 */ 00246 if (err == MP_OKAY) 00247 err = mp_mul(&Q->z, &t1, &t1); 00248 if (err == MP_OKAY) 00249 err = mp_montgomery_reduce(&t1, modulus, *mp); 00250 00251 /* Y = Y * T1 */ 00252 if (err == MP_OKAY) 00253 err = mp_mul(&t1, &y, &y); 00254 if (err == MP_OKAY) 00255 err = mp_montgomery_reduce(&y, modulus, *mp); 00256 } 00257 } 00258 00259 /* T1 = Z*Z */ 00260 if (err == MP_OKAY) 00261 err = mp_sqr(&z, &t1); 00262 if (err == MP_OKAY) 00263 err = mp_montgomery_reduce(&t1, modulus, *mp); 00264 00265 /* T2 = X' * T1 */ 00266 if (err == MP_OKAY) 00267 err = mp_mul(&Q->x, &t1, &t2); 00268 if (err == MP_OKAY) 00269 err = mp_montgomery_reduce(&t2, modulus, *mp); 00270 00271 /* T1 = Z * T1 */ 00272 if (err == MP_OKAY) 00273 err = mp_mul(&z, &t1, &t1); 00274 if (err == MP_OKAY) 00275 err = mp_montgomery_reduce(&t1, modulus, *mp); 00276 00277 /* T1 = Y' * T1 */ 00278 if (err == MP_OKAY) 00279 err = mp_mul(&Q->y, &t1, &t1); 00280 if (err == MP_OKAY) 00281 err = mp_montgomery_reduce(&t1, modulus, *mp); 00282 00283 /* Y = Y - T1 */ 00284 if (err == MP_OKAY) 00285 err = mp_sub(&y, &t1, &y); 00286 if (err == MP_OKAY) { 00287 if (mp_cmp_d(&y, 0) == MP_LT) 00288 err = mp_add(&y, modulus, &y); 00289 } 00290 /* T1 = 2T1 */ 00291 if (err == MP_OKAY) 00292 err = mp_add(&t1, &t1, &t1); 00293 if (err == MP_OKAY) { 00294 if (mp_cmp(&t1, modulus) != MP_LT) 00295 err = mp_sub(&t1, modulus, &t1); 00296 } 00297 /* T1 = Y + T1 */ 00298 if (err == MP_OKAY) 00299 err = mp_add(&t1, &y, &t1); 00300 if (err == MP_OKAY) { 00301 if (mp_cmp(&t1, modulus) != MP_LT) 00302 err = mp_sub(&t1, modulus, &t1); 00303 } 00304 /* X = X - T2 */ 00305 if (err == MP_OKAY) 00306 err = mp_sub(&x, &t2, &x); 00307 if (err == MP_OKAY) { 00308 if (mp_cmp_d(&x, 0) == MP_LT) 00309 err = mp_add(&x, modulus, &x); 00310 } 00311 /* T2 = 2T2 */ 00312 if (err == MP_OKAY) 00313 err = mp_add(&t2, &t2, &t2); 00314 if (err == MP_OKAY) { 00315 if (mp_cmp(&t2, modulus) != MP_LT) 00316 err = mp_sub(&t2, modulus, &t2); 00317 } 00318 /* T2 = X + T2 */ 00319 if (err == MP_OKAY) 00320 err = mp_add(&t2, &x, &t2); 00321 if (err == MP_OKAY) { 00322 if (mp_cmp(&t2, modulus) != MP_LT) 00323 err = mp_sub(&t2, modulus, &t2); 00324 } 00325 00326 if (err == MP_OKAY) { 00327 if (get_digit_count(&Q->z)) { 00328 /* Z = Z * Z' */ 00329 err = mp_mul(&z, &Q->z, &z); 00330 if (err == MP_OKAY) 00331 err = mp_montgomery_reduce(&z, modulus, *mp); 00332 } 00333 } 00334 00335 /* Z = Z * X */ 00336 if (err == MP_OKAY) 00337 err = mp_mul(&z, &x, &z); 00338 if (err == MP_OKAY) 00339 err = mp_montgomery_reduce(&z, modulus, *mp); 00340 00341 /* T1 = T1 * X */ 00342 if (err == MP_OKAY) 00343 err = mp_mul(&t1, &x, &t1); 00344 if (err == MP_OKAY) 00345 err = mp_montgomery_reduce(&t1, modulus, *mp); 00346 00347 /* X = X * X */ 00348 if (err == MP_OKAY) 00349 err = mp_sqr(&x, &x); 00350 if (err == MP_OKAY) 00351 err = mp_montgomery_reduce(&x, modulus, *mp); 00352 00353 /* T2 = T2 * x */ 00354 if (err == MP_OKAY) 00355 err = mp_mul(&t2, &x, &t2); 00356 if (err == MP_OKAY) 00357 err = mp_montgomery_reduce(&t2, modulus, *mp); 00358 00359 /* T1 = T1 * X */ 00360 if (err == MP_OKAY) 00361 err = mp_mul(&t1, &x, &t1); 00362 if (err == MP_OKAY) 00363 err = mp_montgomery_reduce(&t1, modulus, *mp); 00364 00365 /* X = Y*Y */ 00366 if (err == MP_OKAY) 00367 err = mp_sqr(&y, &x); 00368 if (err == MP_OKAY) 00369 err = mp_montgomery_reduce(&x, modulus, *mp); 00370 00371 /* X = X - T2 */ 00372 if (err == MP_OKAY) 00373 err = mp_sub(&x, &t2, &x); 00374 if (err == MP_OKAY) { 00375 if (mp_cmp_d(&x, 0) == MP_LT) 00376 err = mp_add(&x, modulus, &x); 00377 } 00378 /* T2 = T2 - X */ 00379 if (err == MP_OKAY) 00380 err = mp_sub(&t2, &x, &t2); 00381 if (err == MP_OKAY) { 00382 if (mp_cmp_d(&t2, 0) == MP_LT) 00383 err = mp_add(&t2, modulus, &t2); 00384 } 00385 /* T2 = T2 - X */ 00386 if (err == MP_OKAY) 00387 err = mp_sub(&t2, &x, &t2); 00388 if (err == MP_OKAY) { 00389 if (mp_cmp_d(&t2, 0) == MP_LT) 00390 err = mp_add(&t2, modulus, &t2); 00391 } 00392 /* T2 = T2 * Y */ 00393 if (err == MP_OKAY) 00394 err = mp_mul(&t2, &y, &t2); 00395 if (err == MP_OKAY) 00396 err = mp_montgomery_reduce(&t2, modulus, *mp); 00397 00398 /* Y = T2 - T1 */ 00399 if (err == MP_OKAY) 00400 err = mp_sub(&t2, &t1, &y); 00401 if (err == MP_OKAY) { 00402 if (mp_cmp_d(&y, 0) == MP_LT) 00403 err = mp_add(&y, modulus, &y); 00404 } 00405 /* Y = Y/2 */ 00406 if (err == MP_OKAY) { 00407 if (mp_isodd(&y)) 00408 err = mp_add(&y, modulus, &y); 00409 } 00410 if (err == MP_OKAY) 00411 err = mp_div_2(&y, &y); 00412 00413 if (err == MP_OKAY) 00414 err = mp_copy(&x, &R->x); 00415 if (err == MP_OKAY) 00416 err = mp_copy(&y, &R->y); 00417 if (err == MP_OKAY) 00418 err = mp_copy(&z, &R->z); 00419 00420 /* clean up */ 00421 mp_clear(&t1); 00422 mp_clear(&t2); 00423 mp_clear(&x); 00424 mp_clear(&y); 00425 mp_clear(&z); 00426 00427 return err; 00428 } 00429 00430 00431 /** 00432 Double an ECC point 00433 P The point to double 00434 R [out] The destination of the double 00435 modulus The modulus of the field the ECC curve is in 00436 mp The "b" value from montgomery_setup() 00437 return MP_OKAY on success 00438 */ 00439 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus, 00440 mp_digit* mp) 00441 { 00442 mp_int t1; 00443 mp_int t2; 00444 int err; 00445 00446 if (P == NULL || R == NULL || modulus == NULL || mp == NULL) 00447 return ECC_BAD_ARG_E; 00448 00449 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) { 00450 return err; 00451 } 00452 00453 if (P != R) { 00454 err = mp_copy(&P->x, &R->x); 00455 if (err == MP_OKAY) 00456 err = mp_copy(&P->y, &R->y); 00457 if (err == MP_OKAY) 00458 err = mp_copy(&P->z, &R->z); 00459 } 00460 00461 /* t1 = Z * Z */ 00462 if (err == MP_OKAY) 00463 err = mp_sqr(&R->z, &t1); 00464 if (err == MP_OKAY) 00465 err = mp_montgomery_reduce(&t1, modulus, *mp); 00466 00467 /* Z = Y * Z */ 00468 if (err == MP_OKAY) 00469 err = mp_mul(&R->z, &R->y, &R->z); 00470 if (err == MP_OKAY) 00471 err = mp_montgomery_reduce(&R->z, modulus, *mp); 00472 00473 /* Z = 2Z */ 00474 if (err == MP_OKAY) 00475 err = mp_add(&R->z, &R->z, &R->z); 00476 if (err == MP_OKAY) { 00477 if (mp_cmp(&R->z, modulus) != MP_LT) 00478 err = mp_sub(&R->z, modulus, &R->z); 00479 } 00480 00481 /* T2 = X - T1 */ 00482 if (err == MP_OKAY) 00483 err = mp_sub(&R->x, &t1, &t2); 00484 if (err == MP_OKAY) { 00485 if (mp_cmp_d(&t2, 0) == MP_LT) 00486 err = mp_add(&t2, modulus, &t2); 00487 } 00488 /* T1 = X + T1 */ 00489 if (err == MP_OKAY) 00490 err = mp_add(&t1, &R->x, &t1); 00491 if (err == MP_OKAY) { 00492 if (mp_cmp(&t1, modulus) != MP_LT) 00493 err = mp_sub(&t1, modulus, &t1); 00494 } 00495 /* T2 = T1 * T2 */ 00496 if (err == MP_OKAY) 00497 err = mp_mul(&t1, &t2, &t2); 00498 if (err == MP_OKAY) 00499 err = mp_montgomery_reduce(&t2, modulus, *mp); 00500 00501 /* T1 = 2T2 */ 00502 if (err == MP_OKAY) 00503 err = mp_add(&t2, &t2, &t1); 00504 if (err == MP_OKAY) { 00505 if (mp_cmp(&t1, modulus) != MP_LT) 00506 err = mp_sub(&t1, modulus, &t1); 00507 } 00508 /* T1 = T1 + T2 */ 00509 if (err == MP_OKAY) 00510 err = mp_add(&t1, &t2, &t1); 00511 if (err == MP_OKAY) { 00512 if (mp_cmp(&t1, modulus) != MP_LT) 00513 err = mp_sub(&t1, modulus, &t1); 00514 } 00515 /* Y = 2Y */ 00516 if (err == MP_OKAY) 00517 err = mp_add(&R->y, &R->y, &R->y); 00518 if (err == MP_OKAY) { 00519 if (mp_cmp(&R->y, modulus) != MP_LT) 00520 err = mp_sub(&R->y, modulus, &R->y); 00521 } 00522 /* Y = Y * Y */ 00523 if (err == MP_OKAY) 00524 err = mp_sqr(&R->y, &R->y); 00525 if (err == MP_OKAY) 00526 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00527 00528 /* T2 = Y * Y */ 00529 if (err == MP_OKAY) 00530 err = mp_sqr(&R->y, &t2); 00531 if (err == MP_OKAY) 00532 err = mp_montgomery_reduce(&t2, modulus, *mp); 00533 00534 /* T2 = T2/2 */ 00535 if (err == MP_OKAY) { 00536 if (mp_isodd(&t2)) 00537 err = mp_add(&t2, modulus, &t2); 00538 } 00539 if (err == MP_OKAY) 00540 err = mp_div_2(&t2, &t2); 00541 00542 /* Y = Y * X */ 00543 if (err == MP_OKAY) 00544 err = mp_mul(&R->y, &R->x, &R->y); 00545 if (err == MP_OKAY) 00546 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00547 00548 /* X = T1 * T1 */ 00549 if (err == MP_OKAY) 00550 err = mp_sqr(&t1, &R->x); 00551 if (err == MP_OKAY) 00552 err = mp_montgomery_reduce(&R->x, modulus, *mp); 00553 00554 /* X = X - Y */ 00555 if (err == MP_OKAY) 00556 err = mp_sub(&R->x, &R->y, &R->x); 00557 if (err == MP_OKAY) { 00558 if (mp_cmp_d(&R->x, 0) == MP_LT) 00559 err = mp_add(&R->x, modulus, &R->x); 00560 } 00561 /* X = X - Y */ 00562 if (err == MP_OKAY) 00563 err = mp_sub(&R->x, &R->y, &R->x); 00564 if (err == MP_OKAY) { 00565 if (mp_cmp_d(&R->x, 0) == MP_LT) 00566 err = mp_add(&R->x, modulus, &R->x); 00567 } 00568 /* Y = Y - X */ 00569 if (err == MP_OKAY) 00570 err = mp_sub(&R->y, &R->x, &R->y); 00571 if (err == MP_OKAY) { 00572 if (mp_cmp_d(&R->y, 0) == MP_LT) 00573 err = mp_add(&R->y, modulus, &R->y); 00574 } 00575 /* Y = Y * T1 */ 00576 if (err == MP_OKAY) 00577 err = mp_mul(&R->y, &t1, &R->y); 00578 if (err == MP_OKAY) 00579 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00580 00581 /* Y = Y - T2 */ 00582 if (err == MP_OKAY) 00583 err = mp_sub(&R->y, &t2, &R->y); 00584 if (err == MP_OKAY) { 00585 if (mp_cmp_d(&R->y, 0) == MP_LT) 00586 err = mp_add(&R->y, modulus, &R->y); 00587 } 00588 00589 /* clean up */ 00590 mp_clear(&t1); 00591 mp_clear(&t2); 00592 00593 return err; 00594 } 00595 00596 00597 /** 00598 Map a projective jacbobian point back to affine space 00599 P [in/out] The point to map 00600 modulus The modulus of the field the ECC curve is in 00601 mp The "b" value from montgomery_setup() 00602 return MP_OKAY on success 00603 */ 00604 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp) 00605 { 00606 mp_int t1; 00607 mp_int t2; 00608 int err; 00609 00610 if (P == NULL || mp == NULL || modulus == NULL) 00611 return ECC_BAD_ARG_E; 00612 00613 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) { 00614 return MEMORY_E; 00615 } 00616 00617 /* first map z back to normal */ 00618 err = mp_montgomery_reduce(&P->z, modulus, *mp); 00619 00620 /* get 1/z */ 00621 if (err == MP_OKAY) 00622 err = mp_invmod(&P->z, modulus, &t1); 00623 00624 /* get 1/z^2 and 1/z^3 */ 00625 if (err == MP_OKAY) 00626 err = mp_sqr(&t1, &t2); 00627 if (err == MP_OKAY) 00628 err = mp_mod(&t2, modulus, &t2); 00629 if (err == MP_OKAY) 00630 err = mp_mul(&t1, &t2, &t1); 00631 if (err == MP_OKAY) 00632 err = mp_mod(&t1, modulus, &t1); 00633 00634 /* multiply against x/y */ 00635 if (err == MP_OKAY) 00636 err = mp_mul(&P->x, &t2, &P->x); 00637 if (err == MP_OKAY) 00638 err = mp_montgomery_reduce(&P->x, modulus, *mp); 00639 if (err == MP_OKAY) 00640 err = mp_mul(&P->y, &t1, &P->y); 00641 if (err == MP_OKAY) 00642 err = mp_montgomery_reduce(&P->y, modulus, *mp); 00643 00644 if (err == MP_OKAY) 00645 mp_set(&P->z, 1); 00646 00647 /* clean up */ 00648 mp_clear(&t1); 00649 mp_clear(&t2); 00650 00651 return err; 00652 } 00653 00654 00655 #ifndef ECC_TIMING_RESISTANT 00656 00657 /* size of sliding window, don't change this! */ 00658 #define WINSIZE 4 00659 00660 /** 00661 Perform a point multiplication 00662 k The scalar to multiply by 00663 G The base point 00664 R [out] Destination for kG 00665 modulus The modulus of the field the ECC curve is in 00666 map Boolean whether to map back to affine or not 00667 (1==map, 0 == leave in projective) 00668 return MP_OKAY on success 00669 */ 00670 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus, 00671 int map) 00672 { 00673 ecc_point *tG, *M[8]; 00674 int i, j, err; 00675 mp_int mu; 00676 mp_digit mp; 00677 unsigned long buf; 00678 int first, bitbuf, bitcpy, bitcnt, mode, digidx; 00679 00680 if (k == NULL || G == NULL || R == NULL || modulus == NULL) 00681 return ECC_BAD_ARG_E; 00682 00683 /* init montgomery reduction */ 00684 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) { 00685 return err; 00686 } 00687 if ((err = mp_init(&mu)) != MP_OKAY) { 00688 return err; 00689 } 00690 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) { 00691 mp_clear(&mu); 00692 return err; 00693 } 00694 00695 /* alloc ram for window temps */ 00696 for (i = 0; i < 8; i++) { 00697 M[i] = ecc_new_point(); 00698 if (M[i] == NULL) { 00699 for (j = 0; j < i; j++) { 00700 ecc_del_point(M[j]); 00701 } 00702 mp_clear(&mu); 00703 return MEMORY_E; 00704 } 00705 } 00706 00707 /* make a copy of G incase R==G */ 00708 tG = ecc_new_point(); 00709 if (tG == NULL) 00710 err = MEMORY_E; 00711 00712 /* tG = G and convert to montgomery */ 00713 if (err == MP_OKAY) { 00714 if (mp_cmp_d(&mu, 1) == MP_EQ) { 00715 err = mp_copy(&G->x, &tG->x); 00716 if (err == MP_OKAY) 00717 err = mp_copy(&G->y, &tG->y); 00718 if (err == MP_OKAY) 00719 err = mp_copy(&G->z, &tG->z); 00720 } else { 00721 err = mp_mulmod(&G->x, &mu, modulus, &tG->x); 00722 if (err == MP_OKAY) 00723 err = mp_mulmod(&G->y, &mu, modulus, &tG->y); 00724 if (err == MP_OKAY) 00725 err = mp_mulmod(&G->z, &mu, modulus, &tG->z); 00726 } 00727 } 00728 mp_clear(&mu); 00729 00730 /* calc the M tab, which holds kG for k==8..15 */ 00731 /* M[0] == 8G */ 00732 if (err == MP_OKAY) 00733 err = ecc_projective_dbl_point(tG, M[0], modulus, &mp); 00734 if (err == MP_OKAY) 00735 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp); 00736 if (err == MP_OKAY) 00737 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp); 00738 00739 /* now find (8+k)G for k=1..7 */ 00740 if (err == MP_OKAY) 00741 for (j = 9; j < 16; j++) { 00742 err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp); 00743 if (err != MP_OKAY) break; 00744 } 00745 00746 /* setup sliding window */ 00747 if (err == MP_OKAY) { 00748 mode = 0; 00749 bitcnt = 1; 00750 buf = 0; 00751 digidx = get_digit_count(k) - 1; 00752 bitcpy = bitbuf = 0; 00753 first = 1; 00754 00755 /* perform ops */ 00756 for (;;) { 00757 /* grab next digit as required */ 00758 if (--bitcnt == 0) { 00759 if (digidx == -1) { 00760 break; 00761 } 00762 buf = get_digit(k, digidx); 00763 bitcnt = (int) DIGIT_BIT; 00764 --digidx; 00765 } 00766 00767 /* grab the next msb from the ltiplicand */ 00768 i = (int)(buf >> (DIGIT_BIT - 1)) & 1; 00769 buf <<= 1; 00770 00771 /* skip leading zero bits */ 00772 if (mode == 0 && i == 0) 00773 continue; 00774 00775 /* if the bit is zero and mode == 1 then we double */ 00776 if (mode == 1 && i == 0) { 00777 err = ecc_projective_dbl_point(R, R, modulus, &mp); 00778 if (err != MP_OKAY) break; 00779 continue; 00780 } 00781 00782 /* else we add it to the window */ 00783 bitbuf |= (i << (WINSIZE - ++bitcpy)); 00784 mode = 2; 00785 00786 if (bitcpy == WINSIZE) { 00787 /* if this is the first window we do a simple copy */ 00788 if (first == 1) { 00789 /* R = kG [k = first window] */ 00790 err = mp_copy(&M[bitbuf-8]->x, &R->x); 00791 if (err != MP_OKAY) break; 00792 00793 err = mp_copy(&M[bitbuf-8]->y, &R->y); 00794 if (err != MP_OKAY) break; 00795 00796 err = mp_copy(&M[bitbuf-8]->z, &R->z); 00797 first = 0; 00798 } else { 00799 /* normal window */ 00800 /* ok window is filled so double as required and add */ 00801 /* double first */ 00802 for (j = 0; j < WINSIZE; j++) { 00803 err = ecc_projective_dbl_point(R, R, modulus, &mp); 00804 if (err != MP_OKAY) break; 00805 } 00806 if (err != MP_OKAY) break; /* out of first for(;;) */ 00807 00808 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */ 00809 err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp); 00810 } 00811 if (err != MP_OKAY) break; 00812 /* empty window and reset */ 00813 bitcpy = bitbuf = 0; 00814 mode = 1; 00815 } 00816 } 00817 } 00818 00819 /* if bits remain then double/add */ 00820 if (err == MP_OKAY) { 00821 if (mode == 2 && bitcpy > 0) { 00822 /* double then add */ 00823 for (j = 0; j < bitcpy; j++) { 00824 /* only double if we have had at least one add first */ 00825 if (first == 0) { 00826 err = ecc_projective_dbl_point(R, R, modulus, &mp); 00827 if (err != MP_OKAY) break; 00828 } 00829 00830 bitbuf <<= 1; 00831 if ((bitbuf & (1 << WINSIZE)) != 0) { 00832 if (first == 1) { 00833 /* first add, so copy */ 00834 err = mp_copy(&tG->x, &R->x); 00835 if (err != MP_OKAY) break; 00836 00837 err = mp_copy(&tG->y, &R->y); 00838 if (err != MP_OKAY) break; 00839 00840 err = mp_copy(&tG->z, &R->z); 00841 if (err != MP_OKAY) break; 00842 first = 0; 00843 } else { 00844 /* then add */ 00845 err = ecc_projective_add_point(R, tG, R, modulus, &mp); 00846 if (err != MP_OKAY) break; 00847 } 00848 } 00849 } 00850 } 00851 } 00852 00853 /* map R back from projective space */ 00854 if (err == MP_OKAY && map) 00855 err = ecc_map(R, modulus, &mp); 00856 00857 mp_clear(&mu); 00858 ecc_del_point(tG); 00859 for (i = 0; i < 8; i++) { 00860 ecc_del_point(M[i]); 00861 } 00862 return err; 00863 } 00864 00865 #undef WINSIZE 00866 #endif /* ECC_TIMING_RESISTANT */ 00867 00868 00869 /** 00870 Allocate a new ECC point 00871 return A newly allocated point or NULL on error 00872 */ 00873 ecc_point* ecc_new_point(void) 00874 { 00875 ecc_point* p; 00876 p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT); 00877 if (p == NULL) { 00878 return NULL; 00879 } 00880 XMEMSET(p, 0, sizeof(ecc_point)); 00881 if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) { 00882 XFREE(p, 0, DYNAMIC_TYPE_BIGINT); 00883 return NULL; 00884 } 00885 return p; 00886 } 00887 00888 /** Free an ECC point from memory 00889 p The point to free 00890 */ 00891 void ecc_del_point(ecc_point* p) 00892 { 00893 /* prevents free'ing null arguments */ 00894 if (p != NULL) { 00895 mp_clear(&p->x); 00896 mp_clear(&p->y); 00897 mp_clear(&p->z); 00898 XFREE(p, 0, DYNAMIC_TYPE_BIGINT); 00899 } 00900 } 00901 00902 00903 /** Returns whether an ECC idx is valid or not 00904 n The idx number to check 00905 return 1 if valid, 0 if not 00906 */ 00907 static int ecc_is_valid_idx(int n) 00908 { 00909 int x; 00910 00911 for (x = 0; ecc_sets[x].size != 0; x++) 00912 ; 00913 /* -1 is a valid index --- indicating that the domain params 00914 were supplied by the user */ 00915 if ((n >= -1) && (n < x)) { 00916 return 1; 00917 } 00918 return 0; 00919 } 00920 00921 00922 /** 00923 Create an ECC shared secret between two keys 00924 private_key The private ECC key 00925 public_key The public key 00926 out [out] Destination of the shared secret 00927 Conforms to EC-DH from ANSI X9.63 00928 outlen [in/out] The max size and resulting size of the shared secret 00929 return MP_OKAY if successful 00930 */ 00931 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out, 00932 word32* outlen) 00933 { 00934 word32 x = 0; 00935 ecc_point* result; 00936 mp_int prime; 00937 int err; 00938 00939 if (private_key == NULL || public_key == NULL || out == NULL || 00940 outlen == NULL) 00941 return BAD_FUNC_ARG; 00942 00943 /* type valid? */ 00944 if (private_key->type != ECC_PRIVATEKEY) { 00945 return ECC_BAD_ARG_E; 00946 } 00947 00948 if (ecc_is_valid_idx(private_key->idx) == 0 || 00949 ecc_is_valid_idx(public_key->idx) == 0) 00950 return ECC_BAD_ARG_E; 00951 00952 if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0) 00953 return ECC_BAD_ARG_E; 00954 00955 /* make new point */ 00956 result = ecc_new_point(); 00957 if (result == NULL) { 00958 return MEMORY_E; 00959 } 00960 00961 if ((err = mp_init(&prime)) != MP_OKAY) { 00962 ecc_del_point(result); 00963 return err; 00964 } 00965 00966 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16); 00967 00968 if (err == MP_OKAY) 00969 err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1); 00970 00971 if (err == MP_OKAY) { 00972 x = mp_unsigned_bin_size(&prime); 00973 if (*outlen < x) 00974 err = BUFFER_E; 00975 } 00976 00977 if (err == MP_OKAY) { 00978 XMEMSET(out, 0, x); 00979 err = mp_to_unsigned_bin(&result->x,out + (x - 00980 mp_unsigned_bin_size(&result->x))); 00981 *outlen = x; 00982 } 00983 00984 mp_clear(&prime); 00985 ecc_del_point(result); 00986 00987 return err; 00988 } 00989 00990 00991 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp); 00992 00993 /** 00994 Make a new ECC key 00995 rng An active RNG state 00996 keysize The keysize for the new key (in octets from 20 to 65 bytes) 00997 key [out] Destination of the newly created key 00998 return MP_OKAY if successful, 00999 upon error all allocated memory will be freed 01000 */ 01001 int ecc_make_key(RNG* rng, int keysize, ecc_key* key) 01002 { 01003 int x, err; 01004 01005 /* find key size */ 01006 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++) 01007 ; 01008 keysize = ecc_sets[x].size; 01009 01010 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) { 01011 return BAD_FUNC_ARG; 01012 } 01013 err = ecc_make_key_ex(rng, key, &ecc_sets[x]); 01014 key->idx = x; 01015 01016 return err; 01017 } 01018 01019 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp) 01020 { 01021 int err; 01022 ecc_point* base; 01023 mp_int prime; 01024 mp_int order; 01025 byte buf[ECC_MAXSIZE]; 01026 int keysize; 01027 01028 if (key == NULL || rng == NULL || dp == NULL) 01029 return ECC_BAD_ARG_E; 01030 01031 key->idx = -1; 01032 key->dp = dp; 01033 keysize = dp->size; 01034 01035 /* allocate ram */ 01036 base = NULL; 01037 01038 /* make up random string */ 01039 RNG_GenerateBlock(rng, buf, keysize); 01040 buf[0] |= 0x0c; 01041 01042 /* setup the key variables */ 01043 if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, 01044 &key->k, &prime, &order)) != MP_OKAY) 01045 return MEMORY_E; 01046 01047 base = ecc_new_point(); 01048 if (base == NULL) 01049 err = MEMORY_E; 01050 01051 /* read in the specs for this key */ 01052 if (err == MP_OKAY) 01053 err = mp_read_radix(&prime, (char *)key->dp->prime, 16); 01054 if (err == MP_OKAY) 01055 err = mp_read_radix(&order, (char *)key->dp->order, 16); 01056 if (err == MP_OKAY) 01057 err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16); 01058 if (err == MP_OKAY) 01059 err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16); 01060 01061 if (err == MP_OKAY) 01062 mp_set(&base->z, 1); 01063 if (err == MP_OKAY) 01064 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize); 01065 01066 /* the key should be smaller than the order of base point */ 01067 if (err == MP_OKAY) { 01068 if (mp_cmp(&key->k, &order) != MP_LT) 01069 err = mp_mod(&key->k, &order, &key->k); 01070 } 01071 /* make the public key */ 01072 if (err == MP_OKAY) 01073 err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1); 01074 if (err == MP_OKAY) 01075 key->type = ECC_PRIVATEKEY; 01076 01077 if (err != MP_OKAY) { 01078 /* clean up */ 01079 mp_clear(&key->pubkey.x); 01080 mp_clear(&key->pubkey.y); 01081 mp_clear(&key->pubkey.z); 01082 mp_clear(&key->k); 01083 } 01084 ecc_del_point(base); 01085 mp_clear(&prime); 01086 mp_clear(&order); 01087 #ifdef ECC_CLEAN_STACK 01088 XMEMSET(buff, 0, ECC_MAXSIZE); 01089 #endif 01090 return err; 01091 } 01092 01093 01094 /* Setup dynamic pointers is using normal math for proper freeing */ 01095 void ecc_init(ecc_key* key) 01096 { 01097 (void)key; 01098 #ifndef USE_FAST_MATH 01099 key->pubkey.x.dp = NULL; 01100 key->pubkey.y.dp = NULL; 01101 key->pubkey.z.dp = NULL; 01102 01103 key->k.dp = NULL; 01104 #endif 01105 } 01106 01107 01108 /** 01109 Sign a message digest 01110 in The message digest to sign 01111 inlen The length of the digest 01112 out [out] The destination for the signature 01113 outlen [in/out] The max size and resulting size of the signature 01114 key A private ECC key 01115 return MP_OKAY if successful 01116 */ 01117 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen, 01118 RNG* rng, ecc_key* key) 01119 { 01120 mp_int r; 01121 mp_int s; 01122 mp_int e; 01123 mp_int p; 01124 int err; 01125 01126 if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL) 01127 return ECC_BAD_ARG_E; 01128 01129 /* is this a private key? */ 01130 if (key->type != ECC_PRIVATEKEY) { 01131 return ECC_BAD_ARG_E; 01132 } 01133 01134 /* is the IDX valid ? */ 01135 if (ecc_is_valid_idx(key->idx) != 1) { 01136 return ECC_BAD_ARG_E; 01137 } 01138 01139 /* get the hash and load it as a bignum into 'e' */ 01140 /* init the bignums */ 01141 if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) { 01142 return err; 01143 } 01144 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01145 01146 if (err == MP_OKAY) { 01147 int truncLen = (int)inlen; 01148 if (truncLen > ecc_size(key)) 01149 truncLen = ecc_size(key); 01150 err = mp_read_unsigned_bin(&e, (byte*)in, truncLen); 01151 } 01152 01153 /* make up a key and export the public copy */ 01154 if (err == MP_OKAY) { 01155 ecc_key pubkey; 01156 ecc_init(&pubkey); 01157 for (;;) { 01158 err = ecc_make_key_ex(rng, &pubkey, key->dp); 01159 if (err != MP_OKAY) break; 01160 01161 /* find r = x1 mod n */ 01162 err = mp_mod(&pubkey.pubkey.x, &p, &r); 01163 if (err != MP_OKAY) break; 01164 01165 if (mp_iszero(&r) == MP_YES) 01166 ecc_free(&pubkey); 01167 else { 01168 /* find s = (e + xr)/k */ 01169 err = mp_invmod(&pubkey.k, &p, &pubkey.k); 01170 if (err != MP_OKAY) break; 01171 01172 err = mp_mulmod(&key->k, &r, &p, &s); /* s = xr */ 01173 if (err != MP_OKAY) break; 01174 01175 err = mp_add(&e, &s, &s); /* s = e + xr */ 01176 if (err != MP_OKAY) break; 01177 01178 err = mp_mod(&s, &p, &s); /* s = e + xr */ 01179 if (err != MP_OKAY) break; 01180 01181 err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */ 01182 if (err != MP_OKAY) break; 01183 01184 ecc_free(&pubkey); 01185 if (mp_iszero(&s) == MP_NO) 01186 break; 01187 } 01188 } 01189 ecc_free(&pubkey); 01190 } 01191 01192 /* store as SEQUENCE { r, s -- integer } */ 01193 if (err == MP_OKAY) 01194 err = StoreECC_DSA_Sig(out, outlen, &r, &s); 01195 01196 mp_clear(&r); 01197 mp_clear(&s); 01198 mp_clear(&p); 01199 mp_clear(&e); 01200 01201 return err; 01202 } 01203 01204 01205 /** 01206 Free an ECC key from memory 01207 key The key you wish to free 01208 */ 01209 void ecc_free(ecc_key* key) 01210 { 01211 if (key == NULL) 01212 return; 01213 01214 mp_clear(&key->pubkey.x); 01215 mp_clear(&key->pubkey.y); 01216 mp_clear(&key->pubkey.z); 01217 mp_clear(&key->k); 01218 } 01219 01220 01221 /* verify 01222 * 01223 * w = s^-1 mod n 01224 * u1 = xw 01225 * u2 = rw 01226 * X = u1*G + u2*Q 01227 * v = X_x1 mod n 01228 * accept if v == r 01229 */ 01230 01231 /** 01232 Verify an ECC signature 01233 sig The signature to verify 01234 siglen The length of the signature (octets) 01235 hash The hash (message digest) that was signed 01236 hashlen The length of the hash (octets) 01237 stat Result of signature, 1==valid, 0==invalid 01238 key The corresponding public ECC key 01239 return MP_OKAY if successful (even if the signature is not valid) 01240 */ 01241 int ecc_verify_hash(const byte* sig, word32 siglen, byte* hash, word32 hashlen, 01242 int* stat, ecc_key* key) 01243 { 01244 ecc_point *mG, *mQ; 01245 mp_int r; 01246 mp_int s; 01247 mp_int v; 01248 mp_int w; 01249 mp_int u1; 01250 mp_int u2; 01251 mp_int e; 01252 mp_int p; 01253 mp_int m; 01254 mp_digit mp; 01255 int err; 01256 01257 if (sig == NULL || hash == NULL || stat == NULL || key == NULL) 01258 return ECC_BAD_ARG_E; 01259 01260 /* default to invalid signature */ 01261 *stat = 0; 01262 01263 /* is the IDX valid ? */ 01264 if (ecc_is_valid_idx(key->idx) != 1) { 01265 return ECC_BAD_ARG_E; 01266 } 01267 01268 /* allocate ints */ 01269 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) { 01270 return MEMORY_E; 01271 } 01272 01273 if ((err = mp_init(&m)) != MP_OKAY) { 01274 mp_clear(&v); 01275 mp_clear(&w); 01276 mp_clear(&u1); 01277 mp_clear(&u2); 01278 mp_clear(&p); 01279 mp_clear(&e); 01280 return MEMORY_E; 01281 } 01282 01283 /* allocate points */ 01284 mG = ecc_new_point(); 01285 mQ = ecc_new_point(); 01286 if (mQ == NULL || mG == NULL) 01287 err = MEMORY_E; 01288 01289 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s. 01290 * If either of those don't allocate correctly, none of 01291 * the rest of this function will execute, and everything 01292 * gets cleaned up at the end. */ 01293 XMEMSET(&r, 0, sizeof(r)); 01294 XMEMSET(&s, 0, sizeof(s)); 01295 if (err == MP_OKAY) 01296 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s); 01297 01298 /* get the order */ 01299 if (err == MP_OKAY) 01300 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01301 01302 /* get the modulus */ 01303 if (err == MP_OKAY) 01304 err = mp_read_radix(&m, (char *)key->dp->prime, 16); 01305 01306 /* check for zero */ 01307 if (err == MP_OKAY) { 01308 if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT || 01309 mp_cmp(&s, &p) != MP_LT) 01310 err = MP_ZERO_E; 01311 } 01312 /* read hash */ 01313 if (err == MP_OKAY) { 01314 int truncLen = (int)hashlen; 01315 if (truncLen > ecc_size(key)) 01316 truncLen = ecc_size(key); 01317 err = mp_read_unsigned_bin(&e, (byte*)hash, truncLen); 01318 } 01319 01320 /* w = s^-1 mod n */ 01321 if (err == MP_OKAY) 01322 err = mp_invmod(&s, &p, &w); 01323 01324 /* u1 = ew */ 01325 if (err == MP_OKAY) 01326 err = mp_mulmod(&e, &w, &p, &u1); 01327 01328 /* u2 = rw */ 01329 if (err == MP_OKAY) 01330 err = mp_mulmod(&r, &w, &p, &u2); 01331 01332 /* find mG and mQ */ 01333 if (err == MP_OKAY) 01334 err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16); 01335 01336 if (err == MP_OKAY) 01337 err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16); 01338 if (err == MP_OKAY) 01339 mp_set(&mG->z, 1); 01340 01341 if (err == MP_OKAY) 01342 err = mp_copy(&key->pubkey.x, &mQ->x); 01343 if (err == MP_OKAY) 01344 err = mp_copy(&key->pubkey.y, &mQ->y); 01345 if (err == MP_OKAY) 01346 err = mp_copy(&key->pubkey.z, &mQ->z); 01347 01348 #ifndef ECC_SHAMIR 01349 /* compute u1*mG + u2*mQ = mG */ 01350 if (err == MP_OKAY) 01351 err = ecc_mulmod(&u1, mG, mG, &m, 0); 01352 if (err == MP_OKAY) 01353 err = ecc_mulmod(&u2, mQ, mQ, &m, 0); 01354 01355 /* find the montgomery mp */ 01356 if (err == MP_OKAY) 01357 err = mp_montgomery_setup(&m, &mp); 01358 01359 /* add them */ 01360 if (err == MP_OKAY) 01361 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp); 01362 01363 /* reduce */ 01364 if (err == MP_OKAY) 01365 err = ecc_map(mG, &m, &mp); 01366 #else 01367 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */ 01368 if (err == MP_OKAY) 01369 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m); 01370 #endif /* ECC_SHAMIR */ 01371 01372 /* v = X_x1 mod n */ 01373 if (err == MP_OKAY) 01374 err = mp_mod(&mG->x, &p, &v); 01375 01376 /* does v == r */ 01377 if (err == MP_OKAY) { 01378 if (mp_cmp(&v, &r) == MP_EQ) 01379 *stat = 1; 01380 } 01381 01382 ecc_del_point(mG); 01383 ecc_del_point(mQ); 01384 01385 mp_clear(&r); 01386 mp_clear(&s); 01387 mp_clear(&v); 01388 mp_clear(&w); 01389 mp_clear(&u1); 01390 mp_clear(&u2); 01391 mp_clear(&p); 01392 mp_clear(&e); 01393 mp_clear(&m); 01394 01395 return err; 01396 } 01397 01398 01399 /* export public ECC key in ANSI X9.63 format */ 01400 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen) 01401 { 01402 byte buf[ECC_BUFSIZE]; 01403 word32 numlen; 01404 01405 if (key == NULL || out == NULL || outLen == NULL) 01406 return ECC_BAD_ARG_E; 01407 01408 if (ecc_is_valid_idx(key->idx) == 0) { 01409 return ECC_BAD_ARG_E; 01410 } 01411 numlen = key->dp->size; 01412 01413 if (*outLen < (1 + 2*numlen)) { 01414 *outLen = 1 + 2*numlen; 01415 return BUFFER_E; 01416 } 01417 01418 /* store byte 0x04 */ 01419 out[0] = 0x04; 01420 01421 /* pad and store x */ 01422 XMEMSET(buf, 0, sizeof(buf)); 01423 mp_to_unsigned_bin(&key->pubkey.x, 01424 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x))); 01425 XMEMCPY(out+1, buf, numlen); 01426 01427 /* pad and store y */ 01428 XMEMSET(buf, 0, sizeof(buf)); 01429 mp_to_unsigned_bin(&key->pubkey.y, 01430 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y))); 01431 XMEMCPY(out+1+numlen, buf, numlen); 01432 01433 *outLen = 1 + 2*numlen; 01434 01435 return 0; 01436 } 01437 01438 01439 /* import public ECC key in ANSI X9.63 format */ 01440 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key) 01441 { 01442 int x, err; 01443 01444 01445 if (in == NULL || key == NULL) 01446 return ECC_BAD_ARG_E; 01447 01448 /* must be odd */ 01449 if ((inLen & 1) == 0) { 01450 return ECC_BAD_ARG_E; 01451 } 01452 01453 /* init key */ 01454 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, 01455 NULL, NULL) != MP_OKAY) { 01456 return MEMORY_E; 01457 } 01458 err = MP_OKAY; 01459 01460 /* check for 4, 6 or 7 */ 01461 if (in[0] != 4 && in[0] != 6 && in[0] != 7) { 01462 err = ASN_PARSE_E; 01463 } 01464 01465 /* read data */ 01466 if (err == MP_OKAY) 01467 err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1); 01468 01469 if (err == MP_OKAY) 01470 err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1), 01471 (inLen-1)>>1); 01472 01473 if (err == MP_OKAY) 01474 mp_set(&key->pubkey.z, 1); 01475 01476 if (err == MP_OKAY) { 01477 /* determine the idx */ 01478 for (x = 0; ecc_sets[x].size != 0; x++) { 01479 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) { 01480 break; 01481 } 01482 } 01483 if (ecc_sets[x].size == 0) { 01484 err = ASN_PARSE_E; 01485 } else { 01486 /* set the idx */ 01487 key->idx = x; 01488 key->dp = &ecc_sets[x]; 01489 key->type = ECC_PUBLICKEY; 01490 } 01491 } 01492 01493 if (err != MP_OKAY) { 01494 mp_clear(&key->pubkey.x); 01495 mp_clear(&key->pubkey.y); 01496 mp_clear(&key->pubkey.z); 01497 mp_clear(&key->k); 01498 } 01499 01500 return err; 01501 } 01502 01503 01504 /* ecc private key import, public key in ANSI X9.63 format, private raw */ 01505 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub, 01506 word32 pubSz, ecc_key* key) 01507 { 01508 int ret = ecc_import_x963(pub, pubSz, key); 01509 if (ret != 0) 01510 return ret; 01511 01512 key->type = ECC_PRIVATEKEY; 01513 01514 return mp_read_unsigned_bin(&key->k, priv, privSz); 01515 } 01516 01517 01518 /* key size in octets */ 01519 int ecc_size(ecc_key* key) 01520 { 01521 if (key == NULL) return 0; 01522 01523 return key->dp->size; 01524 } 01525 01526 01527 /* signature size in octets */ 01528 int ecc_sig_size(ecc_key* key) 01529 { 01530 int sz = ecc_size(key); 01531 if (sz < 0) 01532 return sz; 01533 01534 return sz * 2 + SIG_HEADER_SZ; 01535 } 01536 01537 #endif /* HAVE_ECC */
Generated on Thu Jul 14 2022 00:25:23 by
1.7.2