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@gmail.com, http://libtom.org
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 "../../headers/tomcrypt.h"
18
19 /**
20 @file ltc_ecc_mul2add.c
21 ECC Crypto, Shamir's Trick, Tom St Denis
22 */
23
24 #ifdef LTC_MECC
25
26 #ifdef LTC_ECC_SHAMIR
27
28 /** Computes kA*A + kB*B = C using Shamir's Trick
29 @param A First point to multiply
30 @param kA What to multiple A by
31 @param B Second point to multiply
32 @param kB What to multiple B by
33 @param C [out] Destination point (can overlap with A or B
34 @param modulus Modulus for curve
35 @return CRYPT_OK on success
36 */
ltc_ecc_mul2add(ecc_point * A,void * kA,ecc_point * B,void * kB,ecc_point * C,void * modulus)37 int ltc_ecc_mul2add(ecc_point *A, void *kA,
38 ecc_point *B, void *kB,
39 ecc_point *C,
40 void *modulus)
41 {
42 ecc_point *precomp[16];
43 unsigned bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
44 unsigned char *tA, *tB;
45 int err, first;
46 void *mp, *mu;
47
48 /* argchks */
49 LTC_ARGCHK(A != NULL);
50 LTC_ARGCHK(B != NULL);
51 LTC_ARGCHK(C != NULL);
52 LTC_ARGCHK(kA != NULL);
53 LTC_ARGCHK(kB != NULL);
54 LTC_ARGCHK(modulus != NULL);
55
56 /* allocate memory */
57 tA = XCALLOC(1, ECC_BUF_SIZE);
58 if (tA == NULL) {
59 return CRYPT_MEM;
60 }
61 tB = XCALLOC(1, ECC_BUF_SIZE);
62 if (tB == NULL) {
63 XFREE(tA);
64 return CRYPT_MEM;
65 }
66
67 /* get sizes */
68 lenA = mp_unsigned_bin_size(kA);
69 lenB = mp_unsigned_bin_size(kB);
70 len = MAX(lenA, lenB);
71
72 /* sanity check */
73 if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) {
74 err = CRYPT_INVALID_ARG;
75 goto ERR_T;
76 }
77
78 /* extract and justify kA */
79 mp_to_unsigned_bin(kA, (len - lenA) + tA);
80
81 /* extract and justify kB */
82 mp_to_unsigned_bin(kB, (len - lenB) + tB);
83
84 /* allocate the table */
85 for (x = 0; x < 16; x++) {
86 precomp[x] = ltc_ecc_new_point();
87 if (precomp[x] == NULL) {
88 for (y = 0; y < x; ++y) {
89 ltc_ecc_del_point(precomp[y]);
90 }
91 err = CRYPT_MEM;
92 goto ERR_T;
93 }
94 }
95
96 /* init montgomery reduction */
97 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
98 goto ERR_P;
99 }
100 if ((err = mp_init(&mu)) != CRYPT_OK) {
101 goto ERR_MP;
102 }
103 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
104 goto ERR_MU;
105 }
106
107 /* copy ones ... */
108 if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK) { goto ERR_MU; }
109 if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK) { goto ERR_MU; }
110 if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK) { goto ERR_MU; }
111
112 if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK) { goto ERR_MU; }
113 if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK) { goto ERR_MU; }
114 if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK) { goto ERR_MU; }
115
116 /* precomp [i,0](A + B) table */
117 if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
118 if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
119
120 /* precomp [0,i](A + B) table */
121 if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
122 if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
123
124 /* precomp [i,j](A + B) table (i != 0, j != 0) */
125 for (x = 1; x < 4; x++) {
126 for (y = 1; y < 4; y++) {
127 if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
128 }
129 }
130
131 nibble = 3;
132 first = 1;
133 bitbufA = tA[0];
134 bitbufB = tB[0];
135
136 /* for every byte of the multiplicands */
137 for (x = -1;; ) {
138 /* grab a nibble */
139 if (++nibble == 4) {
140 ++x; if (x == len) break;
141 bitbufA = tA[x];
142 bitbufB = tB[x];
143 nibble = 0;
144 }
145
146 /* extract two bits from both, shift/update */
147 nA = (bitbufA >> 6) & 0x03;
148 nB = (bitbufB >> 6) & 0x03;
149 bitbufA = (bitbufA << 2) & 0xFF;
150 bitbufB = (bitbufB << 2) & 0xFF;
151
152 /* if both zero, if first, continue */
153 if ((nA == 0) && (nB == 0) && (first == 1)) {
154 continue;
155 }
156
157 /* double twice, only if this isn't the first */
158 if (first == 0) {
159 /* double twice */
160 if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
161 if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
162 }
163
164 /* if not both zero */
165 if ((nA != 0) || (nB != 0)) {
166 if (first == 1) {
167 /* if first, copy from table */
168 first = 0;
169 if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK) { goto ERR_MU; }
170 if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK) { goto ERR_MU; }
171 if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK) { goto ERR_MU; }
172 } else {
173 /* if not first, add from table */
174 if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
175 }
176 }
177 }
178
179 /* reduce to affine */
180 err = ltc_ecc_map(C, modulus, mp);
181
182 /* clean up */
183 ERR_MU:
184 mp_clear(mu);
185 ERR_MP:
186 mp_montgomery_free(mp);
187 ERR_P:
188 for (x = 0; x < 16; x++) {
189 ltc_ecc_del_point(precomp[x]);
190 }
191 ERR_T:
192 #ifdef LTC_CLEAN_STACK
193 zeromem(tA, ECC_BUF_SIZE);
194 zeromem(tB, ECC_BUF_SIZE);
195 #endif
196 XFREE(tA);
197 XFREE(tB);
198
199 return err;
200 }
201
202 #endif
203 #endif
204
205 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.c,v $ */
206 /* $Revision: 1.8 $ */
207 /* $Date: 2007/05/12 14:32:35 $ */
208