/* 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_mul2add.c ECC Crypto, Shamir's Trick, Tom St Denis */ #ifdef MECC #ifdef LTC_ECC_SHAMIR /** Computes kA*A + kB*B = C using Shamir's Trick @param A First point to multiply @param kA What to multiple A by @param B Second point to multiply @param kB What to multiple B by @param C [out] Destination point (can overlap with A or B @param modulus Modulus for curve @return CRYPT_OK on success */ int ltc_ecc_mul2add(ecc_point *A, void *kA, ecc_point *B, void *kB, ecc_point *C, void *modulus) { ecc_point *precomp[16]; unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble; unsigned char *tA, *tB; int err, first; void *mp, *mu; /* argchks */ LTC_ARGCHK(A != NULL); LTC_ARGCHK(B != NULL); LTC_ARGCHK(C != NULL); LTC_ARGCHK(kA != NULL); LTC_ARGCHK(kB != NULL); LTC_ARGCHK(modulus != NULL); /* allocate memory */ tA = XCALLOC(1, ECC_BUF_SIZE); if (tA == NULL) { return CRYPT_MEM; } tB = XCALLOC(1, ECC_BUF_SIZE); if (tB == NULL) { XFREE(tA); return CRYPT_MEM; } /* get sizes */ lenA = mp_unsigned_bin_size(kA); lenB = mp_unsigned_bin_size(kB); len = MAX(lenA, lenB); /* sanity check */ if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) { err = CRYPT_INVALID_ARG; goto ERR_T; } /* extract and justify kA */ mp_to_unsigned_bin(kA, (len - lenA) + tA); /* extract and justify kB */ mp_to_unsigned_bin(kB, (len - lenB) + tB); /* allocate the table */ for (x = 0; x < 16; x++) { precomp[x] = ltc_ecc_new_point(); if (precomp[x] == NULL) { for (y = 0; y < x; ++y) { ltc_ecc_del_point(precomp[y]); } err = CRYPT_MEM; goto ERR_T; } } /* init montgomery reduction */ if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { goto ERR_P; } if ((err = mp_init(&mu)) != CRYPT_OK) { goto ERR_MP; } if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { goto ERR_MU; } /* copy ones ... */ if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK) { goto ERR_MU; } /* precomp [i,0](A + B) table */ if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; } if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], modulus, mp)) != CRYPT_OK) { goto ERR_MU; } /* precomp [0,i](A + B) table */ if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; } if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; } /* precomp [i,j](A + B) table (i != 0, j != 0) */ for (x = 1; x < 4; x++) { for (y = 1; y < 4; y++) { if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], modulus, mp)) != CRYPT_OK) { goto ERR_MU; } } } nibble = 3; first = 1; bitbufA = tA[0]; bitbufB = tB[0]; /* for every byte of the multiplicands */ for (x = -1;; ) { /* grab a nibble */ if (++nibble == 4) { ++x; if (x == len) break; bitbufA = tA[x]; bitbufB = tB[x]; nibble = 0; } /* extract two bits from both, shift/update */ nA = (bitbufA >> 6) & 0x03; nB = (bitbufB >> 6) & 0x03; bitbufA = (bitbufA << 2) & 0xFF; bitbufB = (bitbufB << 2) & 0xFF; /* if both zero, if first, continue */ if ((nA == 0) && (nB == 0) && (first == 1)) { continue; } /* double twice, only if this isn't the first */ if (first == 0) { /* double twice */ if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } } /* if not both zero */ if ((nA != 0) || (nB != 0)) { if (first == 1) { /* if first, copy from table */ first = 0; if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK) { goto ERR_MU; } if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK) { goto ERR_MU; } } else { /* if not first, add from table */ if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } } } } /* reduce to affine */ err = ltc_ecc_map(C, modulus, mp); /* clean up */ ERR_MU: mp_clear(mu); ERR_MP: mp_montgomery_free(mp); ERR_P: for (x = 0; x < 16; x++) { ltc_ecc_del_point(precomp[x]); } ERR_T: #ifdef LTC_CLEAN_STACK zeromem(tA, ECC_BUF_SIZE); zeromem(tB, ECC_BUF_SIZE); #endif XFREE(tA); XFREE(tB); return err; } #endif #endif /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.c,v $ */ /* $Revision: 1.6 $ */ /* $Date: 2006/12/04 05:07:59 $ */