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_mulmod.c 21 ECC Crypto, Tom St Denis 22 */ 23 24 #ifdef MECC 25 #ifndef LTC_ECC_TIMING_RESISTANT 26 27 /* size of sliding window, don't change this! */ 28 #define WINSIZE 4 29 30 /** 31 Perform a point multiplication 32 @param k The scalar to multiply by 33 @param G The base point 34 @param R [out] Destination for kG 35 @param modulus The modulus of the field the ECC curve is in 36 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective) 37 @return CRYPT_OK on success 38 */ 39 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map) 40 { 41 ecc_point *tG, *M[8]; 42 int i, j, err; 43 void *mu, *mp; 44 unsigned long buf; 45 int first, bitbuf, bitcpy, bitcnt, mode, digidx; 46 47 LTC_ARGCHK(k != NULL); 48 LTC_ARGCHK(G != NULL); 49 LTC_ARGCHK(R != NULL); 50 LTC_ARGCHK(modulus != NULL); 51 52 /* init montgomery reduction */ 53 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { 54 return err; 55 } 56 if ((err = mp_init(&mu)) != CRYPT_OK) { 57 mp_montgomery_free(mp); 58 return err; 59 } 60 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { 61 mp_montgomery_free(mp); 62 mp_clear(mu); 63 return err; 64 } 65 66 /* alloc ram for window temps */ 67 for (i = 0; i < 8; i++) { 68 M[i] = ltc_ecc_new_point(); 69 if (M[i] == NULL) { 70 for (j = 0; j < i; j++) { 71 ltc_ecc_del_point(M[j]); 72 } 73 mp_montgomery_free(mp); 74 mp_clear(mu); 75 return CRYPT_MEM; 76 } 77 } 78 79 /* make a copy of G incase R==G */ 80 tG = ltc_ecc_new_point(); 81 if (tG == NULL) { err = CRYPT_MEM; goto done; } 82 83 /* tG = G and convert to montgomery */ 84 if (mp_cmp_d(mu, 1) == LTC_MP_EQ) { 85 if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK) { goto done; } 86 if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK) { goto done; } 87 if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK) { goto done; } 88 } else { 89 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; } 90 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; } 91 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; } 92 } 93 mp_clear(mu); 94 mu = NULL; 95 96 /* calc the M tab, which holds kG for k==8..15 */ 97 /* M[0] == 8G */ 98 if ((err = ltc_mp.ecc_ptdbl(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; } 99 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; } 100 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; } 101 102 /* now find (8+k)G for k=1..7 */ 103 for (j = 9; j < 16; j++) { 104 if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; } 105 } 106 107 /* setup sliding window */ 108 mode = 0; 109 bitcnt = 1; 110 buf = 0; 111 digidx = mp_get_digit_count(k) - 1; 112 bitcpy = bitbuf = 0; 113 first = 1; 114 115 /* perform ops */ 116 for (;;) { 117 /* grab next digit as required */ 118 if (--bitcnt == 0) { 119 if (digidx == -1) { 120 break; 121 } 122 buf = mp_get_digit(k, digidx); 123 bitcnt = (int) ltc_mp.bits_per_digit; 124 --digidx; 125 } 126 127 /* grab the next msb from the ltiplicand */ 128 i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1; 129 buf <<= 1; 130 131 /* skip leading zero bits */ 132 if (mode == 0 && i == 0) { 133 continue; 134 } 135 136 /* if the bit is zero and mode == 1 then we double */ 137 if (mode == 1 && i == 0) { 138 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } 139 continue; 140 } 141 142 /* else we add it to the window */ 143 bitbuf |= (i << (WINSIZE - ++bitcpy)); 144 mode = 2; 145 146 if (bitcpy == WINSIZE) { 147 /* if this is the first window we do a simple copy */ 148 if (first == 1) { 149 /* R = kG [k = first window] */ 150 if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK) { goto done; } 151 if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK) { goto done; } 152 if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK) { goto done; } 153 first = 0; 154 } else { 155 /* normal window */ 156 /* ok window is filled so double as required and add */ 157 /* double first */ 158 for (j = 0; j < WINSIZE; j++) { 159 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } 160 } 161 162 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */ 163 if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; } 164 } 165 /* empty window and reset */ 166 bitcpy = bitbuf = 0; 167 mode = 1; 168 } 169 } 170 171 /* if bits remain then double/add */ 172 if (mode == 2 && bitcpy > 0) { 173 /* double then add */ 174 for (j = 0; j < bitcpy; j++) { 175 /* only double if we have had at least one add first */ 176 if (first == 0) { 177 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } 178 } 179 180 bitbuf <<= 1; 181 if ((bitbuf & (1 << WINSIZE)) != 0) { 182 if (first == 1){ 183 /* first add, so copy */ 184 if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK) { goto done; } 185 if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK) { goto done; } 186 if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK) { goto done; } 187 first = 0; 188 } else { 189 /* then add */ 190 if ((err = ltc_mp.ecc_ptadd(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; } 191 } 192 } 193 } 194 } 195 196 /* map R back from projective space */ 197 if (map) { 198 err = ltc_ecc_map(R, modulus, mp); 199 } else { 200 err = CRYPT_OK; 201 } 202 done: 203 if (mu != NULL) { 204 mp_clear(mu); 205 } 206 mp_montgomery_free(mp); 207 ltc_ecc_del_point(tG); 208 for (i = 0; i < 8; i++) { 209 ltc_ecc_del_point(M[i]); 210 } 211 return err; 212 } 213 214 #endif 215 216 #undef WINSIZE 217 218 #endif 219 220 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod.c,v $ */ 221 /* $Revision: 1.24 $ */ 222 /* $Date: 2006/12/04 05:07:59 $ */ 223
