source: UsbWattMeter/trunk/wolfssl-3.7.0/wolfcrypt/src/ecc.c@ 167

Last change on this file since 167 was 167, checked in by coas-nagasima, 7 years ago

MIMEにSJISを設定
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
  • Property svn:mime-type set to text/x-csrc; charset=SHIFT_JIS
File size: 203.6 KB
Line 
1/* ecc.c
2 *
3 * Copyright (C) 2006-2015 wolfSSL Inc.
4 *
5 * This file is part of wolfSSL. (formerly known as CyaSSL)
6 *
7 * wolfSSL is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * wolfSSL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
20 */
21
22
23#ifdef HAVE_CONFIG_H
24 #include <config.h>
25#endif
26
27/* in case user set HAVE_ECC there */
28#include <wolfssl/wolfcrypt/settings.h>
29
30#ifdef HAVE_ECC
31
32#include <wolfssl/wolfcrypt/ecc.h>
33#include <wolfssl/openssl/ec.h>
34#include <wolfssl/wolfcrypt/asn.h>
35#include <wolfssl/wolfcrypt/error-crypt.h>
36
37#ifdef HAVE_ECC_ENCRYPT
38 #include <wolfssl/wolfcrypt/hmac.h>
39 #include <wolfssl/wolfcrypt/aes.h>
40#endif
41
42#ifdef NO_INLINE
43 #include <wolfssl/wolfcrypt/misc.h>
44#else
45 #include <wolfcrypt/src/misc.c>
46#endif
47
48/* map
49
50 ptmul -> mulmod
51
52*/
53
54
55/* p256 curve on by default whether user curves or not */
56#if defined(HAVE_ECC112) || defined(HAVE_ALL_CURVES)
57 #define ECC112
58#endif
59#if defined(HAVE_ECC128) || defined(HAVE_ALL_CURVES)
60 #define ECC128
61#endif
62#if defined(HAVE_ECC160) || defined(HAVE_ALL_CURVES)
63 #define ECC160
64#endif
65#if defined(HAVE_ECC192) || defined(HAVE_ALL_CURVES)
66 #define ECC192
67#endif
68#if defined(HAVE_ECC224) || defined(HAVE_ALL_CURVES)
69 #define ECC224
70#endif
71#if !defined(NO_ECC256) || defined(HAVE_ALL_CURVES)
72 #define ECC256
73#endif
74#if defined(HAVE_ECC384) || defined(HAVE_ALL_CURVES)
75 #define ECC384
76#endif
77#if defined(HAVE_ECC521) || defined(HAVE_ALL_CURVES)
78 #define ECC521
79#endif
80
81
82
83/* This holds the key settings. ***MUST*** be organized by size from
84 smallest to largest. */
85
86const ecc_set_type ecc_sets[] = {
87#ifdef ECC112
88{
89 14,
90 NID_secp111r1,
91 "SECP112R1",
92 "DB7C2ABF62E35E668076BEAD208B",
93 "DB7C2ABF62E35E668076BEAD2088",
94 "659EF8BA043916EEDE8911702B22",
95 "DB7C2ABF62E35E7628DFAC6561C5",
96 "09487239995A5EE76B55F9C2F098",
97 "A89CE5AF8724C0A23E0E0FF77500"
98},
99#endif
100#ifdef ECC128
101{
102 16,
103 NID_secp128r1,
104 "SECP128R1",
105 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
106 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC",
107 "E87579C11079F43DD824993C2CEE5ED3",
108 "FFFFFFFE0000000075A30D1B9038A115",
109 "161FF7528B899B2D0C28607CA52C5B86",
110 "CF5AC8395BAFEB13C02DA292DDED7A83",
111},
112#endif
113#ifdef ECC160
114{
115 20,
116 NID_secp160r1,
117 "SECP160R1",
118 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF",
119 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC",
120 "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45",
121 "0100000000000000000001F4C8F927AED3CA752257",
122 "4A96B5688EF573284664698968C38BB913CBFC82",
123 "23A628553168947D59DCC912042351377AC5FB32",
124},
125#endif
126#ifdef ECC192
127{
128 24,
129 NID_cert192,
130 "ECC-192",
131 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF",
132 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC",
133 "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1",
134 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
135 "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012",
136 "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811",
137},
138#endif
139#ifdef ECC224
140{
141 28,
142 NID_cert224,
143 "ECC-224",
144 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
145 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE",
146 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
147 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
148 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
149 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34",
150},
151#endif
152#ifdef ECC256
153{
154 32,
155 NID_X9_62_prime256v1,
156 "nistp256",
157 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
158 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC",
159 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
160 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
161 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
162 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
163},
164#endif
165#ifdef ECC384
166{
167 48,
168 NID_secp384r1,
169 "nistp384",
170 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
171 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC",
172 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
173 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
174 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
175 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
176},
177#endif
178#ifdef ECC521
179{
180 66,
181 NID_secp521r1,
182 "nistp521",
183 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
184 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC",
185 "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
186 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
187 "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
188 "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
189},
190#endif
191{
192 0, -1,
193 NULL, NULL, NULL, NULL, NULL, NULL, NULL
194}
195};
196
197
198int ecc_map(ecc_point*, mp_int*, mp_digit*);
199int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
200 mp_int* modulus, mp_digit* mp);
201int ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus,
202 mp_digit* mp);
203static int ecc_check_pubkey_order(ecc_key* key, mp_int* prime, mp_int* order);
204#ifdef ECC_SHAMIR
205static int ecc_mul2add(ecc_point* A, mp_int* kA, ecc_point* B, mp_int* kB,
206 ecc_point* C, mp_int* modulus);
207#endif
208
209int mp_jacobi(mp_int* a, mp_int* p, int* c);
210int mp_sqrtmod_prime(mp_int* n, mp_int* prime, mp_int* ret);
211int mp_submod(mp_int* a, mp_int* b, mp_int* c, mp_int* d);
212
213#ifdef HAVE_COMP_KEY
214static int wc_ecc_export_x963_compressed(ecc_key*, byte* out, word32* outLen);
215#endif
216
217/* helper for either lib */
218static int get_digit_count(mp_int* a)
219{
220 if (a == NULL)
221 return 0;
222
223 return a->used;
224}
225
226/* helper for either lib */
227static mp_digit get_digit(mp_int* a, int n)
228{
229 if (a == NULL)
230 return 0;
231
232 return (n >= a->used || n < 0) ? 0 : a->dp[n];
233}
234
235
236#if defined(USE_FAST_MATH)
237
238/* fast math accelerated version, but not for fp ecc yet */
239
240/**
241 Add two ECC points
242 P The point to add
243 Q The point to add
244 R [out] The destination of the double
245 modulus The modulus of the field the ECC curve is in
246 mp The "b" value from montgomery_setup()
247 return MP_OKAY on success
248*/
249int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R,
250 mp_int* modulus, mp_digit* mp)
251{
252 fp_int t1, t2, x, y, z;
253 int err;
254
255 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
256 return ECC_BAD_ARG_E;
257
258 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
259 return err;
260 }
261
262 /* should we dbl instead? */
263 fp_sub(modulus, Q->y, &t1);
264 if ( (fp_cmp(P->x, Q->x) == FP_EQ) &&
265 (get_digit_count(Q->z) && fp_cmp(P->z, Q->z) == FP_EQ) &&
266 (fp_cmp(P->y, Q->y) == FP_EQ || fp_cmp(P->y, &t1) == FP_EQ)) {
267 return ecc_projective_dbl_point(P, R, modulus, mp);
268 }
269
270 fp_copy(P->x, &x);
271 fp_copy(P->y, &y);
272 fp_copy(P->z, &z);
273
274 /* if Z is one then these are no-operations */
275 if (get_digit_count(Q->z)) {
276 /* T1 = Z' * Z' */
277 fp_sqr(Q->z, &t1);
278 fp_montgomery_reduce(&t1, modulus, *mp);
279 /* X = X * T1 */
280 fp_mul(&t1, &x, &x);
281 fp_montgomery_reduce(&x, modulus, *mp);
282 /* T1 = Z' * T1 */
283 fp_mul(Q->z, &t1, &t1);
284 fp_montgomery_reduce(&t1, modulus, *mp);
285 /* Y = Y * T1 */
286 fp_mul(&t1, &y, &y);
287 fp_montgomery_reduce(&y, modulus, *mp);
288 }
289
290 /* T1 = Z*Z */
291 fp_sqr(&z, &t1);
292 fp_montgomery_reduce(&t1, modulus, *mp);
293 /* T2 = X' * T1 */
294 fp_mul(Q->x, &t1, &t2);
295 fp_montgomery_reduce(&t2, modulus, *mp);
296 /* T1 = Z * T1 */
297 fp_mul(&z, &t1, &t1);
298 fp_montgomery_reduce(&t1, modulus, *mp);
299 /* T1 = Y' * T1 */
300 fp_mul(Q->y, &t1, &t1);
301 fp_montgomery_reduce(&t1, modulus, *mp);
302
303 /* Y = Y - T1 */
304 fp_sub(&y, &t1, &y);
305 if (fp_cmp_d(&y, 0) == FP_LT) {
306 fp_add(&y, modulus, &y);
307 }
308 /* T1 = 2T1 */
309 fp_add(&t1, &t1, &t1);
310 if (fp_cmp(&t1, modulus) != FP_LT) {
311 fp_sub(&t1, modulus, &t1);
312 }
313 /* T1 = Y + T1 */
314 fp_add(&t1, &y, &t1);
315 if (fp_cmp(&t1, modulus) != FP_LT) {
316 fp_sub(&t1, modulus, &t1);
317 }
318 /* X = X - T2 */
319 fp_sub(&x, &t2, &x);
320 if (fp_cmp_d(&x, 0) == FP_LT) {
321 fp_add(&x, modulus, &x);
322 }
323 /* T2 = 2T2 */
324 fp_add(&t2, &t2, &t2);
325 if (fp_cmp(&t2, modulus) != FP_LT) {
326 fp_sub(&t2, modulus, &t2);
327 }
328 /* T2 = X + T2 */
329 fp_add(&t2, &x, &t2);
330 if (fp_cmp(&t2, modulus) != FP_LT) {
331 fp_sub(&t2, modulus, &t2);
332 }
333
334 /* if Z' != 1 */
335 if (get_digit_count(Q->z)) {
336 /* Z = Z * Z' */
337 fp_mul(&z, Q->z, &z);
338 fp_montgomery_reduce(&z, modulus, *mp);
339 }
340
341 /* Z = Z * X */
342 fp_mul(&z, &x, &z);
343 fp_montgomery_reduce(&z, modulus, *mp);
344
345 /* T1 = T1 * X */
346 fp_mul(&t1, &x, &t1);
347 fp_montgomery_reduce(&t1, modulus, *mp);
348 /* X = X * X */
349 fp_sqr(&x, &x);
350 fp_montgomery_reduce(&x, modulus, *mp);
351 /* T2 = T2 * x */
352 fp_mul(&t2, &x, &t2);
353 fp_montgomery_reduce(&t2, modulus, *mp);
354 /* T1 = T1 * X */
355 fp_mul(&t1, &x, &t1);
356 fp_montgomery_reduce(&t1, modulus, *mp);
357
358 /* X = Y*Y */
359 fp_sqr(&y, &x);
360 fp_montgomery_reduce(&x, modulus, *mp);
361 /* X = X - T2 */
362 fp_sub(&x, &t2, &x);
363 if (fp_cmp_d(&x, 0) == FP_LT) {
364 fp_add(&x, modulus, &x);
365 }
366
367 /* T2 = T2 - X */
368 fp_sub(&t2, &x, &t2);
369 if (fp_cmp_d(&t2, 0) == FP_LT) {
370 fp_add(&t2, modulus, &t2);
371 }
372 /* T2 = T2 - X */
373 fp_sub(&t2, &x, &t2);
374 if (fp_cmp_d(&t2, 0) == FP_LT) {
375 fp_add(&t2, modulus, &t2);
376 }
377 /* T2 = T2 * Y */
378 fp_mul(&t2, &y, &t2);
379 fp_montgomery_reduce(&t2, modulus, *mp);
380 /* Y = T2 - T1 */
381 fp_sub(&t2, &t1, &y);
382 if (fp_cmp_d(&y, 0) == FP_LT) {
383 fp_add(&y, modulus, &y);
384 }
385 /* Y = Y/2 */
386 if (fp_isodd(&y)) {
387 fp_add(&y, modulus, &y);
388 }
389 fp_div_2(&y, &y);
390
391 fp_copy(&x, R->x);
392 fp_copy(&y, R->y);
393 fp_copy(&z, R->z);
394
395 return MP_OKAY;
396}
397
398
399/**
400 Double an ECC point
401 P The point to double
402 R [out] The destination of the double
403 modulus The modulus of the field the ECC curve is in
404 mp The "b" value from montgomery_setup()
405 return MP_OKAY on success
406*/
407int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
408 mp_digit* mp)
409{
410 fp_int t1, t2;
411 int err;
412
413 if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
414 return ECC_BAD_ARG_E;
415
416 if (P != R) {
417 fp_copy(P->x, R->x);
418 fp_copy(P->y, R->y);
419 fp_copy(P->z, R->z);
420 }
421
422 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
423 return err;
424 }
425
426 /* t1 = Z * Z */
427 fp_sqr(R->z, &t1);
428 fp_montgomery_reduce(&t1, modulus, *mp);
429 /* Z = Y * Z */
430 fp_mul(R->z, R->y, R->z);
431 fp_montgomery_reduce(R->z, modulus, *mp);
432 /* Z = 2Z */
433 fp_add(R->z, R->z, R->z);
434 if (fp_cmp(R->z, modulus) != FP_LT) {
435 fp_sub(R->z, modulus, R->z);
436 }
437
438 /* &t2 = X - T1 */
439 fp_sub(R->x, &t1, &t2);
440 if (fp_cmp_d(&t2, 0) == FP_LT) {
441 fp_add(&t2, modulus, &t2);
442 }
443 /* T1 = X + T1 */
444 fp_add(&t1, R->x, &t1);
445 if (fp_cmp(&t1, modulus) != FP_LT) {
446 fp_sub(&t1, modulus, &t1);
447 }
448 /* T2 = T1 * T2 */
449 fp_mul(&t1, &t2, &t2);
450 fp_montgomery_reduce(&t2, modulus, *mp);
451 /* T1 = 2T2 */
452 fp_add(&t2, &t2, &t1);
453 if (fp_cmp(&t1, modulus) != FP_LT) {
454 fp_sub(&t1, modulus, &t1);
455 }
456 /* T1 = T1 + T2 */
457 fp_add(&t1, &t2, &t1);
458 if (fp_cmp(&t1, modulus) != FP_LT) {
459 fp_sub(&t1, modulus, &t1);
460 }
461
462 /* Y = 2Y */
463 fp_add(R->y, R->y, R->y);
464 if (fp_cmp(R->y, modulus) != FP_LT) {
465 fp_sub(R->y, modulus, R->y);
466 }
467 /* Y = Y * Y */
468 fp_sqr(R->y, R->y);
469 fp_montgomery_reduce(R->y, modulus, *mp);
470 /* T2 = Y * Y */
471 fp_sqr(R->y, &t2);
472 fp_montgomery_reduce(&t2, modulus, *mp);
473 /* T2 = T2/2 */
474 if (fp_isodd(&t2)) {
475 fp_add(&t2, modulus, &t2);
476 }
477 fp_div_2(&t2, &t2);
478 /* Y = Y * X */
479 fp_mul(R->y, R->x, R->y);
480 fp_montgomery_reduce(R->y, modulus, *mp);
481
482 /* X = T1 * T1 */
483 fp_sqr(&t1, R->x);
484 fp_montgomery_reduce(R->x, modulus, *mp);
485 /* X = X - Y */
486 fp_sub(R->x, R->y, R->x);
487 if (fp_cmp_d(R->x, 0) == FP_LT) {
488 fp_add(R->x, modulus, R->x);
489 }
490 /* X = X - Y */
491 fp_sub(R->x, R->y, R->x);
492 if (fp_cmp_d(R->x, 0) == FP_LT) {
493 fp_add(R->x, modulus, R->x);
494 }
495
496 /* Y = Y - X */
497 fp_sub(R->y, R->x, R->y);
498 if (fp_cmp_d(R->y, 0) == FP_LT) {
499 fp_add(R->y, modulus, R->y);
500 }
501 /* Y = Y * T1 */
502 fp_mul(R->y, &t1, R->y);
503 fp_montgomery_reduce(R->y, modulus, *mp);
504 /* Y = Y - T2 */
505 fp_sub(R->y, &t2, R->y);
506 if (fp_cmp_d(R->y, 0) == FP_LT) {
507 fp_add(R->y, modulus, R->y);
508 }
509
510 return MP_OKAY;
511}
512
513#else /* USE_FAST_MATH */
514
515/**
516 Add two ECC points
517 P The point to add
518 Q The point to add
519 R [out] The destination of the double
520 modulus The modulus of the field the ECC curve is in
521 mp The "b" value from montgomery_setup()
522 return MP_OKAY on success
523*/
524int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
525 mp_int* modulus, mp_digit* mp)
526{
527 mp_int t1;
528 mp_int t2;
529 mp_int x;
530 mp_int y;
531 mp_int z;
532 int err;
533
534 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
535 return ECC_BAD_ARG_E;
536
537 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
538 return err;
539 }
540
541 /* should we dbl instead? */
542 err = mp_sub(modulus, Q->y, &t1);
543
544 if (err == MP_OKAY) {
545 if ( (mp_cmp(P->x, Q->x) == MP_EQ) &&
546 (get_digit_count(Q->z) && mp_cmp(P->z, Q->z) == MP_EQ) &&
547 (mp_cmp(P->y, Q->y) == MP_EQ || mp_cmp(P->y, &t1) == MP_EQ)) {
548 mp_clear(&t1);
549 mp_clear(&t2);
550 mp_clear(&x);
551 mp_clear(&y);
552 mp_clear(&z);
553
554 return ecc_projective_dbl_point(P, R, modulus, mp);
555 }
556 }
557
558 if (err == MP_OKAY)
559 err = mp_copy(P->x, &x);
560 if (err == MP_OKAY)
561 err = mp_copy(P->y, &y);
562 if (err == MP_OKAY)
563 err = mp_copy(P->z, &z);
564
565 /* if Z is one then these are no-operations */
566 if (err == MP_OKAY) {
567 if (get_digit_count(Q->z)) {
568 /* T1 = Z' * Z' */
569 err = mp_sqr(Q->z, &t1);
570 if (err == MP_OKAY)
571 err = mp_montgomery_reduce(&t1, modulus, *mp);
572
573 /* X = X * T1 */
574 if (err == MP_OKAY)
575 err = mp_mul(&t1, &x, &x);
576 if (err == MP_OKAY)
577 err = mp_montgomery_reduce(&x, modulus, *mp);
578
579 /* T1 = Z' * T1 */
580 if (err == MP_OKAY)
581 err = mp_mul(Q->z, &t1, &t1);
582 if (err == MP_OKAY)
583 err = mp_montgomery_reduce(&t1, modulus, *mp);
584
585 /* Y = Y * T1 */
586 if (err == MP_OKAY)
587 err = mp_mul(&t1, &y, &y);
588 if (err == MP_OKAY)
589 err = mp_montgomery_reduce(&y, modulus, *mp);
590 }
591 }
592
593 /* T1 = Z*Z */
594 if (err == MP_OKAY)
595 err = mp_sqr(&z, &t1);
596 if (err == MP_OKAY)
597 err = mp_montgomery_reduce(&t1, modulus, *mp);
598
599 /* T2 = X' * T1 */
600 if (err == MP_OKAY)
601 err = mp_mul(Q->x, &t1, &t2);
602 if (err == MP_OKAY)
603 err = mp_montgomery_reduce(&t2, modulus, *mp);
604
605 /* T1 = Z * T1 */
606 if (err == MP_OKAY)
607 err = mp_mul(&z, &t1, &t1);
608 if (err == MP_OKAY)
609 err = mp_montgomery_reduce(&t1, modulus, *mp);
610
611 /* T1 = Y' * T1 */
612 if (err == MP_OKAY)
613 err = mp_mul(Q->y, &t1, &t1);
614 if (err == MP_OKAY)
615 err = mp_montgomery_reduce(&t1, modulus, *mp);
616
617 /* Y = Y - T1 */
618 if (err == MP_OKAY)
619 err = mp_sub(&y, &t1, &y);
620 if (err == MP_OKAY) {
621 if (mp_cmp_d(&y, 0) == MP_LT)
622 err = mp_add(&y, modulus, &y);
623 }
624 /* T1 = 2T1 */
625 if (err == MP_OKAY)
626 err = mp_add(&t1, &t1, &t1);
627 if (err == MP_OKAY) {
628 if (mp_cmp(&t1, modulus) != MP_LT)
629 err = mp_sub(&t1, modulus, &t1);
630 }
631 /* T1 = Y + T1 */
632 if (err == MP_OKAY)
633 err = mp_add(&t1, &y, &t1);
634 if (err == MP_OKAY) {
635 if (mp_cmp(&t1, modulus) != MP_LT)
636 err = mp_sub(&t1, modulus, &t1);
637 }
638 /* X = X - T2 */
639 if (err == MP_OKAY)
640 err = mp_sub(&x, &t2, &x);
641 if (err == MP_OKAY) {
642 if (mp_cmp_d(&x, 0) == MP_LT)
643 err = mp_add(&x, modulus, &x);
644 }
645 /* T2 = 2T2 */
646 if (err == MP_OKAY)
647 err = mp_add(&t2, &t2, &t2);
648 if (err == MP_OKAY) {
649 if (mp_cmp(&t2, modulus) != MP_LT)
650 err = mp_sub(&t2, modulus, &t2);
651 }
652 /* T2 = X + T2 */
653 if (err == MP_OKAY)
654 err = mp_add(&t2, &x, &t2);
655 if (err == MP_OKAY) {
656 if (mp_cmp(&t2, modulus) != MP_LT)
657 err = mp_sub(&t2, modulus, &t2);
658 }
659
660 if (err == MP_OKAY) {
661 if (get_digit_count(Q->z)) {
662 /* Z = Z * Z' */
663 err = mp_mul(&z, Q->z, &z);
664 if (err == MP_OKAY)
665 err = mp_montgomery_reduce(&z, modulus, *mp);
666 }
667 }
668
669 /* Z = Z * X */
670 if (err == MP_OKAY)
671 err = mp_mul(&z, &x, &z);
672 if (err == MP_OKAY)
673 err = mp_montgomery_reduce(&z, modulus, *mp);
674
675 /* T1 = T1 * X */
676 if (err == MP_OKAY)
677 err = mp_mul(&t1, &x, &t1);
678 if (err == MP_OKAY)
679 err = mp_montgomery_reduce(&t1, modulus, *mp);
680
681 /* X = X * X */
682 if (err == MP_OKAY)
683 err = mp_sqr(&x, &x);
684 if (err == MP_OKAY)
685 err = mp_montgomery_reduce(&x, modulus, *mp);
686
687 /* T2 = T2 * x */
688 if (err == MP_OKAY)
689 err = mp_mul(&t2, &x, &t2);
690 if (err == MP_OKAY)
691 err = mp_montgomery_reduce(&t2, modulus, *mp);
692
693 /* T1 = T1 * X */
694 if (err == MP_OKAY)
695 err = mp_mul(&t1, &x, &t1);
696 if (err == MP_OKAY)
697 err = mp_montgomery_reduce(&t1, modulus, *mp);
698
699 /* X = Y*Y */
700 if (err == MP_OKAY)
701 err = mp_sqr(&y, &x);
702 if (err == MP_OKAY)
703 err = mp_montgomery_reduce(&x, modulus, *mp);
704
705 /* X = X - T2 */
706 if (err == MP_OKAY)
707 err = mp_sub(&x, &t2, &x);
708 if (err == MP_OKAY) {
709 if (mp_cmp_d(&x, 0) == MP_LT)
710 err = mp_add(&x, modulus, &x);
711 }
712 /* T2 = T2 - X */
713 if (err == MP_OKAY)
714 err = mp_sub(&t2, &x, &t2);
715 if (err == MP_OKAY) {
716 if (mp_cmp_d(&t2, 0) == MP_LT)
717 err = mp_add(&t2, modulus, &t2);
718 }
719 /* T2 = T2 - X */
720 if (err == MP_OKAY)
721 err = mp_sub(&t2, &x, &t2);
722 if (err == MP_OKAY) {
723 if (mp_cmp_d(&t2, 0) == MP_LT)
724 err = mp_add(&t2, modulus, &t2);
725 }
726 /* T2 = T2 * Y */
727 if (err == MP_OKAY)
728 err = mp_mul(&t2, &y, &t2);
729 if (err == MP_OKAY)
730 err = mp_montgomery_reduce(&t2, modulus, *mp);
731
732 /* Y = T2 - T1 */
733 if (err == MP_OKAY)
734 err = mp_sub(&t2, &t1, &y);
735 if (err == MP_OKAY) {
736 if (mp_cmp_d(&y, 0) == MP_LT)
737 err = mp_add(&y, modulus, &y);
738 }
739 /* Y = Y/2 */
740 if (err == MP_OKAY) {
741 if (mp_isodd(&y))
742 err = mp_add(&y, modulus, &y);
743 }
744 if (err == MP_OKAY)
745 err = mp_div_2(&y, &y);
746
747 if (err == MP_OKAY)
748 err = mp_copy(&x, R->x);
749 if (err == MP_OKAY)
750 err = mp_copy(&y, R->y);
751 if (err == MP_OKAY)
752 err = mp_copy(&z, R->z);
753
754 /* clean up */
755 mp_clear(&t1);
756 mp_clear(&t2);
757 mp_clear(&x);
758 mp_clear(&y);
759 mp_clear(&z);
760
761 return err;
762}
763
764
765/**
766 Double an ECC point
767 P The point to double
768 R [out] The destination of the double
769 modulus The modulus of the field the ECC curve is in
770 mp The "b" value from montgomery_setup()
771 return MP_OKAY on success
772*/
773int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
774 mp_digit* mp)
775{
776 mp_int t1;
777 mp_int t2;
778 int err;
779
780 if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
781 return ECC_BAD_ARG_E;
782
783 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
784 return err;
785 }
786
787 if (P != R) {
788 err = mp_copy(P->x, R->x);
789 if (err == MP_OKAY)
790 err = mp_copy(P->y, R->y);
791 if (err == MP_OKAY)
792 err = mp_copy(P->z, R->z);
793 }
794
795 /* t1 = Z * Z */
796 if (err == MP_OKAY)
797 err = mp_sqr(R->z, &t1);
798 if (err == MP_OKAY)
799 err = mp_montgomery_reduce(&t1, modulus, *mp);
800
801 /* Z = Y * Z */
802 if (err == MP_OKAY)
803 err = mp_mul(R->z, R->y, R->z);
804 if (err == MP_OKAY)
805 err = mp_montgomery_reduce(R->z, modulus, *mp);
806
807 /* Z = 2Z */
808 if (err == MP_OKAY)
809 err = mp_add(R->z, R->z, R->z);
810 if (err == MP_OKAY) {
811 if (mp_cmp(R->z, modulus) != MP_LT)
812 err = mp_sub(R->z, modulus, R->z);
813 }
814
815 /* T2 = X - T1 */
816 if (err == MP_OKAY)
817 err = mp_sub(R->x, &t1, &t2);
818 if (err == MP_OKAY) {
819 if (mp_cmp_d(&t2, 0) == MP_LT)
820 err = mp_add(&t2, modulus, &t2);
821 }
822 /* T1 = X + T1 */
823 if (err == MP_OKAY)
824 err = mp_add(&t1, R->x, &t1);
825 if (err == MP_OKAY) {
826 if (mp_cmp(&t1, modulus) != MP_LT)
827 err = mp_sub(&t1, modulus, &t1);
828 }
829 /* T2 = T1 * T2 */
830 if (err == MP_OKAY)
831 err = mp_mul(&t1, &t2, &t2);
832 if (err == MP_OKAY)
833 err = mp_montgomery_reduce(&t2, modulus, *mp);
834
835 /* T1 = 2T2 */
836 if (err == MP_OKAY)
837 err = mp_add(&t2, &t2, &t1);
838 if (err == MP_OKAY) {
839 if (mp_cmp(&t1, modulus) != MP_LT)
840 err = mp_sub(&t1, modulus, &t1);
841 }
842 /* T1 = T1 + T2 */
843 if (err == MP_OKAY)
844 err = mp_add(&t1, &t2, &t1);
845 if (err == MP_OKAY) {
846 if (mp_cmp(&t1, modulus) != MP_LT)
847 err = mp_sub(&t1, modulus, &t1);
848 }
849 /* Y = 2Y */
850 if (err == MP_OKAY)
851 err = mp_add(R->y, R->y, R->y);
852 if (err == MP_OKAY) {
853 if (mp_cmp(R->y, modulus) != MP_LT)
854 err = mp_sub(R->y, modulus, R->y);
855 }
856 /* Y = Y * Y */
857 if (err == MP_OKAY)
858 err = mp_sqr(R->y, R->y);
859 if (err == MP_OKAY)
860 err = mp_montgomery_reduce(R->y, modulus, *mp);
861
862 /* T2 = Y * Y */
863 if (err == MP_OKAY)
864 err = mp_sqr(R->y, &t2);
865 if (err == MP_OKAY)
866 err = mp_montgomery_reduce(&t2, modulus, *mp);
867
868 /* T2 = T2/2 */
869 if (err == MP_OKAY) {
870 if (mp_isodd(&t2))
871 err = mp_add(&t2, modulus, &t2);
872 }
873 if (err == MP_OKAY)
874 err = mp_div_2(&t2, &t2);
875
876 /* Y = Y * X */
877 if (err == MP_OKAY)
878 err = mp_mul(R->y, R->x, R->y);
879 if (err == MP_OKAY)
880 err = mp_montgomery_reduce(R->y, modulus, *mp);
881
882 /* X = T1 * T1 */
883 if (err == MP_OKAY)
884 err = mp_sqr(&t1, R->x);
885 if (err == MP_OKAY)
886 err = mp_montgomery_reduce(R->x, modulus, *mp);
887
888 /* X = X - Y */
889 if (err == MP_OKAY)
890 err = mp_sub(R->x, R->y, R->x);
891 if (err == MP_OKAY) {
892 if (mp_cmp_d(R->x, 0) == MP_LT)
893 err = mp_add(R->x, modulus, R->x);
894 }
895 /* X = X - Y */
896 if (err == MP_OKAY)
897 err = mp_sub(R->x, R->y, R->x);
898 if (err == MP_OKAY) {
899 if (mp_cmp_d(R->x, 0) == MP_LT)
900 err = mp_add(R->x, modulus, R->x);
901 }
902 /* Y = Y - X */
903 if (err == MP_OKAY)
904 err = mp_sub(R->y, R->x, R->y);
905 if (err == MP_OKAY) {
906 if (mp_cmp_d(R->y, 0) == MP_LT)
907 err = mp_add(R->y, modulus, R->y);
908 }
909 /* Y = Y * T1 */
910 if (err == MP_OKAY)
911 err = mp_mul(R->y, &t1, R->y);
912 if (err == MP_OKAY)
913 err = mp_montgomery_reduce(R->y, modulus, *mp);
914
915 /* Y = Y - T2 */
916 if (err == MP_OKAY)
917 err = mp_sub(R->y, &t2, R->y);
918 if (err == MP_OKAY) {
919 if (mp_cmp_d(R->y, 0) == MP_LT)
920 err = mp_add(R->y, modulus, R->y);
921 }
922
923 /* clean up */
924 mp_clear(&t1);
925 mp_clear(&t2);
926
927 return err;
928}
929
930#endif /* USE_FAST_MATH */
931
932/**
933 Map a projective jacbobian point back to affine space
934 P [in/out] The point to map
935 modulus The modulus of the field the ECC curve is in
936 mp The "b" value from montgomery_setup()
937 return MP_OKAY on success
938*/
939int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp)
940{
941 mp_int t1;
942 mp_int t2;
943 int err;
944
945 if (P == NULL || mp == NULL || modulus == NULL)
946 return ECC_BAD_ARG_E;
947
948 /* special case for point at infinity */
949 if (mp_cmp_d(P->z, 0) == MP_EQ) {
950 mp_set(P->x, 0);
951 mp_set(P->y, 0);
952 mp_set(P->z, 1);
953 return MP_OKAY;
954 }
955
956 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
957 return MEMORY_E;
958 }
959
960 /* first map z back to normal */
961 err = mp_montgomery_reduce(P->z, modulus, *mp);
962
963 /* get 1/z */
964 if (err == MP_OKAY)
965 err = mp_invmod(P->z, modulus, &t1);
966
967 /* get 1/z^2 and 1/z^3 */
968 if (err == MP_OKAY)
969 err = mp_sqr(&t1, &t2);
970 if (err == MP_OKAY)
971 err = mp_mod(&t2, modulus, &t2);
972 if (err == MP_OKAY)
973 err = mp_mul(&t1, &t2, &t1);
974 if (err == MP_OKAY)
975 err = mp_mod(&t1, modulus, &t1);
976
977 /* multiply against x/y */
978 if (err == MP_OKAY)
979 err = mp_mul(P->x, &t2, P->x);
980 if (err == MP_OKAY)
981 err = mp_montgomery_reduce(P->x, modulus, *mp);
982 if (err == MP_OKAY)
983 err = mp_mul(P->y, &t1, P->y);
984 if (err == MP_OKAY)
985 err = mp_montgomery_reduce(P->y, modulus, *mp);
986
987 if (err == MP_OKAY)
988 mp_set(P->z, 1);
989
990 /* clean up */
991 mp_clear(&t1);
992 mp_clear(&t2);
993
994 return err;
995}
996
997
998#ifndef ECC_TIMING_RESISTANT
999
1000/* size of sliding window, don't change this! */
1001#define WINSIZE 4
1002
1003/**
1004 Perform a point multiplication
1005 k The scalar to multiply by
1006 G The base point
1007 R [out] Destination for kG
1008 modulus The modulus of the field the ECC curve is in
1009 map Boolean whether to map back to affine or not
1010 (1==map, 0 == leave in projective)
1011 return MP_OKAY on success
1012*/
1013#ifdef FP_ECC
1014static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R,
1015 mp_int* modulus, int map)
1016#else
1017int wc_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
1018 int map)
1019#endif
1020{
1021 ecc_point *tG, *M[8];
1022 int i, j, err;
1023 mp_int mu;
1024 mp_digit mp;
1025 mp_digit buf;
1026 int first = 1, bitbuf = 0, bitcpy = 0, bitcnt = 0, mode = 0,
1027 digidx = 0;
1028
1029 if (k == NULL || G == NULL || R == NULL || modulus == NULL)
1030 return ECC_BAD_ARG_E;
1031
1032 /* init montgomery reduction */
1033 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
1034 return err;
1035 }
1036 if ((err = mp_init(&mu)) != MP_OKAY) {
1037 return err;
1038 }
1039 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
1040 mp_clear(&mu);
1041 return err;
1042 }
1043
1044 /* alloc ram for window temps */
1045 for (i = 0; i < 8; i++) {
1046 M[i] = wc_ecc_new_point();
1047 if (M[i] == NULL) {
1048 for (j = 0; j < i; j++) {
1049 wc_ecc_del_point(M[j]);
1050 }
1051 mp_clear(&mu);
1052 return MEMORY_E;
1053 }
1054 }
1055
1056 /* make a copy of G incase R==G */
1057 tG = wc_ecc_new_point();
1058 if (tG == NULL)
1059 err = MEMORY_E;
1060
1061 /* tG = G and convert to montgomery */
1062 if (err == MP_OKAY) {
1063 if (mp_cmp_d(&mu, 1) == MP_EQ) {
1064 err = mp_copy(G->x, tG->x);
1065 if (err == MP_OKAY)
1066 err = mp_copy(G->y, tG->y);
1067 if (err == MP_OKAY)
1068 err = mp_copy(G->z, tG->z);
1069 } else {
1070 err = mp_mulmod(G->x, &mu, modulus, tG->x);
1071 if (err == MP_OKAY)
1072 err = mp_mulmod(G->y, &mu, modulus, tG->y);
1073 if (err == MP_OKAY)
1074 err = mp_mulmod(G->z, &mu, modulus, tG->z);
1075 }
1076 }
1077 mp_clear(&mu);
1078
1079 /* calc the M tab, which holds kG for k==8..15 */
1080 /* M[0] == 8G */
1081 if (err == MP_OKAY)
1082 err = ecc_projective_dbl_point(tG, M[0], modulus, &mp);
1083 if (err == MP_OKAY)
1084 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1085 if (err == MP_OKAY)
1086 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1087
1088 /* now find (8+k)G for k=1..7 */
1089 if (err == MP_OKAY)
1090 for (j = 9; j < 16; j++) {
1091 err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp);
1092 if (err != MP_OKAY) break;
1093 }
1094
1095 /* setup sliding window */
1096 if (err == MP_OKAY) {
1097 mode = 0;
1098 bitcnt = 1;
1099 buf = 0;
1100 digidx = get_digit_count(k) - 1;
1101 bitcpy = bitbuf = 0;
1102 first = 1;
1103
1104 /* perform ops */
1105 for (;;) {
1106 /* grab next digit as required */
1107 if (--bitcnt == 0) {
1108 if (digidx == -1) {
1109 break;
1110 }
1111 buf = get_digit(k, digidx);
1112 bitcnt = (int) DIGIT_BIT;
1113 --digidx;
1114 }
1115
1116 /* grab the next msb from the ltiplicand */
1117 i = (int)(buf >> (DIGIT_BIT - 1)) & 1;
1118 buf <<= 1;
1119
1120 /* skip leading zero bits */
1121 if (mode == 0 && i == 0)
1122 continue;
1123
1124 /* if the bit is zero and mode == 1 then we double */
1125 if (mode == 1 && i == 0) {
1126 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1127 if (err != MP_OKAY) break;
1128 continue;
1129 }
1130
1131 /* else we add it to the window */
1132 bitbuf |= (i << (WINSIZE - ++bitcpy));
1133 mode = 2;
1134
1135 if (bitcpy == WINSIZE) {
1136 /* if this is the first window we do a simple copy */
1137 if (first == 1) {
1138 /* R = kG [k = first window] */
1139 err = mp_copy(M[bitbuf-8]->x, R->x);
1140 if (err != MP_OKAY) break;
1141
1142 err = mp_copy(M[bitbuf-8]->y, R->y);
1143 if (err != MP_OKAY) break;
1144
1145 err = mp_copy(M[bitbuf-8]->z, R->z);
1146 first = 0;
1147 } else {
1148 /* normal window */
1149 /* ok window is filled so double as required and add */
1150 /* double first */
1151 for (j = 0; j < WINSIZE; j++) {
1152 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1153 if (err != MP_OKAY) break;
1154 }
1155 if (err != MP_OKAY) break; /* out of first for(;;) */
1156
1157 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */
1158 err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp);
1159 }
1160 if (err != MP_OKAY) break;
1161 /* empty window and reset */
1162 bitcpy = bitbuf = 0;
1163 mode = 1;
1164 }
1165 }
1166 }
1167
1168 /* if bits remain then double/add */
1169 if (err == MP_OKAY) {
1170 if (mode == 2 && bitcpy > 0) {
1171 /* double then add */
1172 for (j = 0; j < bitcpy; j++) {
1173 /* only double if we have had at least one add first */
1174 if (first == 0) {
1175 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1176 if (err != MP_OKAY) break;
1177 }
1178
1179 bitbuf <<= 1;
1180 if ((bitbuf & (1 << WINSIZE)) != 0) {
1181 if (first == 1) {
1182 /* first add, so copy */
1183 err = mp_copy(tG->x, R->x);
1184 if (err != MP_OKAY) break;
1185
1186 err = mp_copy(tG->y, R->y);
1187 if (err != MP_OKAY) break;
1188
1189 err = mp_copy(tG->z, R->z);
1190 if (err != MP_OKAY) break;
1191 first = 0;
1192 } else {
1193 /* then add */
1194 err = ecc_projective_add_point(R, tG, R, modulus, &mp);
1195 if (err != MP_OKAY) break;
1196 }
1197 }
1198 }
1199 }
1200 }
1201
1202 /* map R back from projective space */
1203 if (err == MP_OKAY && map)
1204 err = ecc_map(R, modulus, &mp);
1205
1206 mp_clear(&mu);
1207 wc_ecc_del_point(tG);
1208 for (i = 0; i < 8; i++) {
1209 wc_ecc_del_point(M[i]);
1210 }
1211 return err;
1212}
1213
1214#undef WINSIZE
1215
1216#else /* ECC_TIMING_RESISTANT */
1217
1218/**
1219 Perform a point multiplication (timing resistant)
1220 k The scalar to multiply by
1221 G The base point
1222 R [out] Destination for kG
1223 modulus The modulus of the field the ECC curve is in
1224 map Boolean whether to map back to affine or not
1225 (1==map, 0 == leave in projective)
1226 return MP_OKAY on success
1227*/
1228#ifdef FP_ECC
1229static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R,
1230 mp_int* modulus, int map)
1231#else
1232int wc_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
1233 int map)
1234#endif
1235{
1236 ecc_point *tG, *M[3];
1237 int i, j, err;
1238 mp_int mu;
1239 mp_digit mp;
1240 mp_digit buf;
1241 int bitcnt = 0, mode = 0, digidx = 0;
1242
1243 if (k == NULL || G == NULL || R == NULL || modulus == NULL)
1244 return ECC_BAD_ARG_E;
1245
1246 /* init montgomery reduction */
1247 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
1248 return err;
1249 }
1250 if ((err = mp_init(&mu)) != MP_OKAY) {
1251 return err;
1252 }
1253 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
1254 mp_clear(&mu);
1255 return err;
1256 }
1257
1258 /* alloc ram for window temps */
1259 for (i = 0; i < 3; i++) {
1260 M[i] = wc_ecc_new_point();
1261 if (M[i] == NULL) {
1262 for (j = 0; j < i; j++) {
1263 wc_ecc_del_point(M[j]);
1264 }
1265 mp_clear(&mu);
1266 return MEMORY_E;
1267 }
1268 }
1269
1270 /* make a copy of G incase R==G */
1271 tG = wc_ecc_new_point();
1272 if (tG == NULL)
1273 err = MEMORY_E;
1274
1275 /* tG = G and convert to montgomery */
1276 if (err == MP_OKAY) {
1277 err = mp_mulmod(G->x, &mu, modulus, tG->x);
1278 if (err == MP_OKAY)
1279 err = mp_mulmod(G->y, &mu, modulus, tG->y);
1280 if (err == MP_OKAY)
1281 err = mp_mulmod(G->z, &mu, modulus, tG->z);
1282 }
1283 mp_clear(&mu);
1284
1285 /* calc the M tab */
1286 /* M[0] == G */
1287 if (err == MP_OKAY)
1288 err = mp_copy(tG->x, M[0]->x);
1289 if (err == MP_OKAY)
1290 err = mp_copy(tG->y, M[0]->y);
1291 if (err == MP_OKAY)
1292 err = mp_copy(tG->z, M[0]->z);
1293
1294 /* M[1] == 2G */
1295 if (err == MP_OKAY)
1296 err = ecc_projective_dbl_point(tG, M[1], modulus, &mp);
1297
1298 /* setup sliding window */
1299 mode = 0;
1300 bitcnt = 1;
1301 buf = 0;
1302 digidx = get_digit_count(k) - 1;
1303
1304 /* perform ops */
1305 if (err == MP_OKAY) {
1306 for (;;) {
1307 /* grab next digit as required */
1308 if (--bitcnt == 0) {
1309 if (digidx == -1) {
1310 break;
1311 }
1312 buf = get_digit(k, digidx);
1313 bitcnt = (int) DIGIT_BIT;
1314 --digidx;
1315 }
1316
1317 /* grab the next msb from the ltiplicand */
1318 i = (buf >> (DIGIT_BIT - 1)) & 1;
1319 buf <<= 1;
1320
1321 if (mode == 0 && i == 0) {
1322 /* dummy operations */
1323 if (err == MP_OKAY)
1324 err = ecc_projective_add_point(M[0], M[1], M[2], modulus,
1325 &mp);
1326 if (err == MP_OKAY)
1327 err = ecc_projective_dbl_point(M[1], M[2], modulus, &mp);
1328 if (err == MP_OKAY)
1329 continue;
1330 }
1331
1332 if (mode == 0 && i == 1) {
1333 mode = 1;
1334 /* dummy operations */
1335 if (err == MP_OKAY)
1336 err = ecc_projective_add_point(M[0], M[1], M[2], modulus,
1337 &mp);
1338 if (err == MP_OKAY)
1339 err = ecc_projective_dbl_point(M[1], M[2], modulus, &mp);
1340 if (err == MP_OKAY)
1341 continue;
1342 }
1343
1344 if (err == MP_OKAY)
1345 err = ecc_projective_add_point(M[0], M[1], M[i^1], modulus, &mp);
1346 if (err == MP_OKAY)
1347 err = ecc_projective_dbl_point(M[i], M[i], modulus, &mp);
1348 if (err != MP_OKAY)
1349 break;
1350 } /* end for */
1351 }
1352
1353 /* copy result out */
1354 if (err == MP_OKAY)
1355 err = mp_copy(M[0]->x, R->x);
1356 if (err == MP_OKAY)
1357 err = mp_copy(M[0]->y, R->y);
1358 if (err == MP_OKAY)
1359 err = mp_copy(M[0]->z, R->z);
1360
1361 /* map R back from projective space */
1362 if (err == MP_OKAY && map)
1363 err = ecc_map(R, modulus, &mp);
1364
1365 /* done */
1366 mp_clear(&mu);
1367 wc_ecc_del_point(tG);
1368 for (i = 0; i < 3; i++) {
1369 wc_ecc_del_point(M[i]);
1370 }
1371 return err;
1372}
1373
1374#endif /* ECC_TIMING_RESISTANT */
1375
1376
1377#ifdef ALT_ECC_SIZE
1378
1379static void alt_fp_init(fp_int* a)
1380{
1381 a->size = FP_SIZE_ECC;
1382 fp_zero(a);
1383}
1384
1385#endif /* ALT_ECC_SIZE */
1386
1387
1388/**
1389 Allocate a new ECC point
1390 return A newly allocated point or NULL on error
1391*/
1392ecc_point* wc_ecc_new_point(void)
1393{
1394 ecc_point* p;
1395
1396 p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_ECC);
1397 if (p == NULL) {
1398 return NULL;
1399 }
1400 XMEMSET(p, 0, sizeof(ecc_point));
1401
1402#ifndef USE_FAST_MATH
1403 p->x->dp = NULL;
1404 p->y->dp = NULL;
1405 p->z->dp = NULL;
1406#endif
1407
1408#ifndef ALT_ECC_SIZE
1409 if (mp_init_multi(p->x, p->y, p->z, NULL, NULL, NULL) != MP_OKAY) {
1410 XFREE(p, 0, DYNAMIC_TYPE_ECC);
1411 return NULL;
1412 }
1413#else
1414 p->x = (mp_int*)&p->xyz[0];
1415 p->y = (mp_int*)&p->xyz[1];
1416 p->z = (mp_int*)&p->xyz[2];
1417 alt_fp_init(p->x);
1418 alt_fp_init(p->y);
1419 alt_fp_init(p->z);
1420#endif
1421
1422 return p;
1423}
1424
1425/** Free an ECC point from memory
1426 p The point to free
1427*/
1428void wc_ecc_del_point(ecc_point* p)
1429{
1430 /* prevents free'ing null arguments */
1431 if (p != NULL) {
1432 mp_clear(p->x);
1433 mp_clear(p->y);
1434 mp_clear(p->z);
1435 XFREE(p, 0, DYNAMIC_TYPE_ECC);
1436 }
1437}
1438
1439/** Copy the value of a point to an other one
1440 p The point to copy
1441 r The created point
1442*/
1443int wc_ecc_copy_point(ecc_point* p, ecc_point *r)
1444{
1445 int ret;
1446
1447 /* prevents null arguments */
1448 if (p == NULL || r == NULL)
1449 return ECC_BAD_ARG_E;
1450
1451 ret = mp_copy(p->x, r->x);
1452 if (ret != MP_OKAY)
1453 return ret;
1454 ret = mp_copy(p->y, r->y);
1455 if (ret != MP_OKAY)
1456 return ret;
1457 ret = mp_copy(p->z, r->z);
1458 if (ret != MP_OKAY)
1459 return ret;
1460
1461 return MP_OKAY;
1462}
1463
1464/** Compare the value of a point with an other one
1465 a The point to compare
1466 b The othe point to compare
1467
1468 return MP_EQ if equal, MP_LT/MP_GT if not, < 0 in case of error
1469 */
1470int wc_ecc_cmp_point(ecc_point* a, ecc_point *b)
1471{
1472 int ret;
1473
1474 /* prevents null arguments */
1475 if (a == NULL || b == NULL)
1476 return BAD_FUNC_ARG;
1477
1478 ret = mp_cmp(a->x, b->x);
1479 if (ret != MP_EQ)
1480 return ret;
1481 ret = mp_cmp(a->y, b->y);
1482 if (ret != MP_EQ)
1483 return ret;
1484 ret = mp_cmp(a->z, b->z);
1485 if (ret != MP_EQ)
1486 return ret;
1487
1488 return MP_EQ;
1489}
1490
1491/** Returns whether an ECC idx is valid or not
1492 n The idx number to check
1493 return 1 if valid, 0 if not
1494*/
1495int wc_ecc_is_valid_idx(int n)
1496{
1497 int x;
1498
1499 for (x = 0; ecc_sets[x].size != 0; x++)
1500 ;
1501 /* -1 is a valid index --- indicating that the domain params
1502 were supplied by the user */
1503 if ((n >= -1) && (n < x)) {
1504 return 1;
1505 }
1506 return 0;
1507}
1508
1509
1510/**
1511 Create an ECC shared secret between two keys
1512 private_key The private ECC key
1513 public_key The public key
1514 out [out] Destination of the shared secret
1515 Conforms to EC-DH from ANSI X9.63
1516 outlen [in/out] The max size and resulting size of the shared secret
1517 return MP_OKAY if successful
1518*/
1519int wc_ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out,
1520 word32* outlen)
1521{
1522 word32 x = 0;
1523 ecc_point* result;
1524 mp_int prime;
1525 int err;
1526
1527 if (private_key == NULL || public_key == NULL || out == NULL ||
1528 outlen == NULL)
1529 return BAD_FUNC_ARG;
1530
1531 /* type valid? */
1532 if (private_key->type != ECC_PRIVATEKEY) {
1533 return ECC_BAD_ARG_E;
1534 }
1535
1536 if (wc_ecc_is_valid_idx(private_key->idx) == 0 ||
1537 wc_ecc_is_valid_idx(public_key->idx) == 0)
1538 return ECC_BAD_ARG_E;
1539
1540 if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0)
1541 return ECC_BAD_ARG_E;
1542
1543 /* make new point */
1544 result = wc_ecc_new_point();
1545 if (result == NULL) {
1546 return MEMORY_E;
1547 }
1548
1549 if ((err = mp_init(&prime)) != MP_OKAY) {
1550 wc_ecc_del_point(result);
1551 return err;
1552 }
1553
1554 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
1555
1556 if (err == MP_OKAY)
1557 err = wc_ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1);
1558
1559 if (err == MP_OKAY) {
1560 x = mp_unsigned_bin_size(&prime);
1561 if (*outlen < x)
1562 err = BUFFER_E;
1563 }
1564
1565 if (err == MP_OKAY) {
1566 XMEMSET(out, 0, x);
1567 err = mp_to_unsigned_bin(result->x,out + (x -
1568 mp_unsigned_bin_size(result->x)));
1569 *outlen = x;
1570 }
1571
1572 mp_clear(&prime);
1573 wc_ecc_del_point(result);
1574
1575 return err;
1576}
1577
1578/**
1579 Create an ECC shared secret between two keys
1580 private_key The private ECC key
1581 point The point to use (public key)
1582 out [out] Destination of the shared secret
1583 Conforms to EC-DH from ANSI X9.63
1584 outlen [in/out] The max size and resulting size of the shared secret
1585 return MP_OKAY if successful
1586 */
1587int wc_ecc_shared_secret_ssh(ecc_key* private_key, ecc_point* point,
1588 byte* out, word32 *outlen)
1589{
1590 word32 x = 0;
1591 ecc_point* result;
1592 mp_int prime;
1593 int err;
1594
1595 if (private_key == NULL || point == NULL || out == NULL || outlen == NULL)
1596 return BAD_FUNC_ARG;
1597
1598 /* type valid? */
1599 if (private_key->type != ECC_PRIVATEKEY) {
1600 return ECC_BAD_ARG_E;
1601 }
1602
1603 if (wc_ecc_is_valid_idx(private_key->idx) == 0)
1604 return ECC_BAD_ARG_E;
1605
1606 /* make new point */
1607 result = wc_ecc_new_point();
1608 if (result == NULL) {
1609 return MEMORY_E;
1610 }
1611
1612 if ((err = mp_init(&prime)) != MP_OKAY) {
1613 wc_ecc_del_point(result);
1614 return err;
1615 }
1616
1617 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
1618
1619 if (err == MP_OKAY)
1620 err = wc_ecc_mulmod(&private_key->k, point, result, &prime, 1);
1621
1622 if (err == MP_OKAY) {
1623 x = mp_unsigned_bin_size(&prime);
1624 if (*outlen < x)
1625 err = BUFFER_E;
1626 }
1627
1628 if (err == MP_OKAY) {
1629 XMEMSET(out, 0, x);
1630 err = mp_to_unsigned_bin(result->x,out +
1631 (x - mp_unsigned_bin_size(result->x)));
1632 *outlen = x;
1633 }
1634
1635 mp_clear(&prime);
1636 wc_ecc_del_point(result);
1637
1638 return err;
1639}
1640
1641
1642/* return 1 if point is at infinity, 0 if not, < 0 on error */
1643int wc_ecc_point_is_at_infinity(ecc_point* p)
1644{
1645 if (p == NULL)
1646 return BAD_FUNC_ARG;
1647
1648 if (get_digit_count(p->x) == 0 && get_digit_count(p->y) == 0)
1649 return 1;
1650
1651 return 0;
1652}
1653
1654
1655static int wc_ecc_make_key_ex(WC_RNG* rng, ecc_key* key, const ecc_set_type* dp)
1656{
1657 int err;
1658 ecc_point* base;
1659 mp_int prime;
1660 mp_int order;
1661#ifdef WOLFSSL_SMALL_STACK
1662 byte* buf;
1663#else
1664 byte buf[ECC_MAXSIZE_GEN];
1665#endif
1666 int keysize;
1667 int po_init = 0; /* prime order Init flag for clear */
1668
1669 if (key == NULL || rng == NULL || dp == NULL)
1670 return ECC_BAD_ARG_E;
1671
1672#ifdef WOLFSSL_SMALL_STACK
1673 buf = (byte*)XMALLOC(ECC_MAXSIZE_GEN, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1674 if (buf == NULL)
1675 return MEMORY_E;
1676#endif
1677
1678 key->idx = -1;
1679 key->dp = dp;
1680
1681 /*generate 8 extra bytes to mitigate bias from the modulo operation below*/
1682 /*see section A.1.2 in 'Suite B Implementor's Guide to FIPS 186-3 (ECDSA)'*/
1683 keysize = dp->size + 8;
1684
1685 /* allocate ram */
1686 base = NULL;
1687
1688 /* make up random string */
1689 err = wc_RNG_GenerateBlock(rng, buf, keysize);
1690
1691 /* setup the key variables */
1692 if (err == 0) {
1693#ifndef ALT_ECC_SIZE
1694 err = mp_init_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z,
1695 &key->k, &prime, &order);
1696#else
1697 key->pubkey.x = (mp_int*)&key->pubkey.xyz[0];
1698 key->pubkey.y = (mp_int*)&key->pubkey.xyz[1];
1699 key->pubkey.z = (mp_int*)&key->pubkey.xyz[2];
1700 alt_fp_init(key->pubkey.x);
1701 alt_fp_init(key->pubkey.y);
1702 alt_fp_init(key->pubkey.z);
1703 err = mp_init_multi(&key->k, &prime, &order, NULL, NULL, NULL);
1704#endif
1705 if (err != MP_OKAY)
1706 err = MEMORY_E;
1707 else
1708 po_init = 1;
1709 }
1710
1711 if (err == MP_OKAY) {
1712 base = wc_ecc_new_point();
1713 if (base == NULL)
1714 err = MEMORY_E;
1715 }
1716
1717 /* read in the specs for this key */
1718 if (err == MP_OKAY)
1719 err = mp_read_radix(&prime, (char *)key->dp->prime, 16);
1720 if (err == MP_OKAY)
1721 err = mp_read_radix(&order, (char *)key->dp->order, 16);
1722 if (err == MP_OKAY)
1723 err = mp_read_radix(base->x, (char *)key->dp->Gx, 16);
1724 if (err == MP_OKAY)
1725 err = mp_read_radix(base->y, (char *)key->dp->Gy, 16);
1726
1727 if (err == MP_OKAY)
1728 mp_set(base->z, 1);
1729 if (err == MP_OKAY)
1730 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize);
1731
1732 /* quick sanity check to make sure we're not dealing with a 0 key */
1733 if (err == MP_OKAY) {
1734 if (MP_YES == mp_iszero(&key->k))
1735 err = MP_ZERO_E;
1736 }
1737
1738 /* the key should be smaller than the order of base point */
1739 if (err == MP_OKAY) {
1740 if (mp_cmp(&key->k, &order) != MP_LT)
1741 err = mp_mod(&key->k, &order, &key->k);
1742 }
1743 /* make the public key */
1744 if (err == MP_OKAY)
1745 err = wc_ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1);
1746
1747#ifdef WOLFSSL_VALIDATE_ECC_KEYGEN
1748 /* validate the public key, order * pubkey = point at infinity */
1749 if (err == MP_OKAY)
1750 err = ecc_check_pubkey_order(key, &prime, &order);
1751#endif /* WOLFSSL_VALIDATE_KEYGEN */
1752
1753 if (err == MP_OKAY)
1754 key->type = ECC_PRIVATEKEY;
1755
1756 if (err != MP_OKAY) {
1757 /* clean up */
1758 mp_clear(key->pubkey.x);
1759 mp_clear(key->pubkey.y);
1760 mp_clear(key->pubkey.z);
1761 mp_clear(&key->k);
1762 }
1763 wc_ecc_del_point(base);
1764 if (po_init) {
1765 mp_clear(&prime);
1766 mp_clear(&order);
1767 }
1768
1769 ForceZero(buf, ECC_MAXSIZE);
1770#ifdef WOLFSSL_SMALL_STACK
1771 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1772#endif
1773
1774 return err;
1775}
1776
1777/**
1778 Make a new ECC key
1779 rng An active RNG state
1780 keysize The keysize for the new key (in octets from 20 to 65 bytes)
1781 key [out] Destination of the newly created key
1782 return MP_OKAY if successful,
1783 upon error all allocated memory will be freed
1784 */
1785int wc_ecc_make_key(WC_RNG* rng, int keysize, ecc_key* key)
1786{
1787 int x, err;
1788
1789 if (key == NULL || rng == NULL)
1790 return ECC_BAD_ARG_E;
1791
1792 /* find key size */
1793 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++)
1794 ;
1795 keysize = ecc_sets[x].size;
1796
1797 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) {
1798 return BAD_FUNC_ARG;
1799 }
1800 err = wc_ecc_make_key_ex(rng, key, &ecc_sets[x]);
1801 key->idx = x;
1802
1803 return err;
1804}
1805
1806/* Setup dynamic pointers is using normal math for proper freeing */
1807int wc_ecc_init(ecc_key* key)
1808{
1809 (void)key;
1810
1811#ifndef USE_FAST_MATH
1812 key->pubkey.x->dp = NULL;
1813 key->pubkey.y->dp = NULL;
1814 key->pubkey.z->dp = NULL;
1815
1816 key->k.dp = NULL;
1817#endif
1818
1819#ifdef ALT_ECC_SIZE
1820 if (mp_init(&key->k) != MP_OKAY)
1821 return MEMORY_E;
1822
1823 key->pubkey.x = (mp_int*)&key->pubkey.xyz[0];
1824 key->pubkey.y = (mp_int*)&key->pubkey.xyz[1];
1825 key->pubkey.z = (mp_int*)&key->pubkey.xyz[2];
1826 alt_fp_init(key->pubkey.x);
1827 alt_fp_init(key->pubkey.y);
1828 alt_fp_init(key->pubkey.z);
1829#endif
1830
1831 return MP_OKAY;
1832}
1833
1834
1835/**
1836 Sign a message digest
1837 in The message digest to sign
1838 inlen The length of the digest
1839 out [out] The destination for the signature
1840 outlen [in/out] The max size and resulting size of the signature
1841 key A private ECC key
1842 return MP_OKAY if successful
1843 */
1844int wc_ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen,
1845 WC_RNG* rng, ecc_key* key)
1846{
1847 mp_int r;
1848 mp_int s;
1849 int err;
1850
1851 if (in == NULL || out == NULL || outlen == NULL ||
1852 key == NULL || rng == NULL)
1853 return ECC_BAD_ARG_E;
1854
1855 if ((err = mp_init_multi(&r, &s, NULL, NULL, NULL, NULL)) != MP_OKAY) {
1856 return err;
1857 }
1858
1859 err = wc_ecc_sign_hash_ex(in, inlen, rng, key, &r, &s);
1860 if (err == MP_OKAY)
1861 err = StoreECC_DSA_Sig(out, outlen, &r, &s);
1862
1863 mp_clear(&r);
1864 mp_clear(&s);
1865
1866 return err;
1867}
1868
1869/**
1870 Sign a message digest
1871 in The message digest to sign
1872 inlen The length of the digest
1873 out [out] The destination for the signature
1874 outlen [in/out] The max size and resulting size of the signature
1875 key A private ECC key
1876 r [out] The destination for r component of the signature
1877 s [out] The destination for s component of the signature
1878 return MP_OKAY if successful
1879*/
1880int wc_ecc_sign_hash_ex(const byte* in, word32 inlen, WC_RNG* rng,
1881 ecc_key* key, mp_int *r, mp_int *s)
1882{
1883 mp_int e;
1884 mp_int p;
1885 int err;
1886
1887 if (in == NULL || r == NULL || s == NULL || key == NULL || rng == NULL)
1888 return ECC_BAD_ARG_E;
1889
1890 /* is this a private key? */
1891 if (key->type != ECC_PRIVATEKEY) {
1892 return ECC_BAD_ARG_E;
1893 }
1894
1895 /* is the IDX valid ? */
1896 if (wc_ecc_is_valid_idx(key->idx) != 1) {
1897 return ECC_BAD_ARG_E;
1898 }
1899
1900 /* get the hash and load it as a bignum into 'e' */
1901 /* init the bignums */
1902 if ((err = mp_init_multi(&p, &e, NULL, NULL, NULL, NULL)) != MP_OKAY) {
1903 return err;
1904 }
1905 err = mp_read_radix(&p, (char *)key->dp->order, 16);
1906
1907 if (err == MP_OKAY) {
1908 /* we may need to truncate if hash is longer than key size */
1909 word32 orderBits = mp_count_bits(&p);
1910
1911 /* truncate down to byte size, may be all that's needed */
1912 if ( (WOLFSSL_BIT_SIZE * inlen) > orderBits)
1913 inlen = (orderBits + WOLFSSL_BIT_SIZE - 1)/WOLFSSL_BIT_SIZE;
1914 err = mp_read_unsigned_bin(&e, (byte*)in, inlen);
1915
1916 /* may still need bit truncation too */
1917 if (err == MP_OKAY && (WOLFSSL_BIT_SIZE * inlen) > orderBits)
1918 mp_rshb(&e, WOLFSSL_BIT_SIZE - (orderBits & 0x7));
1919 }
1920
1921 /* make up a key and export the public copy */
1922 if (err == MP_OKAY) {
1923 int loop_check = 0;
1924 ecc_key pubkey;
1925 if (wc_ecc_init(&pubkey) == MP_OKAY) {
1926 for (;;) {
1927 if (++loop_check > 64) {
1928 err = RNG_FAILURE_E;
1929 break;
1930 }
1931 err = wc_ecc_make_key_ex(rng, &pubkey, key->dp);
1932 if (err != MP_OKAY) break;
1933
1934 /* find r = x1 mod n */
1935 err = mp_mod(pubkey.pubkey.x, &p, r);
1936 if (err != MP_OKAY) break;
1937
1938 if (mp_iszero(r) == MP_YES) {
1939 mp_clear(pubkey.pubkey.x);
1940 mp_clear(pubkey.pubkey.y);
1941 mp_clear(pubkey.pubkey.z);
1942 mp_clear(&pubkey.k);
1943 }
1944 else {
1945 /* find s = (e + xr)/k */
1946 err = mp_invmod(&pubkey.k, &p, &pubkey.k);
1947 if (err != MP_OKAY) break;
1948
1949 err = mp_mulmod(&key->k, r, &p, s); /* s = xr */
1950 if (err != MP_OKAY) break;
1951
1952 err = mp_add(&e, s, s); /* s = e + xr */
1953 if (err != MP_OKAY) break;
1954
1955 err = mp_mod(s, &p, s); /* s = e + xr */
1956 if (err != MP_OKAY) break;
1957
1958 err = mp_mulmod(s, &pubkey.k, &p, s); /* s = (e + xr)/k */
1959 if (err != MP_OKAY) break;
1960
1961 if (mp_iszero(s) == MP_NO)
1962 break;
1963 }
1964 }
1965 wc_ecc_free(&pubkey);
1966 }
1967 }
1968
1969 mp_clear(&p);
1970 mp_clear(&e);
1971
1972 return err;
1973}
1974
1975
1976/**
1977 Free an ECC key from memory
1978 key The key you wish to free
1979*/
1980void wc_ecc_free(ecc_key* key)
1981{
1982 if (key == NULL)
1983 return;
1984
1985 mp_clear(key->pubkey.x);
1986 mp_clear(key->pubkey.y);
1987 mp_clear(key->pubkey.z);
1988 mp_clear(&key->k);
1989}
1990
1991
1992#ifdef USE_FAST_MATH
1993 #define GEN_MEM_ERR FP_MEM
1994#else
1995 #define GEN_MEM_ERR MP_MEM
1996#endif
1997
1998#ifdef ECC_SHAMIR
1999
2000/** Computes kA*A + kB*B = C using Shamir's Trick
2001 A First point to multiply
2002 kA What to multiple A by
2003 B Second point to multiply
2004 kB What to multiple B by
2005 C [out] Destination point (can overlap with A or B)
2006 modulus Modulus for curve
2007 return MP_OKAY on success
2008*/
2009#ifdef FP_ECC
2010static int normal_ecc_mul2add(ecc_point* A, mp_int* kA,
2011 ecc_point* B, mp_int* kB,
2012 ecc_point* C, mp_int* modulus)
2013#else
2014static int ecc_mul2add(ecc_point* A, mp_int* kA,
2015 ecc_point* B, mp_int* kB,
2016 ecc_point* C, mp_int* modulus)
2017#endif
2018{
2019 ecc_point* precomp[16];
2020 unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
2021 unsigned char* tA;
2022 unsigned char* tB;
2023 int err = MP_OKAY, first;
2024 int muInit = 0;
2025 int tableInit = 0;
2026 mp_digit mp;
2027 mp_int mu;
2028
2029 /* argchks */
2030 if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL ||
2031 modulus == NULL)
2032 return ECC_BAD_ARG_E;
2033
2034
2035 /* allocate memory */
2036 tA = (unsigned char*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2037 if (tA == NULL) {
2038 return GEN_MEM_ERR;
2039 }
2040 tB = (unsigned char*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2041 if (tB == NULL) {
2042 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2043 return GEN_MEM_ERR;
2044 }
2045 XMEMSET(tA, 0, ECC_BUFSIZE);
2046 XMEMSET(tB, 0, ECC_BUFSIZE);
2047
2048 /* get sizes */
2049 lenA = mp_unsigned_bin_size(kA);
2050 lenB = mp_unsigned_bin_size(kB);
2051 len = MAX(lenA, lenB);
2052
2053 /* sanity check */
2054 if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) {
2055 err = BAD_FUNC_ARG;
2056 }
2057
2058 if (err == MP_OKAY) {
2059 /* extract and justify kA */
2060 err = mp_to_unsigned_bin(kA, (len - lenA) + tA);
2061
2062 /* extract and justify kB */
2063 if (err == MP_OKAY)
2064 err = mp_to_unsigned_bin(kB, (len - lenB) + tB);
2065
2066 /* allocate the table */
2067 if (err == MP_OKAY) {
2068 for (x = 0; x < 16; x++) {
2069 precomp[x] = wc_ecc_new_point();
2070 if (precomp[x] == NULL) {
2071 for (y = 0; y < x; ++y) {
2072 wc_ecc_del_point(precomp[y]);
2073 }
2074 err = GEN_MEM_ERR;
2075 break;
2076 }
2077 }
2078 }
2079 }
2080
2081 if (err == MP_OKAY)
2082 tableInit = 1;
2083
2084 if (err == MP_OKAY)
2085 /* init montgomery reduction */
2086 err = mp_montgomery_setup(modulus, &mp);
2087
2088 if (err == MP_OKAY)
2089 err = mp_init(&mu);
2090 if (err == MP_OKAY)
2091 muInit = 1;
2092
2093 if (err == MP_OKAY)
2094 err = mp_montgomery_calc_normalization(&mu, modulus);
2095
2096 if (err == MP_OKAY)
2097 /* copy ones ... */
2098 err = mp_mulmod(A->x, &mu, modulus, precomp[1]->x);
2099
2100 if (err == MP_OKAY)
2101 err = mp_mulmod(A->y, &mu, modulus, precomp[1]->y);
2102 if (err == MP_OKAY)
2103 err = mp_mulmod(A->z, &mu, modulus, precomp[1]->z);
2104
2105 if (err == MP_OKAY)
2106 err = mp_mulmod(B->x, &mu, modulus, precomp[1<<2]->x);
2107 if (err == MP_OKAY)
2108 err = mp_mulmod(B->y, &mu, modulus, precomp[1<<2]->y);
2109 if (err == MP_OKAY)
2110 err = mp_mulmod(B->z, &mu, modulus, precomp[1<<2]->z);
2111
2112 if (err == MP_OKAY)
2113 /* precomp [i,0](A + B) table */
2114 err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp);
2115
2116 if (err == MP_OKAY)
2117 err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3],
2118 modulus, &mp);
2119 if (err == MP_OKAY)
2120 /* precomp [0,i](A + B) table */
2121 err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp);
2122
2123 if (err == MP_OKAY)
2124 err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2],
2125 modulus, &mp);
2126
2127 if (err == MP_OKAY) {
2128 /* precomp [i,j](A + B) table (i != 0, j != 0) */
2129 for (x = 1; x < 4; x++) {
2130 for (y = 1; y < 4; y++) {
2131 if (err == MP_OKAY)
2132 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)],
2133 precomp[x+(y<<2)], modulus, &mp);
2134 }
2135 }
2136 }
2137
2138 if (err == MP_OKAY) {
2139 nibble = 3;
2140 first = 1;
2141 bitbufA = tA[0];
2142 bitbufB = tB[0];
2143
2144 /* for every byte of the multiplicands */
2145 for (x = -1;; ) {
2146 /* grab a nibble */
2147 if (++nibble == 4) {
2148 ++x; if (x == len) break;
2149 bitbufA = tA[x];
2150 bitbufB = tB[x];
2151 nibble = 0;
2152 }
2153
2154 /* extract two bits from both, shift/update */
2155 nA = (bitbufA >> 6) & 0x03;
2156 nB = (bitbufB >> 6) & 0x03;
2157 bitbufA = (bitbufA << 2) & 0xFF;
2158 bitbufB = (bitbufB << 2) & 0xFF;
2159
2160 /* if both zero, if first, continue */
2161 if ((nA == 0) && (nB == 0) && (first == 1)) {
2162 continue;
2163 }
2164
2165 /* double twice, only if this isn't the first */
2166 if (first == 0) {
2167 /* double twice */
2168 if (err == MP_OKAY)
2169 err = ecc_projective_dbl_point(C, C, modulus, &mp);
2170 if (err == MP_OKAY)
2171 err = ecc_projective_dbl_point(C, C, modulus, &mp);
2172 else
2173 break;
2174 }
2175
2176 /* if not both zero */
2177 if ((nA != 0) || (nB != 0)) {
2178 if (first == 1) {
2179 /* if first, copy from table */
2180 first = 0;
2181 if (err == MP_OKAY)
2182 err = mp_copy(precomp[nA + (nB<<2)]->x, C->x);
2183
2184 if (err == MP_OKAY)
2185 err = mp_copy(precomp[nA + (nB<<2)]->y, C->y);
2186
2187 if (err == MP_OKAY)
2188 err = mp_copy(precomp[nA + (nB<<2)]->z, C->z);
2189 else
2190 break;
2191 } else {
2192 /* if not first, add from table */
2193 if (err == MP_OKAY)
2194 err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C,
2195 modulus, &mp);
2196 else
2197 break;
2198 }
2199 }
2200 }
2201 }
2202
2203 if (err == MP_OKAY)
2204 /* reduce to affine */
2205 err = ecc_map(C, modulus, &mp);
2206
2207 /* clean up */
2208 if (muInit)
2209 mp_clear(&mu);
2210
2211 if (tableInit) {
2212 for (x = 0; x < 16; x++) {
2213 wc_ecc_del_point(precomp[x]);
2214 }
2215 }
2216 ForceZero(tA, ECC_BUFSIZE);
2217 ForceZero(tB, ECC_BUFSIZE);
2218 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2219 XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2220
2221 return err;
2222}
2223
2224
2225#endif /* ECC_SHAMIR */
2226
2227
2228
2229/* verify
2230 *
2231 * w = s^-1 mod n
2232 * u1 = xw
2233 * u2 = rw
2234 * X = u1*G + u2*Q
2235 * v = X_x1 mod n
2236 * accept if v == r
2237 */
2238
2239/**
2240 Verify an ECC signature
2241 sig The signature to verify
2242 siglen The length of the signature (octets)
2243 hash The hash (message digest) that was signed
2244 hashlen The length of the hash (octets)
2245 stat Result of signature, 1==valid, 0==invalid
2246 key The corresponding public ECC key
2247 return MP_OKAY if successful (even if the signature is not valid)
2248 */
2249int wc_ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash,
2250 word32 hashlen, int* stat, ecc_key* key)
2251{
2252 mp_int r;
2253 mp_int s;
2254 int err;
2255
2256 if (sig == NULL || hash == NULL || stat == NULL || key == NULL)
2257 return ECC_BAD_ARG_E;
2258
2259 /* default to invalid signature */
2260 *stat = 0;
2261
2262 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s.
2263 * If either of those don't allocate correctly, none of
2264 * the rest of this function will execute, and everything
2265 * gets cleaned up at the end. */
2266 XMEMSET(&r, 0, sizeof(r));
2267 XMEMSET(&s, 0, sizeof(s));
2268
2269 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s);
2270
2271 if (err == MP_OKAY)
2272 err = wc_ecc_verify_hash_ex(&r, &s, hash, hashlen, stat, key);
2273
2274 mp_clear(&r);
2275 mp_clear(&s);
2276
2277 return err;
2278}
2279
2280/**
2281 Verify an ECC signature
2282 r The signature R component to verify
2283 s The signature S component to verify
2284 hash The hash (message digest) that was signed
2285 hashlen The length of the hash (octets)
2286 stat Result of signature, 1==valid, 0==invalid
2287 key The corresponding public ECC key
2288 return MP_OKAY if successful (even if the signature is not valid)
2289*/
2290int wc_ecc_verify_hash_ex(mp_int *r, mp_int *s, const byte* hash,
2291 word32 hashlen, int* stat, ecc_key* key)
2292{
2293 ecc_point *mG, *mQ;
2294 mp_int v;
2295 mp_int w;
2296 mp_int u1;
2297 mp_int u2;
2298 mp_int e;
2299 mp_int p;
2300 mp_int m;
2301 int err;
2302
2303 if (r == NULL || s == NULL || hash == NULL || stat == NULL || key == NULL)
2304 return ECC_BAD_ARG_E;
2305
2306 /* default to invalid signature */
2307 *stat = 0;
2308
2309 /* is the IDX valid ? */
2310 if (wc_ecc_is_valid_idx(key->idx) != 1) {
2311 return ECC_BAD_ARG_E;
2312 }
2313
2314 /* allocate ints */
2315 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) {
2316 return MEMORY_E;
2317 }
2318
2319 if ((err = mp_init(&m)) != MP_OKAY) {
2320 mp_clear(&v);
2321 mp_clear(&w);
2322 mp_clear(&u1);
2323 mp_clear(&u2);
2324 mp_clear(&p);
2325 mp_clear(&e);
2326 return MEMORY_E;
2327 }
2328
2329 /* allocate points */
2330 mG = wc_ecc_new_point();
2331 mQ = wc_ecc_new_point();
2332 if (mQ == NULL || mG == NULL)
2333 err = MEMORY_E;
2334
2335 /* get the order */
2336 if (err == MP_OKAY)
2337 err = mp_read_radix(&p, (char *)key->dp->order, 16);
2338
2339 /* get the modulus */
2340 if (err == MP_OKAY)
2341 err = mp_read_radix(&m, (char *)key->dp->prime, 16);
2342
2343 /* check for zero */
2344 if (err == MP_OKAY) {
2345 if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, &p) != MP_LT ||
2346 mp_cmp(s, &p) != MP_LT)
2347 err = MP_ZERO_E;
2348 }
2349 /* read hash */
2350 if (err == MP_OKAY) {
2351 /* we may need to truncate if hash is longer than key size */
2352 unsigned int orderBits = mp_count_bits(&p);
2353
2354 /* truncate down to byte size, may be all that's needed */
2355 if ( (WOLFSSL_BIT_SIZE * hashlen) > orderBits)
2356 hashlen = (orderBits + WOLFSSL_BIT_SIZE - 1)/WOLFSSL_BIT_SIZE;
2357 err = mp_read_unsigned_bin(&e, hash, hashlen);
2358
2359 /* may still need bit truncation too */
2360 if (err == MP_OKAY && (WOLFSSL_BIT_SIZE * hashlen) > orderBits)
2361 mp_rshb(&e, WOLFSSL_BIT_SIZE - (orderBits & 0x7));
2362 }
2363
2364 /* w = s^-1 mod n */
2365 if (err == MP_OKAY)
2366 err = mp_invmod(s, &p, &w);
2367
2368 /* u1 = ew */
2369 if (err == MP_OKAY)
2370 err = mp_mulmod(&e, &w, &p, &u1);
2371
2372 /* u2 = rw */
2373 if (err == MP_OKAY)
2374 err = mp_mulmod(r, &w, &p, &u2);
2375
2376 /* find mG and mQ */
2377 if (err == MP_OKAY)
2378 err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16);
2379
2380 if (err == MP_OKAY)
2381 err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16);
2382 if (err == MP_OKAY)
2383 mp_set(mG->z, 1);
2384
2385 if (err == MP_OKAY)
2386 err = mp_copy(key->pubkey.x, mQ->x);
2387 if (err == MP_OKAY)
2388 err = mp_copy(key->pubkey.y, mQ->y);
2389 if (err == MP_OKAY)
2390 err = mp_copy(key->pubkey.z, mQ->z);
2391
2392#ifndef ECC_SHAMIR
2393 {
2394 mp_digit mp;
2395
2396 /* compute u1*mG + u2*mQ = mG */
2397 if (err == MP_OKAY)
2398 err = wc_ecc_mulmod(&u1, mG, mG, &m, 0);
2399 if (err == MP_OKAY)
2400 err = wc_ecc_mulmod(&u2, mQ, mQ, &m, 0);
2401
2402 /* find the montgomery mp */
2403 if (err == MP_OKAY)
2404 err = mp_montgomery_setup(&m, &mp);
2405
2406 /* add them */
2407 if (err == MP_OKAY)
2408 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp);
2409
2410 /* reduce */
2411 if (err == MP_OKAY)
2412 err = ecc_map(mG, &m, &mp);
2413 }
2414#else
2415 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */
2416 if (err == MP_OKAY)
2417 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m);
2418#endif /* ECC_SHAMIR */
2419
2420 /* v = X_x1 mod n */
2421 if (err == MP_OKAY)
2422 err = mp_mod(mG->x, &p, &v);
2423
2424 /* does v == r */
2425 if (err == MP_OKAY) {
2426 if (mp_cmp(&v, r) == MP_EQ)
2427 *stat = 1;
2428 }
2429
2430 wc_ecc_del_point(mG);
2431 wc_ecc_del_point(mQ);
2432
2433 mp_clear(&v);
2434 mp_clear(&w);
2435 mp_clear(&u1);
2436 mp_clear(&u2);
2437 mp_clear(&p);
2438 mp_clear(&e);
2439 mp_clear(&m);
2440
2441 return err;
2442}
2443
2444/* import point from der */
2445int wc_ecc_import_point_der(byte* in, word32 inLen, const int curve_idx,
2446 ecc_point* point)
2447{
2448 int err = 0;
2449 int compressed = 0;
2450
2451 if (in == NULL || point == NULL || (curve_idx < 0) ||
2452 (wc_ecc_is_valid_idx(curve_idx) == 0))
2453 return ECC_BAD_ARG_E;
2454
2455 /* must be odd */
2456 if ((inLen & 1) == 0) {
2457 return ECC_BAD_ARG_E;
2458 }
2459
2460 /* init point */
2461#ifdef ALT_ECC_SIZE
2462 point->x = (mp_int*)&point->xyz[0];
2463 point->y = (mp_int*)&point->xyz[1];
2464 point->z = (mp_int*)&point->xyz[2];
2465 alt_fp_init(point->x);
2466 alt_fp_init(point->y);
2467 alt_fp_init(point->z);
2468#else
2469 err = mp_init_multi(point->x, point->y, point->z, NULL, NULL, NULL);
2470#endif
2471 if (err != MP_OKAY)
2472 return MEMORY_E;
2473
2474 /* check for 4, 2, or 3 */
2475 if (in[0] != 0x04 && in[0] != 0x02 && in[0] != 0x03) {
2476 err = ASN_PARSE_E;
2477 }
2478
2479 if (in[0] == 0x02 || in[0] == 0x03) {
2480#ifdef HAVE_COMP_KEY
2481 compressed = 1;
2482#else
2483 err = NOT_COMPILED_IN;
2484#endif
2485 }
2486
2487 /* read data */
2488 if (err == MP_OKAY)
2489 err = mp_read_unsigned_bin(point->x, (byte*)in+1, (inLen-1)>>1);
2490
2491#ifdef HAVE_COMP_KEY
2492 if (err == MP_OKAY && compressed == 1) { /* build y */
2493 mp_int t1, t2, prime, a, b;
2494
2495 if (mp_init_multi(&t1, &t2, &prime, &a, &b, NULL) != MP_OKAY)
2496 err = MEMORY_E;
2497
2498 /* load prime */
2499 if (err == MP_OKAY)
2500 err = mp_read_radix(&prime, (char *)ecc_sets[curve_idx].prime, 16);
2501
2502 /* load a */
2503 if (err == MP_OKAY)
2504 err = mp_read_radix(&a, (char *)ecc_sets[curve_idx].Af, 16);
2505
2506 /* load b */
2507 if (err == MP_OKAY)
2508 err = mp_read_radix(&b, (char *)ecc_sets[curve_idx].Bf, 16);
2509
2510 /* compute x^3 */
2511 if (err == MP_OKAY)
2512 err = mp_sqr(point->x, &t1);
2513
2514 if (err == MP_OKAY)
2515 err = mp_mulmod(&t1, point->x, &prime, &t1);
2516
2517 /* compute x^3 + a*x */
2518 if (err == MP_OKAY)
2519 err = mp_mulmod(&a, point->x, &prime, &t2);
2520
2521 if (err == MP_OKAY)
2522 err = mp_add(&t1, &t2, &t1);
2523
2524 /* compute x^3 + a*x + b */
2525 if (err == MP_OKAY)
2526 err = mp_add(&t1, &b, &t1);
2527
2528 /* compute sqrt(x^3 + a*x + b) */
2529 if (err == MP_OKAY)
2530 err = mp_sqrtmod_prime(&t1, &prime, &t2);
2531
2532 /* adjust y */
2533 if (err == MP_OKAY) {
2534 if ((mp_isodd(&t2) && in[0] == 0x03) ||
2535 (!mp_isodd(&t2) && in[0] == 0x02)) {
2536 err = mp_mod(&t2, &prime, point->y);
2537 }
2538 else {
2539 err = mp_submod(&prime, &t2, &prime, point->y);
2540 }
2541 }
2542
2543 mp_clear(&a);
2544 mp_clear(&b);
2545 mp_clear(&prime);
2546 mp_clear(&t2);
2547 mp_clear(&t1);
2548 }
2549#endif
2550
2551 if (err == MP_OKAY && compressed == 0)
2552 err = mp_read_unsigned_bin(point->y,
2553 (byte*)in+1+((inLen-1)>>1), (inLen-1)>>1);
2554 if (err == MP_OKAY)
2555 mp_set(point->z, 1);
2556
2557 if (err != MP_OKAY) {
2558 mp_clear(point->x);
2559 mp_clear(point->y);
2560 mp_clear(point->z);
2561 }
2562
2563 return err;
2564}
2565
2566/* export point to der */
2567int wc_ecc_export_point_der(const int curve_idx, ecc_point* point, byte* out,
2568 word32* outLen)
2569{
2570#ifdef WOLFSSL_SMALL_STACK
2571 byte* buf;
2572#else
2573 byte buf[ECC_BUFSIZE];
2574#endif
2575 word32 numlen;
2576 int ret = MP_OKAY;
2577
2578 if ((curve_idx < 0) || (wc_ecc_is_valid_idx(curve_idx) == 0))
2579 return ECC_BAD_ARG_E;
2580
2581 /* return length needed only */
2582 if (point != NULL && out == NULL && outLen != NULL) {
2583 numlen = ecc_sets[curve_idx].size;
2584 *outLen = 1 + 2*numlen;
2585 return LENGTH_ONLY_E;
2586 }
2587
2588 if (point == NULL || out == NULL || outLen == NULL)
2589 return ECC_BAD_ARG_E;
2590
2591 numlen = ecc_sets[curve_idx].size;
2592
2593 if (*outLen < (1 + 2*numlen)) {
2594 *outLen = 1 + 2*numlen;
2595 return BUFFER_E;
2596 }
2597
2598 /* store byte 0x04 */
2599 out[0] = 0x04;
2600
2601#ifdef WOLFSSL_SMALL_STACK
2602 buf = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2603 if (buf == NULL)
2604 return MEMORY_E;
2605#endif
2606
2607 /* pad and store x */
2608 XMEMSET(buf, 0, ECC_BUFSIZE);
2609 ret = mp_to_unsigned_bin(point->x, buf +
2610 (numlen - mp_unsigned_bin_size(point->x)));
2611 if (ret != MP_OKAY)
2612 goto done;
2613 XMEMCPY(out+1, buf, numlen);
2614
2615 /* pad and store y */
2616 XMEMSET(buf, 0, ECC_BUFSIZE);
2617 ret = mp_to_unsigned_bin(point->y, buf +
2618 (numlen - mp_unsigned_bin_size(point->y)));
2619 if (ret != MP_OKAY)
2620 goto done;
2621 XMEMCPY(out+1+numlen, buf, numlen);
2622
2623 *outLen = 1 + 2*numlen;
2624
2625done:
2626#ifdef WOLFSSL_SMALL_STACK
2627 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2628#endif
2629
2630 return ret;
2631}
2632
2633
2634/* export public ECC key in ANSI X9.63 format */
2635int wc_ecc_export_x963(ecc_key* key, byte* out, word32* outLen)
2636{
2637#ifdef WOLFSSL_SMALL_STACK
2638 byte* buf;
2639#else
2640 byte buf[ECC_BUFSIZE];
2641#endif
2642 word32 numlen;
2643 int ret = MP_OKAY;
2644
2645 /* return length needed only */
2646 if (key != NULL && out == NULL && outLen != NULL) {
2647 numlen = key->dp->size;
2648 *outLen = 1 + 2*numlen;
2649 return LENGTH_ONLY_E;
2650 }
2651
2652 if (key == NULL || out == NULL || outLen == NULL)
2653 return ECC_BAD_ARG_E;
2654
2655 if (wc_ecc_is_valid_idx(key->idx) == 0) {
2656 return ECC_BAD_ARG_E;
2657 }
2658 numlen = key->dp->size;
2659
2660 if (*outLen < (1 + 2*numlen)) {
2661 *outLen = 1 + 2*numlen;
2662 return BUFFER_E;
2663 }
2664
2665 /* store byte 0x04 */
2666 out[0] = 0x04;
2667
2668#ifdef WOLFSSL_SMALL_STACK
2669 buf = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2670 if (buf == NULL)
2671 return MEMORY_E;
2672#endif
2673
2674 /* pad and store x */
2675 XMEMSET(buf, 0, ECC_BUFSIZE);
2676 ret = mp_to_unsigned_bin(key->pubkey.x,
2677 buf + (numlen - mp_unsigned_bin_size(key->pubkey.x)));
2678 if (ret != MP_OKAY)
2679 goto done;
2680 XMEMCPY(out+1, buf, numlen);
2681
2682 /* pad and store y */
2683 XMEMSET(buf, 0, ECC_BUFSIZE);
2684 ret = mp_to_unsigned_bin(key->pubkey.y,
2685 buf + (numlen - mp_unsigned_bin_size(key->pubkey.y)));
2686 if (ret != MP_OKAY)
2687 goto done;
2688 XMEMCPY(out+1+numlen, buf, numlen);
2689
2690 *outLen = 1 + 2*numlen;
2691
2692done:
2693#ifdef WOLFSSL_SMALL_STACK
2694 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2695#endif
2696
2697 return ret;
2698}
2699
2700
2701/* export public ECC key in ANSI X9.63 format, extended with
2702 * compression option */
2703int wc_ecc_export_x963_ex(ecc_key* key, byte* out, word32* outLen,
2704 int compressed)
2705{
2706 if (compressed == 0)
2707 return wc_ecc_export_x963(key, out, outLen);
2708#ifdef HAVE_COMP_KEY
2709 else
2710 return wc_ecc_export_x963_compressed(key, out, outLen);
2711#endif
2712
2713 return NOT_COMPILED_IN;
2714}
2715
2716
2717/* is ec point on curve descriped by dp ? */
2718static int ecc_is_point(const ecc_set_type* dp, ecc_point* ecp, mp_int* prime)
2719{
2720 mp_int b, t1, t2;
2721 int err;
2722
2723 if ((err = mp_init_multi(&b, &t1, &t2, NULL, NULL, NULL)) != MP_OKAY) {
2724 return err;
2725 }
2726
2727 /* load b */
2728 err = mp_read_radix(&b, dp->Bf, 16);
2729
2730 /* compute y^2 */
2731 if (err == MP_OKAY)
2732 err = mp_sqr(ecp->y, &t1);
2733
2734 /* compute x^3 */
2735 if (err == MP_OKAY)
2736 err = mp_sqr(ecp->x, &t2);
2737 if (err == MP_OKAY)
2738 err = mp_mod(&t2, prime, &t2);
2739 if (err == MP_OKAY)
2740 err = mp_mul(ecp->x, &t2, &t2);
2741
2742 /* compute y^2 - x^3 */
2743 if (err == MP_OKAY)
2744 err = mp_sub(&t1, &t2, &t1);
2745
2746 /* compute y^2 - x^3 + 3x */
2747 if (err == MP_OKAY)
2748 err = mp_add(&t1, ecp->x, &t1);
2749 if (err == MP_OKAY)
2750 err = mp_add(&t1, ecp->x, &t1);
2751 if (err == MP_OKAY)
2752 err = mp_add(&t1, ecp->x, &t1);
2753 if (err == MP_OKAY)
2754 err = mp_mod(&t1, prime, &t1);
2755
2756 while (err == MP_OKAY && mp_cmp_d(&t1, 0) == MP_LT) {
2757 err = mp_add(&t1, prime, &t1);
2758 }
2759 while (err == MP_OKAY && mp_cmp(&t1, prime) != MP_LT) {
2760 err = mp_sub(&t1, prime, &t1);
2761 }
2762
2763 /* compare to b */
2764 if (err == MP_OKAY) {
2765 if (mp_cmp(&t1, &b) != MP_EQ) {
2766 err = MP_VAL;
2767 } else {
2768 err = MP_OKAY;
2769 }
2770 }
2771
2772 mp_clear(&b);
2773 mp_clear(&t1);
2774 mp_clear(&t2);
2775
2776 return err;
2777}
2778
2779
2780/* validate privkey * generator == pubkey, 0 on success */
2781static int ecc_check_privkey_gen(ecc_key* key, mp_int* prime)
2782{
2783 ecc_point* base = NULL;
2784 ecc_point* res = NULL;
2785 int err;
2786
2787 if (key == NULL)
2788 return BAD_FUNC_ARG;
2789
2790 base = wc_ecc_new_point();
2791 if (base == NULL)
2792 return MEMORY_E;
2793
2794 /* set up base generator */
2795 err = mp_read_radix(base->x, (char*)key->dp->Gx, 16);
2796 if (err == MP_OKAY)
2797 err = mp_read_radix(base->y, (char*)key->dp->Gy, 16);
2798 if (err == MP_OKAY)
2799 mp_set(base->z, 1);
2800
2801 if (err == MP_OKAY) {
2802 res = wc_ecc_new_point();
2803 if (res == NULL)
2804 err = MEMORY_E;
2805 else {
2806 err = wc_ecc_mulmod(&key->k, base, res, prime, 1);
2807 if (err == MP_OKAY) {
2808 /* compare result to public key */
2809 if (mp_cmp(res->x, key->pubkey.x) != MP_EQ ||
2810 mp_cmp(res->y, key->pubkey.y) != MP_EQ ||
2811 mp_cmp(res->z, key->pubkey.z) != MP_EQ) {
2812 /* didn't match */
2813 err = ECC_PRIV_KEY_E;
2814 }
2815 }
2816 }
2817 }
2818
2819 wc_ecc_del_point(res);
2820 wc_ecc_del_point(base);
2821
2822 return err;
2823}
2824
2825
2826#ifdef WOLFSSL_VALIDATE_ECC_IMPORT
2827
2828/* check privkey generator helper, creates prime needed */
2829static int ecc_check_privkey_gen_helper(ecc_key* key)
2830{
2831 mp_int prime;
2832 int err;
2833
2834 if (key == NULL)
2835 return BAD_FUNC_ARG;
2836
2837 err = mp_init(&prime);
2838 if (err != MP_OKAY)
2839 return err;
2840
2841 err = mp_read_radix(&prime, (char*)key->dp->prime, 16);
2842
2843 if (err == MP_OKAY);
2844 err = ecc_check_privkey_gen(key, &prime);
2845
2846 mp_clear(&prime);
2847
2848 return err;
2849}
2850
2851#endif /* WOLFSSL_VALIDATE_ECC_IMPORT */
2852
2853
2854/* validate order * pubkey = point at infinity, 0 on success */
2855static int ecc_check_pubkey_order(ecc_key* key, mp_int* prime, mp_int* order)
2856{
2857 ecc_point* inf = NULL;
2858 int err;
2859
2860 if (key == NULL)
2861 return BAD_FUNC_ARG;
2862
2863 inf = wc_ecc_new_point();
2864 if (inf == NULL)
2865 err = MEMORY_E;
2866 else {
2867 err = wc_ecc_mulmod(order, &key->pubkey, inf, prime, 1);
2868 if (err == MP_OKAY && !wc_ecc_point_is_at_infinity(inf))
2869 err = ECC_INF_E;
2870 }
2871
2872 wc_ecc_del_point(inf);
2873
2874 return err;
2875}
2876
2877
2878/* perform sanity checks on ec key validity, 0 on success */
2879int wc_ecc_check_key(ecc_key* key)
2880{
2881 mp_int prime; /* used by multiple calls so let's cache */
2882 mp_int order; /* other callers have, so let's gen here */
2883 int err;
2884
2885 if (key == NULL)
2886 return BAD_FUNC_ARG;
2887
2888 /* pubkey point cannot be at inifinity */
2889 if (wc_ecc_point_is_at_infinity(&key->pubkey))
2890 return ECC_INF_E;
2891
2892 err = mp_init_multi(&prime, &order, NULL, NULL, NULL, NULL);
2893 if (err != MP_OKAY)
2894 return err;
2895
2896 err = mp_read_radix(&prime, (char*)key->dp->prime, 16);
2897
2898 /* make sure point is actually on curve */
2899 if (err == MP_OKAY)
2900 err = ecc_is_point(key->dp, &key->pubkey, &prime);
2901
2902 if (err == MP_OKAY)
2903 err = mp_read_radix(&order, (char*)key->dp->order, 16);
2904
2905 /* pubkey * order must be at infinity */
2906 if (err == MP_OKAY)
2907 err = ecc_check_pubkey_order(key, &prime, &order);
2908
2909 /* private * base generator must equal pubkey */
2910 if (err == MP_OKAY && key->type == ECC_PRIVATEKEY)
2911 err = ecc_check_privkey_gen(key, &prime);
2912
2913 mp_clear(&order);
2914 mp_clear(&prime);
2915
2916 return err;
2917}
2918
2919
2920/* import public ECC key in ANSI X9.63 format */
2921int wc_ecc_import_x963(const byte* in, word32 inLen, ecc_key* key)
2922{
2923 int x, err;
2924 int compressed = 0;
2925
2926 if (in == NULL || key == NULL)
2927 return ECC_BAD_ARG_E;
2928
2929 /* must be odd */
2930 if ((inLen & 1) == 0) {
2931 return ECC_BAD_ARG_E;
2932 }
2933
2934 /* init key */
2935#ifdef ALT_ECC_SIZE
2936 key->pubkey.x = (mp_int*)&key->pubkey.xyz[0];
2937 key->pubkey.y = (mp_int*)&key->pubkey.xyz[1];
2938 key->pubkey.z = (mp_int*)&key->pubkey.xyz[2];
2939 alt_fp_init(key->pubkey.x);
2940 alt_fp_init(key->pubkey.y);
2941 alt_fp_init(key->pubkey.z);
2942 err = mp_init(&key->k);
2943#else
2944 err = mp_init_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, &key->k,
2945 NULL, NULL);
2946#endif
2947 if (err != MP_OKAY)
2948 return MEMORY_E;
2949
2950 /* check for 4, 2, or 3 */
2951 if (in[0] != 0x04 && in[0] != 0x02 && in[0] != 0x03) {
2952 err = ASN_PARSE_E;
2953 }
2954
2955 if (in[0] == 0x02 || in[0] == 0x03) {
2956#ifdef HAVE_COMP_KEY
2957 compressed = 1;
2958#else
2959 err = NOT_COMPILED_IN;
2960#endif
2961 }
2962
2963 if (err == MP_OKAY) {
2964 /* determine the idx */
2965
2966 if (compressed)
2967 inLen = (inLen-1)*2 + 1; /* used uncompressed len */
2968
2969 for (x = 0; ecc_sets[x].size != 0; x++) {
2970 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) {
2971 break;
2972 }
2973 }
2974 if (ecc_sets[x].size == 0) {
2975 err = ASN_PARSE_E;
2976 } else {
2977 /* set the idx */
2978 key->idx = x;
2979 key->dp = &ecc_sets[x];
2980 key->type = ECC_PUBLICKEY;
2981 }
2982 }
2983
2984 /* read data */
2985 if (err == MP_OKAY)
2986 err = mp_read_unsigned_bin(key->pubkey.x, (byte*)in+1, (inLen-1)>>1);
2987
2988#ifdef HAVE_COMP_KEY
2989 if (err == MP_OKAY && compressed == 1) { /* build y */
2990 mp_int t1, t2, prime, a, b;
2991
2992 if (mp_init_multi(&t1, &t2, &prime, &a, &b, NULL) != MP_OKAY)
2993 err = MEMORY_E;
2994
2995 /* load prime */
2996 if (err == MP_OKAY)
2997 err = mp_read_radix(&prime, (char *)key->dp->prime, 16);
2998
2999 /* load a */
3000 if (err == MP_OKAY)
3001 err = mp_read_radix(&a, (char *)key->dp->Af, 16);
3002
3003 /* load b */
3004 if (err == MP_OKAY)
3005 err = mp_read_radix(&b, (char *)key->dp->Bf, 16);
3006
3007 /* compute x^3 */
3008 if (err == MP_OKAY)
3009 err = mp_sqr(key->pubkey.x, &t1);
3010
3011 if (err == MP_OKAY)
3012 err = mp_mulmod(&t1, key->pubkey.x, &prime, &t1);
3013
3014 /* compute x^3 + a*x */
3015 if (err == MP_OKAY)
3016 err = mp_mulmod(&a, key->pubkey.x, &prime, &t2);
3017
3018 if (err == MP_OKAY)
3019 err = mp_add(&t1, &t2, &t1);
3020
3021 /* compute x^3 + a*x + b */
3022 if (err == MP_OKAY)
3023 err = mp_add(&t1, &b, &t1);
3024
3025 /* compute sqrt(x^3 + a*x + b) */
3026 if (err == MP_OKAY)
3027 err = mp_sqrtmod_prime(&t1, &prime, &t2);
3028
3029 /* adjust y */
3030 if (err == MP_OKAY) {
3031 if ((mp_isodd(&t2) && in[0] == 0x03) ||
3032 (!mp_isodd(&t2) && in[0] == 0x02)) {
3033 err = mp_mod(&t2, &prime, key->pubkey.y);
3034 }
3035 else {
3036 err = mp_submod(&prime, &t2, &prime, key->pubkey.y);
3037 }
3038 }
3039
3040 mp_clear(&a);
3041 mp_clear(&b);
3042 mp_clear(&prime);
3043 mp_clear(&t2);
3044 mp_clear(&t1);
3045 }
3046#endif
3047
3048 if (err == MP_OKAY && compressed == 0)
3049 err = mp_read_unsigned_bin(key->pubkey.y, (byte*)in+1+((inLen-1)>>1),
3050 (inLen-1)>>1);
3051 if (err == MP_OKAY)
3052 mp_set(key->pubkey.z, 1);
3053
3054#ifdef WOLFSSL_VALIDATE_ECC_IMPORT
3055 if (err == MP_OKAY)
3056 err = wc_ecc_check_key(key);
3057#endif
3058
3059 if (err != MP_OKAY) {
3060 mp_clear(key->pubkey.x);
3061 mp_clear(key->pubkey.y);
3062 mp_clear(key->pubkey.z);
3063 mp_clear(&key->k);
3064 }
3065
3066 return err;
3067}
3068
3069
3070/* export ecc private key only raw, outLen is in/out size
3071 return MP_OKAY on success */
3072int wc_ecc_export_private_only(ecc_key* key, byte* out, word32* outLen)
3073{
3074 word32 numlen;
3075
3076 if (key == NULL || out == NULL || outLen == NULL)
3077 return ECC_BAD_ARG_E;
3078
3079 if (wc_ecc_is_valid_idx(key->idx) == 0) {
3080 return ECC_BAD_ARG_E;
3081 }
3082 numlen = key->dp->size;
3083
3084 if (*outLen < numlen) {
3085 *outLen = numlen;
3086 return BUFFER_E;
3087 }
3088 *outLen = numlen;
3089 XMEMSET(out, 0, *outLen);
3090 return mp_to_unsigned_bin(&key->k, out + (numlen -
3091 mp_unsigned_bin_size(&key->k)));
3092}
3093
3094
3095/* ecc private key import, public key in ANSI X9.63 format, private raw */
3096int wc_ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub,
3097 word32 pubSz, ecc_key* key)
3098{
3099 int ret = wc_ecc_import_x963(pub, pubSz, key);
3100 if (ret != 0)
3101 return ret;
3102
3103 key->type = ECC_PRIVATEKEY;
3104
3105 ret = mp_read_unsigned_bin(&key->k, priv, privSz);
3106
3107#ifdef WOLFSSL_VALIDATE_ECC_IMPORT
3108 if (ret == MP_OKAY)
3109 ret = ecc_check_privkey_gen_helper(key);
3110#endif
3111
3112 return ret;
3113}
3114
3115/**
3116 Convert ECC R,S to signature
3117 r R component of signature
3118 s S component of signature
3119 out DER-encoded ECDSA signature
3120 outlen [in/out] output buffer size, output signature size
3121 return MP_OKAY on success
3122*/
3123int wc_ecc_rs_to_sig(const char* r, const char* s, byte* out, word32* outlen)
3124{
3125 int err;
3126 mp_int rtmp;
3127 mp_int stmp;
3128
3129 if (r == NULL || s == NULL || out == NULL || outlen == NULL)
3130 return ECC_BAD_ARG_E;
3131
3132 err = mp_init_multi(&rtmp, &stmp, NULL, NULL, NULL, NULL);
3133 if (err != MP_OKAY)
3134 return err;
3135
3136 err = mp_read_radix(&rtmp, r, 16);
3137 if (err == MP_OKAY)
3138 err = mp_read_radix(&stmp, s, 16);
3139
3140 /* convert mp_ints to ECDSA sig, initializes rtmp and stmp internally */
3141 if (err == MP_OKAY)
3142 err = StoreECC_DSA_Sig(out, outlen, &rtmp, &stmp);
3143
3144 if (err == MP_OKAY) {
3145 if (mp_iszero(&rtmp) || mp_iszero(&stmp))
3146 err = MP_ZERO_E;
3147 }
3148
3149 mp_clear(&rtmp);
3150 mp_clear(&stmp);
3151
3152 return err;
3153}
3154
3155/**
3156 Import raw ECC key
3157 key The destination ecc_key structure
3158 qx x component of base point, as ASCII hex string
3159 qy y component of base point, as ASCII hex string
3160 d private key, as ASCII hex string
3161 curveName ECC curve name, from ecc_sets[]
3162 return MP_OKAY on success
3163*/
3164int wc_ecc_import_raw(ecc_key* key, const char* qx, const char* qy,
3165 const char* d, const char* curveName)
3166{
3167 int err, x;
3168
3169 if (key == NULL || qx == NULL || qy == NULL || d == NULL ||
3170 curveName == NULL)
3171 return ECC_BAD_ARG_E;
3172
3173 /* init key */
3174#ifdef ALT_ECC_SIZE
3175 key->pubkey.x = (mp_int*)&key->pubkey.xyz[0];
3176 key->pubkey.y = (mp_int*)&key->pubkey.xyz[1];
3177 key->pubkey.z = (mp_int*)&key->pubkey.xyz[2];
3178 alt_fp_init(key->pubkey.x);
3179 alt_fp_init(key->pubkey.y);
3180 alt_fp_init(key->pubkey.z);
3181 err = mp_init(&key->k);
3182#else
3183 err = mp_init_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, &key->k,
3184 NULL, NULL);
3185#endif
3186 if (err != MP_OKAY)
3187 return MEMORY_E;
3188
3189 /* read Qx */
3190 if (err == MP_OKAY)
3191 err = mp_read_radix(key->pubkey.x, qx, 16);
3192
3193 /* read Qy */
3194 if (err == MP_OKAY)
3195 err = mp_read_radix(key->pubkey.y, qy, 16);
3196
3197 if (err == MP_OKAY)
3198 mp_set(key->pubkey.z, 1);
3199
3200 /* read and set the curve */
3201 if (err == MP_OKAY) {
3202 for (x = 0; ecc_sets[x].size != 0; x++) {
3203 if (XSTRNCMP(ecc_sets[x].name, curveName,
3204 XSTRLEN(curveName)) == 0) {
3205 break;
3206 }
3207 }
3208 if (ecc_sets[x].size == 0) {
3209 err = ASN_PARSE_E;
3210 } else {
3211 /* set the curve */
3212 key->idx = x;
3213 key->dp = &ecc_sets[x];
3214 key->type = ECC_PUBLICKEY;
3215 }
3216 }
3217
3218 /* import private key */
3219 if (err == MP_OKAY) {
3220 key->type = ECC_PRIVATEKEY;
3221 err = mp_read_radix(&key->k, d, 16);
3222 }
3223
3224#ifdef WOLFSSL_VALIDATE_ECC_IMPORT
3225 if (err == MP_OKAY)
3226 err = wc_ecc_check_key(key);
3227#endif
3228
3229 if (err != MP_OKAY) {
3230 mp_clear(key->pubkey.x);
3231 mp_clear(key->pubkey.y);
3232 mp_clear(key->pubkey.z);
3233 mp_clear(&key->k);
3234 }
3235
3236 return err;
3237}
3238
3239
3240/* key size in octets */
3241int wc_ecc_size(ecc_key* key)
3242{
3243 if (key == NULL) return 0;
3244
3245 return key->dp->size;
3246}
3247
3248
3249/* worst case estimate, check actual return from wc_ecc_sign_hash for actual
3250 value of signature size in octets */
3251int wc_ecc_sig_size(ecc_key* key)
3252{
3253 int sz = wc_ecc_size(key);
3254 if (sz <= 0)
3255 return sz;
3256
3257 return sz * 2 + SIG_HEADER_SZ + 4; /* (4) worst case estimate */
3258}
3259
3260
3261#ifdef FP_ECC
3262
3263/* fixed point ECC cache */
3264/* number of entries in the cache */
3265#ifndef FP_ENTRIES
3266 #define FP_ENTRIES 16
3267#endif
3268
3269/* number of bits in LUT */
3270#ifndef FP_LUT
3271 #define FP_LUT 8U
3272#endif
3273
3274#ifdef ECC_SHAMIR
3275 /* Sharmir requires a bigger LUT, TAO */
3276 #if (FP_LUT > 12) || (FP_LUT < 4)
3277 #error FP_LUT must be between 4 and 12 inclusively
3278 #endif
3279#else
3280 #if (FP_LUT > 12) || (FP_LUT < 2)
3281 #error FP_LUT must be between 2 and 12 inclusively
3282 #endif
3283#endif
3284
3285
3286/** Our FP cache */
3287typedef struct {
3288 ecc_point* g; /* cached COPY of base point */
3289 ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */
3290 mp_int mu; /* copy of the montgomery constant */
3291 int lru_count; /* amount of times this entry has been used */
3292 int lock; /* flag to indicate cache eviction */
3293 /* permitted (0) or not (1) */
3294} fp_cache_t;
3295
3296/* if HAVE_THREAD_LS this cache is per thread, no locking needed */
3297static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES];
3298
3299#ifndef HAVE_THREAD_LS
3300 static volatile int initMutex = 0; /* prevent multiple mutex inits */
3301 static wolfSSL_Mutex ecc_fp_lock;
3302#endif /* HAVE_THREAD_LS */
3303
3304/* simple table to help direct the generation of the LUT */
3305static const struct {
3306 int ham, terma, termb;
3307} lut_orders[] = {
3308 { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 },
3309 { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 },
3310 { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 },
3311 { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 },
3312 { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 },
3313 { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 },
3314 { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 },
3315 { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 },
3316#if FP_LUT > 6
3317 { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 },
3318 { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 },
3319 { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 },
3320 { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 },
3321 { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 },
3322 { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 },
3323 { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 },
3324 { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 },
3325#if FP_LUT > 7
3326 { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 },
3327 { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 },
3328 { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 },
3329 { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 },
3330 { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 },
3331 { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 },
3332 { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 },
3333 { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 },
3334 { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 },
3335 { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 },
3336 { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 },
3337 { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 },
3338 { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 },
3339 { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 },
3340 { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 },
3341 { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 },
3342#if FP_LUT > 8
3343 { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 },
3344 { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 },
3345 { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 },
3346 { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 },
3347 { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 },
3348 { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 },
3349 { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 },
3350 { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 },
3351 { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 },
3352 { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 },
3353 { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 },
3354 { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 },
3355 { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 },
3356 { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 },
3357 { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 },
3358 { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 },
3359 { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 },
3360 { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 },
3361 { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 },
3362 { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 },
3363 { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 },
3364 { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 },
3365 { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 },
3366 { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 },
3367 { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 },
3368 { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 },
3369 { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 },
3370 { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 },
3371 { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 },
3372 { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 },
3373 { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 },
3374 { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 },
3375#if FP_LUT > 9
3376 { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 },
3377 { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 },
3378 { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 },
3379 { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 },
3380 { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 },
3381 { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 },
3382 { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 },
3383 { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 },
3384 { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 },
3385 { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 },
3386 { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 },
3387 { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 },
3388 { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 },
3389 { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 },
3390 { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 },
3391 { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 },
3392 { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 },
3393 { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 },
3394 { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 },
3395 { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 },
3396 { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 },
3397 { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 },
3398 { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 },
3399 { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 },
3400 { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 },
3401 { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 },
3402 { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 },
3403 { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 },
3404 { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 },
3405 { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 },
3406 { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 },
3407 { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 },
3408 { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 },
3409 { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 },
3410 { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 },
3411 { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 },
3412 { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 },
3413 { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 },
3414 { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 },
3415 { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 },
3416 { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 },
3417 { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 },
3418 { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 },
3419 { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 },
3420 { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 },
3421 { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 },
3422 { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 },
3423 { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 },
3424 { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 },
3425 { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 },
3426 { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 },
3427 { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 },
3428 { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 },
3429 { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 },
3430 { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 },
3431 { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 },
3432 { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 },
3433 { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 },
3434 { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 },
3435 { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 },
3436 { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 },
3437 { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 },
3438 { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 },
3439 { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 },
3440#if FP_LUT > 10
3441 { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 },
3442 { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 },
3443 { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 },
3444 { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 },
3445 { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 },
3446 { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 },
3447 { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 },
3448 { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 },
3449 { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 },
3450 { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 },
3451 { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 },
3452 { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 },
3453 { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 },
3454 { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 },
3455 { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 },
3456 { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 },
3457 { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 },
3458 { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 },
3459 { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 },
3460 { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 },
3461 { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 },
3462 { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 },
3463 { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 },
3464 { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 },
3465 { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 },
3466 { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 },
3467 { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 },
3468 { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 },
3469 { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 },
3470 { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 },
3471 { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 },
3472 { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 },
3473 { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 },
3474 { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 },
3475 { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 },
3476 { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 },
3477 { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 },
3478 { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 },
3479 { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 },
3480 { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 },
3481 { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 },
3482 { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 },
3483 { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 },
3484 { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 },
3485 { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 },
3486 { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 },
3487 { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 },
3488 { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 },
3489 { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 },
3490 { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 },
3491 { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 },
3492 { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 },
3493 { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 },
3494 { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 },
3495 { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 },
3496 { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 },
3497 { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 },
3498 { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 },
3499 { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 },
3500 { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 },
3501 { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 },
3502 { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 },
3503 { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 },
3504 { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 },
3505 { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 },
3506 { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 },
3507 { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 },
3508 { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 },
3509 { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 },
3510 { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 },
3511 { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 },
3512 { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 },
3513 { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 },
3514 { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 },
3515 { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 },
3516 { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 },
3517 { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 },
3518 { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 },
3519 { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 },
3520 { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 },
3521 { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 },
3522 { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 },
3523 { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 },
3524 { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 },
3525 { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 },
3526 { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 },
3527 { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 },
3528 { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 },
3529 { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 },
3530 { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 },
3531 { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 },
3532 { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 },
3533 { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 },
3534 { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 },
3535 { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 },
3536 { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 },
3537 { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 },
3538 { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 },
3539 { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 },
3540 { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 },
3541 { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 },
3542 { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 },
3543 { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 },
3544 { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 },
3545 { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 },
3546 { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 },
3547 { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 },
3548 { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 },
3549 { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 },
3550 { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 },
3551 { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883