3 * Copyright (C) 2006-2014 wolfSSL Inc.
5 * This file is part of CyaSSL.
7 * CyaSSL 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.
12 * CyaSSL 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.
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
27 /* in case user set HAVE_ECC there */
28 #include <cyassl/ctaocrypt/settings.h>
32 #include <cyassl/ctaocrypt/ecc.h>
33 #include <cyassl/ctaocrypt/asn.h>
34 #include <cyassl/ctaocrypt/error-crypt.h>
36 #ifdef HAVE_ECC_ENCRYPT
37 #include <cyassl/ctaocrypt/hmac.h>
38 #include <cyassl/ctaocrypt/aes.h>
59 /* This holds the key settings. ***MUST*** be organized by size from
60 smallest to largest. */
62 const ecc_set_type ecc_sets[] = {
67 "DB7C2ABF62E35E668076BEAD208B",
68 "659EF8BA043916EEDE8911702B22",
69 "DB7C2ABF62E35E7628DFAC6561C5",
70 "09487239995A5EE76B55F9C2F098",
71 "A89CE5AF8724C0A23E0E0FF77500"
78 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
79 "E87579C11079F43DD824993C2CEE5ED3",
80 "FFFFFFFE0000000075A30D1B9038A115",
81 "161FF7528B899B2D0C28607CA52C5B86",
82 "CF5AC8395BAFEB13C02DA292DDED7A83",
89 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF",
90 "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45",
91 "0100000000000000000001F4C8F927AED3CA752257",
92 "4A96B5688EF573284664698968C38BB913CBFC82",
93 "23A628553168947D59DCC912042351377AC5FB32",
100 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF",
101 "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1",
102 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
103 "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012",
104 "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811",
111 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
112 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
113 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
114 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
115 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34",
122 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
123 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
124 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
125 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
126 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
133 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
134 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
135 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
136 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
137 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
144 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
145 "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
146 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
147 "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
148 "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
153 NULL, NULL, NULL, NULL, NULL, NULL
158 ecc_point* ecc_new_point(void);
159 void ecc_del_point(ecc_point* p);
160 int ecc_map(ecc_point*, mp_int*, mp_digit*);
161 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
162 mp_int* modulus, mp_digit* mp);
163 int ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus,
165 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
168 static int ecc_mul2add(ecc_point* A, mp_int* kA, ecc_point* B, mp_int* kB,
169 ecc_point* C, mp_int* modulus);
173 /* helper for either lib */
174 static int get_digit_count(mp_int* a)
182 /* helper for either lib */
183 static unsigned long get_digit(mp_int* a, int n)
188 return (n >= a->used || n < 0) ? 0 : a->dp[n];
192 #if defined(USE_FAST_MATH)
194 /* fast math accelerated version, but not for fp ecc yet */
200 R [out] The destination of the double
201 modulus The modulus of the field the ECC curve is in
202 mp The "b" value from montgomery_setup()
203 return MP_OKAY on success
205 int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R,
206 mp_int* modulus, mp_digit* mp)
208 fp_int t1, t2, x, y, z;
211 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
212 return ECC_BAD_ARG_E;
214 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
218 /* should we dbl instead? */
219 fp_sub(modulus, &Q->y, &t1);
220 if ( (fp_cmp(&P->x, &Q->x) == FP_EQ) &&
221 (get_digit_count(&Q->z) && fp_cmp(&P->z, &Q->z) == FP_EQ) &&
222 (fp_cmp(&P->y, &Q->y) == FP_EQ || fp_cmp(&P->y, &t1) == FP_EQ)) {
223 return ecc_projective_dbl_point(P, R, modulus, mp);
230 /* if Z is one then these are no-operations */
231 if (get_digit_count(&Q->z)) {
234 fp_montgomery_reduce(&t1, modulus, *mp);
237 fp_montgomery_reduce(&x, modulus, *mp);
239 fp_mul(&Q->z, &t1, &t1);
240 fp_montgomery_reduce(&t1, modulus, *mp);
243 fp_montgomery_reduce(&y, modulus, *mp);
248 fp_montgomery_reduce(&t1, modulus, *mp);
250 fp_mul(&Q->x, &t1, &t2);
251 fp_montgomery_reduce(&t2, modulus, *mp);
253 fp_mul(&z, &t1, &t1);
254 fp_montgomery_reduce(&t1, modulus, *mp);
256 fp_mul(&Q->y, &t1, &t1);
257 fp_montgomery_reduce(&t1, modulus, *mp);
261 if (fp_cmp_d(&y, 0) == FP_LT) {
262 fp_add(&y, modulus, &y);
265 fp_add(&t1, &t1, &t1);
266 if (fp_cmp(&t1, modulus) != FP_LT) {
267 fp_sub(&t1, modulus, &t1);
270 fp_add(&t1, &y, &t1);
271 if (fp_cmp(&t1, modulus) != FP_LT) {
272 fp_sub(&t1, modulus, &t1);
276 if (fp_cmp_d(&x, 0) == FP_LT) {
277 fp_add(&x, modulus, &x);
280 fp_add(&t2, &t2, &t2);
281 if (fp_cmp(&t2, modulus) != FP_LT) {
282 fp_sub(&t2, modulus, &t2);
285 fp_add(&t2, &x, &t2);
286 if (fp_cmp(&t2, modulus) != FP_LT) {
287 fp_sub(&t2, modulus, &t2);
291 if (get_digit_count(&Q->z)) {
293 fp_mul(&z, &Q->z, &z);
294 fp_montgomery_reduce(&z, modulus, *mp);
299 fp_montgomery_reduce(&z, modulus, *mp);
302 fp_mul(&t1, &x, &t1);
303 fp_montgomery_reduce(&t1, modulus, *mp);
306 fp_montgomery_reduce(&x, modulus, *mp);
308 fp_mul(&t2, &x, &t2);
309 fp_montgomery_reduce(&t2, modulus, *mp);
311 fp_mul(&t1, &x, &t1);
312 fp_montgomery_reduce(&t1, modulus, *mp);
316 fp_montgomery_reduce(&x, modulus, *mp);
319 if (fp_cmp_d(&x, 0) == FP_LT) {
320 fp_add(&x, modulus, &x);
324 fp_sub(&t2, &x, &t2);
325 if (fp_cmp_d(&t2, 0) == FP_LT) {
326 fp_add(&t2, modulus, &t2);
329 fp_sub(&t2, &x, &t2);
330 if (fp_cmp_d(&t2, 0) == FP_LT) {
331 fp_add(&t2, modulus, &t2);
334 fp_mul(&t2, &y, &t2);
335 fp_montgomery_reduce(&t2, modulus, *mp);
337 fp_sub(&t2, &t1, &y);
338 if (fp_cmp_d(&y, 0) == FP_LT) {
339 fp_add(&y, modulus, &y);
343 fp_add(&y, modulus, &y);
357 P The point to double
358 R [out] The destination of the double
359 modulus The modulus of the field the ECC curve is in
360 mp The "b" value from montgomery_setup()
361 return MP_OKAY on success
363 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
369 if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
370 return ECC_BAD_ARG_E;
373 fp_copy(&P->x, &R->x);
374 fp_copy(&P->y, &R->y);
375 fp_copy(&P->z, &R->z);
378 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
384 fp_montgomery_reduce(&t1, modulus, *mp);
386 fp_mul(&R->z, &R->y, &R->z);
387 fp_montgomery_reduce(&R->z, modulus, *mp);
389 fp_add(&R->z, &R->z, &R->z);
390 if (fp_cmp(&R->z, modulus) != FP_LT) {
391 fp_sub(&R->z, modulus, &R->z);
395 fp_sub(&R->x, &t1, &t2);
396 if (fp_cmp_d(&t2, 0) == FP_LT) {
397 fp_add(&t2, modulus, &t2);
400 fp_add(&t1, &R->x, &t1);
401 if (fp_cmp(&t1, modulus) != FP_LT) {
402 fp_sub(&t1, modulus, &t1);
405 fp_mul(&t1, &t2, &t2);
406 fp_montgomery_reduce(&t2, modulus, *mp);
408 fp_add(&t2, &t2, &t1);
409 if (fp_cmp(&t1, modulus) != FP_LT) {
410 fp_sub(&t1, modulus, &t1);
413 fp_add(&t1, &t2, &t1);
414 if (fp_cmp(&t1, modulus) != FP_LT) {
415 fp_sub(&t1, modulus, &t1);
419 fp_add(&R->y, &R->y, &R->y);
420 if (fp_cmp(&R->y, modulus) != FP_LT) {
421 fp_sub(&R->y, modulus, &R->y);
424 fp_sqr(&R->y, &R->y);
425 fp_montgomery_reduce(&R->y, modulus, *mp);
428 fp_montgomery_reduce(&t2, modulus, *mp);
431 fp_add(&t2, modulus, &t2);
435 fp_mul(&R->y, &R->x, &R->y);
436 fp_montgomery_reduce(&R->y, modulus, *mp);
440 fp_montgomery_reduce(&R->x, modulus, *mp);
442 fp_sub(&R->x, &R->y, &R->x);
443 if (fp_cmp_d(&R->x, 0) == FP_LT) {
444 fp_add(&R->x, modulus, &R->x);
447 fp_sub(&R->x, &R->y, &R->x);
448 if (fp_cmp_d(&R->x, 0) == FP_LT) {
449 fp_add(&R->x, modulus, &R->x);
453 fp_sub(&R->y, &R->x, &R->y);
454 if (fp_cmp_d(&R->y, 0) == FP_LT) {
455 fp_add(&R->y, modulus, &R->y);
458 fp_mul(&R->y, &t1, &R->y);
459 fp_montgomery_reduce(&R->y, modulus, *mp);
461 fp_sub(&R->y, &t2, &R->y);
462 if (fp_cmp_d(&R->y, 0) == FP_LT) {
463 fp_add(&R->y, modulus, &R->y);
469 #else /* USE_FAST_MATH */
475 R [out] The destination of the double
476 modulus The modulus of the field the ECC curve is in
477 mp The "b" value from montgomery_setup()
478 return MP_OKAY on success
480 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
481 mp_int* modulus, mp_digit* mp)
490 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
491 return ECC_BAD_ARG_E;
493 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
497 /* should we dbl instead? */
498 err = mp_sub(modulus, &Q->y, &t1);
500 if (err == MP_OKAY) {
501 if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) &&
502 (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) &&
503 (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) {
510 return ecc_projective_dbl_point(P, R, modulus, mp);
515 err = mp_copy(&P->x, &x);
517 err = mp_copy(&P->y, &y);
519 err = mp_copy(&P->z, &z);
521 /* if Z is one then these are no-operations */
522 if (err == MP_OKAY) {
523 if (get_digit_count(&Q->z)) {
525 err = mp_sqr(&Q->z, &t1);
527 err = mp_montgomery_reduce(&t1, modulus, *mp);
531 err = mp_mul(&t1, &x, &x);
533 err = mp_montgomery_reduce(&x, modulus, *mp);
537 err = mp_mul(&Q->z, &t1, &t1);
539 err = mp_montgomery_reduce(&t1, modulus, *mp);
543 err = mp_mul(&t1, &y, &y);
545 err = mp_montgomery_reduce(&y, modulus, *mp);
551 err = mp_sqr(&z, &t1);
553 err = mp_montgomery_reduce(&t1, modulus, *mp);
557 err = mp_mul(&Q->x, &t1, &t2);
559 err = mp_montgomery_reduce(&t2, modulus, *mp);
563 err = mp_mul(&z, &t1, &t1);
565 err = mp_montgomery_reduce(&t1, modulus, *mp);
569 err = mp_mul(&Q->y, &t1, &t1);
571 err = mp_montgomery_reduce(&t1, modulus, *mp);
575 err = mp_sub(&y, &t1, &y);
576 if (err == MP_OKAY) {
577 if (mp_cmp_d(&y, 0) == MP_LT)
578 err = mp_add(&y, modulus, &y);
582 err = mp_add(&t1, &t1, &t1);
583 if (err == MP_OKAY) {
584 if (mp_cmp(&t1, modulus) != MP_LT)
585 err = mp_sub(&t1, modulus, &t1);
589 err = mp_add(&t1, &y, &t1);
590 if (err == MP_OKAY) {
591 if (mp_cmp(&t1, modulus) != MP_LT)
592 err = mp_sub(&t1, modulus, &t1);
596 err = mp_sub(&x, &t2, &x);
597 if (err == MP_OKAY) {
598 if (mp_cmp_d(&x, 0) == MP_LT)
599 err = mp_add(&x, modulus, &x);
603 err = mp_add(&t2, &t2, &t2);
604 if (err == MP_OKAY) {
605 if (mp_cmp(&t2, modulus) != MP_LT)
606 err = mp_sub(&t2, modulus, &t2);
610 err = mp_add(&t2, &x, &t2);
611 if (err == MP_OKAY) {
612 if (mp_cmp(&t2, modulus) != MP_LT)
613 err = mp_sub(&t2, modulus, &t2);
616 if (err == MP_OKAY) {
617 if (get_digit_count(&Q->z)) {
619 err = mp_mul(&z, &Q->z, &z);
621 err = mp_montgomery_reduce(&z, modulus, *mp);
627 err = mp_mul(&z, &x, &z);
629 err = mp_montgomery_reduce(&z, modulus, *mp);
633 err = mp_mul(&t1, &x, &t1);
635 err = mp_montgomery_reduce(&t1, modulus, *mp);
639 err = mp_sqr(&x, &x);
641 err = mp_montgomery_reduce(&x, modulus, *mp);
645 err = mp_mul(&t2, &x, &t2);
647 err = mp_montgomery_reduce(&t2, modulus, *mp);
651 err = mp_mul(&t1, &x, &t1);
653 err = mp_montgomery_reduce(&t1, modulus, *mp);
657 err = mp_sqr(&y, &x);
659 err = mp_montgomery_reduce(&x, modulus, *mp);
663 err = mp_sub(&x, &t2, &x);
664 if (err == MP_OKAY) {
665 if (mp_cmp_d(&x, 0) == MP_LT)
666 err = mp_add(&x, modulus, &x);
670 err = mp_sub(&t2, &x, &t2);
671 if (err == MP_OKAY) {
672 if (mp_cmp_d(&t2, 0) == MP_LT)
673 err = mp_add(&t2, modulus, &t2);
677 err = mp_sub(&t2, &x, &t2);
678 if (err == MP_OKAY) {
679 if (mp_cmp_d(&t2, 0) == MP_LT)
680 err = mp_add(&t2, modulus, &t2);
684 err = mp_mul(&t2, &y, &t2);
686 err = mp_montgomery_reduce(&t2, modulus, *mp);
690 err = mp_sub(&t2, &t1, &y);
691 if (err == MP_OKAY) {
692 if (mp_cmp_d(&y, 0) == MP_LT)
693 err = mp_add(&y, modulus, &y);
696 if (err == MP_OKAY) {
698 err = mp_add(&y, modulus, &y);
701 err = mp_div_2(&y, &y);
704 err = mp_copy(&x, &R->x);
706 err = mp_copy(&y, &R->y);
708 err = mp_copy(&z, &R->z);
723 P The point to double
724 R [out] The destination of the double
725 modulus The modulus of the field the ECC curve is in
726 mp The "b" value from montgomery_setup()
727 return MP_OKAY on success
729 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
736 if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
737 return ECC_BAD_ARG_E;
739 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
744 err = mp_copy(&P->x, &R->x);
746 err = mp_copy(&P->y, &R->y);
748 err = mp_copy(&P->z, &R->z);
753 err = mp_sqr(&R->z, &t1);
755 err = mp_montgomery_reduce(&t1, modulus, *mp);
759 err = mp_mul(&R->z, &R->y, &R->z);
761 err = mp_montgomery_reduce(&R->z, modulus, *mp);
765 err = mp_add(&R->z, &R->z, &R->z);
766 if (err == MP_OKAY) {
767 if (mp_cmp(&R->z, modulus) != MP_LT)
768 err = mp_sub(&R->z, modulus, &R->z);
773 err = mp_sub(&R->x, &t1, &t2);
774 if (err == MP_OKAY) {
775 if (mp_cmp_d(&t2, 0) == MP_LT)
776 err = mp_add(&t2, modulus, &t2);
780 err = mp_add(&t1, &R->x, &t1);
781 if (err == MP_OKAY) {
782 if (mp_cmp(&t1, modulus) != MP_LT)
783 err = mp_sub(&t1, modulus, &t1);
787 err = mp_mul(&t1, &t2, &t2);
789 err = mp_montgomery_reduce(&t2, modulus, *mp);
793 err = mp_add(&t2, &t2, &t1);
794 if (err == MP_OKAY) {
795 if (mp_cmp(&t1, modulus) != MP_LT)
796 err = mp_sub(&t1, modulus, &t1);
800 err = mp_add(&t1, &t2, &t1);
801 if (err == MP_OKAY) {
802 if (mp_cmp(&t1, modulus) != MP_LT)
803 err = mp_sub(&t1, modulus, &t1);
807 err = mp_add(&R->y, &R->y, &R->y);
808 if (err == MP_OKAY) {
809 if (mp_cmp(&R->y, modulus) != MP_LT)
810 err = mp_sub(&R->y, modulus, &R->y);
814 err = mp_sqr(&R->y, &R->y);
816 err = mp_montgomery_reduce(&R->y, modulus, *mp);
820 err = mp_sqr(&R->y, &t2);
822 err = mp_montgomery_reduce(&t2, modulus, *mp);
825 if (err == MP_OKAY) {
827 err = mp_add(&t2, modulus, &t2);
830 err = mp_div_2(&t2, &t2);
834 err = mp_mul(&R->y, &R->x, &R->y);
836 err = mp_montgomery_reduce(&R->y, modulus, *mp);
840 err = mp_sqr(&t1, &R->x);
842 err = mp_montgomery_reduce(&R->x, modulus, *mp);
846 err = mp_sub(&R->x, &R->y, &R->x);
847 if (err == MP_OKAY) {
848 if (mp_cmp_d(&R->x, 0) == MP_LT)
849 err = mp_add(&R->x, modulus, &R->x);
853 err = mp_sub(&R->x, &R->y, &R->x);
854 if (err == MP_OKAY) {
855 if (mp_cmp_d(&R->x, 0) == MP_LT)
856 err = mp_add(&R->x, modulus, &R->x);
860 err = mp_sub(&R->y, &R->x, &R->y);
861 if (err == MP_OKAY) {
862 if (mp_cmp_d(&R->y, 0) == MP_LT)
863 err = mp_add(&R->y, modulus, &R->y);
867 err = mp_mul(&R->y, &t1, &R->y);
869 err = mp_montgomery_reduce(&R->y, modulus, *mp);
873 err = mp_sub(&R->y, &t2, &R->y);
874 if (err == MP_OKAY) {
875 if (mp_cmp_d(&R->y, 0) == MP_LT)
876 err = mp_add(&R->y, modulus, &R->y);
886 #endif /* USE_FAST_MATH */
889 Map a projective jacbobian point back to affine space
890 P [in/out] The point to map
891 modulus The modulus of the field the ECC curve is in
892 mp The "b" value from montgomery_setup()
893 return MP_OKAY on success
895 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp)
901 if (P == NULL || mp == NULL || modulus == NULL)
902 return ECC_BAD_ARG_E;
904 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
908 /* first map z back to normal */
909 err = mp_montgomery_reduce(&P->z, modulus, *mp);
913 err = mp_invmod(&P->z, modulus, &t1);
915 /* get 1/z^2 and 1/z^3 */
917 err = mp_sqr(&t1, &t2);
919 err = mp_mod(&t2, modulus, &t2);
921 err = mp_mul(&t1, &t2, &t1);
923 err = mp_mod(&t1, modulus, &t1);
925 /* multiply against x/y */
927 err = mp_mul(&P->x, &t2, &P->x);
929 err = mp_montgomery_reduce(&P->x, modulus, *mp);
931 err = mp_mul(&P->y, &t1, &P->y);
933 err = mp_montgomery_reduce(&P->y, modulus, *mp);
946 #ifndef ECC_TIMING_RESISTANT
948 /* size of sliding window, don't change this! */
952 Perform a point multiplication
953 k The scalar to multiply by
955 R [out] Destination for kG
956 modulus The modulus of the field the ECC curve is in
957 map Boolean whether to map back to affine or not
958 (1==map, 0 == leave in projective)
959 return MP_OKAY on success
962 static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R,
963 mp_int* modulus, int map)
965 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
969 ecc_point *tG, *M[8];
974 int first = 1, bitbuf = 0, bitcpy = 0, bitcnt = 0, mode = 0,
977 if (k == NULL || G == NULL || R == NULL || modulus == NULL)
978 return ECC_BAD_ARG_E;
980 /* init montgomery reduction */
981 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
984 if ((err = mp_init(&mu)) != MP_OKAY) {
987 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
992 /* alloc ram for window temps */
993 for (i = 0; i < 8; i++) {
994 M[i] = ecc_new_point();
996 for (j = 0; j < i; j++) {
1004 /* make a copy of G incase R==G */
1005 tG = ecc_new_point();
1009 /* tG = G and convert to montgomery */
1010 if (err == MP_OKAY) {
1011 if (mp_cmp_d(&mu, 1) == MP_EQ) {
1012 err = mp_copy(&G->x, &tG->x);
1014 err = mp_copy(&G->y, &tG->y);
1016 err = mp_copy(&G->z, &tG->z);
1018 err = mp_mulmod(&G->x, &mu, modulus, &tG->x);
1020 err = mp_mulmod(&G->y, &mu, modulus, &tG->y);
1022 err = mp_mulmod(&G->z, &mu, modulus, &tG->z);
1027 /* calc the M tab, which holds kG for k==8..15 */
1030 err = ecc_projective_dbl_point(tG, M[0], modulus, &mp);
1032 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1034 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1036 /* now find (8+k)G for k=1..7 */
1038 for (j = 9; j < 16; j++) {
1039 err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp);
1040 if (err != MP_OKAY) break;
1043 /* setup sliding window */
1044 if (err == MP_OKAY) {
1048 digidx = get_digit_count(k) - 1;
1049 bitcpy = bitbuf = 0;
1054 /* grab next digit as required */
1055 if (--bitcnt == 0) {
1059 buf = get_digit(k, digidx);
1060 bitcnt = (int) DIGIT_BIT;
1064 /* grab the next msb from the ltiplicand */
1065 i = (int)(buf >> (DIGIT_BIT - 1)) & 1;
1068 /* skip leading zero bits */
1069 if (mode == 0 && i == 0)
1072 /* if the bit is zero and mode == 1 then we double */
1073 if (mode == 1 && i == 0) {
1074 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1075 if (err != MP_OKAY) break;
1079 /* else we add it to the window */
1080 bitbuf |= (i << (WINSIZE - ++bitcpy));
1083 if (bitcpy == WINSIZE) {
1084 /* if this is the first window we do a simple copy */
1086 /* R = kG [k = first window] */
1087 err = mp_copy(&M[bitbuf-8]->x, &R->x);
1088 if (err != MP_OKAY) break;
1090 err = mp_copy(&M[bitbuf-8]->y, &R->y);
1091 if (err != MP_OKAY) break;
1093 err = mp_copy(&M[bitbuf-8]->z, &R->z);
1097 /* ok window is filled so double as required and add */
1099 for (j = 0; j < WINSIZE; j++) {
1100 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1101 if (err != MP_OKAY) break;
1103 if (err != MP_OKAY) break; /* out of first for(;;) */
1105 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */
1106 err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp);
1108 if (err != MP_OKAY) break;
1109 /* empty window and reset */
1110 bitcpy = bitbuf = 0;
1116 /* if bits remain then double/add */
1117 if (err == MP_OKAY) {
1118 if (mode == 2 && bitcpy > 0) {
1119 /* double then add */
1120 for (j = 0; j < bitcpy; j++) {
1121 /* only double if we have had at least one add first */
1123 err = ecc_projective_dbl_point(R, R, modulus, &mp);
1124 if (err != MP_OKAY) break;
1128 if ((bitbuf & (1 << WINSIZE)) != 0) {
1130 /* first add, so copy */
1131 err = mp_copy(&tG->x, &R->x);
1132 if (err != MP_OKAY) break;
1134 err = mp_copy(&tG->y, &R->y);
1135 if (err != MP_OKAY) break;
1137 err = mp_copy(&tG->z, &R->z);
1138 if (err != MP_OKAY) break;
1142 err = ecc_projective_add_point(R, tG, R, modulus, &mp);
1143 if (err != MP_OKAY) break;
1150 /* map R back from projective space */
1151 if (err == MP_OKAY && map)
1152 err = ecc_map(R, modulus, &mp);
1156 for (i = 0; i < 8; i++) {
1157 ecc_del_point(M[i]);
1163 #endif /* ECC_TIMING_RESISTANT */
1167 Allocate a new ECC point
1168 return A newly allocated point or NULL on error
1170 ecc_point* ecc_new_point(void)
1173 p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT);
1177 XMEMSET(p, 0, sizeof(ecc_point));
1178 if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) {
1179 XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
1185 /** Free an ECC point from memory
1188 void ecc_del_point(ecc_point* p)
1190 /* prevents free'ing null arguments */
1195 XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
1200 /** Returns whether an ECC idx is valid or not
1201 n The idx number to check
1202 return 1 if valid, 0 if not
1204 static int ecc_is_valid_idx(int n)
1208 for (x = 0; ecc_sets[x].size != 0; x++)
1210 /* -1 is a valid index --- indicating that the domain params
1211 were supplied by the user */
1212 if ((n >= -1) && (n < x)) {
1220 Create an ECC shared secret between two keys
1221 private_key The private ECC key
1222 public_key The public key
1223 out [out] Destination of the shared secret
1224 Conforms to EC-DH from ANSI X9.63
1225 outlen [in/out] The max size and resulting size of the shared secret
1226 return MP_OKAY if successful
1228 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out,
1236 if (private_key == NULL || public_key == NULL || out == NULL ||
1238 return BAD_FUNC_ARG;
1241 if (private_key->type != ECC_PRIVATEKEY) {
1242 return ECC_BAD_ARG_E;
1245 if (ecc_is_valid_idx(private_key->idx) == 0 ||
1246 ecc_is_valid_idx(public_key->idx) == 0)
1247 return ECC_BAD_ARG_E;
1249 if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0)
1250 return ECC_BAD_ARG_E;
1252 /* make new point */
1253 result = ecc_new_point();
1254 if (result == NULL) {
1258 if ((err = mp_init(&prime)) != MP_OKAY) {
1259 ecc_del_point(result);
1263 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
1266 err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1);
1268 if (err == MP_OKAY) {
1269 x = mp_unsigned_bin_size(&prime);
1274 if (err == MP_OKAY) {
1276 err = mp_to_unsigned_bin(&result->x,out + (x -
1277 mp_unsigned_bin_size(&result->x)));
1282 ecc_del_point(result);
1288 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp);
1292 rng An active RNG state
1293 keysize The keysize for the new key (in octets from 20 to 65 bytes)
1294 key [out] Destination of the newly created key
1295 return MP_OKAY if successful,
1296 upon error all allocated memory will be freed
1298 int ecc_make_key(RNG* rng, int keysize, ecc_key* key)
1302 if (key == NULL || rng == NULL)
1303 return ECC_BAD_ARG_E;
1306 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++)
1308 keysize = ecc_sets[x].size;
1310 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) {
1311 return BAD_FUNC_ARG;
1313 err = ecc_make_key_ex(rng, key, &ecc_sets[x]);
1319 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp)
1325 #ifdef CYASSL_SMALL_STACK
1328 byte buf[ECC_MAXSIZE];
1332 if (key == NULL || rng == NULL || dp == NULL)
1333 return ECC_BAD_ARG_E;
1335 #ifdef CYASSL_SMALL_STACK
1336 buf = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1348 /* make up random string */
1349 err = RNG_GenerateBlock(rng, buf, keysize);
1353 /* setup the key variables */
1355 err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z,
1356 &key->k, &prime, &order);
1361 if (err == MP_OKAY) {
1362 base = ecc_new_point();
1367 /* read in the specs for this key */
1369 err = mp_read_radix(&prime, (char *)key->dp->prime, 16);
1371 err = mp_read_radix(&order, (char *)key->dp->order, 16);
1373 err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16);
1375 err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16);
1378 mp_set(&base->z, 1);
1380 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize);
1382 /* the key should be smaller than the order of base point */
1383 if (err == MP_OKAY) {
1384 if (mp_cmp(&key->k, &order) != MP_LT)
1385 err = mp_mod(&key->k, &order, &key->k);
1387 /* make the public key */
1389 err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1);
1391 key->type = ECC_PRIVATEKEY;
1393 if (err != MP_OKAY) {
1395 mp_clear(&key->pubkey.x);
1396 mp_clear(&key->pubkey.y);
1397 mp_clear(&key->pubkey.z);
1400 ecc_del_point(base);
1404 #ifdef ECC_CLEAN_STACK
1405 XMEMSET(buf, 0, ECC_MAXSIZE);
1408 #ifdef CYASSL_SMALL_STACK
1409 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1416 /* Setup dynamic pointers is using normal math for proper freeing */
1417 void ecc_init(ecc_key* key)
1420 #ifndef USE_FAST_MATH
1421 key->pubkey.x.dp = NULL;
1422 key->pubkey.y.dp = NULL;
1423 key->pubkey.z.dp = NULL;
1431 Sign a message digest
1432 in The message digest to sign
1433 inlen The length of the digest
1434 out [out] The destination for the signature
1435 outlen [in/out] The max size and resulting size of the signature
1436 key A private ECC key
1437 return MP_OKAY if successful
1439 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen,
1440 RNG* rng, ecc_key* key)
1448 if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL)
1449 return ECC_BAD_ARG_E;
1451 /* is this a private key? */
1452 if (key->type != ECC_PRIVATEKEY) {
1453 return ECC_BAD_ARG_E;
1456 /* is the IDX valid ? */
1457 if (ecc_is_valid_idx(key->idx) != 1) {
1458 return ECC_BAD_ARG_E;
1461 /* get the hash and load it as a bignum into 'e' */
1462 /* init the bignums */
1463 if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) {
1466 err = mp_read_radix(&p, (char *)key->dp->order, 16);
1468 if (err == MP_OKAY) {
1469 /* we may need to truncate if hash is longer than key size */
1470 word32 orderBits = mp_count_bits(&p);
1472 /* truncate down to byte size, may be all that's needed */
1473 if ( (CYASSL_BIT_SIZE * inlen) > orderBits)
1474 inlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
1475 err = mp_read_unsigned_bin(&e, (byte*)in, inlen);
1477 /* may still need bit truncation too */
1478 if (err == MP_OKAY && (CYASSL_BIT_SIZE * inlen) > orderBits)
1479 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
1482 /* make up a key and export the public copy */
1483 if (err == MP_OKAY) {
1487 err = ecc_make_key_ex(rng, &pubkey, key->dp);
1488 if (err != MP_OKAY) break;
1490 /* find r = x1 mod n */
1491 err = mp_mod(&pubkey.pubkey.x, &p, &r);
1492 if (err != MP_OKAY) break;
1494 if (mp_iszero(&r) == MP_YES)
1497 /* find s = (e + xr)/k */
1498 err = mp_invmod(&pubkey.k, &p, &pubkey.k);
1499 if (err != MP_OKAY) break;
1501 err = mp_mulmod(&key->k, &r, &p, &s); /* s = xr */
1502 if (err != MP_OKAY) break;
1504 err = mp_add(&e, &s, &s); /* s = e + xr */
1505 if (err != MP_OKAY) break;
1507 err = mp_mod(&s, &p, &s); /* s = e + xr */
1508 if (err != MP_OKAY) break;
1510 err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */
1511 if (err != MP_OKAY) break;
1514 if (mp_iszero(&s) == MP_NO)
1521 /* store as SEQUENCE { r, s -- integer } */
1523 err = StoreECC_DSA_Sig(out, outlen, &r, &s);
1535 Free an ECC key from memory
1536 key The key you wish to free
1538 void ecc_free(ecc_key* key)
1543 mp_clear(&key->pubkey.x);
1544 mp_clear(&key->pubkey.y);
1545 mp_clear(&key->pubkey.z);
1550 #ifdef USE_FAST_MATH
1551 #define GEN_MEM_ERR FP_MEM
1553 #define GEN_MEM_ERR MP_MEM
1558 /** Computes kA*A + kB*B = C using Shamir's Trick
1559 A First point to multiply
1560 kA What to multiple A by
1561 B Second point to multiply
1562 kB What to multiple B by
1563 C [out] Destination point (can overlap with A or B)
1564 modulus Modulus for curve
1565 return MP_OKAY on success
1568 static int normal_ecc_mul2add(ecc_point* A, mp_int* kA,
1569 ecc_point* B, mp_int* kB,
1570 ecc_point* C, mp_int* modulus)
1572 static int ecc_mul2add(ecc_point* A, mp_int* kA,
1573 ecc_point* B, mp_int* kB,
1574 ecc_point* C, mp_int* modulus)
1577 ecc_point* precomp[16];
1578 unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
1581 int err = MP_OKAY, first;
1588 if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL ||
1590 return ECC_BAD_ARG_E;
1593 /* allocate memory */
1594 tA = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1598 tB = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1600 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1603 XMEMSET(tA, 0, ECC_BUFSIZE);
1604 XMEMSET(tB, 0, ECC_BUFSIZE);
1607 lenA = mp_unsigned_bin_size(kA);
1608 lenB = mp_unsigned_bin_size(kB);
1609 len = MAX(lenA, lenB);
1612 if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) {
1616 if (err == MP_OKAY) {
1617 /* extract and justify kA */
1618 err = mp_to_unsigned_bin(kA, (len - lenA) + tA);
1620 /* extract and justify kB */
1622 err = mp_to_unsigned_bin(kB, (len - lenB) + tB);
1624 /* allocate the table */
1625 if (err == MP_OKAY) {
1626 for (x = 0; x < 16; x++) {
1627 precomp[x] = ecc_new_point();
1628 if (precomp[x] == NULL) {
1629 for (y = 0; y < x; ++y) {
1630 ecc_del_point(precomp[y]);
1643 /* init montgomery reduction */
1644 err = mp_montgomery_setup(modulus, &mp);
1652 err = mp_montgomery_calc_normalization(&mu, modulus);
1656 err = mp_mulmod(&A->x, &mu, modulus, &precomp[1]->x);
1659 err = mp_mulmod(&A->y, &mu, modulus, &precomp[1]->y);
1661 err = mp_mulmod(&A->z, &mu, modulus, &precomp[1]->z);
1664 err = mp_mulmod(&B->x, &mu, modulus, &precomp[1<<2]->x);
1666 err = mp_mulmod(&B->y, &mu, modulus, &precomp[1<<2]->y);
1668 err = mp_mulmod(&B->z, &mu, modulus, &precomp[1<<2]->z);
1671 /* precomp [i,0](A + B) table */
1672 err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp);
1675 err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3],
1678 /* precomp [0,i](A + B) table */
1679 err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp);
1682 err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2],
1685 if (err == MP_OKAY) {
1686 /* precomp [i,j](A + B) table (i != 0, j != 0) */
1687 for (x = 1; x < 4; x++) {
1688 for (y = 1; y < 4; y++) {
1690 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)],
1691 precomp[x+(y<<2)], modulus, &mp);
1696 if (err == MP_OKAY) {
1702 /* for every byte of the multiplicands */
1705 if (++nibble == 4) {
1706 ++x; if (x == len) break;
1712 /* extract two bits from both, shift/update */
1713 nA = (bitbufA >> 6) & 0x03;
1714 nB = (bitbufB >> 6) & 0x03;
1715 bitbufA = (bitbufA << 2) & 0xFF;
1716 bitbufB = (bitbufB << 2) & 0xFF;
1718 /* if both zero, if first, continue */
1719 if ((nA == 0) && (nB == 0) && (first == 1)) {
1723 /* double twice, only if this isn't the first */
1727 err = ecc_projective_dbl_point(C, C, modulus, &mp);
1729 err = ecc_projective_dbl_point(C, C, modulus, &mp);
1734 /* if not both zero */
1735 if ((nA != 0) || (nB != 0)) {
1737 /* if first, copy from table */
1740 err = mp_copy(&precomp[nA + (nB<<2)]->x, &C->x);
1743 err = mp_copy(&precomp[nA + (nB<<2)]->y, &C->y);
1746 err = mp_copy(&precomp[nA + (nB<<2)]->z, &C->z);
1750 /* if not first, add from table */
1752 err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C,
1762 /* reduce to affine */
1763 err = ecc_map(C, modulus, &mp);
1770 for (x = 0; x < 16; x++) {
1771 ecc_del_point(precomp[x]);
1774 #ifdef ECC_CLEAN_STACK
1775 XMEMSET(tA, 0, ECC_BUFSIZE);
1776 XMEMSET(tB, 0, ECC_BUFSIZE);
1778 XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1779 XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1785 #endif /* ECC_SHAMIR */
1800 Verify an ECC signature
1801 sig The signature to verify
1802 siglen The length of the signature (octets)
1803 hash The hash (message digest) that was signed
1804 hashlen The length of the hash (octets)
1805 stat Result of signature, 1==valid, 0==invalid
1806 key The corresponding public ECC key
1807 return MP_OKAY if successful (even if the signature is not valid)
1809 int ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash,
1810 word32 hashlen, int* stat, ecc_key* key)
1824 if (sig == NULL || hash == NULL || stat == NULL || key == NULL)
1825 return ECC_BAD_ARG_E;
1827 /* default to invalid signature */
1830 /* is the IDX valid ? */
1831 if (ecc_is_valid_idx(key->idx) != 1) {
1832 return ECC_BAD_ARG_E;
1836 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) {
1840 if ((err = mp_init(&m)) != MP_OKAY) {
1850 /* allocate points */
1851 mG = ecc_new_point();
1852 mQ = ecc_new_point();
1853 if (mQ == NULL || mG == NULL)
1856 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s.
1857 * If either of those don't allocate correctly, none of
1858 * the rest of this function will execute, and everything
1859 * gets cleaned up at the end. */
1860 XMEMSET(&r, 0, sizeof(r));
1861 XMEMSET(&s, 0, sizeof(s));
1863 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s);
1867 err = mp_read_radix(&p, (char *)key->dp->order, 16);
1869 /* get the modulus */
1871 err = mp_read_radix(&m, (char *)key->dp->prime, 16);
1873 /* check for zero */
1874 if (err == MP_OKAY) {
1875 if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT ||
1876 mp_cmp(&s, &p) != MP_LT)
1880 if (err == MP_OKAY) {
1881 /* we may need to truncate if hash is longer than key size */
1882 unsigned int orderBits = mp_count_bits(&p);
1884 /* truncate down to byte size, may be all that's needed */
1885 if ( (CYASSL_BIT_SIZE * hashlen) > orderBits)
1886 hashlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
1887 err = mp_read_unsigned_bin(&e, hash, hashlen);
1889 /* may still need bit truncation too */
1890 if (err == MP_OKAY && (CYASSL_BIT_SIZE * hashlen) > orderBits)
1891 mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
1894 /* w = s^-1 mod n */
1896 err = mp_invmod(&s, &p, &w);
1900 err = mp_mulmod(&e, &w, &p, &u1);
1904 err = mp_mulmod(&r, &w, &p, &u2);
1906 /* find mG and mQ */
1908 err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16);
1911 err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16);
1916 err = mp_copy(&key->pubkey.x, &mQ->x);
1918 err = mp_copy(&key->pubkey.y, &mQ->y);
1920 err = mp_copy(&key->pubkey.z, &mQ->z);
1926 /* compute u1*mG + u2*mQ = mG */
1928 err = ecc_mulmod(&u1, mG, mG, &m, 0);
1930 err = ecc_mulmod(&u2, mQ, mQ, &m, 0);
1932 /* find the montgomery mp */
1934 err = mp_montgomery_setup(&m, &mp);
1938 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp);
1942 err = ecc_map(mG, &m, &mp);
1945 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */
1947 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m);
1948 #endif /* ECC_SHAMIR */
1950 /* v = X_x1 mod n */
1952 err = mp_mod(&mG->x, &p, &v);
1955 if (err == MP_OKAY) {
1956 if (mp_cmp(&v, &r) == MP_EQ)
1977 /* export public ECC key in ANSI X9.63 format */
1978 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen)
1980 #ifdef CYASSL_SMALL_STACK
1983 byte buf[ECC_BUFSIZE];
1988 if (key == NULL || out == NULL || outLen == NULL)
1989 return ECC_BAD_ARG_E;
1991 if (ecc_is_valid_idx(key->idx) == 0) {
1992 return ECC_BAD_ARG_E;
1994 numlen = key->dp->size;
1996 if (*outLen < (1 + 2*numlen)) {
1997 *outLen = 1 + 2*numlen;
2001 /* store byte 0x04 */
2004 #ifdef CYASSL_SMALL_STACK
2005 buf = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2011 /* pad and store x */
2012 XMEMSET(buf, 0, ECC_BUFSIZE);
2013 ret = mp_to_unsigned_bin(&key->pubkey.x,
2014 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x)));
2017 XMEMCPY(out+1, buf, numlen);
2019 /* pad and store y */
2020 XMEMSET(buf, 0, ECC_BUFSIZE);
2021 ret = mp_to_unsigned_bin(&key->pubkey.y,
2022 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y)));
2025 XMEMCPY(out+1+numlen, buf, numlen);
2027 *outLen = 1 + 2*numlen;
2030 #ifdef CYASSL_SMALL_STACK
2031 XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2038 /* import public ECC key in ANSI X9.63 format */
2039 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key)
2043 if (in == NULL || key == NULL)
2044 return ECC_BAD_ARG_E;
2047 if ((inLen & 1) == 0) {
2048 return ECC_BAD_ARG_E;
2052 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k,
2053 NULL, NULL) != MP_OKAY) {
2058 /* check for 4, 6 or 7 */
2059 if (in[0] != 4 && in[0] != 6 && in[0] != 7) {
2065 err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1);
2068 err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1),
2072 mp_set(&key->pubkey.z, 1);
2074 if (err == MP_OKAY) {
2075 /* determine the idx */
2076 for (x = 0; ecc_sets[x].size != 0; x++) {
2077 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) {
2081 if (ecc_sets[x].size == 0) {
2086 key->dp = &ecc_sets[x];
2087 key->type = ECC_PUBLICKEY;
2091 if (err != MP_OKAY) {
2092 mp_clear(&key->pubkey.x);
2093 mp_clear(&key->pubkey.y);
2094 mp_clear(&key->pubkey.z);
2102 /* export ecc private key only raw, outLen is in/out size
2103 return MP_OKAY on success */
2104 int ecc_export_private_only(ecc_key* key, byte* out, word32* outLen)
2108 if (key == NULL || out == NULL || outLen == NULL)
2109 return ECC_BAD_ARG_E;
2111 if (ecc_is_valid_idx(key->idx) == 0) {
2112 return ECC_BAD_ARG_E;
2114 numlen = key->dp->size;
2116 if (*outLen < numlen) {
2121 XMEMSET(out, 0, *outLen);
2122 return mp_to_unsigned_bin(&key->k, out + (numlen -
2123 mp_unsigned_bin_size(&key->k)));
2127 /* ecc private key import, public key in ANSI X9.63 format, private raw */
2128 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub,
2129 word32 pubSz, ecc_key* key)
2131 int ret = ecc_import_x963(pub, pubSz, key);
2135 key->type = ECC_PRIVATEKEY;
2137 return mp_read_unsigned_bin(&key->k, priv, privSz);
2141 /* key size in octets */
2142 int ecc_size(ecc_key* key)
2144 if (key == NULL) return 0;
2146 return key->dp->size;
2150 /* worst case estimate, check actual return from ecc_sign_hash for actual value
2151 of signature size in octets */
2152 int ecc_sig_size(ecc_key* key)
2154 int sz = ecc_size(key);
2158 return sz * 2 + SIG_HEADER_SZ + 4; /* (4) worst case estimate */
2164 /* fixed point ECC cache */
2165 /* number of entries in the cache */
2167 #define FP_ENTRIES 16
2170 /* number of bits in LUT */
2176 /* Sharmir requires a bigger LUT, TAO */
2177 #if (FP_LUT > 12) || (FP_LUT < 4)
2178 #error FP_LUT must be between 4 and 12 inclusively
2181 #if (FP_LUT > 12) || (FP_LUT < 2)
2182 #error FP_LUT must be between 2 and 12 inclusively
2189 ecc_point* g; /* cached COPY of base point */
2190 ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */
2191 mp_int mu; /* copy of the montgomery constant */
2192 int lru_count; /* amount of times this entry has been used */
2193 int lock; /* flag to indicate cache eviction */
2194 /* permitted (0) or not (1) */
2197 /* if HAVE_THREAD_LS this cache is per thread, no locking needed */
2198 static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES];
2200 #ifndef HAVE_THREAD_LS
2201 static volatile int initMutex = 0; /* prevent multiple mutex inits */
2202 static CyaSSL_Mutex ecc_fp_lock;
2203 #endif /* HAVE_THREAD_LS */
2205 /* simple table to help direct the generation of the LUT */
2206 static const struct {
2207 int ham, terma, termb;
2209 { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 },
2210 { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 },
2211 { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 },
2212 { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 },
2213 { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 },
2214 { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 },
2215 { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 },
2216 { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 },
2218 { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 },
2219 { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 },
2220 { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 },
2221 { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 },
2222 { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 },
2223 { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 },
2224 { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 },
2225 { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 },
2227 { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 },
2228 { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 },
2229 { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 },
2230 { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 },
2231 { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 },
2232 { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 },
2233 { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 },
2234 { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 },
2235 { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 },
2236 { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 },
2237 { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 },
2238 { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 },
2239 { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 },
2240 { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 },
2241 { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 },
2242 { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 },
2244 { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 },
2245 { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 },
2246 { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 },
2247 { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 },
2248 { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 },
2249 { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 },
2250 { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 },
2251 { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 },
2252 { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 },
2253 { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 },
2254 { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 },
2255 { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 },
2256 { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 },
2257 { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 },
2258 { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 },
2259 { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 },
2260 { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 },
2261 { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 },
2262 { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 },
2263 { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 },
2264 { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 },
2265 { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 },
2266 { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 },
2267 { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 },
2268 { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 },
2269 { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 },
2270 { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 },
2271 { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 },
2272 { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 },
2273 { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 },
2274 { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 },
2275 { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 },
2277 { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 },
2278 { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 },
2279 { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 },
2280 { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 },
2281 { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 },
2282 { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 },
2283 { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 },
2284 { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 },
2285 { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 },
2286 { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 },
2287 { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 },
2288 { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 },
2289 { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 },
2290 { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 },
2291 { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 },
2292 { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 },
2293 { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 },
2294 { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 },
2295 { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 },
2296 { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 },
2297 { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 },
2298 { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 },
2299 { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 },
2300 { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 },
2301 { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 },
2302 { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 },
2303 { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 },
2304 { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 },
2305 { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 },
2306 { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 },
2307 { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 },
2308 { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 },
2309 { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 },
2310 { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 },
2311 { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 },
2312 { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 },
2313 { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 },
2314 { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 },
2315 { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 },
2316 { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 },
2317 { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 },
2318 { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 },
2319 { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 },
2320 { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 },
2321 { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 },
2322 { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 },
2323 { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 },
2324 { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 },
2325 { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 },
2326 { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 },
2327 { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 },
2328 { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 },
2329 { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 },
2330 { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 },
2331 { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 },
2332 { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 },
2333 { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 },
2334 { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 },
2335 { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 },
2336 { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 },
2337 { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 },
2338 { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 },
2339 { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 },
2340 { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 },
2342 { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 },
2343 { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 },
2344 { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 },
2345 { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 },
2346 { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 },
2347 { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 },
2348 { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 },
2349 { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 },
2350 { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 },
2351 { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 },
2352 { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 },
2353 { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 },
2354 { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 },
2355 { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 },
2356 { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 },
2357 { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 },
2358 { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 },
2359 { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 },
2360 { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 },
2361 { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 },
2362 { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 },
2363 { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 },
2364 { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 },
2365 { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 },
2366 { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 },
2367 { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 },
2368 { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 },
2369 { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 },
2370 { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 },
2371 { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 },
2372 { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 },
2373 { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 },
2374 { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 },
2375 { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 },
2376 { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 },
2377 { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 },
2378 { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 },
2379 { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 },
2380 { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 },
2381 { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 },
2382 { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 },
2383 { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 },
2384 { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 },
2385 { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 },
2386 { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 },
2387 { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 },
2388 { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 },
2389 { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 },
2390 { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 },
2391 { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 },
2392 { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 },
2393 { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 },
2394 { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 },
2395 { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 },
2396 { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 },
2397 { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 },
2398 { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 },
2399 { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 },
2400 { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 },
2401 { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 },
2402 { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 },
2403 { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 },
2404 { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 },
2405 { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 },
2406 { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 },
2407 { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 },
2408 { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 },
2409 { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 },
2410 { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 },
2411 { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 },
2412 { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 },
2413 { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 },
2414 { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 },
2415 { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 },
2416 { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 },
2417 { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 },
2418 { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 },
2419 { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 },
2420 { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 },
2421 { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 },
2422 { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 },
2423 { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 },
2424 { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 },
2425 { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 },
2426 { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 },
2427 { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 },
2428 { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 },
2429 { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 },
2430 { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 },
2431 { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 },
2432 { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 },
2433 { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 },
2434 { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 },
2435 { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 },
2436 { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 },
2437 { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 },
2438 { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 },
2439 { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 },
2440 { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 },
2441 { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 },
2442 { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 },
2443 { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 },
2444 { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 },
2445 { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 },
2446 { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 },
2447 { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 },
2448 { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 },
2449 { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 },
2450 { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 },
2451 { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 },
2452 { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883, 1024 }, { 7, 884, 1024 }, { 8, 885, 1024 }, { 8, 886, 1024 }, { 9, 887, 1024 },
2453 { 7, 888, 1024 }, { 8, 889, 1024 }, { 8, 890, 1024 }, { 9, 891, 1024 }, { 8, 892, 1024 }, { 9, 893, 1024 }, { 9, 894, 1024 }, { 10, 895, 1024 },
2454 { 4, 896, 1024 }, { 5, 897, 1024 }, { 5, 898, 1024 }, { 6, 899, 1024 }, { 5, 900, 1024 }, { 6, 901, 1024 }, { 6, 902, 1024 }, { 7, 903, 1024 },
2455 { 5, 904, 1024 }, { 6, 905, 1024 }, { 6, 906, 1024 }, { 7, 907, 1024 }, { 6, 908, 1024 }, { 7, 909, 1024 }, { 7, 910, 1024 }, { 8, 911, 1024 },
2456 { 5, 912, 1024 }, { 6, 913, 1024 }, { 6, 914, 1024 }, { 7, 915, 1024 }, { 6, 916, 1024 }, { 7, 917, 1024 }, { 7, 918, 1024 }, { 8, 919, 1024 },
2457 { 6, 920, 1024 }, { 7, 921, 1024 }, { 7, 922, 1024 }, { 8, 923, 1024 }, { 7, 924, 1024 }, { 8, 925, 1024 }, { 8, 926, 1024 }, { 9, 927, 1024 },
2458 { 5, 928, 1024 }, { 6, 929, 1024 }, { 6, 930, 1024 }, { 7, 931, 1024 }, { 6, 932, 1024 }, { 7, 933, 1024 }, { 7, 934, 1024 }, { 8, 935, 1024 },
2459 { 6, 936, 1024 }, { 7, 937, 1024 }, { 7, 938, 1024 }, { 8, 939, 1024 }, { 7, 940, 1024 }, { 8, 941, 1024 }, { 8, 942, 1024 }, { 9, 943, 1024 },
2460 { 6, 944, 1024 }, { 7, 945, 1024 }, { 7, 946, 1024 }, { 8, 947, 1024 }, { 7, 948, 1024 }, { 8, 949, 1024 }, { 8, 950, 1024 }, { 9, 951, 1024 },
2461 { 7, 952, 1024 }, { 8, 953, 1024 }, { 8, 954, 1024 }, { 9, 955, 1024 }, { 8, 956, 1024 }, { 9, 957, 1024 }, { 9, 958, 1024 }, { 10, 959, 1024 },
2462 { 5, 960, 1024 }, { 6, 961, 1024 }, { 6, 962, 1024 }, { 7, 963, 1024 }, { 6, 964, 1024 }, { 7, 965, 1024 }, { 7, 966, 1024 }, { 8, 967, 1024 },
2463 { 6, 968, 1024 }, { 7, 969, 1024 }, { 7, 970, 1024 }, { 8, 971, 1024 }, { 7, 972, 1024 }, { 8, 973, 1024 }, { 8, 974, 1024 }, { 9, 975, 1024 },
2464 { 6, 976, 1024 }, { 7, 977, 1024 }, { 7, 978, 1024 }, { 8, 979, 1024 }, { 7, 980, 1024 }, { 8, 981, 1024 }, { 8, 982, 1024 }, { 9, 983, 1024 },
2465 { 7, 984, 1024 }, { 8, 985, 1024 }, { 8, 986, 1024 }, { 9, 987, 1024 }, { 8, 988, 1024 }, { 9, 989, 1024 }, { 9, 990, 1024 }, { 10, 991, 1024 },
2466 { 6, 992, 1024 }, { 7, 993, 1024 }, { 7, 994, 1024 }, { 8, 995, 1024 }, { 7, 996, 1024 }, { 8, 997, 1024 }, { 8, 998, 1024 }, { 9, 999, 1024 },
2467 { 7, 1000, 1024 }, { 8, 1001, 1024 }, { 8, 1002, 1024 }, { 9, 1003, 1024 }, { 8, 1004, 1024 }, { 9, 1005, 1024 }, { 9, 1006, 1024 }, { 10, 1007, 1024 },
2468 { 7, 1008, 1024 }, { 8, 1009, 1024 }, { 8, 1010, 1024 }, { 9, 1011, 1024 }, { 8, 1012, 1024 }, { 9, 1013, 1024 }, { 9, 1014, 1024 }, { 10, 1015, 1024 },
2469 { 8, 1016, 1024 }, { 9, 1017, 1024 }, { 9, 1018, 1024 }, { 10, 1019, 1024 }, { 9, 1020, 1024 }, { 10, 1021, 1024 }, { 10, 1022, 1024 }, { 11, 1023, 1024 },
2471 { 1, 0, 0 }, { 2, 1, 2048 }, { 2, 2, 2048 }, { 3, 3, 2048 }, { 2, 4, 2048 }, { 3, 5, 2048 }, { 3, 6, 2048 }, { 4, 7, 2048 },
2472 { 2, 8, 2048 }, { 3, 9, 2048 }, { 3, 10, 2048 }, { 4, 11, 2048 }, { 3, 12, 2048 }, { 4, 13, 2048 }, { 4, 14, 2048 }, { 5, 15, 2048 },
2473 { 2, 16, 2048 }, { 3, 17, 2048 }, { 3, 18, 2048 }, { 4, 19, 2048 }, { 3, 20, 2048 }, { 4, 21, 2048 }, { 4, 22, 2048 }, { 5, 23, 2048 },
2474 { 3, 24, 2048 }, { 4, 25, 2048 }, { 4, 26, 2048 }, { 5, 27, 2048 }, { 4, 28, 2048 }, { 5, 29, 2048 }, { 5, 30, 2048 }, { 6, 31, 2048 },
2475 { 2, 32, 2048 }, { 3, 33, 2048 }, { 3, 34, 2048 }, { 4, 35, 2048 }, { 3, 36, 2048 }, { 4, 37, 2048 }, { 4, 38, 2048 }, { 5, 39, 2048 },
2476 { 3, 40, 2048 }, { 4, 41, 2048 }, { 4, 42, 2048 }, { 5, 43, 2048 }, { 4, 44, 2048 }, { 5, 45, 2048 }, { 5, 46, 2048 }, { 6, 47, 2048 },
2477 { 3, 48, 2048 }, { 4, 49, 2048 }, { 4, 50, 2048 }, { 5, 51, 2048 }, { 4, 52, 2048 }, { 5, 53, 2048 }, { 5, 54, 2048 }, { 6, 55, 2048 },
2478 { 4, 56, 2048 }, { 5, 57, 2048 }, { 5, 58, 2048 }, { 6, 59, 2048 }, { 5, 60, 2048 }, { 6, 61, 2048 }, { 6, 62, 2048 }, { 7, 63, 2048 },
2479 { 2, 64, 2048 }, { 3, 65, 2048 }, { 3, 66, 2048 }, { 4, 67, 2048 }, { 3, 68, 2048 }, { 4, 69, 2048 }, { 4, 70, 2048 }, { 5, 71, 2048 },
2480 { 3, 72, 2048 }, { 4, 73, 2048 }, { 4, 74, 2048 }, { 5, 75, 2048 }, { 4, 76, 2048 }, { 5, 77, 2048 }, { 5, 78, 2048 }, { 6, 79, 2048 },
2481 { 3, 80, 2048 }, { 4, 81, 2048 }, { 4, 82, 2048 }, { 5, 83, 2048 }, { 4, 84, 2048 }, { 5, 85, 2048 }, { 5, 86, 2048 }, { 6, 87, 2048 },
2482 { 4, 88, 2048 }, { 5, 89, 2048 }, { 5, 90, 2048 }, { 6, 91, 2048 }, { 5, 92, 2048 }, { 6, 93, 2048 }, { 6, 94, 2048 }, { 7, 95, 2048 },
2483 { 3, 96, 2048 }, { 4, 97, 2048 }, { 4, 98, 2048 }, { 5, 99, 2048 }, { 4, 100, 2048 }, { 5, 101, 2048 }, { 5, 102, 2048 }, { 6, 103, 2048 },
2484 { 4, 104, 2048 }, { 5, 105, 2048 }, { 5, 106, 2048 }, { 6, 107, 2048 }, { 5, 108, 2048 }, { 6, 109, 2048 }, { 6, 110, 2048 }, { 7, 111, 2048 },
2485 { 4, 112, 2048 }, { 5, 113, 2048 }, { 5, 114, 2048 }, { 6, 115, 2048 }, { 5, 116, 2048 }, { 6, 117, 2048 }, { 6, 118, 2048 }, { 7, 119, 2048 },
2486 { 5, 120, 2048 }, { 6, 121, 2048 }, { 6, 122, 2048 }, { 7, 123, 2048 }, { 6, 124, 2048 }, { 7, 125, 2048 }, { 7, 126, 2048 }, { 8, 127, 2048 },
2487 { 2, 128, 2048 }, { 3, 129, 2048 }, { 3, 130, 2048 }, { 4, 131, 2048 }, { 3, 132, 2048 }, { 4, 133, 2048 }, { 4, 134, 2048 }, { 5, 135, 2048 },
2488 { 3, 136, 2048 }, { 4, 137, 2048 }, { 4, 138, 2048 }, { 5, 139, 2048 }, { 4, 140, 2048 }, { 5, 141, 2048 }, { 5, 142, 2048 }, { 6, 143, 2048 },
2489 { 3, 144, 2048 }, { 4, 145, 2048 }, { 4, 146, 2048 }, { 5, 147, 2048 }, { 4, 148, 2048 }, { 5, 149, 2048 }, { 5, 150, 2048 }, { 6, 151, 2048 },
2490 { 4, 152, 2048 }, { 5, 153, 2048 }, { 5, 154, 2048 }, { 6, 155, 2048 }, { 5, 156, 2048 }, { 6, 157, 2048 }, { 6, 158, 2048 }, { 7, 159, 2048 },
2491 { 3, 160, 2048 }, { 4, 161, 2048 }, { 4, 162, 2048 }, { 5, 163, 2048 }, { 4, 164, 2048 }, { 5, 165, 2048 }, { 5, 166, 2048 }, { 6, 167, 2048 },
2492 { 4, 168, 2048 }, { 5, 169, 2048 }, { 5, 170, 2048 }, { 6, 171, 2048 }, { 5, 172, 2048 }, { 6, 173, 2048 }, { 6, 174, 2048 }, { 7, 175, 2048 },
2493 { 4, 176, 2048 }, { 5, 177, 2048 }, { 5, 178, 2048 }, { 6, 179, 2048 }, { 5, 180, 2048 }, { 6, 181, 2048 }, { 6, 182, 2048 }, { 7, 183, 2048 },
2494 { 5, 184, 2048 }, { 6, 185, 2048 }, { 6, 186, 2048 }, { 7, 187, 2048 }, { 6, 188, 2048 }, { 7, 189, 2048 }, { 7, 190, 2048 }, { 8, 191, 2048 },
2495 { 3, 192, 2048 }, { 4, 193, 2048 }, { 4, 194, 2048 }, { 5, 195, 2048 }, { 4, 196, 2048 }, { 5, 197, 2048 }, { 5, 198, 2048 }, { 6, 199, 2048 },
2496 { 4, 200, 2048 }, { 5, 201, 2048 }, { 5, 202, 2048 }, { 6, 203, 2048 }, { 5, 204, 2048 }, { 6, 205, 2048 }, { 6, 206, 2048 }, { 7, 207, 2048 },
2497 { 4, 208, 2048 }, { 5, 209, 2048 }, { 5, 210, 2048 }, { 6, 211, 2048 }, { 5, 212, 2048 }, { 6, 213, 2048 }, { 6, 214, 2048 }, { 7, 215, 2048 },
2498 { 5, 216, 2048 }, { 6, 217, 2048 }, { 6, 218, 2048 }, { 7, 219, 2048 }, { 6, 220, 2048 }, { 7, 221, 2048 }, { 7, 222, 2048 }, { 8, 223, 2048 },
2499 { 4, 224, 2048 }, { 5, 225, 2048 }, { 5, 226, 2048 }, { 6, 227, 2048 }, { 5, 228, 2048 }, { 6, 229, 2048 }, { 6, 230, 2048 }, { 7, 231, 2048 },
2500 { 5, 232, 2048 }, { 6, 233, 2048 }, { 6, 234, 2048 }, { 7, 235, 2048 }, { 6, 236, 2048 }, { 7, 237, 2048 }, { 7, 238, 2048 }, { 8, 239, 2048 },
2501 { 5, 240, 2048 }, { 6, 241, 2048 }, { 6, 242, 2048 }, { 7, 243, 2048 }, { 6, 244, 2048 }, { 7, 245, 2048 }, { 7, 246, 2048 }, { 8, 247, 2048 },
2502 { 6, 248, 2048 }, { 7, 249, 2048 }, { 7, 250, 2048 }, { 8, 251, 2048 }, { 7, 252, 2048 }, { 8, 253, 2048 }, { 8, 254, 2048 }, { 9, 255, 2048 },
2503 { 2, 256, 2048 }, { 3, 257, 2048 }, { 3, 258, 2048 }, { 4, 259, 2048 }, { 3, 260, 2048 }, { 4, 261, 2048 }, { 4, 262, 2048 }, { 5, 263, 2048 },
2504 { 3, 264, 2048 }, { 4, 265, 2048 }, { 4, 266, 2048 }, { 5, 267, 2048 }, { 4, 268, 2048 }, { 5, 269, 2048 }, { 5, 270, 2048 }, { 6, 271, 2048 },
2505 { 3, 272, 2048 }, { 4, 273, 2048 }, { 4, 274, 2048 }, { 5, 275, 2048 }, { 4, 276, 2048 }, { 5, 277, 2048 }, { 5, 278, 2048 }, { 6, 279, 2048 },
2506 { 4, 280, 2048 }, { 5, 281, 2048 }, { 5, 282, 2048 }, { 6, 283, 2048 }, { 5, 284, 2048 }, { 6, 285, 2048 }, { 6, 286, 2048 }, { 7, 287, 2048 },
2507 { 3, 288, 2048 }, { 4, 289, 2048 }, { 4, 290, 2048 }, { 5, 291, 2048 }, { 4, 292, 2048 }, { 5, 293, 2048 }, { 5, 294, 2048 }, { 6, 295, 2048 },
2508 { 4, 296, 2048 }, { 5, 297, 2048 }, { 5, 298, 2048 }, { 6, 299, 2048 }, { 5, 300, 2048 }, { 6, 301, 2048 }, { 6, 302, 2048 }, { 7, 303, 2048 },
2509 { 4, 304, 2048 }, { 5, 305, 2048 }, { 5, 306, 2048 }, { 6, 307, 2048 }, { 5, 308, 2048 }, { 6, 309, 2048 }, { 6, 310, 2048 }, { 7, 311, 2048 },
2510 { 5, 312, 2048 }, { 6, 313, 2048 }, { 6, 314, 2048 }, { 7, 315, 2048 }, { 6, 316, 2048 }, { 7, 317, 2048 }, { 7, 318, 2048 }, { 8, 319, 2048 },
2511 { 3, 320, 2048 }, { 4, 321, 2048 }, { 4, 322, 2048 }, { 5, 323, 2048 }, { 4, 324, 2048 }, { 5, 325, 2048 }, { 5, 326, 2048 }, { 6, 327, 2048 },
2512 { 4, 328, 2048 }, { 5, 329, 2048 }, { 5, 330, 2048 }, { 6, 331, 2048 }, { 5, 332, 2048 }, { 6, 333, 2048 }, { 6, 334, 2048 }, { 7, 335, 2048 },
2513 { 4, 336, 2048 }, { 5, 337, 2048 }, { 5, 338, 2048 }, { 6, 339, 2048 }, { 5, 340, 2048 }, { 6, 341, 2048 }, { 6, 342, 2048 }, { 7, 343, 2048 },
2514 { 5, 344, 2048 }, { 6, 345, 2048 }, { 6, 346, 2048 }, { 7, 347, 2048 }, { 6, 348, 2048 }, { 7, 349, 2048 }, { 7, 350, 2048 }, { 8, 351, 2048 },
2515 { 4, 352, 2048 }, { 5, 353, 2048 }, { 5, 354, 2048 }, { 6, 355, 2048 }, { 5, 356, 2048 }, { 6, 357, 2048 }, { 6, 358, 2048 }, { 7, 359, 2048 },
2516 { 5, 360, 2048 }, { 6, 361, 2048 }, { 6, 362, 2048 }, { 7, 363, 2048 }, { 6, 364, 2048 }, { 7, 365, 2048 }, { 7, 366, 2048 }, { 8, 367, 2048 },
2517 { 5, 368, 2048 }, { 6, 369, 2048 }, { 6, 370, 2048 }, { 7, 371, 2048 }, { 6, 372, 2048 }, { 7, 373, 2048 }, { 7, 374, 2048 }, { 8, 375, 2048 },
2518 { 6, 376, 2048 }, { 7, 377, 2048 }, { 7, 378, 2048 }, { 8, 379, 2048 }, { 7, 380, 2048 }, { 8, 381, 2048 }, { 8, 382, 2048 }, { 9, 383, 2048 },
2519 { 3, 384, 2048 }, { 4, 385, 2048 }, { 4, 386, 2048 }, { 5, 387, 2048 }, { 4, 388, 2048 }, { 5, 389, 2048 }, { 5, 390, 2048 }, { 6, 391, 2048 },
2520 { 4, 392, 2048 }, { 5, 393, 2048 }, { 5, 394, 2048 }, { 6, 395, 2048 }, { 5, 396, 2048 }, { 6, 397, 2048 }, { 6, 398, 2048 }, { 7, 399, 2048 },
2521 { 4, 400, 2048 }, { 5, 401, 2048 }, { 5, 402, 2048 }, { 6, 403, 2048 }, { 5, 404, 2048 }, { 6, 405, 2048 }, { 6, 406, 2048 }, { 7, 407, 2048 },
2522 { 5, 408, 2048 }, { 6, 409, 2048 }, { 6, 410, 2048 }, { 7, 411, 2048 }, { 6, 412, 2048 }, { 7, 413, 2048 }, { 7, 414, 2048 }, { 8, 415, 2048 },
2523 { 4, 416, 2048 }, { 5, 417, 2048 }, { 5, 418, 2048 }, { 6, 419, 2048 }, { 5, 420, 2048 }, { 6, 421, 2048 }, { 6, 422, 2048 }, { 7, 423, 2048 },
2524 { 5, 424, 2048 }, { 6, 425, 2048 }, { 6, 426, 2048 }, { 7, 427, 2048 }, { 6, 428, 2048 }, { 7, 429, 2048 }, { 7, 430, 2048 }, { 8, 431, 2048 },
2525 { 5, 432, 2048 }, { 6, 433, 2048 }, { 6, 434, 2048 }, { 7, 435, 2048 }, { 6, 436, 2048 }, { 7, 437, 2048 }, { 7, 438, 2048 }, { 8, 439, 2048 },
2526 { 6, 440, 2048 }, { 7, 441, 2048 }, { 7, 442, 2048 }, { 8, 443, 2048 }, { 7, 444, 2048 }, { 8, 445, 2048 }, { 8, 446, 2048 }, { 9, 447, 2048 },
2527 { 4, 448, 2048 }, { 5, 449, 2048 }, { 5, 450, 2048 }, { 6, 451, 2048 }, { 5, 452, 2048 }, { 6, 453, 2048 }, { 6, 454, 2048 }, { 7, 455, 2048 },
2528 { 5, 456, 2048 }, { 6, 457, 2048 }, { 6, 458, 2048 }, { 7, 459, 2048 }, { 6, 460, 2048 }, { 7, 461, 2048 }, { 7, 462, 2048 }, { 8, 463, 2048 },
2529 { 5, 464, 2048 }, { 6, 465, 2048 }, { 6, 466, 2048 }, { 7, 467, 2048 }, { 6, 468, 2048 }, { 7, 469, 2048 }, { 7, 470, 2048 }, { 8, 471, 2048 },
2530 { 6, 472, 2048 }, { 7, 473, 2048 }, { 7, 474, 2048 }, { 8, 475, 2048 }, { 7, 476, 2048 }, { 8, 477, 2048 }, { 8, 478, 2048 }, { 9, 479, 2048 },
2531 { 5, 480, 2048 }, { 6, 481, 2048 }, { 6, 482, 2048 }, { 7, 483, 2048 }, { 6, 484, 2048 }, { 7, 485, 2048 }, { 7, 486, 2048 }, { 8, 487, 2048 },
2532 { 6, 488, 2048 }, { 7, 489, 2048 }, { 7, 490, 2048 }, { 8, 491, 2048 }, { 7, 492, 2048 }, { 8, 493, 2048 }, { 8, 494, 2048 }, { 9, 495, 2048 },
2533 { 6, 496, 2048 }, { 7, 497, 2048 }, { 7, 498, 2048 }, { 8, 499, 2048 }, { 7, 500, 2048 }, { 8, 501, 2048 }, { 8, 502, 2048 }, { 9, 503, 2048 },
2534 { 7, 504, 2048 }, { 8, 505, 2048 }, { 8, 506, 2048 }, { 9, 507, 2048 }, { 8, 508, 2048 }, { 9, 509, 2048 }, { 9, 510, 2048 }, { 10, 511, 2048 },
2535 { 2, 512, 2048 }, { 3, 513, 2048 }, { 3, 514, 2048 }, { 4, 515, 2048 }, { 3, 516, 2048 }, { 4, 517, 2048 }, { 4, 518, 2048 }, { 5, 519, 2048 },
2536 { 3, 520, 2048 }, { 4, 521, 2048 }, { 4, 522, 2048 }, { 5, 523, 2048 }, { 4, 524, 2048 }, { 5, 525, 2048 }, { 5, 526, 2048 }, { 6, 527, 2048 },
2537 { 3, 528, 2048 }, { 4, 529, 2048 }, { 4, 530, 2048 }, { 5, 531, 2048 }, { 4, 532, 2048 }, { 5, 533, 2048 }, { 5, 534, 2048 }, { 6, 535, 2048 },
2538 { 4, 536, 2048 }, { 5, 537, 2048 }, { 5, 538, 2048 }, { 6, 539, 2048 }, { 5, 540, 2048 }, { 6, 541, 2048 }, { 6, 542, 2048 }, { 7, 543, 2048 },
2539 { 3, 544, 2048 }, { 4, 545, 2048 }, { 4, 546, 2048 }, { 5, 547, 2048 }, { 4, 548, 2048 }, { 5, 549, 2048 }, { 5, 550, 2048 }, { 6, 551, 2048 },
2540 { 4, 552, 2048 }, { 5, 553, 2048 }, { 5, 554, 2048 }, { 6, 555, 2048 }, { 5, 556, 2048 }, { 6, 557, 2048 }, { 6, 558, 2048 }, { 7, 559, 2048 },
2541 { 4, 560, 2048 }, { 5, 561, 2048 }, { 5, 562, 2048 }, { 6, 563, 2048 }, { 5, 564, 2048 }, { 6, 565, 2048 }, { 6, 566, 2048 }, { 7, 567, 2048 },
2542 { 5, 568, 2048 }, { 6, 569, 2048 }, { 6, 570, 2048 }, { 7, 571, 2048 }, { 6, 572, 2048 }, { 7, 573, 2048 }, { 7, 574, 2048 }, { 8, 575, 2048 },
2543 { 3, 576, 2048 }, { 4, 577, 2048 }, { 4, 578, 2048 }, { 5, 579, 2048 }, { 4, 580, 2048 }, { 5, 581, 2048 }, { 5, 582, 2048 }, { 6, 583, 2048 },
2544 { 4, 584, 2048 }, { 5, 585, 2048 }, { 5, 586, 2048 }, { 6, 587, 2048 }, { 5, 588, 2048 }, { 6, 589, 2048 }, { 6, 590, 2048 }, { 7, 591, 2048 },
2545 { 4, 592, 2048 }, { 5, 593, 2048 }, { 5, 594, 2048 }, { 6, 595, 2048 }, { 5, 596, 2048 }, { 6, 597, 2048 }, { 6, 598, 2048 }, { 7, 599, 2048 },
2546 { 5, 600, 2048 }, { 6, 601, 2048 }, { 6, 602, 2048 }, { 7, 603, 2048 }, { 6, 604, 2048 }, { 7, 605, 2048 }, { 7, 606, 2048 }, { 8, 607, 2048 },
2547 { 4, 608, 2048 }, { 5, 609, 2048 }, { 5, 610, 2048 }, { 6, 611, 2048 }, { 5, 612, 2048 }, { 6, 613, 2048 }, { 6, 614, 2048 }, { 7, 615, 2048 },
2548 { 5, 616, 2048 }, { 6, 617, 2048 }, { 6, 618, 2048 }, { 7, 619, 2048 }, { 6, 620, 2048 }, { 7, 621, 2048 }, { 7, 622, 2048 }, { 8, 623, 2048 },
2549 { 5, 624, 2048 }, { 6, 625, 2048 }, { 6, 626, 2048 }, { 7, 627, 2048 }, { 6, 628, 2048 }, { 7, 629, 2048 }, { 7, 630, 2048 }, { 8, 631, 2048 },
2550 { 6, 632, 2048 }, { 7, 633, 2048 }, { 7, 634, 2048 }, { 8, 635, 2048 }, { 7, 636, 2048 }, { 8, 637, 2048 }, { 8, 638, 2048 }, { 9, 639, 2048 },
2551 { 3, 640, 2048 }, { 4, 641, 2048 }, { 4, 642, 2048 }, { 5, 643, 2048 }, { 4, 644, 2048 }, { 5, 645, 2048 }, { 5, 646, 2048 }, { 6, 647, 2048 },
2552 { 4, 648, 2048 }, { 5, 649, 2048 }, { 5, 650, 2048 }, { 6, 651, 2048 }, { 5, 652, 2048 }, { 6, 653, 2048 }, { 6, 654, 2048 }, { 7, 655, 2048 },
2553 { 4, 656, 2048 }, { 5, 657, 2048 }, { 5, 658, 2048 }, { 6, 659, 2048 }, { 5, 660, 2048 }, { 6, 661, 2048 }, { 6, 662, 2048 }, { 7, 663, 2048 },
2554 { 5, 664, 2048 }, { 6, 665, 2048 }, { 6, 666, 2048 }, { 7, 667, 2048 }, { 6, 668, 2048 }, { 7, 669, 2048 }, { 7, 670, 2048 }, { 8, 671, 2048 },
2555 { 4, 672, 2048 }, { 5, 673, 2048 }, { 5, 674, 2048 }, { 6, 675, 2048 }, { 5, 676, 2048 }, { 6, 677, 2048 }, { 6, 678, 2048 }, { 7, 679, 2048 },
2556 { 5, 680, 2048 }, { 6, 681, 2048 }, { 6, 682, 2048 }, { 7, 683, 2048 }, { 6, 684, 2048 }, { 7, 685, 2048 }, { 7, 686, 2048 }, { 8, 687, 2048 },
2557 { 5, 688, 2048 }, { 6, 689, 2048 }, { 6, 690, 2048 }, { 7, 691, 2048 }, { 6, 692, 2048 }, { 7, 693, 2048 }, { 7, 694, 2048 }, { 8, 695, 2048 },
2558 { 6, 696, 2048 }, { 7, 697, 2048 }, { 7, 698, 2048 }, { 8, 699, 2048 }, { 7, 700, 2048 }, { 8, 701, 2048 }, { 8, 702, 2048 }, { 9, 703, 2048 },
2559 { 4, 704, 2048 }, { 5, 705, 2048 }, { 5, 706, 2048 }, { 6, 707, 2048 }, { 5, 708, 2048 }, { 6, 709, 2048 }, { 6, 710, 2048 }, { 7, 711, 2048 },
2560 { 5, 712, 2048 }, { 6, 713, 2048 }, { 6, 714, 2048 }, { 7, 715, 2048 }, { 6, 716, 2048 }, { 7, 717, 2048 }, { 7, 718, 2048 }, { 8, 719, 2048 },
2561 { 5, 720, 2048 }, { 6, 721, 2048 }, { 6, 722, 2048 }, { 7, 723, 2048 }, { 6, 724, 2048 }, { 7, 725, 2048 }, { 7, 726, 2048 }, { 8, 727, 2048 },
2562 { 6, 728, 2048 }, { 7, 729, 2048 }, { 7, 730, 2048 }, { 8, 731, 2048 }, { 7, 732, 2048 }, { 8, 733, 2048 }, { 8, 734, 2048 }, { 9, 735, 2048 },
2563 { 5, 736, 2048 }, { 6, 737, 2048 }, { 6, 738, 2048 }, { 7, 739, 2048 }, { 6, 740, 2048 }, { 7, 741, 2048 }, { 7, 742, 2048 }, { 8, 743, 2048 },
2564 { 6, 744, 2048 }, { 7, 745, 2048 }, { 7, 746, 2048 }, { 8, 747, 2048 }, { 7, 748, 2048 }, { 8, 749, 2048 }, { 8, 750, 2048 }, { 9, 751, 2048 },
2565 { 6, 752, 2048 }, { 7, 753, 2048 }, { 7, 754, 2048 }, { 8, 755, 2048 }, { 7, 756, 2048 }, { 8, 757, 2048 }, { 8, 758, 2048 }, { 9, 759, 2048 },
2566 { 7, 760, 2048 }, { 8, 761, 2048 }, { 8, 762, 2048 }, { 9, 763, 2048 }, { 8, 764, 2048 }, { 9, 765, 2048 }, { 9, 766, 2048 }, { 10, 767, 2048 },
2567 { 3, 768, 2048 }, { 4, 769, 2048 }, { 4, 770, 2048 }, { 5, 771, 2048 }, { 4, 772, 2048 }, { 5, 773, 2048 }, { 5, 774, 2048 }, { 6, 775, 2048 },
2568 { 4, 776, 2048 }, { 5, 777, 2048 }, { 5, 778, 2048 }, { 6, 779, 2048 }, { 5, 780, 2048 }, { 6, 781, 2048 }, { 6, 782, 2048 }, { 7, 783, 2048 },
2569 { 4, 784, 2048 }, { 5, 785, 2048 }, { 5, 786, 2048 }, { 6, 787, 2048 }, { 5, 788, 2048 }, { 6, 789, 2048 }, { 6, 790, 2048 }, { 7, 791, 2048 },
2570 { 5, 792, 2048 }, { 6, 793, 2048 }, { 6, 794, 2048 }, { 7, 795, 2048 }, { 6, 796, 2048 }, { 7, 797, 2048 }, { 7, 798, 2048 }, { 8, 799, 2048 },
2571 { 4, 800, 2048 }, { 5, 801, 2048 }, { 5, 802, 2048 }, { 6, 803, 2048 }, { 5, 804, 2048 }, { 6, 805, 2048 }, { 6, 806, 2048 }, { 7, 807, 2048 },
2572 { 5, 808, 2048 }, { 6, 809, 2048 }, { 6, 810, 2048 }, { 7, 811, 2048 }, { 6, 812, 2048 }, { 7, 813, 2048 }, { 7, 814, 2048 }, { 8, 815, 2048 },
2573 { 5, 816, 2048 }, { 6, 817, 2048 }, { 6, 818, 2048 }, { 7, 819, 2048 }, { 6, 820, 2048 }, { 7, 821, 2048 }, { 7, 822, 2048 }, { 8, 823, 2048 },
2574 { 6, 824, 2048 }, { 7, 825, 2048 }, { 7, 826, 2048 }, { 8, 827, 2048 }, { 7, 828, 2048 }, { 8, 829, 2048 }, { 8, 830, 2048 }, { 9, 831, 2048 },
2575 { 4, 832, 2048 }, { 5, 833, 2048 }, { 5, 834, 2048 }, { 6, 835, 2048 }, { 5, 836, 2048 }, { 6, 837, 2048 }, { 6, 838, 2048 }, { 7, 839, 2048 },
2576 { 5, 840, 2048 }, { 6, 841, 2048 }, { 6, 842, 2048 }, { 7, 843, 2048 }, { 6, 844, 2048 }, { 7, 845, 2048 }, { 7, 846, 2048 }, { 8, 847, 2048 },
2577 { 5, 848, 2048 }, { 6, 849, 2048 }, { 6, 850, 2048 }, { 7, 851, 2048 }, { 6, 852, 2048 }, { 7, 853, 2048 }, { 7, 854, 2048 }, { 8, 855, 2048 },
2578 { 6, 856, 2048 }, { 7, 857, 2048 }, { 7, 858, 2048 }, { 8, 859, 2048 }, { 7, 860, 2048 }, { 8, 861, 2048 }, { 8, 862, 2048 }, { 9, 863, 2048 },
2579 { 5, 864, 2048 }, { 6, 865, 2048 }, { 6, 866, 2048 }, { 7, 867, 2048 }, { 6, 868, 2048 }, { 7, 869, 2048 }, { 7, 870, 2048 }, { 8, 871, 2048 },
2580 { 6, 872, 2048 }, { 7, 873, 2048 }, { 7, 874, 2048 }, { 8, 875, 2048 }, { 7, 876, 2048 }, { 8, 877, 2048 }, { 8, 878, 2048 }, { 9, 879, 2048 },
2581 { 6, 880, 2048 }, { 7, 881, 2048 }, { 7, 882, 2048 }, { 8, 883, 2048 }, { 7, 884, 2048 }, { 8, 885, 2048 }, { 8, 886, 2048 }, { 9, 887, 2048 },
2582 { 7, 888, 2048 }, { 8, 889, 2048 }, { 8, 890, 2048 }, { 9, 891, 2048 }, { 8, 892, 2048 }, { 9, 893, 2048 }, { 9, 894, 2048 }, { 10, 895, 2048 },
2583 { 4, 896, 2048 }, { 5, 897, 2048 }, { 5, 898, 2048 }, { 6, 899, 2048 }, { 5, 900, 2048 }, { 6, 901, 2048 }, { 6, 902, 2048 }, { 7, 903, 2048 },
2584 { 5, 904, 2048 }, { 6, 905, 2048 }, { 6, 906, 2048 }, { 7, 907, 2048 }, { 6, 908, 2048 }, { 7, 909, 2048 }, { 7, 910, 2048 }, { 8, 911, 2048 },
2585 { 5, 912, 2048 }, { 6, 913, 2048 }, { 6, 914, 2048 }, { 7, 915, 2048 }, { 6, 916, 2048 }, { 7, 917, 2048 }, { 7, 918, 2048 }, { 8, 919, 2048 },
2586 { 6, 920, 2048 }, { 7, 921, 2048 }, { 7, 922, 2048 }, { 8, 923, 2048 }, { 7, 924, 2048 }, { 8, 925, 2048 }, { 8, 926, 2048 }, { 9, 927, 2048 },
2587 { 5, 928, 2048 }, { 6, 929, 2048 }, { 6, 930, 2048 }, { 7, 931, 2048 }, { 6, 932, 2048 }, { 7, 933, 2048 }, { 7, 934, 2048 }, { 8, 935, 2048 },
2588 { 6, 936, 2048 }, { 7, 937, 2048 }, { 7, 938, 2048 }, { 8, 939, 2048 }, { 7, 940, 2048 }, { 8, 941, 2048 }, { 8, 942, 2048 }, { 9, 943, 2048 },
2589 { 6, 944, 2048 }, { 7, 945, 2048 }, { 7, 946, 2048 }, { 8, 947, 2048 }, { 7, 948, 2048 }, { 8, 949, 2048 }, { 8, 950, 2048 }, { 9, 951, 2048 },
2590 { 7, 952, 2048 }, { 8, 953, 2048 }, { 8, 954, 2048 }, { 9, 955, 2048 }, { 8, 956, 2048 }, { 9, 957, 2048 }, { 9, 958, 2048 }, { 10, 959, 2048 },
2591 { 5, 960, 2048 }, { 6, 961, 2048 }, { 6, 962, 2048 }, { 7, 963, 2048 }, { 6, 964, 2048 }, { 7, 965, 2048 }, { 7, 966, 2048 }, { 8, 967, 2048 },
2592 { 6, 968, 2048 }, { 7, 969, 2048 }, { 7, 970, 2048 }, { 8, 971, 2048 }, { 7, 972, 2048 }, { 8, 973, 2048 }, { 8, 974, 2048 }, { 9, 975, 2048 },
2593 { 6, 976, 2048 }, { 7, 977, 2048 }, { 7, 978, 2048 }, { 8, 979, 2048 }, { 7, 980, 2048 }, { 8, 981, 2048 }, { 8, 982, 2048 }, { 9, 983, 2048 },
2594 { 7, 984, 2048 }, { 8, 985, 2048 }, { 8, 986, 2048 }, { 9, 987, 2048 }, { 8, 988, 2048 }, { 9, 989, 2048 }, { 9, 990, 2048 }, { 10, 991, 2048 },
2595 { 6, 992, 2048 }, { 7, 993, 2048 }, { 7, 994, 2048 }, { 8, 995, 2048 }, { 7, 996, 2048 }, { 8, 997, 2048 }, { 8, 998, 2048 }, { 9, 999, 2048 },
2596 { 7, 1000, 2048 }, { 8, 1001, 2048 }, { 8, 1002, 2048 }, { 9, 1003, 2048 }, { 8, 1004, 2048 }, { 9, 1005, 2048 }, { 9, 1006, 2048 }, { 10, 1007, 2048 },
2597 { 7, 1008, 2048 }, { 8, 1009, 2048 }, { 8, 1010, 2048 }, { 9, 1011, 2048 }, { 8, 1012, 2048 }, { 9, 1013, 2048 }, { 9, 1014, 2048 }, { 10, 1015, 2048 },
2598 { 8, 1016, 2048 }, { 9, 1017, 2048 }, { 9, 1018, 2048 }, { 10, 1019, 2048 }, { 9, 1020, 2048 }, { 10, 1021, 2048 }, { 10, 1022, 2048 }, { 11, 1023, 2048 },
2599 { 2, 1024, 2048 }, { 3, 1025, 2048 }, { 3, 1026, 2048 }, { 4, 1027, 2048 }, { 3, 1028, 2048 }, { 4, 1029, 2048 }, { 4, 1030, 2048 }, { 5, 1031, 2048 },
2600 { 3, 1032, 2048 }, { 4, 1033, 2048 }, { 4, 1034, 2048 }, { 5, 1035, 2048 }, { 4, 1036, 2048 }, { 5, 1037, 2048 }, { 5, 1038, 2048 }, { 6, 1039, 2048 },
2601 { 3, 1040, 2048 }, { 4, 1041, 2048 }, { 4, 1042, 2048 }, { 5, 1043, 2048 }, { 4, 1044, 2048 }, { 5, 1045, 2048 }, { 5, 1046, 2048 }, { 6, 1047, 2048 },
2602 { 4, 1048, 2048 }, { 5, 1049, 2048 }, { 5, 1050, 2048 }, { 6, 1051, 2048 }, { 5, 1052, 2048 }, { 6, 1053, 2048 }, { 6, 1054, 2048 }, { 7, 1055, 2048 },
2603 { 3, 1056, 2048 }, { 4, 1057, 2048 }, { 4, 1058, 2048 }, { 5, 1059, 2048 }, { 4, 1060, 2048 }, { 5, 1061, 2048 }, { 5, 1062, 2048 }, { 6, 1063, 2048 },
2604 { 4, 1064, 2048 }, { 5, 1065, 2048 }, { 5, 1066, 2048 }, { 6, 1067, 2048 }, { 5, 1068, 2048 }, { 6, 1069, 2048 }, { 6, 1070, 2048 }, { 7, 1071, 2048 },
2605 { 4, 1072, 2048 }, { 5, 1073, 2048 }, { 5, 1074, 2048 }, { 6, 1075, 2048 }, { 5, 1076, 2048 }, { 6, 1077, 2048 }, { 6, 1078, 2048 }, { 7, 1079, 2048 },
2606 { 5, 1080, 2048 }, { 6, 1081, 2048 }, { 6, 1082, 2048 }, { 7, 1083, 2048 }, { 6, 1084, 2048 }, { 7, 1085, 2048 }, { 7, 1086, 2048 }, { 8, 1087, 2048 },
2607 { 3, 1088, 2048 }, { 4, 1089, 2048 }, { 4, 1090, 2048 }, { 5, 1091, 2048 }, { 4, 1092, 2048 }, { 5, 1093, 2048 }, { 5, 1094, 2048 }, { 6, 1095, 2048 },
2608 { 4, 1096, 2048 }, { 5, 1097, 2048 }, { 5, 1098, 2048 }, { 6, 1099, 2048 }, { 5, 1100, 2048 }, { 6, 1101, 2048 }, { 6, 1102, 2048 }, { 7, 1103, 2048 },
2609 { 4, 1104, 2048 }, { 5, 1105, 2048 }, { 5, 1106, 2048 }, { 6, 1107, 2048 }, { 5, 1108, 2048 }, { 6, 1109, 2048 }, { 6, 1110, 2048 }, { 7, 1111, 2048 },
2610 { 5, 1112, 2048 }, { 6, 1113, 2048 }, { 6, 1114, 2048 }, { 7, 1115, 2048 }, { 6, 1116, 2048 }, { 7, 1117, 2048 }, { 7, 1118, 2048 }, { 8, 1119, 2048 },
2611 { 4, 1120, 2048 }, { 5, 1121, 2048 }, { 5, 1122, 2048 }, { 6, 1123, 2048 }, { 5, 1124, 2048 }, { 6, 1125, 2048 }, { 6, 1126, 2048 }, { 7, 1127, 2048 },
2612 { 5, 1128, 2048 }, { 6, 1129, 2048 }, { 6, 1130, 2048 }, { 7, 1131, 2048 }, { 6, 1132, 2048 }, { 7, 1133, 2048 }, { 7, 1134, 2048 }, { 8, 1135, 2048 },
2613 { 5, 1136, 2048 }, { 6, 1137, 2048 }, { 6, 1138, 2048 }, { 7, 1139, 2048 }, { 6, 1140, 2048 }, { 7, 1141, 2048 }, { 7, 1142, 2048 }, { 8, 1143, 2048 },
2614 { 6, 1144, 2048 }, { 7, 1145, 2048 }, { 7, 1146, 2048 }, { 8, 1147, 2048 }, { 7, 1148, 2048 }, { 8, 1149, 2048 }, { 8, 1150, 2048 }, { 9, 1151, 2048 },
2615 { 3, 1152, 2048 }, { 4, 1153, 2048 }, { 4, 1154, 2048 }, { 5, 1155, 2048 }, { 4, 1156, 2048 }, { 5, 1157, 2048 }, { 5, 1158, 2048 }, { 6, 1159, 2048 },
2616 { 4, 1160, 2048 }, { 5, 1161, 2048 }, { 5, 1162, 2048 }, { 6, 1163, 2048 }, { 5, 1164, 2048 }, { 6, 1165, 2048 }, { 6, 1166, 2048 }, { 7, 1167, 2048 },
2617 { 4, 1168, 2048 }, { 5, 1169, 2048 }, { 5, 1170, 2048 }, { 6, 1171, 2048 }, { 5, 1172, 2048 }, { 6, 1173, 2048 }, { 6, 1174, 2048 }, { 7, 1175, 2048 },
2618 { 5, 1176, 2048 }, { 6, 1177, 2048 }, { 6, 1178, 2048 }, { 7, 1179, 2048 }, { 6, 1180, 2048 }, { 7, 1181, 2048 }, { 7, 1182, 2048 }, { 8, 1183, 2048 },
2619 { 4, 1184, 2048 }, { 5, 1185, 2048 }, { 5, 1186, 2048 }, { 6, 1187, 2048 }, { 5, 1188, 2048 }, { 6, 1189, 2048 }, { 6, 1190, 2048 }, { 7, 1191, 2048 },
2620 { 5, 1192, 2048 }, { 6, 1193, 2048 }, { 6, 1194, 2048 }, { 7, 1195, 2048 }, { 6, 1196, 2048 }, { 7, 1197, 2048 }, { 7, 1198, 2048 }, { 8, 1199, 2048 },
2621 { 5, 1200, 2048 }, { 6, 1201, 2048 }, { 6, 1202, 2048 }, { 7, 1203, 2048 }, { 6, 1204, 2048 }, { 7, 1205, 2048 }, { 7, 1206, 2048 }, { 8, 1207, 2048 },
2622 { 6, 1208, 2048 }, { 7, 1209, 2048 }, { 7, 1210, 2048 }, { 8, 1211, 2048 }, { 7, 1212, 2048 }, { 8, 1213, 2048 }, { 8, 1214, 2048 }, { 9, 1215, 2048 },
2623 { 4, 1216, 2048 }, { 5, 1217, 2048 }, { 5, 1218, 2048 }, { 6, 1219, 2048 }, { 5, 1220, 2048 }, { 6, 1221, 2048 }, { 6, 1222, 2048 }, { 7, 1223, 2048 },
2624 { 5, 1224, 2048 }, { 6, 1225, 2048 }, { 6, 1226, 2048 }, { 7, 1227, 2048 }, { 6, 1228, 2048 }, { 7, 1229, 2048 }, { 7, 1230, 2048 }, { 8, 1231, 2048 },
2625 { 5, 1232, 2048 }, { 6, 1233, 2048 }, { 6, 1234, 2048 }, { 7, 1235, 2048 }, { 6, 1236, 2048 }, { 7, 1237, 2048 }, { 7, 1238, 2048 }, { 8, 1239, 2048 },
2626 { 6, 1240, 2048 }, { 7, 1241, 2048 }, { 7, 1242, 2048 }, { 8, 1243, 2048 }, { 7, 1244, 2048 }, { 8, 1245, 2048 }, { 8, 1246, 2048 }, { 9, 1247, 2048 },
2627 { 5, 1248, 2048 }, { 6, 1249, 2048 }, { 6, 1250, 2048 }, { 7, 1251, 2048 }, { 6, 1252, 2048 }, { 7, 1253, 2048 }, { 7, 1254, 2048 }, { 8, 1255, 2048 },
2628 { 6, 1256, 2048 }, { 7, 1257, 2048 }, { 7, 1258, 2048 }, { 8, 1259, 2048 }, { 7, 1260, 2048 }, { 8, 1261, 2048 }, { 8, 1262, 2048 }, { 9, 1263, 2048 },
2629 { 6, 1264, 2048 }, { 7, 1265, 2048 }, { 7, 1266, 2048 }, { 8, 1267, 2048 }, { 7, 1268, 2048 }, { 8, 1269, 2048 }, { 8, 1270, 2048 }, { 9, 1271, 2048 },
2630 { 7, 1272, 2048 }, { 8, 1273, 2048 }, { 8, 1274, 2048 }, { 9, 1275, 2048 }, { 8, 1276, 2048 }, { 9, 1277, 2048 }, { 9, 1278, 2048 }, { 10, 1279, 2048 },
2631 { 3, 1280, 2048 }, { 4, 1281, 2048 }, { 4, 1282, 2048 }, { 5, 1283, 2048 }, { 4, 1284, 2048 }, { 5, 1285, 2048 }, { 5, 1286, 2048 }, { 6, 1287, 2048 },
2632 { 4, 1288, 2048 }, { 5, 1289, 2048 }, { 5, 1290, 2048 }, { 6, 1291, 2048 }, { 5, 1292, 2048 }, { 6, 1293, 2048 }, { 6, 1294, 2048 }, { 7, 1295, 2048 },
2633 { 4, 1296, 2048 }, { 5, 1297, 2048 }, { 5, 1298, 2048 }, { 6, 1299, 2048 }, { 5, 1300, 2048 }, { 6, 1301, 2048 }, { 6, 1302, 2048 }, { 7, 1303, 2048 },
2634 { 5, 1304, 2048 }, { 6, 1305, 2048 }, { 6, 1306, 2048 }, { 7, 1307, 2048 }, { 6, 1308, 2048 }, { 7, 1309, 2048 }, { 7, 1310, 2048 }, { 8, 1311, 2048 },
2635 { 4, 1312, 2048 }, { 5, 1313, 2048 }, { 5, 1314, 2048 }, { 6, 1315, 2048 }, { 5, 1316, 2048 }, { 6, 1317, 2048 }, { 6, 1318, 2048 }, { 7, 1319, 2048 },
2636 { 5, 1320, 2048 }, { 6, 1321, 2048 }, { 6, 1322, 2048 }, { 7, 1323, 2048 }, { 6, 1324, 2048 }, { 7, 1325, 2048 }, { 7, 1326, 2048 }, { 8, 1327, 2048 },
2637 { 5, 1328, 2048 }, { 6, 1329, 2048 }, { 6, 1330, 2048 }, { 7, 1331, 2048 }, { 6, 1332, 2048 }, { 7, 1333, 2048 }, { 7, 1334, 2048 }, { 8, 1335, 2048 },
2638 { 6, 1336, 2048 }, { 7, 1337, 2048 }, { 7, 1338, 2048 }, { 8, 1339, 2048 }, { 7, 1340, 2048 }, { 8, 1341, 2048 }, { 8, 1342, 2048 }, { 9, 1343, 2048 },
2639 { 4, 1344, 2048 }, { 5, 1345, 2048 }, { 5, 1346, 2048 }, { 6, 1347, 2048 }, { 5, 1348, 2048 }, { 6, 1349, 2048 }, { 6, 1350, 2048 }, { 7, 1351, 2048 },
2640 { 5, 1352, 2048 }, { 6, 1353, 2048 }, { 6, 1354, 2048 }, { 7, 1355, 2048 }, { 6, 1356, 2048 }, { 7, 1357, 2048 }, { 7, 1358, 2048 }, { 8, 1359, 2048 },
2641 { 5, 1360, 2048 }, { 6, 1361, 2048 }, { 6, 1362, 2048 }, { 7, 1363, 2048 }, { 6, 1364, 2048 }, { 7, 1365, 2048 }, { 7, 1366, 2048 }, { 8, 1367, 2048 },
2642 { 6, 1368, 2048 }, { 7, 1369, 2048 }, { 7, 1370, 2048 }, { 8, 1371, 2048 }, { 7, 1372, 2048 }, { 8, 1373, 2048 }, { 8, 1374, 2048 }, { 9, 1375, 2048 },
2643 { 5, 1376, 2048 }, { 6, 1377, 2048 }, { 6, 1378, 2048 }, { 7, 1379, 2048 }, { 6, 1380, 2048 }, { 7, 1381, 2048 }, { 7, 1382, 2048 }, { 8, 1383, 2048 },
2644 { 6, 1384, 2048 }, { 7, 1385, 2048 }, { 7, 1386, 2048 }, { 8, 1387, 2048 }, { 7, 1388, 2048 }, { 8, 1389, 2048 }, { 8, 1390, 2048 }, { 9, 1391, 2048 },
2645 { 6, 1392, 2048 }, { 7, 1393, 2048 }, { 7, 1394, 2048 }, { 8, 1395, 2048 }, { 7, 1396, 2048 }, { 8, 1397, 2048 }, { 8, 1398, 2048 }, { 9, 1399, 2048 },
2646 { 7, 1400, 2048 }, { 8, 1401, 2048 }, { 8, 1402, 2048 }, { 9, 1403, 2048 }, { 8, 1404, 2048 }, { 9, 1405, 2048 }, { 9, 1406, 2048 }, { 10, 1407, 2048 },
2647 { 4, 1408, 2048 }, { 5, 1409, 2048 }, { 5, 1410, 2048 }, { 6, 1411, 2048 }, { 5, 1412, 2048 }, { 6, 1413, 2048 }, { 6, 1414, 2048 }, { 7, 1415, 2048 },
2648 { 5, 1416, 2048 }, { 6, 1417, 2048 }, { 6, 1418, 2048 }, { 7, 1419, 2048 }, { 6, 1420, 2048 }, { 7, 1421, 2048 }, { 7, 1422, 2048 }, { 8, 1423, 2048 },
2649 { 5, 1424, 2048 }, { 6, 1425, 2048 }, { 6, 1426, 2048 }, { 7, 1427, 2048 }, { 6, 1428, 2048 }, { 7, 1429, 2048 }, { 7, 1430, 2048 }, { 8, 1431, 2048 },
2650 { 6, 1432, 2048 }, { 7, 1433, 2048 }, { 7, 1434, 2048 }, { 8, 1435, 2048 }, { 7, 1436, 2048 }, { 8, 1437, 2048 }, { 8, 1438, 2048 }, { 9, 1439, 2048 },
2651 { 5, 1440, 2048 }, { 6, 1441, 2048 }, { 6, 1442, 2048 }, { 7, 1443, 2048 }, { 6, 1444, 2048 }, { 7, 1445, 2048 }, { 7, 1446, 2048 }, { 8, 1447, 2048 },
2652 { 6, 1448, 2048 }, { 7, 1449, 2048 }, { 7, 1450, 2048 }, { 8, 1451, 2048 }, { 7, 1452, 2048 }, { 8, 1453, 2048 }, { 8, 1454, 2048 }, { 9, 1455, 2048 },
2653 { 6, 1456, 2048 }, { 7, 1457, 2048 }, { 7, 1458, 2048 }, { 8, 1459, 2048 }, { 7, 1460, 2048 }, { 8, 1461, 2048 }, { 8, 1462, 2048 }, { 9, 1463, 2048 },
2654 { 7, 1464, 2048 }, { 8, 1465, 2048 }, { 8, 1466, 2048 }, { 9, 1467, 2048 }, { 8, 1468, 2048 }, { 9, 1469, 2048 }, { 9, 1470, 2048 }, { 10, 1471, 2048 },
2655 { 5, 1472, 2048 }, { 6, 1473, 2048 }, { 6, 1474, 2048 }, { 7, 1475, 2048 }, { 6, 1476, 2048 }, { 7, 1477, 2048 }, { 7, 1478, 2048 }, { 8, 1479, 2048 },
2656 { 6, 1480, 2048 }, { 7, 1481, 2048 }, { 7, 1482, 2048 }, { 8, 1483, 2048 }, { 7, 1484, 2048 }, { 8, 1485, 2048 }, { 8, 1486, 2048 }, { 9, 1487, 2048 },
2657 { 6, 1488, 2048 }, { 7, 1489, 2048 }, { 7, 1490, 2048 }, { 8, 1491, 2048 }, { 7, 1492, 2048 }, { 8, 1493, 2048 }, { 8, 1494, 2048 }, { 9, 1495, 2048 },
2658 { 7, 1496, 2048 }, { 8, 1497, 2048 }, { 8, 1498, 2048 }, { 9, 1499, 2048 }, { 8, 1500, 2048 }, { 9, 1501, 2048 }, { 9, 1502, 2048 }, { 10, 1503, 2048 },
2659 { 6, 1504, 2048 }, { 7, 1505, 2048 }, { 7, 1506, 2048 }, { 8, 1507, 2048 }, { 7, 1508, 2048 }, { 8, 1509, 2048 }, { 8, 1510, 2048 }, { 9, 1511, 2048 },
2660 { 7, 1512, 2048 }, { 8, 1513, 2048 }, { 8, 1514, 2048 }, { 9, 1515, 2048 }, { 8, 1516, 2048 }, { 9, 1517, 2048 }, { 9, 1518, 2048 }, { 10, 1519, 2048 },
2661 { 7, 1520, 2048 }, { 8, 1521, 2048 }, { 8, 1522, 2048 }, { 9, 1523, 2048 }, { 8, 1524, 2048 }, { 9, 1525, 2048 }, { 9, 1526, 2048 }, { 10, 1527, 2048 },
2662 { 8, 1528, 2048 }, { 9, 1529, 2048 }, { 9, 1530, 2048 }, { 10, 1531, 2048 }, { 9, 1532, 2048 }, { 10, 1533, 2048 }, { 10, 1534, 2048 }, { 11, 1535, 2048 },
2663 { 3, 1536, 2048 }, { 4, 1537, 2048 }, { 4, 1538, 2048 }, { 5, 1539, 2048 }, { 4, 1540, 2048 }, { 5, 1541, 2048 }, { 5, 1542, 2048 }, { 6, 1543, 2048 },
2664 { 4, 1544, 2048 }, { 5, 1545, 2048 }, { 5, 1546, 2048 }, { 6, 1547, 2048 }, { 5, 1548, 2048 }, { 6, 1549, 2048 }, { 6, 1550, 2048 }, { 7, 1551, 2048 },
2665 { 4, 1552, 2048 }, { 5, 1553, 2048 }, { 5, 1554, 2048 }, { 6, 1555, 2048 }, { 5, 1556, 2048 }, { 6, 1557, 2048 }, { 6, 1558, 2048 }, { 7, 1559, 2048 },
2666 { 5, 1560, 2048 }, { 6, 1561, 2048 }, { 6, 1562, 2048 }, { 7, 1563, 2048 }, { 6, 1564, 2048 }, { 7, 1565, 2048 }, { 7, 1566, 2048 }, { 8, 1567, 2048 },
2667 { 4, 1568, 2048 }, { 5, 1569, 2048 }, { 5, 1570, 2048 }, { 6, 1571, 2048 }, { 5, 1572, 2048 }, { 6, 1573, 2048 }, { 6, 1574, 2048 }, { 7, 1575, 2048 },
2668 { 5, 1576, 2048 }, { 6, 1577, 2048 }, { 6, 1578, 2048 }, { 7, 1579, 2048 }, { 6, 1580, 2048 }, { 7, 1581, 2048 }, { 7, 1582, 2048 }, { 8, 1583, 2048 },
2669 { 5, 1584, 2048 }, { 6, 1585, 2048 }, { 6, 1586, 2048 }, { 7, 1587, 2048 }, { 6, 1588, 2048 }, { 7, 1589, 2048 }, { 7, 1590, 2048 }, { 8, 1591, 2048 },
2670 { 6, 1592, 2048 }, { 7, 1593, 2048 }, { 7, 1594, 2048 }, { 8, 1595, 2048 }, { 7, 1596, 2048 }, { 8, 1597, 2048 }, { 8, 1598, 2048 }, { 9, 1599, 2048 },
2671 { 4, 1600, 2048 }, { 5, 1601, 2048 }, { 5, 1602, 2048 }, { 6, 1603, 2048 }, { 5, 1604, 2048 }, { 6, 1605, 2048 }, { 6, 1606, 2048 }, { 7, 1607, 2048 },
2672 { 5, 1608, 2048 }, { 6, 1609, 2048 }, { 6, 1610, 2048 }, { 7, 1611, 2048 }, { 6, 1612, 2048 }, { 7, 1613, 2048 }, { 7, 1614, 2048 }, { 8, 1615, 2048 },
2673 { 5, 1616, 2048 }, { 6, 1617, 2048 }, { 6, 1618, 2048 }, { 7, 1619, 2048 }, { 6, 1620, 2048 }, { 7, 1621, 2048 }, { 7, 1622, 2048 }, { 8, 1623, 2048 },
2674 { 6, 1624, 2048 }, { 7, 1625, 2048 }, { 7, 1626, 2048 }, { 8, 1627, 2048 }, { 7, 1628, 2048 }, { 8, 1629, 2048 }, { 8, 1630, 2048 }, { 9, 1631, 2048 },
2675 { 5, 1632, 2048 }, { 6, 1633, 2048 }, { 6, 1634, 2048 }, { 7, 1635, 2048 }, { 6, 1636, 2048 }, { 7, 1637, 2048 }, { 7, 1638, 2048 }, { 8, 1639, 2048 },
2676 { 6, 1640, 2048 }, { 7, 1641, 2048 }, { 7, 1642, 2048 }, { 8, 1643, 2048 }, { 7, 1644, 2048 }, { 8, 1645, 2048 }, { 8, 1646, 2048 }, { 9, 1647, 2048 },
2677 { 6, 1648, 2048 }, { 7, 1649, 2048 }, { 7, 1650, 2048 }, { 8, 1651, 2048 }, { 7, 1652, 2048 }, { 8, 1653, 2048 }, { 8, 1654, 2048 }, { 9, 1655, 2048 },
2678 { 7, 1656, 2048 }, { 8, 1657, 2048 }, { 8, 1658, 2048 }, { 9, 1659, 2048 }, { 8, 1660, 2048 }, { 9, 1661, 2048 }, { 9, 1662, 2048 }, { 10, 1663, 2048 },
2679 { 4, 1664, 2048 }, { 5, 1665, 2048 }, { 5, 1666, 2048 }, { 6, 1667, 2048 }, { 5, 1668, 2048 }, { 6, 1669, 2048 }, { 6, 1670, 2048 }, { 7, 1671, 2048 },
2680 { 5, 1672, 2048 }, { 6, 1673, 2048 }, { 6, 1674, 2048 }, { 7, 1675, 2048 }, { 6, 1676, 2048 }, { 7, 1677, 2048 }, { 7, 1678, 2048 }, { 8, 1679, 2048 },
2681 { 5, 1680, 2048 }, { 6, 1681, 2048 }, { 6, 1682, 2048 }, { 7, 1683, 2048 }, { 6, 1684, 2048 }, { 7, 1685, 2048 }, { 7, 1686, 2048 }, { 8, 1687, 2048 },
2682 { 6, 1688, 2048 }, { 7, 1689, 2048 }, { 7, 1690, 2048 }, { 8, 1691, 2048 }, { 7, 1692, 2048 }, { 8, 1693, 2048 }, { 8, 1694, 2048 }, { 9, 1695, 2048 },
2683 { 5, 1696, 2048 }, { 6, 1697, 2048 }, { 6, 1698, 2048 }, { 7, 1699, 2048 }, { 6, 1700, 2048 }, { 7, 1701, 2048 }, { 7, 1702, 2048 }, { 8, 1703, 2048 },
2684 { 6, 1704, 2048 }, { 7, 1705, 2048 }, { 7, 1706, 2048 }, { 8, 1707, 2048 }, { 7, 1708, 2048 }, { 8, 1709, 2048 }, { 8, 1710, 2048 }, { 9, 1711, 2048 },
2685 { 6, 1712, 2048 }, { 7, 1713, 2048 }, { 7, 1714, 2048 }, { 8, 1715, 2048 }, { 7, 1716, 2048 }, { 8, 1717, 2048 }, { 8, 1718, 2048 }, { 9, 1719, 2048 },
2686 { 7, 1720, 2048 }, { 8, 1721, 2048 }, { 8, 1722, 2048 }, { 9, 1723, 2048 }, { 8, 1724, 2048 }, { 9, 1725, 2048 }, { 9, 1726, 2048 }, { 10, 1727, 2048 },
2687 { 5, 1728, 2048 }, { 6, 1729, 2048 }, { 6, 1730, 2048 }, { 7, 1731, 2048 }, { 6, 1732, 2048 }, { 7, 1733, 2048 }, { 7, 1734, 2048 }, { 8, 1735, 2048 },
2688 { 6, 1736, 2048 }, { 7, 1737, 2048 }, { 7, 1738, 2048 }, { 8, 1739, 2048 }, { 7, 1740, 2048 }, { 8, 1741, 2048 }, { 8, 1742, 2048 }, { 9, 1743, 2048 },
2689 { 6, 1744, 2048 }, { 7, 1745, 2048 }, { 7, 1746, 2048 }, { 8, 1747, 2048 }, { 7, 1748, 2048 }, { 8, 1749, 2048 }, { 8, 1750, 2048 }, { 9, 1751, 2048 },
2690 { 7, 1752, 2048 }, { 8, 1753, 2048 }, { 8, 1754, 2048 }, { 9, 1755, 2048 }, { 8, 1756, 2048 }, { 9, 1757, 2048 }, { 9, 1758, 2048 }, { 10, 1759, 2048 },
2691 { 6, 1760, 2048 }, { 7, 1761, 2048 }, { 7, 1762, 2048 }, { 8, 1763, 2048 }, { 7, 1764, 2048 }, { 8, 1765, 2048 }, { 8, 1766, 2048 }, { 9, 1767, 2048 },
2692 { 7, 1768, 2048 }, { 8, 1769, 2048 }, { 8, 1770, 2048 }, { 9, 1771, 2048 }, { 8, 1772, 2048 }, { 9, 1773, 2048 }, { 9, 1774, 2048 }, { 10, 1775, 2048 },
2693 { 7, 1776, 2048 }, { 8, 1777, 2048 }, { 8, 1778, 2048 }, { 9, 1779, 2048 }, { 8, 1780, 2048 }, { 9, 1781, 2048 }, { 9, 1782, 2048 }, { 10, 1783, 2048 },
2694 { 8, 1784, 2048 }, { 9, 1785, 2048 }, { 9, 1786, 2048 }, { 10, 1787, 2048 }, { 9, 1788, 2048 }, { 10, 1789, 2048 }, { 10, 1790, 2048 }, { 11, 1791, 2048 },
2695 { 4, 1792, 2048 }, { 5, 1793, 2048 }, { 5, 1794, 2048 }, { 6, 1795, 2048 }, { 5, 1796, 2048 }, { 6, 1797, 2048 }, { 6, 1798, 2048 }, { 7, 1799, 2048 },
2696 { 5, 1800, 2048 }, { 6, 1801, 2048 }, { 6, 1802, 2048 }, { 7, 1803, 2048 }, { 6, 1804, 2048 }, { 7, 1805, 2048 }, { 7, 1806, 2048 }, { 8, 1807, 2048 },
2697 { 5, 1808, 2048 }, { 6, 1809, 2048 }, { 6, 1810, 2048 }, { 7, 1811, 2048 }, { 6, 1812, 2048 }, { 7, 1813, 2048 }, { 7, 1814, 2048 }, { 8, 1815, 2048 },
2698 { 6, 1816, 2048 }, { 7, 1817, 2048 }, { 7, 1818, 2048 }, { 8, 1819, 2048 }, { 7, 1820, 2048 }, { 8, 1821, 2048 }, { 8, 1822, 2048 }, { 9, 1823, 2048 },
2699 { 5, 1824, 2048 }, { 6, 1825, 2048 }, { 6, 1826, 2048 }, { 7, 1827, 2048 }, { 6, 1828, 2048 }, { 7, 1829, 2048 }, { 7, 1830, 2048 }, { 8, 1831, 2048 },
2700 { 6, 1832, 2048 }, { 7, 1833, 2048 }, { 7, 1834, 2048 }, { 8, 1835, 2048 }, { 7, 1836, 2048 }, { 8, 1837, 2048 }, { 8, 1838, 2048 }, { 9, 1839, 2048 },
2701 { 6, 1840, 2048 }, { 7, 1841, 2048 }, { 7, 1842, 2048 }, { 8, 1843, 2048 }, { 7, 1844, 2048 }, { 8, 1845, 2048 }, { 8, 1846, 2048 }, { 9, 1847, 2048 },
2702 { 7, 1848, 2048 }, { 8, 1849, 2048 }, { 8, 1850, 2048 }, { 9, 1851, 2048 }, { 8, 1852, 2048 }, { 9, 1853, 2048 }, { 9, 1854, 2048 }, { 10, 1855, 2048 },
2703 { 5, 1856, 2048 }, { 6, 1857, 2048 }, { 6, 1858, 2048 }, { 7, 1859, 2048 }, { 6, 1860, 2048 }, { 7, 1861, 2048 }, { 7, 1862, 2048 }, { 8, 1863, 2048 },
2704 { 6, 1864, 2048 }, { 7, 1865, 2048 }, { 7, 1866, 2048 }, { 8, 1867, 2048 }, { 7, 1868, 2048 }, { 8, 1869, 2048 }, { 8, 1870, 2048 }, { 9, 1871, 2048 },
2705 { 6, 1872, 2048 }, { 7, 1873, 2048 }, { 7, 1874, 2048 }, { 8, 1875, 2048 }, { 7, 1876, 2048 }, { 8, 1877, 2048 }, { 8, 1878, 2048 }, { 9, 1879, 2048 },
2706 { 7, 1880, 2048 }, { 8, 1881, 2048 }, { 8, 1882, 2048 }, { 9, 1883, 2048 }, { 8, 1884, 2048 }, { 9, 1885, 2048 }, { 9, 1886, 2048 }, { 10, 1887, 2048 },
2707 { 6, 1888, 2048 }, { 7, 1889, 2048 }, { 7, 1890, 2048 }, { 8, 1891, 2048 }, { 7, 1892, 2048 }, { 8, 1893, 2048 }, { 8, 1894, 2048 }, { 9, 1895, 2048 },
2708 { 7, 1896, 2048 }, { 8, 1897, 2048 }, { 8, 1898, 2048 }, { 9, 1899, 2048 }, { 8, 1900, 2048 }, { 9, 1901, 2048 }, { 9, 1902, 2048 }, { 10, 1903, 2048 },
2709 { 7, 1904, 2048 }, { 8, 1905, 2048 }, { 8, 1906, 2048 }, { 9, 1907, 2048 }, { 8, 1908, 2048 }, { 9, 1909, 2048 }, { 9, 1910, 2048 }, { 10, 1911, 2048 },
2710 { 8, 1912, 2048 }, { 9, 1913, 2048 }, { 9, 1914, 2048 }, { 10, 1915, 2048 }, { 9, 1916, 2048 }, { 10, 1917, 2048 }, { 10, 1918, 2048 }, { 11, 1919, 2048 },
2711 { 5, 1920, 2048 }, { 6, 1921, 2048 }, { 6, 1922, 2048 }, { 7, 1923, 2048 }, { 6, 1924, 2048 }, { 7, 1925, 2048 }, { 7, 1926, 2048 }, { 8, 1927, 2048 },
2712 { 6, 1928, 2048 }, { 7, 1929, 2048 }, { 7, 1930, 2048 }, { 8, 1931, 2048 }, { 7, 1932, 2048 }, { 8, 1933, 2048 }, { 8, 1934, 2048 }, { 9, 1935, 2048 },
2713 { 6, 1936, 2048 }, { 7, 1937, 2048 }, { 7, 1938, 2048 }, { 8, 1939, 2048 }, { 7, 1940, 2048 }, { 8, 1941, 2048 }, { 8, 1942, 2048 }, { 9, 1943, 2048 },
2714 { 7, 1944, 2048 }, { 8, 1945, 2048 }, { 8, 1946, 2048 }, { 9, 1947, 2048 }, { 8, 1948, 2048 }, { 9, 1949, 2048 }, { 9, 1950, 2048 }, { 10, 1951, 2048 },
2715 { 6, 1952, 2048 }, { 7, 1953, 2048 }, { 7, 1954, 2048 }, { 8, 1955, 2048 }, { 7, 1956, 2048 }, { 8, 1957, 2048 }, { 8, 1958, 2048 }, { 9, 1959, 2048 },
2716 { 7, 1960, 2048 }, { 8, 1961, 2048 }, { 8, 1962, 2048 }, { 9, 1963, 2048 }, { 8, 1964, 2048 }, { 9, 1965, 2048 }, { 9, 1966, 2048 }, { 10, 1967, 2048 },
2717 { 7, 1968, 2048 }, { 8, 1969, 2048 }, { 8, 1970, 2048 }, { 9, 1971, 2048 }, { 8, 1972, 2048 }, { 9, 1973, 2048 }, { 9, 1974, 2048 }, { 10, 1975, 2048 },
2718 { 8, 1976, 2048 }, { 9, 1977, 2048 }, { 9, 1978, 2048 }, { 10, 1979, 2048 }, { 9, 1980, 2048 }, { 10, 1981, 2048 }, { 10, 1982, 2048 }, { 11, 1983, 2048 },
2719 { 6, 1984, 2048 }, { 7, 1985, 2048 }, { 7, 1986, 2048 }, { 8, 1987, 2048 }, { 7, 1988, 2048 }, { 8, 1989, 2048 }, { 8, 1990, 2048 }, { 9, 1991, 2048 },
2720 { 7, 1992, 2048 }, { 8, 1993, 2048 }, { 8, 1994, 2048 }, { 9, 1995, 2048 }, { 8, 1996, 2048 }, { 9, 1997, 2048 }, { 9, 1998, 2048 }, { 10, 1999, 2048 },
2721 { 7, 2000, 2048 }, { 8, 2001, 2048 }, { 8, 2002, 2048 }, { 9, 2003, 2048 }, { 8, 2004, 2048 }, { 9, 2005, 2048 }, { 9, 2006, 2048 }, { 10, 2007, 2048 },
2722 { 8, 2008, 2048 }, { 9, 2009, 2048 }, { 9, 2010, 2048 }, { 10, 2011, 2048 }, { 9, 2012, 2048 }, { 10, 2013, 2048 }, { 10, 2014, 2048 }, { 11, 2015, 2048 },
2723 { 7, 2016, 2048 }, { 8, 2017, 2048 }, { 8, 2018, 2048 }, { 9, 2019, 2048 }, { 8, 2020, 2048 }, { 9, 2021, 2048 }, { 9, 2022, 2048 }, { 10, 2023, 2048 },
2724 { 8, 2024, 2048 }, { 9, 2025, 2048 }, { 9, 2026, 2048 }, { 10, 2027, 2048 }, { 9, 2028, 2048 }, { 10, 2029, 2048 }, { 10, 2030, 2048 }, { 11, 2031, 2048 },
2725 { 8, 2032, 2048 }, { 9, 2033, 2048 }, { 9, 2034, 2048 }, { 10, 2035, 2048 }, { 9, 2036, 2048 }, { 10, 2037, 2048 }, { 10, 2038, 2048 }, { 11, 2039, 2048 },
2726 { 9, 2040, 2048 }, { 10, 2041, 2048 }, { 10, 2042, 2048 }, { 11, 2043, 2048 }, { 10, 2044, 2048 }, { 11, 2045, 2048 }, { 11, 2046, 2048 }, { 12, 2047, 2048 },
2735 /* find a hole and free as required, return -1 if no hole found */
2736 static int find_hole(void)
2740 for (z = -1, y = INT_MAX, x = 0; x < FP_ENTRIES; x++) {
2741 if (fp_cache[x].lru_count < y && fp_cache[x].lock == 0) {
2743 y = fp_cache[x].lru_count;
2748 for (x = 0; x < FP_ENTRIES; x++) {
2749 if (fp_cache[x].lru_count > 3) {
2750 --(fp_cache[x].lru_count);
2755 if (z >= 0 && fp_cache[z].g) {
2756 mp_clear(&fp_cache[z].mu);
2757 ecc_del_point(fp_cache[z].g);
2758 fp_cache[z].g = NULL;
2759 for (x = 0; x < (1U<<FP_LUT); x++) {
2760 ecc_del_point(fp_cache[z].LUT[x]);
2761 fp_cache[z].LUT[x] = NULL;
2763 fp_cache[z].lru_count = 0;
2768 /* determine if a base is already in the cache and if so, where */
2769 static int find_base(ecc_point* g)
2772 for (x = 0; x < FP_ENTRIES; x++) {
2773 if (fp_cache[x].g != NULL &&
2774 mp_cmp(&fp_cache[x].g->x, &g->x) == MP_EQ &&
2775 mp_cmp(&fp_cache[x].g->y, &g->y) == MP_EQ &&
2776 mp_cmp(&fp_cache[x].g->z, &g->z) == MP_EQ) {
2780 if (x == FP_ENTRIES) {
2786 /* add a new base to the cache */
2787 static int add_entry(int idx, ecc_point *g)
2791 /* allocate base and LUT */
2792 fp_cache[idx].g = ecc_new_point();
2793 if (fp_cache[idx].g == NULL) {
2798 if ((mp_copy(&g->x, &fp_cache[idx].g->x) != MP_OKAY) ||
2799 (mp_copy(&g->y, &fp_cache[idx].g->y) != MP_OKAY) ||
2800 (mp_copy(&g->z, &fp_cache[idx].g->z) != MP_OKAY)) {
2801 ecc_del_point(fp_cache[idx].g);
2802 fp_cache[idx].g = NULL;
2806 for (x = 0; x < (1U<<FP_LUT); x++) {
2807 fp_cache[idx].LUT[x] = ecc_new_point();
2808 if (fp_cache[idx].LUT[x] == NULL) {
2809 for (y = 0; y < x; y++) {
2810 ecc_del_point(fp_cache[idx].LUT[y]);
2811 fp_cache[idx].LUT[y] = NULL;
2813 ecc_del_point(fp_cache[idx].g);
2814 fp_cache[idx].g = NULL;
2815 fp_cache[idx].lru_count = 0;
2820 fp_cache[idx].lru_count = 0;
2825 /* build the LUT by spacing the bits of the input by #modulus/FP_LUT bits apart
2827 * The algorithm builds patterns in increasing bit order by first making all
2828 * single bit input patterns, then all two bit input patterns and so on
2830 static int build_lut(int idx, mp_int* modulus, mp_digit* mp, mp_int* mu)
2832 unsigned x, y, err, bitlen, lut_gap;
2835 if (mp_init(&tmp) != MP_OKAY)
2838 /* sanity check to make sure lut_order table is of correct size,
2839 should compile out to a NOP if true */
2840 if ((sizeof(lut_orders) / sizeof(lut_orders[0])) < (1U<<FP_LUT)) {
2844 /* get bitlen and round up to next multiple of FP_LUT */
2845 bitlen = mp_unsigned_bin_size(modulus) << 3;
2846 x = bitlen % FP_LUT;
2848 bitlen += FP_LUT - x;
2850 lut_gap = bitlen / FP_LUT;
2853 err = mp_init_copy(&fp_cache[idx].mu, mu);
2857 if (err == MP_OKAY) {
2858 if ((mp_mulmod(&fp_cache[idx].g->x, mu, modulus,
2859 &fp_cache[idx].LUT[1]->x) != MP_OKAY) ||
2860 (mp_mulmod(&fp_cache[idx].g->y, mu, modulus,
2861 &fp_cache[idx].LUT[1]->y) != MP_OKAY) ||
2862 (mp_mulmod(&fp_cache[idx].g->z, mu, modulus,
2863 &fp_cache[idx].LUT[1]->z) != MP_OKAY)) {
2868 /* make all single bit entries */
2869 for (x = 1; x < FP_LUT; x++) {
2872 if ((mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->x,
2873 &fp_cache[idx].LUT[1<<x]->x) != MP_OKAY) ||
2874 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->y,
2875 &fp_cache[idx].LUT[1<<x]->y) != MP_OKAY) ||
2876 (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->z,
2877 &fp_cache[idx].LUT[1<<x]->z) != MP_OKAY)){
2882 /* now double it bitlen/FP_LUT times */
2883 for (y = 0; y < lut_gap; y++) {
2884 if ((err = ecc_projective_dbl_point(fp_cache[idx].LUT[1<<x],
2885 fp_cache[idx].LUT[1<<x], modulus, mp)) != MP_OKAY) {
2892 /* now make all entries in increase order of hamming weight */
2893 for (x = 2; x <= FP_LUT; x++) {
2896 for (y = 0; y < (1UL<<FP_LUT); y++) {
2899 if (lut_orders[y].ham != (int)x) continue;
2901 /* perform the add */
2902 if ((err = ecc_projective_add_point(
2903 fp_cache[idx].LUT[lut_orders[y].terma],
2904 fp_cache[idx].LUT[lut_orders[y].termb],
2905 fp_cache[idx].LUT[y], modulus, mp)) != MP_OKAY) {
2911 /* now map all entries back to affine space to make point addition faster */
2912 for (x = 1; x < (1UL<<FP_LUT); x++) {
2916 /* convert z to normal from montgomery */
2917 err = mp_montgomery_reduce(&fp_cache[idx].LUT[x]->z, modulus, *mp);
2921 err = mp_invmod(&fp_cache[idx].LUT[x]->z, modulus,
2922 &fp_cache[idx].LUT[x]->z);
2926 err = mp_sqrmod(&fp_cache[idx].LUT[x]->z, modulus, &tmp);
2930 err = mp_mulmod(&fp_cache[idx].LUT[x]->x, &tmp, modulus,
2931 &fp_cache[idx].LUT[x]->x);
2935 err = mp_mulmod(&tmp, &fp_cache[idx].LUT[x]->z, modulus, &tmp);
2939 err = mp_mulmod(&fp_cache[idx].LUT[x]->y, &tmp, modulus,
2940 &fp_cache[idx].LUT[x]->y);
2944 mp_clear(&fp_cache[idx].LUT[x]->z);
2952 for (y = 0; y < (1U<<FP_LUT); y++) {
2953 ecc_del_point(fp_cache[idx].LUT[y]);
2954 fp_cache[idx].LUT[y] = NULL;
2956 ecc_del_point(fp_cache[idx].g);
2957 fp_cache[idx].g = NULL;
2958 fp_cache[idx].lru_count = 0;
2959 mp_clear(&fp_cache[idx].mu);
2965 /* perform a fixed point ECC mulmod */
2966 static int accel_fp_mul(int idx, mp_int* k, ecc_point *R, mp_int* modulus,
2967 mp_digit* mp, int map)
2971 #ifdef CYASSL_SMALL_STACK
2974 unsigned char kb[128];
2977 unsigned y, z, err, bitlen, bitpos, lut_gap, first;
2980 if (mp_init(&tk) != MP_OKAY)
2983 /* if it's smaller than modulus we fine */
2984 if (mp_unsigned_bin_size(k) > mp_unsigned_bin_size(modulus)) {
2986 if (mp_init(&order) != MP_OKAY) {
2992 y = mp_unsigned_bin_size(modulus);
2993 for (x = 0; ecc_sets[x].size; x++) {
2994 if (y <= (unsigned)ecc_sets[x].size) break;
2997 /* back off if we are on the 521 bit curve */
3000 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3006 /* k must be less than modulus */
3007 if (mp_cmp(k, &order) != MP_LT) {
3008 if ((err = mp_mod(k, &order, &tk)) != MP_OKAY) {
3021 /* get bitlen and round up to next multiple of FP_LUT */
3022 bitlen = mp_unsigned_bin_size(modulus) << 3;
3023 x = bitlen % FP_LUT;
3025 bitlen += FP_LUT - x;
3027 lut_gap = bitlen / FP_LUT;
3029 /* get the k value */
3030 if (mp_unsigned_bin_size(&tk) > (int)(KB_SIZE - 2)) {
3036 #ifdef CYASSL_SMALL_STACK
3037 kb = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3042 XMEMSET(kb, 0, KB_SIZE);
3043 if ((err = mp_to_unsigned_bin(&tk, kb)) != MP_OKAY) {
3047 /* let's reverse kb so it's little endian */
3049 y = mp_unsigned_bin_size(&tk) - 1;
3052 while ((unsigned)x < y) {
3053 z = kb[x]; kb[x] = kb[y]; kb[y] = z;
3057 /* at this point we can start, yipee */
3059 for (x = lut_gap-1; x >= 0; x--) {
3060 /* extract FP_LUT bits from kb spread out by lut_gap bits and offset
3061 by x bits from the start */
3063 for (y = z = 0; y < FP_LUT; y++) {
3064 z |= ((kb[bitpos>>3] >> (bitpos&7)) & 1) << y;
3065 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid
3066 the mult in each loop */
3069 /* double if not first */
3071 if ((err = ecc_projective_dbl_point(R, R, modulus,
3077 /* add if not first, otherwise copy */
3079 if ((err = ecc_projective_add_point(R, fp_cache[idx].LUT[z], R,
3080 modulus, mp)) != MP_OKAY) {
3084 if ((mp_copy(&fp_cache[idx].LUT[z]->x, &R->x) != MP_OKAY) ||
3085 (mp_copy(&fp_cache[idx].LUT[z]->y, &R->y) != MP_OKAY) ||
3086 (mp_copy(&fp_cache[idx].mu, &R->z) != MP_OKAY)) {
3095 if (err == MP_OKAY) {
3097 XMEMSET(kb, 0, KB_SIZE);
3098 /* map R back from projective space */
3100 err = ecc_map(R, modulus, mp);
3106 #ifdef CYASSL_SMALL_STACK
3107 XFREE(kb, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3116 /* perform a fixed point ECC mulmod */
3117 static int accel_fp_mul2add(int idx1, int idx2,
3118 mp_int* kA, mp_int* kB,
3119 ecc_point *R, mp_int* modulus, mp_digit* mp)
3123 #ifdef CYASSL_SMALL_STACK
3124 unsigned char* kb[2];
3126 unsigned char kb[2][128];
3129 unsigned y, z, err, bitlen, bitpos, lut_gap, first, zA, zB;
3134 if (mp_init_multi(&tka, &tkb, 0, 0, 0, 0) != MP_OKAY)
3137 /* if it's smaller than modulus we fine */
3138 if (mp_unsigned_bin_size(kA) > mp_unsigned_bin_size(modulus)) {
3140 y = mp_unsigned_bin_size(modulus);
3141 for (x = 0; ecc_sets[x].size; x++) {
3142 if (y <= (unsigned)ecc_sets[x].size) break;
3145 /* back off if we are on the 521 bit curve */
3148 if ((err = mp_init(&order)) != MP_OKAY) {
3153 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3160 /* kA must be less than modulus */
3161 if (mp_cmp(kA, &order) != MP_LT) {
3162 if ((err = mp_mod(kA, &order, &tka)) != MP_OKAY) {
3176 /* if it's smaller than modulus we fine */
3177 if (mp_unsigned_bin_size(kB) > mp_unsigned_bin_size(modulus)) {
3179 y = mp_unsigned_bin_size(modulus);
3180 for (x = 0; ecc_sets[x].size; x++) {
3181 if (y <= (unsigned)ecc_sets[x].size) break;
3184 /* back off if we are on the 521 bit curve */
3187 if ((err = mp_init(&order)) != MP_OKAY) {
3192 if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3199 /* kB must be less than modulus */
3200 if (mp_cmp(kB, &order) != MP_LT) {
3201 if ((err = mp_mod(kB, &order, &tkb)) != MP_OKAY) {
3215 /* get bitlen and round up to next multiple of FP_LUT */
3216 bitlen = mp_unsigned_bin_size(modulus) << 3;
3217 x = bitlen % FP_LUT;
3219 bitlen += FP_LUT - x;
3221 lut_gap = bitlen / FP_LUT;
3223 /* get the k value */
3224 if ((mp_unsigned_bin_size(&tka) > (int)(KB_SIZE - 2)) ||
3225 (mp_unsigned_bin_size(&tkb) > (int)(KB_SIZE - 2)) ) {
3232 #ifdef CYASSL_SMALL_STACK
3233 kb[0] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3238 XMEMSET(kb[0], 0, KB_SIZE);
3239 if ((err = mp_to_unsigned_bin(&tka, kb[0])) != MP_OKAY) {
3242 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3246 /* let's reverse kb so it's little endian */
3248 y = mp_unsigned_bin_size(&tka) - 1;
3250 while ((unsigned)x < y) {
3251 z = kb[0][x]; kb[0][x] = kb[0][y]; kb[0][y] = z;
3256 #ifdef CYASSL_SMALL_STACK
3257 kb[1] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3258 if (kb[1] == NULL) {
3259 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3264 XMEMSET(kb[1], 0, KB_SIZE);
3265 if ((err = mp_to_unsigned_bin(&tkb, kb[1])) != MP_OKAY) {
3270 y = mp_unsigned_bin_size(&tkb) - 1;
3272 while ((unsigned)x < y) {
3273 z = kb[1][x]; kb[1][x] = kb[1][y]; kb[1][y] = z;
3277 /* at this point we can start, yipee */
3279 for (x = lut_gap-1; x >= 0; x--) {
3280 /* extract FP_LUT bits from kb spread out by lut_gap bits and
3281 offset by x bits from the start */
3283 for (y = zA = zB = 0; y < FP_LUT; y++) {
3284 zA |= ((kb[0][bitpos>>3] >> (bitpos&7)) & 1) << y;
3285 zB |= ((kb[1][bitpos>>3] >> (bitpos&7)) & 1) << y;
3286 bitpos += lut_gap; /* it's y*lut_gap + x, but here we can avoid
3287 the mult in each loop */
3290 /* double if not first */
3292 if ((err = ecc_projective_dbl_point(R, R, modulus,
3298 /* add if not first, otherwise copy */
3301 if ((err = ecc_projective_add_point(R, fp_cache[idx1].LUT[zA],
3302 R, modulus, mp)) != MP_OKAY) {
3307 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB],
3308 R, modulus, mp)) != MP_OKAY) {
3314 if ((mp_copy(&fp_cache[idx1].LUT[zA]->x, &R->x) != MP_OKAY) ||
3315 (mp_copy(&fp_cache[idx1].LUT[zA]->y, &R->y) != MP_OKAY) ||
3316 (mp_copy(&fp_cache[idx1].mu, &R->z) != MP_OKAY)) {
3322 if (zB && first == 0) {
3324 if ((err = ecc_projective_add_point(R,
3325 fp_cache[idx2].LUT[zB], R, modulus, mp)) != MP_OKAY){
3329 } else if (zB && first == 1) {
3330 if ((mp_copy(&fp_cache[idx2].LUT[zB]->x, &R->x) != MP_OKAY) ||
3331 (mp_copy(&fp_cache[idx2].LUT[zB]->y, &R->y) != MP_OKAY) ||
3332 (mp_copy(&fp_cache[idx2].mu, &R->z) != MP_OKAY)) {
3342 XMEMSET(kb[0], 0, KB_SIZE);
3343 XMEMSET(kb[1], 0, KB_SIZE);
3345 #ifdef CYASSL_SMALL_STACK
3346 XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3347 XFREE(kb[1], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3352 return ecc_map(R, modulus, mp);
3355 /** ECC Fixed Point mulmod global
3356 Computes kA*A + kB*B = C using Shamir's Trick
3357 A First point to multiply
3358 kA What to multiple A by
3359 B Second point to multiply
3360 kB What to multiple B by
3361 C [out] Destination point (can overlap with A or B)
3362 modulus Modulus for curve
3363 return MP_OKAY on success
3365 int ecc_mul2add(ecc_point* A, mp_int* kA,
3366 ecc_point* B, mp_int* kB,
3367 ecc_point* C, mp_int* modulus)
3369 int idx1 = -1, idx2 = -1, err = MP_OKAY, mpInit = 0;
3377 #ifndef HAVE_THREAD_LS
3378 if (initMutex == 0) {
3379 InitMutex(&ecc_fp_lock);
3382 if (LockMutex(&ecc_fp_lock) != 0)
3384 #endif /* HAVE_THREAD_LS */
3387 idx1 = find_base(A);
3391 /* find hole and add it */
3392 if ((idx1 = find_hole()) >= 0) {
3393 err = add_entry(idx1, A);
3396 if (err == MP_OKAY && idx1 != -1) {
3398 ++(fp_cache[idx1].lru_count);
3403 idx2 = find_base(B);
3405 if (err == MP_OKAY) {
3408 /* find hole and add it */
3409 if ((idx2 = find_hole()) >= 0)
3410 err = add_entry(idx2, B);
3414 if (err == MP_OKAY && idx2 != -1) {
3416 ++(fp_cache[idx2].lru_count);
3419 if (err == MP_OKAY) {
3420 /* if it's 2 build the LUT, if it's higher just use the LUT */
3421 if (idx1 >= 0 && fp_cache[idx1].lru_count == 2) {
3423 err = mp_montgomery_setup(modulus, &mp);
3425 if (err == MP_OKAY) {
3427 err = mp_montgomery_calc_normalization(&mu, modulus);
3432 err = build_lut(idx1, modulus, &mp, &mu);
3436 if (err == MP_OKAY) {
3437 /* if it's 2 build the LUT, if it's higher just use the LUT */
3438 if (idx2 >= 0 && fp_cache[idx2].lru_count == 2) {
3441 err = mp_montgomery_setup(modulus, &mp);
3442 if (err == MP_OKAY) {
3444 err = mp_montgomery_calc_normalization(&mu, modulus);
3450 err = build_lut(idx2, modulus, &mp, &mu);
3455 if (err == MP_OKAY) {
3456 if (idx1 >=0 && idx2 >= 0 && fp_cache[idx1].lru_count >= 2 &&
3457 fp_cache[idx2].lru_count >= 2) {
3460 err = mp_montgomery_setup(modulus, &mp);
3463 err = accel_fp_mul2add(idx1, idx2, kA, kB, C, modulus, &mp);
3465 err = normal_ecc_mul2add(A, kA, B, kB, C, modulus);
3469 #ifndef HAVE_THREAD_LS
3470 UnLockMutex(&ecc_fp_lock);
3471 #endif /* HAVE_THREAD_LS */
3478 /** ECC Fixed Point mulmod global
3480 G Base point to multiply
3481 R [out] Destination of product
3482 modulus The modulus for the curve
3483 map [boolean] If non-zero maps the point back to affine co-ordinates,
3484 otherwise it's left in jacobian-montgomery form
3485 return MP_OKAY if successful
3487 int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
3490 int idx, err = MP_OKAY;
3495 if (mp_init(&mu) != MP_OKAY)
3498 #ifndef HAVE_THREAD_LS
3499 if (initMutex == 0) {
3500 InitMutex(&ecc_fp_lock);
3504 if (LockMutex(&ecc_fp_lock) != 0)
3506 #endif /* HAVE_THREAD_LS */
3513 /* find hole and add it */
3517 err = add_entry(idx, G);
3519 if (err == MP_OKAY && idx != -1) {
3521 ++(fp_cache[idx].lru_count);
3525 if (err == MP_OKAY) {
3526 /* if it's 2 build the LUT, if it's higher just use the LUT */
3527 if (idx >= 0 && fp_cache[idx].lru_count == 2) {
3529 err = mp_montgomery_setup(modulus, &mp);
3531 if (err == MP_OKAY) {
3534 err = mp_montgomery_calc_normalization(&mu, modulus);
3539 err = build_lut(idx, modulus, &mp, &mu);
3543 if (err == MP_OKAY) {
3544 if (idx >= 0 && fp_cache[idx].lru_count >= 2) {
3547 err = mp_montgomery_setup(modulus, &mp);
3550 err = accel_fp_mul(idx, k, R, modulus, &mp, map);
3552 err = normal_ecc_mulmod(k, G, R, modulus, map);
3556 #ifndef HAVE_THREAD_LS
3557 UnLockMutex(&ecc_fp_lock);
3558 #endif /* HAVE_THREAD_LS */
3564 /* helper function for freeing the cache ...
3565 must be called with the cache mutex locked */
3566 static void ecc_fp_free_cache(void)
3569 for (x = 0; x < FP_ENTRIES; x++) {
3570 if (fp_cache[x].g != NULL) {
3571 for (y = 0; y < (1U<<FP_LUT); y++) {
3572 ecc_del_point(fp_cache[x].LUT[y]);
3573 fp_cache[x].LUT[y] = NULL;
3575 ecc_del_point(fp_cache[x].g);
3576 fp_cache[x].g = NULL;
3577 mp_clear(&fp_cache[x].mu);
3578 fp_cache[x].lru_count = 0;
3579 fp_cache[x].lock = 0;
3584 /** Free the Fixed Point cache */
3585 void ecc_fp_free(void)
3587 #ifndef HAVE_THREAD_LS
3588 if (initMutex == 0) {
3589 InitMutex(&ecc_fp_lock);
3593 if (LockMutex(&ecc_fp_lock) == 0) {
3594 #endif /* HAVE_THREAD_LS */
3596 ecc_fp_free_cache();
3598 #ifndef HAVE_THREAD_LS
3599 UnLockMutex(&ecc_fp_lock);
3600 FreeMutex(&ecc_fp_lock);
3603 #endif /* HAVE_THREAD_LS */
3609 #ifdef HAVE_ECC_ENCRYPT
3617 ecCLI_RECV_RESP = 5,
3618 ecCLI_BAD_STATE = 99
3626 ecSRV_SENT_RESP = 5,
3627 ecSRV_BAD_STATE = 99
3632 const byte* kdfSalt; /* optional salt for kdf */
3633 const byte* kdfInfo; /* optional info for kdf */
3634 const byte* macSalt; /* optional salt for mac */
3635 word32 kdfSaltSz; /* size of kdfSalt */
3636 word32 kdfInfoSz; /* size of kdfInfo */
3637 word32 macSaltSz; /* size of macSalt */
3638 byte clientSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */
3639 byte serverSalt[EXCHANGE_SALT_SZ]; /* for msg exchange */
3640 byte encAlgo; /* which encryption type */
3641 byte kdfAlgo; /* which key derivation function type */
3642 byte macAlgo; /* which mac function type */
3643 byte protocol; /* are we REQ_RESP client or server ? */
3644 byte cliSt; /* protocol state, for sanity checks */
3645 byte srvSt; /* protocol state, for sanity checks */
3649 const byte* ecc_ctx_get_own_salt(ecEncCtx* ctx)
3651 if (ctx == NULL || ctx->protocol == 0)
3654 if (ctx->protocol == REQ_RESP_CLIENT) {
3655 if (ctx->cliSt == ecCLI_INIT) {
3656 ctx->cliSt = ecCLI_SALT_GET;
3657 return ctx->clientSalt;
3660 ctx->cliSt = ecCLI_BAD_STATE;
3664 else if (ctx->protocol == REQ_RESP_SERVER) {
3665 if (ctx->srvSt == ecSRV_INIT) {
3666 ctx->srvSt = ecSRV_SALT_GET;
3667 return ctx->serverSalt;
3670 ctx->srvSt = ecSRV_BAD_STATE;
3679 /* optional set info, can be called before or after set_peer_salt */
3680 int ecc_ctx_set_info(ecEncCtx* ctx, const byte* info, int sz)
3682 if (ctx == NULL || info == 0 || sz < 0)
3683 return BAD_FUNC_ARG;
3685 ctx->kdfInfo = info;
3686 ctx->kdfInfoSz = sz;
3692 static const char* exchange_info = "Secure Message Exchange";
3694 int ecc_ctx_set_peer_salt(ecEncCtx* ctx, const byte* salt)
3696 byte tmp[EXCHANGE_SALT_SZ/2];
3697 int halfSz = EXCHANGE_SALT_SZ/2;
3699 if (ctx == NULL || ctx->protocol == 0 || salt == NULL)
3700 return BAD_FUNC_ARG;
3702 if (ctx->protocol == REQ_RESP_CLIENT) {
3703 XMEMCPY(ctx->serverSalt, salt, EXCHANGE_SALT_SZ);
3704 if (ctx->cliSt == ecCLI_SALT_GET)
3705 ctx->cliSt = ecCLI_SALT_SET;
3707 ctx->cliSt = ecCLI_BAD_STATE;
3708 return BAD_ENC_STATE_E;
3712 XMEMCPY(ctx->clientSalt, salt, EXCHANGE_SALT_SZ);
3713 if (ctx->srvSt == ecSRV_SALT_GET)
3714 ctx->srvSt = ecSRV_SALT_SET;
3716 ctx->srvSt = ecSRV_BAD_STATE;
3717 return BAD_ENC_STATE_E;
3721 /* mix half and half */
3722 /* tmp stores 2nd half of client before overwrite */
3723 XMEMCPY(tmp, ctx->clientSalt + halfSz, halfSz);
3724 XMEMCPY(ctx->clientSalt + halfSz, ctx->serverSalt, halfSz);
3725 XMEMCPY(ctx->serverSalt, tmp, halfSz);
3727 ctx->kdfSalt = ctx->clientSalt;
3728 ctx->kdfSaltSz = EXCHANGE_SALT_SZ;
3730 ctx->macSalt = ctx->serverSalt;
3731 ctx->macSaltSz = EXCHANGE_SALT_SZ;
3733 if (ctx->kdfInfo == NULL) {
3735 ctx->kdfInfo = (const byte*)exchange_info;
3736 ctx->kdfInfoSz = EXCHANGE_INFO_SZ;
3743 static int ecc_ctx_set_salt(ecEncCtx* ctx, int flags, RNG* rng)
3745 byte* saltBuffer = NULL;
3747 if (ctx == NULL || rng == NULL || flags == 0)
3748 return BAD_FUNC_ARG;
3750 saltBuffer = (flags == REQ_RESP_CLIENT) ? ctx->clientSalt : ctx->serverSalt;
3752 return RNG_GenerateBlock(rng, saltBuffer, EXCHANGE_SALT_SZ);
3756 static void ecc_ctx_init(ecEncCtx* ctx, int flags)
3759 XMEMSET(ctx, 0, sizeof(ecEncCtx));
3761 ctx->encAlgo = ecAES_128_CBC;
3762 ctx->kdfAlgo = ecHKDF_SHA256;
3763 ctx->macAlgo = ecHMAC_SHA256;
3764 ctx->protocol = (byte)flags;
3766 if (flags == REQ_RESP_CLIENT)
3767 ctx->cliSt = ecCLI_INIT;
3768 if (flags == REQ_RESP_SERVER)
3769 ctx->srvSt = ecSRV_INIT;
3774 /* allow ecc context reset so user doesn't have to init/free for resue */
3775 int ecc_ctx_reset(ecEncCtx* ctx, RNG* rng)
3777 if (ctx == NULL || rng == NULL)
3778 return BAD_FUNC_ARG;
3780 ecc_ctx_init(ctx, ctx->protocol);
3781 return ecc_ctx_set_salt(ctx, ctx->protocol, rng);
3785 /* alloc/init and set defaults, return new Context */
3786 ecEncCtx* ecc_ctx_new(int flags, RNG* rng)
3789 ecEncCtx* ctx = (ecEncCtx*)XMALLOC(sizeof(ecEncCtx), 0, DYNAMIC_TYPE_ECC);
3792 ctx->protocol = (byte)flags;
3794 ret = ecc_ctx_reset(ctx, rng);
3804 /* free any resources, clear any keys */
3805 void ecc_ctx_free(ecEncCtx* ctx)
3808 XMEMSET(ctx, 0, sizeof(ecEncCtx));
3809 XFREE(ctx, 0, DYNAMIC_TYPE_ECC);
3814 static int ecc_get_key_sizes(ecEncCtx* ctx, int* encKeySz, int* ivSz,
3815 int* keysLen, word32* digestSz, word32* blockSz)
3818 switch (ctx->encAlgo) {
3820 *encKeySz = KEY_SIZE_128;
3822 *blockSz = AES_BLOCK_SIZE;
3825 return BAD_FUNC_ARG;
3828 switch (ctx->macAlgo) {
3830 *digestSz = SHA256_DIGEST_SIZE;
3833 return BAD_FUNC_ARG;
3836 return BAD_FUNC_ARG;
3838 *keysLen = *encKeySz + *ivSz + *digestSz;
3844 /* ecc encrypt with shared secret run through kdf
3845 ctx holds non default algos and inputs
3846 msgSz should be the right size for encAlgo, i.e., already padded
3847 return 0 on success */
3848 int ecc_encrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
3849 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
3855 #ifdef CYASSL_SMALL_STACK
3859 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */
3860 byte keys[ECC_BUFSIZE]; /* max size */
3862 word32 sharedSz = ECC_MAXSIZE;
3866 int offset = 0; /* keys offset if doing msg exchange */
3871 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
3873 return BAD_FUNC_ARG;
3875 if (ctx == NULL) { /* use defaults */
3876 ecc_ctx_init(&localCtx, 0);
3880 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
3885 if (ctx->protocol == REQ_RESP_SERVER) {
3889 if (ctx->srvSt != ecSRV_RECV_REQ)
3890 return BAD_ENC_STATE_E;
3892 ctx->srvSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
3894 else if (ctx->protocol == REQ_RESP_CLIENT) {
3895 if (ctx->cliSt != ecCLI_SALT_SET)
3896 return BAD_ENC_STATE_E;
3898 ctx->cliSt = ecCLI_SENT_REQ; /* only do this once */
3901 if (keysLen > ECC_BUFSIZE) /* keys size */
3904 if ( (msgSz%blockSz) != 0)
3905 return BAD_PADDING_E;
3907 if (*outSz < (msgSz + digestSz))
3910 #ifdef CYASSL_SMALL_STACK
3911 sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3912 if (sharedSecret == NULL)
3915 keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3917 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3922 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz);
3925 switch (ctx->kdfAlgo) {
3926 case ecHKDF_SHA256 :
3927 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
3928 ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz,
3939 encKey = keys + offset;
3940 encIv = encKey + encKeySz;
3941 macKey = encKey + encKeySz + ivSz;
3943 switch (ctx->encAlgo) {
3947 ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv,
3951 ret = AesCbcEncrypt(&aes, out, msg, msgSz);
3962 switch (ctx->macAlgo) {
3966 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
3969 ret = HmacUpdate(&hmac, out, msgSz);
3972 ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
3975 ret = HmacFinal(&hmac, out+msgSz);
3986 *outSz = msgSz + digestSz;
3988 #ifdef CYASSL_SMALL_STACK
3989 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3990 XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3997 /* ecc decrypt with shared secret run through kdf
3998 ctx holds non default algos and inputs
3999 return 0 on success */
4000 int ecc_decrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
4001 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
4007 #ifdef CYASSL_SMALL_STACK
4011 byte sharedSecret[ECC_MAXSIZE]; /* 521 max size */
4012 byte keys[ECC_BUFSIZE]; /* max size */
4014 word32 sharedSz = ECC_MAXSIZE;
4018 int offset = 0; /* in case using msg exchange */
4023 if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
4025 return BAD_FUNC_ARG;
4027 if (ctx == NULL) { /* use defaults */
4028 ecc_ctx_init(&localCtx, 0);
4032 ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
4037 if (ctx->protocol == REQ_RESP_CLIENT) {
4041 if (ctx->cliSt != ecCLI_SENT_REQ)
4042 return BAD_ENC_STATE_E;
4044 ctx->cliSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
4046 else if (ctx->protocol == REQ_RESP_SERVER) {
4047 if (ctx->srvSt != ecSRV_SALT_SET)
4048 return BAD_ENC_STATE_E;
4050 ctx->srvSt = ecSRV_RECV_REQ; /* only do this once */
4053 if (keysLen > ECC_BUFSIZE) /* keys size */
4056 if ( ((msgSz-digestSz) % blockSz) != 0)
4057 return BAD_PADDING_E;
4059 if (*outSz < (msgSz - digestSz))
4062 #ifdef CYASSL_SMALL_STACK
4063 sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4064 if (sharedSecret == NULL)
4067 keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4069 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4074 ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz);
4077 switch (ctx->kdfAlgo) {
4078 case ecHKDF_SHA256 :
4079 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
4080 ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz,
4091 encKey = keys + offset;
4092 encIv = encKey + encKeySz;
4093 macKey = encKey + encKeySz + ivSz;
4095 switch (ctx->macAlgo) {
4098 byte verify[SHA256_DIGEST_SIZE];
4100 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
4103 ret = HmacUpdate(&hmac, msg, msgSz-digestSz);
4106 ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
4109 ret = HmacFinal(&hmac, verify);
4112 if (memcmp(verify, msg + msgSz - digestSz, digestSz) != 0)
4124 switch (ctx->encAlgo) {
4128 ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv,
4132 ret = AesCbcDecrypt(&aes, out, msg, msgSz-digestSz);
4143 *outSz = msgSz - digestSz;
4145 #ifdef CYASSL_SMALL_STACK
4146 XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4147 XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4154 #endif /* HAVE_ECC_ENCRYPT */
4156 #endif /* HAVE_ECC */