pd.if.org Git - zpackage/blob - libtomcrypt/src/pk/ecc/ltc_ecc_mulmod.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.c
  19   ECC Crypto, Tom St Denis
  20 */
  21
  22 #ifdef LTC_MECC
  23 #ifndef LTC_ECC_TIMING_RESISTANT
  24
  25 /* size of sliding window, don't change this! */
  26 #define WINSIZE 4
  27
  28 /**
  29    Perform a point multiplication
  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[8];
  40    int        i, j, err;
  41    void       *mu, *mp;
  42    ltc_mp_digit buf;
  43    int        first, bitbuf, bitcpy, 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_montgomery_free(mp);
  60       mp_clear(mu);
  61       return err;
  62    }
  63
  64   /* alloc ram for window temps */
  65   for (i = 0; i < 8; 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_montgomery_free(mp);
  72          mp_clear(mu);
  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 (mp_cmp_d(mu, 1) == LTC_MP_EQ) {
  83       if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK)                                  { goto done; }
  84       if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK)                                  { goto done; }
  85       if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK)                                  { goto done; }
  86    } else {
  87       if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK)                   { goto done; }
  88       if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK)                   { goto done; }
  89       if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK)                   { goto done; }
  90    }
  91    mp_clear(mu);
  92    mu = NULL;
  93
  94    /* calc the M tab, which holds kG for k==8..15 */
  95    /* M[0] == 8G */
  96    if ((err = ltc_mp.ecc_ptdbl(tG, M[0], modulus, mp)) != CRYPT_OK)                 { goto done; }
  97    if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK)               { goto done; }
  98    if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK)               { goto done; }
  99
 100    /* now find (8+k)G for k=1..7 */
 101    for (j = 9; j < 16; j++) {
 102        if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK)   { goto done; }
 103    }
 104
 105    /* setup sliding window */
 106    mode   = 0;
 107    bitcnt = 1;
 108    buf    = 0;
 109    digidx = mp_get_digit_count(k) - 1;
 110    bitcpy = bitbuf = 0;
 111    first  = 1;
 112
 113    /* perform ops */
 114    for (;;) {
 115      /* grab next digit as required */
 116      if (--bitcnt == 0) {
 117        if (digidx == -1) {
 118           break;
 119        }
 120        buf    = mp_get_digit(k, digidx);
 121        bitcnt = (int) ltc_mp.bits_per_digit;
 122        --digidx;
 123      }
 124
 125      /* grab the next msb from the ltiplicand */
 126      i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1;
 127      buf <<= 1;
 128
 129      /* skip leading zero bits */
 130      if (mode == 0 && i == 0) {
 131         continue;
 132      }
 133
 134      /* if the bit is zero and mode == 1 then we double */
 135      if (mode == 1 && i == 0) {
 136         if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK)                 { goto done; }
 137         continue;
 138      }
 139
 140      /* else we add it to the window */
 141      bitbuf |= (i << (WINSIZE - ++bitcpy));
 142      mode = 2;
 143
 144      if (bitcpy == WINSIZE) {
 145        /* if this is the first window we do a simple copy */
 146        if (first == 1) {
 147           /* R = kG [k = first window] */
 148           if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK)                     { goto done; }
 149           if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK)                     { goto done; }
 150           if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK)                     { goto done; }
 151           first = 0;
 152        } else {
 153          /* normal window */
 154          /* ok window is filled so double as required and add  */
 155          /* double first */
 156          for (j = 0; j < WINSIZE; j++) {
 157            if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK)              { goto done; }
 158          }
 159
 160          /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
 161          if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK)   { goto done; }
 162        }
 163        /* empty window and reset */
 164        bitcpy = bitbuf = 0;
 165        mode = 1;
 166     }
 167   }
 168
 169    /* if bits remain then double/add */
 170    if (mode == 2 && bitcpy > 0) {
 171      /* double then add */
 172      for (j = 0; j < bitcpy; j++) {
 173        /* only double if we have had at least one add first */
 174        if (first == 0) {
 175           if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK)              { goto done; }
 176        }
 177
 178        bitbuf <<= 1;
 179        if ((bitbuf & (1 << WINSIZE)) != 0) {
 180          if (first == 1){
 181             /* first add, so copy */
 182             if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK)                           { goto done; }
 183             if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK)                           { goto done; }
 184             if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK)                           { goto done; }
 185             first = 0;
 186          } else {
 187             /* then add */
 188             if ((err = ltc_mp.ecc_ptadd(R, tG, R, modulus, mp)) != CRYPT_OK)        { goto done; }
 189          }
 190        }
 191      }
 192    }
 193
 194    /* map R back from projective space */
 195    if (map) {
 196       err = ltc_ecc_map(R, modulus, mp);
 197    } else {
 198       err = CRYPT_OK;
 199    }
 200 done:
 201    if (mu != NULL) {
 202       mp_clear(mu);
 203    }
 204    mp_montgomery_free(mp);
 205    ltc_ecc_del_point(tG);
 206    for (i = 0; i < 8; i++) {
 207        ltc_ecc_del_point(M[i]);
 208    }
 209    return err;
 210 }
 211
 212 #endif
 213
 214 #undef WINSIZE
 215
 216 #endif
 217
 218 /* ref:         $Format:%D$ */
 219 /* git commit:  $Format:%H$ */
 220 /* commit time: $Format:%ai$ */