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