3 This file is part of the ARM-Crypto-Lib.
4 Copyright (C) 2006-2012 Daniel Otte (daniel.otte@rub.de)
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
29 #include "bigint_io.h"
31 #include <avr/pgmspace.h>
36 #define bigint_print_hex(a)
41 uint8_t ecc_chudnovsky_point_alloc(ecc_chudnovsky_point_t *p, size_t length_B){
42 if(!(p->x.wordv = malloc(length_B))){
43 printf_P(PSTR("DBG: XXX <%S %s %d>\n"), PSTR(__FILE__), __func__, __LINE__);
46 if(!(p->y.wordv = malloc(length_B))){
47 printf_P(PSTR("DBG: XXX <%S %s %d>\n"), PSTR(__FILE__), __func__, __LINE__);
51 if(!(p->z1.wordv = malloc(length_B))){
52 printf_P(PSTR("DBG: XXX <%S %s %d>\n"), PSTR(__FILE__), __func__, __LINE__);
57 if(!(p->z2.wordv = malloc(length_B))){
58 printf_P(PSTR("DBG: XXX <%S %s %d>\n"), PSTR(__FILE__), __func__, __LINE__);
64 if(!(p->z3.wordv = malloc(length_B))){
65 printf_P(PSTR("DBG: XXX <%S %s %d>\n"), PSTR(__FILE__), __func__, __LINE__);
72 bigint_set_zero(&p->x);
73 bigint_set_zero(&p->y);
74 bigint_set_zero(&p->z1);
75 bigint_set_zero(&p->z2);
76 bigint_set_zero(&p->z3);
80 void ecc_chudnovsky_point_free(ecc_chudnovsky_point_t *p){
90 * return POINT_AT_INFINITY
92 * M = 3*(X + Z^2)*(X - Z^2)
94 * Y' = M*(S - X') - 8*Y^4
98 * return (X', Y', Z', Z'^2, Z'^3)
101 uint8_t ecc_affine_to_chudnovsky_point(ecc_chudnovsky_point_t *dest,
102 const ecc_affine_point_t *src){
103 if(src->y.length_W == 0){
104 /* point at infinity */
105 bigint_set_zero(&dest->y);
108 bigint_copy(&dest->x, &src->x);
109 bigint_copy(&dest->y, &src->y);
110 dest->z1.wordv[0] = 1;
111 dest->z2.wordv[0] = 1;
112 dest->z3.wordv[0] = 1;
113 dest->z1.length_W = 1;
114 dest->z2.length_W = 1;
115 dest->z3.length_W = 1;
119 bigint_adjust(&dest->z1);
120 bigint_adjust(&dest->z2);
121 bigint_adjust(&dest->z3);
125 uint8_t ecc_chudnovsky_to_affine_point(ecc_affine_point_t *dest,
126 const ecc_chudnovsky_point_t *src,
127 const ecc_curve_sp_t *curve){
128 if(src->y.length_W == 0){
129 /* point at infinity */
130 bigint_set_zero(&dest->y);
133 bigint_word_t t_w[curve->p->length_W * 2];
134 bigint_word_t z1_w[curve->p->length_W * 2];
135 bigint_word_t z2_w[curve->p->length_W];
141 bigint_inverse(&z1, &src->z1, curve->p);
142 bigint_square(&t, &z1);
144 bigint_copy(&z2, &t);
145 bigint_mul_u(&t, &src->x, &z2);
147 bigint_copy(&dest->x, &t);
148 bigint_mul_u(&t, &z1, &z2);
150 bigint_mul_u(&t, &t, &src->y);
152 bigint_copy(&dest->y, &t);
157 void ecc_chudnovsky_point_print(const ecc_chudnovsky_point_t *p){
158 if(p->y.length_W == 0){
159 printf_P(PSTR(" ECC point = point-at-infinity\n"));
162 printf_P(PSTR(" ECC point x = "));
163 bigint_print_hex(&p->x);
164 printf_P(PSTR("\n ECC point y = "));
165 bigint_print_hex(&p->y);
166 printf_P(PSTR("\n ECC point z1 = "));
167 bigint_print_hex(&p->z1);
168 printf_P(PSTR("\n ECC point z2 = "));
169 bigint_print_hex(&p->z2);
170 printf_P(PSTR("\n ECC point z3 = "));
171 bigint_print_hex(&p->z3);
175 uint8_t ecc_chudnovsky_point_double_sp(ecc_chudnovsky_point_t *dest,
176 const ecc_chudnovsky_point_t *a,
177 const ecc_curve_sp_t *curve){
178 if(a->y.length_W == 0){
179 /* point at infinity */
180 bigint_set_zero(&dest->y);
183 bigint_word_t s_w[curve->p->length_W * 2];
184 bigint_word_t m_w[curve->p->length_W * 2];
185 bigint_word_t t_w[curve->p->length_W * 2];
193 bigint_square(&t, &a->y);
195 bigint_mul_u(&s, &t, &a->x);
197 bigint_shiftleft(&s, 2);
201 bigint_sub_u(&t, &a->x, &a->z2);
202 // /**/curve->reduce_p(&t);
203 bigint_add_u(&m, &a->x, &a->z2);
204 // /**/curve->reduce_p(&m);
205 bigint_mul_s(&m, &m, &t);
208 bigint_shiftleft(&t, 1);
209 bigint_add_s(&m, &m, &t);
213 bigint_mul_u(&t, &a->z1, &a->y);
215 bigint_shiftleft(&t, 1);
217 bigint_copy(&dest->z1, &t);
220 bigint_square(&t, &m);
222 bigint_sub_s(&t, &t, &s);
223 bigint_sub_s(&t, &t, &s);
225 bigint_copy(&dest->x, &t);
228 bigint_sub_s(&s, &s, &t);
230 bigint_mul_s(&s, &s, &m);
232 bigint_square(&t, &a->y);
234 bigint_square(&t, &t);
236 bigint_shiftleft(&t, 3);
238 bigint_sub_s(&s, &s, &t);
240 bigint_copy(&dest->y, &s);
243 bigint_square(&t, &dest->z1);
245 bigint_copy(&dest->z2, &t);
248 bigint_mul_u(&t, &t, &dest->z1);
250 bigint_copy(&dest->z3, &t);
255 void ecc_chudnovsky_point_copy(ecc_chudnovsky_point_t *dest,
256 const ecc_chudnovsky_point_t *src){
257 bigint_copy(&dest->x, &src->x);
258 bigint_copy(&dest->y, &src->y);
259 bigint_copy(&dest->z1, &src->z1);
260 bigint_copy(&dest->z2, &src->z2);
261 bigint_copy(&dest->z3, &src->z3);
264 uint8_t ecc_chudnovsky_point_add_sp(ecc_chudnovsky_point_t *dest,
265 const ecc_chudnovsky_point_t *a,
266 const ecc_chudnovsky_point_t *b,
267 const ecc_curve_sp_t *curve){
268 if(a->y.length_W == 0){
269 ecc_chudnovsky_point_copy(dest, b);
272 if(b->y.length_W == 0){
273 ecc_chudnovsky_point_copy(dest, a);
276 bigint_word_t u1_w[curve->p->length_W * 2];
277 bigint_word_t u2_w[curve->p->length_W * 2];
278 bigint_word_t s1_w[curve->p->length_W * 2];
279 bigint_word_t s2_w[curve->p->length_W * 2];
280 bigint_t u1, u2, s1, s2;
288 bigint_mul_u(&u1, &a->x, &b->z2);
289 curve->reduce_p(&u1);
292 bigint_mul_u(&u2, &b->x, &a->z2);
293 curve->reduce_p(&u2);
296 bigint_mul_u(&s1, &a->y, &b->z3);
297 curve->reduce_p(&s1);
300 bigint_mul_u(&s2, &b->y, &a->z3);
301 curve->reduce_p(&s2);
303 if(bigint_cmp_u(&u1, &u2) == 0){
304 if(bigint_cmp_u(&s1, &s2)){
305 /* point at infinity */
306 bigint_set_zero(&dest->y);
309 /* a == b --> dest = 2*a */
310 ecc_chudnovsky_point_double_sp(dest, a, curve);
314 bigint_word_t h_w[curve->p->length_W * 2];
315 bigint_word_t r_w[curve->p->length_W * 2];
321 bigint_sub_s(&h, &u2, &u1);
322 /**/curve->reduce_p(&h);
325 bigint_sub_s(&r, &s2, &s1);
326 // /**/curve->reduce_p(&r);
329 bigint_mul_u(&s2, &a->z1, &b->z1);
330 curve->reduce_p(&s2);
331 bigint_mul_s(&s2, &s2, &h);
332 curve->reduce_p(&s2);
333 bigint_copy(&dest->z1, &s2);
335 /* compute u1*h^2 and h^3 */
336 bigint_square(&s2, &h);
337 curve->reduce_p(&s2);
338 bigint_mul_s(&h, &s2, &h);
340 bigint_mul_s(&u1, &s2, &u1);
341 curve->reduce_p(&u1);
344 bigint_square(&u2, &r);
345 curve->reduce_p(&u2);
346 bigint_sub_s(&u2, &u2, &h);
347 curve->reduce_p(&u2);
348 bigint_sub_s(&u2, &u2, &u1);
349 bigint_sub_s(&u2, &u2, &u1);
350 curve->reduce_p(&u2);
351 bigint_copy(&dest->x, &u2);
354 bigint_sub_s(&u1, &u1, &u2);
355 curve->reduce_p(&u1);
356 bigint_mul_s(&s2, &u1, &r);
357 curve->reduce_p(&s2);
358 bigint_mul_s(&s1, &s1, &h);
359 curve->reduce_p(&s1);
360 bigint_sub_s(&s2, &s2, &s1);
361 curve->reduce_p(&s2);
362 bigint_copy(&dest->y, &s2);
366 bigint_square(&s1, &dest->z1);
367 curve->reduce_p(&s1);
368 bigint_copy(&dest->z2, &s1);
371 bigint_mul_u(&s1, &s1, &dest->z1);
372 curve->reduce_p(&s1);
373 bigint_copy(&dest->z3, &s1);
378 uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest,
380 const ecc_chudnovsky_point_t *p,
381 const ecc_curve_sp_t *curve){
386 for(i = k->length_W; i > 0; --i){
387 v = 1 << (BIGINT_WORD_SIZE - 1);
391 ecc_chudnovsky_point_double_sp(dest, dest, curve);
393 ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
398 ecc_chudnovsky_point_copy(dest, p);
407 uint8_t bigint_to_naf(uint8_t *dest, uint16_t *length, const bigint_t *src){
408 if(src->length_W == 0){
414 memset(dest, 0, src->length_W * sizeof(bigint_word_t) * 2 +1);
417 uint8_t t; /* 3 -> -1 ; 1 -> 1; 0 -> 0 (2 should not happen) */
419 bigint_word_t k_w[src->length_W + 1];
420 bigint_word_t p_w = 1;
425 bigint_copy(&k, src);
427 while(k.length_W >= 1){
431 bigint_sub_u(&k, &k, &p);
433 bigint_add_u(&k, &k, &p);
438 dest[(i * 2) / 8] |= t << ((2 * i) & 7);
439 bigint_shiftright(&k, 1);
446 void print_naf(uint8_t *naf, uint16_t length){
453 t = (naf[(length * 2) / 8] >> ((length * 2) & 7)) & 3;
455 case 0: putchar('0'); break;
456 case 1: putchar('1'); break;
457 case 3: putchar('-'); putchar('1'); break;
458 default: putchar('E');
466 uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest,
468 const ecc_chudnovsky_point_t *p,
469 const ecc_curve_sp_t *curve){
470 if(k->length_W == 0 || p->y.length_W == 0){
471 bigint_set_zero(&dest->y);
477 ecc_chudnovsky_point_t p_;
478 bigint_word_t y_[curve->p->length_W];
482 memcpy(&p_, p, sizeof(p_));
484 bigint_copy(&p_.y, &p->y);
485 p_.y.info |= BIGINT_NEG_MASK;
486 bigint_add_s(&p_.y, &p_.y, curve->p);
489 if(!(t = calloc(k->length_W * sizeof(bigint_word_t) * 2 + 1, 1))){
492 bigint_to_naf(t, &i, k);
498 dest->y.length_W = 0;
500 q = (t[(i * 2) / 8] >> ((i * 2) & 7)) & 3;
501 ecc_chudnovsky_point_double_sp(dest, dest, curve);
503 ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
506 ecc_chudnovsky_point_add_sp(dest, dest, &p_, curve);
515 uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest,
517 const ecc_chudnovsky_point_t *p,
518 const ecc_curve_sp_t *curve){
519 return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);
524 uint8_t ecc_chudnovsky_multipy_and_sum(ecc_chudnovsky_point_t *dest,
526 const ecc_chudnovsky_point_t *p,
528 const ecc_chudnovsky_point_t *q,
529 const ecc_curve_sp_t *curve){
530 return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);