ecdsa/ecc_chudnovsky.c

   1 /* ecc_chudnovsky.c */
   2 /*
   3     This file is part of the ARM-Crypto-Lib.
   4     Copyright (C) 2006-2012 Daniel Otte (daniel.otte@rub.de)
   5
   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.
  10
  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.
  15
  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/>.
  18 */
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "bigint.h"
  23 #include "ecc.h"
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #if 1
  28 #include <stdio.h>
  29 #include "bigint_io.h"
  30 #include "uart_i.h"
  31 #include <avr/pgmspace.h>
  32 #endif
  33
  34 #if 0
  35 #define printf_P(...)
  36 #define bigint_print_hex(a)
  37 #undef putchar
  38 #define putchar(a)
  39 #endif
  40
  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         return 1;
  44     }
  45     if(!(p->y.wordv = malloc(length_B))){
  46         free(p->x.wordv);
  47         return 1;
  48     }
  49     if(!(p->z1.wordv = malloc(length_B))){
  50         free(p->x.wordv);
  51         free(p->y.wordv);
  52         return 1;
  53     }
  54     if(!(p->z2.wordv = malloc(length_B))){
  55         free(p->x.wordv);
  56         free(p->y.wordv);
  57         free(p->z1.wordv);
  58         return 1;
  59     }
  60     if(!(p->z3.wordv = malloc(length_B))){
  61         free(p->x.wordv);
  62         free(p->y.wordv);
  63         free(p->z1.wordv);
  64         free(p->z2.wordv);
  65         return 1;
  66     }
  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);
  72     return 0;
  73 }
  74
  75 void ecc_chudnovsky_point_free(ecc_chudnovsky_point_t* p){
  76     free(p->x.wordv);
  77     free(p->y.wordv);
  78     free(p->z1.wordv);
  79     free(p->z2.wordv);
  80     free(p->z3.wordv);
  81 }
  82
  83 /*
  84  * if (Y == 0)
  85  *   return POINT_AT_INFINITY
  86  * S = 4*X*Y^2
  87  * M = 3*(X + Z^2)*(X - Z^2)
  88  * X' = M^2 - 2*S
  89  * Y' = M*(S - X') - 8*Y^4
  90  * Z' = 2*Y*Z
  91  * Z'^2 = Z'^2
  92  * Z'^3 = Z'^2 * Z'
  93  * return (X', Y', Z', Z'^2, Z'^3)
  94  */
  95
  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);
 101         return 0;
 102     }
 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;
 111     dest->z1.info = 0;
 112     dest->z2.info = 0;
 113     dest->z3.info = 0;
 114     bigint_adjust(&dest->z1);
 115     bigint_adjust(&dest->z2);
 116     bigint_adjust(&dest->z3);
 117     return 0;
 118 }
 119
 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);
 126         return 0;
 127     }
 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];
 131     bigint_t t, z1, z2;
 132     t.wordv =  t_w;
 133     z1.wordv = z1_w;
 134     z2.wordv = z2_w;
 135
 136     bigint_inverse(&z1, &src->z1, curve->p);
 137     bigint_square(&t, &z1);
 138     curve->reduce_p(&t);
 139     bigint_copy(&z2, &t);
 140     bigint_mul_u(&t, &src->x, &z2);
 141     curve->reduce_p(&t);
 142     bigint_copy(&dest->x, &t);
 143     bigint_mul_u(&t, &z1, &z2);
 144     curve->reduce_p(&t);
 145     bigint_mul_u(&t, &t, &src->y);
 146     curve->reduce_p(&t);
 147     bigint_copy(&dest->y, &t);
 148
 149     return 0;
 150 }
 151
 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"));
 155         return;
 156     }
 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);
 167     putchar('\n');
 168 }
 169
 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);
 176         return 0;
 177     }
 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];
 181     bigint_t s, m, t;
 182
 183     s.wordv = s_w;
 184     m.wordv = m_w;
 185     t.wordv = t_w;
 186
 187     /* compute s*/
 188     bigint_square(&t, &a->y);
 189     curve->reduce_p(&t);
 190     bigint_mul_u(&s, &t, &a->x);
 191     curve->reduce_p(&s);
 192     bigint_shiftleft(&s, 2);
 193     curve->reduce_p(&s);
 194
 195     /* compute m */
 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);
 201     curve->reduce_p(&m);
 202     bigint_copy(&t, &m);
 203     bigint_shiftleft(&t, 1);
 204     bigint_add_s(&m, &m, &t);
 205     curve->reduce_p(&m);
 206
 207     /* compute new z1 */
 208     bigint_mul_u(&t, &a->z1, &a->y);
 209     curve->reduce_p(&t);
 210     bigint_shiftleft(&t, 1);
 211     curve->reduce_p(&t);
 212     bigint_copy(&dest->z1, &t);
 213
 214     /* compute new x */
 215     bigint_square(&t, &m);
 216     curve->reduce_p(&t);
 217     bigint_sub_s(&t, &t, &s);
 218     bigint_sub_s(&t, &t, &s);
 219     curve->reduce_p(&t);
 220     bigint_copy(&dest->x, &t);
 221
 222     /* compute new y */
 223     bigint_sub_s(&s, &s, &t);
 224     curve->reduce_p(&s);
 225     bigint_mul_s(&s, &s, &m);
 226     curve->reduce_p(&s);
 227     bigint_square(&t, &a->y);
 228     curve->reduce_p(&t);
 229     bigint_square(&t, &t);
 230     curve->reduce_p(&t);
 231     bigint_shiftleft(&t, 3);
 232     curve->reduce_p(&t);
 233     bigint_sub_s(&s, &s, &t);
 234     curve->reduce_p(&s);
 235     bigint_copy(&dest->y, &s);
 236
 237     /* compute new z2 */
 238     bigint_square(&t, &dest->z1);
 239     curve->reduce_p(&t);
 240     bigint_copy(&dest->z2, &t);
 241
 242     /* compute new z3 */
 243     bigint_mul_u(&t, &t, &dest->z1);
 244     curve->reduce_p(&t);
 245     bigint_copy(&dest->z3, &t);
 246
 247     return 0;
 248 }
 249
 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);
 257 }
 258
 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);
 265         return 0;
 266     }
 267     if(b->y.length_W == 0){
 268         ecc_chudnovsky_point_copy(dest, a);
 269         return 0;
 270     }
 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;
 276
 277     u1.wordv = u1_w;
 278     u2.wordv = u2_w;
 279     s1.wordv = s1_w;
 280     s2.wordv = s2_w;
 281
 282     /* compute u1 */
 283     bigint_mul_u(&u1, &a->x, &b->z2);
 284     curve->reduce_p(&u1);
 285
 286     /* compute u2 */
 287     bigint_mul_u(&u2, &b->x, &a->z2);
 288     curve->reduce_p(&u2);
 289
 290     /* compute s1 */
 291     bigint_mul_u(&s1, &a->y, &b->z3);
 292     curve->reduce_p(&s1);
 293
 294     /* compute s2 */
 295     bigint_mul_u(&s2, &b->y, &a->z3);
 296     curve->reduce_p(&s2);
 297
 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);
 302             return 0;
 303         }else{
 304             /* a == b --> dest = 2*a */
 305             ecc_chudnovsky_point_double_sp(dest, a, curve);
 306         }
 307     }
 308
 309     bigint_word_t h_w[curve->p->length_W * 2];
 310     bigint_word_t r_w[curve->p->length_W * 2];
 311     bigint_t h, r;
 312
 313     h.wordv = h_w;
 314     r.wordv = r_w;
 315     /* compute h */
 316     bigint_sub_s(&h, &u2, &u1);
 317     /**/curve->reduce_p(&h);
 318
 319     /* compute r */
 320     bigint_sub_s(&r, &s2, &s1);
 321 //    /**/curve->reduce_p(&r);
 322
 323     /* compute new z */
 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);
 329
 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);
 334     curve->reduce_p(&h);
 335     bigint_mul_s(&u1, &s2, &u1);
 336     curve->reduce_p(&u1);
 337
 338     /* compute new x */
 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);
 347
 348     /* compute new y */
 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);
 358
 359
 360     /* compute new z2 */
 361     bigint_square(&s1, &dest->z1);
 362     curve->reduce_p(&s1);
 363     bigint_copy(&dest->z2, &s1);
 364
 365     /* compute new z2 */
 366     bigint_mul_u(&s1, &s1, &dest->z1);
 367     curve->reduce_p(&s1);
 368     bigint_copy(&dest->z3, &s1);
 369
 370     return 0;
 371 }
 372
 373 uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest,
 374                                       const bigint_t *k,
 375                                       const ecc_chudnovsky_point_t *p,
 376                                       const ecc_curve_sp_t* curve){
 377     uint16_t i;
 378     uint8_t s = 0;
 379     bigint_word_t v, t;
 380
 381     for(i = k->length_W; i > 0; --i){
 382         v = 1 << (BIGINT_WORD_SIZE - 1);
 383         t = k->wordv[i - 1];
 384         do{
 385             if(s){
 386                 ecc_chudnovsky_point_double_sp(dest, dest, curve);
 387                 if(v & t){
 388                     ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
 389                 }
 390             }else{
 391                 if(v & t){
 392                     s = 1;
 393                     ecc_chudnovsky_point_copy(dest, p);
 394                 }
 395             }
 396             v >>= 1;
 397         }while(v);
 398     }
 399     return 0;
 400 }
 401
 402 uint8_t bigint_to_naf(uint8_t* dest, uint16_t *length, const bigint_t *src){
 403     if(src->length_W == 0){
 404         *dest = 0;
 405         *length = 2;
 406         return 0;
 407     }
 408
 409     memset(dest, 0, src->length_W * sizeof(bigint_word_t) * 2 +1);
 410
 411     uint16_t i = 0;
 412     uint8_t t; /* 3 -> -1 ; 1 -> 1; 0 -> 0 (2 should not happen) */
 413     bigint_t k, p;
 414     bigint_word_t k_w[src->length_W + 1];
 415     bigint_word_t p_w = 1;
 416     p.wordv = &p_w;
 417     p.info = 0;
 418     p.length_W = 1;
 419     k.wordv = k_w;
 420     bigint_copy(&k, src);
 421
 422     while(k.length_W >= 1){
 423         if(k.wordv[0] & 1){
 424             t = k.wordv[0] & 3;
 425             if(t == 1){
 426                 bigint_sub_u(&k, &k, &p);
 427             }else{
 428                 bigint_add_u(&k, &k, &p);
 429             }
 430         }else{
 431             t = 0;
 432         }
 433         dest[(i * 2) / 8] |= t << ((2 * i) & 7);
 434         bigint_shiftright(&k, 1);
 435         i += 1;
 436     }
 437     *length = i;
 438     return 0;
 439 }
 440
 441 void print_naf(uint8_t* naf, uint16_t length){
 442     if(!length){
 443         return;
 444     }
 445     --length;
 446     int8_t t;
 447     do{
 448         t = (naf[(length * 2) / 8] >> ((length * 2) & 7)) & 3;
 449         switch(t & 3){
 450         case 0: putchar('0'); break;
 451         case 1: putchar('1'); break;
 452         case 3: putchar('-'); putchar('1'); break;
 453         default: putchar('E');
 454         }
 455         if(length){
 456             putchar(' ');
 457         }
 458     }while(length--);
 459 }
 460
 461 uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest,
 462                                           const bigint_t *k,
 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);
 467         return 0;
 468     }
 469
 470     uint8_t *t, q;
 471     uint16_t i;
 472     ecc_chudnovsky_point_t p_;
 473     bigint_word_t y_[curve->p->length_W];
 474
 475     /* p_ = -p*/
 476
 477     memcpy(&p_, p, sizeof(p_));
 478     p_.y.wordv = y_;
 479     bigint_copy(&p_.y, &p->y);
 480     p_.y.info |= BIGINT_NEG_MASK;
 481     bigint_add_s(&p_.y, &p_.y, curve->p);
 482
 483
 484     if(!(t = calloc(k->length_W * sizeof(bigint_word_t) * 2 + 1, 1))){
 485         return 1;
 486     }
 487     bigint_to_naf(t, &i, k);
 488
 489     printf(" naf: ");
 490     print_naf(t, i);
 491
 492     --i;
 493     dest->y.length_W = 0;
 494     do{
 495         q = (t[(i * 2) / 8] >> ((i * 2) & 7)) & 3;
 496         ecc_chudnovsky_point_double_sp(dest, dest, curve);
 497         if(q == 1){
 498             ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
 499         }
 500         if(q == 3){
 501             ecc_chudnovsky_point_add_sp(dest, dest, &p_, curve);
 502         }
 503     }while(i--);
 504
 505     free(t);
 506
 507     return 0;
 508 }
 509
 510 uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest,
 511                                       const bigint_t *k,
 512                                       const ecc_chudnovsky_point_t *p,
 513                                       const ecc_curve_sp_t* curve){
 514     return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);
 515 }
 516
 517
 518
 519 uint8_t ecc_chudnovsky_multipy_and_sum(ecc_chudnovsky_point_t *dest,
 520                                       const bigint_t *k,
 521                                       const ecc_chudnovsky_point_t *p,
 522                                       const bigint_t *l,
 523                                       const ecc_chudnovsky_point_t *q,
 524                                       const ecc_curve_sp_t* curve){
 525     return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);
 526 }