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