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