--- /dev/null
+/* 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"
+
+/**
+ @file ltc_ecc_mul2add.c
+ 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
+*/
+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 = 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$ */
projects / zpackage / blobdiff