wolf SSL
/
CyaSSL
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Dependents: HTTPClient-SSL HTTPClient HTTPClient-SSL http_access ... more
Embed:
(wiki syntax)
Show/hide line numbers
ecc.c
00001 /* ecc.c 00002 * 00003 * Copyright (C) 2006-2014 wolfSSL Inc. 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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-crypt.h> 00035 00036 #ifdef HAVE_ECC_ENCRYPT 00037 #include <cyassl/ctaocrypt/hmac.h> 00038 #include <cyassl/ctaocrypt/aes.h> 00039 #endif 00040 00041 00042 /* map 00043 00044 ptmul -> mulmod 00045 00046 */ 00047 00048 #define ECC112 00049 #define ECC128 00050 #define ECC160 00051 #define ECC192 00052 #define ECC224 00053 #define ECC256 00054 #define ECC384 00055 #define ECC521 00056 00057 00058 00059 /* This holds the key settings. ***MUST*** be organized by size from 00060 smallest to largest. */ 00061 00062 const ecc_set_type ecc_sets[] = { 00063 #ifdef ECC112 00064 { 00065 14, 00066 "SECP112R1", 00067 "DB7C2ABF62E35E668076BEAD208B", 00068 "659EF8BA043916EEDE8911702B22", 00069 "DB7C2ABF62E35E7628DFAC6561C5", 00070 "09487239995A5EE76B55F9C2F098", 00071 "A89CE5AF8724C0A23E0E0FF77500" 00072 }, 00073 #endif 00074 #ifdef ECC128 00075 { 00076 16, 00077 "SECP128R1", 00078 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF", 00079 "E87579C11079F43DD824993C2CEE5ED3", 00080 "FFFFFFFE0000000075A30D1B9038A115", 00081 "161FF7528B899B2D0C28607CA52C5B86", 00082 "CF5AC8395BAFEB13C02DA292DDED7A83", 00083 }, 00084 #endif 00085 #ifdef ECC160 00086 { 00087 20, 00088 "SECP160R1", 00089 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF", 00090 "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45", 00091 "0100000000000000000001F4C8F927AED3CA752257", 00092 "4A96B5688EF573284664698968C38BB913CBFC82", 00093 "23A628553168947D59DCC912042351377AC5FB32", 00094 }, 00095 #endif 00096 #ifdef ECC192 00097 { 00098 24, 00099 "ECC-192", 00100 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", 00101 "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1", 00102 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831", 00103 "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012", 00104 "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811", 00105 }, 00106 #endif 00107 #ifdef ECC224 00108 { 00109 28, 00110 "ECC-224", 00111 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001", 00112 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4", 00113 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D", 00114 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21", 00115 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34", 00116 }, 00117 #endif 00118 #ifdef ECC256 00119 { 00120 32, 00121 "ECC-256", 00122 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", 00123 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B", 00124 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551", 00125 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296", 00126 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5", 00127 }, 00128 #endif 00129 #ifdef ECC384 00130 { 00131 48, 00132 "ECC-384", 00133 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF", 00134 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF", 00135 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973", 00136 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7", 00137 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F", 00138 }, 00139 #endif 00140 #ifdef ECC521 00141 { 00142 66, 00143 "ECC-521", 00144 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 00145 "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00", 00146 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409", 00147 "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66", 00148 "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650", 00149 }, 00150 #endif 00151 { 00152 0, 00153 NULL, NULL, NULL, NULL, NULL, NULL 00154 } 00155 }; 00156 00157 00158 ecc_point* ecc_new_point(void); 00159 void ecc_del_point(ecc_point* p); 00160 int ecc_map(ecc_point*, mp_int*, mp_digit*); 00161 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R, 00162 mp_int* modulus, mp_digit* mp); 00163 int ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus, 00164 mp_digit* mp); 00165 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus, 00166 int map); 00167 #ifdef ECC_SHAMIR 00168 static int ecc_mul2add(ecc_point* A, mp_int* kA, ecc_point* B, mp_int* kB, 00169 ecc_point* C, mp_int* modulus); 00170 #endif 00171 00172 00173 /* helper for either lib */ 00174 static int get_digit_count(mp_int* a) 00175 { 00176 if (a == NULL) 00177 return 0; 00178 00179 return a->used; 00180 } 00181 00182 /* helper for either lib */ 00183 static unsigned long get_digit(mp_int* a, int n) 00184 { 00185 if (a == NULL) 00186 return 0; 00187 00188 return (n >= a->used || n < 0) ? 0 : a->dp[n]; 00189 } 00190 00191 00192 #if defined(USE_FAST_MATH) 00193 00194 /* fast math accelerated version, but not for fp ecc yet */ 00195 00196 /** 00197 Add two ECC points 00198 P The point to add 00199 Q The point to add 00200 R [out] The destination of the double 00201 modulus The modulus of the field the ECC curve is in 00202 mp The "b" value from montgomery_setup() 00203 return MP_OKAY on success 00204 */ 00205 int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, 00206 mp_int* modulus, mp_digit* mp) 00207 { 00208 fp_int t1, t2, x, y, z; 00209 int err; 00210 00211 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL) 00212 return ECC_BAD_ARG_E; 00213 00214 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) { 00215 return err; 00216 } 00217 00218 /* should we dbl instead? */ 00219 fp_sub(modulus, &Q->y, &t1); 00220 if ( (fp_cmp(&P->x, &Q->x) == FP_EQ) && 00221 (get_digit_count(&Q->z) && fp_cmp(&P->z, &Q->z) == FP_EQ) && 00222 (fp_cmp(&P->y, &Q->y) == FP_EQ || fp_cmp(&P->y, &t1) == FP_EQ)) { 00223 return ecc_projective_dbl_point(P, R, modulus, mp); 00224 } 00225 00226 fp_copy(&P->x, &x); 00227 fp_copy(&P->y, &y); 00228 fp_copy(&P->z, &z); 00229 00230 /* if Z is one then these are no-operations */ 00231 if (get_digit_count(&Q->z)) { 00232 /* T1 = Z' * Z' */ 00233 fp_sqr(&Q->z, &t1); 00234 fp_montgomery_reduce(&t1, modulus, *mp); 00235 /* X = X * T1 */ 00236 fp_mul(&t1, &x, &x); 00237 fp_montgomery_reduce(&x, modulus, *mp); 00238 /* T1 = Z' * T1 */ 00239 fp_mul(&Q->z, &t1, &t1); 00240 fp_montgomery_reduce(&t1, modulus, *mp); 00241 /* Y = Y * T1 */ 00242 fp_mul(&t1, &y, &y); 00243 fp_montgomery_reduce(&y, modulus, *mp); 00244 } 00245 00246 /* T1 = Z*Z */ 00247 fp_sqr(&z, &t1); 00248 fp_montgomery_reduce(&t1, modulus, *mp); 00249 /* T2 = X' * T1 */ 00250 fp_mul(&Q->x, &t1, &t2); 00251 fp_montgomery_reduce(&t2, modulus, *mp); 00252 /* T1 = Z * T1 */ 00253 fp_mul(&z, &t1, &t1); 00254 fp_montgomery_reduce(&t1, modulus, *mp); 00255 /* T1 = Y' * T1 */ 00256 fp_mul(&Q->y, &t1, &t1); 00257 fp_montgomery_reduce(&t1, modulus, *mp); 00258 00259 /* Y = Y - T1 */ 00260 fp_sub(&y, &t1, &y); 00261 if (fp_cmp_d(&y, 0) == FP_LT) { 00262 fp_add(&y, modulus, &y); 00263 } 00264 /* T1 = 2T1 */ 00265 fp_add(&t1, &t1, &t1); 00266 if (fp_cmp(&t1, modulus) != FP_LT) { 00267 fp_sub(&t1, modulus, &t1); 00268 } 00269 /* T1 = Y + T1 */ 00270 fp_add(&t1, &y, &t1); 00271 if (fp_cmp(&t1, modulus) != FP_LT) { 00272 fp_sub(&t1, modulus, &t1); 00273 } 00274 /* X = X - T2 */ 00275 fp_sub(&x, &t2, &x); 00276 if (fp_cmp_d(&x, 0) == FP_LT) { 00277 fp_add(&x, modulus, &x); 00278 } 00279 /* T2 = 2T2 */ 00280 fp_add(&t2, &t2, &t2); 00281 if (fp_cmp(&t2, modulus) != FP_LT) { 00282 fp_sub(&t2, modulus, &t2); 00283 } 00284 /* T2 = X + T2 */ 00285 fp_add(&t2, &x, &t2); 00286 if (fp_cmp(&t2, modulus) != FP_LT) { 00287 fp_sub(&t2, modulus, &t2); 00288 } 00289 00290 /* if Z' != 1 */ 00291 if (get_digit_count(&Q->z)) { 00292 /* Z = Z * Z' */ 00293 fp_mul(&z, &Q->z, &z); 00294 fp_montgomery_reduce(&z, modulus, *mp); 00295 } 00296 00297 /* Z = Z * X */ 00298 fp_mul(&z, &x, &z); 00299 fp_montgomery_reduce(&z, modulus, *mp); 00300 00301 /* T1 = T1 * X */ 00302 fp_mul(&t1, &x, &t1); 00303 fp_montgomery_reduce(&t1, modulus, *mp); 00304 /* X = X * X */ 00305 fp_sqr(&x, &x); 00306 fp_montgomery_reduce(&x, modulus, *mp); 00307 /* T2 = T2 * x */ 00308 fp_mul(&t2, &x, &t2); 00309 fp_montgomery_reduce(&t2, modulus, *mp); 00310 /* T1 = T1 * X */ 00311 fp_mul(&t1, &x, &t1); 00312 fp_montgomery_reduce(&t1, modulus, *mp); 00313 00314 /* X = Y*Y */ 00315 fp_sqr(&y, &x); 00316 fp_montgomery_reduce(&x, modulus, *mp); 00317 /* X = X - T2 */ 00318 fp_sub(&x, &t2, &x); 00319 if (fp_cmp_d(&x, 0) == FP_LT) { 00320 fp_add(&x, modulus, &x); 00321 } 00322 00323 /* T2 = T2 - X */ 00324 fp_sub(&t2, &x, &t2); 00325 if (fp_cmp_d(&t2, 0) == FP_LT) { 00326 fp_add(&t2, modulus, &t2); 00327 } 00328 /* T2 = T2 - X */ 00329 fp_sub(&t2, &x, &t2); 00330 if (fp_cmp_d(&t2, 0) == FP_LT) { 00331 fp_add(&t2, modulus, &t2); 00332 } 00333 /* T2 = T2 * Y */ 00334 fp_mul(&t2, &y, &t2); 00335 fp_montgomery_reduce(&t2, modulus, *mp); 00336 /* Y = T2 - T1 */ 00337 fp_sub(&t2, &t1, &y); 00338 if (fp_cmp_d(&y, 0) == FP_LT) { 00339 fp_add(&y, modulus, &y); 00340 } 00341 /* Y = Y/2 */ 00342 if (fp_isodd(&y)) { 00343 fp_add(&y, modulus, &y); 00344 } 00345 fp_div_2(&y, &y); 00346 00347 fp_copy(&x, &R->x); 00348 fp_copy(&y, &R->y); 00349 fp_copy(&z, &R->z); 00350 00351 return MP_OKAY; 00352 } 00353 00354 00355 /** 00356 Double an ECC point 00357 P The point to double 00358 R [out] The destination of the double 00359 modulus The modulus of the field the ECC curve is in 00360 mp The "b" value from montgomery_setup() 00361 return MP_OKAY on success 00362 */ 00363 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus, 00364 mp_digit* mp) 00365 { 00366 fp_int t1, t2; 00367 int err; 00368 00369 if (P == NULL || R == NULL || modulus == NULL || mp == NULL) 00370 return ECC_BAD_ARG_E; 00371 00372 if (P != R) { 00373 fp_copy(&P->x, &R->x); 00374 fp_copy(&P->y, &R->y); 00375 fp_copy(&P->z, &R->z); 00376 } 00377 00378 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) { 00379 return err; 00380 } 00381 00382 /* t1 = Z * Z */ 00383 fp_sqr(&R->z, &t1); 00384 fp_montgomery_reduce(&t1, modulus, *mp); 00385 /* Z = Y * Z */ 00386 fp_mul(&R->z, &R->y, &R->z); 00387 fp_montgomery_reduce(&R->z, modulus, *mp); 00388 /* Z = 2Z */ 00389 fp_add(&R->z, &R->z, &R->z); 00390 if (fp_cmp(&R->z, modulus) != FP_LT) { 00391 fp_sub(&R->z, modulus, &R->z); 00392 } 00393 00394 /* &t2 = X - T1 */ 00395 fp_sub(&R->x, &t1, &t2); 00396 if (fp_cmp_d(&t2, 0) == FP_LT) { 00397 fp_add(&t2, modulus, &t2); 00398 } 00399 /* T1 = X + T1 */ 00400 fp_add(&t1, &R->x, &t1); 00401 if (fp_cmp(&t1, modulus) != FP_LT) { 00402 fp_sub(&t1, modulus, &t1); 00403 } 00404 /* T2 = T1 * T2 */ 00405 fp_mul(&t1, &t2, &t2); 00406 fp_montgomery_reduce(&t2, modulus, *mp); 00407 /* T1 = 2T2 */ 00408 fp_add(&t2, &t2, &t1); 00409 if (fp_cmp(&t1, modulus) != FP_LT) { 00410 fp_sub(&t1, modulus, &t1); 00411 } 00412 /* T1 = T1 + T2 */ 00413 fp_add(&t1, &t2, &t1); 00414 if (fp_cmp(&t1, modulus) != FP_LT) { 00415 fp_sub(&t1, modulus, &t1); 00416 } 00417 00418 /* Y = 2Y */ 00419 fp_add(&R->y, &R->y, &R->y); 00420 if (fp_cmp(&R->y, modulus) != FP_LT) { 00421 fp_sub(&R->y, modulus, &R->y); 00422 } 00423 /* Y = Y * Y */ 00424 fp_sqr(&R->y, &R->y); 00425 fp_montgomery_reduce(&R->y, modulus, *mp); 00426 /* T2 = Y * Y */ 00427 fp_sqr(&R->y, &t2); 00428 fp_montgomery_reduce(&t2, modulus, *mp); 00429 /* T2 = T2/2 */ 00430 if (fp_isodd(&t2)) { 00431 fp_add(&t2, modulus, &t2); 00432 } 00433 fp_div_2(&t2, &t2); 00434 /* Y = Y * X */ 00435 fp_mul(&R->y, &R->x, &R->y); 00436 fp_montgomery_reduce(&R->y, modulus, *mp); 00437 00438 /* X = T1 * T1 */ 00439 fp_sqr(&t1, &R->x); 00440 fp_montgomery_reduce(&R->x, modulus, *mp); 00441 /* X = X - Y */ 00442 fp_sub(&R->x, &R->y, &R->x); 00443 if (fp_cmp_d(&R->x, 0) == FP_LT) { 00444 fp_add(&R->x, modulus, &R->x); 00445 } 00446 /* X = X - Y */ 00447 fp_sub(&R->x, &R->y, &R->x); 00448 if (fp_cmp_d(&R->x, 0) == FP_LT) { 00449 fp_add(&R->x, modulus, &R->x); 00450 } 00451 00452 /* Y = Y - X */ 00453 fp_sub(&R->y, &R->x, &R->y); 00454 if (fp_cmp_d(&R->y, 0) == FP_LT) { 00455 fp_add(&R->y, modulus, &R->y); 00456 } 00457 /* Y = Y * T1 */ 00458 fp_mul(&R->y, &t1, &R->y); 00459 fp_montgomery_reduce(&R->y, modulus, *mp); 00460 /* Y = Y - T2 */ 00461 fp_sub(&R->y, &t2, &R->y); 00462 if (fp_cmp_d(&R->y, 0) == FP_LT) { 00463 fp_add(&R->y, modulus, &R->y); 00464 } 00465 00466 return MP_OKAY; 00467 } 00468 00469 #else /* USE_FAST_MATH */ 00470 00471 /** 00472 Add two ECC points 00473 P The point to add 00474 Q The point to add 00475 R [out] The destination of the double 00476 modulus The modulus of the field the ECC curve is in 00477 mp The "b" value from montgomery_setup() 00478 return MP_OKAY on success 00479 */ 00480 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R, 00481 mp_int* modulus, mp_digit* mp) 00482 { 00483 mp_int t1; 00484 mp_int t2; 00485 mp_int x; 00486 mp_int y; 00487 mp_int z; 00488 int err; 00489 00490 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL) 00491 return ECC_BAD_ARG_E; 00492 00493 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) { 00494 return err; 00495 } 00496 00497 /* should we dbl instead? */ 00498 err = mp_sub(modulus, &Q->y, &t1); 00499 00500 if (err == MP_OKAY) { 00501 if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) && 00502 (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) && 00503 (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) { 00504 mp_clear(&t1); 00505 mp_clear(&t2); 00506 mp_clear(&x); 00507 mp_clear(&y); 00508 mp_clear(&z); 00509 00510 return ecc_projective_dbl_point(P, R, modulus, mp); 00511 } 00512 } 00513 00514 if (err == MP_OKAY) 00515 err = mp_copy(&P->x, &x); 00516 if (err == MP_OKAY) 00517 err = mp_copy(&P->y, &y); 00518 if (err == MP_OKAY) 00519 err = mp_copy(&P->z, &z); 00520 00521 /* if Z is one then these are no-operations */ 00522 if (err == MP_OKAY) { 00523 if (get_digit_count(&Q->z)) { 00524 /* T1 = Z' * Z' */ 00525 err = mp_sqr(&Q->z, &t1); 00526 if (err == MP_OKAY) 00527 err = mp_montgomery_reduce(&t1, modulus, *mp); 00528 00529 /* X = X * T1 */ 00530 if (err == MP_OKAY) 00531 err = mp_mul(&t1, &x, &x); 00532 if (err == MP_OKAY) 00533 err = mp_montgomery_reduce(&x, modulus, *mp); 00534 00535 /* T1 = Z' * T1 */ 00536 if (err == MP_OKAY) 00537 err = mp_mul(&Q->z, &t1, &t1); 00538 if (err == MP_OKAY) 00539 err = mp_montgomery_reduce(&t1, modulus, *mp); 00540 00541 /* Y = Y * T1 */ 00542 if (err == MP_OKAY) 00543 err = mp_mul(&t1, &y, &y); 00544 if (err == MP_OKAY) 00545 err = mp_montgomery_reduce(&y, modulus, *mp); 00546 } 00547 } 00548 00549 /* T1 = Z*Z */ 00550 if (err == MP_OKAY) 00551 err = mp_sqr(&z, &t1); 00552 if (err == MP_OKAY) 00553 err = mp_montgomery_reduce(&t1, modulus, *mp); 00554 00555 /* T2 = X' * T1 */ 00556 if (err == MP_OKAY) 00557 err = mp_mul(&Q->x, &t1, &t2); 00558 if (err == MP_OKAY) 00559 err = mp_montgomery_reduce(&t2, modulus, *mp); 00560 00561 /* T1 = Z * T1 */ 00562 if (err == MP_OKAY) 00563 err = mp_mul(&z, &t1, &t1); 00564 if (err == MP_OKAY) 00565 err = mp_montgomery_reduce(&t1, modulus, *mp); 00566 00567 /* T1 = Y' * T1 */ 00568 if (err == MP_OKAY) 00569 err = mp_mul(&Q->y, &t1, &t1); 00570 if (err == MP_OKAY) 00571 err = mp_montgomery_reduce(&t1, modulus, *mp); 00572 00573 /* Y = Y - T1 */ 00574 if (err == MP_OKAY) 00575 err = mp_sub(&y, &t1, &y); 00576 if (err == MP_OKAY) { 00577 if (mp_cmp_d(&y, 0) == MP_LT) 00578 err = mp_add(&y, modulus, &y); 00579 } 00580 /* T1 = 2T1 */ 00581 if (err == MP_OKAY) 00582 err = mp_add(&t1, &t1, &t1); 00583 if (err == MP_OKAY) { 00584 if (mp_cmp(&t1, modulus) != MP_LT) 00585 err = mp_sub(&t1, modulus, &t1); 00586 } 00587 /* T1 = Y + T1 */ 00588 if (err == MP_OKAY) 00589 err = mp_add(&t1, &y, &t1); 00590 if (err == MP_OKAY) { 00591 if (mp_cmp(&t1, modulus) != MP_LT) 00592 err = mp_sub(&t1, modulus, &t1); 00593 } 00594 /* X = X - T2 */ 00595 if (err == MP_OKAY) 00596 err = mp_sub(&x, &t2, &x); 00597 if (err == MP_OKAY) { 00598 if (mp_cmp_d(&x, 0) == MP_LT) 00599 err = mp_add(&x, modulus, &x); 00600 } 00601 /* T2 = 2T2 */ 00602 if (err == MP_OKAY) 00603 err = mp_add(&t2, &t2, &t2); 00604 if (err == MP_OKAY) { 00605 if (mp_cmp(&t2, modulus) != MP_LT) 00606 err = mp_sub(&t2, modulus, &t2); 00607 } 00608 /* T2 = X + T2 */ 00609 if (err == MP_OKAY) 00610 err = mp_add(&t2, &x, &t2); 00611 if (err == MP_OKAY) { 00612 if (mp_cmp(&t2, modulus) != MP_LT) 00613 err = mp_sub(&t2, modulus, &t2); 00614 } 00615 00616 if (err == MP_OKAY) { 00617 if (get_digit_count(&Q->z)) { 00618 /* Z = Z * Z' */ 00619 err = mp_mul(&z, &Q->z, &z); 00620 if (err == MP_OKAY) 00621 err = mp_montgomery_reduce(&z, modulus, *mp); 00622 } 00623 } 00624 00625 /* Z = Z * X */ 00626 if (err == MP_OKAY) 00627 err = mp_mul(&z, &x, &z); 00628 if (err == MP_OKAY) 00629 err = mp_montgomery_reduce(&z, modulus, *mp); 00630 00631 /* T1 = T1 * X */ 00632 if (err == MP_OKAY) 00633 err = mp_mul(&t1, &x, &t1); 00634 if (err == MP_OKAY) 00635 err = mp_montgomery_reduce(&t1, modulus, *mp); 00636 00637 /* X = X * X */ 00638 if (err == MP_OKAY) 00639 err = mp_sqr(&x, &x); 00640 if (err == MP_OKAY) 00641 err = mp_montgomery_reduce(&x, modulus, *mp); 00642 00643 /* T2 = T2 * x */ 00644 if (err == MP_OKAY) 00645 err = mp_mul(&t2, &x, &t2); 00646 if (err == MP_OKAY) 00647 err = mp_montgomery_reduce(&t2, modulus, *mp); 00648 00649 /* T1 = T1 * X */ 00650 if (err == MP_OKAY) 00651 err = mp_mul(&t1, &x, &t1); 00652 if (err == MP_OKAY) 00653 err = mp_montgomery_reduce(&t1, modulus, *mp); 00654 00655 /* X = Y*Y */ 00656 if (err == MP_OKAY) 00657 err = mp_sqr(&y, &x); 00658 if (err == MP_OKAY) 00659 err = mp_montgomery_reduce(&x, modulus, *mp); 00660 00661 /* X = X - T2 */ 00662 if (err == MP_OKAY) 00663 err = mp_sub(&x, &t2, &x); 00664 if (err == MP_OKAY) { 00665 if (mp_cmp_d(&x, 0) == MP_LT) 00666 err = mp_add(&x, modulus, &x); 00667 } 00668 /* T2 = T2 - X */ 00669 if (err == MP_OKAY) 00670 err = mp_sub(&t2, &x, &t2); 00671 if (err == MP_OKAY) { 00672 if (mp_cmp_d(&t2, 0) == MP_LT) 00673 err = mp_add(&t2, modulus, &t2); 00674 } 00675 /* T2 = T2 - X */ 00676 if (err == MP_OKAY) 00677 err = mp_sub(&t2, &x, &t2); 00678 if (err == MP_OKAY) { 00679 if (mp_cmp_d(&t2, 0) == MP_LT) 00680 err = mp_add(&t2, modulus, &t2); 00681 } 00682 /* T2 = T2 * Y */ 00683 if (err == MP_OKAY) 00684 err = mp_mul(&t2, &y, &t2); 00685 if (err == MP_OKAY) 00686 err = mp_montgomery_reduce(&t2, modulus, *mp); 00687 00688 /* Y = T2 - T1 */ 00689 if (err == MP_OKAY) 00690 err = mp_sub(&t2, &t1, &y); 00691 if (err == MP_OKAY) { 00692 if (mp_cmp_d(&y, 0) == MP_LT) 00693 err = mp_add(&y, modulus, &y); 00694 } 00695 /* Y = Y/2 */ 00696 if (err == MP_OKAY) { 00697 if (mp_isodd(&y)) 00698 err = mp_add(&y, modulus, &y); 00699 } 00700 if (err == MP_OKAY) 00701 err = mp_div_2(&y, &y); 00702 00703 if (err == MP_OKAY) 00704 err = mp_copy(&x, &R->x); 00705 if (err == MP_OKAY) 00706 err = mp_copy(&y, &R->y); 00707 if (err == MP_OKAY) 00708 err = mp_copy(&z, &R->z); 00709 00710 /* clean up */ 00711 mp_clear(&t1); 00712 mp_clear(&t2); 00713 mp_clear(&x); 00714 mp_clear(&y); 00715 mp_clear(&z); 00716 00717 return err; 00718 } 00719 00720 00721 /** 00722 Double an ECC point 00723 P The point to double 00724 R [out] The destination of the double 00725 modulus The modulus of the field the ECC curve is in 00726 mp The "b" value from montgomery_setup() 00727 return MP_OKAY on success 00728 */ 00729 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus, 00730 mp_digit* mp) 00731 { 00732 mp_int t1; 00733 mp_int t2; 00734 int err; 00735 00736 if (P == NULL || R == NULL || modulus == NULL || mp == NULL) 00737 return ECC_BAD_ARG_E; 00738 00739 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) { 00740 return err; 00741 } 00742 00743 if (P != R) { 00744 err = mp_copy(&P->x, &R->x); 00745 if (err == MP_OKAY) 00746 err = mp_copy(&P->y, &R->y); 00747 if (err == MP_OKAY) 00748 err = mp_copy(&P->z, &R->z); 00749 } 00750 00751 /* t1 = Z * Z */ 00752 if (err == MP_OKAY) 00753 err = mp_sqr(&R->z, &t1); 00754 if (err == MP_OKAY) 00755 err = mp_montgomery_reduce(&t1, modulus, *mp); 00756 00757 /* Z = Y * Z */ 00758 if (err == MP_OKAY) 00759 err = mp_mul(&R->z, &R->y, &R->z); 00760 if (err == MP_OKAY) 00761 err = mp_montgomery_reduce(&R->z, modulus, *mp); 00762 00763 /* Z = 2Z */ 00764 if (err == MP_OKAY) 00765 err = mp_add(&R->z, &R->z, &R->z); 00766 if (err == MP_OKAY) { 00767 if (mp_cmp(&R->z, modulus) != MP_LT) 00768 err = mp_sub(&R->z, modulus, &R->z); 00769 } 00770 00771 /* T2 = X - T1 */ 00772 if (err == MP_OKAY) 00773 err = mp_sub(&R->x, &t1, &t2); 00774 if (err == MP_OKAY) { 00775 if (mp_cmp_d(&t2, 0) == MP_LT) 00776 err = mp_add(&t2, modulus, &t2); 00777 } 00778 /* T1 = X + T1 */ 00779 if (err == MP_OKAY) 00780 err = mp_add(&t1, &R->x, &t1); 00781 if (err == MP_OKAY) { 00782 if (mp_cmp(&t1, modulus) != MP_LT) 00783 err = mp_sub(&t1, modulus, &t1); 00784 } 00785 /* T2 = T1 * T2 */ 00786 if (err == MP_OKAY) 00787 err = mp_mul(&t1, &t2, &t2); 00788 if (err == MP_OKAY) 00789 err = mp_montgomery_reduce(&t2, modulus, *mp); 00790 00791 /* T1 = 2T2 */ 00792 if (err == MP_OKAY) 00793 err = mp_add(&t2, &t2, &t1); 00794 if (err == MP_OKAY) { 00795 if (mp_cmp(&t1, modulus) != MP_LT) 00796 err = mp_sub(&t1, modulus, &t1); 00797 } 00798 /* T1 = T1 + T2 */ 00799 if (err == MP_OKAY) 00800 err = mp_add(&t1, &t2, &t1); 00801 if (err == MP_OKAY) { 00802 if (mp_cmp(&t1, modulus) != MP_LT) 00803 err = mp_sub(&t1, modulus, &t1); 00804 } 00805 /* Y = 2Y */ 00806 if (err == MP_OKAY) 00807 err = mp_add(&R->y, &R->y, &R->y); 00808 if (err == MP_OKAY) { 00809 if (mp_cmp(&R->y, modulus) != MP_LT) 00810 err = mp_sub(&R->y, modulus, &R->y); 00811 } 00812 /* Y = Y * Y */ 00813 if (err == MP_OKAY) 00814 err = mp_sqr(&R->y, &R->y); 00815 if (err == MP_OKAY) 00816 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00817 00818 /* T2 = Y * Y */ 00819 if (err == MP_OKAY) 00820 err = mp_sqr(&R->y, &t2); 00821 if (err == MP_OKAY) 00822 err = mp_montgomery_reduce(&t2, modulus, *mp); 00823 00824 /* T2 = T2/2 */ 00825 if (err == MP_OKAY) { 00826 if (mp_isodd(&t2)) 00827 err = mp_add(&t2, modulus, &t2); 00828 } 00829 if (err == MP_OKAY) 00830 err = mp_div_2(&t2, &t2); 00831 00832 /* Y = Y * X */ 00833 if (err == MP_OKAY) 00834 err = mp_mul(&R->y, &R->x, &R->y); 00835 if (err == MP_OKAY) 00836 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00837 00838 /* X = T1 * T1 */ 00839 if (err == MP_OKAY) 00840 err = mp_sqr(&t1, &R->x); 00841 if (err == MP_OKAY) 00842 err = mp_montgomery_reduce(&R->x, modulus, *mp); 00843 00844 /* X = X - Y */ 00845 if (err == MP_OKAY) 00846 err = mp_sub(&R->x, &R->y, &R->x); 00847 if (err == MP_OKAY) { 00848 if (mp_cmp_d(&R->x, 0) == MP_LT) 00849 err = mp_add(&R->x, modulus, &R->x); 00850 } 00851 /* X = X - Y */ 00852 if (err == MP_OKAY) 00853 err = mp_sub(&R->x, &R->y, &R->x); 00854 if (err == MP_OKAY) { 00855 if (mp_cmp_d(&R->x, 0) == MP_LT) 00856 err = mp_add(&R->x, modulus, &R->x); 00857 } 00858 /* Y = Y - X */ 00859 if (err == MP_OKAY) 00860 err = mp_sub(&R->y, &R->x, &R->y); 00861 if (err == MP_OKAY) { 00862 if (mp_cmp_d(&R->y, 0) == MP_LT) 00863 err = mp_add(&R->y, modulus, &R->y); 00864 } 00865 /* Y = Y * T1 */ 00866 if (err == MP_OKAY) 00867 err = mp_mul(&R->y, &t1, &R->y); 00868 if (err == MP_OKAY) 00869 err = mp_montgomery_reduce(&R->y, modulus, *mp); 00870 00871 /* Y = Y - T2 */ 00872 if (err == MP_OKAY) 00873 err = mp_sub(&R->y, &t2, &R->y); 00874 if (err == MP_OKAY) { 00875 if (mp_cmp_d(&R->y, 0) == MP_LT) 00876 err = mp_add(&R->y, modulus, &R->y); 00877 } 00878 00879 /* clean up */ 00880 mp_clear(&t1); 00881 mp_clear(&t2); 00882 00883 return err; 00884 } 00885 00886 #endif /* USE_FAST_MATH */ 00887 00888 /** 00889 Map a projective jacbobian point back to affine space 00890 P [in/out] The point to map 00891 modulus The modulus of the field the ECC curve is in 00892 mp The "b" value from montgomery_setup() 00893 return MP_OKAY on success 00894 */ 00895 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp) 00896 { 00897 mp_int t1; 00898 mp_int t2; 00899 int err; 00900 00901 if (P == NULL || mp == NULL || modulus == NULL) 00902 return ECC_BAD_ARG_E; 00903 00904 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) { 00905 return MEMORY_E; 00906 } 00907 00908 /* first map z back to normal */ 00909 err = mp_montgomery_reduce(&P->z, modulus, *mp); 00910 00911 /* get 1/z */ 00912 if (err == MP_OKAY) 00913 err = mp_invmod(&P->z, modulus, &t1); 00914 00915 /* get 1/z^2 and 1/z^3 */ 00916 if (err == MP_OKAY) 00917 err = mp_sqr(&t1, &t2); 00918 if (err == MP_OKAY) 00919 err = mp_mod(&t2, modulus, &t2); 00920 if (err == MP_OKAY) 00921 err = mp_mul(&t1, &t2, &t1); 00922 if (err == MP_OKAY) 00923 err = mp_mod(&t1, modulus, &t1); 00924 00925 /* multiply against x/y */ 00926 if (err == MP_OKAY) 00927 err = mp_mul(&P->x, &t2, &P->x); 00928 if (err == MP_OKAY) 00929 err = mp_montgomery_reduce(&P->x, modulus, *mp); 00930 if (err == MP_OKAY) 00931 err = mp_mul(&P->y, &t1, &P->y); 00932 if (err == MP_OKAY) 00933 err = mp_montgomery_reduce(&P->y, modulus, *mp); 00934 00935 if (err == MP_OKAY) 00936 mp_set(&P->z, 1); 00937 00938 /* clean up */ 00939 mp_clear(&t1); 00940 mp_clear(&t2); 00941 00942 return err; 00943 } 00944 00945 00946 #ifndef ECC_TIMING_RESISTANT 00947 00948 /* size of sliding window, don't change this! */ 00949 #define WINSIZE 4 00950 00951 /** 00952 Perform a point multiplication 00953 k The scalar to multiply by 00954 G The base point 00955 R [out] Destination for kG 00956 modulus The modulus of the field the ECC curve is in 00957 map Boolean whether to map back to affine or not 00958 (1==map, 0 == leave in projective) 00959 return MP_OKAY on success 00960 */ 00961 #ifdef FP_ECC 00962 static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, 00963 mp_int* modulus, int map) 00964 #else 00965 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus, 00966 int map) 00967 #endif 00968 { 00969 ecc_point *tG, *M[8]; 00970 int i, j, err; 00971 mp_int mu; 00972 mp_digit mp; 00973 unsigned long buf; 00974 int first = 1, bitbuf = 0, bitcpy = 0, bitcnt = 0, mode = 0, 00975 digidx = 0; 00976 00977 if (k == NULL || G == NULL || R == NULL || modulus == NULL) 00978 return ECC_BAD_ARG_E; 00979 00980 /* init montgomery reduction */ 00981 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) { 00982 return err; 00983 } 00984 if ((err = mp_init(&mu)) != MP_OKAY) { 00985 return err; 00986 } 00987 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) { 00988 mp_clear(&mu); 00989 return err; 00990 } 00991 00992 /* alloc ram for window temps */ 00993 for (i = 0; i < 8; i++) { 00994 M[i] = ecc_new_point(); 00995 if (M[i] == NULL) { 00996 for (j = 0; j < i; j++) { 00997 ecc_del_point(M[j]); 00998 } 00999 mp_clear(&mu); 01000 return MEMORY_E; 01001 } 01002 } 01003 01004 /* make a copy of G incase R==G */ 01005 tG = ecc_new_point(); 01006 if (tG == NULL) 01007 err = MEMORY_E; 01008 01009 /* tG = G and convert to montgomery */ 01010 if (err == MP_OKAY) { 01011 if (mp_cmp_d(&mu, 1) == MP_EQ) { 01012 err = mp_copy(&G->x, &tG->x); 01013 if (err == MP_OKAY) 01014 err = mp_copy(&G->y, &tG->y); 01015 if (err == MP_OKAY) 01016 err = mp_copy(&G->z, &tG->z); 01017 } else { 01018 err = mp_mulmod(&G->x, &mu, modulus, &tG->x); 01019 if (err == MP_OKAY) 01020 err = mp_mulmod(&G->y, &mu, modulus, &tG->y); 01021 if (err == MP_OKAY) 01022 err = mp_mulmod(&G->z, &mu, modulus, &tG->z); 01023 } 01024 } 01025 mp_clear(&mu); 01026 01027 /* calc the M tab, which holds kG for k==8..15 */ 01028 /* M[0] == 8G */ 01029 if (err == MP_OKAY) 01030 err = ecc_projective_dbl_point(tG, M[0], modulus, &mp); 01031 if (err == MP_OKAY) 01032 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp); 01033 if (err == MP_OKAY) 01034 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp); 01035 01036 /* now find (8+k)G for k=1..7 */ 01037 if (err == MP_OKAY) 01038 for (j = 9; j < 16; j++) { 01039 err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp); 01040 if (err != MP_OKAY) break; 01041 } 01042 01043 /* setup sliding window */ 01044 if (err == MP_OKAY) { 01045 mode = 0; 01046 bitcnt = 1; 01047 buf = 0; 01048 digidx = get_digit_count(k) - 1; 01049 bitcpy = bitbuf = 0; 01050 first = 1; 01051 01052 /* perform ops */ 01053 for (;;) { 01054 /* grab next digit as required */ 01055 if (--bitcnt == 0) { 01056 if (digidx == -1) { 01057 break; 01058 } 01059 buf = get_digit(k, digidx); 01060 bitcnt = (int) DIGIT_BIT; 01061 --digidx; 01062 } 01063 01064 /* grab the next msb from the ltiplicand */ 01065 i = (int)(buf >> (DIGIT_BIT - 1)) & 1; 01066 buf <<= 1; 01067 01068 /* skip leading zero bits */ 01069 if (mode == 0 && i == 0) 01070 continue; 01071 01072 /* if the bit is zero and mode == 1 then we double */ 01073 if (mode == 1 && i == 0) { 01074 err = ecc_projective_dbl_point(R, R, modulus, &mp); 01075 if (err != MP_OKAY) break; 01076 continue; 01077 } 01078 01079 /* else we add it to the window */ 01080 bitbuf |= (i << (WINSIZE - ++bitcpy)); 01081 mode = 2; 01082 01083 if (bitcpy == WINSIZE) { 01084 /* if this is the first window we do a simple copy */ 01085 if (first == 1) { 01086 /* R = kG [k = first window] */ 01087 err = mp_copy(&M[bitbuf-8]->x, &R->x); 01088 if (err != MP_OKAY) break; 01089 01090 err = mp_copy(&M[bitbuf-8]->y, &R->y); 01091 if (err != MP_OKAY) break; 01092 01093 err = mp_copy(&M[bitbuf-8]->z, &R->z); 01094 first = 0; 01095 } else { 01096 /* normal window */ 01097 /* ok window is filled so double as required and add */ 01098 /* double first */ 01099 for (j = 0; j < WINSIZE; j++) { 01100 err = ecc_projective_dbl_point(R, R, modulus, &mp); 01101 if (err != MP_OKAY) break; 01102 } 01103 if (err != MP_OKAY) break; /* out of first for(;;) */ 01104 01105 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */ 01106 err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp); 01107 } 01108 if (err != MP_OKAY) break; 01109 /* empty window and reset */ 01110 bitcpy = bitbuf = 0; 01111 mode = 1; 01112 } 01113 } 01114 } 01115 01116 /* if bits remain then double/add */ 01117 if (err == MP_OKAY) { 01118 if (mode == 2 && bitcpy > 0) { 01119 /* double then add */ 01120 for (j = 0; j < bitcpy; j++) { 01121 /* only double if we have had at least one add first */ 01122 if (first == 0) { 01123 err = ecc_projective_dbl_point(R, R, modulus, &mp); 01124 if (err != MP_OKAY) break; 01125 } 01126 01127 bitbuf <<= 1; 01128 if ((bitbuf & (1 << WINSIZE)) != 0) { 01129 if (first == 1) { 01130 /* first add, so copy */ 01131 err = mp_copy(&tG->x, &R->x); 01132 if (err != MP_OKAY) break; 01133 01134 err = mp_copy(&tG->y, &R->y); 01135 if (err != MP_OKAY) break; 01136 01137 err = mp_copy(&tG->z, &R->z); 01138 if (err != MP_OKAY) break; 01139 first = 0; 01140 } else { 01141 /* then add */ 01142 err = ecc_projective_add_point(R, tG, R, modulus, &mp); 01143 if (err != MP_OKAY) break; 01144 } 01145 } 01146 } 01147 } 01148 } 01149 01150 /* map R back from projective space */ 01151 if (err == MP_OKAY && map) 01152 err = ecc_map(R, modulus, &mp); 01153 01154 mp_clear(&mu); 01155 ecc_del_point(tG); 01156 for (i = 0; i < 8; i++) { 01157 ecc_del_point(M[i]); 01158 } 01159 return err; 01160 } 01161 01162 #undef WINSIZE 01163 #endif /* ECC_TIMING_RESISTANT */ 01164 01165 01166 /** 01167 Allocate a new ECC point 01168 return A newly allocated point or NULL on error 01169 */ 01170 ecc_point* ecc_new_point(void) 01171 { 01172 ecc_point* p; 01173 p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT); 01174 if (p == NULL) { 01175 return NULL; 01176 } 01177 XMEMSET(p, 0, sizeof(ecc_point)); 01178 if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) { 01179 XFREE(p, 0, DYNAMIC_TYPE_BIGINT); 01180 return NULL; 01181 } 01182 return p; 01183 } 01184 01185 /** Free an ECC point from memory 01186 p The point to free 01187 */ 01188 void ecc_del_point(ecc_point* p) 01189 { 01190 /* prevents free'ing null arguments */ 01191 if (p != NULL) { 01192 mp_clear(&p->x); 01193 mp_clear(&p->y); 01194 mp_clear(&p->z); 01195 XFREE(p, 0, DYNAMIC_TYPE_BIGINT); 01196 } 01197 } 01198 01199 01200 /** Returns whether an ECC idx is valid or not 01201 n The idx number to check 01202 return 1 if valid, 0 if not 01203 */ 01204 static int ecc_is_valid_idx(int n) 01205 { 01206 int x; 01207 01208 for (x = 0; ecc_sets[x].size != 0; x++) 01209 ; 01210 /* -1 is a valid index --- indicating that the domain params 01211 were supplied by the user */ 01212 if ((n >= -1) && (n < x)) { 01213 return 1; 01214 } 01215 return 0; 01216 } 01217 01218 01219 /** 01220 Create an ECC shared secret between two keys 01221 private_key The private ECC key 01222 public_key The public key 01223 out [out] Destination of the shared secret 01224 Conforms to EC-DH from ANSI X9.63 01225 outlen [in/out] The max size and resulting size of the shared secret 01226 return MP_OKAY if successful 01227 */ 01228 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out, 01229 word32* outlen) 01230 { 01231 word32 x = 0; 01232 ecc_point* result; 01233 mp_int prime; 01234 int err; 01235 01236 if (private_key == NULL || public_key == NULL || out == NULL || 01237 outlen == NULL) 01238 return BAD_FUNC_ARG; 01239 01240 /* type valid? */ 01241 if (private_key->type != ECC_PRIVATEKEY) { 01242 return ECC_BAD_ARG_E; 01243 } 01244 01245 if (ecc_is_valid_idx(private_key->idx) == 0 || 01246 ecc_is_valid_idx(public_key->idx) == 0) 01247 return ECC_BAD_ARG_E; 01248 01249 if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0) 01250 return ECC_BAD_ARG_E; 01251 01252 /* make new point */ 01253 result = ecc_new_point(); 01254 if (result == NULL) { 01255 return MEMORY_E; 01256 } 01257 01258 if ((err = mp_init(&prime)) != MP_OKAY) { 01259 ecc_del_point(result); 01260 return err; 01261 } 01262 01263 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16); 01264 01265 if (err == MP_OKAY) 01266 err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1); 01267 01268 if (err == MP_OKAY) { 01269 x = mp_unsigned_bin_size(&prime); 01270 if (*outlen < x) 01271 err = BUFFER_E; 01272 } 01273 01274 if (err == MP_OKAY) { 01275 XMEMSET(out, 0, x); 01276 err = mp_to_unsigned_bin(&result->x,out + (x - 01277 mp_unsigned_bin_size(&result->x))); 01278 *outlen = x; 01279 } 01280 01281 mp_clear(&prime); 01282 ecc_del_point(result); 01283 01284 return err; 01285 } 01286 01287 01288 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp); 01289 01290 /** 01291 Make a new ECC key 01292 rng An active RNG state 01293 keysize The keysize for the new key (in octets from 20 to 65 bytes) 01294 key [out] Destination of the newly created key 01295 return MP_OKAY if successful, 01296 upon error all allocated memory will be freed 01297 */ 01298 int ecc_make_key(RNG* rng, int keysize, ecc_key* key) 01299 { 01300 int x, err; 01301 01302 if (key == NULL || rng == NULL) 01303 return ECC_BAD_ARG_E; 01304 01305 /* find key size */ 01306 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++) 01307 ; 01308 keysize = ecc_sets[x].size; 01309 01310 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) { 01311 return BAD_FUNC_ARG; 01312 } 01313 err = ecc_make_key_ex(rng, key, &ecc_sets[x]); 01314 key->idx = x; 01315 01316 return err; 01317 } 01318 01319 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp) 01320 { 01321 int err; 01322 ecc_point* base; 01323 mp_int prime; 01324 mp_int order; 01325 #ifdef CYASSL_SMALL_STACK 01326 byte* buf; 01327 #else 01328 byte buf[ECC_MAXSIZE]; 01329 #endif 01330 int keysize; 01331 01332 if (key == NULL || rng == NULL || dp == NULL) 01333 return ECC_BAD_ARG_E; 01334 01335 #ifdef CYASSL_SMALL_STACK 01336 buf = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01337 if (buf == NULL) 01338 return MEMORY_E; 01339 #endif 01340 01341 key->idx = -1; 01342 key->dp = dp; 01343 keysize = dp->size; 01344 01345 /* allocate ram */ 01346 base = NULL; 01347 01348 /* make up random string */ 01349 err = RNG_GenerateBlock(rng, buf, keysize); 01350 if (err == 0) 01351 buf[0] |= 0x0c; 01352 01353 /* setup the key variables */ 01354 if (err == 0) { 01355 err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, 01356 &key->k, &prime, &order); 01357 if (err != MP_OKAY) 01358 err = MEMORY_E; 01359 } 01360 01361 if (err == MP_OKAY) { 01362 base = ecc_new_point(); 01363 if (base == NULL) 01364 err = MEMORY_E; 01365 } 01366 01367 /* read in the specs for this key */ 01368 if (err == MP_OKAY) 01369 err = mp_read_radix(&prime, (char *)key->dp->prime, 16); 01370 if (err == MP_OKAY) 01371 err = mp_read_radix(&order, (char *)key->dp->order, 16); 01372 if (err == MP_OKAY) 01373 err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16); 01374 if (err == MP_OKAY) 01375 err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16); 01376 01377 if (err == MP_OKAY) 01378 mp_set(&base->z, 1); 01379 if (err == MP_OKAY) 01380 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize); 01381 01382 /* the key should be smaller than the order of base point */ 01383 if (err == MP_OKAY) { 01384 if (mp_cmp(&key->k, &order) != MP_LT) 01385 err = mp_mod(&key->k, &order, &key->k); 01386 } 01387 /* make the public key */ 01388 if (err == MP_OKAY) 01389 err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1); 01390 if (err == MP_OKAY) 01391 key->type = ECC_PRIVATEKEY; 01392 01393 if (err != MP_OKAY) { 01394 /* clean up */ 01395 mp_clear(&key->pubkey.x); 01396 mp_clear(&key->pubkey.y); 01397 mp_clear(&key->pubkey.z); 01398 mp_clear(&key->k); 01399 } 01400 ecc_del_point(base); 01401 mp_clear(&prime); 01402 mp_clear(&order); 01403 01404 #ifdef ECC_CLEAN_STACK 01405 XMEMSET(buf, 0, ECC_MAXSIZE); 01406 #endif 01407 01408 #ifdef CYASSL_SMALL_STACK 01409 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01410 #endif 01411 01412 return err; 01413 } 01414 01415 01416 /* Setup dynamic pointers is using normal math for proper freeing */ 01417 void ecc_init(ecc_key* key) 01418 { 01419 (void)key; 01420 #ifndef USE_FAST_MATH 01421 key->pubkey.x.dp = NULL; 01422 key->pubkey.y.dp = NULL; 01423 key->pubkey.z.dp = NULL; 01424 01425 key->k.dp = NULL; 01426 #endif 01427 } 01428 01429 01430 /** 01431 Sign a message digest 01432 in The message digest to sign 01433 inlen The length of the digest 01434 out [out] The destination for the signature 01435 outlen [in/out] The max size and resulting size of the signature 01436 key A private ECC key 01437 return MP_OKAY if successful 01438 */ 01439 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen, 01440 RNG* rng, ecc_key* key) 01441 { 01442 mp_int r; 01443 mp_int s; 01444 mp_int e; 01445 mp_int p; 01446 int err; 01447 01448 if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL) 01449 return ECC_BAD_ARG_E; 01450 01451 /* is this a private key? */ 01452 if (key->type != ECC_PRIVATEKEY) { 01453 return ECC_BAD_ARG_E; 01454 } 01455 01456 /* is the IDX valid ? */ 01457 if (ecc_is_valid_idx(key->idx) != 1) { 01458 return ECC_BAD_ARG_E; 01459 } 01460 01461 /* get the hash and load it as a bignum into 'e' */ 01462 /* init the bignums */ 01463 if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) { 01464 return err; 01465 } 01466 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01467 01468 if (err == MP_OKAY) { 01469 /* we may need to truncate if hash is longer than key size */ 01470 word32 orderBits = mp_count_bits(&p); 01471 01472 /* truncate down to byte size, may be all that's needed */ 01473 if ( (CYASSL_BIT_SIZE * inlen) > orderBits) 01474 inlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE; 01475 err = mp_read_unsigned_bin(&e, (byte*)in, inlen); 01476 01477 /* may still need bit truncation too */ 01478 if (err == MP_OKAY && (CYASSL_BIT_SIZE * inlen) > orderBits) 01479 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7)); 01480 } 01481 01482 /* make up a key and export the public copy */ 01483 if (err == MP_OKAY) { 01484 ecc_key pubkey; 01485 ecc_init(&pubkey); 01486 for (;;) { 01487 err = ecc_make_key_ex(rng, &pubkey, key->dp); 01488 if (err != MP_OKAY) break; 01489 01490 /* find r = x1 mod n */ 01491 err = mp_mod(&pubkey.pubkey.x, &p, &r); 01492 if (err != MP_OKAY) break; 01493 01494 if (mp_iszero(&r) == MP_YES) 01495 ecc_free(&pubkey); 01496 else { 01497 /* find s = (e + xr)/k */ 01498 err = mp_invmod(&pubkey.k, &p, &pubkey.k); 01499 if (err != MP_OKAY) break; 01500 01501 err = mp_mulmod(&key->k, &r, &p, &s); /* s = xr */ 01502 if (err != MP_OKAY) break; 01503 01504 err = mp_add(&e, &s, &s); /* s = e + xr */ 01505 if (err != MP_OKAY) break; 01506 01507 err = mp_mod(&s, &p, &s); /* s = e + xr */ 01508 if (err != MP_OKAY) break; 01509 01510 err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */ 01511 if (err != MP_OKAY) break; 01512 01513 ecc_free(&pubkey); 01514 if (mp_iszero(&s) == MP_NO) 01515 break; 01516 } 01517 } 01518 ecc_free(&pubkey); 01519 } 01520 01521 /* store as SEQUENCE { r, s -- integer } */ 01522 if (err == MP_OKAY) 01523 err = StoreECC_DSA_Sig(out, outlen, &r, &s); 01524 01525 mp_clear(&r); 01526 mp_clear(&s); 01527 mp_clear(&p); 01528 mp_clear(&e); 01529 01530 return err; 01531 } 01532 01533 01534 /** 01535 Free an ECC key from memory 01536 key The key you wish to free 01537 */ 01538 void ecc_free(ecc_key* key) 01539 { 01540 if (key == NULL) 01541 return; 01542 01543 mp_clear(&key->pubkey.x); 01544 mp_clear(&key->pubkey.y); 01545 mp_clear(&key->pubkey.z); 01546 mp_clear(&key->k); 01547 } 01548 01549 01550 #ifdef USE_FAST_MATH 01551 #define GEN_MEM_ERR FP_MEM 01552 #else 01553 #define GEN_MEM_ERR MP_MEM 01554 #endif 01555 01556 #ifdef ECC_SHAMIR 01557 01558 /** Computes kA*A + kB*B = C using Shamir's Trick 01559 A First point to multiply 01560 kA What to multiple A by 01561 B Second point to multiply 01562 kB What to multiple B by 01563 C [out] Destination point (can overlap with A or B) 01564 modulus Modulus for curve 01565 return MP_OKAY on success 01566 */ 01567 #ifdef FP_ECC 01568 static int normal_ecc_mul2add(ecc_point* A, mp_int* kA, 01569 ecc_point* B, mp_int* kB, 01570 ecc_point* C, mp_int* modulus) 01571 #else 01572 static int ecc_mul2add(ecc_point* A, mp_int* kA, 01573 ecc_point* B, mp_int* kB, 01574 ecc_point* C, mp_int* modulus) 01575 #endif 01576 { 01577 ecc_point* precomp[16]; 01578 unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble; 01579 unsigned char* tA; 01580 unsigned char* tB; 01581 int err = MP_OKAY, first; 01582 int muInit = 0; 01583 int tableInit = 0; 01584 mp_digit mp; 01585 mp_int mu; 01586 01587 /* argchks */ 01588 if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL || 01589 modulus == NULL) 01590 return ECC_BAD_ARG_E; 01591 01592 01593 /* allocate memory */ 01594 tA = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01595 if (tA == NULL) { 01596 return GEN_MEM_ERR; 01597 } 01598 tB = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01599 if (tB == NULL) { 01600 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01601 return GEN_MEM_ERR; 01602 } 01603 XMEMSET(tA, 0, ECC_BUFSIZE); 01604 XMEMSET(tB, 0, ECC_BUFSIZE); 01605 01606 /* get sizes */ 01607 lenA = mp_unsigned_bin_size(kA); 01608 lenB = mp_unsigned_bin_size(kB); 01609 len = MAX(lenA, lenB); 01610 01611 /* sanity check */ 01612 if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) { 01613 err = BAD_FUNC_ARG; 01614 } 01615 01616 if (err == MP_OKAY) { 01617 /* extract and justify kA */ 01618 err = mp_to_unsigned_bin(kA, (len - lenA) + tA); 01619 01620 /* extract and justify kB */ 01621 if (err == MP_OKAY) 01622 err = mp_to_unsigned_bin(kB, (len - lenB) + tB); 01623 01624 /* allocate the table */ 01625 if (err == MP_OKAY) { 01626 for (x = 0; x < 16; x++) { 01627 precomp[x] = ecc_new_point(); 01628 if (precomp[x] == NULL) { 01629 for (y = 0; y < x; ++y) { 01630 ecc_del_point(precomp[y]); 01631 } 01632 err = GEN_MEM_ERR; 01633 break; 01634 } 01635 } 01636 } 01637 } 01638 01639 if (err == MP_OKAY) 01640 tableInit = 1; 01641 01642 if (err == MP_OKAY) 01643 /* init montgomery reduction */ 01644 err = mp_montgomery_setup(modulus, &mp); 01645 01646 if (err == MP_OKAY) 01647 err = mp_init(&mu); 01648 if (err == MP_OKAY) 01649 muInit = 1; 01650 01651 if (err == MP_OKAY) 01652 err = mp_montgomery_calc_normalization(&mu, modulus); 01653 01654 if (err == MP_OKAY) 01655 /* copy ones ... */ 01656 err = mp_mulmod(&A->x, &mu, modulus, &precomp[1]->x); 01657 01658 if (err == MP_OKAY) 01659 err = mp_mulmod(&A->y, &mu, modulus, &precomp[1]->y); 01660 if (err == MP_OKAY) 01661 err = mp_mulmod(&A->z, &mu, modulus, &precomp[1]->z); 01662 01663 if (err == MP_OKAY) 01664 err = mp_mulmod(&B->x, &mu, modulus, &precomp[1<<2]->x); 01665 if (err == MP_OKAY) 01666 err = mp_mulmod(&B->y, &mu, modulus, &precomp[1<<2]->y); 01667 if (err == MP_OKAY) 01668 err = mp_mulmod(&B->z, &mu, modulus, &precomp[1<<2]->z); 01669 01670 if (err == MP_OKAY) 01671 /* precomp [i,0](A + B) table */ 01672 err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp); 01673 01674 if (err == MP_OKAY) 01675 err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3], 01676 modulus, &mp); 01677 if (err == MP_OKAY) 01678 /* precomp [0,i](A + B) table */ 01679 err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp); 01680 01681 if (err == MP_OKAY) 01682 err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2], 01683 modulus, &mp); 01684 01685 if (err == MP_OKAY) { 01686 /* precomp [i,j](A + B) table (i != 0, j != 0) */ 01687 for (x = 1; x < 4; x++) { 01688 for (y = 1; y < 4; y++) { 01689 if (err == MP_OKAY) 01690 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)], 01691 precomp[x+(y<<2)], modulus, &mp); 01692 } 01693 } 01694 } 01695 01696 if (err == MP_OKAY) { 01697 nibble = 3; 01698 first = 1; 01699 bitbufA = tA[0]; 01700 bitbufB = tB[0]; 01701 01702 /* for every byte of the multiplicands */ 01703 for (x = -1;; ) { 01704 /* grab a nibble */ 01705 if (++nibble == 4) { 01706 ++x; if (x == len) break; 01707 bitbufA = tA[x]; 01708 bitbufB = tB[x]; 01709 nibble = 0; 01710 } 01711 01712 /* extract two bits from both, shift/update */ 01713 nA = (bitbufA >> 6) & 0x03; 01714 nB = (bitbufB >> 6) & 0x03; 01715 bitbufA = (bitbufA << 2) & 0xFF; 01716 bitbufB = (bitbufB << 2) & 0xFF; 01717 01718 /* if both zero, if first, continue */ 01719 if ((nA == 0) && (nB == 0) && (first == 1)) { 01720 continue; 01721 } 01722 01723 /* double twice, only if this isn't the first */ 01724 if (first == 0) { 01725 /* double twice */ 01726 if (err == MP_OKAY) 01727 err = ecc_projective_dbl_point(C, C, modulus, &mp); 01728 if (err == MP_OKAY) 01729 err = ecc_projective_dbl_point(C, C, modulus, &mp); 01730 else 01731 break; 01732 } 01733 01734 /* if not both zero */ 01735 if ((nA != 0) || (nB != 0)) { 01736 if (first == 1) { 01737 /* if first, copy from table */ 01738 first = 0; 01739 if (err == MP_OKAY) 01740 err = mp_copy(&precomp[nA + (nB<<2)]->x, &C->x); 01741 01742 if (err == MP_OKAY) 01743 err = mp_copy(&precomp[nA + (nB<<2)]->y, &C->y); 01744 01745 if (err == MP_OKAY) 01746 err = mp_copy(&precomp[nA + (nB<<2)]->z, &C->z); 01747 else 01748 break; 01749 } else { 01750 /* if not first, add from table */ 01751 if (err == MP_OKAY) 01752 err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C, 01753 modulus, &mp); 01754 else 01755 break; 01756 } 01757 } 01758 } 01759 } 01760 01761 if (err == MP_OKAY) 01762 /* reduce to affine */ 01763 err = ecc_map(C, modulus, &mp); 01764 01765 /* clean up */ 01766 if (muInit) 01767 mp_clear(&mu); 01768 01769 if (tableInit) { 01770 for (x = 0; x < 16; x++) { 01771 ecc_del_point(precomp[x]); 01772 } 01773 } 01774 #ifdef ECC_CLEAN_STACK 01775 XMEMSET(tA, 0, ECC_BUFSIZE); 01776 XMEMSET(tB, 0, ECC_BUFSIZE); 01777 #endif 01778 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01779 XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01780 01781 return err; 01782 } 01783 01784 01785 #endif /* ECC_SHAMIR */ 01786 01787 01788 01789 /* verify 01790 * 01791 * w = s^-1 mod n 01792 * u1 = xw 01793 * u2 = rw 01794 * X = u1*G + u2*Q 01795 * v = X_x1 mod n 01796 * accept if v == r 01797 */ 01798 01799 /** 01800 Verify an ECC signature 01801 sig The signature to verify 01802 siglen The length of the signature (octets) 01803 hash The hash (message digest) that was signed 01804 hashlen The length of the hash (octets) 01805 stat Result of signature, 1==valid, 0==invalid 01806 key The corresponding public ECC key 01807 return MP_OKAY if successful (even if the signature is not valid) 01808 */ 01809 int ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash, 01810 word32 hashlen, int* stat, ecc_key* key) 01811 { 01812 ecc_point *mG, *mQ; 01813 mp_int r; 01814 mp_int s; 01815 mp_int v; 01816 mp_int w; 01817 mp_int u1; 01818 mp_int u2; 01819 mp_int e; 01820 mp_int p; 01821 mp_int m; 01822 int err; 01823 01824 if (sig == NULL || hash == NULL || stat == NULL || key == NULL) 01825 return ECC_BAD_ARG_E; 01826 01827 /* default to invalid signature */ 01828 *stat = 0; 01829 01830 /* is the IDX valid ? */ 01831 if (ecc_is_valid_idx(key->idx) != 1) { 01832 return ECC_BAD_ARG_E; 01833 } 01834 01835 /* allocate ints */ 01836 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) { 01837 return MEMORY_E; 01838 } 01839 01840 if ((err = mp_init(&m)) != MP_OKAY) { 01841 mp_clear(&v); 01842 mp_clear(&w); 01843 mp_clear(&u1); 01844 mp_clear(&u2); 01845 mp_clear(&p); 01846 mp_clear(&e); 01847 return MEMORY_E; 01848 } 01849 01850 /* allocate points */ 01851 mG = ecc_new_point(); 01852 mQ = ecc_new_point(); 01853 if (mQ == NULL || mG == NULL) 01854 err = MEMORY_E; 01855 01856 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s. 01857 * If either of those don't allocate correctly, none of 01858 * the rest of this function will execute, and everything 01859 * gets cleaned up at the end. */ 01860 XMEMSET(&r, 0, sizeof(r)); 01861 XMEMSET(&s, 0, sizeof(s)); 01862 if (err == MP_OKAY) 01863 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s); 01864 01865 /* get the order */ 01866 if (err == MP_OKAY) 01867 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01868 01869 /* get the modulus */ 01870 if (err == MP_OKAY) 01871 err = mp_read_radix(&m, (char *)key->dp->prime, 16); 01872 01873 /* check for zero */ 01874 if (err == MP_OKAY) { 01875 if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT || 01876 mp_cmp(&s, &p) != MP_LT) 01877 err = MP_ZERO_E; 01878 } 01879 /* read hash */ 01880 if (err == MP_OKAY) { 01881 /* we may need to truncate if hash is longer than key size */ 01882 unsigned int orderBits = mp_count_bits(&p); 01883 01884 /* truncate down to byte size, may be all that's needed */ 01885 if ( (CYASSL_BIT_SIZE * hashlen) > orderBits) 01886 hashlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE; 01887 err = mp_read_unsigned_bin(&e, hash, hashlen); 01888 01889 /* may still need bit truncation too */ 01890 if (err == MP_OKAY && (CYASSL_BIT_SIZE * hashlen) > orderBits) 01891 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7)); 01892 } 01893 01894 /* w = s^-1 mod n */ 01895 if (err == MP_OKAY) 01896 err = mp_invmod(&s, &p, &w); 01897 01898 /* u1 = ew */ 01899 if (err == MP_OKAY) 01900 err = mp_mulmod(&e, &w, &p, &u1); 01901 01902 /* u2 = rw */ 01903 if (err == MP_OKAY) 01904 err = mp_mulmod(&r, &w, &p, &u2); 01905 01906 /* find mG and mQ */ 01907 if (err == MP_OKAY) 01908 err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16); 01909 01910 if (err == MP_OKAY) 01911 err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16); 01912 if (err == MP_OKAY) 01913 mp_set(&mG->z, 1); 01914 01915 if (err == MP_OKAY) 01916 err = mp_copy(&key->pubkey.x, &mQ->x); 01917 if (err == MP_OKAY) 01918 err = mp_copy(&key->pubkey.y, &mQ->y); 01919 if (err == MP_OKAY) 01920 err = mp_copy(&key->pubkey.z, &mQ->z); 01921 01922 #ifndef ECC_SHAMIR 01923 { 01924 mp_digit mp; 01925 01926 /* compute u1*mG + u2*mQ = mG */ 01927 if (err == MP_OKAY) 01928 err = ecc_mulmod(&u1, mG, mG, &m, 0); 01929 if (err == MP_OKAY) 01930 err = ecc_mulmod(&u2, mQ, mQ, &m, 0); 01931 01932 /* find the montgomery mp */ 01933 if (err == MP_OKAY) 01934 err = mp_montgomery_setup(&m, &mp); 01935 01936 /* add them */ 01937 if (err == MP_OKAY) 01938 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp); 01939 01940 /* reduce */ 01941 if (err == MP_OKAY) 01942 err = ecc_map(mG, &m, &mp); 01943 } 01944 #else 01945 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */ 01946 if (err == MP_OKAY) 01947 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m); 01948 #endif /* ECC_SHAMIR */ 01949 01950 /* v = X_x1 mod n */ 01951 if (err == MP_OKAY) 01952 err = mp_mod(&mG->x, &p, &v); 01953 01954 /* does v == r */ 01955 if (err == MP_OKAY) { 01956 if (mp_cmp(&v, &r) == MP_EQ) 01957 *stat = 1; 01958 } 01959 01960 ecc_del_point(mG); 01961 ecc_del_point(mQ); 01962 01963 mp_clear(&r); 01964 mp_clear(&s); 01965 mp_clear(&v); 01966 mp_clear(&w); 01967 mp_clear(&u1); 01968 mp_clear(&u2); 01969 mp_clear(&p); 01970 mp_clear(&e); 01971 mp_clear(&m); 01972 01973 return err; 01974 } 01975 01976 01977 /* export public ECC key in ANSI X9.63 format */ 01978 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen) 01979 { 01980 #ifdef CYASSL_SMALL_STACK 01981 byte* buf; 01982 #else 01983 byte buf[ECC_BUFSIZE]; 01984 #endif 01985 word32 numlen; 01986 int ret = MP_OKAY; 01987 01988 if (key == NULL || out == NULL || outLen == NULL) 01989 return ECC_BAD_ARG_E; 01990 01991 if (ecc_is_valid_idx(key->idx) == 0) { 01992 return ECC_BAD_ARG_E; 01993 } 01994 numlen = key->dp->size; 01995 01996 if (*outLen < (1 + 2*numlen)) { 01997 *outLen = 1 + 2*numlen; 01998 return BUFFER_E; 01999 } 02000 02001 /* store byte 0x04 */ 02002 out[0] = 0x04; 02003 02004 #ifdef CYASSL_SMALL_STACK 02005 buf = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 02006 if (buf == NULL) 02007 return MEMORY_E; 02008 #endif 02009 02010 do { 02011 /* pad and store x */ 02012 XMEMSET(buf, 0, ECC_BUFSIZE); 02013 ret = mp_to_unsigned_bin(&key->pubkey.x, 02014 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x))); 02015 if (ret != MP_OKAY) 02016 break; 02017 XMEMCPY(out+1, buf, numlen); 02018 02019 /* pad and store y */ 02020 XMEMSET(buf, 0, ECC_BUFSIZE); 02021 ret = mp_to_unsigned_bin(&key->pubkey.y, 02022 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y))); 02023 if (ret != MP_OKAY) 02024 break; 02025 XMEMCPY(out+1+numlen, buf, numlen); 02026 02027 *outLen = 1 + 2*numlen; 02028 } while (0); 02029 02030 #ifdef CYASSL_SMALL_STACK 02031 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER); 02032 #endif 02033 02034 return ret; 02035 } 02036 02037 02038 /* import public ECC key in ANSI X9.63 format */ 02039 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key) 02040 { 02041 int x, err; 02042 02043 if (in == NULL || key == NULL) 02044 return ECC_BAD_ARG_E; 02045 02046 /* must be odd */ 02047 if ((inLen & 1) == 0) { 02048 return ECC_BAD_ARG_E; 02049 } 02050 02051 /* init key */ 02052 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, 02053 NULL, NULL) != MP_OKAY) { 02054 return MEMORY_E; 02055 } 02056 err = MP_OKAY; 02057 02058 /* check for 4, 6 or 7 */ 02059 if (in[0] != 4 && in[0] != 6 && in[0] != 7) { 02060 err = ASN_PARSE_E; 02061 } 02062 02063 /* read data */ 02064 if (err == MP_OKAY) 02065 err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1); 02066 02067 if (err == MP_OKAY) 02068 err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1), 02069 (inLen-1)>>1); 02070 02071 if (err == MP_OKAY) 02072 mp_set(&key->pubkey.z, 1); 02073 02074 if (err == MP_OKAY) { 02075 /* determine the idx */ 02076 for (x = 0; ecc_sets[x].size != 0; x++) { 02077 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) { 02078 break; 02079 } 02080 } 02081 if (ecc_sets[x].size == 0) { 02082 err = ASN_PARSE_E; 02083 } else { 02084 /* set the idx */ 02085 key->idx = x; 02086 key->dp = &ecc_sets[x]; 02087 key->type = ECC_PUBLICKEY; 02088 } 02089 } 02090 02091 if (err != MP_OKAY) { 02092 mp_clear(&key->pubkey.x); 02093 mp_clear(&key->pubkey.y); 02094 mp_clear(&key->pubkey.z); 02095 mp_clear(&key->k); 02096 } 02097 02098 return err; 02099 } 02100 02101 02102 /* export ecc private key only raw, outLen is in/out size 02103 return MP_OKAY on success */ 02104 int ecc_export_private_only(ecc_key* key, byte* out, word32* outLen) 02105 { 02106 word32 numlen; 02107 02108 if (key == NULL || out == NULL || outLen == NULL) 02109 return ECC_BAD_ARG_E; 02110 02111 if (ecc_is_valid_idx(key->idx) == 0) { 02112 return ECC_BAD_ARG_E; 02113 } 02114 numlen = key->dp->size; 02115 02116 if (*outLen < numlen) { 02117 *outLen = numlen; 02118 return BUFFER_E; 02119 } 02120 *outLen = numlen; 02121 XMEMSET(out, 0, *outLen); 02122 return mp_to_unsigned_bin(&key->k, out + (numlen - 02123 mp_unsigned_bin_size(&key->k))); 02124 } 02125 02126 02127 /* ecc private key import, public key in ANSI X9.63 format, private raw */ 02128 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub, 02129 word32 pubSz, ecc_key* key) 02130 { 02131 int ret = ecc_import_x963(pub, pubSz, key); 02132 if (ret != 0) 02133 return ret; 02134 02135 key->type = ECC_PRIVATEKEY; 02136 02137 return mp_read_unsigned_bin(&key->k, priv, privSz); 02138 } 02139 02140 02141 /* key size in octets */ 02142 int ecc_size(ecc_key* key) 02143 { 02144 if (key == NULL) return 0; 02145 02146 return key->dp->size; 02147 } 02148 02149 02150 /* worst case estimate, check actual return from ecc_sign_hash for actual value 02151 of signature size in octets */ 02152 int ecc_sig_size(ecc_key* key) 02153 { 02154 int sz = ecc_size(key); 02155 if (sz < 0) 02156 return sz; 02157 02158 return sz * 2 + SIG_HEADER_SZ + 4; /* (4) worst case estimate */ 02159 } 02160 02161 02162 #ifdef FP_ECC 02163 02164 /* fixed point ECC cache */ 02165 /* number of entries in the cache */ 02166 #ifndef FP_ENTRIES 02167 #define FP_ENTRIES 16 02168 #endif 02169 02170 /* number of bits in LUT */ 02171 #ifndef FP_LUT 02172 #define FP_LUT 8U 02173 #endif 02174 02175 #ifdef ECC_SHAMIR 02176 /* Sharmir requires a bigger LUT, TAO */ 02177 #if (FP_LUT > 12) || (FP_LUT < 4) 02178 #error FP_LUT must be between 4 and 12 inclusively 02179 #endif 02180 #else 02181 #if (FP_LUT > 12) || (FP_LUT < 2) 02182 #error FP_LUT must be between 2 and 12 inclusively 02183 #endif 02184 #endif 02185 02186 02187 /** Our FP cache */ 02188 typedef struct { 02189 ecc_point* g; /* cached COPY of base point */ 02190 ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */ 02191 mp_int mu; /* copy of the montgomery constant */ 02192 int lru_count; /* amount of times this entry has been used */ 02193 int lock; /* flag to indicate cache eviction */ 02194 /* permitted (0) or not (1) */ 02195 } fp_cache_t; 02196 02197 /* if HAVE_THREAD_LS this cache is per thread, no locking needed */ 02198 static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES]; 02199 02200 #ifndef HAVE_THREAD_LS 02201 static volatile int initMutex = 0; /* prevent multiple mutex inits */ 02202 static CyaSSL_Mutex ecc_fp_lock; 02203 #endif /* HAVE_THREAD_LS */ 02204 02205 /* simple table to help direct the generation of the LUT */ 02206 static const struct { 02207 int ham, terma, termb; 02208 } lut_orders[] = { 02209 { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 }, 02210 { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 }, 02211 { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 }, 02212 { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 }, 02213 { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 }, 02214 { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 }, 02215 { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 }, 02216 { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 }, 02217 #if FP_LUT > 6 02218 { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 }, 02219 { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 }, 02220 { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 }, 02221 { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 }, 02222 { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 }, 02223 { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 }, 02224 { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 }, 02225 { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 }, 02226 #if FP_LUT > 7 02227 { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 }, 02228 { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 }, 02229 { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 }, 02230 { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 }, 02231 { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 }, 02232 { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 }, 02233 { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 }, 02234 { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 }, 02235 { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 }, 02236 { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 }, 02237 { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 }, 02238 { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 }, 02239 { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 }, 02240 { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 }, 02241 { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 }, 02242 { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 }, 02243 #if FP_LUT > 8 02244 { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 }, 02245 { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 }, 02246 { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 }, 02247 { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 }, 02248 { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 }, 02249 { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 }, 02250 { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 }, 02251 { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 }, 02252 { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 }, 02253 { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 }, 02254 { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 }, 02255 { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 }, 02256 { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 }, 02257 { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 }, 02258 { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 }, 02259 { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 }, 02260 { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 }, 02261 { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 }, 02262 { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 }, 02263 { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 }, 02264 { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 }, 02265 { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 }, 02266 { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 }, 02267 { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 }, 02268 { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 }, 02269 { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 }, 02270 { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 }, 02271 { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 }, 02272 { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 }, 02273 { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 }, 02274 { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 }, 02275 { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 }, 02276 #if FP_LUT > 9 02277 { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 }, 02278 { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 }, 02279 { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 }, 02280 { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 }, 02281 { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 }, 02282 { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 }, 02283 { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 }, 02284 { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 }, 02285 { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 }, 02286 { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 }, 02287 { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 }, 02288 { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 }, 02289 { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 }, 02290 { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 }, 02291 { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 }, 02292 { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 }, 02293 { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 }, 02294 { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 }, 02295 { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 }, 02296 { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 }, 02297 { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 }, 02298 { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 }, 02299 { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 }, 02300 { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 }, 02301 { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 }, 02302 { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 }, 02303 { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 }, 02304 { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 }, 02305 { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 }, 02306 { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 }, 02307 { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 }, 02308 { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 }, 02309 { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 }, 02310 { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 }, 02311 { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 }, 02312 { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 }, 02313 { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 }, 02314 { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 }, 02315 { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 }, 02316 { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 }, 02317 { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 }, 02318 { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 }, 02319 { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 }, 02320 { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 }, 02321 { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 }, 02322 { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 }, 02323 { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 }, 02324 { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 }, 02325 { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 }, 02326 { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 }, 02327 { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 }, 02328 { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 }, 02329 { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 }, 02330 { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 }, 02331 { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 }, 02332 { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 }, 02333 { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 }, 02334 { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 }, 02335 { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 }, 02336 { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 }, 02337 { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 }, 02338 { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 }, 02339 { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 }, 02340 { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 }, 02341 #if FP_LUT > 10 02342 { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 }, 02343 { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 }, 02344 { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 }, 02345 { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 }, 02346 { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 }, 02347 { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 }, 02348 { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 }, 02349 { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 }, 02350 { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 }, 02351 { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 }, 02352 { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 }, 02353 { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 }, 02354 { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 }, 02355 { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 }, 02356 { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 }, 02357 { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 }, 02358 { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 }, 02359 { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 }, 02360 { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 }, 02361 { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 }, 02362 { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 }, 02363 { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 }, 02364 { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 }, 02365 { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 }, 02366 { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 }, 02367 { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 }, 02368 { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 }, 02369 { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 }, 02370 { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 }, 02371 { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 }, 02372 { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 }, 02373 { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 }, 02374 { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 }, 02375 { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 }, 02376 { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 }, 02377 { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 }, 02378 { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 }, 02379 { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 }, 02380 { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 }, 02381 { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 }, 02382 { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 }, 02383 { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 }, 02384 { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 }, 02385 { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 }, 02386 { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 }, 02387 { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 }, 02388 { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 }, 02389 { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 }, 02390 { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 }, 02391 { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 }, 02392 { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 }, 02393 { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 }, 02394 { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 }, 02395 { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 }, 02396 { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 }, 02397 { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 }, 02398 { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 }, 02399 { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 }, 02400 { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 }, 02401 { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 }, 02402 { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 }, 02403 { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 }, 02404 { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 }, 02405 { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 }, 02406 { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 }, 02407 { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 }, 02408 { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 }, 02409 { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 }, 02410 { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 }, 02411 { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 }, 02412 { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 }, 02413 { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 }, 02414 { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 }, 02415 { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 }, 02416 { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 }, 02417 { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 }, 02418 { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 }, 02419 { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 }, 02420 { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 }, 02421 { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 }, 02422 { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 }, 02423 { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 }, 02424 { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 }, 02425 { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 }, 02426 { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 }, 02427 { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 }, 02428 { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 }, 02429 { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 }, 02430 { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 }, 02431 { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 }, 02432 { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 }, 02433 { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 }, 02434 { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 }, 02435 { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 }, 02436 { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 }, 02437 { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 }, 02438 { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 }, 02439 { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 }, 02440 { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 }, 02441 { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 }, 02442 { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 }, 02443 { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 }, 02444 { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 }, 02445 { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 }, 02446 { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 }, 02447 { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 }, 02448 { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 }, 02449 { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 }, 02450 { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 }, 02451 { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 }, 02452 { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883, 1024 }, { 7, 884, 1024 }, { 8, 885, 1024 }, { 8, 886, 1024 }, { 9, 887, 1024 }, 02453 { 7, 888, 1024 }, { 8, 889, 1024 }, { 8, 890, 1024 }, { 9, 891, 1024 }, { 8, 892, 1024 }, { 9, 893, 1024 }, { 9, 894, 1024 }, { 10, 895, 1024 }, 02454 { 4, 896, 1024 }, { 5, 897, 1024 }, { 5, 898, 1024 }, { 6, 899, 1024 }, { 5, 900, 1024 }, { 6, 901, 1024 }, { 6, 902, 1024 }, { 7, 903, 1024 }, 02455 { 5, 904, 1024 }, { 6, 905, 1024 }, { 6, 906, 1024 }, { 7, 907, 1024 }, { 6, 908, 1024 }, { 7, 909, 1024 }, { 7, 910, 1024 }, { 8, 911, 1024 }, 02456 { 5, 912, 1024 }, { 6, 913, 1024 }, { 6, 914, 1024 }, { 7, 915, 1024 }, { 6, 916, 1024 }, { 7, 917, 1024 }, { 7, 918, 1024 }, { 8, 919, 1024 }, 02457 { 6, 920, 1024 }, { 7, 921, 1024 }, { 7, 922, 1024 }, { 8, 923, 1024 }, { 7, 924, 1024 }, { 8, 925, 1024 }, { 8, 926, 1024 }, { 9, 927, 1024 }, 02458 { 5, 928, 1024 }, { 6, 929, 1024 }, { 6, 930, 1024 }, { 7, 931, 1024 }, { 6, 932, 1024 }, { 7, 933, 1024 }, { 7, 934, 1024 }, { 8, 935, 1024 }, 02459 { 6, 936, 1024 }, { 7, 937, 1024 }, { 7, 938, 1024 }, { 8, 939, 1024 }, { 7, 940, 1024 }, { 8, 941, 1024 }, { 8, 942, 1024 }, { 9, 943, 1024 }, 02460 { 6, 944, 1024 }, { 7, 945, 1024 }, { 7, 946, 1024 }, { 8, 947, 1024 }, { 7, 948, 1024 }, { 8, 949, 1024 }, { 8, 950, 1024 }, { 9, 951, 1024 }, 02461 { 7, 952, 1024 }, { 8, 953, 1024 }, { 8, 954, 1024 }, { 9, 955, 1024 }, { 8, 956, 1024 }, { 9, 957, 1024 }, { 9, 958, 1024 }, { 10, 959, 1024 }, 02462 { 5, 960, 1024 }, { 6, 961, 1024 }, { 6, 962, 1024 }, { 7, 963, 1024 }, { 6, 964, 1024 }, { 7, 965, 1024 }, { 7, 966, 1024 }, { 8, 967, 1024 }, 02463 { 6, 968, 1024 }, { 7, 969, 1024 }, { 7, 970, 1024 }, { 8, 971, 1024 }, { 7, 972, 1024 }, { 8, 973, 1024 }, { 8, 974, 1024 }, { 9, 975, 1024 }, 02464 { 6, 976, 1024 }, { 7, 977, 1024 }, { 7, 978, 1024 }, { 8, 979, 1024 }, { 7, 980, 1024 }, { 8, 981, 1024 }, { 8, 982, 1024 }, { 9, 983, 1024 }, 02465 { 7, 984, 1024 }, { 8, 985, 1024 }, { 8, 986, 1024 }, { 9, 987, 1024 }, { 8, 988, 1024 }, { 9, 989, 1024 }, { 9, 990, 1024 }, { 10, 991, 1024 }, 02466 { 6, 992, 1024 }, { 7, 993, 1024 }, { 7, 994, 1024 }, { 8, 995, 1024 }, { 7, 996, 1024 }, { 8, 997, 1024 }, { 8, 998, 1024 }, { 9, 999, 1024 }, 02467 { 7, 1000, 1024 }, { 8, 1001, 1024 }, { 8, 1002, 1024 }, { 9, 1003, 1024 }, { 8, 1004, 1024 }, { 9, 1005, 1024 }, { 9, 1006, 1024 }, { 10, 1007, 1024 }, 02468 { 7, 1008, 1024 }, { 8, 1009, 1024 }, { 8, 1010, 1024 }, { 9, 1011, 1024 }, { 8, 1012, 1024 }, { 9, 1013, 1024 }, { 9, 1014, 1024 }, { 10, 1015, 1024 }, 02469 { 8, 1016, 1024 }, { 9, 1017, 1024 }, { 9, 1018, 1024 }, { 10, 1019, 1024 }, { 9, 1020, 1024 }, { 10, 1021, 1024 }, { 10, 1022, 1024 }, { 11, 1023, 1024 }, 02470 #if FP_LUT > 11 02471 { 1, 0, 0 }, { 2, 1, 2048 }, { 2, 2, 2048 }, { 3, 3, 2048 }, { 2, 4, 2048 }, { 3, 5, 2048 }, { 3, 6, 2048 }, { 4, 7, 2048 }, 02472 { 2, 8, 2048 }, { 3, 9, 2048 }, { 3, 10, 2048 }, { 4, 11, 2048 }, { 3, 12, 2048 }, { 4, 13, 2048 }, { 4, 14, 2048 }, { 5, 15, 2048 }, 02473 { 2, 16, 2048 }, { 3, 17, 2048 }, { 3, 18, 2048 }, { 4, 19, 2048 }, { 3, 20, 2048 }, { 4, 21, 2048 }, { 4, 22, 2048 }, { 5, 23, 2048 }, 02474 { 3, 24, 2048 }, { 4, 25, 2048 }, { 4, 26, 2048 }, { 5, 27, 2048 }, { 4, 28, 2048 }, { 5, 29, 2048 }, { 5, 30, 2048 }, { 6, 31, 2048 }, 02475 { 2, 32, 2048 }, { 3, 33, 2048 }, { 3, 34, 2048 }, { 4, 35, 2048 }, { 3, 36, 2048 }, { 4, 37, 2048 }, { 4, 38, 2048 }, { 5, 39, 2048 }, 02476 { 3, 40, 2048 }, { 4, 41, 2048 }, { 4, 42, 2048 }, { 5, 43, 2048 }, { 4, 44, 2048 }, { 5, 45, 2048 }, { 5, 46, 2048 }, { 6, 47, 2048 }, 02477 { 3, 48, 2048 }, { 4, 49, 2048 }, { 4, 50, 2048 }, { 5, 51, 2048 }, { 4, 52, 2048 }, { 5, 53, 2048 }, { 5, 54, 2048 }, { 6, 55, 2048 }, 02478 { 4, 56, 2048 }, { 5, 57, 2048 }, { 5, 58, 2048 }, { 6, 59, 2048 }, { 5, 60, 2048 }, { 6, 61, 2048 }, { 6, 62, 2048 }, { 7, 63, 2048 }, 02479 { 2, 64, 2048 }, { 3, 65, 2048 }, { 3, 66, 2048 }, { 4, 67, 2048 }, { 3, 68, 2048 }, { 4, 69, 2048 }, { 4, 70, 2048 }, { 5, 71, 2048 }, 02480 { 3, 72, 2048 }, { 4, 73, 2048 }, { 4, 74, 2048 }, { 5, 75, 2048 }, { 4, 76, 2048 }, { 5, 77, 2048 }, { 5, 78, 2048 }, { 6, 79, 2048 }, 02481 { 3, 80, 2048 }, { 4, 81, 2048 }, { 4, 82, 2048 }, { 5, 83, 2048 }, { 4, 84, 2048 }, { 5, 85, 2048 }, { 5, 86, 2048 }, { 6, 87, 2048 }, 02482 { 4, 88, 2048 }, { 5, 89, 2048 }, { 5, 90, 2048 }, { 6, 91, 2048 }, { 5, 92, 2048 }, { 6, 93, 2048 }, { 6, 94, 2048 }, { 7, 95, 2048 }, 02483 { 3, 96, 2048 }, { 4, 97, 2048 }, { 4, 98, 2048 }, { 5, 99, 2048 }, { 4, 100, 2048 }, { 5, 101, 2048 }, { 5, 102, 2048 }, { 6, 103, 2048 }, 02484 { 4, 104, 2048 }, { 5, 105, 2048 }, { 5, 106, 2048 }, { 6, 107, 2048 }, { 5, 108, 2048 }, { 6, 109, 2048 }, { 6, 110, 2048 }, { 7, 111, 2048 }, 02485 { 4, 112, 2048 }, { 5, 113, 2048 }, { 5, 114, 2048 }, { 6, 115, 2048 }, { 5, 116, 2048 }, { 6, 117, 2048 }, { 6, 118, 2048 }, { 7, 119, 2048 }, 02486 { 5, 120, 2048 }, { 6, 121, 2048 }, { 6, 122, 2048 }, { 7, 123, 2048 }, { 6, 124, 2048 }, { 7, 125, 2048 }, { 7, 126, 2048 }, { 8, 127, 2048 }, 02487 { 2, 128, 2048 }, { 3, 129, 2048 }, { 3, 130, 2048 }, { 4, 131, 2048 }, { 3, 132, 2048 }, { 4, 133, 2048 }, { 4, 134, 2048 }, { 5, 135, 2048 }, 02488 { 3, 136, 2048 }, { 4, 137, 2048 }, { 4, 138, 2048 }, { 5, 139, 2048 }, { 4, 140, 2048 }, { 5, 141, 2048 }, { 5, 142, 2048 }, { 6, 143, 2048 }, 02489 { 3, 144, 2048 }, { 4, 145, 2048 }, { 4, 146, 2048 }, { 5, 147, 2048 }, { 4, 148, 2048 }, { 5, 149, 2048 }, { 5, 150, 2048 }, { 6, 151, 2048 }, 02490 { 4, 152, 2048 }, { 5, 153, 2048 }, { 5, 154, 2048 }, { 6, 155, 2048 }, { 5, 156, 2048 }, { 6, 157, 2048 }, { 6, 158, 2048 }, { 7, 159, 2048 }, 02491 { 3, 160, 2048 }, { 4, 161, 2048 }, { 4, 162, 2048 }, { 5, 163, 2048 }, { 4, 164, 2048 }, { 5, 165, 2048 }, { 5, 166, 2048 }, { 6, 167, 2048 }, 02492 { 4, 168, 2048 }, { 5, 169, 2048 }, { 5, 170, 2048 }, { 6, 171, 2048 }, { 5, 172, 2048 }, { 6, 173, 2048 }, { 6, 174, 2048 }, { 7, 175, 2048 }, 02493 { 4, 176, 2048 }, { 5, 177, 2048 }, { 5, 178, 2048 }, { 6, 179, 2048 }, { 5, 180, 2048 }, { 6, 181, 2048 }, { 6, 182, 2048 }, { 7, 183, 2048 }, 02494 { 5, 184, 2048 }, { 6, 185, 2048 }, { 6, 186, 2048 }, { 7, 187, 2048 }, { 6, 188, 2048 }, { 7, 189, 2048 }, { 7, 190, 2048 }, { 8, 191, 2048 }, 02495 { 3, 192, 2048 }, { 4, 193, 2048 }, { 4, 194, 2048 }, { 5, 195, 2048 }, { 4, 196, 2048 }, { 5, 197, 2048 }, { 5, 198, 2048 }, { 6, 199, 2048 }, 02496 { 4, 200, 2048 }, { 5, 201, 2048 }, { 5, 202, 2048 }, { 6, 203, 2048 }, { 5, 204, 2048 }, { 6, 205, 2048 }, { 6, 206, 2048 }, { 7, 207, 2048 }, 02497 { 4, 208, 2048 }, { 5, 209, 2048 }, { 5, 210, 2048 }, { 6, 211, 2048 }, { 5, 212, 2048 }, { 6, 213, 2048 }, { 6, 214, 2048 }, { 7, 215, 2048 }, 02498 { 5, 216, 2048 }, { 6, 217, 2048 }, { 6, 218, 2048 }, { 7, 219, 2048 }, { 6, 220, 2048 }, { 7, 221, 2048 }, { 7, 222, 2048 }, { 8, 223, 2048 }, 02499 { 4, 224, 2048 }, { 5, 225, 2048 }, { 5, 226, 2048 }, { 6, 227, 2048 }, { 5, 228, 2048 }, { 6, 229, 2048 }, { 6, 230, 2048 }, { 7, 231, 2048 }, 02500 { 5, 232, 2048 }, { 6, 233, 2048 }, { 6, 234, 2048 }, { 7, 235, 2048 }, { 6, 236, 2048 }, { 7, 237, 2048 }, { 7, 238, 2048 }, { 8, 239, 2048 }, 02501 { 5, 240, 2048 }, { 6, 241, 2048 }, { 6, 242, 2048 }, { 7, 243, 2048 }, { 6, 244, 2048 }, { 7, 245, 2048 }, { 7, 246, 2048 }, { 8, 247, 2048 }, 02502 { 6, 248, 2048 }, { 7, 249, 2048 }, { 7, 250, 2048 }, { 8, 251, 2048 }, { 7, 252, 2048 }, { 8, 253, 2048 }, { 8, 254, 2048 }, { 9, 255, 2048 }, 02503 { 2, 256, 2048 }, { 3, 257, 2048 }, { 3, 258, 2048 }, { 4, 259, 2048 }, { 3, 260, 2048 }, { 4, 261, 2048 }, { 4, 262, 2048 }, { 5, 263, 2048 }, 02504 { 3, 264, 2048 }, { 4, 265, 2048 }, { 4, 266, 2048 }, { 5, 267, 2048 }, { 4, 268, 2048 }, { 5, 269, 2048 }, { 5, 270, 2048 }, { 6, 271, 2048 }, 02505 { 3, 272, 2048 }, { 4, 273, 2048 }, { 4, 274, 2048 }, { 5, 275, 2048 }, { 4, 276, 2048 }, { 5, 277, 2048 }, { 5, 278, 2048 }, { 6, 279, 2048 }, 02506 { 4, 280, 2048 }, { 5, 281, 2048 }, { 5, 282, 2048 }, { 6, 283, 2048 }, { 5, 284, 2048 }, { 6, 285, 2048 }, { 6, 286, 2048 }, { 7, 287, 2048 }, 02507 { 3, 288, 2048 }, { 4, 289, 2048 }, { 4, 290, 2048 }, { 5, 291, 2048 }, { 4, 292, 2048 }, { 5, 293, 2048 }, { 5, 294, 2048 }, { 6, 295, 2048 }, 02508 { 4, 296, 2048 }, { 5, 297, 2048 }, { 5, 298, 2048 }, { 6, 299, 2048 }, { 5, 300, 2048 }, { 6, 301, 2048 }, { 6, 302, 2048 }, { 7, 303, 2048 }, 02509 { 4, 304, 2048 }, { 5, 305, 2048 }, { 5, 306, 2048 }, { 6, 307, 2048 }, { 5, 308, 2048 }, { 6, 309, 2048 }, { 6, 310, 2048 }, { 7, 311, 2048 }, 02510 { 5, 312, 2048 }, { 6, 313, 2048 }, { 6, 314, 2048 }, { 7, 315, 2048 }, { 6, 316, 2048 }, { 7, 317, 2048 }, { 7, 318, 2048 }, { 8, 319, 2048 }, 02511 { 3, 320, 2048 }, { 4, 321, 2048 }, { 4, 322, 2048 }, { 5, 323, 2048 }, { 4, 324, 2048 }, { 5, 325, 2048 }, { 5, 326, 2048 }, { 6, 327, 2048 }, 02512 { 4, 328, 2048 }, { 5, 329, 2048 }, { 5, 330, 2048 }, { 6, 331, 2048 }, { 5, 332, 2048 }, { 6, 333, 2048 }, { 6, 334, 2048 }, { 7, 335, 2048 }, 02513 { 4, 336, 2048 }, { 5, 337, 2048 }, { 5, 338, 2048 }, { 6, 339, 2048 }, { 5, 340, 2048 }, { 6, 341, 2048 }, { 6, 342, 2048 }, { 7, 343, 2048 }, 02514 { 5, 344, 2048 }, { 6, 345, 2048 }, { 6, 346, 2048 }, { 7, 347, 2048 }, { 6, 348, 2048 }, { 7, 349, 2048 }, { 7, 350, 2048 }, { 8, 351, 2048 }, 02515 { 4, 352, 2048 }, { 5, 353, 2048 }, { 5, 354, 2048 }, { 6, 355, 2048 }, { 5, 356, 2048 }, { 6, 357, 2048 }, { 6, 358, 2048 }, { 7, 359, 2048 }, 02516 { 5, 360, 2048 }, { 6, 361, 2048 }, { 6, 362, 2048 }, { 7, 363, 2048 }, { 6, 364, 2048 }, { 7, 365, 2048 }, { 7, 366, 2048 }, { 8, 367, 2048 }, 02517 { 5, 368, 2048 }, { 6, 369, 2048 }, { 6, 370, 2048 }, { 7, 371, 2048 }, { 6, 372, 2048 }, { 7, 373, 2048 }, { 7, 374, 2048 }, { 8, 375, 2048 }, 02518 { 6, 376, 2048 }, { 7, 377, 2048 }, { 7, 378, 2048 }, { 8, 379, 2048 }, { 7, 380, 2048 }, { 8, 381, 2048 }, { 8, 382, 2048 }, { 9, 383, 2048 }, 02519 { 3, 384, 2048 }, { 4, 385, 2048 }, { 4, 386, 2048 }, { 5, 387, 2048 }, { 4, 388, 2048 }, { 5, 389, 2048 }, { 5, 390, 2048 }, { 6, 391, 2048 }, 02520 { 4, 392, 2048 }, { 5, 393, 2048 }, { 5, 394, 2048 }, { 6, 395, 2048 }, { 5, 396, 2048 }, { 6, 397, 2048 }, { 6, 398, 2048 }, { 7, 399, 2048 }, 02521 { 4, 400, 2048 }, { 5, 401, 2048 }, { 5, 402, 2048 }, { 6, 403, 2048 }, { 5, 404, 2048 }, { 6, 405, 2048 }, { 6, 406, 2048 }, { 7, 407, 2048 }, 02522 { 5, 408, 2048 }, { 6, 409, 2048 }, { 6, 410, 2048 }, { 7, 411, 2048 }, { 6, 412, 2048 }, { 7, 413, 2048 }, { 7, 414, 2048 }, { 8, 415, 2048 }, 02523 { 4, 416, 2048 }, { 5, 417, 2048 }, { 5, 418, 2048 }, { 6, 419, 2048 }, { 5, 420, 2048 }, { 6, 421, 2048 }, { 6, 422, 2048 }, { 7, 423, 2048 }, 02524 { 5, 424, 2048 }, { 6, 425, 2048 }, { 6, 426, 2048 }, { 7, 427, 2048 }, { 6, 428, 2048 }, { 7, 429, 2048 }, { 7, 430, 2048 }, { 8, 431, 2048 }, 02525 { 5, 432, 2048 }, { 6, 433, 2048 }, { 6, 434, 2048 }, { 7, 435, 2048 }, { 6, 436, 2048 }, { 7, 437, 2048 }, { 7, 438, 2048 }, { 8, 439, 2048 }, 02526 { 6, 440, 2048 }, { 7, 441, 2048 }, { 7, 442, 2048 }, { 8, 443, 2048 }, { 7, 444, 2048 }, { 8, 445, 2048 }, { 8, 446, 2048 }, { 9, 447, 2048 }, 02527 { 4, 448, 2048 }, { 5, 449, 2048 }, { 5, 450, 2048 }, { 6, 451, 2048 }, { 5, 452, 2048 }, { 6, 453, 2048 }, { 6, 454, 2048 }, { 7, 455, 2048 }, 02528 { 5, 456, 2048 }, { 6, 457, 2048 }, { 6, 458, 2048 }, { 7, 459, 2048 }, { 6, 460, 2048 }, { 7, 461, 2048 }, { 7, 462, 2048 }, { 8, 463, 2048 }, 02529 { 5, 464, 2048 }, { 6, 465, 2048 }, { 6, 466, 2048 }, { 7, 467, 2048 }, { 6, 468, 2048 }, { 7, 469, 2048 }, { 7, 470, 2048 }, { 8, 471, 2048 }, 02530 { 6, 472, 2048 }, { 7, 473, 2048 }, { 7, 474, 2048 }, { 8, 475, 2048 }, { 7, 476, 2048 }, { 8, 477, 2048 }, { 8, 478, 2048 }, { 9, 479, 2048 }, 02531 { 5, 480, 2048 }, { 6, 481, 2048 }, { 6, 482, 2048 }, { 7, 483, 2048 }, { 6, 484, 2048 }, { 7, 485, 2048 }, { 7, 486, 2048 }, { 8, 487, 2048 }, 02532 { 6, 488, 2048 }, { 7, 489, 2048 }, { 7, 490, 2048 }, { 8, 491, 2048 }, { 7, 492, 2048 }, { 8, 493, 2048 }, { 8, 494, 2048 }, { 9, 495, 2048 }, 02533 { 6, 496, 2048 }, { 7, 497, 2048 }, { 7, 498, 2048 }, { 8, 499, 2048 }, { 7, 500, 2048 }, { 8, 501, 2048 }, { 8, 502, 2048 }, { 9, 503, 2048 }, 02534 { 7, 504, 2048 }, { 8, 505, 2048 }, { 8, 506, 2048 }, { 9, 507, 2048 }, { 8, 508, 2048 }, { 9, 509, 2048 }, { 9, 510, 2048 }, { 10, 511, 2048 }, 02535 { 2, 512, 2048 }, { 3, 513, 2048 }, { 3, 514, 2048 }, { 4, 515, 2048 }, { 3, 516, 2048 }, { 4, 517, 2048 }, { 4, 518, 2048 }, { 5, 519, 2048 }, 02536 { 3, 520, 2048 }, { 4, 521, 2048 }, { 4, 522, 2048 }, { 5, 523, 2048 }, { 4, 524, 2048 }, { 5, 525, 2048 }, { 5, 526, 2048 }, { 6, 527, 2048 }, 02537 { 3, 528, 2048 }, { 4, 529, 2048 }, { 4, 530, 2048 }, { 5, 531, 2048 }, { 4, 532, 2048 }, { 5, 533, 2048 }, { 5, 534, 2048 }, { 6, 535, 2048 }, 02538 { 4, 536, 2048 }, { 5, 537, 2048 }, { 5, 538, 2048 }, { 6, 539, 2048 }, { 5, 540, 2048 }, { 6, 541, 2048 }, { 6, 542, 2048 }, { 7, 543, 2048 }, 02539 { 3, 544, 2048 }, { 4, 545, 2048 }, { 4, 546, 2048 }, { 5, 547, 2048 }, { 4, 548, 2048 }, { 5, 549, 2048 }, { 5, 550, 2048 }, { 6, 551, 2048 }, 02540 { 4, 552, 2048 }, { 5, 553, 2048 }, { 5, 554, 2048 }, { 6, 555, 2048 }, { 5, 556, 2048 }, { 6, 557, 2048 }, { 6, 558, 2048 }, { 7, 559, 2048 }, 02541 { 4, 560, 2048 }, { 5, 561, 2048 }, { 5, 562, 2048 }, { 6, 563, 2048 }, { 5, 564, 2048 }, { 6, 565, 2048 }, { 6, 566, 2048 }, { 7, 567, 2048 }, 02542 { 5, 568, 2048 }, { 6, 569, 2048 }, { 6, 570, 2048 }, { 7, 571, 2048 }, { 6, 572, 2048 }, { 7, 573, 2048 }, { 7, 574, 2048 }, { 8, 575, 2048 }, 02543 { 3, 576, 2048 }, { 4, 577, 2048 }, { 4, 578, 2048 }, { 5, 579, 2048 }, { 4, 580, 2048 }, { 5, 581, 2048 }, { 5, 582, 2048 }, { 6, 583, 2048 }, 02544 { 4, 584, 2048 }, { 5, 585, 2048 }, { 5, 586, 2048 }, { 6, 587, 2048 }, { 5, 588, 2048 }, { 6, 589, 2048 }, { 6, 590, 2048 }, { 7, 591, 2048 }, 02545 { 4, 592, 2048 }, { 5, 593, 2048 }, { 5, 594, 2048 }, { 6, 595, 2048 }, { 5, 596, 2048 }, { 6, 597, 2048 }, { 6, 598, 2048 }, { 7, 599, 2048 }, 02546 { 5, 600, 2048 }, { 6, 601, 2048 }, { 6, 602, 2048 }, { 7, 603, 2048 }, { 6, 604, 2048 }, { 7, 605, 2048 }, { 7, 606, 2048 }, { 8, 607, 2048 }, 02547 { 4, 608, 2048 }, { 5, 609, 2048 }, { 5, 610, 2048 }, { 6, 611, 2048 }, { 5, 612, 2048 }, { 6, 613, 2048 }, { 6, 614, 2048 }, { 7, 615, 2048 }, 02548 { 5, 616, 2048 }, { 6, 617, 2048 }, { 6, 618, 2048 }, { 7, 619, 2048 }, { 6, 620, 2048 }, { 7, 621, 2048 }, { 7, 622, 2048 }, { 8, 623, 2048 }, 02549 { 5, 624, 2048 }, { 6, 625, 2048 }, { 6, 626, 2048 }, { 7, 627, 2048 }, { 6, 628, 2048 }, { 7, 629, 2048 }, { 7, 630, 2048 }, { 8, 631, 2048 }, 02550 { 6, 632, 2048 }, { 7, 633, 2048 }, { 7, 634, 2048 }, { 8, 635, 2048 }, { 7, 636, 2048 }, { 8, 637, 2048 }, { 8, 638, 2048 }, { 9, 639, 2048 }, 02551 { 3, 640, 2048 }, { 4, 641, 2048 }, { 4, 642, 2048 }, { 5, 643, 2048 }, { 4, 644, 2048 }, { 5, 645, 2048 }, { 5, 646, 2048 }, { 6, 647, 2048 }, 02552 { 4, 648, 2048 }, { 5, 649, 2048 }, { 5, 650, 2048 }, { 6, 651, 2048 }, { 5, 652, 2048 }, { 6, 653, 2048 }, { 6, 654, 2048 }, { 7, 655, 2048 }, 02553 { 4, 656, 2048 }, { 5, 657, 2048 }, { 5, 658, 2048 }, { 6, 659, 2048 }, { 5, 660, 2048 }, { 6, 661, 2048 }, { 6, 662, 2048 }, { 7, 663, 2048 }, 02554 { 5, 664, 2048 }, { 6, 665, 2048 }, { 6, 666, 2048 }, { 7, 667, 2048 }, { 6, 668, 2048 }, { 7, 669, 2048 }, { 7, 670, 2048 }, { 8, 671, 2048 }, 02555 { 4, 672, 2048 }, { 5, 673, 2048 }, { 5, 674, 2048 }, { 6, 675, 2048 }, { 5, 676, 2048 }, { 6, 677, 2048 }, { 6, 678, 2048 }, { 7, 679, 2048 }, 02556 { 5, 680, 2048 }, { 6, 681, 2048 }, { 6, 682, 2048 }, { 7, 683, 2048 }, { 6, 684, 2048 }, { 7, 685, 2048 }, { 7, 686, 2048 }, { 8, 687, 2048 }, 02557 { 5, 688, 2048 }, { 6, 689, 2048 }, { 6, 690, 2048 }, { 7, 691, 2048 }, { 6, 692, 2048 }, { 7, 693, 2048 }, { 7, 694, 2048 }, { 8, 695, 2048 }, 02558 { 6, 696, 2048 }, { 7, 697, 2048 }, { 7, 698, 2048 }, { 8, 699, 2048 }, { 7, 700, 2048 }, { 8, 701, 2048 }, { 8, 702, 2048 }, { 9, 703, 2048 }, 02559 { 4, 704, 2048 }, { 5, 705, 2048 }, { 5, 706, 2048 }, { 6, 707, 2048 }, { 5, 708, 2048 }, { 6, 709, 2048 }, { 6, 710, 2048 }, { 7, 711, 2048 }, 02560 { 5, 712, 2048 }, { 6, 713, 2048 }, { 6, 714, 2048 }, { 7, 715, 2048 }, { 6, 716, 2048 }, { 7, 717, 2048 }, { 7, 718, 2048 }, { 8, 719, 2048 }, 02561 { 5, 720, 2048 }, { 6, 721, 2048 }, { 6, 722, 2048 }, { 7, 723, 2048 }, { 6, 724, 2048 }, { 7, 725, 2048 }, { 7, 726, 2048 }, { 8, 727, 2048 }, 02562 { 6, 728, 2048 }, { 7, 729, 2048 }, { 7, 730, 2048 }, { 8, 731, 2048 }, { 7, 732, 2048 }, { 8, 733, 2048 }, { 8, 734, 2048 }, { 9, 735, 2048 }, 02563 { 5, 736, 2048 }, { 6, 737, 2048 }, { 6, 738, 2048 }, { 7, 739, 2048 }, { 6, 740, 2048 }, { 7, 741, 2048 }, { 7, 742, 2048 }, { 8, 743, 2048 }, 02564 { 6, 744, 2048 }, { 7, 745, 2048 }, { 7, 746, 2048 }, { 8, 747, 2048 }, { 7, 748, 2048 }, { 8, 749, 2048 }, { 8, 750, 2048 }, { 9, 751, 2048 }, 02565 { 6, 752, 2048 }, { 7, 753, 2048 }, { 7, 754, 2048 }, { 8, 755, 2048 }, { 7, 756, 2048 }, { 8, 757, 2048 }, { 8, 758, 2048 }, { 9, 759, 2048 }, 02566 { 7, 760, 2048 }, { 8, 761, 2048 }, { 8, 762, 2048 }, { 9, 763, 2048 }, { 8, 764, 2048 }, { 9, 765, 2048 }, { 9, 766, 2048 }, { 10, 767, 2048 }, 02567 { 3, 768, 2048 }, { 4, 769, 2048 }, { 4, 770, 2048 }, { 5, 771, 2048 }, { 4, 772, 2048 }, { 5, 773, 2048 }, { 5, 774, 2048 }, { 6, 775, 2048 }, 02568 { 4, 776, 2048 }, { 5, 777, 2048 }, { 5, 778, 2048 }, { 6, 779, 2048 }, { 5, 780, 2048 }, { 6, 781, 2048 }, { 6, 782, 2048 }, { 7, 783, 2048 }, 02569 { 4, 784, 2048 }, { 5, 785, 2048 }, { 5, 786, 2048 }, { 6, 787, 2048 }, { 5, 788, 2048 }, { 6, 789, 2048 }, { 6, 790, 2048 }, { 7, 791, 2048 }, 02570 { 5, 792, 2048 }, { 6, 793, 2048 }, { 6, 794, 2048 }, { 7, 795, 2048 }, { 6, 796, 2048 }, { 7, 797, 2048 }, { 7, 798, 2048 }, { 8, 799, 2048 }, 02571 { 4, 800, 2048 }, { 5, 801, 2048 }, { 5, 802, 2048 }, { 6, 803, 2048 }, { 5, 804, 2048 }, { 6, 805, 2048 }, { 6, 806, 2048 }, { 7, 807, 2048 }, 02572 { 5, 808, 2048 }, { 6, 809, 2048 }, { 6, 810, 2048 }, { 7, 811, 2048 }, { 6, 812, 2048 }, { 7, 813, 2048 }, { 7, 814, 2048 }, { 8, 815, 2048 }, 02573 { 5, 816, 2048 }, { 6, 817, 2048 }, { 6, 818, 2048 }, { 7, 819, 2048 }, { 6, 820, 2048 }, { 7, 821, 2048 }, { 7, 822, 2048 }, { 8, 823, 2048 }, 02574 { 6, 824, 2048 }, { 7, 825, 2048 }, { 7, 826, 2048 }, { 8, 827, 2048 }, { 7, 828, 2048 }, { 8, 829, 2048 }, { 8, 830, 2048 }, { 9, 831, 2048 }, 02575 { 4, 832, 2048 }, { 5, 833, 2048 }, { 5, 834, 2048 }, { 6, 835, 2048 }, { 5, 836, 2048 }, { 6, 837, 2048 }, { 6, 838, 2048 }, { 7, 839, 2048 }, 02576 { 5, 840, 2048 }, { 6, 841, 2048 }, { 6, 842, 2048 }, { 7, 843, 2048 }, { 6, 844, 2048 }, { 7, 845, 2048 }, { 7, 846, 2048 }, { 8, 847, 2048 }, 02577 { 5, 848, 2048 }, { 6, 849, 2048 }, { 6, 850, 2048 }, { 7, 851, 2048 }, { 6, 852, 2048 }, { 7, 853, 2048 }, { 7, 854, 2048 }, { 8, 855, 2048 }, 02578 { 6, 856, 2048 }, { 7, 857, 2048 }, { 7, 858, 2048 }, { 8, 859, 2048 }, { 7, 860, 2048 }, { 8, 861, 2048 }, { 8, 862, 2048 }, { 9, 863, 2048 }, 02579 { 5, 864, 2048 }, { 6, 865, 2048 }, { 6, 866, 2048 }, { 7, 867, 2048 }, { 6, 868, 2048 }, { 7, 869, 2048 }, { 7, 870, 2048 }, { 8, 871, 2048 }, 02580 { 6, 872, 2048 }, { 7, 873, 2048 }, { 7, 874, 2048 }, { 8, 875, 2048 }, { 7, 876, 2048 }, { 8, 877, 2048 }, { 8, 878, 2048 }, { 9, 879, 2048 }, 02581 { 6, 880, 2048 }, { 7, 881, 2048 }, { 7, 882, 2048 }, { 8, 883, 2048 }, { 7, 884, 2048 }, { 8, 885, 2048 }, { 8, 886, 2048 }, { 9, 887, 2048 }, 02582 { 7, 888, 2048 }, { 8, 889, 2048 }, { 8, 890, 2048 }, { 9, 891, 2048 }, { 8, 892, 2048 }, { 9, 893, 2048 }, { 9, 894, 2048 }, { 10, 895, 2048 }, 02583 { 4, 896, 2048 }, { 5, 897, 2048 }, { 5, 898, 2048 }, { 6, 899, 2048 }, { 5, 900, 2048 }, { 6, 901, 2048 }, { 6, 902, 2048 }, { 7, 903, 2048 }, 02584 { 5, 904, 2048 }, { 6, 905, 2048 }, { 6, 906, 2048 }, { 7, 907, 2048 }, { 6, 908, 2048 }, { 7, 909, 2048 }, { 7, 910, 2048 }, { 8, 911, 2048 }, 02585 { 5, 912, 2048 }, { 6, 913, 2048 }, { 6, 914, 2048 }, { 7, 915, 2048 }, { 6, 916, 2048 }, { 7, 917, 2048 }, { 7, 918, 2048 }, { 8, 919, 2048 }, 02586 { 6, 920, 2048 }, { 7, 921, 2048 }, { 7, 922, 2048 }, { 8, 923, 2048 }, { 7, 924, 2048 }, { 8, 925, 2048 }, { 8, 926, 2048 }, { 9, 927, 2048 }, 02587 { 5, 928, 2048 }, { 6, 929, 2048 }, { 6, 930, 2048 }, { 7, 931, 2048 }, { 6, 932, 2048 }, { 7, 933, 2048 }, { 7, 934, 2048 }, { 8, 935, 2048 }, 02588 { 6, 936, 2048 }, { 7, 937, 2048 }, { 7, 938, 2048 }, { 8, 939, 2048 }, { 7, 940, 2048 }, { 8, 941, 2048 }, { 8, 942, 2048 }, { 9, 943, 2048 }, 02589 { 6, 944, 2048 }, { 7, 945, 2048 }, { 7, 946, 2048 }, { 8, 947, 2048 }, { 7, 948, 2048 }, { 8, 949, 2048 }, { 8, 950, 2048 }, { 9, 951, 2048 }, 02590 { 7, 952, 2048 }, { 8, 953, 2048 }, { 8, 954, 2048 }, { 9, 955, 2048 }, { 8, 956, 2048 }, { 9, 957, 2048 }, { 9, 958, 2048 }, { 10, 959, 2048 }, 02591 { 5, 960, 2048 }, { 6, 961, 2048 }, { 6, 962, 2048 }, { 7, 963, 2048 }, { 6, 964, 2048 }, { 7, 965, 2048 }, { 7, 966, 2048 }, { 8, 967, 2048 }, 02592 { 6, 968, 2048 }, { 7, 969, 2048 }, { 7, 970, 2048 }, { 8, 971, 2048 }, { 7, 972, 2048 }, { 8, 973, 2048 }, { 8, 974, 2048 }, { 9, 975, 2048 }, 02593 { 6, 976, 2048 }, { 7, 977, 2048 }, { 7, 978, 2048 }, { 8, 979, 2048 }, { 7, 980, 2048 }, { 8, 981, 2048 }, { 8, 982, 2048 }, { 9, 983, 2048 }, 02594 { 7, 984, 2048 }, { 8, 985, 2048 }, { 8, 986, 2048 }, { 9, 987, 2048 }, { 8, 988, 2048 }, { 9, 989, 2048 }, { 9, 990, 2048 }, { 10, 991, 2048 }, 02595 { 6, 992, 2048 }, { 7, 993, 2048 }, { 7, 994, 2048 }, { 8, 995, 2048 }, { 7, 996, 2048 }, { 8, 997, 2048 }, { 8, 998, 2048 }, { 9, 999, 2048 }, 02596 { 7, 1000, 2048 }, { 8, 1001, 2048 }, { 8, 1002, 2048 }, { 9, 1003, 2048 }, { 8, 1004, 2048 }, { 9, 1005, 2048 }, { 9, 1006, 2048 }, { 10, 1007, 2048 }, 02597 { 7, 1008, 2048 }, { 8, 1009, 2048 }, { 8, 1010, 2048 }, { 9, 1011, 2048 }, { 8, 1012, 2048 }, { 9, 1013, 2048 }, { 9, 1014, 2048 }, { 10, 1015, 2048 }, 02598 { 8, 1016, 2048 }, { 9, 1017, 2048 }, { 9, 1018, 2048 }, { 10, 1019, 2048 }, { 9, 1020, 2048 }, { 10, 1021, 2048 }, { 10, 1022, 2048 }, { 11, 1023, 2048 }, 02599 { 2, 1024, 2048 }, { 3, 1025, 2048 }, { 3, 1026, 2048 }, { 4, 1027, 2048 }, { 3, 1028, 2048 }, { 4, 1029, 2048 }, { 4, 1030, 2048 }, { 5, 1031, 2048 }, 02600 { 3, 1032, 2048 }, { 4, 1033, 2048 }, { 4, 1034, 2048 }, { 5, 1035, 2048 }, { 4, 1036, 2048 }, { 5, 1037, 2048 }, { 5, 1038, 2048 }, { 6, 1039, 2048 }, 02601 { 3, 1040, 2048 }, { 4, 1041, 2048 }, { 4, 1042, 2048 }, { 5, 1043, 2048 }, { 4, 1044, 2048 }, { 5, 1045, 2048 }, { 5, 1046, 2048 }, { 6, 1047, 2048 }, 02602 { 4, 1048, 2048 }, { 5, 1049, 2048 }, { 5, 1050, 2048 }, { 6, 1051, 2048 }, { 5, 1052, 2048 }, { 6, 1053, 2048 }, { 6, 1054, 2048 }, { 7, 1055, 2048 }, 02603 { 3, 1056, 2048 }, { 4, 1057, 2048 }, { 4, 1058, 2048 }, { 5, 1059, 2048 }, { 4, 1060, 2048 }, { 5, 1061, 2048 }, { 5, 1062, 2048 }, { 6, 1063, 2048 }, 02604 { 4, 1064, 2048 }, { 5, 1065, 2048 }, { 5, 1066, 2048 }, { 6, 1067, 2048 }, { 5, 1068, 2048 }, { 6, 1069, 2048 }, { 6, 1070, 2048 }, { 7, 1071, 2048 }, 02605 { 4, 1072, 2048 }, { 5, 1073, 2048 }, { 5, 1074, 2048 }, { 6, 1075, 2048 }, { 5, 1076, 2048 }, { 6, 1077, 2048 }, { 6, 1078, 2048 }, { 7, 1079, 2048 }, 02606 { 5, 1080, 2048 }, { 6, 1081, 2048 }, { 6, 1082, 2048 }, { 7, 1083, 2048 }, { 6, 1084, 2048 }, { 7, 1085, 2048 }, { 7, 1086, 2048 }, { 8, 1087, 2048 }, 02607 { 3, 1088, 2048 }, { 4, 1089, 2048 }, { 4, 1090, 2048 }, { 5, 1091, 2048 }, { 4, 1092, 2048 }, { 5, 1093, 2048 }, { 5, 1094, 2048 }, { 6, 1095, 2048 }, 02608 { 4, 1096, 2048 }, { 5, 1097, 2048 }, { 5, 1098, 2048 }, { 6, 1099, 2048 }, { 5, 1100, 2048 }, { 6, 1101, 2048 }, { 6, 1102, 2048 }, { 7, 1103, 2048 }, 02609 { 4, 1104, 2048 }, { 5, 1105, 2048 }, { 5, 1106, 2048 }, { 6, 1107, 2048 }, { 5, 1108, 2048 }, { 6, 1109, 2048 }, { 6, 1110, 2048 }, { 7, 1111, 2048 }, 02610 { 5, 1112, 2048 }, { 6, 1113, 2048 }, { 6, 1114, 2048 }, { 7, 1115, 2048 }, { 6, 1116, 2048 }, { 7, 1117, 2048 }, { 7, 1118, 2048 }, { 8, 1119, 2048 }, 02611 { 4, 1120, 2048 }, { 5, 1121, 2048 }, { 5, 1122, 2048 }, { 6, 1123, 2048 }, { 5, 1124, 2048 }, { 6, 1125, 2048 }, { 6, 1126, 2048 }, { 7, 1127, 2048 }, 02612 { 5, 1128, 2048 }, { 6, 1129, 2048 }, { 6, 1130, 2048 }, { 7, 1131, 2048 }, { 6, 1132, 2048 }, { 7, 1133, 2048 }, { 7, 1134, 2048 }, { 8, 1135, 2048 }, 02613 { 5, 1136, 2048 }, { 6, 1137, 2048 }, { 6, 1138, 2048 }, { 7, 1139, 2048 }, { 6, 1140, 2048 }, { 7, 1141, 2048 }, { 7, 1142, 2048 }, { 8, 1143, 2048 }, 02614 { 6, 1144, 2048 }, { 7, 1145, 2048 }, { 7, 1146, 2048 }, { 8, 1147, 2048 }, { 7, 1148, 2048 }, { 8, 1149, 2048 }, { 8, 1150, 2048 }, { 9, 1151, 2048 }, 02615 { 3, 1152, 2048 }, { 4, 1153, 2048 }, { 4, 1154, 2048 }, { 5, 1155, 2048 }, { 4, 1156, 2048 }, { 5, 1157, 2048 }, { 5, 1158, 2048 }, { 6, 1159, 2048 }, 02616 { 4, 1160, 2048 }, { 5, 1161, 2048 }, { 5, 1162, 2048 }, { 6, 1163, 2048 }, { 5, 1164, 2048 }, { 6, 1165, 2048 }, { 6, 1166, 2048 }, { 7, 1167, 2048 }, 02617 { 4, 1168, 2048 }, { 5, 1169, 2048 }, { 5, 1170, 2048 }, { 6, 1171, 2048 }, { 5, 1172, 2048 }, { 6, 1173, 2048 }, { 6, 1174, 2048 }, { 7, 1175, 2048 }, 02618 { 5, 1176, 2048 }, { 6, 1177, 2048 }, { 6, 1178, 2048 }, { 7, 1179, 2048 }, { 6, 1180, 2048 }, { 7, 1181, 2048 }, { 7, 1182, 2048 }, { 8, 1183, 2048 }, 02619 { 4, 1184, 2048 }, { 5, 1185, 2048 }, { 5, 1186, 2048 }, { 6, 1187, 2048 }, { 5, 1188, 2048 }, { 6, 1189, 2048 }, { 6, 1190, 2048 }, { 7, 1191, 2048 }, 02620 { 5, 1192, 2048 }, { 6, 1193, 2048 }, { 6, 1194, 2048 }, { 7, 1195, 2048 }, { 6, 1196, 2048 }, { 7, 1197, 2048 }, { 7, 1198, 2048 }, { 8, 1199, 2048 }, 02621 { 5, 1200, 2048 }, { 6, 1201, 2048 }, { 6, 1202, 2048 }, { 7, 1203, 2048 }, { 6, 1204, 2048 }, { 7, 1205, 2048 }, { 7, 1206, 2048 }, { 8, 1207, 2048 }, 02622 { 6, 1208, 2048 }, { 7, 1209, 2048 }, { 7, 1210, 2048 }, { 8, 1211, 2048 }, { 7, 1212, 2048 }, { 8, 1213, 2048 }, { 8, 1214, 2048 }, { 9, 1215, 2048 }, 02623 { 4, 1216, 2048 }, { 5, 1217, 2048 }, { 5, 1218, 2048 }, { 6, 1219, 2048 }, { 5, 1220, 2048 }, { 6, 1221, 2048 }, { 6, 1222, 2048 }, { 7, 1223, 2048 }, 02624 { 5, 1224, 2048 }, { 6, 1225, 2048 }, { 6, 1226, 2048 }, { 7, 1227, 2048 }, { 6, 1228, 2048 }, { 7, 1229, 2048 }, { 7, 1230, 2048 }, { 8, 1231, 2048 }, 02625 { 5, 1232, 2048 }, { 6, 1233, 2048 }, { 6, 1234, 2048 }, { 7, 1235, 2048 }, { 6, 1236, 2048 }, { 7, 1237, 2048 }, { 7, 1238, 2048 }, { 8, 1239, 2048 }, 02626 { 6, 1240, 2048 }, { 7, 1241, 2048 }, { 7, 1242, 2048 }, { 8, 1243, 2048 }, { 7, 1244, 2048 }, { 8, 1245, 2048 }, { 8, 1246, 2048 }, { 9, 1247, 2048 }, 02627 { 5, 1248, 2048 }, { 6, 1249, 2048 }, { 6, 1250, 2048 }, { 7, 1251, 2048 }, { 6, 1252, 2048 }, { 7, 1253, 2048 }, { 7, 1254, 2048 }, { 8, 1255, 2048 }, 02628 { 6, 1256, 2048 }, { 7, 1257, 2048 }, { 7, 1258, 2048 }, { 8, 1259, 2048 }, { 7, 1260, 2048 }, { 8, 1261, 2048 }, { 8, 1262, 2048 }, { 9, 1263, 2048 }, 02629 { 6, 1264, 2048 }, { 7, 1265, 2048 }, { 7, 1266, 2048 }, { 8, 1267, 2048 }, { 7, 1268, 2048 }, { 8, 1269, 2048 }, { 8, 1270, 2048 }, { 9, 1271, 2048 }, 02630 { 7, 1272, 2048 }, { 8, 1273, 2048 }, { 8, 1274, 2048 }, { 9, 1275, 2048 }, { 8, 1276, 2048 }, { 9, 1277, 2048 }, { 9, 1278, 2048 }, { 10, 1279, 2048 }, 02631 { 3, 1280, 2048 }, { 4, 1281, 2048 }, { 4, 1282, 2048 }, { 5, 1283, 2048 }, { 4, 1284, 2048 }, { 5, 1285, 2048 }, { 5, 1286, 2048 }, { 6, 1287, 2048 }, 02632 { 4, 1288, 2048 }, { 5, 1289, 2048 }, { 5, 1290, 2048 }, { 6, 1291, 2048 }, { 5, 1292, 2048 }, { 6, 1293, 2048 }, { 6, 1294, 2048 }, { 7, 1295, 2048 }, 02633 { 4, 1296, 2048 }, { 5, 1297, 2048 }, { 5, 1298, 2048 }, { 6, 1299, 2048 }, { 5, 1300, 2048 }, { 6, 1301, 2048 }, { 6, 1302, 2048 }, { 7, 1303, 2048 }, 02634 { 5, 1304, 2048 }, { 6, 1305, 2048 }, { 6, 1306, 2048 }, { 7, 1307, 2048 }, { 6, 1308, 2048 }, { 7, 1309, 2048 }, { 7, 1310, 2048 }, { 8, 1311, 2048 }, 02635 { 4, 1312, 2048 }, { 5, 1313, 2048 }, { 5, 1314, 2048 }, { 6, 1315, 2048 }, { 5, 1316, 2048 }, { 6, 1317, 2048 }, { 6, 1318, 2048 }, { 7, 1319, 2048 }, 02636 { 5, 1320, 2048 }, { 6, 1321, 2048 }, { 6, 1322, 2048 }, { 7, 1323, 2048 }, { 6, 1324, 2048 }, { 7, 1325, 2048 }, { 7, 1326, 2048 }, { 8, 1327, 2048 }, 02637 { 5, 1328, 2048 }, { 6, 1329, 2048 }, { 6, 1330, 2048 }, { 7, 1331, 2048 }, { 6, 1332, 2048 }, { 7, 1333, 2048 }, { 7, 1334, 2048 }, { 8, 1335, 2048 }, 02638 { 6, 1336, 2048 }, { 7, 1337, 2048 }, { 7, 1338, 2048 }, { 8, 1339, 2048 }, { 7, 1340, 2048 }, { 8, 1341, 2048 }, { 8, 1342, 2048 }, { 9, 1343, 2048 }, 02639 { 4, 1344, 2048 }, { 5, 1345, 2048 }, { 5, 1346, 2048 }, { 6, 1347, 2048 }, { 5, 1348, 2048 }, { 6, 1349, 2048 }, { 6, 1350, 2048 }, { 7, 1351, 2048 }, 02640 { 5, 1352, 2048 }, { 6, 1353, 2048 }, { 6, 1354, 2048 }, { 7, 1355, 2048 }, { 6, 1356, 2048 }, { 7, 1357, 2048 }, { 7, 1358, 2048 }, { 8, 1359, 2048 }, 02641 { 5, 1360, 2048 }, { 6, 1361, 2048 }, { 6, 1362, 2048 }, { 7, 1363, 2048 }, { 6, 1364, 2048 }, { 7, 1365, 2048 }, { 7, 1366, 2048 }, { 8, 1367, 2048 }, 02642 { 6, 1368, 2048 }, { 7, 1369, 2048 }, { 7, 1370, 2048 }, { 8, 1371, 2048 }, { 7, 1372, 2048 }, { 8, 1373, 2048 }, { 8, 1374, 2048 }, { 9, 1375, 2048 }, 02643 { 5, 1376, 2048 }, { 6, 1377, 2048 }, { 6, 1378, 2048 }, { 7, 1379, 2048 }, { 6, 1380, 2048 }, { 7, 1381, 2048 }, { 7, 1382, 2048 }, { 8, 1383, 2048 }, 02644 { 6, 1384, 2048 }, { 7, 1385, 2048 }, { 7, 1386, 2048 }, { 8, 1387, 2048 }, { 7, 1388, 2048 }, { 8, 1389, 2048 }, { 8, 1390, 2048 }, { 9, 1391, 2048 }, 02645 { 6, 1392, 2048 }, { 7, 1393, 2048 }, { 7, 1394, 2048 }, { 8, 1395, 2048 }, { 7, 1396, 2048 }, { 8, 1397, 2048 }, { 8, 1398, 2048 }, { 9, 1399, 2048 }, 02646 { 7, 1400, 2048 }, { 8, 1401, 2048 }, { 8, 1402, 2048 }, { 9, 1403, 2048 }, { 8, 1404, 2048 }, { 9, 1405, 2048 }, { 9, 1406, 2048 }, { 10, 1407, 2048 }, 02647 { 4, 1408, 2048 }, { 5, 1409, 2048 }, { 5, 1410, 2048 }, { 6, 1411, 2048 }, { 5, 1412, 2048 }, { 6, 1413, 2048 }, { 6, 1414, 2048 }, { 7, 1415, 2048 }, 02648 { 5, 1416, 2048 }, { 6, 1417, 2048 }, { 6, 1418, 2048 }, { 7, 1419, 2048 }, { 6, 1420, 2048 }, { 7, 1421, 2048 }, { 7, 1422, 2048 }, { 8, 1423, 2048 }, 02649 { 5, 1424, 2048 }, { 6, 1425, 2048 }, { 6, 1426, 2048 }, { 7, 1427, 2048 }, { 6, 1428, 2048 }, { 7, 1429, 2048 }, { 7, 1430, 2048 }, { 8, 1431, 2048 }, 02650 { 6, 1432, 2048 }, { 7, 1433, 2048 }, { 7, 1434, 2048 }, { 8, 1435, 2048 }, { 7, 1436, 2048 }, { 8, 1437, 2048 }, { 8, 1438, 2048 }, { 9, 1439, 2048 }, 02651 { 5, 1440, 2048 }, { 6, 1441, 2048 }, { 6, 1442, 2048 }, { 7, 1443, 2048 }, { 6, 1444, 2048 }, { 7, 1445, 2048 }, { 7, 1446, 2048 }, { 8, 1447, 2048 }, 02652 { 6, 1448, 2048 }, { 7, 1449, 2048 }, { 7, 1450, 2048 }, { 8, 1451, 2048 }, { 7, 1452, 2048 }, { 8, 1453, 2048 }, { 8, 1454, 2048 }, { 9, 1455, 2048 }, 02653 { 6, 1456, 2048 }, { 7, 1457, 2048 }, { 7, 1458, 2048 }, { 8, 1459, 2048 }, { 7, 1460, 2048 }, { 8, 1461, 2048 }, { 8, 1462, 2048 }, { 9, 1463, 2048 }, 02654 { 7, 1464, 2048 }, { 8, 1465, 2048 }, { 8, 1466, 2048 }, { 9, 1467, 2048 }, { 8, 1468, 2048 }, { 9, 1469, 2048 }, { 9, 1470, 2048 }, { 10, 1471, 2048 }, 02655 { 5, 1472, 2048 }, { 6, 1473, 2048 }, { 6, 1474, 2048 }, { 7, 1475, 2048 }, { 6, 1476, 2048 }, { 7, 1477, 2048 }, { 7, 1478, 2048 }, { 8, 1479, 2048 }, 02656 { 6, 1480, 2048 }, { 7, 1481, 2048 }, { 7, 1482, 2048 }, { 8, 1483, 2048 }, { 7, 1484, 2048 }, { 8, 1485, 2048 }, { 8, 1486, 2048 }, { 9, 1487, 2048 }, 02657 { 6, 1488, 2048 }, { 7, 1489, 2048 }, { 7, 1490, 2048 }, { 8, 1491, 2048 }, { 7, 1492, 2048 }, { 8, 1493, 2048 }, { 8, 1494, 2048 }, { 9, 1495, 2048 }, 02658 { 7, 1496, 2048 }, { 8, 1497, 2048 }, { 8, 1498, 2048 }, { 9, 1499, 2048 }, { 8, 1500, 2048 }, { 9, 1501, 2048 }, { 9, 1502, 2048 }, { 10, 1503, 2048 }, 02659 { 6, 1504, 2048 }, { 7, 1505, 2048 }, { 7, 1506, 2048 }, { 8, 1507, 2048 }, { 7, 1508, 2048 }, { 8, 1509, 2048 }, { 8, 1510, 2048 }, { 9, 1511, 2048 }, 02660 { 7, 1512, 2048 }, { 8, 1513, 2048 }, { 8, 1514, 2048 }, { 9, 1515, 2048 }, { 8, 1516, 2048 }, { 9, 1517, 2048 }, { 9, 1518, 2048 }, { 10, 1519, 2048 }, 02661 { 7, 1520, 2048 }, { 8, 1521, 2048 }, { 8, 1522, 2048 }, { 9, 1523, 2048 }, { 8, 1524, 2048 }, { 9, 1525, 2048 }, { 9, 1526, 2048 }, { 10, 1527, 2048 }, 02662 { 8, 1528, 2048 }, { 9, 1529, 2048 }, { 9, 1530, 2048 }, { 10, 1531, 2048 }, { 9, 1532, 2048 }, { 10, 1533, 2048 }, { 10, 1534, 2048 }, { 11, 1535, 2048 }, 02663 { 3, 1536, 2048 }, { 4, 1537, 2048 }, { 4, 1538, 2048 }, { 5, 1539, 2048 }, { 4, 1540, 2048 }, { 5, 1541, 2048 }, { 5, 1542, 2048 }, { 6, 1543, 2048 }, 02664 { 4, 1544, 2048 }, { 5, 1545, 2048 }, { 5, 1546, 2048 }, { 6, 1547, 2048 }, { 5, 1548, 2048 }, { 6, 1549, 2048 }, { 6, 1550, 2048 }, { 7, 1551, 2048 }, 02665 { 4, 1552, 2048 }, { 5, 1553, 2048 }, { 5, 1554, 2048 }, { 6, 1555, 2048 }, { 5, 1556, 2048 }, { 6, 1557, 2048 }, { 6, 1558, 2048 }, { 7, 1559, 2048 }, 02666 { 5, 1560, 2048 }, { 6, 1561, 2048 }, { 6, 1562, 2048 }, { 7, 1563, 2048 }, { 6, 1564, 2048 }, { 7, 1565, 2048 }, { 7, 1566, 2048 }, { 8, 1567, 2048 }, 02667 { 4, 1568, 2048 }, { 5, 1569, 2048 }, { 5, 1570, 2048 }, { 6, 1571, 2048 }, { 5, 1572, 2048 }, { 6, 1573, 2048 }, { 6, 1574, 2048 }, { 7, 1575, 2048 }, 02668 { 5, 1576, 2048 }, { 6, 1577, 2048 }, { 6, 1578, 2048 }, { 7, 1579, 2048 }, { 6, 1580, 2048 }, { 7, 1581, 2048 }, { 7, 1582, 2048 }, { 8, 1583, 2048 }, 02669 { 5, 1584, 2048 }, { 6, 1585, 2048 }, { 6, 1586, 2048 }, { 7, 1587, 2048 }, { 6, 1588, 2048 }, { 7, 1589, 2048 }, { 7, 1590, 2048 }, { 8, 1591, 2048 }, 02670 { 6, 1592, 2048 }, { 7, 1593, 2048 }, { 7, 1594, 2048 }, { 8, 1595, 2048 }, { 7, 1596, 2048 }, { 8, 1597, 2048 }, { 8, 1598, 2048 }, { 9, 1599, 2048 }, 02671 { 4, 1600, 2048 }, { 5, 1601, 2048 }, { 5, 1602, 2048 }, { 6, 1603, 2048 }, { 5, 1604, 2048 }, { 6, 1605, 2048 }, { 6, 1606, 2048 }, { 7, 1607, 2048 }, 02672 { 5, 1608, 2048 }, { 6, 1609, 2048 }, { 6, 1610, 2048 }, { 7, 1611, 2048 }, { 6, 1612, 2048 }, { 7, 1613, 2048 }, { 7, 1614, 2048 }, { 8, 1615, 2048 }, 02673 { 5, 1616, 2048 }, { 6, 1617, 2048 }, { 6, 1618, 2048 }, { 7, 1619, 2048 }, { 6, 1620, 2048 }, { 7, 1621, 2048 }, { 7, 1622, 2048 }, { 8, 1623, 2048 }, 02674 { 6, 1624, 2048 }, { 7, 1625, 2048 }, { 7, 1626, 2048 }, { 8, 1627, 2048 }, { 7, 1628, 2048 }, { 8, 1629, 2048 }, { 8, 1630, 2048 }, { 9, 1631, 2048 }, 02675 { 5, 1632, 2048 }, { 6, 1633, 2048 }, { 6, 1634, 2048 }, { 7, 1635, 2048 }, { 6, 1636, 2048 }, { 7, 1637, 2048 }, { 7, 1638, 2048 }, { 8, 1639, 2048 }, 02676 { 6, 1640, 2048 }, { 7, 1641, 2048 }, { 7, 1642, 2048 }, { 8, 1643, 2048 }, { 7, 1644, 2048 }, { 8, 1645, 2048 }, { 8, 1646, 2048 }, { 9, 1647, 2048 }, 02677 { 6, 1648, 2048 }, { 7, 1649, 2048 }, { 7, 1650, 2048 }, { 8, 1651, 2048 }, { 7, 1652, 2048 }, { 8, 1653, 2048 }, { 8, 1654, 2048 }, { 9, 1655, 2048 }, 02678 { 7, 1656, 2048 }, { 8, 1657, 2048 }, { 8, 1658, 2048 }, { 9, 1659, 2048 }, { 8, 1660, 2048 }, { 9, 1661, 2048 }, { 9, 1662, 2048 }, { 10, 1663, 2048 }, 02679 { 4, 1664, 2048 }, { 5, 1665, 2048 }, { 5, 1666, 2048 }, { 6, 1667, 2048 }, { 5, 1668, 2048 }, { 6, 1669, 2048 }, { 6, 1670, 2048 }, { 7, 1671, 2048 }, 02680 { 5, 1672, 2048 }, { 6, 1673, 2048 }, { 6, 1674, 2048 }, { 7, 1675, 2048 }, { 6, 1676, 2048 }, { 7, 1677, 2048 }, { 7, 1678, 2048 }, { 8, 1679, 2048 }, 02681 { 5, 1680, 2048 }, { 6, 1681, 2048 }, { 6, 1682, 2048 }, { 7, 1683, 2048 }, { 6, 1684, 2048 }, { 7, 1685, 2048 }, { 7, 1686, 2048 }, { 8, 1687, 2048 }, 02682 { 6, 1688, 2048 }, { 7, 1689, 2048 }, { 7, 1690, 2048 }, { 8, 1691, 2048 }, { 7, 1692, 2048 }, { 8, 1693, 2048 }, { 8, 1694, 2048 }, { 9, 1695, 2048 }, 02683 { 5, 1696, 2048 }, { 6, 1697, 2048 }, { 6, 1698, 2048 }, { 7, 1699, 2048 }, { 6, 1700, 2048 }, { 7, 1701, 2048 }, { 7, 1702, 2048 }, { 8, 1703, 2048 }, 02684 { 6, 1704, 2048 }, { 7, 1705, 2048 }, { 7, 1706, 2048 }, { 8, 1707, 2048 }, { 7, 1708, 2048 }, { 8, 1709, 2048 }, { 8, 1710, 2048 }, { 9, 1711, 2048 }, 02685 { 6, 1712, 2048 }, { 7, 1713, 2048 }, { 7, 1714, 2048 }, { 8, 1715, 2048 }, { 7, 1716, 2048 }, { 8, 1717, 2048 }, { 8, 1718, 2048 }, { 9, 1719, 2048 }, 02686 { 7, 1720, 2048 }, { 8, 1721, 2048 }, { 8, 1722, 2048 }, { 9, 1723, 2048 }, { 8, 1724, 2048 }, { 9, 1725, 2048 }, { 9, 1726, 2048 }, { 10, 1727, 2048 }, 02687 { 5, 1728, 2048 }, { 6, 1729, 2048 }, { 6, 1730, 2048 }, { 7, 1731, 2048 }, { 6, 1732, 2048 }, { 7, 1733, 2048 }, { 7, 1734, 2048 }, { 8, 1735, 2048 }, 02688 { 6, 1736, 2048 }, { 7, 1737, 2048 }, { 7, 1738, 2048 }, { 8, 1739, 2048 }, { 7, 1740, 2048 }, { 8, 1741, 2048 }, { 8, 1742, 2048 }, { 9, 1743, 2048 }, 02689 { 6, 1744, 2048 }, { 7, 1745, 2048 }, { 7, 1746, 2048 }, { 8, 1747, 2048 }, { 7, 1748, 2048 }, { 8, 1749, 2048 }, { 8, 1750, 2048 }, { 9, 1751, 2048 }, 02690 { 7, 1752, 2048 }, { 8, 1753, 2048 }, { 8, 1754, 2048 }, { 9, 1755, 2048 }, { 8, 1756, 2048 }, { 9, 1757, 2048 }, { 9, 1758, 2048 }, { 10, 1759, 2048 }, 02691 { 6, 1760, 2048 }, { 7, 1761, 2048 }, { 7, 1762, 2048 }, { 8, 1763, 2048 }, { 7, 1764, 2048 }, { 8, 1765, 2048 }, { 8, 1766, 2048 }, { 9, 1767, 2048 }, 02692 { 7, 1768, 2048 }, { 8, 1769, 2048 }, { 8, 1770, 2048 }, { 9, 1771, 2048 }, { 8, 1772, 2048 }, { 9, 1773, 2048 }, { 9, 1774, 2048 }, { 10, 1775, 2048 }, 02693 { 7, 1776, 2048 }, { 8, 1777, 2048 }, { 8, 1778, 2048 }, { 9, 1779, 2048 }, { 8, 1780, 2048 }, { 9, 1781, 2048 }, { 9, 1782, 2048 }, { 10, 1783, 2048 }, 02694 { 8, 1784, 2048 }, { 9, 1785, 2048 }, { 9, 1786, 2048 }, { 10, 1787, 2048 }, { 9, 1788, 2048 }, { 10, 1789, 2048 }, { 10, 1790, 2048 }, { 11, 1791, 2048 }, 02695 { 4, 1792, 2048 }, { 5, 1793, 2048 }, { 5, 1794, 2048 }, { 6, 1795, 2048 }, { 5, 1796, 2048 }, { 6, 1797, 2048 }, { 6, 1798, 2048 }, { 7, 1799, 2048 }, 02696 { 5, 1800, 2048 }, { 6, 1801, 2048 }, { 6, 1802, 2048 }, { 7, 1803, 2048 }, { 6, 1804, 2048 }, { 7, 1805, 2048 }, { 7, 1806, 2048 }, { 8, 1807, 2048 }, 02697 { 5, 1808, 2048 }, { 6, 1809, 2048 }, { 6, 1810, 2048 }, { 7, 1811, 2048 }, { 6, 1812, 2048 }, { 7, 1813, 2048 }, { 7, 1814, 2048 }, { 8, 1815, 2048 }, 02698 { 6, 1816, 2048 }, { 7, 1817, 2048 }, { 7, 1818, 2048 }, { 8, 1819, 2048 }, { 7, 1820, 2048 }, { 8, 1821, 2048 }, { 8, 1822, 2048 }, { 9, 1823, 2048 }, 02699 { 5, 1824, 2048 }, { 6, 1825, 2048 }, { 6, 1826, 2048 }, { 7, 1827, 2048 }, { 6, 1828, 2048 }, { 7, 1829, 2048 }, { 7, 1830, 2048 }, { 8, 1831, 2048 }, 02700 { 6, 1832, 2048 }, { 7, 1833, 2048 }, { 7, 1834, 2048 }, { 8, 1835, 2048 }, { 7, 1836, 2048 }, { 8, 1837, 2048 }, { 8, 1838, 2048 }, { 9, 1839, 2048 }, 02701 { 6, 1840, 2048 }, { 7, 1841, 2048 }, { 7, 1842, 2048 }, { 8, 1843, 2048 }, { 7, 1844, 2048 }, { 8, 1845, 2048 }, { 8, 1846, 2048 }, { 9, 1847, 2048 }, 02702 { 7, 1848, 2048 }, { 8, 1849, 2048 }, { 8, 1850, 2048 }, { 9, 1851, 2048 }, { 8, 1852, 2048 }, { 9, 1853, 2048 }, { 9, 1854, 2048 }, { 10, 1855, 2048 }, 02703 { 5, 1856, 2048 }, { 6, 1857, 2048 }, { 6, 1858, 2048 }, { 7, 1859, 2048 }, { 6, 1860, 2048 }, { 7, 1861, 2048 }, { 7, 1862, 2048 }, { 8, 1863, 2048 }, 02704 { 6, 1864, 2048 }, { 7, 1865, 2048 }, { 7, 1866, 2048 }, { 8, 1867, 2048 }, { 7, 1868, 2048 }, { 8, 1869, 2048 }, { 8, 1870, 2048 }, { 9, 1871, 2048 }, 02705 { 6, 1872, 2048 }, { 7, 1873, 2048 }, { 7, 1874, 2048 }, { 8, 1875, 2048 }, { 7, 1876, 2048 }, { 8, 1877, 2048 }, { 8, 1878, 2048 }, { 9, 1879, 2048 }, 02706 { 7, 1880, 2048 }, { 8, 1881, 2048 }, { 8, 1882, 2048 }, { 9, 1883, 2048 }, { 8, 1884, 2048 }, { 9, 1885, 2048 }, { 9, 1886, 2048 }, { 10, 1887, 2048 }, 02707 { 6, 1888, 2048 }, { 7, 1889, 2048 }, { 7, 1890, 2048 }, { 8, 1891, 2048 }, { 7, 1892, 2048 }, { 8, 1893, 2048 }, { 8, 1894, 2048 }, { 9, 1895, 2048 }, 02708 { 7, 1896, 2048 }, { 8, 1897, 2048 }, { 8, 1898, 2048 }, { 9, 1899, 2048 }, { 8, 1900, 2048 }, { 9, 1901, 2048 }, { 9, 1902, 2048 }, { 10, 1903, 2048 }, 02709 { 7, 1904, 2048 }, { 8, 1905, 2048 }, { 8, 1906, 2048 }, { 9, 1907, 2048 }, { 8, 1908, 2048 }, { 9, 1909, 2048 }, { 9, 1910, 2048 }, { 10, 1911, 2048 }, 02710 { 8, 1912, 2048 }, { 9, 1913, 2048 }, { 9, 1914, 2048 }, { 10, 1915, 2048 }, { 9, 1916, 2048 }, { 10, 1917, 2048 }, { 10, 1918, 2048 }, { 11, 1919, 2048 }, 02711 { 5, 1920, 2048 }, { 6, 1921, 2048 }, { 6, 1922, 2048 }, { 7, 1923, 2048 }, { 6, 1924, 2048 }, { 7, 1925, 2048 }, { 7, 1926, 2048 }, { 8, 1927, 2048 }, 02712 { 6, 1928, 2048 }, { 7, 1929, 2048 }, { 7, 1930, 2048 }, { 8, 1931, 2048 }, { 7, 1932, 2048 }, { 8, 1933, 2048 }, { 8, 1934, 2048 }, { 9, 1935, 2048 }, 02713 { 6, 1936, 2048 }, { 7, 1937, 2048 }, { 7, 1938, 2048 }, { 8, 1939, 2048 }, { 7, 1940, 2048 }, { 8, 1941, 2048 }, { 8, 1942, 2048 }, { 9, 1943, 2048 }, 02714 { 7, 1944, 2048 }, { 8, 1945, 2048 }, { 8, 1946, 2048 }, { 9, 1947, 2048 }, { 8, 1948, 2048 }, { 9, 1949, 2048 }, { 9, 1950, 2048 }, { 10, 1951, 2048 }, 02715 { 6, 1952, 2048 }, { 7, 1953, 2048 }, { 7, 1954, 2048 }, { 8, 1955, 2048 }, { 7, 1956, 2048 }, { 8, 1957, 2048 }, { 8, 1958, 2048 }, { 9, 1959, 2048 }, 02716 { 7, 1960, 2048 }, { 8, 1961, 2048 }, { 8, 1962, 2048 }, { 9, 1963, 2048 }, { 8, 1964, 2048 }, { 9, 1965, 2048 }, { 9, 1966, 2048 }, { 10, 1967, 2048 }, 02717 { 7, 1968, 2048 }, { 8, 1969, 2048 }, { 8, 1970, 2048 }, { 9, 1971, 2048 }, { 8, 1972, 2048 }, { 9, 1973, 2048 }, { 9, 1974, 2048 }, { 10, 1975, 2048 }, 02718 { 8, 1976, 2048 }, { 9, 1977, 2048 }, { 9, 1978, 2048 }, { 10, 1979, 2048 }, { 9, 1980, 2048 }, { 10, 1981, 2048 }, { 10, 1982, 2048 }, { 11, 1983, 2048 }, 02719 { 6, 1984, 2048 }, { 7, 1985, 2048 }, { 7, 1986, 2048 }, { 8, 1987, 2048 }, { 7, 1988, 2048 }, { 8, 1989, 2048 }, { 8, 1990, 2048 }, { 9, 1991, 2048 }, 02720 { 7, 1992, 2048 }, { 8, 1993, 2048 }, { 8, 1994, 2048 }, { 9, 1995, 2048 }, { 8, 1996, 2048 }, { 9, 1997, 2048 }, { 9, 1998, 2048 }, { 10, 1999, 2048 }, 02721 { 7, 2000, 2048 }, { 8, 2001, 2048 }, { 8, 2002, 2048 }, { 9, 2003, 2048 }, { 8, 2004, 2048 }, { 9, 2005, 2048 }, { 9, 2006, 2048 }, { 10, 2007, 2048 }, 02722 { 8, 2008, 2048 }, { 9, 2009, 2048 }, { 9, 2010, 2048 }, { 10, 2011, 2048 }, { 9, 2012, 2048 }, { 10, 2013, 2048 }, { 10, 2014, 2048 }, { 11, 2015, 2048 }, 02723 { 7, 2016, 2048 }, { 8, 2017, 2048 }, { 8, 2018, 2048 }, { 9, 2019, 2048 }, { 8, 2020, 2048 }, { 9, 2021, 2048 }, { 9, 2022, 2048 }, { 10, 2023, 2048 }, 02724 { 8, 2024, 2048 }, { 9, 2025, 2048 }, { 9, 2026, 2048 }, { 10, 2027, 2048 }, { 9, 2028, 2048 }, { 10, 2029, 2048 }, { 10, 2030, 2048 }, { 11, 2031, 2048 }, 02725 { 8, 2032, 2048 }, { 9, 2033, 2048 }, { 9, 2034, 2048 }, { 10, 2035, 2048 }, { 9, 2036, 2048 }, { 10, 2037, 2048 }, { 10, 2038, 2048 }, { 11, 2039, 2048 }, 02726 { 9, 2040, 2048 }, { 10, 2041, 2048 }, { 10, 2042, 2048 }, { 11, 2043, 2048 }, { 10, 2044, 2048 }, { 11, 2045, 2048 }, { 11, 2046, 2048 }, { 12, 2047, 2048 }, 02727 #endif 02728 #endif 02729 #endif 02730 #endif 02731 #endif 02732 #endif 02733 }; 02734 02735 /* find a hole and free as required, return -1 if no hole found */ 02736 static int find_hole(void) 02737 { 02738 unsigned x; 02739 int y, z; 02740 for (z = -1, y = INT_MAX, x = 0; x < FP_ENTRIES; x++) { 02741 if (fp_cache[x].lru_count < y && fp_cache[x].lock == 0) { 02742 z = x; 02743 y = fp_cache[x].lru_count; 02744 } 02745 } 02746 02747 /* decrease all */ 02748 for (x = 0; x < FP_ENTRIES; x++) { 02749 if (fp_cache[x].lru_count > 3) { 02750 --(fp_cache[x].lru_count); 02751 } 02752 } 02753 02754 /* free entry z */ 02755 if (z >= 0 && fp_cache[z].g) { 02756 mp_clear(&fp_cache[z].mu); 02757 ecc_del_point(fp_cache[z].g); 02758 fp_cache[z].g = NULL; 02759 for (x = 0; x < (1U<<FP_LUT); x++) { 02760 ecc_del_point(fp_cache[z].LUT[x]); 02761 fp_cache[z].LUT[x] = NULL; 02762 } 02763 fp_cache[z].lru_count = 0; 02764 } 02765 return z; 02766 } 02767 02768 /* determine if a base is already in the cache and if so, where */ 02769 static int find_base(ecc_point* g) 02770 { 02771 int x; 02772 for (x = 0; x < FP_ENTRIES; x++) { 02773 if (fp_cache[x].g != NULL && 02774 mp_cmp(&fp_cache[x].g->x, &g->x) == MP_EQ && 02775 mp_cmp(&fp_cache[x].g->y, &g->y) == MP_EQ && 02776 mp_cmp(&fp_cache[x].g->z, &g->z) == MP_EQ) { 02777 break; 02778 } 02779 } 02780 if (x == FP_ENTRIES) { 02781 x = -1; 02782 } 02783 return x; 02784 } 02785 02786 /* add a new base to the cache */ 02787 static int add_entry(int idx, ecc_point *g) 02788 { 02789 unsigned x, y; 02790 02791 /* allocate base and LUT */ 02792 fp_cache[idx].g = ecc_new_point(); 02793 if (fp_cache[idx].g == NULL) { 02794 return GEN_MEM_ERR; 02795 } 02796 02797 /* copy x and y */ 02798 if ((mp_copy(&g->x, &fp_cache[idx].g->x) != MP_OKAY) || 02799 (mp_copy(&g->y, &fp_cache[idx].g->y) != MP_OKAY) || 02800 (mp_copy(&g->z, &fp_cache[idx].g->z) != MP_OKAY)) { 02801 ecc_del_point(fp_cache[idx].g); 02802 fp_cache[idx].g = NULL; 02803 return GEN_MEM_ERR; 02804 } 02805 02806 for (x = 0; x < (1U<<FP_LUT); x++) { 02807 fp_cache[idx].LUT[x] = ecc_new_point(); 02808 if (fp_cache[idx].LUT[x] == NULL) { 02809 for (y = 0; y < x; y++) { 02810 ecc_del_point(fp_cache[idx].LUT[y]); 02811 fp_cache[idx].LUT[y] = NULL; 02812 } 02813 ecc_del_point(fp_cache[idx].g); 02814 fp_cache[idx].g = NULL; 02815 fp_cache[idx].lru_count = 0; 02816 return GEN_MEM_ERR; 02817 } 02818 } 02819 02820 fp_cache[idx].lru_count = 0; 02821 02822 return MP_OKAY; 02823 } 02824 02825 /* build the LUT by spacing the bits of the input by #modulus/FP_LUT bits apart 02826 * 02827 * The algorithm builds patterns in increasing bit order by first making all 02828 * single bit input patterns, then all two bit input patterns and so on 02829 */ 02830 static int build_lut(int idx, mp_int* modulus, mp_digit* mp, mp_int* mu) 02831 { 02832 unsigned x, y, err, bitlen, lut_gap; 02833 mp_int tmp; 02834 02835 if (mp_init(&tmp) != MP_OKAY) 02836 return GEN_MEM_ERR; 02837 02838 /* sanity check to make sure lut_order table is of correct size, 02839 should compile out to a NOP if true */ 02840 if ((sizeof(lut_orders) / sizeof(lut_orders[0])) < (1U<<FP_LUT)) { 02841 err = BAD_FUNC_ARG; 02842 } 02843 else { 02844 /* get bitlen and round up to next multiple of FP_LUT */ 02845 bitlen = mp_unsigned_bin_size(modulus) << 3; 02846 x = bitlen % FP_LUT; 02847 if (x) { 02848 bitlen += FP_LUT - x; 02849 } 02850 lut_gap = bitlen / FP_LUT; 02851 02852 /* init the mu */ 02853 err = mp_init_copy(&fp_cache[idx].mu, mu); 02854 } 02855 02856 /* copy base */ 02857 if (err == MP_OKAY) { 02858 if ((mp_mulmod(&fp_cache[idx].g->x, mu, modulus, 02859 &fp_cache[idx].LUT[1]->x) != MP_OKAY) || 02860 (mp_mulmod(&fp_cache[idx].g->y, mu, modulus, 02861 &fp_cache[idx].LUT[1]->y) != MP_OKAY) || 02862 (mp_mulmod(&fp_cache[idx].g->z, mu, modulus, 02863 &fp_cache[idx].LUT[1]->z) != MP_OKAY)) { 02864 err = MP_MULMOD_E; 02865 } 02866 } 02867 02868 /* make all single bit entries */ 02869 for (x = 1; x < FP_LUT; x++) { 02870 if (err != MP_OKAY) 02871 break; 02872 if ((mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->x, 02873 &fp_cache[idx].LUT[1<<x]->x) != MP_OKAY) || 02874 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->y, 02875 &fp_cache[idx].LUT[1<<x]->y) != MP_OKAY) || 02876 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->z, 02877 &fp_cache[idx].LUT[1<<x]->z) != MP_OKAY)){ 02878 err = MP_INIT_E; 02879 break; 02880 } else { 02881 02882 /* now double it bitlen/FP_LUT times */ 02883 for (y = 0; y < lut_gap; y++) { 02884 if ((err = ecc_projective_dbl_point(fp_cache[idx].LUT[1<<x], 02885 fp_cache[idx].LUT[1<<x], modulus, mp)) != MP_OKAY) { 02886 break; 02887 } 02888 } 02889 } 02890 } 02891 02892 /* now make all entries in increase order of hamming weight */ 02893 for (x = 2; x <= FP_LUT; x++) { 02894 if (err != MP_OKAY) 02895 break; 02896 for (y = 0; y < (1UL<<FP_LUT); y++) { 02897 if (err != MP_OKAY) 02898 break; 02899 if (lut_orders[y].ham != (int)x) continue; 02900 02901 /* perform the add */ 02902 if ((err = ecc_projective_add_point( 02903 fp_cache[idx].LUT[lut_orders[y].terma], 02904 fp_cache[idx].LUT[lut_orders[y].termb], 02905 fp_cache[idx].LUT[y], modulus, mp)) != MP_OKAY) { 02906 break; 02907 } 02908 } 02909 } 02910 02911 /* now map all entries back to affine space to make point addition faster */ 02912 for (x = 1; x < (1UL<<FP_LUT); x++) { 02913 if (err != MP_OKAY) 02914 break; 02915 02916 /* convert z to normal from montgomery */ 02917 err = mp_montgomery_reduce(&fp_cache[idx].LUT[x]->z, modulus, *mp); 02918 02919 /* invert it */ 02920 if (err == MP_OKAY) 02921 err = mp_invmod(&fp_cache[idx].LUT[x]->z, modulus, 02922 &fp_cache[idx].LUT[x]->z); 02923 02924 if (err == MP_OKAY) 02925 /* now square it */ 02926 err = mp_sqrmod(&fp_cache[idx].LUT[x]->z, modulus, &tmp); 02927 02928 if (err == MP_OKAY) 02929 /* fix x */ 02930 err = mp_mulmod(&fp_cache[idx].LUT[x]->x, &tmp, modulus, 02931 &fp_cache[idx].LUT[x]->x); 02932 02933 if (err == MP_OKAY) 02934 /* get 1/z^3 */ 02935 err = mp_mulmod(&tmp, &fp_cache[idx].LUT[x]->z, modulus, &tmp); 02936 02937 if (err == MP_OKAY) 02938 /* fix y */ 02939 err = mp_mulmod(&fp_cache[idx].LUT[x]->y, &tmp, modulus, 02940 &fp_cache[idx].LUT[x]->y); 02941 02942 if (err == MP_OKAY) 02943 /* free z */ 02944 mp_clear(&fp_cache[idx].LUT[x]->z); 02945 } 02946 mp_clear(&tmp); 02947 02948 if (err == MP_OKAY) 02949 return MP_OKAY; 02950 02951 /* err cleanup */ 02952 for (y = 0; y < (1U<<FP_LUT); y++) { 02953 ecc_del_point(fp_cache[idx].LUT[y]); 02954 fp_cache[idx].LUT[y] = NULL; 02955 } 02956 ecc_del_point(fp_cache[idx].g); 02957 fp_cache[idx].g = NULL; 02958 fp_cache[idx].lru_count = 0; 02959 mp_clear(&fp_cache[idx].mu); 02960 mp_clear(&tmp); 02961 02962 return err; 02963 } 02964 02965 /* perform a fixed point ECC mulmod */ 02966 static int accel_fp_mul(int idx, mp_int* k, ecc_point *R, mp_int* modulus, 02967 mp_digit* mp, int map) 02968 { 02969 #define KB_SIZE 128 02970 02971 #ifdef CYASSL_SMALL_STACK 02972 unsigned char* kb; 02973 #else 02974 unsigned char kb[128]; 02975 #endif 02976 int x; 02977 unsigned y, z, err, bitlen, bitpos, lut_gap, first; 02978 mp_int tk; 02979 02980 if (mp_init(&tk) != MP_OKAY) 02981 return MP_INIT_E; 02982 02983 /* if it's smaller than modulus we fine */ 02984 if (mp_unsigned_bin_size(k) > mp_unsigned_bin_size(modulus)) { 02985 mp_int order; 02986 if (mp_init(&order) != MP_OKAY) { 02987 mp_clear(&tk); 02988 return MP_INIT_E; 02989 } 02990 02991 /* find order */ 02992 y = mp_unsigned_bin_size(modulus); 02993 for (x = 0; ecc_sets[x].size; x++) { 02994 if (y <= (unsigned)ecc_sets[x].size) break; 02995 } 02996 02997 /* back off if we are on the 521 bit curve */ 02998 if (y == 66) --x; 02999 03000 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 03001 mp_clear(&order); 03002 mp_clear(&tk); 03003 return err; 03004 } 03005 03006 /* k must be less than modulus */ 03007 if (mp_cmp(k, &order) != MP_LT) { 03008 if ((err = mp_mod(k, &order, &tk)) != MP_OKAY) { 03009 mp_clear(&tk); 03010 mp_clear(&order); 03011 return err; 03012 } 03013 } else { 03014 mp_copy(k, &tk); 03015 } 03016 mp_clear(&order); 03017 } else { 03018 mp_copy(k, &tk); 03019 } 03020 03021 /* get bitlen and round up to next multiple of FP_LUT */ 03022 bitlen = mp_unsigned_bin_size(modulus) << 3; 03023 x = bitlen % FP_LUT; 03024 if (x) { 03025 bitlen += FP_LUT - x; 03026 } 03027 lut_gap = bitlen / FP_LUT; 03028 03029 /* get the k value */ 03030 if (mp_unsigned_bin_size(&tk) > (int)(KB_SIZE - 2)) { 03031 mp_clear(&tk); 03032 return BUFFER_E; 03033 } 03034 03035 /* store k */ 03036 #ifdef CYASSL_SMALL_STACK 03037 kb = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03038 if (kb == NULL) 03039 return MEMORY_E; 03040 #endif 03041 03042 XMEMSET(kb, 0, KB_SIZE); 03043 if ((err = mp_to_unsigned_bin(&tk, kb)) != MP_OKAY) { 03044 mp_clear(&tk); 03045 } 03046 else { 03047 /* let's reverse kb so it's little endian */ 03048 x = 0; 03049 y = mp_unsigned_bin_size(&tk) - 1; 03050 mp_clear(&tk); 03051 03052 while ((unsigned)x < y) { 03053 z = kb[x]; kb[x] = kb[y]; kb[y] = z; 03054 ++x; --y; 03055 } 03056 03057 /* at this point we can start, yipee */ 03058 first = 1; 03059 for (x = lut_gap-1; x >= 0; x--) { 03060 /* extract FP_LUT bits from kb spread out by lut_gap bits and offset 03061 by x bits from the start */ 03062 bitpos = x; 03063 for (y = z = 0; y < FP_LUT; y++) { 03064 z |= ((kb[bitpos>>3] >> (bitpos&7)) & 1) << y; 03065 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid 03066 the mult in each loop */ 03067 } 03068 03069 /* double if not first */ 03070 if (!first) { 03071 if ((err = ecc_projective_dbl_point(R, R, modulus, 03072 mp)) != MP_OKAY) { 03073 break; 03074 } 03075 } 03076 03077 /* add if not first, otherwise copy */ 03078 if (!first && z) { 03079 if ((err = ecc_projective_add_point(R, fp_cache[idx].LUT[z], R, 03080 modulus, mp)) != MP_OKAY) { 03081 break; 03082 } 03083 } else if (z) { 03084 if ((mp_copy(&fp_cache[idx].LUT[z]->x, &R->x) != MP_OKAY) || 03085 (mp_copy(&fp_cache[idx].LUT[z]->y, &R->y) != MP_OKAY) || 03086 (mp_copy(&fp_cache[idx].mu, &R->z) != MP_OKAY)) { 03087 err = GEN_MEM_ERR; 03088 break; 03089 } 03090 first = 0; 03091 } 03092 } 03093 } 03094 03095 if (err == MP_OKAY) { 03096 z = 0; 03097 XMEMSET(kb, 0, KB_SIZE); 03098 /* map R back from projective space */ 03099 if (map) { 03100 err = ecc_map(R, modulus, mp); 03101 } else { 03102 err = MP_OKAY; 03103 } 03104 } 03105 03106 #ifdef CYASSL_SMALL_STACK 03107 XFREE(kb, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03108 #endif 03109 03110 #undef KB_SIZE 03111 03112 return err; 03113 } 03114 03115 #ifdef ECC_SHAMIR 03116 /* perform a fixed point ECC mulmod */ 03117 static int accel_fp_mul2add(int idx1, int idx2, 03118 mp_int* kA, mp_int* kB, 03119 ecc_point *R, mp_int* modulus, mp_digit* mp) 03120 { 03121 #define KB_SIZE 128 03122 03123 #ifdef CYASSL_SMALL_STACK 03124 unsigned char* kb[2]; 03125 #else 03126 unsigned char kb[2][128]; 03127 #endif 03128 int x; 03129 unsigned y, z, err, bitlen, bitpos, lut_gap, first, zA, zB; 03130 mp_int tka; 03131 mp_int tkb; 03132 mp_int order; 03133 03134 if (mp_init_multi(&tka, &tkb, 0, 0, 0, 0) != MP_OKAY) 03135 return MP_INIT_E; 03136 03137 /* if it's smaller than modulus we fine */ 03138 if (mp_unsigned_bin_size(kA) > mp_unsigned_bin_size(modulus)) { 03139 /* find order */ 03140 y = mp_unsigned_bin_size(modulus); 03141 for (x = 0; ecc_sets[x].size; x++) { 03142 if (y <= (unsigned)ecc_sets[x].size) break; 03143 } 03144 03145 /* back off if we are on the 521 bit curve */ 03146 if (y == 66) --x; 03147 03148 if ((err = mp_init(&order)) != MP_OKAY) { 03149 mp_clear(&tkb); 03150 mp_clear(&tka); 03151 return err; 03152 } 03153 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 03154 mp_clear(&tkb); 03155 mp_clear(&tka); 03156 mp_clear(&order); 03157 return err; 03158 } 03159 03160 /* kA must be less than modulus */ 03161 if (mp_cmp(kA, &order) != MP_LT) { 03162 if ((err = mp_mod(kA, &order, &tka)) != MP_OKAY) { 03163 mp_clear(&tkb); 03164 mp_clear(&tka); 03165 mp_clear(&order); 03166 return err; 03167 } 03168 } else { 03169 mp_copy(kA, &tka); 03170 } 03171 mp_clear(&order); 03172 } else { 03173 mp_copy(kA, &tka); 03174 } 03175 03176 /* if it's smaller than modulus we fine */ 03177 if (mp_unsigned_bin_size(kB) > mp_unsigned_bin_size(modulus)) { 03178 /* find order */ 03179 y = mp_unsigned_bin_size(modulus); 03180 for (x = 0; ecc_sets[x].size; x++) { 03181 if (y <= (unsigned)ecc_sets[x].size) break; 03182 } 03183 03184 /* back off if we are on the 521 bit curve */ 03185 if (y == 66) --x; 03186 03187 if ((err = mp_init(&order)) != MP_OKAY) { 03188 mp_clear(&tkb); 03189 mp_clear(&tka); 03190 return err; 03191 } 03192 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 03193 mp_clear(&tkb); 03194 mp_clear(&tka); 03195 mp_clear(&order); 03196 return err; 03197 } 03198 03199 /* kB must be less than modulus */ 03200 if (mp_cmp(kB, &order) != MP_LT) { 03201 if ((err = mp_mod(kB, &order, &tkb)) != MP_OKAY) { 03202 mp_clear(&tkb); 03203 mp_clear(&tka); 03204 mp_clear(&order); 03205 return err; 03206 } 03207 } else { 03208 mp_copy(kB, &tkb); 03209 } 03210 mp_clear(&order); 03211 } else { 03212 mp_copy(kB, &tkb); 03213 } 03214 03215 /* get bitlen and round up to next multiple of FP_LUT */ 03216 bitlen = mp_unsigned_bin_size(modulus) << 3; 03217 x = bitlen % FP_LUT; 03218 if (x) { 03219 bitlen += FP_LUT - x; 03220 } 03221 lut_gap = bitlen / FP_LUT; 03222 03223 /* get the k value */ 03224 if ((mp_unsigned_bin_size(&tka) > (int)(KB_SIZE - 2)) || 03225 (mp_unsigned_bin_size(&tkb) > (int)(KB_SIZE - 2)) ) { 03226 mp_clear(&tka); 03227 mp_clear(&tkb); 03228 return BUFFER_E; 03229 } 03230 03231 /* store k */ 03232 #ifdef CYASSL_SMALL_STACK 03233 kb[0] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03234 if (kb[0] == NULL) 03235 return MEMORY_E; 03236 #endif 03237 03238 XMEMSET(kb[0], 0, KB_SIZE); 03239 if ((err = mp_to_unsigned_bin(&tka, kb[0])) != MP_OKAY) { 03240 mp_clear(&tka); 03241 mp_clear(&tkb); 03242 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER); 03243 return err; 03244 } 03245 03246 /* let's reverse kb so it's little endian */ 03247 x = 0; 03248 y = mp_unsigned_bin_size(&tka) - 1; 03249 mp_clear(&tka); 03250 while ((unsigned)x < y) { 03251 z = kb[0][x]; kb[0][x] = kb[0][y]; kb[0][y] = z; 03252 ++x; --y; 03253 } 03254 03255 /* store b */ 03256 #ifdef CYASSL_SMALL_STACK 03257 kb[1] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03258 if (kb[1] == NULL) { 03259 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER); 03260 return MEMORY_E; 03261 } 03262 #endif 03263 03264 XMEMSET(kb[1], 0, KB_SIZE); 03265 if ((err = mp_to_unsigned_bin(&tkb, kb[1])) != MP_OKAY) { 03266 mp_clear(&tkb); 03267 } 03268 else { 03269 x = 0; 03270 y = mp_unsigned_bin_size(&tkb) - 1; 03271 mp_clear(&tkb); 03272 while ((unsigned)x < y) { 03273 z = kb[1][x]; kb[1][x] = kb[1][y]; kb[1][y] = z; 03274 ++x; --y; 03275 } 03276 03277 /* at this point we can start, yipee */ 03278 first = 1; 03279 for (x = lut_gap-1; x >= 0; x--) { 03280 /* extract FP_LUT bits from kb spread out by lut_gap bits and 03281 offset by x bits from the start */ 03282 bitpos = x; 03283 for (y = zA = zB = 0; y < FP_LUT; y++) { 03284 zA |= ((kb[0][bitpos>>3] >> (bitpos&7)) & 1) << y; 03285 zB |= ((kb[1][bitpos>>3] >> (bitpos&7)) & 1) << y; 03286 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid 03287 the mult in each loop */ 03288 } 03289 03290 /* double if not first */ 03291 if (!first) { 03292 if ((err = ecc_projective_dbl_point(R, R, modulus, 03293 mp)) != MP_OKAY) { 03294 break; 03295 } 03296 } 03297 03298 /* add if not first, otherwise copy */ 03299 if (!first) { 03300 if (zA) { 03301 if ((err = ecc_projective_add_point(R, fp_cache[idx1].LUT[zA], 03302 R, modulus, mp)) != MP_OKAY) { 03303 break; 03304 } 03305 } 03306 if (zB) { 03307 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB], 03308 R, modulus, mp)) != MP_OKAY) { 03309 break; 03310 } 03311 } 03312 } else { 03313 if (zA) { 03314 if ((mp_copy(&fp_cache[idx1].LUT[zA]->x, &R->x) != MP_OKAY) || 03315 (mp_copy(&fp_cache[idx1].LUT[zA]->y, &R->y) != MP_OKAY) || 03316 (mp_copy(&fp_cache[idx1].mu, &R->z) != MP_OKAY)) { 03317 err = GEN_MEM_ERR; 03318 break; 03319 } 03320 first = 0; 03321 } 03322 if (zB && first == 0) { 03323 if (zB) { 03324 if ((err = ecc_projective_add_point(R, 03325 fp_cache[idx2].LUT[zB], R, modulus, mp)) != MP_OKAY){ 03326 break; 03327 } 03328 } 03329 } else if (zB && first == 1) { 03330 if ((mp_copy(&fp_cache[idx2].LUT[zB]->x, &R->x) != MP_OKAY) || 03331 (mp_copy(&fp_cache[idx2].LUT[zB]->y, &R->y) != MP_OKAY) || 03332 (mp_copy(&fp_cache[idx2].mu, &R->z) != MP_OKAY)) { 03333 err = GEN_MEM_ERR; 03334 break; 03335 } 03336 first = 0; 03337 } 03338 } 03339 } 03340 } 03341 03342 XMEMSET(kb[0], 0, KB_SIZE); 03343 XMEMSET(kb[1], 0, KB_SIZE); 03344 03345 #ifdef CYASSL_SMALL_STACK 03346 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER); 03347 XFREE(kb[1], NULL, DYNAMIC_TYPE_TMP_BUFFER); 03348 #endif 03349 03350 #undef KB_SIZE 03351 03352 return ecc_map(R, modulus, mp); 03353 } 03354 03355 /** ECC Fixed Point mulmod global 03356 Computes kA*A + kB*B = C using Shamir's Trick 03357 A First point to multiply 03358 kA What to multiple A by 03359 B Second point to multiply 03360 kB What to multiple B by 03361 C [out] Destination point (can overlap with A or B) 03362 modulus Modulus for curve 03363 return MP_OKAY on success 03364 */ 03365 int ecc_mul2add(ecc_point* A, mp_int* kA, 03366 ecc_point* B, mp_int* kB, 03367 ecc_point* C, mp_int* modulus) 03368 { 03369 int idx1 = -1, idx2 = -1, err = MP_OKAY, mpInit = 0; 03370 mp_digit mp; 03371 mp_int mu; 03372 03373 err = mp_init(&mu); 03374 if (err != MP_OKAY) 03375 return err; 03376 03377 #ifndef HAVE_THREAD_LS 03378 if (initMutex == 0) { 03379 InitMutex(&ecc_fp_lock); 03380 initMutex = 1; 03381 } 03382 if (LockMutex(&ecc_fp_lock) != 0) 03383 return BAD_MUTEX_E; 03384 #endif /* HAVE_THREAD_LS */ 03385 03386 /* find point */ 03387 idx1 = find_base(A); 03388 03389 /* no entry? */ 03390 if (idx1 == -1) { 03391 /* find hole and add it */ 03392 if ((idx1 = find_hole()) >= 0) { 03393 err = add_entry(idx1, A); 03394 } 03395 } 03396 if (err == MP_OKAY && idx1 != -1) { 03397 /* increment LRU */ 03398 ++(fp_cache[idx1].lru_count); 03399 } 03400 03401 if (err == MP_OKAY) 03402 /* find point */ 03403 idx2 = find_base(B); 03404 03405 if (err == MP_OKAY) { 03406 /* no entry? */ 03407 if (idx2 == -1) { 03408 /* find hole and add it */ 03409 if ((idx2 = find_hole()) >= 0) 03410 err = add_entry(idx2, B); 03411 } 03412 } 03413 03414 if (err == MP_OKAY && idx2 != -1) { 03415 /* increment LRU */ 03416 ++(fp_cache[idx2].lru_count); 03417 } 03418 03419 if (err == MP_OKAY) { 03420 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03421 if (idx1 >= 0 && fp_cache[idx1].lru_count == 2) { 03422 /* compute mp */ 03423 err = mp_montgomery_setup(modulus, &mp); 03424 03425 if (err == MP_OKAY) { 03426 mpInit = 1; 03427 err = mp_montgomery_calc_normalization(&mu, modulus); 03428 } 03429 03430 if (err == MP_OKAY) 03431 /* build the LUT */ 03432 err = build_lut(idx1, modulus, &mp, &mu); 03433 } 03434 } 03435 03436 if (err == MP_OKAY) { 03437 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03438 if (idx2 >= 0 && fp_cache[idx2].lru_count == 2) { 03439 if (mpInit == 0) { 03440 /* compute mp */ 03441 err = mp_montgomery_setup(modulus, &mp); 03442 if (err == MP_OKAY) { 03443 mpInit = 1; 03444 err = mp_montgomery_calc_normalization(&mu, modulus); 03445 } 03446 } 03447 03448 if (err == MP_OKAY) 03449 /* build the LUT */ 03450 err = build_lut(idx2, modulus, &mp, &mu); 03451 } 03452 } 03453 03454 03455 if (err == MP_OKAY) { 03456 if (idx1 >=0 && idx2 >= 0 && fp_cache[idx1].lru_count >= 2 && 03457 fp_cache[idx2].lru_count >= 2) { 03458 if (mpInit == 0) { 03459 /* compute mp */ 03460 err = mp_montgomery_setup(modulus, &mp); 03461 } 03462 if (err == MP_OKAY) 03463 err = accel_fp_mul2add(idx1, idx2, kA, kB, C, modulus, &mp); 03464 } else { 03465 err = normal_ecc_mul2add(A, kA, B, kB, C, modulus); 03466 } 03467 } 03468 03469 #ifndef HAVE_THREAD_LS 03470 UnLockMutex(&ecc_fp_lock); 03471 #endif /* HAVE_THREAD_LS */ 03472 mp_clear(&mu); 03473 03474 return err; 03475 } 03476 #endif 03477 03478 /** ECC Fixed Point mulmod global 03479 k The multiplicand 03480 G Base point to multiply 03481 R [out] Destination of product 03482 modulus The modulus for the curve 03483 map [boolean] If non-zero maps the point back to affine co-ordinates, 03484 otherwise it's left in jacobian-montgomery form 03485 return MP_OKAY if successful 03486 */ 03487 int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus, 03488 int map) 03489 { 03490 int idx, err = MP_OKAY; 03491 mp_digit mp; 03492 mp_int mu; 03493 int mpSetup = 0; 03494 03495 if (mp_init(&mu) != MP_OKAY) 03496 return MP_INIT_E; 03497 03498 #ifndef HAVE_THREAD_LS 03499 if (initMutex == 0) { 03500 InitMutex(&ecc_fp_lock); 03501 initMutex = 1; 03502 } 03503 03504 if (LockMutex(&ecc_fp_lock) != 0) 03505 return BAD_MUTEX_E; 03506 #endif /* HAVE_THREAD_LS */ 03507 03508 /* find point */ 03509 idx = find_base(G); 03510 03511 /* no entry? */ 03512 if (idx == -1) { 03513 /* find hole and add it */ 03514 idx = find_hole(); 03515 03516 if (idx >= 0) 03517 err = add_entry(idx, G); 03518 } 03519 if (err == MP_OKAY && idx != -1) { 03520 /* increment LRU */ 03521 ++(fp_cache[idx].lru_count); 03522 } 03523 03524 03525 if (err == MP_OKAY) { 03526 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03527 if (idx >= 0 && fp_cache[idx].lru_count == 2) { 03528 /* compute mp */ 03529 err = mp_montgomery_setup(modulus, &mp); 03530 03531 if (err == MP_OKAY) { 03532 /* compute mu */ 03533 mpSetup = 1; 03534 err = mp_montgomery_calc_normalization(&mu, modulus); 03535 } 03536 03537 if (err == MP_OKAY) 03538 /* build the LUT */ 03539 err = build_lut(idx, modulus, &mp, &mu); 03540 } 03541 } 03542 03543 if (err == MP_OKAY) { 03544 if (idx >= 0 && fp_cache[idx].lru_count >= 2) { 03545 if (mpSetup == 0) { 03546 /* compute mp */ 03547 err = mp_montgomery_setup(modulus, &mp); 03548 } 03549 if (err == MP_OKAY) 03550 err = accel_fp_mul(idx, k, R, modulus, &mp, map); 03551 } else { 03552 err = normal_ecc_mulmod(k, G, R, modulus, map); 03553 } 03554 } 03555 03556 #ifndef HAVE_THREAD_LS 03557 UnLockMutex(&ecc_fp_lock); 03558 #endif /* HAVE_THREAD_LS */ 03559 mp_clear(&mu); 03560 03561 return err; 03562 } 03563 03564 /* helper function for freeing the cache ... 03565 must be called with the cache mutex locked */ 03566 static void ecc_fp_free_cache(void) 03567 { 03568 unsigned x, y; 03569 for (x = 0; x < FP_ENTRIES; x++) { 03570 if (fp_cache[x].g != NULL) { 03571 for (y = 0; y < (1U<<FP_LUT); y++) { 03572 ecc_del_point(fp_cache[x].LUT[y]); 03573 fp_cache[x].LUT[y] = NULL; 03574 } 03575 ecc_del_point(fp_cache[x].g); 03576 fp_cache[x].g = NULL; 03577 mp_clear(&fp_cache[x].mu); 03578 fp_cache[x].lru_count = 0; 03579 fp_cache[x].lock = 0; 03580 } 03581 } 03582 } 03583 03584 /** Free the Fixed Point cache */ 03585 void ecc_fp_free(void) 03586 { 03587 #ifndef HAVE_THREAD_LS 03588 if (initMutex == 0) { 03589 InitMutex(&ecc_fp_lock); 03590 initMutex = 1; 03591 } 03592 03593 if (LockMutex(&ecc_fp_lock) == 0) { 03594 #endif /* HAVE_THREAD_LS */ 03595 03596 ecc_fp_free_cache(); 03597 03598 #ifndef HAVE_THREAD_LS 03599 UnLockMutex(&ecc_fp_lock); 03600 FreeMutex(&ecc_fp_lock); 03601 initMutex = 0; 03602 } 03603 #endif /* HAVE_THREAD_LS */ 03604 } 03605 03606 03607 #endif /* FP_ECC */ 03608 03609 #ifdef HAVE_ECC_ENCRYPT 03610 03611 03612 enum ecCliState { 03613 ecCLI_INIT = 1, 03614 ecCLI_SALT_GET = 2, 03615 ecCLI_SALT_SET = 3, 03616 ecCLI_SENT_REQ = 4, 03617 ecCLI_RECV_RESP = 5, 03618 ecCLI_BAD_STATE = 99 03619 }; 03620 03621 enum ecSrvState { 03622 ecSRV_INIT = 1, 03623 ecSRV_SALT_GET = 2, 03624 ecSRV_SALT_SET = 3, 03625 ecSRV_RECV_REQ = 4, 03626 ecSRV_SENT_RESP = 5, 03627 ecSRV_BAD_STATE = 99 03628 }; 03629 03630 03631 struct ecEncCtx { 03632 byte* kdfSalt; /* optional salt for kdf */ 03633 byte* kdfInfo; /* optional info for kdf */ 03634 byte* macSalt; /* optional salt for mac */ 03635 word32 kdfSaltSz; /* size of kdfSalt */ 03636 word32 kdfInfoSz; /* size of kdfInfo */ 03637 word32 macSaltSz; /* size of macSalt */ 03638 byte clientSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */ 03639 byte serverSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */ 03640 byte encAlgo; /* which encryption type */ 03641 byte kdfAlgo; /* which key derivation function type */ 03642 byte macAlgo; /* which mac function type */ 03643 byte protocol; /* are we REQ_RESP client or server ? */ 03644 byte cliSt; /* protocol state, for sanity checks */ 03645 byte srvSt; /* protocol state, for sanity checks */ 03646 }; 03647 03648 03649 const byte* ecc_ctx_get_own_salt(ecEncCtx* ctx) 03650 { 03651 if (ctx == NULL || ctx->protocol == 0) 03652 return NULL; 03653 03654 if (ctx->protocol == REQ_RESP_CLIENT) { 03655 if (ctx->cliSt == ecCLI_INIT) { 03656 ctx->cliSt = ecCLI_SALT_GET; 03657 return ctx->clientSalt; 03658 } 03659 else { 03660 ctx->cliSt = ecCLI_BAD_STATE; 03661 return NULL; 03662 } 03663 } 03664 else if (ctx->protocol == REQ_RESP_SERVER) { 03665 if (ctx->srvSt == ecSRV_INIT) { 03666 ctx->srvSt = ecSRV_SALT_GET; 03667 return ctx->serverSalt; 03668 } 03669 else { 03670 ctx->srvSt = ecSRV_BAD_STATE; 03671 return NULL; 03672 } 03673 } 03674 03675 return NULL; 03676 } 03677 03678 03679 static const char* exchange_info = "Secure Message Exchange"; 03680 03681 int ecc_ctx_set_peer_salt(ecEncCtx* ctx, const byte* salt) 03682 { 03683 byte tmp[EXCHANGE_SALT_SZ/2]; 03684 int halfSz = EXCHANGE_SALT_SZ/2; 03685 03686 if (ctx == NULL || ctx->protocol == 0 || salt == NULL) 03687 return BAD_FUNC_ARG; 03688 03689 if (ctx->protocol == REQ_RESP_CLIENT) { 03690 XMEMCPY(ctx->serverSalt, salt, EXCHANGE_SALT_SZ); 03691 if (ctx->cliSt == ecCLI_SALT_GET) 03692 ctx->cliSt = ecCLI_SALT_SET; 03693 else { 03694 ctx->cliSt = ecCLI_BAD_STATE; 03695 return BAD_ENC_STATE_E; 03696 } 03697 } 03698 else { 03699 XMEMCPY(ctx->clientSalt, salt, EXCHANGE_SALT_SZ); 03700 if (ctx->srvSt == ecSRV_SALT_GET) 03701 ctx->srvSt = ecSRV_SALT_SET; 03702 else { 03703 ctx->srvSt = ecSRV_BAD_STATE; 03704 return BAD_ENC_STATE_E; 03705 } 03706 } 03707 03708 /* mix half and half */ 03709 /* tmp stores 2nd half of client before overwrite */ 03710 XMEMCPY(tmp, ctx->clientSalt + halfSz, halfSz); 03711 XMEMCPY(ctx->clientSalt + halfSz, ctx->serverSalt, halfSz); 03712 XMEMCPY(ctx->serverSalt, tmp, halfSz); 03713 03714 ctx->kdfSalt = ctx->clientSalt; 03715 ctx->kdfSaltSz = EXCHANGE_SALT_SZ; 03716 03717 ctx->macSalt = ctx->serverSalt; 03718 ctx->macSaltSz = EXCHANGE_SALT_SZ; 03719 03720 ctx->kdfInfo = (byte*)exchange_info; 03721 ctx->kdfInfoSz = EXCHANGE_INFO_SZ; 03722 03723 return 0; 03724 } 03725 03726 03727 static int ecc_ctx_set_salt(ecEncCtx* ctx, int flags, RNG* rng) 03728 { 03729 byte* saltBuffer = NULL; 03730 03731 if (ctx == NULL || rng == NULL || flags == 0) 03732 return BAD_FUNC_ARG; 03733 03734 saltBuffer = (flags == REQ_RESP_CLIENT) ? ctx->clientSalt : ctx->serverSalt; 03735 03736 return RNG_GenerateBlock(rng, saltBuffer, EXCHANGE_SALT_SZ); 03737 } 03738 03739 03740 static void ecc_ctx_init(ecEncCtx* ctx, int flags) 03741 { 03742 if (ctx) { 03743 XMEMSET(ctx, 0, sizeof(ecEncCtx)); 03744 03745 ctx->encAlgo = ecAES_128_CBC; 03746 ctx->kdfAlgo = ecHKDF_SHA256; 03747 ctx->macAlgo = ecHMAC_SHA256; 03748 ctx->protocol = (byte)flags; 03749 03750 if (flags == REQ_RESP_CLIENT) 03751 ctx->cliSt = ecCLI_INIT; 03752 if (flags == REQ_RESP_SERVER) 03753 ctx->srvSt = ecSRV_INIT; 03754 } 03755 } 03756 03757 03758 /* allow ecc context reset so user doesn't have to init/free for resue */ 03759 int ecc_ctx_reset(ecEncCtx* ctx, RNG* rng) 03760 { 03761 if (ctx == NULL || rng == NULL) 03762 return BAD_FUNC_ARG; 03763 03764 ecc_ctx_init(ctx, ctx->protocol); 03765 return ecc_ctx_set_salt(ctx, ctx->protocol, rng); 03766 } 03767 03768 03769 /* alloc/init and set defaults, return new Context */ 03770 ecEncCtx* ecc_ctx_new(int flags, RNG* rng) 03771 { 03772 int ret = 0; 03773 ecEncCtx* ctx = (ecEncCtx*)XMALLOC(sizeof(ecEncCtx), 0, DYNAMIC_TYPE_ECC); 03774 03775 if (ctx) 03776 ctx->protocol = (byte)flags; 03777 03778 ret = ecc_ctx_reset(ctx, rng); 03779 if (ret != 0) { 03780 ecc_ctx_free(ctx); 03781 ctx = NULL; 03782 } 03783 03784 return ctx; 03785 } 03786 03787 03788 /* free any resources, clear any keys */ 03789 void ecc_ctx_free(ecEncCtx* ctx) 03790 { 03791 if (ctx) { 03792 XMEMSET(ctx, 0, sizeof(ecEncCtx)); 03793 XFREE(ctx, 0, DYNAMIC_TYPE_ECC); 03794 } 03795 } 03796 03797 03798 static int ecc_get_key_sizes(ecEncCtx* ctx, int* encKeySz, int* ivSz, 03799 int* keysLen, word32* digestSz, word32* blockSz) 03800 { 03801 if (ctx) { 03802 switch (ctx->encAlgo) { 03803 case ecAES_128_CBC: 03804 *encKeySz = KEY_SIZE_128; 03805 *ivSz = IV_SIZE_64; 03806 *blockSz = AES_BLOCK_SIZE; 03807 break; 03808 default: 03809 return BAD_FUNC_ARG; 03810 } 03811 03812 switch (ctx->macAlgo) { 03813 case ecHMAC_SHA256: 03814 *digestSz = SHA256_DIGEST_SIZE; 03815 break; 03816 default: 03817 return BAD_FUNC_ARG; 03818 } 03819 } else 03820 return BAD_FUNC_ARG; 03821 03822 *keysLen = *encKeySz + *ivSz + *digestSz; 03823 03824 return 0; 03825 } 03826 03827 03828 /* ecc encrypt with shared secret run through kdf 03829 ctx holds non default algos and inputs 03830 msgSz should be the right size for encAlgo, i.e., already padded 03831 return 0 on success */ 03832 int ecc_encrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg, 03833 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx) 03834 { 03835 int ret; 03836 word32 blockSz; 03837 word32 digestSz; 03838 ecEncCtx localCtx; 03839 #ifdef CYASSL_SMALL_STACK 03840 byte* sharedSecret; 03841 byte* keys; 03842 #else 03843 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */ 03844 byte keys[ECC_BUFSIZE]; /* max size */ 03845 #endif 03846 word32 sharedSz = ECC_MAXSIZE; 03847 int keysLen; 03848 int encKeySz; 03849 int ivSz; 03850 int offset = 0; /* keys offset if doing msg exchange */ 03851 byte* encKey; 03852 byte* encIv; 03853 byte* macKey; 03854 03855 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL || 03856 outSz == NULL) 03857 return BAD_FUNC_ARG; 03858 03859 if (ctx == NULL) { /* use defaults */ 03860 ecc_ctx_init(&localCtx, 0); 03861 ctx = &localCtx; 03862 } 03863 03864 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz, 03865 &blockSz); 03866 if (ret != 0) 03867 return ret; 03868 03869 if (ctx->protocol == REQ_RESP_SERVER) { 03870 offset = keysLen; 03871 keysLen *= 2; 03872 03873 if (ctx->srvSt != ecSRV_RECV_REQ) 03874 return BAD_ENC_STATE_E; 03875 03876 ctx->srvSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */ 03877 } 03878 else if (ctx->protocol == REQ_RESP_CLIENT) { 03879 if (ctx->cliSt != ecCLI_SALT_SET) 03880 return BAD_ENC_STATE_E; 03881 03882 ctx->cliSt = ecCLI_SENT_REQ; /* only do this once */ 03883 } 03884 03885 if (keysLen > ECC_BUFSIZE) /* keys size */ 03886 return BUFFER_E; 03887 03888 if ( (msgSz%blockSz) != 0) 03889 return BAD_PADDING_E; 03890 03891 if (*outSz < (msgSz + digestSz)) 03892 return BUFFER_E; 03893 03894 #ifdef CYASSL_SMALL_STACK 03895 sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03896 if (sharedSecret == NULL) 03897 return MEMORY_E; 03898 03899 keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03900 if (keys == NULL) { 03901 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03902 return MEMORY_E; 03903 } 03904 #endif 03905 03906 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 03907 03908 if (ret == 0) { 03909 switch (ctx->kdfAlgo) { 03910 case ecHKDF_SHA256 : 03911 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt, 03912 ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz, 03913 keys, keysLen); 03914 break; 03915 03916 default: 03917 ret = BAD_FUNC_ARG; 03918 break; 03919 } 03920 } 03921 03922 if (ret == 0) { 03923 encKey = keys + offset; 03924 encIv = encKey + encKeySz; 03925 macKey = encKey + encKeySz + ivSz; 03926 03927 switch (ctx->encAlgo) { 03928 case ecAES_128_CBC: 03929 { 03930 Aes aes; 03931 ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv, 03932 AES_ENCRYPTION); 03933 if (ret != 0) 03934 break; 03935 ret = AesCbcEncrypt(&aes, out, msg, msgSz); 03936 } 03937 break; 03938 03939 default: 03940 ret = BAD_FUNC_ARG; 03941 break; 03942 } 03943 } 03944 03945 if (ret == 0) { 03946 switch (ctx->macAlgo) { 03947 case ecHMAC_SHA256: 03948 { 03949 Hmac hmac; 03950 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE); 03951 if (ret != 0) 03952 break; 03953 ret = HmacUpdate(&hmac, out, msgSz); 03954 if (ret != 0) 03955 break; 03956 ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz); 03957 if (ret != 0) 03958 break; 03959 ret = HmacFinal(&hmac, out+msgSz); 03960 } 03961 break; 03962 03963 default: 03964 ret = BAD_FUNC_ARG; 03965 break; 03966 } 03967 } 03968 03969 if (ret == 0) 03970 *outSz = msgSz + digestSz; 03971 03972 #ifdef CYASSL_SMALL_STACK 03973 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03974 XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER); 03975 #endif 03976 03977 return ret; 03978 } 03979 03980 03981 /* ecc decrypt with shared secret run through kdf 03982 ctx holds non default algos and inputs 03983 return 0 on success */ 03984 int ecc_decrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg, 03985 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx) 03986 { 03987 int ret; 03988 word32 blockSz; 03989 word32 digestSz; 03990 ecEncCtx localCtx; 03991 #ifdef CYASSL_SMALL_STACK 03992 byte* sharedSecret; 03993 byte* keys; 03994 #else 03995 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */ 03996 byte keys[ECC_BUFSIZE]; /* max size */ 03997 #endif 03998 word32 sharedSz = ECC_MAXSIZE; 03999 int keysLen; 04000 int encKeySz; 04001 int ivSz; 04002 int offset = 0; /* in case using msg exchange */ 04003 byte* encKey; 04004 byte* encIv; 04005 byte* macKey; 04006 04007 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL || 04008 outSz == NULL) 04009 return BAD_FUNC_ARG; 04010 04011 if (ctx == NULL) { /* use defaults */ 04012 ecc_ctx_init(&localCtx, 0); 04013 ctx = &localCtx; 04014 } 04015 04016 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz, 04017 &blockSz); 04018 if (ret != 0) 04019 return ret; 04020 04021 if (ctx->protocol == REQ_RESP_CLIENT) { 04022 offset = keysLen; 04023 keysLen *= 2; 04024 04025 if (ctx->cliSt != ecCLI_SENT_REQ) 04026 return BAD_ENC_STATE_E; 04027 04028 ctx->cliSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */ 04029 } 04030 else if (ctx->protocol == REQ_RESP_SERVER) { 04031 if (ctx->srvSt != ecSRV_SALT_SET) 04032 return BAD_ENC_STATE_E; 04033 04034 ctx->srvSt = ecSRV_RECV_REQ; /* only do this once */ 04035 } 04036 04037 if (keysLen > ECC_BUFSIZE) /* keys size */ 04038 return BUFFER_E; 04039 04040 if ( ((msgSz-digestSz) % blockSz) != 0) 04041 return BAD_PADDING_E; 04042 04043 if (*outSz < (msgSz - digestSz)) 04044 return BUFFER_E; 04045 04046 #ifdef CYASSL_SMALL_STACK 04047 sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 04048 if (sharedSecret == NULL) 04049 return MEMORY_E; 04050 04051 keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 04052 if (keys == NULL) { 04053 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER); 04054 return MEMORY_E; 04055 } 04056 #endif 04057 04058 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 04059 04060 if (ret == 0) { 04061 switch (ctx->kdfAlgo) { 04062 case ecHKDF_SHA256 : 04063 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt, 04064 ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz, 04065 keys, keysLen); 04066 break; 04067 04068 default: 04069 ret = BAD_FUNC_ARG; 04070 break; 04071 } 04072 } 04073 04074 if (ret == 0) { 04075 encKey = keys + offset; 04076 encIv = encKey + encKeySz; 04077 macKey = encKey + encKeySz + ivSz; 04078 04079 switch (ctx->macAlgo) { 04080 case ecHMAC_SHA256: 04081 { 04082 byte verify[SHA256_DIGEST_SIZE]; 04083 Hmac hmac; 04084 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE); 04085 if (ret != 0) 04086 break; 04087 ret = HmacUpdate(&hmac, msg, msgSz-digestSz); 04088 if (ret != 0) 04089 break; 04090 ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz); 04091 if (ret != 0) 04092 break; 04093 ret = HmacFinal(&hmac, verify); 04094 if (ret != 0) 04095 break; 04096 if (memcmp(verify, msg + msgSz - digestSz, digestSz) != 0) 04097 ret = -1; 04098 } 04099 break; 04100 04101 default: 04102 ret = BAD_FUNC_ARG; 04103 break; 04104 } 04105 } 04106 04107 if (ret == 0) { 04108 switch (ctx->encAlgo) { 04109 case ecAES_128_CBC: 04110 { 04111 Aes aes; 04112 ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv, 04113 AES_DECRYPTION); 04114 if (ret != 0) 04115 break; 04116 ret = AesCbcDecrypt(&aes, out, msg, msgSz-digestSz); 04117 } 04118 break; 04119 04120 default: 04121 ret = BAD_FUNC_ARG; 04122 break; 04123 } 04124 } 04125 04126 if (ret == 0) 04127 *outSz = msgSz - digestSz; 04128 04129 #ifdef CYASSL_SMALL_STACK 04130 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER); 04131 XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER); 04132 #endif 04133 04134 return ret; 04135 } 04136 04137 04138 #endif /* HAVE_ECC_ENCRYPT */ 04139 04140 #endif /* HAVE_ECC */ 04141
Generated on Wed Jul 13 2022 02:18:39 by
1.7.2
