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 /*
  42  * if (Y == 0)
  43  *   return POINT_AT_INFINITY
  44  * S = 4*X*Y^2
  45  * M = 3*(X + Z^2)*(X - Z^2)
  46  * X' = M^2 - 2*S
  47  * Y' = M*(S - X') - 8*Y^4
  48  * Z' = 2*Y*Z
  49  * Z'^2 = Z'^2
  50  * Z'^3 = Z'^2 * Z'
  51  * return (X', Y', Z', Z'^2, Z'^3)
  52  */
  53
  54 uint8_t ecc_affine_to_chudnovsky_point(ecc_chudnovsky_point_t *dest,
  55                                        const ecc_affine_point_t *src){
  56     if(src->y.length_W == 0){
  57         /* point at infinity */
  58         bigint_set_zero(&dest->y);
  59         return 0;
  60     }
  61     bigint_copy(&dest->x, &src->x);
  62     bigint_copy(&dest->y, &src->y);
  63     dest->z1.wordv[0] = 1;
  64     dest->z2.wordv[0] = 1;
  65     dest->z3.wordv[0] = 1;
  66     dest->z1.length_W = 1;
  67     dest->z2.length_W = 1;
  68     dest->z3.length_W = 1;
  69     dest->z1.info = 0;
  70     dest->z2.info = 0;
  71     dest->z3.info = 0;
  72     bigint_adjust(&dest->z1);
  73     bigint_adjust(&dest->z2);
  74     bigint_adjust(&dest->z3);
  75     return 0;
  76 }
  77
  78 uint8_t ecc_chudnovsky_to_affine_point(ecc_affine_point_t *dest,
  79                                        const ecc_chudnovsky_point_t *src,
  80                                        const ecc_curve_sp_t *curve){
  81     if(src->y.length_W == 0){
  82         /* point at infinity */
  83         bigint_set_zero(&dest->y);
  84         return 0;
  85     }
  86     bigint_word_t t_w[curve->p->length_W * 2];
  87     bigint_word_t z1_w[curve->p->length_W * 2];
  88     bigint_word_t z2_w[curve->p->length_W];
  89     bigint_t t, z1, z2;
  90     t.wordv =  t_w;
  91     z1.wordv = z1_w;
  92     z2.wordv = z2_w;
  93
  94     bigint_inverse(&z1, &src->z1, curve->p);
  95     bigint_square(&t, &z1);
  96     curve->reduce_p(&t);
  97     bigint_copy(&z2, &t);
  98     bigint_mul_u(&t, &src->x, &z2);
  99     curve->reduce_p(&t);
 100     bigint_copy(&dest->x, &t);
 101     bigint_mul_u(&t, &z1, &z2);
 102     curve->reduce_p(&t);
 103     bigint_mul_u(&t, &t, &src->y);
 104     curve->reduce_p(&t);
 105     bigint_copy(&dest->y, &t);
 106
 107     return 0;
 108 }
 109
 110 void ecc_chudnovsky_point_print(const ecc_chudnovsky_point_t *p){
 111     if(p->y.length_W == 0){
 112         printf_P(PSTR(" ECC point = point-at-infinity\n"));
 113         return;
 114     }
 115     printf_P(PSTR(" ECC point x  = "));
 116     bigint_print_hex(&p->x);
 117     printf_P(PSTR("\n ECC point y  = "));
 118     bigint_print_hex(&p->y);
 119     printf_P(PSTR("\n ECC point z1 = "));
 120     bigint_print_hex(&p->z1);
 121     printf_P(PSTR("\n ECC point z2 = "));
 122     bigint_print_hex(&p->z2);
 123     printf_P(PSTR("\n ECC point z3 = "));
 124     bigint_print_hex(&p->z3);
 125     putchar('\n');
 126 }
 127
 128 uint8_t ecc_chudnovsky_point_double_sp(ecc_chudnovsky_point_t *dest,
 129                                        const ecc_chudnovsky_point_t *a,
 130                                        const ecc_curve_sp_t *curve){
 131     if(a->y.length_W == 0){
 132         /* point at infinity */
 133         bigint_set_zero(&dest->y);
 134         return 0;
 135     }
 136     bigint_word_t s_w[curve->p->length_W * 2];
 137     bigint_word_t m_w[curve->p->length_W * 2];
 138     bigint_word_t t_w[curve->p->length_W * 2];
 139     bigint_t s, m, t;
 140
 141     s.wordv = s_w;
 142     m.wordv = m_w;
 143     t.wordv = t_w;
 144
 145     /* compute s*/
 146     bigint_square(&t, &a->y);
 147     curve->reduce_p(&t);
 148     bigint_mul_u(&s, &t, &a->x);
 149     curve->reduce_p(&s);
 150     bigint_shiftleft(&s, 2);
 151     curve->reduce_p(&s);
 152
 153     /* compute m */
 154     bigint_sub_u(&t, &a->x, &a->z2);
 155 //    /**/curve->reduce_p(&t);
 156     bigint_add_u(&m, &a->x, &a->z2);
 157 //    /**/curve->reduce_p(&m);
 158     bigint_mul_s(&m, &m, &t);
 159     curve->reduce_p(&m);
 160     bigint_copy(&t, &m);
 161     bigint_shiftleft(&t, 1);
 162     bigint_add_s(&m, &m, &t);
 163     curve->reduce_p(&m);
 164
 165     /* compute new z1 */
 166     bigint_mul_u(&t, &a->z1, &a->y);
 167     curve->reduce_p(&t);
 168     bigint_shiftleft(&t, 1);
 169     curve->reduce_p(&t);
 170     bigint_copy(&dest->z1, &t);
 171
 172     /* compute new x */
 173     bigint_square(&t, &m);
 174     curve->reduce_p(&t);
 175     bigint_sub_s(&t, &t, &s);
 176     bigint_sub_s(&t, &t, &s);
 177     curve->reduce_p(&t);
 178     bigint_copy(&dest->x, &t);
 179
 180     /* compute new y */
 181     bigint_sub_s(&s, &s, &t);
 182     curve->reduce_p(&s);
 183     bigint_mul_s(&s, &s, &m);
 184     curve->reduce_p(&s);
 185     bigint_square(&t, &a->y);
 186     curve->reduce_p(&t);
 187     bigint_square(&t, &t);
 188     curve->reduce_p(&t);
 189     bigint_shiftleft(&t, 3);
 190     curve->reduce_p(&t);
 191     bigint_sub_s(&s, &s, &t);
 192     curve->reduce_p(&s);
 193     bigint_copy(&dest->y, &s);
 194
 195     /* compute new z2 */
 196     bigint_square(&t, &dest->z1);
 197     curve->reduce_p(&t);
 198     bigint_copy(&dest->z2, &t);
 199
 200     /* compute new z3 */
 201     bigint_mul_u(&t, &t, &dest->z1);
 202     curve->reduce_p(&t);
 203     bigint_copy(&dest->z3, &t);
 204
 205     return 0;
 206 }
 207
 208 void ecc_chudnovsky_point_copy(ecc_chudnovsky_point_t *dest,
 209                                const ecc_chudnovsky_point_t *src){
 210     bigint_copy(&dest->x, &src->x);
 211     bigint_copy(&dest->y, &src->y);
 212     bigint_copy(&dest->z1, &src->z1);
 213     bigint_copy(&dest->z2, &src->z2);
 214     bigint_copy(&dest->z3, &src->z3);
 215 }
 216
 217 uint8_t ecc_chudnovsky_point_add_sp(ecc_chudnovsky_point_t *dest,
 218                                     const ecc_chudnovsky_point_t *a,
 219                                     const ecc_chudnovsky_point_t *b,
 220                                     const ecc_curve_sp_t *curve){
 221     if(a->y.length_W == 0){
 222         ecc_chudnovsky_point_copy(dest, b);
 223         return 0;
 224     }
 225     if(b->y.length_W == 0){
 226         ecc_chudnovsky_point_copy(dest, a);
 227         return 0;
 228     }
 229     bigint_word_t u1_w[curve->p->length_W * 2];
 230     bigint_word_t u2_w[curve->p->length_W * 2];
 231     bigint_word_t s1_w[curve->p->length_W * 2];
 232     bigint_word_t s2_w[curve->p->length_W * 2];
 233     bigint_t u1, u2, s1, s2;
 234
 235     u1.wordv = u1_w;
 236     u2.wordv = u2_w;
 237     s1.wordv = s1_w;
 238     s2.wordv = s2_w;
 239
 240     /* compute u1 */
 241     bigint_mul_u(&u1, &a->x, &b->z2);
 242     curve->reduce_p(&u1);
 243
 244     /* compute u2 */
 245     bigint_mul_u(&u2, &b->x, &a->z2);
 246     curve->reduce_p(&u2);
 247
 248     /* compute s1 */
 249     bigint_mul_u(&s1, &a->y, &b->z3);
 250     curve->reduce_p(&s1);
 251
 252     /* compute s2 */
 253     bigint_mul_u(&s2, &b->y, &a->z3);
 254     curve->reduce_p(&s2);
 255
 256     if(bigint_cmp_u(&u1, &u2) == 0){
 257         if(bigint_cmp_u(&s1, &s2)){
 258             /* point at infinity */
 259             bigint_set_zero(&dest->y);
 260             return 0;
 261         }else{
 262             /* a == b --> dest = 2*a */
 263             ecc_chudnovsky_point_double_sp(dest, a, curve);
 264         }
 265     }
 266
 267     bigint_word_t h_w[curve->p->length_W * 2];
 268     bigint_word_t r_w[curve->p->length_W * 2];
 269     bigint_t h, r;
 270
 271     h.wordv = h_w;
 272     r.wordv = r_w;
 273     /* compute h */
 274     bigint_sub_s(&h, &u2, &u1);
 275     /**/curve->reduce_p(&h);
 276
 277     /* compute r */
 278     bigint_sub_s(&r, &s2, &s1);
 279 //    /**/curve->reduce_p(&r);
 280
 281     /* compute new z */
 282     bigint_mul_u(&s2, &a->z1, &b->z1);
 283     curve->reduce_p(&s2);
 284     bigint_mul_s(&s2, &s2, &h);
 285     curve->reduce_p(&s2);
 286     bigint_copy(&dest->z1, &s2);
 287
 288     /* compute u1*h^2 and h^3 */
 289     bigint_square(&s2, &h);
 290     curve->reduce_p(&s2);
 291     bigint_mul_s(&h, &s2, &h);
 292     curve->reduce_p(&h);
 293     bigint_mul_s(&u1, &s2, &u1);
 294     curve->reduce_p(&u1);
 295
 296     /* compute new x */
 297     bigint_square(&u2, &r);
 298     curve->reduce_p(&u2);
 299     bigint_sub_s(&u2, &u2, &h);
 300     curve->reduce_p(&u2);
 301     bigint_sub_s(&u2, &u2, &u1);
 302     bigint_sub_s(&u2, &u2, &u1);
 303     curve->reduce_p(&u2);
 304     bigint_copy(&dest->x, &u2);
 305
 306     /* compute new y */
 307     bigint_sub_s(&u1, &u1, &u2);
 308     curve->reduce_p(&u1);
 309     bigint_mul_s(&s2, &u1, &r);
 310     curve->reduce_p(&s2);
 311     bigint_mul_s(&s1, &s1, &h);
 312     curve->reduce_p(&s1);
 313     bigint_sub_s(&s2, &s2, &s1);
 314     curve->reduce_p(&s2);
 315     bigint_copy(&dest->y, &s2);
 316
 317
 318     /* compute new z2 */
 319     bigint_square(&s1, &dest->z1);
 320     curve->reduce_p(&s1);
 321     bigint_copy(&dest->z2, &s1);
 322
 323     /* compute new z2 */
 324     bigint_mul_u(&s1, &s1, &dest->z1);
 325     curve->reduce_p(&s1);
 326     bigint_copy(&dest->z3, &s1);
 327
 328     return 0;
 329 }
 330
 331 uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest,
 332                                       const bigint_t *k,
 333                                       const ecc_chudnovsky_point_t *p,
 334                                       const ecc_curve_sp_t* curve){
 335     uint16_t i;
 336     uint8_t s = 0;
 337     bigint_word_t v, t;
 338
 339     for(i = k->length_W; i > 0; --i){
 340         v = 1 << (BIGINT_WORD_SIZE - 1);
 341         t = k->wordv[i - 1];
 342         do{
 343             if(s){
 344                 ecc_chudnovsky_point_double_sp(dest, dest, curve);
 345                 if(v & t){
 346                     ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
 347                 }
 348             }else{
 349                 if(v & t){
 350                     s = 1;
 351                     ecc_chudnovsky_point_copy(dest, p);
 352                 }
 353             }
 354             v >>= 1;
 355         }while(v);
 356     }
 357     return 0;
 358 }
 359
 360 uint8_t bigint_to_naf(uint8_t* dest, uint16_t *length, const bigint_t *src){
 361     if(src->length_W == 0){
 362         *dest = 0;
 363         *length = 2;
 364         return 0;
 365     }
 366
 367     memset(dest, 0, src->length_W * sizeof(bigint_word_t));
 368
 369     uint16_t i = 0;
 370     uint8_t t; /* 3 -> -1 ; 1 -> 1; 0 -> 0 (2 should not happen) */
 371     bigint_t k, p;
 372     bigint_word_t k_w[src->length_W];
 373     bigint_word_t p_w = 1;
 374     p.wordv = &p_w;
 375     p.info = 0;
 376     p.length_W = 1;
 377     k.wordv = k_w;
 378     bigint_copy(&k, src);
 379
 380     while(k.length_W >= 1){
 381         if(k.wordv[0] & 1){
 382             t = k.wordv[0] & 3;
 383             if(t == 1){
 384                 bigint_sub_u(&k, &k, &p);
 385             }else{
 386                 bigint_add_u(&k, &k, &p);
 387             }
 388         }else{
 389             t = 0;
 390         }
 391         dest[(i * 2) / 8] |= t << ((2 * i) & 7);
 392         bigint_shiftright(&k, 1);
 393         i += 1;
 394     }
 395     *length = i;
 396     return 0;
 397 }
 398
 399 void print_naf(uint8_t* naf, uint16_t length){
 400     if(!length){
 401         return;
 402     }
 403     --length;
 404     int8_t t;
 405     do{
 406         t = (naf[(length * 2) / 8] >> ((length * 2) & 7)) & 3;
 407         switch(t & 3){
 408         case 0: putchar('0'); break;
 409         case 1: putchar('1'); break;
 410         case 3: putchar('-'); putchar('1'); break;
 411         default: putchar('E');
 412         }
 413         if(length){
 414             putchar(' ');
 415         }
 416     }while(length--);
 417 }
 418
 419 uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest,
 420                                           const bigint_t *k,
 421                                           const ecc_chudnovsky_point_t *p,
 422                                           const ecc_curve_sp_t* curve){
 423     if(k->length_W == 0 || p->y.length_W == 0){
 424         bigint_set_zero(&dest->y);
 425         return 0;
 426     }
 427
 428     uint8_t *t, q;
 429     uint16_t i;
 430     ecc_chudnovsky_point_t p_;
 431     bigint_word_t y_[curve->p->length_W];
 432
 433     /* p_ = -p*/
 434
 435     memcpy(&p_, p, sizeof(p_));
 436     p_.y.wordv = y_;
 437     bigint_copy(&p_.y, &p->y);
 438     p_.y.info |= BIGINT_NEG_MASK;
 439     bigint_add_s(&p_.y, &p_.y, curve->p);
 440
 441
 442     if(!(t = malloc(k->length_W * sizeof(bigint_word_t) * 2))){
 443         return 1;
 444     }
 445     bigint_to_naf(t, &i, k);
 446
 447     --i;
 448     dest->y.length_W = 0;
 449     do{
 450         q = (t[(i * 2) / 8] >> ((i * 2) & 7)) & 3;
 451         ecc_chudnovsky_point_double_sp(dest, dest, curve);
 452         if(q == 1){
 453             ecc_chudnovsky_point_add_sp(dest, dest, p, curve);
 454         }
 455         if(q == 3){
 456             ecc_chudnovsky_point_add_sp(dest, dest, &p_, curve);
 457         }
 458     }while(i--);
 459
 460     free(t);
 461
 462     return 0;
 463 }
 464
 465 uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest,
 466                                       const bigint_t *k,
 467                                       const ecc_chudnovsky_point_t *p,
 468                                       const ecc_curve_sp_t* curve){
 469     return ecc_chudnovsky_naf_multiplication(dest, k, p, curve);
 470 }