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_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 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_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 bitcpy = bitbuf = 0; 102 first = 1; 103 104 /* perform ops */ 105 for (;;) { 106 /* grab next digit as required */ 107 if (--bitcnt == 0) { 108 if (digidx == -1) { 109 break; 110 } 111 buf = mp_get_digit(k, digidx); 112 bitcnt = (int) MP_DIGIT_BIT; 113 --digidx; 114 } 115 116 /* grab the next msb from the ltiplicand */ 117 i = (buf >> (MP_DIGIT_BIT - 1)) & 1; 118 buf <<= 1; 119 120 if (mode == 0 && i == 0) { 121 /* dummy operations */ 122 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; } 123 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; } 124 continue; 125 } 126 127 if (mode == 0 && i == 1) { 128 mode = 1; 129 /* dummy operations */ 130 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; } 131 if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK) { goto done; } 132 continue; 133 } 134 135 if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], modulus, mp)) != CRYPT_OK) { goto done; } 136 if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], modulus, mp)) != CRYPT_OK) { goto done; } 137 } 138 139 /* copy result out */ 140 if ((err = mp_copy(M[0]->x, R->x)) != CRYPT_OK) { goto done; } 141 if ((err = mp_copy(M[0]->y, R->y)) != CRYPT_OK) { goto done; } 142 if ((err = mp_copy(M[0]->z, R->z)) != CRYPT_OK) { goto done; } 143 144 /* map R back from projective space */ 145 if (map) { 146 err = ltc_ecc_map(R, modulus, mp); 147 } else { 148 err = CRYPT_OK; 149 } 150 done: 151 if (mu != NULL) { 152 mp_clear(mu); 153 } 154 mp_montgomery_free(mp); 155 ltc_ecc_del_point(tG); 156 for (i = 0; i < 3; i++) { 157 ltc_ecc_del_point(M[i]); 158 } 159 return err; 160 } 161 162 #endif 163 #endif 164 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */ 165 /* $Revision: 1.11 $ */ 166 /* $Date: 2006/12/04 22:17:46 $ */ 167 168
