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))){
45 if(!(p->y.wordv = malloc(length_B))){
49 if(!(p->z1.wordv = malloc(length_B))){
54 if(!(p->z2.wordv = malloc(length_B))){
60 if(!(p->z3.wordv = malloc(length_B))){
67 bigint_set_zero(&p->x);
68 bigint_set_zero(&p->y);
69 bigint_set_zero(&p->z1);
70 bigint_set_zero(&p->z2);
71 bigint_set_zero(&p->z3);
75 void ecc_chudnovsky_point_free(ecc_chudnovsky_point_t* p){
85 * return POINT_AT_INFINITY
87 * M = 3*(X + Z^2)*(X - Z^2)
89 * Y' = M*(S - X') - 8*Y^4
93 * return (X', Y', Z', Z'^2, Z'^3)
96 uint8_t ecc_affine_to_chudnovsky_point(ecc_chudnovsky_point_t *dest,
97 const ecc_affine_point_t *src){
98 if(src->y.length_W == 0){
99 /* point at infinity */
100 bigint_set_zero(&dest->y);
103 bigint_copy(&dest->x, &src->x);
104 bigint_copy(&dest->y, &src->y);
105 dest->z1.wordv[0] = 1;
106 dest->z2.wordv[0] = 1;
107 dest->z3.wordv[0] = 1;
108 dest->z1.length_W = 1;
109 dest->z2.length_W = 1;
110 dest->z3.length_W = 1;
114 bigint_adjust(&dest->z1);
115 bigint_adjust(&dest->z2);
116 bigint_adjust(&dest->z3);
120 uint8_t ecc_chudnovsky_to_affine_point(ecc_affine_point_t *dest,
121 const ecc_chudnovsky_point_t *src,
122 const ecc_curve_sp_t *curve){
123 if(src->y.length_W == 0){
124 /* point at infinity */
125 bigint_set_zero(&dest->y);
128 bigint_word_t t_w[curve->p->length_W * 2];
129 bigint_word_t z1_w[curve->p->length_W * 2];
130 bigint_word_t z2_w[curve->p->length_W];
136 bigint_inverse(&z1, &src->z1, curve->p);
137 bigint_square(&t, &z1);
139 bigint_copy(&z2, &t);
140 bigint_mul_u(&t, &src->x, &z2);
142 bigint_copy(&dest->x, &t);
143 bigint_mul_u(&t, &z1, &z2);
145 bigint_mul_u(&t, &t, &src->y);
147 bigint_copy(&dest->y, &t);
152 void ecc_chudnovsky_point_print(const ecc_chudnovsky_point_t *p){
153 if(p->y.length_W == 0){
154 printf_P(PSTR(" ECC point = point-at-infinity\n"));
157 printf_P(PSTR(" ECC point x = "));
158 bigint_print_hex(&p->x);
159 printf_P(PSTR("\n ECC point y = "));
160 bigint_print_hex(&p->y);
161 printf_P(PSTR("\n ECC point z1 = "));
162 bigint_print_hex(&p->z1);
163 printf_P(PSTR("\n ECC point z2 = "));
164 bigint_print_hex(&p->z2);
165 printf_P(PSTR("\n ECC point z3 = "));
166 bigint_print_hex(&p->z3);
170 uint8_t ecc_chudnovsky_point_double_sp(ecc_chudnovsky_point_t *dest,
171 const ecc_chudnovsky_point_t *a,
172 const ecc_curve_sp_t *curve){
173 if(a->y.length_W == 0){
174 /* point at infinity */
175 bigint_set_zero(&dest->y);
178 bigint_word_t s_w[curve->p->length_W * 2];
179 bigint_word_t m_w[curve->p->length_W * 2];
180 bigint_word_t t_w[curve->p->length_W * 2];
188 bigint_square(&t, &a->y);
190 bigint_mul_u(&s, &t, &a->x);
192 bigint_shiftleft(&s, 2);
196 bigint_sub_u(&t, &a->x, &a->z2);
197 // /**/curve->reduce_p(&t);
198 bigint_add_u(&m, &a->x, &a->z2);
199 // /**/curve->reduce_p(&m);
200 bigint_mul_s(&m, &m, &t);
203 bigint_shiftleft(&t, 1);
204 bigint_add_s(&m, &m, &t);
208 bigint_mul_u(&t, &a->z1, &a->y);
210 bigint_shiftleft(&t, 1);
212 bigint_copy(&dest->z1, &t);
215 bigint_square(&t, &m);
217 bigint_sub_s(&t, &t, &s);
218 bigint_sub_s(&t, &t, &s);
220 bigint_copy(&dest->x, &t);
223 bigint_sub_s(&s, &s, &t);
225 bigint_mul_s(&s, &s, &m);
227 bigint_square(&t, &a->y);
229 bigint_square(&t, &t);
231 bigint_shiftleft(&t, 3);
233 bigint_sub_s(&s, &s, &t);
235 bigint_copy(&dest->y, &s);
238 bigint_square(&t, &dest->z1);
240 bigint_copy(&dest->z2, &t);
243 bigint_mul_u(&t, &t, &dest->z1);
245 bigint_copy(&dest->z3, &t);
250 void ecc_chudnovsky_point_copy(ecc_chudnovsky_point_t *dest,
251 const ecc_chudnovsky_point_t *src){
252 bigint_copy(&dest->x, &src->x);
253 bigint_copy(&dest->y, &src->y);
254 bigint_copy(&dest->z1, &src->z1);
255 bigint_copy(&dest->z2, &src->z2);
256 bigint_copy(&dest->z3, &src->z3);
259 uint8_t ecc_chudnovsky_point_add_sp(ecc_chudnovsky_point_t *dest,
260 const ecc_chudnovsky_point_t *a,
261 const ecc_chudnovsky_point_t *b,
262 const ecc_curve_sp_t *curve){
263 if(a->y.length_W == 0){
264 ecc_chudnovsky_point_copy(dest, b);
267 if(b->y.length_W == 0){
268 ecc_chudnovsky_point_copy(dest, a);
271 bigint_word_t u1_w[curve->p->length_W * 2];
272 bigint_word_t u2_w[curve->p->length_W * 2];
273 bigint_word_t s1_w[curve->p->length_W * 2];
274 bigint_word_t s2_w[curve->p->length_W * 2];
275 bigint_t u1, u2, s1, s2;
283 bigint_mul_u(&u1, &a->x, &b->z2);
284 curve->reduce_p(&u1);
287 bigint_mul_u(&u2, &b->x, &a->z2);
288 curve->reduce_p(&u2);
291 bigint_mul_u(&s1, &a->y, &b->z3);
292 curve->reduce_p(&s1);
295 bigint_mul_u(&s2, &b->y, &a->z3);
296 curve->reduce_p(&s2);
298 if(bigint_cmp_u(&u1, &u2) == 0){
299 if(bigint_cmp_u(&s1, &s2)){
300 /* point at infinity */
301 bigint_set_zero(&dest->y);
304 /* a == b --> dest = 2*a */
305 ecc_chudnovsky_point_double_sp(dest, a, curve);
309 bigint_word_t h_w[curve->p->length_W * 2];
310 bigint_word_t r_w[curve->p->length_W * 2];
316 bigint_sub_s(&h, &u2, &u1);
317 /**/curve->reduce_p(&h);
320 bigint_sub_s(&r, &s2, &s1);
321 // /**/curve->reduce_p(&r);
324 bigint_mul_u(&s2, &a->z1, &b->z1);
325 curve->reduce_p(&s2);
326 bigint_mul_s(&s2, &s2, &h);
327 curve->reduce_p(&s2);
328 bigint_copy(&dest->z1, &s2);
330 /* compute u1*h^2 and h^3 */
331 bigint_square(&s2, &h);
332 curve->reduce_p(&s2);
333 bigint_mul_s(&h, &s2, &h);
335 bigint_mul_s(&u1, &s2, &u1);
336 curve->reduce_p(&u1);
339 bigint_square(&u2, &r);
340 curve->reduce_p(&u2);
341 bigint_sub_s(&u2, &u2, &h);
342 curve->reduce_p(&u2);
343 bigint_sub_s(&u2, &u2, &u1);
344 bigint_sub_s(&u2, &u2, &u1);
345 curve->reduce_p(&u2);
346 bigint_copy(&dest->x, &u2);
349 bigint_sub_s(&u1, &u1, &u2);
350 curve->reduce_p(&u1);
351 bigint_mul_s(&s2, &u1, &r);
352 curve->reduce_p(&s2);
353 bigint_mul_s(&s1, &s1, &h);
354 curve->reduce_p(&s1);
355 bigint_sub_s(&s2, &s2, &s1);
356 curve->reduce_p(&s2);
357 bigint_copy(&dest->y, &s2);
361 bigint_square(&s1, &dest->z1);
362 curve->reduce_p(&s1);
363 bigint_copy(&dest->z2, &s1);
366 bigint_mul_u(&s1, &s1, &dest->z1);
367 curve->reduce_p(&s1);
368 bigint_copy(&dest->z3, &s1);
373 uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest,
375 const ecc_chudnovsky_point_t *p,
376 const ecc_curve_sp_t* curve){
381 for(i = k->length_W; i > 0; --i){
382 v = 1 << (BIGINT_WORD_SIZE - 1);
386 ecc_chudnovsky_point_double_sp(dest, dest, curve);
388 ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
393 ecc_chudnovsky_point_copy(dest, p);
402 uint8_t bigint_to_naf(uint8_t* dest, uint16_t *length, const bigint_t *src){
403 if(src->length_W == 0){
409 memset(dest, 0, src->length_W * sizeof(bigint_word_t) * 2 +1);
412 uint8_t t; /* 3 -> -1 ; 1 -> 1; 0 -> 0 (2 should not happen) */
414 bigint_word_t k_w[src->length_W + 1];
415 bigint_word_t p_w = 1;
420 bigint_copy(&k, src);
422 while(k.length_W >= 1){
426 bigint_sub_u(&k, &k, &p);
428 bigint_add_u(&k, &k, &p);
433 dest[(i * 2) / 8] |= t << ((2 * i) & 7);
434 bigint_shiftright(&k, 1);
441 void print_naf(uint8_t* naf, uint16_t length){
448 t = (naf[(length * 2) / 8] >> ((length * 2) & 7)) & 3;
450 case 0: putchar('0'); break;
451 case 1: putchar('1'); break;
452 case 3: putchar('-'); putchar('1'); break;
453 default: putchar('E');
461 uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest,
463 const ecc_chudnovsky_point_t *p,
464 const ecc_curve_sp_t* curve){
465 if(k->length_W == 0 || p->y.length_W == 0){
466 bigint_set_zero(&dest->y);
472 ecc_chudnovsky_point_t p_;
473 bigint_word_t y_[curve->p->length_W];
477 memcpy(&p_, p, sizeof(p_));
479 bigint_copy(&p_.y, &p->y);
480 p_.y.info |= BIGINT_NEG_MASK;
481 bigint_add_s(&p_.y, &p_.y, curve->p);
484 if(!(t = calloc(k->length_W * sizeof(bigint_word_t) * 2 + 1, 1))){
487 bigint_to_naf(t, &i, k);
493 dest->y.length_W = 0;
495 q = (t[(i * 2) / 8] >> ((i * 2) & 7)) & 3;
496 ecc_chudnovsky_point_double_sp(dest, dest, curve);
498 ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
501 ecc_chudnovsky_point_add_sp(dest, dest, &p_, curve);
510 uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest,
512 const ecc_chudnovsky_point_t *p,
513 const ecc_curve_sp_t* curve){
514 return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);
519 uint8_t ecc_chudnovsky_multipy_and_sum(ecc_chudnovsky_point_t *dest,
521 const ecc_chudnovsky_point_t *p,
523 const ecc_chudnovsky_point_t *q,
524 const ecc_curve_sp_t* curve){
525 return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);