| /* LibTomCrypt, modular cryptographic library -- Tom St Denis |
| * |
| * LibTomCrypt is a library that provides various cryptographic |
| * algorithms in a highly modular and flexible manner. |
| * |
| * The library is free for all purposes without any express |
| * guarantee it works. |
| * |
| * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com |
| */ |
| |
| /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b |
| * |
| * All curves taken from NIST recommendation paper of July 1999 |
| * Available at http://csrc.nist.gov/cryptval/dss.htm |
| */ |
| #include "tomcrypt.h" |
| |
| /** |
| @file ltc_ecc_mulmod.c |
| ECC Crypto, Tom St Denis |
| */ |
| |
| #ifdef MECC |
| #ifndef LTC_ECC_TIMING_RESISTANT |
| |
| /* size of sliding window, don't change this! */ |
| #define WINSIZE 4 |
| |
| /** |
| Perform a point multiplication |
| @param k The scalar to multiply by |
| @param G The base point |
| @param R [out] Destination for kG |
| @param modulus The modulus of the field the ECC curve is in |
| @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective) |
| @return CRYPT_OK on success |
| */ |
| int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map) |
| { |
| ecc_point *tG, *M[8]; |
| int i, j, err; |
| void *mu, *mp; |
| unsigned long buf; |
| int first, bitbuf, bitcpy, bitcnt, mode, digidx; |
| |
| LTC_ARGCHK(k != NULL); |
| LTC_ARGCHK(G != NULL); |
| LTC_ARGCHK(R != NULL); |
| LTC_ARGCHK(modulus != NULL); |
| |
| /* init montgomery reduction */ |
| if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { |
| return err; |
| } |
| if ((err = mp_init(&mu)) != CRYPT_OK) { |
| mp_montgomery_free(mp); |
| return err; |
| } |
| if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { |
| mp_montgomery_free(mp); |
| mp_clear(mu); |
| return err; |
| } |
| |
| /* alloc ram for window temps */ |
| for (i = 0; i < 8; i++) { |
| M[i] = ltc_ecc_new_point(); |
| if (M[i] == NULL) { |
| for (j = 0; j < i; j++) { |
| ltc_ecc_del_point(M[j]); |
| } |
| mp_montgomery_free(mp); |
| mp_clear(mu); |
| return CRYPT_MEM; |
| } |
| } |
| |
| /* make a copy of G incase R==G */ |
| tG = ltc_ecc_new_point(); |
| if (tG == NULL) { err = CRYPT_MEM; goto done; } |
| |
| /* tG = G and convert to montgomery */ |
| if (mp_cmp_d(mu, 1) == LTC_MP_EQ) { |
| if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK) { goto done; } |
| } else { |
| if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; } |
| if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; } |
| if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; } |
| } |
| mp_clear(mu); |
| mu = NULL; |
| |
| /* calc the M tab, which holds kG for k==8..15 */ |
| /* M[0] == 8G */ |
| if ((err = ltc_mp.ecc_ptdbl(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; } |
| if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; } |
| if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; } |
| |
| /* now find (8+k)G for k=1..7 */ |
| for (j = 9; j < 16; j++) { |
| if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; } |
| } |
| |
| /* setup sliding window */ |
| mode = 0; |
| bitcnt = 1; |
| buf = 0; |
| digidx = mp_get_digit_count(k) - 1; |
| bitcpy = bitbuf = 0; |
| first = 1; |
| |
| /* perform ops */ |
| for (;;) { |
| /* grab next digit as required */ |
| if (--bitcnt == 0) { |
| if (digidx == -1) { |
| break; |
| } |
| buf = mp_get_digit(k, digidx); |
| bitcnt = (int) ltc_mp.bits_per_digit; |
| --digidx; |
| } |
| |
| /* grab the next msb from the ltiplicand */ |
| i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1; |
| buf <<= 1; |
| |
| /* skip leading zero bits */ |
| if (mode == 0 && i == 0) { |
| continue; |
| } |
| |
| /* if the bit is zero and mode == 1 then we double */ |
| if (mode == 1 && i == 0) { |
| if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } |
| continue; |
| } |
| |
| /* else we add it to the window */ |
| bitbuf |= (i << (WINSIZE - ++bitcpy)); |
| mode = 2; |
| |
| if (bitcpy == WINSIZE) { |
| /* if this is the first window we do a simple copy */ |
| if (first == 1) { |
| /* R = kG [k = first window] */ |
| if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK) { goto done; } |
| first = 0; |
| } else { |
| /* normal window */ |
| /* ok window is filled so double as required and add */ |
| /* double first */ |
| for (j = 0; j < WINSIZE; j++) { |
| if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } |
| } |
| |
| /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */ |
| if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; } |
| } |
| /* empty window and reset */ |
| bitcpy = bitbuf = 0; |
| mode = 1; |
| } |
| } |
| |
| /* if bits remain then double/add */ |
| if (mode == 2 && bitcpy > 0) { |
| /* double then add */ |
| for (j = 0; j < bitcpy; j++) { |
| /* only double if we have had at least one add first */ |
| if (first == 0) { |
| if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; } |
| } |
| |
| bitbuf <<= 1; |
| if ((bitbuf & (1 << WINSIZE)) != 0) { |
| if (first == 1){ |
| /* first add, so copy */ |
| if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK) { goto done; } |
| if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK) { goto done; } |
| first = 0; |
| } else { |
| /* then add */ |
| if ((err = ltc_mp.ecc_ptadd(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; } |
| } |
| } |
| } |
| } |
| |
| /* map R back from projective space */ |
| if (map) { |
| err = ltc_ecc_map(R, modulus, mp); |
| } else { |
| err = CRYPT_OK; |
| } |
| done: |
| if (mu != NULL) { |
| mp_clear(mu); |
| } |
| mp_montgomery_free(mp); |
| ltc_ecc_del_point(tG); |
| for (i = 0; i < 8; i++) { |
| ltc_ecc_del_point(M[i]); |
| } |
| return err; |
| } |
| |
| #endif |
| |
| #undef WINSIZE |
| |
| #endif |
| |
| /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod.c,v $ */ |
| /* $Revision: 1.24 $ */ |
| /* $Date: 2006/12/04 05:07:59 $ */ |
