pd.if.org Git - zpackage/blob - libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c

   1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
   2  *
   3  * LibTomCrypt is a library that provides various cryptographic
   4  * algorithms in a highly modular and flexible manner.
   5  *
   6  * The library is free for all purposes without any express
   7  * guarantee it works.
   8  */
   9
  10 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
  11  *
  12  * All curves taken from NIST recommendation paper of July 1999
  13  * Available at http://csrc.nist.gov/cryptval/dss.htm
  14  */
  15 #include "tomcrypt.h"
  16
  17 /**
  18   @file ltc_ecc_mulmod_timing.c
  19   ECC Crypto, Tom St Denis
  20 */
  21
  22 #ifdef LTC_MECC
  23
  24 #ifdef LTC_ECC_TIMING_RESISTANT
  25
  26 /**
  27    Perform a point multiplication  (timing resistant)
  28    @param k    The scalar to multiply by
  29    @param G    The base point
  30    @param R    [out] Destination for kG
  31    @param modulus  The modulus of the field the ECC curve is in
  32    @param map      Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
  33    @return CRYPT_OK on success
  34 */
  35 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
  36 {
  37    ecc_point *tG, *M[3];
  38    int        i, j, err;
  39    void       *mu, *mp;
  40    ltc_mp_digit buf;
  41    int        bitcnt, mode, digidx;
  42
  43    LTC_ARGCHK(k       != NULL);
  44    LTC_ARGCHK(G       != NULL);
  45    LTC_ARGCHK(R       != NULL);
  46    LTC_ARGCHK(modulus != NULL);
  47
  48    /* init montgomery reduction */
  49    if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
  50       return err;
  51    }
  52    if ((err = mp_init(&mu)) != CRYPT_OK) {
  53       mp_montgomery_free(mp);
  54       return err;
  55    }
  56    if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
  57       mp_clear(mu);
  58       mp_montgomery_free(mp);
  59       return err;
  60    }
  61
  62    /* alloc ram for window temps */
  63    for (i = 0; i < 3; i++) {
  64       M[i] = ltc_ecc_new_point();
  65       if (M[i] == NULL) {
  66          for (j = 0; j < i; j++) {
  67              ltc_ecc_del_point(M[j]);
  68          }
  69          mp_clear(mu);
  70          mp_montgomery_free(mp);
  71          return CRYPT_MEM;
  72       }
  73    }
  74
  75    /* make a copy of G incase R==G */
  76    tG = ltc_ecc_new_point();
  77    if (tG == NULL)                                                                   { err = CRYPT_MEM; goto done; }
  78
  79    /* tG = G  and convert to montgomery */
  80    if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK)                      { goto done; }
  81    if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK)                      { goto done; }
  82    if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK)                      { goto done; }
  83    mp_clear(mu);
  84    mu = NULL;
  85
  86    /* calc the M tab */
  87    /* M[0] == G */
  88    if ((err = mp_copy(tG->x, M[0]->x)) != CRYPT_OK)                                  { goto done; }
  89    if ((err = mp_copy(tG->y, M[0]->y)) != CRYPT_OK)                                  { goto done; }
  90    if ((err = mp_copy(tG->z, M[0]->z)) != CRYPT_OK)                                  { goto done; }
  91    /* M[1] == 2G */
  92    if ((err = ltc_mp.ecc_ptdbl(tG, M[1], modulus, mp)) != CRYPT_OK)                  { goto done; }
  93
  94    /* setup sliding window */
  95    mode   = 0;
  96    bitcnt = 1;
  97    buf    = 0;
  98    digidx = mp_get_digit_count(k) - 1;
  99
 100    /* perform ops */
 101    for (;;) {
 102      /* grab next digit as required */
 103       if (--bitcnt == 0) {
 104          if (digidx == -1) {
 105             break;
 106          }
 107          buf    = mp_get_digit(k, digidx);
 108          bitcnt = (int) MP_DIGIT_BIT;
 109          --digidx;
 110       }
 111
 112       /* grab the next msb from the ltiplicand */
 113       i = (buf >> (MP_DIGIT_BIT - 1)) & 1;
 114       buf <<= 1;
 115
 116       if (mode == 0 && i == 0) {
 117          /* dummy operations */
 118          if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK)    { goto done; }
 119          if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK)          { goto done; }
 120          continue;
 121       }
 122
 123       if (mode == 0 && i == 1) {
 124          mode = 1;
 125          /* dummy operations */
 126          if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK)    { goto done; }
 127          if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK)          { goto done; }
 128          continue;
 129       }
 130
 131       if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], modulus, mp)) != CRYPT_OK)     { goto done; }
 132       if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], modulus, mp)) != CRYPT_OK)             { goto done; }
 133    }
 134
 135    /* copy result out */
 136    if ((err = mp_copy(M[0]->x, R->x)) != CRYPT_OK)                                   { goto done; }
 137    if ((err = mp_copy(M[0]->y, R->y)) != CRYPT_OK)                                   { goto done; }
 138    if ((err = mp_copy(M[0]->z, R->z)) != CRYPT_OK)                                   { goto done; }
 139
 140    /* map R back from projective space */
 141    if (map) {
 142       err = ltc_ecc_map(R, modulus, mp);
 143    } else {
 144       err = CRYPT_OK;
 145    }
 146 done:
 147    if (mu != NULL) {
 148       mp_clear(mu);
 149    }
 150    mp_montgomery_free(mp);
 151    ltc_ecc_del_point(tG);
 152    for (i = 0; i < 3; i++) {
 153        ltc_ecc_del_point(M[i]);
 154    }
 155    return err;
 156 }
 157
 158 #endif
 159 #endif
 160 /* ref:         $Format:%D$ */
 161 /* git commit:  $Format:%H$ */
 162 /* commit time: $Format:%ai$ */
 163