wolf SSL
/
CyaSSL-2.9.4
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.
Embed:
(wiki syntax)
Show/hide line numbers
ecc.c
00001 /* ecc.c 00002 * 00003 * Copyright (C) 2006-2013 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 00020 */ 00021 00022 00023 #ifdef HAVE_CONFIG_H 00024 #include <config.h> 00025 #endif 00026 00027 /* in case user set HAVE_ECC there */ 00028 #include <cyassl/ctaocrypt/settings.h> 00029 00030 #ifdef HAVE_ECC 00031 00032 #include <cyassl/ctaocrypt/ecc.h> 00033 #include <cyassl/ctaocrypt/asn.h> 00034 #include <cyassl/ctaocrypt/error-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 /* find key size */ 01303 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++) 01304 ; 01305 keysize = ecc_sets[x].size; 01306 01307 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) { 01308 return BAD_FUNC_ARG; 01309 } 01310 err = ecc_make_key_ex(rng, key, &ecc_sets[x]); 01311 key->idx = x; 01312 01313 return err; 01314 } 01315 01316 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp) 01317 { 01318 int err; 01319 ecc_point* base; 01320 mp_int prime; 01321 mp_int order; 01322 byte buf[ECC_MAXSIZE]; 01323 int keysize; 01324 01325 if (key == NULL || rng == NULL || dp == NULL) 01326 return ECC_BAD_ARG_E; 01327 01328 key->idx = -1; 01329 key->dp = dp; 01330 keysize = dp->size; 01331 01332 /* allocate ram */ 01333 base = NULL; 01334 01335 /* make up random string */ 01336 RNG_GenerateBlock(rng, buf, keysize); 01337 buf[0] |= 0x0c; 01338 01339 /* setup the key variables */ 01340 if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, 01341 &key->k, &prime, &order)) != MP_OKAY) 01342 return MEMORY_E; 01343 01344 base = ecc_new_point(); 01345 if (base == NULL) 01346 err = MEMORY_E; 01347 01348 /* read in the specs for this key */ 01349 if (err == MP_OKAY) 01350 err = mp_read_radix(&prime, (char *)key->dp->prime, 16); 01351 if (err == MP_OKAY) 01352 err = mp_read_radix(&order, (char *)key->dp->order, 16); 01353 if (err == MP_OKAY) 01354 err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16); 01355 if (err == MP_OKAY) 01356 err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16); 01357 01358 if (err == MP_OKAY) 01359 mp_set(&base->z, 1); 01360 if (err == MP_OKAY) 01361 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize); 01362 01363 /* the key should be smaller than the order of base point */ 01364 if (err == MP_OKAY) { 01365 if (mp_cmp(&key->k, &order) != MP_LT) 01366 err = mp_mod(&key->k, &order, &key->k); 01367 } 01368 /* make the public key */ 01369 if (err == MP_OKAY) 01370 err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1); 01371 if (err == MP_OKAY) 01372 key->type = ECC_PRIVATEKEY; 01373 01374 if (err != MP_OKAY) { 01375 /* clean up */ 01376 mp_clear(&key->pubkey.x); 01377 mp_clear(&key->pubkey.y); 01378 mp_clear(&key->pubkey.z); 01379 mp_clear(&key->k); 01380 } 01381 ecc_del_point(base); 01382 mp_clear(&prime); 01383 mp_clear(&order); 01384 #ifdef ECC_CLEAN_STACK 01385 XMEMSET(buff, 0, ECC_MAXSIZE); 01386 #endif 01387 return err; 01388 } 01389 01390 01391 /* Setup dynamic pointers is using normal math for proper freeing */ 01392 void ecc_init(ecc_key* key) 01393 { 01394 (void)key; 01395 #ifndef USE_FAST_MATH 01396 key->pubkey.x.dp = NULL; 01397 key->pubkey.y.dp = NULL; 01398 key->pubkey.z.dp = NULL; 01399 01400 key->k.dp = NULL; 01401 #endif 01402 } 01403 01404 01405 /** 01406 Sign a message digest 01407 in The message digest to sign 01408 inlen The length of the digest 01409 out [out] The destination for the signature 01410 outlen [in/out] The max size and resulting size of the signature 01411 key A private ECC key 01412 return MP_OKAY if successful 01413 */ 01414 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen, 01415 RNG* rng, ecc_key* key) 01416 { 01417 mp_int r; 01418 mp_int s; 01419 mp_int e; 01420 mp_int p; 01421 int err; 01422 01423 if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL) 01424 return ECC_BAD_ARG_E; 01425 01426 /* is this a private key? */ 01427 if (key->type != ECC_PRIVATEKEY) { 01428 return ECC_BAD_ARG_E; 01429 } 01430 01431 /* is the IDX valid ? */ 01432 if (ecc_is_valid_idx(key->idx) != 1) { 01433 return ECC_BAD_ARG_E; 01434 } 01435 01436 /* get the hash and load it as a bignum into 'e' */ 01437 /* init the bignums */ 01438 if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) { 01439 return err; 01440 } 01441 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01442 01443 if (err == MP_OKAY) { 01444 /* we may need to truncate if hash is longer than key size */ 01445 word32 orderBits = mp_count_bits(&p); 01446 01447 /* truncate down to byte size, may be all that's needed */ 01448 if ( (CYASSL_BIT_SIZE * inlen) > orderBits) 01449 inlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE; 01450 err = mp_read_unsigned_bin(&e, (byte*)in, inlen); 01451 01452 /* may still need bit truncation too */ 01453 if (err == MP_OKAY && (CYASSL_BIT_SIZE * inlen) > orderBits) 01454 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7)); 01455 } 01456 01457 /* make up a key and export the public copy */ 01458 if (err == MP_OKAY) { 01459 ecc_key pubkey; 01460 ecc_init(&pubkey); 01461 for (;;) { 01462 err = ecc_make_key_ex(rng, &pubkey, key->dp); 01463 if (err != MP_OKAY) break; 01464 01465 /* find r = x1 mod n */ 01466 err = mp_mod(&pubkey.pubkey.x, &p, &r); 01467 if (err != MP_OKAY) break; 01468 01469 if (mp_iszero(&r) == MP_YES) 01470 ecc_free(&pubkey); 01471 else { 01472 /* find s = (e + xr)/k */ 01473 err = mp_invmod(&pubkey.k, &p, &pubkey.k); 01474 if (err != MP_OKAY) break; 01475 01476 err = mp_mulmod(&key->k, &r, &p, &s); /* s = xr */ 01477 if (err != MP_OKAY) break; 01478 01479 err = mp_add(&e, &s, &s); /* s = e + xr */ 01480 if (err != MP_OKAY) break; 01481 01482 err = mp_mod(&s, &p, &s); /* s = e + xr */ 01483 if (err != MP_OKAY) break; 01484 01485 err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */ 01486 if (err != MP_OKAY) break; 01487 01488 ecc_free(&pubkey); 01489 if (mp_iszero(&s) == MP_NO) 01490 break; 01491 } 01492 } 01493 ecc_free(&pubkey); 01494 } 01495 01496 /* store as SEQUENCE { r, s -- integer } */ 01497 if (err == MP_OKAY) 01498 err = StoreECC_DSA_Sig(out, outlen, &r, &s); 01499 01500 mp_clear(&r); 01501 mp_clear(&s); 01502 mp_clear(&p); 01503 mp_clear(&e); 01504 01505 return err; 01506 } 01507 01508 01509 /** 01510 Free an ECC key from memory 01511 key The key you wish to free 01512 */ 01513 void ecc_free(ecc_key* key) 01514 { 01515 if (key == NULL) 01516 return; 01517 01518 mp_clear(&key->pubkey.x); 01519 mp_clear(&key->pubkey.y); 01520 mp_clear(&key->pubkey.z); 01521 mp_clear(&key->k); 01522 } 01523 01524 01525 #ifdef USE_FAST_MATH 01526 #define GEN_MEM_ERR FP_MEM 01527 #else 01528 #define GEN_MEM_ERR MP_MEM 01529 #endif 01530 01531 #ifdef ECC_SHAMIR 01532 01533 /** Computes kA*A + kB*B = C using Shamir's Trick 01534 A First point to multiply 01535 kA What to multiple A by 01536 B Second point to multiply 01537 kB What to multiple B by 01538 C [out] Destination point (can overlap with A or B) 01539 modulus Modulus for curve 01540 return MP_OKAY on success 01541 */ 01542 #ifdef FP_ECC 01543 static int normal_ecc_mul2add(ecc_point* A, mp_int* kA, 01544 ecc_point* B, mp_int* kB, 01545 ecc_point* C, mp_int* modulus) 01546 #else 01547 static int ecc_mul2add(ecc_point* A, mp_int* kA, 01548 ecc_point* B, mp_int* kB, 01549 ecc_point* C, mp_int* modulus) 01550 #endif 01551 { 01552 ecc_point* precomp[16]; 01553 unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble; 01554 unsigned char* tA; 01555 unsigned char* tB; 01556 int err = MP_OKAY, first; 01557 int muInit = 0; 01558 int tableInit = 0; 01559 mp_digit mp; 01560 mp_int mu; 01561 01562 /* argchks */ 01563 if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL || 01564 modulus == NULL) 01565 return ECC_BAD_ARG_E; 01566 01567 01568 /* allocate memory */ 01569 tA = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01570 if (tA == NULL) { 01571 return GEN_MEM_ERR; 01572 } 01573 tB = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01574 if (tB == NULL) { 01575 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01576 return GEN_MEM_ERR; 01577 } 01578 XMEMSET(tA, 0, ECC_BUFSIZE); 01579 XMEMSET(tB, 0, ECC_BUFSIZE); 01580 01581 /* get sizes */ 01582 lenA = mp_unsigned_bin_size(kA); 01583 lenB = mp_unsigned_bin_size(kB); 01584 len = MAX(lenA, lenB); 01585 01586 /* sanity check */ 01587 if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) { 01588 err = BAD_FUNC_ARG; 01589 } 01590 01591 if (err == MP_OKAY) { 01592 /* extract and justify kA */ 01593 err = mp_to_unsigned_bin(kA, (len - lenA) + tA); 01594 01595 /* extract and justify kB */ 01596 if (err == MP_OKAY) 01597 err = mp_to_unsigned_bin(kB, (len - lenB) + tB); 01598 01599 /* allocate the table */ 01600 if (err == MP_OKAY) { 01601 for (x = 0; x < 16; x++) { 01602 precomp[x] = ecc_new_point(); 01603 if (precomp[x] == NULL) { 01604 for (y = 0; y < x; ++y) { 01605 ecc_del_point(precomp[y]); 01606 } 01607 err = GEN_MEM_ERR; 01608 break; 01609 } 01610 } 01611 } 01612 } 01613 01614 if (err == MP_OKAY) 01615 tableInit = 1; 01616 01617 if (err == MP_OKAY) 01618 /* init montgomery reduction */ 01619 err = mp_montgomery_setup(modulus, &mp); 01620 01621 if (err == MP_OKAY) 01622 err = mp_init(&mu); 01623 if (err == MP_OKAY) 01624 muInit = 1; 01625 01626 if (err == MP_OKAY) 01627 err = mp_montgomery_calc_normalization(&mu, modulus); 01628 01629 if (err == MP_OKAY) 01630 /* copy ones ... */ 01631 err = mp_mulmod(&A->x, &mu, modulus, &precomp[1]->x); 01632 01633 if (err == MP_OKAY) 01634 err = mp_mulmod(&A->y, &mu, modulus, &precomp[1]->y); 01635 if (err == MP_OKAY) 01636 err = mp_mulmod(&A->z, &mu, modulus, &precomp[1]->z); 01637 01638 if (err == MP_OKAY) 01639 err = mp_mulmod(&B->x, &mu, modulus, &precomp[1<<2]->x); 01640 if (err == MP_OKAY) 01641 err = mp_mulmod(&B->y, &mu, modulus, &precomp[1<<2]->y); 01642 if (err == MP_OKAY) 01643 err = mp_mulmod(&B->z, &mu, modulus, &precomp[1<<2]->z); 01644 01645 if (err == MP_OKAY) 01646 /* precomp [i,0](A + B) table */ 01647 err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp); 01648 01649 if (err == MP_OKAY) 01650 err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3], 01651 modulus, &mp); 01652 if (err == MP_OKAY) 01653 /* precomp [0,i](A + B) table */ 01654 err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp); 01655 01656 if (err == MP_OKAY) 01657 err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2], 01658 modulus, &mp); 01659 01660 if (err == MP_OKAY) { 01661 /* precomp [i,j](A + B) table (i != 0, j != 0) */ 01662 for (x = 1; x < 4; x++) { 01663 for (y = 1; y < 4; y++) { 01664 if (err == MP_OKAY) 01665 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)], 01666 precomp[x+(y<<2)], modulus, &mp); 01667 } 01668 } 01669 } 01670 01671 if (err == MP_OKAY) { 01672 nibble = 3; 01673 first = 1; 01674 bitbufA = tA[0]; 01675 bitbufB = tB[0]; 01676 01677 /* for every byte of the multiplicands */ 01678 for (x = -1;; ) { 01679 /* grab a nibble */ 01680 if (++nibble == 4) { 01681 ++x; if (x == len) break; 01682 bitbufA = tA[x]; 01683 bitbufB = tB[x]; 01684 nibble = 0; 01685 } 01686 01687 /* extract two bits from both, shift/update */ 01688 nA = (bitbufA >> 6) & 0x03; 01689 nB = (bitbufB >> 6) & 0x03; 01690 bitbufA = (bitbufA << 2) & 0xFF; 01691 bitbufB = (bitbufB << 2) & 0xFF; 01692 01693 /* if both zero, if first, continue */ 01694 if ((nA == 0) && (nB == 0) && (first == 1)) { 01695 continue; 01696 } 01697 01698 /* double twice, only if this isn't the first */ 01699 if (first == 0) { 01700 /* double twice */ 01701 if (err == MP_OKAY) 01702 err = ecc_projective_dbl_point(C, C, modulus, &mp); 01703 if (err == MP_OKAY) 01704 err = ecc_projective_dbl_point(C, C, modulus, &mp); 01705 else 01706 break; 01707 } 01708 01709 /* if not both zero */ 01710 if ((nA != 0) || (nB != 0)) { 01711 if (first == 1) { 01712 /* if first, copy from table */ 01713 first = 0; 01714 if (err == MP_OKAY) 01715 err = mp_copy(&precomp[nA + (nB<<2)]->x, &C->x); 01716 01717 if (err == MP_OKAY) 01718 err = mp_copy(&precomp[nA + (nB<<2)]->y, &C->y); 01719 01720 if (err == MP_OKAY) 01721 err = mp_copy(&precomp[nA + (nB<<2)]->z, &C->z); 01722 else 01723 break; 01724 } else { 01725 /* if not first, add from table */ 01726 if (err == MP_OKAY) 01727 err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C, 01728 modulus, &mp); 01729 else 01730 break; 01731 } 01732 } 01733 } 01734 } 01735 01736 if (err == MP_OKAY) 01737 /* reduce to affine */ 01738 err = ecc_map(C, modulus, &mp); 01739 01740 /* clean up */ 01741 if (muInit) 01742 mp_clear(&mu); 01743 01744 if (tableInit) { 01745 for (x = 0; x < 16; x++) { 01746 ecc_del_point(precomp[x]); 01747 } 01748 } 01749 #ifdef ECC_CLEAN_STACK 01750 XMEMSET(tA, 0, ECC_BUF_SIZE); 01751 XMEMSET(tB, 0, ECC_BUF_SIZE); 01752 #endif 01753 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01754 XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER); 01755 01756 return err; 01757 } 01758 01759 01760 #endif /* ECC_SHAMIR */ 01761 01762 01763 01764 /* verify 01765 * 01766 * w = s^-1 mod n 01767 * u1 = xw 01768 * u2 = rw 01769 * X = u1*G + u2*Q 01770 * v = X_x1 mod n 01771 * accept if v == r 01772 */ 01773 01774 /** 01775 Verify an ECC signature 01776 sig The signature to verify 01777 siglen The length of the signature (octets) 01778 hash The hash (message digest) that was signed 01779 hashlen The length of the hash (octets) 01780 stat Result of signature, 1==valid, 0==invalid 01781 key The corresponding public ECC key 01782 return MP_OKAY if successful (even if the signature is not valid) 01783 */ 01784 int ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash, 01785 word32 hashlen, int* stat, ecc_key* key) 01786 { 01787 ecc_point *mG, *mQ; 01788 mp_int r; 01789 mp_int s; 01790 mp_int v; 01791 mp_int w; 01792 mp_int u1; 01793 mp_int u2; 01794 mp_int e; 01795 mp_int p; 01796 mp_int m; 01797 int err; 01798 01799 if (sig == NULL || hash == NULL || stat == NULL || key == NULL) 01800 return ECC_BAD_ARG_E; 01801 01802 /* default to invalid signature */ 01803 *stat = 0; 01804 01805 /* is the IDX valid ? */ 01806 if (ecc_is_valid_idx(key->idx) != 1) { 01807 return ECC_BAD_ARG_E; 01808 } 01809 01810 /* allocate ints */ 01811 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) { 01812 return MEMORY_E; 01813 } 01814 01815 if ((err = mp_init(&m)) != MP_OKAY) { 01816 mp_clear(&v); 01817 mp_clear(&w); 01818 mp_clear(&u1); 01819 mp_clear(&u2); 01820 mp_clear(&p); 01821 mp_clear(&e); 01822 return MEMORY_E; 01823 } 01824 01825 /* allocate points */ 01826 mG = ecc_new_point(); 01827 mQ = ecc_new_point(); 01828 if (mQ == NULL || mG == NULL) 01829 err = MEMORY_E; 01830 01831 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s. 01832 * If either of those don't allocate correctly, none of 01833 * the rest of this function will execute, and everything 01834 * gets cleaned up at the end. */ 01835 XMEMSET(&r, 0, sizeof(r)); 01836 XMEMSET(&s, 0, sizeof(s)); 01837 if (err == MP_OKAY) 01838 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s); 01839 01840 /* get the order */ 01841 if (err == MP_OKAY) 01842 err = mp_read_radix(&p, (char *)key->dp->order, 16); 01843 01844 /* get the modulus */ 01845 if (err == MP_OKAY) 01846 err = mp_read_radix(&m, (char *)key->dp->prime, 16); 01847 01848 /* check for zero */ 01849 if (err == MP_OKAY) { 01850 if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT || 01851 mp_cmp(&s, &p) != MP_LT) 01852 err = MP_ZERO_E; 01853 } 01854 /* read hash */ 01855 if (err == MP_OKAY) { 01856 /* we may need to truncate if hash is longer than key size */ 01857 unsigned int orderBits = mp_count_bits(&p); 01858 01859 /* truncate down to byte size, may be all that's needed */ 01860 if ( (CYASSL_BIT_SIZE * hashlen) > orderBits) 01861 hashlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE; 01862 err = mp_read_unsigned_bin(&e, hash, hashlen); 01863 01864 /* may still need bit truncation too */ 01865 if (err == MP_OKAY && (CYASSL_BIT_SIZE * hashlen) > orderBits) 01866 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7)); 01867 } 01868 01869 /* w = s^-1 mod n */ 01870 if (err == MP_OKAY) 01871 err = mp_invmod(&s, &p, &w); 01872 01873 /* u1 = ew */ 01874 if (err == MP_OKAY) 01875 err = mp_mulmod(&e, &w, &p, &u1); 01876 01877 /* u2 = rw */ 01878 if (err == MP_OKAY) 01879 err = mp_mulmod(&r, &w, &p, &u2); 01880 01881 /* find mG and mQ */ 01882 if (err == MP_OKAY) 01883 err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16); 01884 01885 if (err == MP_OKAY) 01886 err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16); 01887 if (err == MP_OKAY) 01888 mp_set(&mG->z, 1); 01889 01890 if (err == MP_OKAY) 01891 err = mp_copy(&key->pubkey.x, &mQ->x); 01892 if (err == MP_OKAY) 01893 err = mp_copy(&key->pubkey.y, &mQ->y); 01894 if (err == MP_OKAY) 01895 err = mp_copy(&key->pubkey.z, &mQ->z); 01896 01897 #ifndef ECC_SHAMIR 01898 { 01899 mp_digit mp; 01900 01901 /* compute u1*mG + u2*mQ = mG */ 01902 if (err == MP_OKAY) 01903 err = ecc_mulmod(&u1, mG, mG, &m, 0); 01904 if (err == MP_OKAY) 01905 err = ecc_mulmod(&u2, mQ, mQ, &m, 0); 01906 01907 /* find the montgomery mp */ 01908 if (err == MP_OKAY) 01909 err = mp_montgomery_setup(&m, &mp); 01910 01911 /* add them */ 01912 if (err == MP_OKAY) 01913 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp); 01914 01915 /* reduce */ 01916 if (err == MP_OKAY) 01917 err = ecc_map(mG, &m, &mp); 01918 } 01919 #else 01920 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */ 01921 if (err == MP_OKAY) 01922 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m); 01923 #endif /* ECC_SHAMIR */ 01924 01925 /* v = X_x1 mod n */ 01926 if (err == MP_OKAY) 01927 err = mp_mod(&mG->x, &p, &v); 01928 01929 /* does v == r */ 01930 if (err == MP_OKAY) { 01931 if (mp_cmp(&v, &r) == MP_EQ) 01932 *stat = 1; 01933 } 01934 01935 ecc_del_point(mG); 01936 ecc_del_point(mQ); 01937 01938 mp_clear(&r); 01939 mp_clear(&s); 01940 mp_clear(&v); 01941 mp_clear(&w); 01942 mp_clear(&u1); 01943 mp_clear(&u2); 01944 mp_clear(&p); 01945 mp_clear(&e); 01946 mp_clear(&m); 01947 01948 return err; 01949 } 01950 01951 01952 /* export public ECC key in ANSI X9.63 format */ 01953 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen) 01954 { 01955 byte buf[ECC_BUFSIZE]; 01956 word32 numlen; 01957 int ret = MP_OKAY; 01958 01959 if (key == NULL || out == NULL || outLen == NULL) 01960 return ECC_BAD_ARG_E; 01961 01962 if (ecc_is_valid_idx(key->idx) == 0) { 01963 return ECC_BAD_ARG_E; 01964 } 01965 numlen = key->dp->size; 01966 01967 if (*outLen < (1 + 2*numlen)) { 01968 *outLen = 1 + 2*numlen; 01969 return BUFFER_E; 01970 } 01971 01972 /* store byte 0x04 */ 01973 out[0] = 0x04; 01974 01975 /* pad and store x */ 01976 XMEMSET(buf, 0, sizeof(buf)); 01977 ret = mp_to_unsigned_bin(&key->pubkey.x, 01978 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x))); 01979 if (ret != MP_OKAY) 01980 return ret; 01981 XMEMCPY(out+1, buf, numlen); 01982 01983 /* pad and store y */ 01984 XMEMSET(buf, 0, sizeof(buf)); 01985 ret = mp_to_unsigned_bin(&key->pubkey.y, 01986 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y))); 01987 if (ret != MP_OKAY) 01988 return ret; 01989 XMEMCPY(out+1+numlen, buf, numlen); 01990 01991 *outLen = 1 + 2*numlen; 01992 01993 return 0; 01994 } 01995 01996 01997 /* import public ECC key in ANSI X9.63 format */ 01998 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key) 01999 { 02000 int x, err; 02001 02002 if (in == NULL || key == NULL) 02003 return ECC_BAD_ARG_E; 02004 02005 /* must be odd */ 02006 if ((inLen & 1) == 0) { 02007 return ECC_BAD_ARG_E; 02008 } 02009 02010 /* init key */ 02011 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, 02012 NULL, NULL) != MP_OKAY) { 02013 return MEMORY_E; 02014 } 02015 err = MP_OKAY; 02016 02017 /* check for 4, 6 or 7 */ 02018 if (in[0] != 4 && in[0] != 6 && in[0] != 7) { 02019 err = ASN_PARSE_E; 02020 } 02021 02022 /* read data */ 02023 if (err == MP_OKAY) 02024 err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1); 02025 02026 if (err == MP_OKAY) 02027 err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1), 02028 (inLen-1)>>1); 02029 02030 if (err == MP_OKAY) 02031 mp_set(&key->pubkey.z, 1); 02032 02033 if (err == MP_OKAY) { 02034 /* determine the idx */ 02035 for (x = 0; ecc_sets[x].size != 0; x++) { 02036 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) { 02037 break; 02038 } 02039 } 02040 if (ecc_sets[x].size == 0) { 02041 err = ASN_PARSE_E; 02042 } else { 02043 /* set the idx */ 02044 key->idx = x; 02045 key->dp = &ecc_sets[x]; 02046 key->type = ECC_PUBLICKEY; 02047 } 02048 } 02049 02050 if (err != MP_OKAY) { 02051 mp_clear(&key->pubkey.x); 02052 mp_clear(&key->pubkey.y); 02053 mp_clear(&key->pubkey.z); 02054 mp_clear(&key->k); 02055 } 02056 02057 return err; 02058 } 02059 02060 02061 /* export ecc private key only raw, outLen is in/out size 02062 return MP_OKAY on success */ 02063 int ecc_export_private_only(ecc_key* key, byte* out, word32* outLen) 02064 { 02065 word32 numlen; 02066 02067 if (key == NULL || out == NULL || outLen == NULL) 02068 return ECC_BAD_ARG_E; 02069 02070 if (ecc_is_valid_idx(key->idx) == 0) { 02071 return ECC_BAD_ARG_E; 02072 } 02073 numlen = key->dp->size; 02074 02075 if (*outLen < numlen) { 02076 *outLen = numlen; 02077 return BUFFER_E; 02078 } 02079 *outLen = numlen; 02080 XMEMSET(out, 0, *outLen); 02081 return mp_to_unsigned_bin(&key->k, out + (numlen - 02082 mp_unsigned_bin_size(&key->k))); 02083 } 02084 02085 02086 /* ecc private key import, public key in ANSI X9.63 format, private raw */ 02087 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub, 02088 word32 pubSz, ecc_key* key) 02089 { 02090 int ret = ecc_import_x963(pub, pubSz, key); 02091 if (ret != 0) 02092 return ret; 02093 02094 key->type = ECC_PRIVATEKEY; 02095 02096 return mp_read_unsigned_bin(&key->k, priv, privSz); 02097 } 02098 02099 02100 /* key size in octets */ 02101 int ecc_size(ecc_key* key) 02102 { 02103 if (key == NULL) return 0; 02104 02105 return key->dp->size; 02106 } 02107 02108 02109 /* worst case estimate, check actual return from ecc_sign_hash for actual value 02110 of signature size in octets */ 02111 int ecc_sig_size(ecc_key* key) 02112 { 02113 int sz = ecc_size(key); 02114 if (sz < 0) 02115 return sz; 02116 02117 return sz * 2 + SIG_HEADER_SZ + 4; /* (4) worst case estimate */ 02118 } 02119 02120 02121 #ifdef FP_ECC 02122 02123 /* fixed point ECC cache */ 02124 /* number of entries in the cache */ 02125 #ifndef FP_ENTRIES 02126 #define FP_ENTRIES 16 02127 #endif 02128 02129 /* number of bits in LUT */ 02130 #ifndef FP_LUT 02131 #define FP_LUT 8U 02132 #endif 02133 02134 #ifdef ECC_SHAMIR 02135 /* Sharmir requires a bigger LUT, TAO */ 02136 #if (FP_LUT > 12) || (FP_LUT < 4) 02137 #error FP_LUT must be between 4 and 12 inclusively 02138 #endif 02139 #else 02140 #if (FP_LUT > 12) || (FP_LUT < 2) 02141 #error FP_LUT must be between 2 and 12 inclusively 02142 #endif 02143 #endif 02144 02145 02146 /** Our FP cache */ 02147 typedef struct { 02148 ecc_point* g; /* cached COPY of base point */ 02149 ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */ 02150 mp_int mu; /* copy of the montgomery constant */ 02151 int lru_count; /* amount of times this entry has been used */ 02152 int lock; /* flag to indicate cache eviction */ 02153 /* permitted (0) or not (1) */ 02154 } fp_cache_t; 02155 02156 /* if HAVE_THREAD_LS this cache is per thread, no locking needed */ 02157 static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES]; 02158 02159 #ifndef HAVE_THREAD_LS 02160 static volatile int initMutex = 0; /* prevent multiple mutex inits */ 02161 static CyaSSL_Mutex ecc_fp_lock; 02162 #endif /* HAVE_THREAD_LS */ 02163 02164 /* simple table to help direct the generation of the LUT */ 02165 static const struct { 02166 int ham, terma, termb; 02167 } lut_orders[] = { 02168 { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 }, 02169 { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 }, 02170 { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 }, 02171 { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 }, 02172 { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 }, 02173 { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 }, 02174 { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 }, 02175 { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 }, 02176 #if FP_LUT > 6 02177 { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 }, 02178 { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 }, 02179 { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 }, 02180 { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 }, 02181 { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 }, 02182 { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 }, 02183 { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 }, 02184 { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 }, 02185 #if FP_LUT > 7 02186 { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 }, 02187 { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 }, 02188 { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 }, 02189 { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 }, 02190 { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 }, 02191 { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 }, 02192 { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 }, 02193 { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 }, 02194 { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 }, 02195 { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 }, 02196 { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 }, 02197 { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 }, 02198 { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 }, 02199 { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 }, 02200 { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 }, 02201 { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 }, 02202 #if FP_LUT > 8 02203 { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 }, 02204 { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 }, 02205 { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 }, 02206 { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 }, 02207 { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 }, 02208 { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 }, 02209 { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 }, 02210 { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 }, 02211 { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 }, 02212 { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 }, 02213 { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 }, 02214 { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 }, 02215 { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 }, 02216 { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 }, 02217 { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 }, 02218 { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 }, 02219 { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 }, 02220 { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 }, 02221 { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 }, 02222 { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 }, 02223 { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 }, 02224 { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 }, 02225 { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 }, 02226 { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 }, 02227 { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 }, 02228 { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 }, 02229 { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 }, 02230 { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 }, 02231 { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 }, 02232 { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 }, 02233 { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 }, 02234 { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 }, 02235 #if FP_LUT > 9 02236 { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 }, 02237 { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 }, 02238 { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 }, 02239 { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 }, 02240 { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 }, 02241 { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 }, 02242 { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 }, 02243 { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 }, 02244 { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 }, 02245 { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 }, 02246 { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 }, 02247 { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 }, 02248 { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 }, 02249 { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 }, 02250 { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 }, 02251 { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 }, 02252 { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 }, 02253 { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 }, 02254 { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 }, 02255 { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 }, 02256 { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 }, 02257 { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 }, 02258 { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 }, 02259 { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 }, 02260 { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 }, 02261 { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 }, 02262 { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 }, 02263 { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 }, 02264 { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 }, 02265 { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 }, 02266 { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 }, 02267 { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 }, 02268 { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 }, 02269 { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 }, 02270 { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 }, 02271 { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 }, 02272 { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 }, 02273 { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 }, 02274 { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 }, 02275 { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 }, 02276 { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 }, 02277 { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 }, 02278 { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 }, 02279 { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 }, 02280 { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 }, 02281 { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 }, 02282 { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 }, 02283 { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 }, 02284 { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 }, 02285 { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 }, 02286 { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 }, 02287 { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 }, 02288 { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 }, 02289 { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 }, 02290 { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 }, 02291 { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 }, 02292 { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 }, 02293 { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 }, 02294 { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 }, 02295 { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 }, 02296 { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 }, 02297 { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 }, 02298 { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 }, 02299 { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 }, 02300 #if FP_LUT > 10 02301 { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 }, 02302 { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 }, 02303 { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 }, 02304 { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 }, 02305 { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 }, 02306 { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 }, 02307 { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 }, 02308 { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 }, 02309 { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 }, 02310 { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 }, 02311 { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 }, 02312 { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 }, 02313 { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 }, 02314 { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 }, 02315 { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 }, 02316 { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 }, 02317 { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 }, 02318 { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 }, 02319 { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 }, 02320 { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 }, 02321 { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 }, 02322 { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 }, 02323 { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 }, 02324 { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 }, 02325 { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 }, 02326 { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 }, 02327 { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 }, 02328 { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 }, 02329 { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 }, 02330 { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 }, 02331 { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 }, 02332 { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 }, 02333 { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 }, 02334 { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 }, 02335 { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 }, 02336 { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 }, 02337 { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 }, 02338 { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 }, 02339 { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 }, 02340 { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 }, 02341 { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 }, 02342 { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 }, 02343 { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 }, 02344 { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 }, 02345 { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 }, 02346 { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 }, 02347 { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 }, 02348 { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 }, 02349 { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 }, 02350 { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 }, 02351 { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 }, 02352 { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 }, 02353 { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 }, 02354 { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 }, 02355 { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 }, 02356 { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 }, 02357 { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 }, 02358 { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 }, 02359 { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 }, 02360 { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 }, 02361 { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 }, 02362 { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 }, 02363 { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 }, 02364 { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 }, 02365 { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 }, 02366 { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 }, 02367 { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 }, 02368 { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 }, 02369 { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 }, 02370 { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 }, 02371 { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 }, 02372 { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 }, 02373 { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 }, 02374 { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 }, 02375 { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 }, 02376 { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 }, 02377 { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 }, 02378 { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 }, 02379 { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 }, 02380 { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 }, 02381 { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 }, 02382 { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 }, 02383 { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 }, 02384 { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 }, 02385 { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 }, 02386 { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 }, 02387 { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 }, 02388 { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 }, 02389 { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 }, 02390 { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 }, 02391 { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 }, 02392 { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 }, 02393 { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 }, 02394 { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 }, 02395 { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 }, 02396 { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 }, 02397 { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 }, 02398 { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 }, 02399 { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 }, 02400 { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 }, 02401 { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 }, 02402 { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 }, 02403 { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 }, 02404 { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 }, 02405 { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 }, 02406 { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 }, 02407 { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 }, 02408 { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 }, 02409 { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 }, 02410 { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 }, 02411 { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883, 1024 }, { 7, 884, 1024 }, { 8, 885, 1024 }, { 8, 886, 1024 }, { 9, 887, 1024 }, 02412 { 7, 888, 1024 }, { 8, 889, 1024 }, { 8, 890, 1024 }, { 9, 891, 1024 }, { 8, 892, 1024 }, { 9, 893, 1024 }, { 9, 894, 1024 }, { 10, 895, 1024 }, 02413 { 4, 896, 1024 }, { 5, 897, 1024 }, { 5, 898, 1024 }, { 6, 899, 1024 }, { 5, 900, 1024 }, { 6, 901, 1024 }, { 6, 902, 1024 }, { 7, 903, 1024 }, 02414 { 5, 904, 1024 }, { 6, 905, 1024 }, { 6, 906, 1024 }, { 7, 907, 1024 }, { 6, 908, 1024 }, { 7, 909, 1024 }, { 7, 910, 1024 }, { 8, 911, 1024 }, 02415 { 5, 912, 1024 }, { 6, 913, 1024 }, { 6, 914, 1024 }, { 7, 915, 1024 }, { 6, 916, 1024 }, { 7, 917, 1024 }, { 7, 918, 1024 }, { 8, 919, 1024 }, 02416 { 6, 920, 1024 }, { 7, 921, 1024 }, { 7, 922, 1024 }, { 8, 923, 1024 }, { 7, 924, 1024 }, { 8, 925, 1024 }, { 8, 926, 1024 }, { 9, 927, 1024 }, 02417 { 5, 928, 1024 }, { 6, 929, 1024 }, { 6, 930, 1024 }, { 7, 931, 1024 }, { 6, 932, 1024 }, { 7, 933, 1024 }, { 7, 934, 1024 }, { 8, 935, 1024 }, 02418 { 6, 936, 1024 }, { 7, 937, 1024 }, { 7, 938, 1024 }, { 8, 939, 1024 }, { 7, 940, 1024 }, { 8, 941, 1024 }, { 8, 942, 1024 }, { 9, 943, 1024 }, 02419 { 6, 944, 1024 }, { 7, 945, 1024 }, { 7, 946, 1024 }, { 8, 947, 1024 }, { 7, 948, 1024 }, { 8, 949, 1024 }, { 8, 950, 1024 }, { 9, 951, 1024 }, 02420 { 7, 952, 1024 }, { 8, 953, 1024 }, { 8, 954, 1024 }, { 9, 955, 1024 }, { 8, 956, 1024 }, { 9, 957, 1024 }, { 9, 958, 1024 }, { 10, 959, 1024 }, 02421 { 5, 960, 1024 }, { 6, 961, 1024 }, { 6, 962, 1024 }, { 7, 963, 1024 }, { 6, 964, 1024 }, { 7, 965, 1024 }, { 7, 966, 1024 }, { 8, 967, 1024 }, 02422 { 6, 968, 1024 }, { 7, 969, 1024 }, { 7, 970, 1024 }, { 8, 971, 1024 }, { 7, 972, 1024 }, { 8, 973, 1024 }, { 8, 974, 1024 }, { 9, 975, 1024 }, 02423 { 6, 976, 1024 }, { 7, 977, 1024 }, { 7, 978, 1024 }, { 8, 979, 1024 }, { 7, 980, 1024 }, { 8, 981, 1024 }, { 8, 982, 1024 }, { 9, 983, 1024 }, 02424 { 7, 984, 1024 }, { 8, 985, 1024 }, { 8, 986, 1024 }, { 9, 987, 1024 }, { 8, 988, 1024 }, { 9, 989, 1024 }, { 9, 990, 1024 }, { 10, 991, 1024 }, 02425 { 6, 992, 1024 }, { 7, 993, 1024 }, { 7, 994, 1024 }, { 8, 995, 1024 }, { 7, 996, 1024 }, { 8, 997, 1024 }, { 8, 998, 1024 }, { 9, 999, 1024 }, 02426 { 7, 1000, 1024 }, { 8, 1001, 1024 }, { 8, 1002, 1024 }, { 9, 1003, 1024 }, { 8, 1004, 1024 }, { 9, 1005, 1024 }, { 9, 1006, 1024 }, { 10, 1007, 1024 }, 02427 { 7, 1008, 1024 }, { 8, 1009, 1024 }, { 8, 1010, 1024 }, { 9, 1011, 1024 }, { 8, 1012, 1024 }, { 9, 1013, 1024 }, { 9, 1014, 1024 }, { 10, 1015, 1024 }, 02428 { 8, 1016, 1024 }, { 9, 1017, 1024 }, { 9, 1018, 1024 }, { 10, 1019, 1024 }, { 9, 1020, 1024 }, { 10, 1021, 1024 }, { 10, 1022, 1024 }, { 11, 1023, 1024 }, 02429 #if FP_LUT > 11 02430 { 1, 0, 0 }, { 2, 1, 2048 }, { 2, 2, 2048 }, { 3, 3, 2048 }, { 2, 4, 2048 }, { 3, 5, 2048 }, { 3, 6, 2048 }, { 4, 7, 2048 }, 02431 { 2, 8, 2048 }, { 3, 9, 2048 }, { 3, 10, 2048 }, { 4, 11, 2048 }, { 3, 12, 2048 }, { 4, 13, 2048 }, { 4, 14, 2048 }, { 5, 15, 2048 }, 02432 { 2, 16, 2048 }, { 3, 17, 2048 }, { 3, 18, 2048 }, { 4, 19, 2048 }, { 3, 20, 2048 }, { 4, 21, 2048 }, { 4, 22, 2048 }, { 5, 23, 2048 }, 02433 { 3, 24, 2048 }, { 4, 25, 2048 }, { 4, 26, 2048 }, { 5, 27, 2048 }, { 4, 28, 2048 }, { 5, 29, 2048 }, { 5, 30, 2048 }, { 6, 31, 2048 }, 02434 { 2, 32, 2048 }, { 3, 33, 2048 }, { 3, 34, 2048 }, { 4, 35, 2048 }, { 3, 36, 2048 }, { 4, 37, 2048 }, { 4, 38, 2048 }, { 5, 39, 2048 }, 02435 { 3, 40, 2048 }, { 4, 41, 2048 }, { 4, 42, 2048 }, { 5, 43, 2048 }, { 4, 44, 2048 }, { 5, 45, 2048 }, { 5, 46, 2048 }, { 6, 47, 2048 }, 02436 { 3, 48, 2048 }, { 4, 49, 2048 }, { 4, 50, 2048 }, { 5, 51, 2048 }, { 4, 52, 2048 }, { 5, 53, 2048 }, { 5, 54, 2048 }, { 6, 55, 2048 }, 02437 { 4, 56, 2048 }, { 5, 57, 2048 }, { 5, 58, 2048 }, { 6, 59, 2048 }, { 5, 60, 2048 }, { 6, 61, 2048 }, { 6, 62, 2048 }, { 7, 63, 2048 }, 02438 { 2, 64, 2048 }, { 3, 65, 2048 }, { 3, 66, 2048 }, { 4, 67, 2048 }, { 3, 68, 2048 }, { 4, 69, 2048 }, { 4, 70, 2048 }, { 5, 71, 2048 }, 02439 { 3, 72, 2048 }, { 4, 73, 2048 }, { 4, 74, 2048 }, { 5, 75, 2048 }, { 4, 76, 2048 }, { 5, 77, 2048 }, { 5, 78, 2048 }, { 6, 79, 2048 }, 02440 { 3, 80, 2048 }, { 4, 81, 2048 }, { 4, 82, 2048 }, { 5, 83, 2048 }, { 4, 84, 2048 }, { 5, 85, 2048 }, { 5, 86, 2048 }, { 6, 87, 2048 }, 02441 { 4, 88, 2048 }, { 5, 89, 2048 }, { 5, 90, 2048 }, { 6, 91, 2048 }, { 5, 92, 2048 }, { 6, 93, 2048 }, { 6, 94, 2048 }, { 7, 95, 2048 }, 02442 { 3, 96, 2048 }, { 4, 97, 2048 }, { 4, 98, 2048 }, { 5, 99, 2048 }, { 4, 100, 2048 }, { 5, 101, 2048 }, { 5, 102, 2048 }, { 6, 103, 2048 }, 02443 { 4, 104, 2048 }, { 5, 105, 2048 }, { 5, 106, 2048 }, { 6, 107, 2048 }, { 5, 108, 2048 }, { 6, 109, 2048 }, { 6, 110, 2048 }, { 7, 111, 2048 }, 02444 { 4, 112, 2048 }, { 5, 113, 2048 }, { 5, 114, 2048 }, { 6, 115, 2048 }, { 5, 116, 2048 }, { 6, 117, 2048 }, { 6, 118, 2048 }, { 7, 119, 2048 }, 02445 { 5, 120, 2048 }, { 6, 121, 2048 }, { 6, 122, 2048 }, { 7, 123, 2048 }, { 6, 124, 2048 }, { 7, 125, 2048 }, { 7, 126, 2048 }, { 8, 127, 2048 }, 02446 { 2, 128, 2048 }, { 3, 129, 2048 }, { 3, 130, 2048 }, { 4, 131, 2048 }, { 3, 132, 2048 }, { 4, 133, 2048 }, { 4, 134, 2048 }, { 5, 135, 2048 }, 02447 { 3, 136, 2048 }, { 4, 137, 2048 }, { 4, 138, 2048 }, { 5, 139, 2048 }, { 4, 140, 2048 }, { 5, 141, 2048 }, { 5, 142, 2048 }, { 6, 143, 2048 }, 02448 { 3, 144, 2048 }, { 4, 145, 2048 }, { 4, 146, 2048 }, { 5, 147, 2048 }, { 4, 148, 2048 }, { 5, 149, 2048 }, { 5, 150, 2048 }, { 6, 151, 2048 }, 02449 { 4, 152, 2048 }, { 5, 153, 2048 }, { 5, 154, 2048 }, { 6, 155, 2048 }, { 5, 156, 2048 }, { 6, 157, 2048 }, { 6, 158, 2048 }, { 7, 159, 2048 }, 02450 { 3, 160, 2048 }, { 4, 161, 2048 }, { 4, 162, 2048 }, { 5, 163, 2048 }, { 4, 164, 2048 }, { 5, 165, 2048 }, { 5, 166, 2048 }, { 6, 167, 2048 }, 02451 { 4, 168, 2048 }, { 5, 169, 2048 }, { 5, 170, 2048 }, { 6, 171, 2048 }, { 5, 172, 2048 }, { 6, 173, 2048 }, { 6, 174, 2048 }, { 7, 175, 2048 }, 02452 { 4, 176, 2048 }, { 5, 177, 2048 }, { 5, 178, 2048 }, { 6, 179, 2048 }, { 5, 180, 2048 }, { 6, 181, 2048 }, { 6, 182, 2048 }, { 7, 183, 2048 }, 02453 { 5, 184, 2048 }, { 6, 185, 2048 }, { 6, 186, 2048 }, { 7, 187, 2048 }, { 6, 188, 2048 }, { 7, 189, 2048 }, { 7, 190, 2048 }, { 8, 191, 2048 }, 02454 { 3, 192, 2048 }, { 4, 193, 2048 }, { 4, 194, 2048 }, { 5, 195, 2048 }, { 4, 196, 2048 }, { 5, 197, 2048 }, { 5, 198, 2048 }, { 6, 199, 2048 }, 02455 { 4, 200, 2048 }, { 5, 201, 2048 }, { 5, 202, 2048 }, { 6, 203, 2048 }, { 5, 204, 2048 }, { 6, 205, 2048 }, { 6, 206, 2048 }, { 7, 207, 2048 }, 02456 { 4, 208, 2048 }, { 5, 209, 2048 }, { 5, 210, 2048 }, { 6, 211, 2048 }, { 5, 212, 2048 }, { 6, 213, 2048 }, { 6, 214, 2048 }, { 7, 215, 2048 }, 02457 { 5, 216, 2048 }, { 6, 217, 2048 }, { 6, 218, 2048 }, { 7, 219, 2048 }, { 6, 220, 2048 }, { 7, 221, 2048 }, { 7, 222, 2048 }, { 8, 223, 2048 }, 02458 { 4, 224, 2048 }, { 5, 225, 2048 }, { 5, 226, 2048 }, { 6, 227, 2048 }, { 5, 228, 2048 }, { 6, 229, 2048 }, { 6, 230, 2048 }, { 7, 231, 2048 }, 02459 { 5, 232, 2048 }, { 6, 233, 2048 }, { 6, 234, 2048 }, { 7, 235, 2048 }, { 6, 236, 2048 }, { 7, 237, 2048 }, { 7, 238, 2048 }, { 8, 239, 2048 }, 02460 { 5, 240, 2048 }, { 6, 241, 2048 }, { 6, 242, 2048 }, { 7, 243, 2048 }, { 6, 244, 2048 }, { 7, 245, 2048 }, { 7, 246, 2048 }, { 8, 247, 2048 }, 02461 { 6, 248, 2048 }, { 7, 249, 2048 }, { 7, 250, 2048 }, { 8, 251, 2048 }, { 7, 252, 2048 }, { 8, 253, 2048 }, { 8, 254, 2048 }, { 9, 255, 2048 }, 02462 { 2, 256, 2048 }, { 3, 257, 2048 }, { 3, 258, 2048 }, { 4, 259, 2048 }, { 3, 260, 2048 }, { 4, 261, 2048 }, { 4, 262, 2048 }, { 5, 263, 2048 }, 02463 { 3, 264, 2048 }, { 4, 265, 2048 }, { 4, 266, 2048 }, { 5, 267, 2048 }, { 4, 268, 2048 }, { 5, 269, 2048 }, { 5, 270, 2048 }, { 6, 271, 2048 }, 02464 { 3, 272, 2048 }, { 4, 273, 2048 }, { 4, 274, 2048 }, { 5, 275, 2048 }, { 4, 276, 2048 }, { 5, 277, 2048 }, { 5, 278, 2048 }, { 6, 279, 2048 }, 02465 { 4, 280, 2048 }, { 5, 281, 2048 }, { 5, 282, 2048 }, { 6, 283, 2048 }, { 5, 284, 2048 }, { 6, 285, 2048 }, { 6, 286, 2048 }, { 7, 287, 2048 }, 02466 { 3, 288, 2048 }, { 4, 289, 2048 }, { 4, 290, 2048 }, { 5, 291, 2048 }, { 4, 292, 2048 }, { 5, 293, 2048 }, { 5, 294, 2048 }, { 6, 295, 2048 }, 02467 { 4, 296, 2048 }, { 5, 297, 2048 }, { 5, 298, 2048 }, { 6, 299, 2048 }, { 5, 300, 2048 }, { 6, 301, 2048 }, { 6, 302, 2048 }, { 7, 303, 2048 }, 02468 { 4, 304, 2048 }, { 5, 305, 2048 }, { 5, 306, 2048 }, { 6, 307, 2048 }, { 5, 308, 2048 }, { 6, 309, 2048 }, { 6, 310, 2048 }, { 7, 311, 2048 }, 02469 { 5, 312, 2048 }, { 6, 313, 2048 }, { 6, 314, 2048 }, { 7, 315, 2048 }, { 6, 316, 2048 }, { 7, 317, 2048 }, { 7, 318, 2048 }, { 8, 319, 2048 }, 02470 { 3, 320, 2048 }, { 4, 321, 2048 }, { 4, 322, 2048 }, { 5, 323, 2048 }, { 4, 324, 2048 }, { 5, 325, 2048 }, { 5, 326, 2048 }, { 6, 327, 2048 }, 02471 { 4, 328, 2048 }, { 5, 329, 2048 }, { 5, 330, 2048 }, { 6, 331, 2048 }, { 5, 332, 2048 }, { 6, 333, 2048 }, { 6, 334, 2048 }, { 7, 335, 2048 }, 02472 { 4, 336, 2048 }, { 5, 337, 2048 }, { 5, 338, 2048 }, { 6, 339, 2048 }, { 5, 340, 2048 }, { 6, 341, 2048 }, { 6, 342, 2048 }, { 7, 343, 2048 }, 02473 { 5, 344, 2048 }, { 6, 345, 2048 }, { 6, 346, 2048 }, { 7, 347, 2048 }, { 6, 348, 2048 }, { 7, 349, 2048 }, { 7, 350, 2048 }, { 8, 351, 2048 }, 02474 { 4, 352, 2048 }, { 5, 353, 2048 }, { 5, 354, 2048 }, { 6, 355, 2048 }, { 5, 356, 2048 }, { 6, 357, 2048 }, { 6, 358, 2048 }, { 7, 359, 2048 }, 02475 { 5, 360, 2048 }, { 6, 361, 2048 }, { 6, 362, 2048 }, { 7, 363, 2048 }, { 6, 364, 2048 }, { 7, 365, 2048 }, { 7, 366, 2048 }, { 8, 367, 2048 }, 02476 { 5, 368, 2048 }, { 6, 369, 2048 }, { 6, 370, 2048 }, { 7, 371, 2048 }, { 6, 372, 2048 }, { 7, 373, 2048 }, { 7, 374, 2048 }, { 8, 375, 2048 }, 02477 { 6, 376, 2048 }, { 7, 377, 2048 }, { 7, 378, 2048 }, { 8, 379, 2048 }, { 7, 380, 2048 }, { 8, 381, 2048 }, { 8, 382, 2048 }, { 9, 383, 2048 }, 02478 { 3, 384, 2048 }, { 4, 385, 2048 }, { 4, 386, 2048 }, { 5, 387, 2048 }, { 4, 388, 2048 }, { 5, 389, 2048 }, { 5, 390, 2048 }, { 6, 391, 2048 }, 02479 { 4, 392, 2048 }, { 5, 393, 2048 }, { 5, 394, 2048 }, { 6, 395, 2048 }, { 5, 396, 2048 }, { 6, 397, 2048 }, { 6, 398, 2048 }, { 7, 399, 2048 }, 02480 { 4, 400, 2048 }, { 5, 401, 2048 }, { 5, 402, 2048 }, { 6, 403, 2048 }, { 5, 404, 2048 }, { 6, 405, 2048 }, { 6, 406, 2048 }, { 7, 407, 2048 }, 02481 { 5, 408, 2048 }, { 6, 409, 2048 }, { 6, 410, 2048 }, { 7, 411, 2048 }, { 6, 412, 2048 }, { 7, 413, 2048 }, { 7, 414, 2048 }, { 8, 415, 2048 }, 02482 { 4, 416, 2048 }, { 5, 417, 2048 }, { 5, 418, 2048 }, { 6, 419, 2048 }, { 5, 420, 2048 }, { 6, 421, 2048 }, { 6, 422, 2048 }, { 7, 423, 2048 }, 02483 { 5, 424, 2048 }, { 6, 425, 2048 }, { 6, 426, 2048 }, { 7, 427, 2048 }, { 6, 428, 2048 }, { 7, 429, 2048 }, { 7, 430, 2048 }, { 8, 431, 2048 }, 02484 { 5, 432, 2048 }, { 6, 433, 2048 }, { 6, 434, 2048 }, { 7, 435, 2048 }, { 6, 436, 2048 }, { 7, 437, 2048 }, { 7, 438, 2048 }, { 8, 439, 2048 }, 02485 { 6, 440, 2048 }, { 7, 441, 2048 }, { 7, 442, 2048 }, { 8, 443, 2048 }, { 7, 444, 2048 }, { 8, 445, 2048 }, { 8, 446, 2048 }, { 9, 447, 2048 }, 02486 { 4, 448, 2048 }, { 5, 449, 2048 }, { 5, 450, 2048 }, { 6, 451, 2048 }, { 5, 452, 2048 }, { 6, 453, 2048 }, { 6, 454, 2048 }, { 7, 455, 2048 }, 02487 { 5, 456, 2048 }, { 6, 457, 2048 }, { 6, 458, 2048 }, { 7, 459, 2048 }, { 6, 460, 2048 }, { 7, 461, 2048 }, { 7, 462, 2048 }, { 8, 463, 2048 }, 02488 { 5, 464, 2048 }, { 6, 465, 2048 }, { 6, 466, 2048 }, { 7, 467, 2048 }, { 6, 468, 2048 }, { 7, 469, 2048 }, { 7, 470, 2048 }, { 8, 471, 2048 }, 02489 { 6, 472, 2048 }, { 7, 473, 2048 }, { 7, 474, 2048 }, { 8, 475, 2048 }, { 7, 476, 2048 }, { 8, 477, 2048 }, { 8, 478, 2048 }, { 9, 479, 2048 }, 02490 { 5, 480, 2048 }, { 6, 481, 2048 }, { 6, 482, 2048 }, { 7, 483, 2048 }, { 6, 484, 2048 }, { 7, 485, 2048 }, { 7, 486, 2048 }, { 8, 487, 2048 }, 02491 { 6, 488, 2048 }, { 7, 489, 2048 }, { 7, 490, 2048 }, { 8, 491, 2048 }, { 7, 492, 2048 }, { 8, 493, 2048 }, { 8, 494, 2048 }, { 9, 495, 2048 }, 02492 { 6, 496, 2048 }, { 7, 497, 2048 }, { 7, 498, 2048 }, { 8, 499, 2048 }, { 7, 500, 2048 }, { 8, 501, 2048 }, { 8, 502, 2048 }, { 9, 503, 2048 }, 02493 { 7, 504, 2048 }, { 8, 505, 2048 }, { 8, 506, 2048 }, { 9, 507, 2048 }, { 8, 508, 2048 }, { 9, 509, 2048 }, { 9, 510, 2048 }, { 10, 511, 2048 }, 02494 { 2, 512, 2048 }, { 3, 513, 2048 }, { 3, 514, 2048 }, { 4, 515, 2048 }, { 3, 516, 2048 }, { 4, 517, 2048 }, { 4, 518, 2048 }, { 5, 519, 2048 }, 02495 { 3, 520, 2048 }, { 4, 521, 2048 }, { 4, 522, 2048 }, { 5, 523, 2048 }, { 4, 524, 2048 }, { 5, 525, 2048 }, { 5, 526, 2048 }, { 6, 527, 2048 }, 02496 { 3, 528, 2048 }, { 4, 529, 2048 }, { 4, 530, 2048 }, { 5, 531, 2048 }, { 4, 532, 2048 }, { 5, 533, 2048 }, { 5, 534, 2048 }, { 6, 535, 2048 }, 02497 { 4, 536, 2048 }, { 5, 537, 2048 }, { 5, 538, 2048 }, { 6, 539, 2048 }, { 5, 540, 2048 }, { 6, 541, 2048 }, { 6, 542, 2048 }, { 7, 543, 2048 }, 02498 { 3, 544, 2048 }, { 4, 545, 2048 }, { 4, 546, 2048 }, { 5, 547, 2048 }, { 4, 548, 2048 }, { 5, 549, 2048 }, { 5, 550, 2048 }, { 6, 551, 2048 }, 02499 { 4, 552, 2048 }, { 5, 553, 2048 }, { 5, 554, 2048 }, { 6, 555, 2048 }, { 5, 556, 2048 }, { 6, 557, 2048 }, { 6, 558, 2048 }, { 7, 559, 2048 }, 02500 { 4, 560, 2048 }, { 5, 561, 2048 }, { 5, 562, 2048 }, { 6, 563, 2048 }, { 5, 564, 2048 }, { 6, 565, 2048 }, { 6, 566, 2048 }, { 7, 567, 2048 }, 02501 { 5, 568, 2048 }, { 6, 569, 2048 }, { 6, 570, 2048 }, { 7, 571, 2048 }, { 6, 572, 2048 }, { 7, 573, 2048 }, { 7, 574, 2048 }, { 8, 575, 2048 }, 02502 { 3, 576, 2048 }, { 4, 577, 2048 }, { 4, 578, 2048 }, { 5, 579, 2048 }, { 4, 580, 2048 }, { 5, 581, 2048 }, { 5, 582, 2048 }, { 6, 583, 2048 }, 02503 { 4, 584, 2048 }, { 5, 585, 2048 }, { 5, 586, 2048 }, { 6, 587, 2048 }, { 5, 588, 2048 }, { 6, 589, 2048 }, { 6, 590, 2048 }, { 7, 591, 2048 }, 02504 { 4, 592, 2048 }, { 5, 593, 2048 }, { 5, 594, 2048 }, { 6, 595, 2048 }, { 5, 596, 2048 }, { 6, 597, 2048 }, { 6, 598, 2048 }, { 7, 599, 2048 }, 02505 { 5, 600, 2048 }, { 6, 601, 2048 }, { 6, 602, 2048 }, { 7, 603, 2048 }, { 6, 604, 2048 }, { 7, 605, 2048 }, { 7, 606, 2048 }, { 8, 607, 2048 }, 02506 { 4, 608, 2048 }, { 5, 609, 2048 }, { 5, 610, 2048 }, { 6, 611, 2048 }, { 5, 612, 2048 }, { 6, 613, 2048 }, { 6, 614, 2048 }, { 7, 615, 2048 }, 02507 { 5, 616, 2048 }, { 6, 617, 2048 }, { 6, 618, 2048 }, { 7, 619, 2048 }, { 6, 620, 2048 }, { 7, 621, 2048 }, { 7, 622, 2048 }, { 8, 623, 2048 }, 02508 { 5, 624, 2048 }, { 6, 625, 2048 }, { 6, 626, 2048 }, { 7, 627, 2048 }, { 6, 628, 2048 }, { 7, 629, 2048 }, { 7, 630, 2048 }, { 8, 631, 2048 }, 02509 { 6, 632, 2048 }, { 7, 633, 2048 }, { 7, 634, 2048 }, { 8, 635, 2048 }, { 7, 636, 2048 }, { 8, 637, 2048 }, { 8, 638, 2048 }, { 9, 639, 2048 }, 02510 { 3, 640, 2048 }, { 4, 641, 2048 }, { 4, 642, 2048 }, { 5, 643, 2048 }, { 4, 644, 2048 }, { 5, 645, 2048 }, { 5, 646, 2048 }, { 6, 647, 2048 }, 02511 { 4, 648, 2048 }, { 5, 649, 2048 }, { 5, 650, 2048 }, { 6, 651, 2048 }, { 5, 652, 2048 }, { 6, 653, 2048 }, { 6, 654, 2048 }, { 7, 655, 2048 }, 02512 { 4, 656, 2048 }, { 5, 657, 2048 }, { 5, 658, 2048 }, { 6, 659, 2048 }, { 5, 660, 2048 }, { 6, 661, 2048 }, { 6, 662, 2048 }, { 7, 663, 2048 }, 02513 { 5, 664, 2048 }, { 6, 665, 2048 }, { 6, 666, 2048 }, { 7, 667, 2048 }, { 6, 668, 2048 }, { 7, 669, 2048 }, { 7, 670, 2048 }, { 8, 671, 2048 }, 02514 { 4, 672, 2048 }, { 5, 673, 2048 }, { 5, 674, 2048 }, { 6, 675, 2048 }, { 5, 676, 2048 }, { 6, 677, 2048 }, { 6, 678, 2048 }, { 7, 679, 2048 }, 02515 { 5, 680, 2048 }, { 6, 681, 2048 }, { 6, 682, 2048 }, { 7, 683, 2048 }, { 6, 684, 2048 }, { 7, 685, 2048 }, { 7, 686, 2048 }, { 8, 687, 2048 }, 02516 { 5, 688, 2048 }, { 6, 689, 2048 }, { 6, 690, 2048 }, { 7, 691, 2048 }, { 6, 692, 2048 }, { 7, 693, 2048 }, { 7, 694, 2048 }, { 8, 695, 2048 }, 02517 { 6, 696, 2048 }, { 7, 697, 2048 }, { 7, 698, 2048 }, { 8, 699, 2048 }, { 7, 700, 2048 }, { 8, 701, 2048 }, { 8, 702, 2048 }, { 9, 703, 2048 }, 02518 { 4, 704, 2048 }, { 5, 705, 2048 }, { 5, 706, 2048 }, { 6, 707, 2048 }, { 5, 708, 2048 }, { 6, 709, 2048 }, { 6, 710, 2048 }, { 7, 711, 2048 }, 02519 { 5, 712, 2048 }, { 6, 713, 2048 }, { 6, 714, 2048 }, { 7, 715, 2048 }, { 6, 716, 2048 }, { 7, 717, 2048 }, { 7, 718, 2048 }, { 8, 719, 2048 }, 02520 { 5, 720, 2048 }, { 6, 721, 2048 }, { 6, 722, 2048 }, { 7, 723, 2048 }, { 6, 724, 2048 }, { 7, 725, 2048 }, { 7, 726, 2048 }, { 8, 727, 2048 }, 02521 { 6, 728, 2048 }, { 7, 729, 2048 }, { 7, 730, 2048 }, { 8, 731, 2048 }, { 7, 732, 2048 }, { 8, 733, 2048 }, { 8, 734, 2048 }, { 9, 735, 2048 }, 02522 { 5, 736, 2048 }, { 6, 737, 2048 }, { 6, 738, 2048 }, { 7, 739, 2048 }, { 6, 740, 2048 }, { 7, 741, 2048 }, { 7, 742, 2048 }, { 8, 743, 2048 }, 02523 { 6, 744, 2048 }, { 7, 745, 2048 }, { 7, 746, 2048 }, { 8, 747, 2048 }, { 7, 748, 2048 }, { 8, 749, 2048 }, { 8, 750, 2048 }, { 9, 751, 2048 }, 02524 { 6, 752, 2048 }, { 7, 753, 2048 }, { 7, 754, 2048 }, { 8, 755, 2048 }, { 7, 756, 2048 }, { 8, 757, 2048 }, { 8, 758, 2048 }, { 9, 759, 2048 }, 02525 { 7, 760, 2048 }, { 8, 761, 2048 }, { 8, 762, 2048 }, { 9, 763, 2048 }, { 8, 764, 2048 }, { 9, 765, 2048 }, { 9, 766, 2048 }, { 10, 767, 2048 }, 02526 { 3, 768, 2048 }, { 4, 769, 2048 }, { 4, 770, 2048 }, { 5, 771, 2048 }, { 4, 772, 2048 }, { 5, 773, 2048 }, { 5, 774, 2048 }, { 6, 775, 2048 }, 02527 { 4, 776, 2048 }, { 5, 777, 2048 }, { 5, 778, 2048 }, { 6, 779, 2048 }, { 5, 780, 2048 }, { 6, 781, 2048 }, { 6, 782, 2048 }, { 7, 783, 2048 }, 02528 { 4, 784, 2048 }, { 5, 785, 2048 }, { 5, 786, 2048 }, { 6, 787, 2048 }, { 5, 788, 2048 }, { 6, 789, 2048 }, { 6, 790, 2048 }, { 7, 791, 2048 }, 02529 { 5, 792, 2048 }, { 6, 793, 2048 }, { 6, 794, 2048 }, { 7, 795, 2048 }, { 6, 796, 2048 }, { 7, 797, 2048 }, { 7, 798, 2048 }, { 8, 799, 2048 }, 02530 { 4, 800, 2048 }, { 5, 801, 2048 }, { 5, 802, 2048 }, { 6, 803, 2048 }, { 5, 804, 2048 }, { 6, 805, 2048 }, { 6, 806, 2048 }, { 7, 807, 2048 }, 02531 { 5, 808, 2048 }, { 6, 809, 2048 }, { 6, 810, 2048 }, { 7, 811, 2048 }, { 6, 812, 2048 }, { 7, 813, 2048 }, { 7, 814, 2048 }, { 8, 815, 2048 }, 02532 { 5, 816, 2048 }, { 6, 817, 2048 }, { 6, 818, 2048 }, { 7, 819, 2048 }, { 6, 820, 2048 }, { 7, 821, 2048 }, { 7, 822, 2048 }, { 8, 823, 2048 }, 02533 { 6, 824, 2048 }, { 7, 825, 2048 }, { 7, 826, 2048 }, { 8, 827, 2048 }, { 7, 828, 2048 }, { 8, 829, 2048 }, { 8, 830, 2048 }, { 9, 831, 2048 }, 02534 { 4, 832, 2048 }, { 5, 833, 2048 }, { 5, 834, 2048 }, { 6, 835, 2048 }, { 5, 836, 2048 }, { 6, 837, 2048 }, { 6, 838, 2048 }, { 7, 839, 2048 }, 02535 { 5, 840, 2048 }, { 6, 841, 2048 }, { 6, 842, 2048 }, { 7, 843, 2048 }, { 6, 844, 2048 }, { 7, 845, 2048 }, { 7, 846, 2048 }, { 8, 847, 2048 }, 02536 { 5, 848, 2048 }, { 6, 849, 2048 }, { 6, 850, 2048 }, { 7, 851, 2048 }, { 6, 852, 2048 }, { 7, 853, 2048 }, { 7, 854, 2048 }, { 8, 855, 2048 }, 02537 { 6, 856, 2048 }, { 7, 857, 2048 }, { 7, 858, 2048 }, { 8, 859, 2048 }, { 7, 860, 2048 }, { 8, 861, 2048 }, { 8, 862, 2048 }, { 9, 863, 2048 }, 02538 { 5, 864, 2048 }, { 6, 865, 2048 }, { 6, 866, 2048 }, { 7, 867, 2048 }, { 6, 868, 2048 }, { 7, 869, 2048 }, { 7, 870, 2048 }, { 8, 871, 2048 }, 02539 { 6, 872, 2048 }, { 7, 873, 2048 }, { 7, 874, 2048 }, { 8, 875, 2048 }, { 7, 876, 2048 }, { 8, 877, 2048 }, { 8, 878, 2048 }, { 9, 879, 2048 }, 02540 { 6, 880, 2048 }, { 7, 881, 2048 }, { 7, 882, 2048 }, { 8, 883, 2048 }, { 7, 884, 2048 }, { 8, 885, 2048 }, { 8, 886, 2048 }, { 9, 887, 2048 }, 02541 { 7, 888, 2048 }, { 8, 889, 2048 }, { 8, 890, 2048 }, { 9, 891, 2048 }, { 8, 892, 2048 }, { 9, 893, 2048 }, { 9, 894, 2048 }, { 10, 895, 2048 }, 02542 { 4, 896, 2048 }, { 5, 897, 2048 }, { 5, 898, 2048 }, { 6, 899, 2048 }, { 5, 900, 2048 }, { 6, 901, 2048 }, { 6, 902, 2048 }, { 7, 903, 2048 }, 02543 { 5, 904, 2048 }, { 6, 905, 2048 }, { 6, 906, 2048 }, { 7, 907, 2048 }, { 6, 908, 2048 }, { 7, 909, 2048 }, { 7, 910, 2048 }, { 8, 911, 2048 }, 02544 { 5, 912, 2048 }, { 6, 913, 2048 }, { 6, 914, 2048 }, { 7, 915, 2048 }, { 6, 916, 2048 }, { 7, 917, 2048 }, { 7, 918, 2048 }, { 8, 919, 2048 }, 02545 { 6, 920, 2048 }, { 7, 921, 2048 }, { 7, 922, 2048 }, { 8, 923, 2048 }, { 7, 924, 2048 }, { 8, 925, 2048 }, { 8, 926, 2048 }, { 9, 927, 2048 }, 02546 { 5, 928, 2048 }, { 6, 929, 2048 }, { 6, 930, 2048 }, { 7, 931, 2048 }, { 6, 932, 2048 }, { 7, 933, 2048 }, { 7, 934, 2048 }, { 8, 935, 2048 }, 02547 { 6, 936, 2048 }, { 7, 937, 2048 }, { 7, 938, 2048 }, { 8, 939, 2048 }, { 7, 940, 2048 }, { 8, 941, 2048 }, { 8, 942, 2048 }, { 9, 943, 2048 }, 02548 { 6, 944, 2048 }, { 7, 945, 2048 }, { 7, 946, 2048 }, { 8, 947, 2048 }, { 7, 948, 2048 }, { 8, 949, 2048 }, { 8, 950, 2048 }, { 9, 951, 2048 }, 02549 { 7, 952, 2048 }, { 8, 953, 2048 }, { 8, 954, 2048 }, { 9, 955, 2048 }, { 8, 956, 2048 }, { 9, 957, 2048 }, { 9, 958, 2048 }, { 10, 959, 2048 }, 02550 { 5, 960, 2048 }, { 6, 961, 2048 }, { 6, 962, 2048 }, { 7, 963, 2048 }, { 6, 964, 2048 }, { 7, 965, 2048 }, { 7, 966, 2048 }, { 8, 967, 2048 }, 02551 { 6, 968, 2048 }, { 7, 969, 2048 }, { 7, 970, 2048 }, { 8, 971, 2048 }, { 7, 972, 2048 }, { 8, 973, 2048 }, { 8, 974, 2048 }, { 9, 975, 2048 }, 02552 { 6, 976, 2048 }, { 7, 977, 2048 }, { 7, 978, 2048 }, { 8, 979, 2048 }, { 7, 980, 2048 }, { 8, 981, 2048 }, { 8, 982, 2048 }, { 9, 983, 2048 }, 02553 { 7, 984, 2048 }, { 8, 985, 2048 }, { 8, 986, 2048 }, { 9, 987, 2048 }, { 8, 988, 2048 }, { 9, 989, 2048 }, { 9, 990, 2048 }, { 10, 991, 2048 }, 02554 { 6, 992, 2048 }, { 7, 993, 2048 }, { 7, 994, 2048 }, { 8, 995, 2048 }, { 7, 996, 2048 }, { 8, 997, 2048 }, { 8, 998, 2048 }, { 9, 999, 2048 }, 02555 { 7, 1000, 2048 }, { 8, 1001, 2048 }, { 8, 1002, 2048 }, { 9, 1003, 2048 }, { 8, 1004, 2048 }, { 9, 1005, 2048 }, { 9, 1006, 2048 }, { 10, 1007, 2048 }, 02556 { 7, 1008, 2048 }, { 8, 1009, 2048 }, { 8, 1010, 2048 }, { 9, 1011, 2048 }, { 8, 1012, 2048 }, { 9, 1013, 2048 }, { 9, 1014, 2048 }, { 10, 1015, 2048 }, 02557 { 8, 1016, 2048 }, { 9, 1017, 2048 }, { 9, 1018, 2048 }, { 10, 1019, 2048 }, { 9, 1020, 2048 }, { 10, 1021, 2048 }, { 10, 1022, 2048 }, { 11, 1023, 2048 }, 02558 { 2, 1024, 2048 }, { 3, 1025, 2048 }, { 3, 1026, 2048 }, { 4, 1027, 2048 }, { 3, 1028, 2048 }, { 4, 1029, 2048 }, { 4, 1030, 2048 }, { 5, 1031, 2048 }, 02559 { 3, 1032, 2048 }, { 4, 1033, 2048 }, { 4, 1034, 2048 }, { 5, 1035, 2048 }, { 4, 1036, 2048 }, { 5, 1037, 2048 }, { 5, 1038, 2048 }, { 6, 1039, 2048 }, 02560 { 3, 1040, 2048 }, { 4, 1041, 2048 }, { 4, 1042, 2048 }, { 5, 1043, 2048 }, { 4, 1044, 2048 }, { 5, 1045, 2048 }, { 5, 1046, 2048 }, { 6, 1047, 2048 }, 02561 { 4, 1048, 2048 }, { 5, 1049, 2048 }, { 5, 1050, 2048 }, { 6, 1051, 2048 }, { 5, 1052, 2048 }, { 6, 1053, 2048 }, { 6, 1054, 2048 }, { 7, 1055, 2048 }, 02562 { 3, 1056, 2048 }, { 4, 1057, 2048 }, { 4, 1058, 2048 }, { 5, 1059, 2048 }, { 4, 1060, 2048 }, { 5, 1061, 2048 }, { 5, 1062, 2048 }, { 6, 1063, 2048 }, 02563 { 4, 1064, 2048 }, { 5, 1065, 2048 }, { 5, 1066, 2048 }, { 6, 1067, 2048 }, { 5, 1068, 2048 }, { 6, 1069, 2048 }, { 6, 1070, 2048 }, { 7, 1071, 2048 }, 02564 { 4, 1072, 2048 }, { 5, 1073, 2048 }, { 5, 1074, 2048 }, { 6, 1075, 2048 }, { 5, 1076, 2048 }, { 6, 1077, 2048 }, { 6, 1078, 2048 }, { 7, 1079, 2048 }, 02565 { 5, 1080, 2048 }, { 6, 1081, 2048 }, { 6, 1082, 2048 }, { 7, 1083, 2048 }, { 6, 1084, 2048 }, { 7, 1085, 2048 }, { 7, 1086, 2048 }, { 8, 1087, 2048 }, 02566 { 3, 1088, 2048 }, { 4, 1089, 2048 }, { 4, 1090, 2048 }, { 5, 1091, 2048 }, { 4, 1092, 2048 }, { 5, 1093, 2048 }, { 5, 1094, 2048 }, { 6, 1095, 2048 }, 02567 { 4, 1096, 2048 }, { 5, 1097, 2048 }, { 5, 1098, 2048 }, { 6, 1099, 2048 }, { 5, 1100, 2048 }, { 6, 1101, 2048 }, { 6, 1102, 2048 }, { 7, 1103, 2048 }, 02568 { 4, 1104, 2048 }, { 5, 1105, 2048 }, { 5, 1106, 2048 }, { 6, 1107, 2048 }, { 5, 1108, 2048 }, { 6, 1109, 2048 }, { 6, 1110, 2048 }, { 7, 1111, 2048 }, 02569 { 5, 1112, 2048 }, { 6, 1113, 2048 }, { 6, 1114, 2048 }, { 7, 1115, 2048 }, { 6, 1116, 2048 }, { 7, 1117, 2048 }, { 7, 1118, 2048 }, { 8, 1119, 2048 }, 02570 { 4, 1120, 2048 }, { 5, 1121, 2048 }, { 5, 1122, 2048 }, { 6, 1123, 2048 }, { 5, 1124, 2048 }, { 6, 1125, 2048 }, { 6, 1126, 2048 }, { 7, 1127, 2048 }, 02571 { 5, 1128, 2048 }, { 6, 1129, 2048 }, { 6, 1130, 2048 }, { 7, 1131, 2048 }, { 6, 1132, 2048 }, { 7, 1133, 2048 }, { 7, 1134, 2048 }, { 8, 1135, 2048 }, 02572 { 5, 1136, 2048 }, { 6, 1137, 2048 }, { 6, 1138, 2048 }, { 7, 1139, 2048 }, { 6, 1140, 2048 }, { 7, 1141, 2048 }, { 7, 1142, 2048 }, { 8, 1143, 2048 }, 02573 { 6, 1144, 2048 }, { 7, 1145, 2048 }, { 7, 1146, 2048 }, { 8, 1147, 2048 }, { 7, 1148, 2048 }, { 8, 1149, 2048 }, { 8, 1150, 2048 }, { 9, 1151, 2048 }, 02574 { 3, 1152, 2048 }, { 4, 1153, 2048 }, { 4, 1154, 2048 }, { 5, 1155, 2048 }, { 4, 1156, 2048 }, { 5, 1157, 2048 }, { 5, 1158, 2048 }, { 6, 1159, 2048 }, 02575 { 4, 1160, 2048 }, { 5, 1161, 2048 }, { 5, 1162, 2048 }, { 6, 1163, 2048 }, { 5, 1164, 2048 }, { 6, 1165, 2048 }, { 6, 1166, 2048 }, { 7, 1167, 2048 }, 02576 { 4, 1168, 2048 }, { 5, 1169, 2048 }, { 5, 1170, 2048 }, { 6, 1171, 2048 }, { 5, 1172, 2048 }, { 6, 1173, 2048 }, { 6, 1174, 2048 }, { 7, 1175, 2048 }, 02577 { 5, 1176, 2048 }, { 6, 1177, 2048 }, { 6, 1178, 2048 }, { 7, 1179, 2048 }, { 6, 1180, 2048 }, { 7, 1181, 2048 }, { 7, 1182, 2048 }, { 8, 1183, 2048 }, 02578 { 4, 1184, 2048 }, { 5, 1185, 2048 }, { 5, 1186, 2048 }, { 6, 1187, 2048 }, { 5, 1188, 2048 }, { 6, 1189, 2048 }, { 6, 1190, 2048 }, { 7, 1191, 2048 }, 02579 { 5, 1192, 2048 }, { 6, 1193, 2048 }, { 6, 1194, 2048 }, { 7, 1195, 2048 }, { 6, 1196, 2048 }, { 7, 1197, 2048 }, { 7, 1198, 2048 }, { 8, 1199, 2048 }, 02580 { 5, 1200, 2048 }, { 6, 1201, 2048 }, { 6, 1202, 2048 }, { 7, 1203, 2048 }, { 6, 1204, 2048 }, { 7, 1205, 2048 }, { 7, 1206, 2048 }, { 8, 1207, 2048 }, 02581 { 6, 1208, 2048 }, { 7, 1209, 2048 }, { 7, 1210, 2048 }, { 8, 1211, 2048 }, { 7, 1212, 2048 }, { 8, 1213, 2048 }, { 8, 1214, 2048 }, { 9, 1215, 2048 }, 02582 { 4, 1216, 2048 }, { 5, 1217, 2048 }, { 5, 1218, 2048 }, { 6, 1219, 2048 }, { 5, 1220, 2048 }, { 6, 1221, 2048 }, { 6, 1222, 2048 }, { 7, 1223, 2048 }, 02583 { 5, 1224, 2048 }, { 6, 1225, 2048 }, { 6, 1226, 2048 }, { 7, 1227, 2048 }, { 6, 1228, 2048 }, { 7, 1229, 2048 }, { 7, 1230, 2048 }, { 8, 1231, 2048 }, 02584 { 5, 1232, 2048 }, { 6, 1233, 2048 }, { 6, 1234, 2048 }, { 7, 1235, 2048 }, { 6, 1236, 2048 }, { 7, 1237, 2048 }, { 7, 1238, 2048 }, { 8, 1239, 2048 }, 02585 { 6, 1240, 2048 }, { 7, 1241, 2048 }, { 7, 1242, 2048 }, { 8, 1243, 2048 }, { 7, 1244, 2048 }, { 8, 1245, 2048 }, { 8, 1246, 2048 }, { 9, 1247, 2048 }, 02586 { 5, 1248, 2048 }, { 6, 1249, 2048 }, { 6, 1250, 2048 }, { 7, 1251, 2048 }, { 6, 1252, 2048 }, { 7, 1253, 2048 }, { 7, 1254, 2048 }, { 8, 1255, 2048 }, 02587 { 6, 1256, 2048 }, { 7, 1257, 2048 }, { 7, 1258, 2048 }, { 8, 1259, 2048 }, { 7, 1260, 2048 }, { 8, 1261, 2048 }, { 8, 1262, 2048 }, { 9, 1263, 2048 }, 02588 { 6, 1264, 2048 }, { 7, 1265, 2048 }, { 7, 1266, 2048 }, { 8, 1267, 2048 }, { 7, 1268, 2048 }, { 8, 1269, 2048 }, { 8, 1270, 2048 }, { 9, 1271, 2048 }, 02589 { 7, 1272, 2048 }, { 8, 1273, 2048 }, { 8, 1274, 2048 }, { 9, 1275, 2048 }, { 8, 1276, 2048 }, { 9, 1277, 2048 }, { 9, 1278, 2048 }, { 10, 1279, 2048 }, 02590 { 3, 1280, 2048 }, { 4, 1281, 2048 }, { 4, 1282, 2048 }, { 5, 1283, 2048 }, { 4, 1284, 2048 }, { 5, 1285, 2048 }, { 5, 1286, 2048 }, { 6, 1287, 2048 }, 02591 { 4, 1288, 2048 }, { 5, 1289, 2048 }, { 5, 1290, 2048 }, { 6, 1291, 2048 }, { 5, 1292, 2048 }, { 6, 1293, 2048 }, { 6, 1294, 2048 }, { 7, 1295, 2048 }, 02592 { 4, 1296, 2048 }, { 5, 1297, 2048 }, { 5, 1298, 2048 }, { 6, 1299, 2048 }, { 5, 1300, 2048 }, { 6, 1301, 2048 }, { 6, 1302, 2048 }, { 7, 1303, 2048 }, 02593 { 5, 1304, 2048 }, { 6, 1305, 2048 }, { 6, 1306, 2048 }, { 7, 1307, 2048 }, { 6, 1308, 2048 }, { 7, 1309, 2048 }, { 7, 1310, 2048 }, { 8, 1311, 2048 }, 02594 { 4, 1312, 2048 }, { 5, 1313, 2048 }, { 5, 1314, 2048 }, { 6, 1315, 2048 }, { 5, 1316, 2048 }, { 6, 1317, 2048 }, { 6, 1318, 2048 }, { 7, 1319, 2048 }, 02595 { 5, 1320, 2048 }, { 6, 1321, 2048 }, { 6, 1322, 2048 }, { 7, 1323, 2048 }, { 6, 1324, 2048 }, { 7, 1325, 2048 }, { 7, 1326, 2048 }, { 8, 1327, 2048 }, 02596 { 5, 1328, 2048 }, { 6, 1329, 2048 }, { 6, 1330, 2048 }, { 7, 1331, 2048 }, { 6, 1332, 2048 }, { 7, 1333, 2048 }, { 7, 1334, 2048 }, { 8, 1335, 2048 }, 02597 { 6, 1336, 2048 }, { 7, 1337, 2048 }, { 7, 1338, 2048 }, { 8, 1339, 2048 }, { 7, 1340, 2048 }, { 8, 1341, 2048 }, { 8, 1342, 2048 }, { 9, 1343, 2048 }, 02598 { 4, 1344, 2048 }, { 5, 1345, 2048 }, { 5, 1346, 2048 }, { 6, 1347, 2048 }, { 5, 1348, 2048 }, { 6, 1349, 2048 }, { 6, 1350, 2048 }, { 7, 1351, 2048 }, 02599 { 5, 1352, 2048 }, { 6, 1353, 2048 }, { 6, 1354, 2048 }, { 7, 1355, 2048 }, { 6, 1356, 2048 }, { 7, 1357, 2048 }, { 7, 1358, 2048 }, { 8, 1359, 2048 }, 02600 { 5, 1360, 2048 }, { 6, 1361, 2048 }, { 6, 1362, 2048 }, { 7, 1363, 2048 }, { 6, 1364, 2048 }, { 7, 1365, 2048 }, { 7, 1366, 2048 }, { 8, 1367, 2048 }, 02601 { 6, 1368, 2048 }, { 7, 1369, 2048 }, { 7, 1370, 2048 }, { 8, 1371, 2048 }, { 7, 1372, 2048 }, { 8, 1373, 2048 }, { 8, 1374, 2048 }, { 9, 1375, 2048 }, 02602 { 5, 1376, 2048 }, { 6, 1377, 2048 }, { 6, 1378, 2048 }, { 7, 1379, 2048 }, { 6, 1380, 2048 }, { 7, 1381, 2048 }, { 7, 1382, 2048 }, { 8, 1383, 2048 }, 02603 { 6, 1384, 2048 }, { 7, 1385, 2048 }, { 7, 1386, 2048 }, { 8, 1387, 2048 }, { 7, 1388, 2048 }, { 8, 1389, 2048 }, { 8, 1390, 2048 }, { 9, 1391, 2048 }, 02604 { 6, 1392, 2048 }, { 7, 1393, 2048 }, { 7, 1394, 2048 }, { 8, 1395, 2048 }, { 7, 1396, 2048 }, { 8, 1397, 2048 }, { 8, 1398, 2048 }, { 9, 1399, 2048 }, 02605 { 7, 1400, 2048 }, { 8, 1401, 2048 }, { 8, 1402, 2048 }, { 9, 1403, 2048 }, { 8, 1404, 2048 }, { 9, 1405, 2048 }, { 9, 1406, 2048 }, { 10, 1407, 2048 }, 02606 { 4, 1408, 2048 }, { 5, 1409, 2048 }, { 5, 1410, 2048 }, { 6, 1411, 2048 }, { 5, 1412, 2048 }, { 6, 1413, 2048 }, { 6, 1414, 2048 }, { 7, 1415, 2048 }, 02607 { 5, 1416, 2048 }, { 6, 1417, 2048 }, { 6, 1418, 2048 }, { 7, 1419, 2048 }, { 6, 1420, 2048 }, { 7, 1421, 2048 }, { 7, 1422, 2048 }, { 8, 1423, 2048 }, 02608 { 5, 1424, 2048 }, { 6, 1425, 2048 }, { 6, 1426, 2048 }, { 7, 1427, 2048 }, { 6, 1428, 2048 }, { 7, 1429, 2048 }, { 7, 1430, 2048 }, { 8, 1431, 2048 }, 02609 { 6, 1432, 2048 }, { 7, 1433, 2048 }, { 7, 1434, 2048 }, { 8, 1435, 2048 }, { 7, 1436, 2048 }, { 8, 1437, 2048 }, { 8, 1438, 2048 }, { 9, 1439, 2048 }, 02610 { 5, 1440, 2048 }, { 6, 1441, 2048 }, { 6, 1442, 2048 }, { 7, 1443, 2048 }, { 6, 1444, 2048 }, { 7, 1445, 2048 }, { 7, 1446, 2048 }, { 8, 1447, 2048 }, 02611 { 6, 1448, 2048 }, { 7, 1449, 2048 }, { 7, 1450, 2048 }, { 8, 1451, 2048 }, { 7, 1452, 2048 }, { 8, 1453, 2048 }, { 8, 1454, 2048 }, { 9, 1455, 2048 }, 02612 { 6, 1456, 2048 }, { 7, 1457, 2048 }, { 7, 1458, 2048 }, { 8, 1459, 2048 }, { 7, 1460, 2048 }, { 8, 1461, 2048 }, { 8, 1462, 2048 }, { 9, 1463, 2048 }, 02613 { 7, 1464, 2048 }, { 8, 1465, 2048 }, { 8, 1466, 2048 }, { 9, 1467, 2048 }, { 8, 1468, 2048 }, { 9, 1469, 2048 }, { 9, 1470, 2048 }, { 10, 1471, 2048 }, 02614 { 5, 1472, 2048 }, { 6, 1473, 2048 }, { 6, 1474, 2048 }, { 7, 1475, 2048 }, { 6, 1476, 2048 }, { 7, 1477, 2048 }, { 7, 1478, 2048 }, { 8, 1479, 2048 }, 02615 { 6, 1480, 2048 }, { 7, 1481, 2048 }, { 7, 1482, 2048 }, { 8, 1483, 2048 }, { 7, 1484, 2048 }, { 8, 1485, 2048 }, { 8, 1486, 2048 }, { 9, 1487, 2048 }, 02616 { 6, 1488, 2048 }, { 7, 1489, 2048 }, { 7, 1490, 2048 }, { 8, 1491, 2048 }, { 7, 1492, 2048 }, { 8, 1493, 2048 }, { 8, 1494, 2048 }, { 9, 1495, 2048 }, 02617 { 7, 1496, 2048 }, { 8, 1497, 2048 }, { 8, 1498, 2048 }, { 9, 1499, 2048 }, { 8, 1500, 2048 }, { 9, 1501, 2048 }, { 9, 1502, 2048 }, { 10, 1503, 2048 }, 02618 { 6, 1504, 2048 }, { 7, 1505, 2048 }, { 7, 1506, 2048 }, { 8, 1507, 2048 }, { 7, 1508, 2048 }, { 8, 1509, 2048 }, { 8, 1510, 2048 }, { 9, 1511, 2048 }, 02619 { 7, 1512, 2048 }, { 8, 1513, 2048 }, { 8, 1514, 2048 }, { 9, 1515, 2048 }, { 8, 1516, 2048 }, { 9, 1517, 2048 }, { 9, 1518, 2048 }, { 10, 1519, 2048 }, 02620 { 7, 1520, 2048 }, { 8, 1521, 2048 }, { 8, 1522, 2048 }, { 9, 1523, 2048 }, { 8, 1524, 2048 }, { 9, 1525, 2048 }, { 9, 1526, 2048 }, { 10, 1527, 2048 }, 02621 { 8, 1528, 2048 }, { 9, 1529, 2048 }, { 9, 1530, 2048 }, { 10, 1531, 2048 }, { 9, 1532, 2048 }, { 10, 1533, 2048 }, { 10, 1534, 2048 }, { 11, 1535, 2048 }, 02622 { 3, 1536, 2048 }, { 4, 1537, 2048 }, { 4, 1538, 2048 }, { 5, 1539, 2048 }, { 4, 1540, 2048 }, { 5, 1541, 2048 }, { 5, 1542, 2048 }, { 6, 1543, 2048 }, 02623 { 4, 1544, 2048 }, { 5, 1545, 2048 }, { 5, 1546, 2048 }, { 6, 1547, 2048 }, { 5, 1548, 2048 }, { 6, 1549, 2048 }, { 6, 1550, 2048 }, { 7, 1551, 2048 }, 02624 { 4, 1552, 2048 }, { 5, 1553, 2048 }, { 5, 1554, 2048 }, { 6, 1555, 2048 }, { 5, 1556, 2048 }, { 6, 1557, 2048 }, { 6, 1558, 2048 }, { 7, 1559, 2048 }, 02625 { 5, 1560, 2048 }, { 6, 1561, 2048 }, { 6, 1562, 2048 }, { 7, 1563, 2048 }, { 6, 1564, 2048 }, { 7, 1565, 2048 }, { 7, 1566, 2048 }, { 8, 1567, 2048 }, 02626 { 4, 1568, 2048 }, { 5, 1569, 2048 }, { 5, 1570, 2048 }, { 6, 1571, 2048 }, { 5, 1572, 2048 }, { 6, 1573, 2048 }, { 6, 1574, 2048 }, { 7, 1575, 2048 }, 02627 { 5, 1576, 2048 }, { 6, 1577, 2048 }, { 6, 1578, 2048 }, { 7, 1579, 2048 }, { 6, 1580, 2048 }, { 7, 1581, 2048 }, { 7, 1582, 2048 }, { 8, 1583, 2048 }, 02628 { 5, 1584, 2048 }, { 6, 1585, 2048 }, { 6, 1586, 2048 }, { 7, 1587, 2048 }, { 6, 1588, 2048 }, { 7, 1589, 2048 }, { 7, 1590, 2048 }, { 8, 1591, 2048 }, 02629 { 6, 1592, 2048 }, { 7, 1593, 2048 }, { 7, 1594, 2048 }, { 8, 1595, 2048 }, { 7, 1596, 2048 }, { 8, 1597, 2048 }, { 8, 1598, 2048 }, { 9, 1599, 2048 }, 02630 { 4, 1600, 2048 }, { 5, 1601, 2048 }, { 5, 1602, 2048 }, { 6, 1603, 2048 }, { 5, 1604, 2048 }, { 6, 1605, 2048 }, { 6, 1606, 2048 }, { 7, 1607, 2048 }, 02631 { 5, 1608, 2048 }, { 6, 1609, 2048 }, { 6, 1610, 2048 }, { 7, 1611, 2048 }, { 6, 1612, 2048 }, { 7, 1613, 2048 }, { 7, 1614, 2048 }, { 8, 1615, 2048 }, 02632 { 5, 1616, 2048 }, { 6, 1617, 2048 }, { 6, 1618, 2048 }, { 7, 1619, 2048 }, { 6, 1620, 2048 }, { 7, 1621, 2048 }, { 7, 1622, 2048 }, { 8, 1623, 2048 }, 02633 { 6, 1624, 2048 }, { 7, 1625, 2048 }, { 7, 1626, 2048 }, { 8, 1627, 2048 }, { 7, 1628, 2048 }, { 8, 1629, 2048 }, { 8, 1630, 2048 }, { 9, 1631, 2048 }, 02634 { 5, 1632, 2048 }, { 6, 1633, 2048 }, { 6, 1634, 2048 }, { 7, 1635, 2048 }, { 6, 1636, 2048 }, { 7, 1637, 2048 }, { 7, 1638, 2048 }, { 8, 1639, 2048 }, 02635 { 6, 1640, 2048 }, { 7, 1641, 2048 }, { 7, 1642, 2048 }, { 8, 1643, 2048 }, { 7, 1644, 2048 }, { 8, 1645, 2048 }, { 8, 1646, 2048 }, { 9, 1647, 2048 }, 02636 { 6, 1648, 2048 }, { 7, 1649, 2048 }, { 7, 1650, 2048 }, { 8, 1651, 2048 }, { 7, 1652, 2048 }, { 8, 1653, 2048 }, { 8, 1654, 2048 }, { 9, 1655, 2048 }, 02637 { 7, 1656, 2048 }, { 8, 1657, 2048 }, { 8, 1658, 2048 }, { 9, 1659, 2048 }, { 8, 1660, 2048 }, { 9, 1661, 2048 }, { 9, 1662, 2048 }, { 10, 1663, 2048 }, 02638 { 4, 1664, 2048 }, { 5, 1665, 2048 }, { 5, 1666, 2048 }, { 6, 1667, 2048 }, { 5, 1668, 2048 }, { 6, 1669, 2048 }, { 6, 1670, 2048 }, { 7, 1671, 2048 }, 02639 { 5, 1672, 2048 }, { 6, 1673, 2048 }, { 6, 1674, 2048 }, { 7, 1675, 2048 }, { 6, 1676, 2048 }, { 7, 1677, 2048 }, { 7, 1678, 2048 }, { 8, 1679, 2048 }, 02640 { 5, 1680, 2048 }, { 6, 1681, 2048 }, { 6, 1682, 2048 }, { 7, 1683, 2048 }, { 6, 1684, 2048 }, { 7, 1685, 2048 }, { 7, 1686, 2048 }, { 8, 1687, 2048 }, 02641 { 6, 1688, 2048 }, { 7, 1689, 2048 }, { 7, 1690, 2048 }, { 8, 1691, 2048 }, { 7, 1692, 2048 }, { 8, 1693, 2048 }, { 8, 1694, 2048 }, { 9, 1695, 2048 }, 02642 { 5, 1696, 2048 }, { 6, 1697, 2048 }, { 6, 1698, 2048 }, { 7, 1699, 2048 }, { 6, 1700, 2048 }, { 7, 1701, 2048 }, { 7, 1702, 2048 }, { 8, 1703, 2048 }, 02643 { 6, 1704, 2048 }, { 7, 1705, 2048 }, { 7, 1706, 2048 }, { 8, 1707, 2048 }, { 7, 1708, 2048 }, { 8, 1709, 2048 }, { 8, 1710, 2048 }, { 9, 1711, 2048 }, 02644 { 6, 1712, 2048 }, { 7, 1713, 2048 }, { 7, 1714, 2048 }, { 8, 1715, 2048 }, { 7, 1716, 2048 }, { 8, 1717, 2048 }, { 8, 1718, 2048 }, { 9, 1719, 2048 }, 02645 { 7, 1720, 2048 }, { 8, 1721, 2048 }, { 8, 1722, 2048 }, { 9, 1723, 2048 }, { 8, 1724, 2048 }, { 9, 1725, 2048 }, { 9, 1726, 2048 }, { 10, 1727, 2048 }, 02646 { 5, 1728, 2048 }, { 6, 1729, 2048 }, { 6, 1730, 2048 }, { 7, 1731, 2048 }, { 6, 1732, 2048 }, { 7, 1733, 2048 }, { 7, 1734, 2048 }, { 8, 1735, 2048 }, 02647 { 6, 1736, 2048 }, { 7, 1737, 2048 }, { 7, 1738, 2048 }, { 8, 1739, 2048 }, { 7, 1740, 2048 }, { 8, 1741, 2048 }, { 8, 1742, 2048 }, { 9, 1743, 2048 }, 02648 { 6, 1744, 2048 }, { 7, 1745, 2048 }, { 7, 1746, 2048 }, { 8, 1747, 2048 }, { 7, 1748, 2048 }, { 8, 1749, 2048 }, { 8, 1750, 2048 }, { 9, 1751, 2048 }, 02649 { 7, 1752, 2048 }, { 8, 1753, 2048 }, { 8, 1754, 2048 }, { 9, 1755, 2048 }, { 8, 1756, 2048 }, { 9, 1757, 2048 }, { 9, 1758, 2048 }, { 10, 1759, 2048 }, 02650 { 6, 1760, 2048 }, { 7, 1761, 2048 }, { 7, 1762, 2048 }, { 8, 1763, 2048 }, { 7, 1764, 2048 }, { 8, 1765, 2048 }, { 8, 1766, 2048 }, { 9, 1767, 2048 }, 02651 { 7, 1768, 2048 }, { 8, 1769, 2048 }, { 8, 1770, 2048 }, { 9, 1771, 2048 }, { 8, 1772, 2048 }, { 9, 1773, 2048 }, { 9, 1774, 2048 }, { 10, 1775, 2048 }, 02652 { 7, 1776, 2048 }, { 8, 1777, 2048 }, { 8, 1778, 2048 }, { 9, 1779, 2048 }, { 8, 1780, 2048 }, { 9, 1781, 2048 }, { 9, 1782, 2048 }, { 10, 1783, 2048 }, 02653 { 8, 1784, 2048 }, { 9, 1785, 2048 }, { 9, 1786, 2048 }, { 10, 1787, 2048 }, { 9, 1788, 2048 }, { 10, 1789, 2048 }, { 10, 1790, 2048 }, { 11, 1791, 2048 }, 02654 { 4, 1792, 2048 }, { 5, 1793, 2048 }, { 5, 1794, 2048 }, { 6, 1795, 2048 }, { 5, 1796, 2048 }, { 6, 1797, 2048 }, { 6, 1798, 2048 }, { 7, 1799, 2048 }, 02655 { 5, 1800, 2048 }, { 6, 1801, 2048 }, { 6, 1802, 2048 }, { 7, 1803, 2048 }, { 6, 1804, 2048 }, { 7, 1805, 2048 }, { 7, 1806, 2048 }, { 8, 1807, 2048 }, 02656 { 5, 1808, 2048 }, { 6, 1809, 2048 }, { 6, 1810, 2048 }, { 7, 1811, 2048 }, { 6, 1812, 2048 }, { 7, 1813, 2048 }, { 7, 1814, 2048 }, { 8, 1815, 2048 }, 02657 { 6, 1816, 2048 }, { 7, 1817, 2048 }, { 7, 1818, 2048 }, { 8, 1819, 2048 }, { 7, 1820, 2048 }, { 8, 1821, 2048 }, { 8, 1822, 2048 }, { 9, 1823, 2048 }, 02658 { 5, 1824, 2048 }, { 6, 1825, 2048 }, { 6, 1826, 2048 }, { 7, 1827, 2048 }, { 6, 1828, 2048 }, { 7, 1829, 2048 }, { 7, 1830, 2048 }, { 8, 1831, 2048 }, 02659 { 6, 1832, 2048 }, { 7, 1833, 2048 }, { 7, 1834, 2048 }, { 8, 1835, 2048 }, { 7, 1836, 2048 }, { 8, 1837, 2048 }, { 8, 1838, 2048 }, { 9, 1839, 2048 }, 02660 { 6, 1840, 2048 }, { 7, 1841, 2048 }, { 7, 1842, 2048 }, { 8, 1843, 2048 }, { 7, 1844, 2048 }, { 8, 1845, 2048 }, { 8, 1846, 2048 }, { 9, 1847, 2048 }, 02661 { 7, 1848, 2048 }, { 8, 1849, 2048 }, { 8, 1850, 2048 }, { 9, 1851, 2048 }, { 8, 1852, 2048 }, { 9, 1853, 2048 }, { 9, 1854, 2048 }, { 10, 1855, 2048 }, 02662 { 5, 1856, 2048 }, { 6, 1857, 2048 }, { 6, 1858, 2048 }, { 7, 1859, 2048 }, { 6, 1860, 2048 }, { 7, 1861, 2048 }, { 7, 1862, 2048 }, { 8, 1863, 2048 }, 02663 { 6, 1864, 2048 }, { 7, 1865, 2048 }, { 7, 1866, 2048 }, { 8, 1867, 2048 }, { 7, 1868, 2048 }, { 8, 1869, 2048 }, { 8, 1870, 2048 }, { 9, 1871, 2048 }, 02664 { 6, 1872, 2048 }, { 7, 1873, 2048 }, { 7, 1874, 2048 }, { 8, 1875, 2048 }, { 7, 1876, 2048 }, { 8, 1877, 2048 }, { 8, 1878, 2048 }, { 9, 1879, 2048 }, 02665 { 7, 1880, 2048 }, { 8, 1881, 2048 }, { 8, 1882, 2048 }, { 9, 1883, 2048 }, { 8, 1884, 2048 }, { 9, 1885, 2048 }, { 9, 1886, 2048 }, { 10, 1887, 2048 }, 02666 { 6, 1888, 2048 }, { 7, 1889, 2048 }, { 7, 1890, 2048 }, { 8, 1891, 2048 }, { 7, 1892, 2048 }, { 8, 1893, 2048 }, { 8, 1894, 2048 }, { 9, 1895, 2048 }, 02667 { 7, 1896, 2048 }, { 8, 1897, 2048 }, { 8, 1898, 2048 }, { 9, 1899, 2048 }, { 8, 1900, 2048 }, { 9, 1901, 2048 }, { 9, 1902, 2048 }, { 10, 1903, 2048 }, 02668 { 7, 1904, 2048 }, { 8, 1905, 2048 }, { 8, 1906, 2048 }, { 9, 1907, 2048 }, { 8, 1908, 2048 }, { 9, 1909, 2048 }, { 9, 1910, 2048 }, { 10, 1911, 2048 }, 02669 { 8, 1912, 2048 }, { 9, 1913, 2048 }, { 9, 1914, 2048 }, { 10, 1915, 2048 }, { 9, 1916, 2048 }, { 10, 1917, 2048 }, { 10, 1918, 2048 }, { 11, 1919, 2048 }, 02670 { 5, 1920, 2048 }, { 6, 1921, 2048 }, { 6, 1922, 2048 }, { 7, 1923, 2048 }, { 6, 1924, 2048 }, { 7, 1925, 2048 }, { 7, 1926, 2048 }, { 8, 1927, 2048 }, 02671 { 6, 1928, 2048 }, { 7, 1929, 2048 }, { 7, 1930, 2048 }, { 8, 1931, 2048 }, { 7, 1932, 2048 }, { 8, 1933, 2048 }, { 8, 1934, 2048 }, { 9, 1935, 2048 }, 02672 { 6, 1936, 2048 }, { 7, 1937, 2048 }, { 7, 1938, 2048 }, { 8, 1939, 2048 }, { 7, 1940, 2048 }, { 8, 1941, 2048 }, { 8, 1942, 2048 }, { 9, 1943, 2048 }, 02673 { 7, 1944, 2048 }, { 8, 1945, 2048 }, { 8, 1946, 2048 }, { 9, 1947, 2048 }, { 8, 1948, 2048 }, { 9, 1949, 2048 }, { 9, 1950, 2048 }, { 10, 1951, 2048 }, 02674 { 6, 1952, 2048 }, { 7, 1953, 2048 }, { 7, 1954, 2048 }, { 8, 1955, 2048 }, { 7, 1956, 2048 }, { 8, 1957, 2048 }, { 8, 1958, 2048 }, { 9, 1959, 2048 }, 02675 { 7, 1960, 2048 }, { 8, 1961, 2048 }, { 8, 1962, 2048 }, { 9, 1963, 2048 }, { 8, 1964, 2048 }, { 9, 1965, 2048 }, { 9, 1966, 2048 }, { 10, 1967, 2048 }, 02676 { 7, 1968, 2048 }, { 8, 1969, 2048 }, { 8, 1970, 2048 }, { 9, 1971, 2048 }, { 8, 1972, 2048 }, { 9, 1973, 2048 }, { 9, 1974, 2048 }, { 10, 1975, 2048 }, 02677 { 8, 1976, 2048 }, { 9, 1977, 2048 }, { 9, 1978, 2048 }, { 10, 1979, 2048 }, { 9, 1980, 2048 }, { 10, 1981, 2048 }, { 10, 1982, 2048 }, { 11, 1983, 2048 }, 02678 { 6, 1984, 2048 }, { 7, 1985, 2048 }, { 7, 1986, 2048 }, { 8, 1987, 2048 }, { 7, 1988, 2048 }, { 8, 1989, 2048 }, { 8, 1990, 2048 }, { 9, 1991, 2048 }, 02679 { 7, 1992, 2048 }, { 8, 1993, 2048 }, { 8, 1994, 2048 }, { 9, 1995, 2048 }, { 8, 1996, 2048 }, { 9, 1997, 2048 }, { 9, 1998, 2048 }, { 10, 1999, 2048 }, 02680 { 7, 2000, 2048 }, { 8, 2001, 2048 }, { 8, 2002, 2048 }, { 9, 2003, 2048 }, { 8, 2004, 2048 }, { 9, 2005, 2048 }, { 9, 2006, 2048 }, { 10, 2007, 2048 }, 02681 { 8, 2008, 2048 }, { 9, 2009, 2048 }, { 9, 2010, 2048 }, { 10, 2011, 2048 }, { 9, 2012, 2048 }, { 10, 2013, 2048 }, { 10, 2014, 2048 }, { 11, 2015, 2048 }, 02682 { 7, 2016, 2048 }, { 8, 2017, 2048 }, { 8, 2018, 2048 }, { 9, 2019, 2048 }, { 8, 2020, 2048 }, { 9, 2021, 2048 }, { 9, 2022, 2048 }, { 10, 2023, 2048 }, 02683 { 8, 2024, 2048 }, { 9, 2025, 2048 }, { 9, 2026, 2048 }, { 10, 2027, 2048 }, { 9, 2028, 2048 }, { 10, 2029, 2048 }, { 10, 2030, 2048 }, { 11, 2031, 2048 }, 02684 { 8, 2032, 2048 }, { 9, 2033, 2048 }, { 9, 2034, 2048 }, { 10, 2035, 2048 }, { 9, 2036, 2048 }, { 10, 2037, 2048 }, { 10, 2038, 2048 }, { 11, 2039, 2048 }, 02685 { 9, 2040, 2048 }, { 10, 2041, 2048 }, { 10, 2042, 2048 }, { 11, 2043, 2048 }, { 10, 2044, 2048 }, { 11, 2045, 2048 }, { 11, 2046, 2048 }, { 12, 2047, 2048 }, 02686 #endif 02687 #endif 02688 #endif 02689 #endif 02690 #endif 02691 #endif 02692 }; 02693 02694 /* find a hole and free as required, return -1 if no hole found */ 02695 static int find_hole(void) 02696 { 02697 unsigned x; 02698 int y, z; 02699 for (z = -1, y = INT_MAX, x = 0; x < FP_ENTRIES; x++) { 02700 if (fp_cache[x].lru_count < y && fp_cache[x].lock == 0) { 02701 z = x; 02702 y = fp_cache[x].lru_count; 02703 } 02704 } 02705 02706 /* decrease all */ 02707 for (x = 0; x < FP_ENTRIES; x++) { 02708 if (fp_cache[x].lru_count > 3) { 02709 --(fp_cache[x].lru_count); 02710 } 02711 } 02712 02713 /* free entry z */ 02714 if (z >= 0 && fp_cache[z].g) { 02715 mp_clear(&fp_cache[z].mu); 02716 ecc_del_point(fp_cache[z].g); 02717 fp_cache[z].g = NULL; 02718 for (x = 0; x < (1U<<FP_LUT); x++) { 02719 ecc_del_point(fp_cache[z].LUT[x]); 02720 fp_cache[z].LUT[x] = NULL; 02721 } 02722 fp_cache[z].lru_count = 0; 02723 } 02724 return z; 02725 } 02726 02727 /* determine if a base is already in the cache and if so, where */ 02728 static int find_base(ecc_point* g) 02729 { 02730 int x; 02731 for (x = 0; x < FP_ENTRIES; x++) { 02732 if (fp_cache[x].g != NULL && 02733 mp_cmp(&fp_cache[x].g->x, &g->x) == MP_EQ && 02734 mp_cmp(&fp_cache[x].g->y, &g->y) == MP_EQ && 02735 mp_cmp(&fp_cache[x].g->z, &g->z) == MP_EQ) { 02736 break; 02737 } 02738 } 02739 if (x == FP_ENTRIES) { 02740 x = -1; 02741 } 02742 return x; 02743 } 02744 02745 /* add a new base to the cache */ 02746 static int add_entry(int idx, ecc_point *g) 02747 { 02748 unsigned x, y; 02749 02750 /* allocate base and LUT */ 02751 fp_cache[idx].g = ecc_new_point(); 02752 if (fp_cache[idx].g == NULL) { 02753 return GEN_MEM_ERR; 02754 } 02755 02756 /* copy x and y */ 02757 if ((mp_copy(&g->x, &fp_cache[idx].g->x) != MP_OKAY) || 02758 (mp_copy(&g->y, &fp_cache[idx].g->y) != MP_OKAY) || 02759 (mp_copy(&g->z, &fp_cache[idx].g->z) != MP_OKAY)) { 02760 ecc_del_point(fp_cache[idx].g); 02761 fp_cache[idx].g = NULL; 02762 return GEN_MEM_ERR; 02763 } 02764 02765 for (x = 0; x < (1U<<FP_LUT); x++) { 02766 fp_cache[idx].LUT[x] = ecc_new_point(); 02767 if (fp_cache[idx].LUT[x] == NULL) { 02768 for (y = 0; y < x; y++) { 02769 ecc_del_point(fp_cache[idx].LUT[y]); 02770 fp_cache[idx].LUT[y] = NULL; 02771 } 02772 ecc_del_point(fp_cache[idx].g); 02773 fp_cache[idx].g = NULL; 02774 fp_cache[idx].lru_count = 0; 02775 return GEN_MEM_ERR; 02776 } 02777 } 02778 02779 fp_cache[idx].lru_count = 0; 02780 02781 return MP_OKAY; 02782 } 02783 02784 /* build the LUT by spacing the bits of the input by #modulus/FP_LUT bits apart 02785 * 02786 * The algorithm builds patterns in increasing bit order by first making all 02787 * single bit input patterns, then all two bit input patterns and so on 02788 */ 02789 static int build_lut(int idx, mp_int* modulus, mp_digit* mp, mp_int* mu) 02790 { 02791 unsigned x, y, err, bitlen, lut_gap; 02792 mp_int tmp; 02793 02794 if (mp_init(&tmp) != MP_OKAY) 02795 return GEN_MEM_ERR; 02796 02797 /* sanity check to make sure lut_order table is of correct size, 02798 should compile out to a NOP if true */ 02799 if ((sizeof(lut_orders) / sizeof(lut_orders[0])) < (1U<<FP_LUT)) { 02800 err = BAD_FUNC_ARG; 02801 } 02802 else { 02803 /* get bitlen and round up to next multiple of FP_LUT */ 02804 bitlen = mp_unsigned_bin_size(modulus) << 3; 02805 x = bitlen % FP_LUT; 02806 if (x) { 02807 bitlen += FP_LUT - x; 02808 } 02809 lut_gap = bitlen / FP_LUT; 02810 02811 /* init the mu */ 02812 err = mp_init_copy(&fp_cache[idx].mu, mu); 02813 } 02814 02815 /* copy base */ 02816 if (err == MP_OKAY) { 02817 if ((mp_mulmod(&fp_cache[idx].g->x, mu, modulus, 02818 &fp_cache[idx].LUT[1]->x) != MP_OKAY) || 02819 (mp_mulmod(&fp_cache[idx].g->y, mu, modulus, 02820 &fp_cache[idx].LUT[1]->y) != MP_OKAY) || 02821 (mp_mulmod(&fp_cache[idx].g->z, mu, modulus, 02822 &fp_cache[idx].LUT[1]->z) != MP_OKAY)) { 02823 err = MP_MULMOD_E; 02824 } 02825 } 02826 02827 /* make all single bit entries */ 02828 for (x = 1; x < FP_LUT; x++) { 02829 if (err != MP_OKAY) 02830 break; 02831 if ((mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->x, 02832 &fp_cache[idx].LUT[1<<x]->x) != MP_OKAY) || 02833 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->y, 02834 &fp_cache[idx].LUT[1<<x]->y) != MP_OKAY) || 02835 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->z, 02836 &fp_cache[idx].LUT[1<<x]->z) != MP_OKAY)){ 02837 err = MP_INIT_E; 02838 break; 02839 } else { 02840 02841 /* now double it bitlen/FP_LUT times */ 02842 for (y = 0; y < lut_gap; y++) { 02843 if ((err = ecc_projective_dbl_point(fp_cache[idx].LUT[1<<x], 02844 fp_cache[idx].LUT[1<<x], modulus, mp)) != MP_OKAY) { 02845 break; 02846 } 02847 } 02848 } 02849 } 02850 02851 /* now make all entries in increase order of hamming weight */ 02852 for (x = 2; x <= FP_LUT; x++) { 02853 if (err != MP_OKAY) 02854 break; 02855 for (y = 0; y < (1UL<<FP_LUT); y++) { 02856 if (err != MP_OKAY) 02857 break; 02858 if (lut_orders[y].ham != (int)x) continue; 02859 02860 /* perform the add */ 02861 if ((err = ecc_projective_add_point( 02862 fp_cache[idx].LUT[lut_orders[y].terma], 02863 fp_cache[idx].LUT[lut_orders[y].termb], 02864 fp_cache[idx].LUT[y], modulus, mp)) != MP_OKAY) { 02865 break; 02866 } 02867 } 02868 } 02869 02870 /* now map all entries back to affine space to make point addition faster */ 02871 for (x = 1; x < (1UL<<FP_LUT); x++) { 02872 if (err != MP_OKAY) 02873 break; 02874 02875 /* convert z to normal from montgomery */ 02876 err = mp_montgomery_reduce(&fp_cache[idx].LUT[x]->z, modulus, *mp); 02877 02878 /* invert it */ 02879 if (err == MP_OKAY) 02880 err = mp_invmod(&fp_cache[idx].LUT[x]->z, modulus, 02881 &fp_cache[idx].LUT[x]->z); 02882 02883 if (err == MP_OKAY) 02884 /* now square it */ 02885 err = mp_sqrmod(&fp_cache[idx].LUT[x]->z, modulus, &tmp); 02886 02887 if (err == MP_OKAY) 02888 /* fix x */ 02889 err = mp_mulmod(&fp_cache[idx].LUT[x]->x, &tmp, modulus, 02890 &fp_cache[idx].LUT[x]->x); 02891 02892 if (err == MP_OKAY) 02893 /* get 1/z^3 */ 02894 err = mp_mulmod(&tmp, &fp_cache[idx].LUT[x]->z, modulus, &tmp); 02895 02896 if (err == MP_OKAY) 02897 /* fix y */ 02898 err = mp_mulmod(&fp_cache[idx].LUT[x]->y, &tmp, modulus, 02899 &fp_cache[idx].LUT[x]->y); 02900 02901 if (err == MP_OKAY) 02902 /* free z */ 02903 mp_clear(&fp_cache[idx].LUT[x]->z); 02904 } 02905 mp_clear(&tmp); 02906 02907 if (err == MP_OKAY) 02908 return MP_OKAY; 02909 02910 /* err cleanup */ 02911 for (y = 0; y < (1U<<FP_LUT); y++) { 02912 ecc_del_point(fp_cache[idx].LUT[y]); 02913 fp_cache[idx].LUT[y] = NULL; 02914 } 02915 ecc_del_point(fp_cache[idx].g); 02916 fp_cache[idx].g = NULL; 02917 fp_cache[idx].lru_count = 0; 02918 mp_clear(&fp_cache[idx].mu); 02919 mp_clear(&tmp); 02920 02921 return err; 02922 } 02923 02924 /* perform a fixed point ECC mulmod */ 02925 static int accel_fp_mul(int idx, mp_int* k, ecc_point *R, mp_int* modulus, 02926 mp_digit* mp, int map) 02927 { 02928 unsigned char kb[128]; 02929 int x; 02930 unsigned y, z, err, bitlen, bitpos, lut_gap, first; 02931 mp_int tk; 02932 02933 if (mp_init(&tk) != MP_OKAY) 02934 return MP_INIT_E; 02935 02936 /* if it's smaller than modulus we fine */ 02937 if (mp_unsigned_bin_size(k) > mp_unsigned_bin_size(modulus)) { 02938 mp_int order; 02939 if (mp_init(&order) != MP_OKAY) { 02940 mp_clear(&tk); 02941 return MP_INIT_E; 02942 } 02943 02944 /* find order */ 02945 y = mp_unsigned_bin_size(modulus); 02946 for (x = 0; ecc_sets[x].size; x++) { 02947 if (y <= (unsigned)ecc_sets[x].size) break; 02948 } 02949 02950 /* back off if we are on the 521 bit curve */ 02951 if (y == 66) --x; 02952 02953 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 02954 mp_clear(&order); 02955 mp_clear(&tk); 02956 return err; 02957 } 02958 02959 /* k must be less than modulus */ 02960 if (mp_cmp(k, &order) != MP_LT) { 02961 if ((err = mp_mod(k, &order, &tk)) != MP_OKAY) { 02962 mp_clear(&tk); 02963 mp_clear(&order); 02964 return err; 02965 } 02966 } else { 02967 mp_copy(k, &tk); 02968 } 02969 mp_clear(&order); 02970 } else { 02971 mp_copy(k, &tk); 02972 } 02973 02974 /* get bitlen and round up to next multiple of FP_LUT */ 02975 bitlen = mp_unsigned_bin_size(modulus) << 3; 02976 x = bitlen % FP_LUT; 02977 if (x) { 02978 bitlen += FP_LUT - x; 02979 } 02980 lut_gap = bitlen / FP_LUT; 02981 02982 /* get the k value */ 02983 if (mp_unsigned_bin_size(&tk) > (int)(sizeof(kb) - 2)) { 02984 mp_clear(&tk); 02985 return BUFFER_E; 02986 } 02987 02988 /* store k */ 02989 XMEMSET(kb, 0, sizeof(kb)); 02990 if ((err = mp_to_unsigned_bin(&tk, kb)) != MP_OKAY) { 02991 mp_clear(&tk); 02992 return err; 02993 } 02994 02995 /* let's reverse kb so it's little endian */ 02996 x = 0; 02997 y = mp_unsigned_bin_size(&tk) - 1; 02998 mp_clear(&tk); 02999 03000 while ((unsigned)x < y) { 03001 z = kb[x]; kb[x] = kb[y]; kb[y] = z; 03002 ++x; --y; 03003 } 03004 03005 /* at this point we can start, yipee */ 03006 first = 1; 03007 for (x = lut_gap-1; x >= 0; x--) { 03008 /* extract FP_LUT bits from kb spread out by lut_gap bits and offset 03009 by x bits from the start */ 03010 bitpos = x; 03011 for (y = z = 0; y < FP_LUT; y++) { 03012 z |= ((kb[bitpos>>3] >> (bitpos&7)) & 1) << y; 03013 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid 03014 the mult in each loop */ 03015 } 03016 03017 /* double if not first */ 03018 if (!first) { 03019 if ((err = ecc_projective_dbl_point(R, R, modulus, mp)) != MP_OKAY) { 03020 return err; 03021 } 03022 } 03023 03024 /* add if not first, otherwise copy */ 03025 if (!first && z) { 03026 if ((err = ecc_projective_add_point(R, fp_cache[idx].LUT[z], R, 03027 modulus, mp)) != MP_OKAY) { 03028 return err; 03029 } 03030 } else if (z) { 03031 if ((mp_copy(&fp_cache[idx].LUT[z]->x, &R->x) != MP_OKAY) || 03032 (mp_copy(&fp_cache[idx].LUT[z]->y, &R->y) != MP_OKAY) || 03033 (mp_copy(&fp_cache[idx].mu, &R->z) != MP_OKAY)) { 03034 return GEN_MEM_ERR; 03035 } 03036 first = 0; 03037 } 03038 } 03039 z = 0; 03040 XMEMSET(kb, 0, sizeof(kb)); 03041 /* map R back from projective space */ 03042 if (map) { 03043 err = ecc_map(R, modulus, mp); 03044 } else { 03045 err = MP_OKAY; 03046 } 03047 03048 return err; 03049 } 03050 03051 #ifdef ECC_SHAMIR 03052 /* perform a fixed point ECC mulmod */ 03053 static int accel_fp_mul2add(int idx1, int idx2, 03054 mp_int* kA, mp_int* kB, 03055 ecc_point *R, mp_int* modulus, mp_digit* mp) 03056 { 03057 unsigned char kb[2][128]; 03058 int x; 03059 unsigned y, z, err, bitlen, bitpos, lut_gap, first, zA, zB; 03060 mp_int tka; 03061 mp_int tkb; 03062 mp_int order; 03063 03064 if (mp_init_multi(&tka, &tkb, 0, 0, 0, 0) != MP_OKAY) 03065 return MP_INIT_E; 03066 03067 /* if it's smaller than modulus we fine */ 03068 if (mp_unsigned_bin_size(kA) > mp_unsigned_bin_size(modulus)) { 03069 /* find order */ 03070 y = mp_unsigned_bin_size(modulus); 03071 for (x = 0; ecc_sets[x].size; x++) { 03072 if (y <= (unsigned)ecc_sets[x].size) break; 03073 } 03074 03075 /* back off if we are on the 521 bit curve */ 03076 if (y == 66) --x; 03077 03078 if ((err = mp_init(&order)) != MP_OKAY) { 03079 mp_clear(&tkb); 03080 mp_clear(&tka); 03081 return err; 03082 } 03083 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 03084 mp_clear(&tkb); 03085 mp_clear(&tka); 03086 mp_clear(&order); 03087 return err; 03088 } 03089 03090 /* kA must be less than modulus */ 03091 if (mp_cmp(kA, &order) != MP_LT) { 03092 if ((err = mp_mod(kA, &order, &tka)) != MP_OKAY) { 03093 mp_clear(&tkb); 03094 mp_clear(&tka); 03095 mp_clear(&order); 03096 return err; 03097 } 03098 } else { 03099 mp_copy(kA, &tka); 03100 } 03101 mp_clear(&order); 03102 } else { 03103 mp_copy(kA, &tka); 03104 } 03105 03106 /* if it's smaller than modulus we fine */ 03107 if (mp_unsigned_bin_size(kB) > mp_unsigned_bin_size(modulus)) { 03108 /* find order */ 03109 y = mp_unsigned_bin_size(modulus); 03110 for (x = 0; ecc_sets[x].size; x++) { 03111 if (y <= (unsigned)ecc_sets[x].size) break; 03112 } 03113 03114 /* back off if we are on the 521 bit curve */ 03115 if (y == 66) --x; 03116 03117 if ((err = mp_init(&order)) != MP_OKAY) { 03118 mp_clear(&tkb); 03119 mp_clear(&tka); 03120 return err; 03121 } 03122 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) { 03123 mp_clear(&tkb); 03124 mp_clear(&tka); 03125 mp_clear(&order); 03126 return err; 03127 } 03128 03129 /* kB must be less than modulus */ 03130 if (mp_cmp(kB, &order) != MP_LT) { 03131 if ((err = mp_mod(kB, &order, &tkb)) != MP_OKAY) { 03132 mp_clear(&tkb); 03133 mp_clear(&tka); 03134 mp_clear(&order); 03135 return err; 03136 } 03137 } else { 03138 mp_copy(kB, &tkb); 03139 } 03140 mp_clear(&order); 03141 } else { 03142 mp_copy(kB, &tkb); 03143 } 03144 03145 /* get bitlen and round up to next multiple of FP_LUT */ 03146 bitlen = mp_unsigned_bin_size(modulus) << 3; 03147 x = bitlen % FP_LUT; 03148 if (x) { 03149 bitlen += FP_LUT - x; 03150 } 03151 lut_gap = bitlen / FP_LUT; 03152 03153 /* get the k value */ 03154 if ((mp_unsigned_bin_size(&tka) > (int)(sizeof(kb[0]) - 2)) || 03155 (mp_unsigned_bin_size(&tkb) > (int)(sizeof(kb[0]) - 2)) ) { 03156 mp_clear(&tka); 03157 mp_clear(&tkb); 03158 return BUFFER_E; 03159 } 03160 03161 /* store k */ 03162 XMEMSET(kb, 0, sizeof(kb)); 03163 if ((err = mp_to_unsigned_bin(&tka, kb[0])) != MP_OKAY) { 03164 mp_clear(&tka); 03165 mp_clear(&tkb); 03166 return err; 03167 } 03168 03169 /* let's reverse kb so it's little endian */ 03170 x = 0; 03171 y = mp_unsigned_bin_size(&tka) - 1; 03172 mp_clear(&tka); 03173 while ((unsigned)x < y) { 03174 z = kb[0][x]; kb[0][x] = kb[0][y]; kb[0][y] = z; 03175 ++x; --y; 03176 } 03177 03178 /* store b */ 03179 if ((err = mp_to_unsigned_bin(&tkb, kb[1])) != MP_OKAY) { 03180 mp_clear(&tkb); 03181 return err; 03182 } 03183 03184 x = 0; 03185 y = mp_unsigned_bin_size(&tkb) - 1; 03186 mp_clear(&tkb); 03187 while ((unsigned)x < y) { 03188 z = kb[1][x]; kb[1][x] = kb[1][y]; kb[1][y] = z; 03189 ++x; --y; 03190 } 03191 03192 /* at this point we can start, yipee */ 03193 first = 1; 03194 for (x = lut_gap-1; x >= 0; x--) { 03195 /* extract FP_LUT bits from kb spread out by lut_gap bits and 03196 offset by x bits from the start */ 03197 bitpos = x; 03198 for (y = zA = zB = 0; y < FP_LUT; y++) { 03199 zA |= ((kb[0][bitpos>>3] >> (bitpos&7)) & 1) << y; 03200 zB |= ((kb[1][bitpos>>3] >> (bitpos&7)) & 1) << y; 03201 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid 03202 the mult in each loop */ 03203 } 03204 03205 /* double if not first */ 03206 if (!first) { 03207 if ((err = ecc_projective_dbl_point(R, R, modulus, mp)) != MP_OKAY) { 03208 return err; 03209 } 03210 } 03211 03212 /* add if not first, otherwise copy */ 03213 if (!first) { 03214 if (zA) { 03215 if ((err = ecc_projective_add_point(R, fp_cache[idx1].LUT[zA], 03216 R, modulus, mp)) != MP_OKAY) { 03217 return err; 03218 } 03219 } 03220 if (zB) { 03221 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB], 03222 R, modulus, mp)) != MP_OKAY) { 03223 return err; 03224 } 03225 } 03226 } else { 03227 if (zA) { 03228 if ((mp_copy(&fp_cache[idx1].LUT[zA]->x, &R->x) != MP_OKAY) || 03229 (mp_copy(&fp_cache[idx1].LUT[zA]->y, &R->y) != MP_OKAY) || 03230 (mp_copy(&fp_cache[idx1].mu, &R->z) != MP_OKAY)) { 03231 return GEN_MEM_ERR; 03232 } 03233 first = 0; 03234 } 03235 if (zB && first == 0) { 03236 if (zB) { 03237 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB], 03238 R, modulus, mp)) != MP_OKAY){ 03239 return err; 03240 } 03241 } 03242 } else if (zB && first == 1) { 03243 if ((mp_copy(&fp_cache[idx2].LUT[zB]->x, &R->x) != MP_OKAY) || 03244 (mp_copy(&fp_cache[idx2].LUT[zB]->y, &R->y) != MP_OKAY) || 03245 (mp_copy(&fp_cache[idx2].mu, &R->z) != MP_OKAY)) { 03246 return GEN_MEM_ERR; 03247 } 03248 first = 0; 03249 } 03250 } 03251 } 03252 XMEMSET(kb, 0, sizeof(kb)); 03253 03254 return ecc_map(R, modulus, mp); 03255 } 03256 03257 /** ECC Fixed Point mulmod global 03258 Computes kA*A + kB*B = C using Shamir's Trick 03259 A First point to multiply 03260 kA What to multiple A by 03261 B Second point to multiply 03262 kB What to multiple B by 03263 C [out] Destination point (can overlap with A or B) 03264 modulus Modulus for curve 03265 return MP_OKAY on success 03266 */ 03267 int ecc_mul2add(ecc_point* A, mp_int* kA, 03268 ecc_point* B, mp_int* kB, 03269 ecc_point* C, mp_int* modulus) 03270 { 03271 int idx1 = -1, idx2 = -1, err = MP_OKAY, mpInit = 0; 03272 mp_digit mp; 03273 mp_int mu; 03274 03275 err = mp_init(&mu); 03276 if (err != MP_OKAY) 03277 return err; 03278 03279 #ifndef HAVE_THREAD_LS 03280 if (initMutex == 0) { 03281 InitMutex(&ecc_fp_lock); 03282 initMutex = 1; 03283 } 03284 if (LockMutex(&ecc_fp_lock) != 0) 03285 return BAD_MUTEX_E; 03286 #endif /* HAVE_THREAD_LS */ 03287 03288 /* find point */ 03289 idx1 = find_base(A); 03290 03291 /* no entry? */ 03292 if (idx1 == -1) { 03293 /* find hole and add it */ 03294 if ((idx1 = find_hole()) >= 0) { 03295 err = add_entry(idx1, A); 03296 } 03297 } 03298 if (err == MP_OKAY && idx1 != -1) { 03299 /* increment LRU */ 03300 ++(fp_cache[idx1].lru_count); 03301 } 03302 03303 if (err == MP_OKAY) 03304 /* find point */ 03305 idx2 = find_base(B); 03306 03307 if (err == MP_OKAY) { 03308 /* no entry? */ 03309 if (idx2 == -1) { 03310 /* find hole and add it */ 03311 if ((idx2 = find_hole()) >= 0) 03312 err = add_entry(idx2, B); 03313 } 03314 } 03315 03316 if (err == MP_OKAY && idx2 != -1) { 03317 /* increment LRU */ 03318 ++(fp_cache[idx2].lru_count); 03319 } 03320 03321 if (err == MP_OKAY) { 03322 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03323 if (idx1 >= 0 && fp_cache[idx1].lru_count == 2) { 03324 /* compute mp */ 03325 err = mp_montgomery_setup(modulus, &mp); 03326 03327 if (err == MP_OKAY) { 03328 mpInit = 1; 03329 err = mp_montgomery_calc_normalization(&mu, modulus); 03330 } 03331 03332 if (err == MP_OKAY) 03333 /* build the LUT */ 03334 err = build_lut(idx1, modulus, &mp, &mu); 03335 } 03336 } 03337 03338 if (err == MP_OKAY) { 03339 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03340 if (idx2 >= 0 && fp_cache[idx2].lru_count == 2) { 03341 if (mpInit == 0) { 03342 /* compute mp */ 03343 err = mp_montgomery_setup(modulus, &mp); 03344 if (err == MP_OKAY) { 03345 mpInit = 1; 03346 err = mp_montgomery_calc_normalization(&mu, modulus); 03347 } 03348 } 03349 03350 if (err == MP_OKAY) 03351 /* build the LUT */ 03352 err = build_lut(idx2, modulus, &mp, &mu); 03353 } 03354 } 03355 03356 03357 if (err == MP_OKAY) { 03358 if (idx1 >=0 && idx2 >= 0 && fp_cache[idx1].lru_count >= 2 && 03359 fp_cache[idx2].lru_count >= 2) { 03360 if (mpInit == 0) { 03361 /* compute mp */ 03362 err = mp_montgomery_setup(modulus, &mp); 03363 } 03364 if (err == MP_OKAY) 03365 err = accel_fp_mul2add(idx1, idx2, kA, kB, C, modulus, &mp); 03366 } else { 03367 err = normal_ecc_mul2add(A, kA, B, kB, C, modulus); 03368 } 03369 } 03370 03371 #ifndef HAVE_THREAD_LS 03372 UnLockMutex(&ecc_fp_lock); 03373 #endif /* HAVE_THREAD_LS */ 03374 mp_clear(&mu); 03375 03376 return err; 03377 } 03378 #endif 03379 03380 /** ECC Fixed Point mulmod global 03381 k The multiplicand 03382 G Base point to multiply 03383 R [out] Destination of product 03384 modulus The modulus for the curve 03385 map [boolean] If non-zero maps the point back to affine co-ordinates, 03386 otherwise it's left in jacobian-montgomery form 03387 return MP_OKAY if successful 03388 */ 03389 int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus, 03390 int map) 03391 { 03392 int idx, err = MP_OKAY; 03393 mp_digit mp; 03394 mp_int mu; 03395 int mpSetup = 0; 03396 03397 if (mp_init(&mu) != MP_OKAY) 03398 return MP_INIT_E; 03399 03400 #ifndef HAVE_THREAD_LS 03401 if (initMutex == 0) { 03402 InitMutex(&ecc_fp_lock); 03403 initMutex = 1; 03404 } 03405 03406 if (LockMutex(&ecc_fp_lock) != 0) 03407 return BAD_MUTEX_E; 03408 #endif /* HAVE_THREAD_LS */ 03409 03410 /* find point */ 03411 idx = find_base(G); 03412 03413 /* no entry? */ 03414 if (idx == -1) { 03415 /* find hole and add it */ 03416 idx = find_hole(); 03417 03418 if (idx >= 0) 03419 err = add_entry(idx, G); 03420 } 03421 if (err == MP_OKAY && idx != -1) { 03422 /* increment LRU */ 03423 ++(fp_cache[idx].lru_count); 03424 } 03425 03426 03427 if (err == MP_OKAY) { 03428 /* if it's 2 build the LUT, if it's higher just use the LUT */ 03429 if (idx >= 0 && fp_cache[idx].lru_count == 2) { 03430 /* compute mp */ 03431 err = mp_montgomery_setup(modulus, &mp); 03432 03433 if (err == MP_OKAY) { 03434 /* compute mu */ 03435 mpSetup = 1; 03436 err = mp_montgomery_calc_normalization(&mu, modulus); 03437 } 03438 03439 if (err == MP_OKAY) 03440 /* build the LUT */ 03441 err = build_lut(idx, modulus, &mp, &mu); 03442 } 03443 } 03444 03445 if (err == MP_OKAY) { 03446 if (idx >= 0 && fp_cache[idx].lru_count >= 2) { 03447 if (mpSetup == 0) { 03448 /* compute mp */ 03449 err = mp_montgomery_setup(modulus, &mp); 03450 } 03451 if (err == MP_OKAY) 03452 err = accel_fp_mul(idx, k, R, modulus, &mp, map); 03453 } else { 03454 err = normal_ecc_mulmod(k, G, R, modulus, map); 03455 } 03456 } 03457 03458 #ifndef HAVE_THREAD_LS 03459 UnLockMutex(&ecc_fp_lock); 03460 #endif /* HAVE_THREAD_LS */ 03461 mp_clear(&mu); 03462 03463 return err; 03464 } 03465 03466 /* helper function for freeing the cache ... 03467 must be called with the cache mutex locked */ 03468 static void ecc_fp_free_cache(void) 03469 { 03470 unsigned x, y; 03471 for (x = 0; x < FP_ENTRIES; x++) { 03472 if (fp_cache[x].g != NULL) { 03473 for (y = 0; y < (1U<<FP_LUT); y++) { 03474 ecc_del_point(fp_cache[x].LUT[y]); 03475 fp_cache[x].LUT[y] = NULL; 03476 } 03477 ecc_del_point(fp_cache[x].g); 03478 fp_cache[x].g = NULL; 03479 mp_clear(&fp_cache[x].mu); 03480 fp_cache[x].lru_count = 0; 03481 fp_cache[x].lock = 0; 03482 } 03483 } 03484 } 03485 03486 /** Free the Fixed Point cache */ 03487 void ecc_fp_free(void) 03488 { 03489 #ifndef HAVE_THREAD_LS 03490 if (initMutex == 0) { 03491 InitMutex(&ecc_fp_lock); 03492 initMutex = 1; 03493 } 03494 03495 if (LockMutex(&ecc_fp_lock) == 0) { 03496 #endif /* HAVE_THREAD_LS */ 03497 03498 ecc_fp_free_cache(); 03499 03500 #ifndef HAVE_THREAD_LS 03501 UnLockMutex(&ecc_fp_lock); 03502 FreeMutex(&ecc_fp_lock); 03503 initMutex = 0; 03504 } 03505 #endif /* HAVE_THREAD_LS */ 03506 } 03507 03508 03509 #endif /* FP_ECC */ 03510 03511 #ifdef HAVE_ECC_ENCRYPT 03512 03513 03514 enum ecCliState { 03515 ecCLI_INIT = 1, 03516 ecCLI_SALT_GET = 2, 03517 ecCLI_SALT_SET = 3, 03518 ecCLI_SENT_REQ = 4, 03519 ecCLI_RECV_RESP = 5, 03520 ecCLI_BAD_STATE = 99 03521 }; 03522 03523 enum ecSrvState { 03524 ecSRV_INIT = 1, 03525 ecSRV_SALT_GET = 2, 03526 ecSRV_SALT_SET = 3, 03527 ecSRV_RECV_REQ = 4, 03528 ecSRV_SENT_RESP = 5, 03529 ecSRV_BAD_STATE = 99 03530 }; 03531 03532 03533 struct ecEncCtx { 03534 byte* kdfSalt; /* optional salt for kdf */ 03535 byte* kdfInfo; /* optional info for kdf */ 03536 byte* macSalt; /* optional salt for mac */ 03537 word32 kdfSaltSz; /* size of kdfSalt */ 03538 word32 kdfInfoSz; /* size of kdfInfo */ 03539 word32 macSaltSz; /* size of macSalt */ 03540 byte clientSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */ 03541 byte serverSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */ 03542 byte encAlgo; /* which encryption type */ 03543 byte kdfAlgo; /* which key derivation function type */ 03544 byte macAlgo; /* which mac function type */ 03545 byte protocol; /* are we REQ_RESP client or server ? */ 03546 byte cliSt; /* protocol state, for sanity checks */ 03547 byte srvSt; /* protocol state, for sanity checks */ 03548 }; 03549 03550 03551 const byte* ecc_ctx_get_own_salt(ecEncCtx* ctx) 03552 { 03553 if (ctx == NULL || ctx->protocol == 0) 03554 return NULL; 03555 03556 if (ctx->protocol == REQ_RESP_CLIENT) { 03557 if (ctx->cliSt == ecCLI_INIT) { 03558 ctx->cliSt = ecCLI_SALT_GET; 03559 return ctx->clientSalt; 03560 } 03561 else { 03562 ctx->cliSt = ecCLI_BAD_STATE; 03563 return NULL; 03564 } 03565 } 03566 else if (ctx->protocol == REQ_RESP_SERVER) { 03567 if (ctx->srvSt == ecSRV_INIT) { 03568 ctx->srvSt = ecSRV_SALT_GET; 03569 return ctx->serverSalt; 03570 } 03571 else { 03572 ctx->srvSt = ecSRV_BAD_STATE; 03573 return NULL; 03574 } 03575 } 03576 03577 return NULL; 03578 } 03579 03580 03581 static const char* exchange_info = "Secure Message Exchange"; 03582 03583 int ecc_ctx_set_peer_salt(ecEncCtx* ctx, const byte* salt) 03584 { 03585 byte tmp[EXCHANGE_SALT_SZ/2]; 03586 int halfSz = EXCHANGE_SALT_SZ/2; 03587 03588 if (ctx == NULL || ctx->protocol == 0 || salt == NULL) 03589 return BAD_FUNC_ARG; 03590 03591 if (ctx->protocol == REQ_RESP_CLIENT) { 03592 XMEMCPY(ctx->serverSalt, salt, EXCHANGE_SALT_SZ); 03593 if (ctx->cliSt == ecCLI_SALT_GET) 03594 ctx->cliSt = ecCLI_SALT_SET; 03595 else { 03596 ctx->cliSt = ecCLI_BAD_STATE; 03597 return BAD_ENC_STATE_E; 03598 } 03599 } 03600 else { 03601 XMEMCPY(ctx->clientSalt, salt, EXCHANGE_SALT_SZ); 03602 if (ctx->srvSt == ecSRV_SALT_GET) 03603 ctx->srvSt = ecSRV_SALT_SET; 03604 else { 03605 ctx->srvSt = ecSRV_BAD_STATE; 03606 return BAD_ENC_STATE_E; 03607 } 03608 } 03609 03610 /* mix half and half */ 03611 /* tmp stores 2nd half of client before overwrite */ 03612 XMEMCPY(tmp, ctx->clientSalt + halfSz, halfSz); 03613 XMEMCPY(ctx->clientSalt + halfSz, ctx->serverSalt, halfSz); 03614 XMEMCPY(ctx->serverSalt, tmp, halfSz); 03615 03616 ctx->kdfSalt = ctx->clientSalt; 03617 ctx->kdfSaltSz = EXCHANGE_SALT_SZ; 03618 03619 ctx->macSalt = ctx->serverSalt; 03620 ctx->macSaltSz = EXCHANGE_SALT_SZ; 03621 03622 ctx->kdfInfo = (byte*)exchange_info; 03623 ctx->kdfInfoSz = EXCHANGE_INFO_SZ; 03624 03625 return 0; 03626 } 03627 03628 03629 static int ecc_ctx_set_salt(ecEncCtx* ctx, int flags, RNG* rng) 03630 { 03631 byte* saltBuffer = NULL; 03632 03633 if (ctx == NULL || rng == NULL || flags == 0) 03634 return BAD_FUNC_ARG; 03635 03636 saltBuffer = (flags == REQ_RESP_CLIENT) ? ctx->clientSalt : ctx->serverSalt; 03637 RNG_GenerateBlock(rng, saltBuffer, EXCHANGE_SALT_SZ); 03638 03639 return 0; 03640 } 03641 03642 03643 static void ecc_ctx_init(ecEncCtx* ctx, int flags) 03644 { 03645 if (ctx) { 03646 XMEMSET(ctx, 0, sizeof(ecEncCtx)); 03647 03648 ctx->encAlgo = ecAES_128_CBC; 03649 ctx->kdfAlgo = ecHKDF_SHA256; 03650 ctx->macAlgo = ecHMAC_SHA256; 03651 ctx->protocol = (byte)flags; 03652 03653 if (flags == REQ_RESP_CLIENT) 03654 ctx->cliSt = ecCLI_INIT; 03655 if (flags == REQ_RESP_SERVER) 03656 ctx->srvSt = ecSRV_INIT; 03657 } 03658 } 03659 03660 03661 /* allow ecc context reset so user doesn't have to init/free for resue */ 03662 int ecc_ctx_reset(ecEncCtx* ctx, RNG* rng) 03663 { 03664 if (ctx == NULL || rng == NULL) 03665 return BAD_FUNC_ARG; 03666 03667 ecc_ctx_init(ctx, ctx->protocol); 03668 return ecc_ctx_set_salt(ctx, ctx->protocol, rng); 03669 } 03670 03671 03672 /* alloc/init and set defaults, return new Context */ 03673 ecEncCtx* ecc_ctx_new(int flags, RNG* rng) 03674 { 03675 int ret = 0; 03676 ecEncCtx* ctx = (ecEncCtx*)XMALLOC(sizeof(ecEncCtx), 0, DYNAMIC_TYPE_ECC); 03677 03678 if (ctx) 03679 ctx->protocol = (byte)flags; 03680 03681 ret = ecc_ctx_reset(ctx, rng); 03682 if (ret != 0) { 03683 ecc_ctx_free(ctx); 03684 ctx = NULL; 03685 } 03686 03687 return ctx; 03688 } 03689 03690 03691 /* free any resources, clear any keys */ 03692 void ecc_ctx_free(ecEncCtx* ctx) 03693 { 03694 if (ctx) { 03695 XMEMSET(ctx, 0, sizeof(ecEncCtx)); 03696 XFREE(ctx, 0, DYNAMIC_TYPE_ECC); 03697 } 03698 } 03699 03700 03701 static int ecc_get_key_sizes(ecEncCtx* ctx, int* encKeySz, int* ivSz, 03702 int* keysLen, word32* digestSz, word32* blockSz) 03703 { 03704 if (ctx) { 03705 switch (ctx->encAlgo) { 03706 case ecAES_128_CBC: 03707 *encKeySz = KEY_SIZE_128; 03708 *ivSz = IV_SIZE_64; 03709 *blockSz = AES_BLOCK_SIZE; 03710 break; 03711 default: 03712 return BAD_FUNC_ARG; 03713 } 03714 03715 switch (ctx->macAlgo) { 03716 case ecHMAC_SHA256: 03717 *digestSz = SHA256_DIGEST_SIZE; 03718 break; 03719 default: 03720 return BAD_FUNC_ARG; 03721 } 03722 } else 03723 return BAD_FUNC_ARG; 03724 03725 *keysLen = *encKeySz + *ivSz + *digestSz; 03726 03727 return 0; 03728 } 03729 03730 03731 /* ecc encrypt with shared secret run through kdf 03732 ctx holds non default algos and inputs 03733 msgSz should be the right size for encAlgo, i.e., already padded 03734 return 0 on success */ 03735 int ecc_encrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg, 03736 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx) 03737 { 03738 int ret; 03739 word32 blockSz; 03740 word32 digestSz; 03741 ecEncCtx localCtx; 03742 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */ 03743 byte keys[ECC_BUFSIZE]; /* max size */ 03744 word32 sharedSz = sizeof(sharedSecret); 03745 int keysLen; 03746 int encKeySz; 03747 int ivSz; 03748 int offset = 0; /* keys offset if doing msg exchange */ 03749 byte* encKey; 03750 byte* encIv; 03751 byte* macKey; 03752 03753 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL || 03754 outSz == NULL) 03755 return BAD_FUNC_ARG; 03756 03757 if (ctx == NULL) { /* use defaults */ 03758 ecc_ctx_init(&localCtx, 0); 03759 ctx = &localCtx; 03760 } 03761 03762 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz, 03763 &blockSz); 03764 if (ret != 0) 03765 return ret; 03766 03767 if (ctx->protocol == REQ_RESP_SERVER) { 03768 offset = keysLen; 03769 keysLen *= 2; 03770 03771 if (ctx->srvSt != ecSRV_RECV_REQ) 03772 return BAD_ENC_STATE_E; 03773 03774 ctx->srvSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */ 03775 } 03776 else if (ctx->protocol == REQ_RESP_CLIENT) { 03777 if (ctx->cliSt != ecCLI_SALT_SET) 03778 return BAD_ENC_STATE_E; 03779 03780 ctx->cliSt = ecCLI_SENT_REQ; /* only do this once */ 03781 } 03782 03783 if (keysLen > (int)sizeof(keys)) 03784 return BUFFER_E; 03785 03786 if ( (msgSz%blockSz) != 0) 03787 return BAD_PADDING_E; 03788 03789 if (*outSz < (msgSz + digestSz)) 03790 return BUFFER_E; 03791 03792 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 03793 if (ret != 0) 03794 return ret; 03795 03796 switch (ctx->kdfAlgo) { 03797 case ecHKDF_SHA256 : 03798 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt, 03799 ctx->kdfSaltSz, ctx->kdfInfo, 03800 ctx->kdfInfoSz, keys, keysLen); 03801 if (ret != 0) 03802 return ret; 03803 break; 03804 03805 default: 03806 return BAD_FUNC_ARG; 03807 } 03808 03809 encKey = keys + offset; 03810 encIv = encKey + encKeySz; 03811 macKey = encKey + encKeySz + ivSz; 03812 03813 switch (ctx->encAlgo) { 03814 case ecAES_128_CBC: 03815 { 03816 Aes aes; 03817 ret = AesSetKey(&aes, encKey,KEY_SIZE_128,encIv,AES_ENCRYPTION); 03818 if (ret != 0) 03819 return ret; 03820 ret = AesCbcEncrypt(&aes, out, msg, msgSz); 03821 if (ret != 0) 03822 return ret; 03823 } 03824 break; 03825 03826 default: 03827 return BAD_FUNC_ARG; 03828 } 03829 03830 switch (ctx->macAlgo) { 03831 case ecHMAC_SHA256: 03832 { 03833 Hmac hmac; 03834 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE); 03835 if (ret != 0) 03836 return ret; 03837 HmacUpdate(&hmac, out, msgSz); 03838 HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz); 03839 HmacFinal(&hmac, out+msgSz); 03840 } 03841 break; 03842 03843 default: 03844 return BAD_FUNC_ARG; 03845 } 03846 03847 *outSz = msgSz + digestSz; 03848 03849 return 0; 03850 } 03851 03852 03853 /* ecc decrypt with shared secret run through kdf 03854 ctx holds non default algos and inputs 03855 return 0 on success */ 03856 int ecc_decrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg, 03857 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx) 03858 { 03859 int ret; 03860 word32 blockSz; 03861 word32 digestSz; 03862 ecEncCtx localCtx; 03863 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */ 03864 byte keys[ECC_BUFSIZE]; /* max size */ 03865 word32 sharedSz = sizeof(sharedSecret); 03866 int keysLen; 03867 int encKeySz; 03868 int ivSz; 03869 int offset = 0; /* in case using msg exchange */ 03870 byte* encKey; 03871 byte* encIv; 03872 byte* macKey; 03873 03874 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL || 03875 outSz == NULL) 03876 return BAD_FUNC_ARG; 03877 03878 if (ctx == NULL) { /* use defaults */ 03879 ecc_ctx_init(&localCtx, 0); 03880 ctx = &localCtx; 03881 } 03882 03883 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz, 03884 &blockSz); 03885 if (ret != 0) 03886 return ret; 03887 03888 if (ctx->protocol == REQ_RESP_CLIENT) { 03889 offset = keysLen; 03890 keysLen *= 2; 03891 03892 if (ctx->cliSt != ecCLI_SENT_REQ) 03893 return BAD_ENC_STATE_E; 03894 03895 ctx->cliSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */ 03896 } 03897 else if (ctx->protocol == REQ_RESP_SERVER) { 03898 if (ctx->srvSt != ecSRV_SALT_SET) 03899 return BAD_ENC_STATE_E; 03900 03901 ctx->srvSt = ecSRV_RECV_REQ; /* only do this once */ 03902 } 03903 03904 if (keysLen > (int)sizeof(keys)) 03905 return BUFFER_E; 03906 03907 if ( ((msgSz-digestSz) % blockSz) != 0) 03908 return BAD_PADDING_E; 03909 03910 if (*outSz < (msgSz - digestSz)) 03911 return BUFFER_E; 03912 03913 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 03914 if (ret != 0) 03915 return ret; 03916 03917 switch (ctx->kdfAlgo) { 03918 case ecHKDF_SHA256 : 03919 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt, 03920 ctx->kdfSaltSz, ctx->kdfInfo, 03921 ctx->kdfInfoSz, keys, keysLen); 03922 if (ret != 0) 03923 return ret; 03924 break; 03925 03926 default: 03927 return BAD_FUNC_ARG; 03928 } 03929 03930 encKey = keys + offset; 03931 encIv = encKey + encKeySz; 03932 macKey = encKey + encKeySz + ivSz; 03933 03934 switch (ctx->macAlgo) { 03935 case ecHMAC_SHA256: 03936 { 03937 byte verify[SHA256_DIGEST_SIZE]; 03938 Hmac hmac; 03939 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE); 03940 if (ret != 0) 03941 return ret; 03942 HmacUpdate(&hmac, msg, msgSz-digestSz); 03943 HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz); 03944 HmacFinal(&hmac, verify); 03945 03946 if (memcmp(verify, msg + msgSz - digestSz, digestSz) != 0) { 03947 return -1; 03948 } 03949 } 03950 break; 03951 03952 default: 03953 return BAD_FUNC_ARG; 03954 } 03955 03956 switch (ctx->encAlgo) { 03957 case ecAES_128_CBC: 03958 { 03959 Aes aes; 03960 ret = AesSetKey(&aes, encKey,KEY_SIZE_128,encIv,AES_DECRYPTION); 03961 if (ret != 0) 03962 return ret; 03963 ret = AesCbcDecrypt(&aes, out, msg, msgSz-digestSz); 03964 if (ret != 0) 03965 return ret; 03966 } 03967 break; 03968 03969 default: 03970 return BAD_FUNC_ARG; 03971 } 03972 03973 *outSz = msgSz - digestSz; 03974 03975 return 0; 03976 } 03977 03978 03979 #endif /* HAVE_ECC_ENCRYPT */ 03980 03981 #endif /* HAVE_ECC */
Generated on Tue Jul 12 2022 20:12:50 by
1.7.2