author Matt Johnston Sun, 24 May 2020 13:15:24 +0800 6dba84798cd5
line wrap: on
line source
```/* 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.
*/

/* 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"

/**
ECC Crypto, Shamir's Trick, Tom St Denis
*/

#ifdef LTC_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
*/
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 = 0;; ) {
/* grab a nibble */
if (++nibble == 4) {
if (x == len) break;
bitbufA = tA[x];
bitbufB = tB[x];
nibble  = 0;
++x;
}

/* 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

/* ref:         \$Format:%D\$ */
/* git commit:  \$Format:%H\$ */
/* commit time: \$Format:%ai\$ */
```