pd.if.org Git - zpackage/blob - libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.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_mul2add.c
  19   ECC Crypto, Shamir's Trick, Tom St Denis
  20 */
  21
  22 #ifdef LTC_MECC
  23
  24 #ifdef LTC_ECC_SHAMIR
  25
  26 /** Computes kA*A + kB*B = C using Shamir's Trick
  27   @param A        First point to multiply
  28   @param kA       What to multiple A by
  29   @param B        Second point to multiply
  30   @param kB       What to multiple B by
  31   @param C        [out] Destination point (can overlap with A or B
  32   @param modulus  Modulus for curve
  33   @return CRYPT_OK on success
  34 */
  35 int ltc_ecc_mul2add(ecc_point *A, void *kA,
  36                     ecc_point *B, void *kB,
  37                     ecc_point *C,
  38                          void *modulus)
  39 {
  40   ecc_point     *precomp[16];
  41   unsigned       bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
  42   unsigned char *tA, *tB;
  43   int            err, first;
  44   void          *mp, *mu;
  45
  46   /* argchks */
  47   LTC_ARGCHK(A       != NULL);
  48   LTC_ARGCHK(B       != NULL);
  49   LTC_ARGCHK(C       != NULL);
  50   LTC_ARGCHK(kA      != NULL);
  51   LTC_ARGCHK(kB      != NULL);
  52   LTC_ARGCHK(modulus != NULL);
  53
  54   /* allocate memory */
  55   tA = XCALLOC(1, ECC_BUF_SIZE);
  56   if (tA == NULL) {
  57      return CRYPT_MEM;
  58   }
  59   tB = XCALLOC(1, ECC_BUF_SIZE);
  60   if (tB == NULL) {
  61      XFREE(tA);
  62      return CRYPT_MEM;
  63   }
  64
  65   /* get sizes */
  66   lenA = mp_unsigned_bin_size(kA);
  67   lenB = mp_unsigned_bin_size(kB);
  68   len  = MAX(lenA, lenB);
  69
  70   /* sanity check */
  71   if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) {
  72      err = CRYPT_INVALID_ARG;
  73      goto ERR_T;
  74   }
  75
  76   /* extract and justify kA */
  77   mp_to_unsigned_bin(kA, (len - lenA) + tA);
  78
  79   /* extract and justify kB */
  80   mp_to_unsigned_bin(kB, (len - lenB) + tB);
  81
  82   /* allocate the table */
  83   for (x = 0; x < 16; x++) {
  84      precomp[x] = ltc_ecc_new_point();
  85      if (precomp[x] == NULL) {
  86          for (y = 0; y < x; ++y) {
  87             ltc_ecc_del_point(precomp[y]);
  88          }
  89          err = CRYPT_MEM;
  90          goto ERR_T;
  91      }
  92   }
  93
  94   /* init montgomery reduction */
  95   if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
  96       goto ERR_P;
  97   }
  98   if ((err = mp_init(&mu)) != CRYPT_OK) {
  99       goto ERR_MP;
 100   }
 101   if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
 102       goto ERR_MU;
 103   }
 104
 105   /* copy ones ... */
 106   if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK)                                         { goto ERR_MU; }
 107   if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK)                                         { goto ERR_MU; }
 108   if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK)                                         { goto ERR_MU; }
 109
 110   if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK)                                      { goto ERR_MU; }
 111   if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK)                                      { goto ERR_MU; }
 112   if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK)                                      { goto ERR_MU; }
 113
 114   /* precomp [i,0](A + B) table */
 115   if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], modulus, mp)) != CRYPT_OK)                               { goto ERR_MU; }
 116   if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], modulus, mp)) != CRYPT_OK)                   { goto ERR_MU; }
 117
 118   /* precomp [0,i](A + B) table */
 119   if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], modulus, mp)) != CRYPT_OK)                         { goto ERR_MU; }
 120   if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], modulus, mp)) != CRYPT_OK)          { goto ERR_MU; }
 121
 122   /* precomp [i,j](A + B) table (i != 0, j != 0) */
 123   for (x = 1; x < 4; x++) {
 124      for (y = 1; y < 4; y++) {
 125         if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
 126      }
 127   }
 128
 129   nibble  = 3;
 130   first   = 1;
 131   bitbufA = tA[0];
 132   bitbufB = tB[0];
 133
 134   /* for every byte of the multiplicands */
 135   for (x = 0;; ) {
 136      /* grab a nibble */
 137      if (++nibble == 4) {
 138         if (x == len) break;
 139         bitbufA = tA[x];
 140         bitbufB = tB[x];
 141         nibble  = 0;
 142         ++x;
 143      }
 144
 145      /* extract two bits from both, shift/update */
 146      nA = (bitbufA >> 6) & 0x03;
 147      nB = (bitbufB >> 6) & 0x03;
 148      bitbufA = (bitbufA << 2) & 0xFF;
 149      bitbufB = (bitbufB << 2) & 0xFF;
 150
 151      /* if both zero, if first, continue */
 152      if ((nA == 0) && (nB == 0) && (first == 1)) {
 153         continue;
 154      }
 155
 156      /* double twice, only if this isn't the first */
 157      if (first == 0) {
 158         /* double twice */
 159         if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
 160         if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
 161      }
 162
 163      /* if not both zero */
 164      if ((nA != 0) || (nB != 0)) {
 165         if (first == 1) {
 166            /* if first, copy from table */
 167            first = 0;
 168            if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK)           { goto ERR_MU; }
 169            if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK)           { goto ERR_MU; }
 170            if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK)           { goto ERR_MU; }
 171         } else {
 172            /* if not first, add from table */
 173            if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
 174         }
 175      }
 176   }
 177
 178   /* reduce to affine */
 179   err = ltc_ecc_map(C, modulus, mp);
 180
 181   /* clean up */
 182 ERR_MU:
 183    mp_clear(mu);
 184 ERR_MP:
 185    mp_montgomery_free(mp);
 186 ERR_P:
 187    for (x = 0; x < 16; x++) {
 188        ltc_ecc_del_point(precomp[x]);
 189    }
 190 ERR_T:
 191 #ifdef LTC_CLEAN_STACK
 192    zeromem(tA, ECC_BUF_SIZE);
 193    zeromem(tB, ECC_BUF_SIZE);
 194 #endif
 195    XFREE(tA);
 196    XFREE(tB);
 197
 198    return err;
 199 }
 200
 201 #endif
 202 #endif
 203
 204 /* ref:         $Format:%D$ */
 205 /* git commit:  $Format:%H$ */
 206 /* commit time: $Format:%ai$ */