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