• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * This file is part of the openHiTLS project.
3  *
4  * openHiTLS is licensed under the Mulan PSL v2.
5  * You can use this software according to the terms and conditions of the Mulan PSL v2.
6  * You may obtain a copy of Mulan PSL v2 at:
7  *
8  *     http://license.coscl.org.cn/MulanPSL2
9  *
10  * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
11  * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
12  * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
13  * See the Mulan PSL v2 for more details.
14  */
15 
16 #include "hitls_build.h"
17 
18 #if defined(HITLS_CRYPTO_ECC) && defined(HITLS_CRYPTO_CURVE_MONT)
19 
20 #include "securec.h"
21 #include "bsl_sal.h"
22 #include "bsl_err_internal.h"
23 #include "crypt_utils.h"
24 #include "crypt_errno.h"
25 #include "ecc_local.h"
26 
27 #ifdef HITLS_CRYPTO_CURVE_MONT_NIST
28 
29 // Jacobian coordinate double the point
ECP_NistPointDoubleMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a)30 int32_t ECP_NistPointDoubleMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a)
31 {
32     if (a == NULL || r == NULL || para == NULL) {
33         return CRYPT_NULL_INPUT;
34     }
35     BN_Optimizer *opt = BN_OptimizerCreate();
36     if (opt == NULL) {
37         return CRYPT_MEM_ALLOC_FAIL;
38     }
39     (void)OptimizerStart(opt);
40     int32_t ret;
41     BN_BigNum *halfP = ECP_HalfPGet(para->p);
42     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
43     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
44     BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
45     if (t1 == NULL || t2 == NULL || t3 == NULL || halfP == NULL) {
46         ret = CRYPT_MEM_ALLOC_FAIL;
47         goto ERR;
48     }
49     GOTO_ERR_IF(para->method->bnMontEnc(halfP, para->montP, opt, false), ret);
50 
51     GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->montP, opt), ret);
52 
53     GOTO_ERR_IF(BN_ModSubQuick(t2, a->x, t1, para->p, opt), ret);
54     GOTO_ERR_IF(BN_ModAddQuick(t1, a->x, t1, para->p, opt), ret);
55     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, t1, para->montP, opt), ret);
56     GOTO_ERR_IF(BN_ModAddQuick(t3, t2, t2, para->p, opt), ret);
57     GOTO_ERR_IF(BN_ModAddQuick(t2, t3, t2, para->p, opt), ret); // t2 = 3*t2
58     GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
59     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->y, a->z, para->montP, opt), ret);
60     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->montP, opt), ret);
61     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, r->y, a->x, para->montP, opt), ret);
62 
63     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->montP, opt), ret);
64     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->montP, opt), ret);
65     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->montP, opt), ret);
66     GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret);
67     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret);
68 
69     GOTO_ERR_IF(BN_ModSubQuick(t1, t3, r->x, para->p, opt), ret);
70     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t2, para->montP, opt), ret);
71     GOTO_ERR_IF(BN_ModSubQuick(r->y, t1, r->y, para->p, opt), ret);
72 ERR:
73     BN_OptimizerDestroy(opt);
74     BN_Destroy(halfP);
75     return ret;
76 }
77 
78 // Jacobian coordinate multi-double the point: r = (2^m) * pt
ECP_NistPointMultDoubleMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,uint32_t m)79 int32_t ECP_NistPointMultDoubleMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, uint32_t m)
80 {
81     if (a == NULL || r == NULL || para == NULL) {
82         return CRYPT_NULL_INPUT;
83     }
84     uint32_t tm = m;
85     BN_Optimizer *opt = BN_OptimizerCreate();
86     if (opt == NULL) {
87         return CRYPT_MEM_ALLOC_FAIL;
88     }
89     int32_t ret;
90     (void)OptimizerStart(opt);
91     BN_BigNum *ta = OptimizerGetBn(opt, a->x->room);
92     BN_BigNum *tb = OptimizerGetBn(opt, a->x->room);
93     BN_BigNum *tc = OptimizerGetBn(opt, a->x->room);
94     BN_BigNum *tw = OptimizerGetBn(opt, a->x->room);
95     BN_BigNum *halfP = ECP_HalfPGet(para->p);
96     if (ta == NULL || tb == NULL || tc == NULL || tw == NULL || halfP == NULL) {
97         ret = CRYPT_MEM_ALLOC_FAIL;
98         goto ERR;
99     }
100     GOTO_ERR_IF(BN_Copy(r->x, a->x), ret);
101     GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
102     GOTO_ERR_IF(BN_Copy(r->z, a->z), ret);
103 
104     GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, a->z, para->montP, opt), ret);
105     GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, tw, para->montP, opt), ret);
106     GOTO_ERR_IF(para->method->bnMontEnc(halfP, para->montP, opt, false), ret);
107 
108     while (tm > 0) {
109         // 3.1
110         // ta = 3*(x^2 - tw)
111         GOTO_ERR_IF(para->method->bnModNistEccSqr(ta, r->x, para->montP, opt), ret);
112         GOTO_ERR_IF(BN_ModSubQuick(tc, ta, tw, para->p, opt), ret);
113         GOTO_ERR_IF(BN_ModAddQuick(ta, tc, tc, para->p, opt), ret);
114         GOTO_ERR_IF(BN_ModAddQuick(ta, ta, tc, para->p, opt), ret);
115         // tb = x*(y^2)
116         GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, r->y, para->montP, opt), ret);
117         GOTO_ERR_IF(para->method->bnModNistEccMul(tb, tc, r->x, para->montP, opt), ret);
118 
119         // 3.2
120         // x = ta^2 - 2*tb
121         GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, ta, para->montP, opt), ret);
122         GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, tb, para->p, opt), ret);
123         GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, tb, para->p, opt), ret);
124         // z = zy
125         GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->z, r->y, para->montP, opt), ret);
126 
127         // 3.3
128         // tc = y^4
129         GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, r->y, para->montP, opt), ret);
130         GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, tc, para->montP, opt), ret);
131         // m = m - 1, if bit > 0, tw = tw * (y^4)
132         tm--;
133         if (tm > 0) {
134             GOTO_ERR_IF(para->method->bnModNistEccMul(tw, tw, tc, para->montP, opt), ret);
135         }
136         // 3.4
137         // y = 2*ta*(tb - x) - (y^4)
138         GOTO_ERR_IF(BN_ModSubQuick(r->y, tb, r->x, para->p, opt), ret);
139         GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, ta, para->montP, opt), ret);
140         GOTO_ERR_IF(BN_ModAddQuick(r->y, r->y, r->y, para->p, opt), ret);
141         GOTO_ERR_IF(BN_ModSubQuick(r->y, r->y, tc, para->p, opt), ret);
142     }
143     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->montP, opt), ret);
144 ERR:
145     BN_Destroy(halfP);
146     BN_OptimizerDestroy(opt); // no need to end opt.
147     return ret;
148 }
149 
150 // Point addition calculation (Jacobian point a plus Jacobian point b)
151 // https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo
ECP_NistPointAddMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)152 int32_t ECP_NistPointAddMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, const ECC_Point *b)
153 {
154     if (para == NULL || r == NULL || a == NULL || b == NULL) {
155         return CRYPT_NULL_INPUT;
156     }
157     if (BN_IsZero(a->z)) {
158         // If point a is an infinity point, r = b
159         return ECC_CopyPoint(r, b);
160     }
161     if (BN_IsZero(b->z)) {
162         // If point b is an infinity point, r = a
163         return ECC_CopyPoint(r, a);
164     }
165     BN_Optimizer *opt = BN_OptimizerCreate();
166     if (opt == NULL) {
167         return CRYPT_MEM_ALLOC_FAIL;
168     }
169     (void)OptimizerStart(opt);
170     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
171     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
172     BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
173     BN_BigNum *t4 = OptimizerGetBn(opt, a->x->room);
174     BN_BigNum *t5 = OptimizerGetBn(opt, a->x->room);
175     BN_BigNum *t6 = OptimizerGetBn(opt, a->x->room);
176     if (t1 == NULL || t2 == NULL || t3 == NULL || t4 == NULL || t5 == NULL || t6 == NULL) {
177         BN_OptimizerDestroy(opt); // no need to end opt.
178         return CRYPT_MEM_ALLOC_FAIL;
179     }
180 
181     int32_t ret;
182     GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, b->z, para->montP, opt), ret); // Z2^2
183     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t1, b->z, para->montP, opt), ret); // Z2^3
184     GOTO_ERR_IF(para->method->bnModNistEccMul(t5, t1, a->x, para->montP, opt), ret); // U1 = X1*Z2^2
185     GOTO_ERR_IF(para->method->bnModNistEccMul(t6, t2, a->y, para->montP, opt), ret); // S1 = Y1*Z2^3
186     GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, a->z, para->montP, opt), ret); // T3 = Z1^2
187 
188     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, a->z, b->y, para->montP, opt), ret); // r->y = Y2*Z1
189     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, a->z, b->z, para->montP, opt), ret); // r->z = Z2*Z1
190     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, t3, r->y, para->montP, opt), ret); // S2 = Y2 * Z1^3
191     GOTO_ERR_IF(para->method->bnModNistEccMul(r->x, t3, b->x, para->montP, opt), ret); // U2 = Z1^2 * X2
192 
193     GOTO_ERR_IF(BN_ModSubQuick(t1, r->x, t5, para->p, opt), ret); // H = U2 - U1
194     GOTO_ERR_IF(BN_ModSubQuick(t2, r->y, t6, para->p, opt), ret); // r = S2 - S1
195     if (BN_IsZero(t1) && BN_IsZero(t2)) {
196         GOTO_ERR_IF(para->method->pointDouble(para, r, b), ret);
197         goto ERR;
198     }
199     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, t1, r->z, para->montP, opt), ret); // r->z = H * Z2*Z1
200     GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, t1, para->montP, opt), ret); // t3 = H^2
201 
202     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t3, para->montP, opt), ret); // t1 = H^3
203     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, t5, para->montP, opt), ret); // t3 = H^2 * U1
204     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->montP, opt), ret); // r->x = r ^ 2
205 
206     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t3, para->p, opt), ret); // r ^ 2 - H^2*U1
207     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t3, para->p, opt), ret); // r ^ 2 - 2*H^2 * U1
208     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret); // r ^ 2 - 2*H^2*U1 - H^3
209     GOTO_ERR_IF(BN_ModSubQuick(t3, t3, r->x, para->p, opt), ret); // H^2 * U1 - X3
210     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t2, t3, para->montP, opt), ret); // r * (H^2 * U1 - X3)
211     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t6, para->montP, opt), ret); // t1 = H^3 * S1
212     GOTO_ERR_IF(BN_ModSubQuick(r->y, t3, t1, para->p, opt), ret); // r * (H^2 * U1 - X3) - H^3 * S1
213 ERR:
214     BN_OptimizerDestroy(opt); // no need to end opt.
215     return ret;
216 }
217 
218 // cal r = a + b (b->z = 1)
219 // https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-madd-2004-hmv
ECP_NistPointAddAffineMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)220 int32_t ECP_NistPointAddAffineMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, const ECC_Point *b)
221 {
222     int32_t ret;
223     if (a == NULL || b == NULL || r == NULL || para == NULL) {
224         return CRYPT_NULL_INPUT;
225     }
226     if (BN_IsZero(a->z)) { // if point a is an infinity point, r = b,
227         return ECC_CopyPoint(r, b);
228     }
229     BN_Optimizer *opt = BN_OptimizerCreate();
230     if (opt == NULL) {
231         return CRYPT_MEM_ALLOC_FAIL;
232     }
233     (void)OptimizerStart(opt);
234     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
235     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
236     BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
237     BN_BigNum *t4 = OptimizerGetBn(opt, a->x->room);
238     if (t1 == NULL || t2 == NULL || t3 == NULL || t4 == NULL) {
239         ret = CRYPT_MEM_ALLOC_FAIL;
240         goto ERR;
241     }
242 
243     GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->montP, opt), ret); // T1 = Z1^2
244     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t1, a->z, para->montP, opt), ret); // T2 = Z1^3
245     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, b->x, para->montP, opt), ret); // T1 = X2*T1
246     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, b->y, para->montP, opt), ret); // T2 = Y2*T2
247     GOTO_ERR_IF(BN_ModSubQuick(t1, t1, a->x, para->p, opt), ret); // T1 = T1-X1
248     GOTO_ERR_IF(BN_ModSubQuick(t2, t2, a->y, para->p, opt), ret); // T2 = T2-Y1
249 
250     if (BN_IsZero(t1)) {
251         if (BN_IsZero(t2)) {
252             // If two points are equal, use double for calculation.
253             GOTO_ERR_IF(para->method->pointDouble(para, r, b), ret);
254         } else {
255             // Obtain the infinite point.
256             GOTO_ERR_IF(BN_SetLimb(r->z, 0), ret);
257         }
258         goto ERR;
259     }
260     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, a->z, t1, para->montP, opt), ret); // Z3 = Z1 * T1
261 
262     GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, t1, para->montP, opt), ret); // T3 = T1 ^ 2
263     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t1, t3, para->montP, opt), ret); // T4 = T3 * T1
264     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, a->x, para->montP, opt), ret); // T3 = T3 * X1
265     GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret); // T1 = 2 * T3
266     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->montP, opt), ret); // X3 = T2 ^ 2
267     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret); // X3 = X3 - T1
268     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t4, para->p, opt), ret); // X3 = X3 - T4
269     GOTO_ERR_IF(BN_ModSubQuick(t3, t3, r->x, para->p, opt), ret); // T3 = T3 - X3
270     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, t2, para->montP, opt), ret); // T3 = T3 * T2
271     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t4, a->y, para->montP, opt), ret); // T4 = T4 * Y1
272     GOTO_ERR_IF(BN_ModSubQuick(r->y, t3, t4, para->p, opt), ret); // Y3 = T3 - T4
273 ERR:
274     BN_OptimizerDestroy(opt); // no need to end opt.
275     return ret;
276 }
277 #endif
278 
279 #ifdef HITLS_CRYPTO_CURVE_MONT_PRIME
280 /*
281  prime curves point multi-double r = (2^m)*a
282  Calculation procedure:
283     1. If the point is an infinity point, return the infinity point.
284     2. Y = 2*Y, W = Z^4
285     3. If m > 0, repeat the following steps:
286             A = 3*X^2 + a*W
287             B = X*Y^2
288             X = A^2 - 2*B
289             Z = Z*Y
290             m = m - 1
291             if m > 0 then W = W*Y^4
292             Y = 2*A*(B-X)-Y^4
293     4. Return (X, Y/2, Z)
294 */
ECP_PrimePointDoubleMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a)295 int32_t ECP_PrimePointDoubleMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a)
296 {
297     if (para == NULL || r == NULL || a == NULL) {
298         return CRYPT_NULL_INPUT;
299     }
300     BN_Optimizer *opt = BN_OptimizerCreate();
301     if (opt == NULL) {
302         return CRYPT_MEM_ALLOC_FAIL;
303     }
304     int32_t ret;
305     (void)OptimizerStart(opt);
306     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
307     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
308     BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
309     BN_BigNum *halfP = ECP_HalfPGet(para->p);
310     if (t1 == NULL || t2 == NULL || t3 == NULL || halfP == NULL) {
311         ret = CRYPT_MEM_ALLOC_FAIL;
312         goto ERR;
313     }
314     GOTO_ERR_IF(para->method->bnMontEnc(halfP, para->montP, opt, false), ret);
315     GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->montP, opt), ret); // Z1^2
316     GOTO_ERR_IF(para->method->bnModNistEccSqr(t2, t1, para->montP, opt), ret); // Z1^4
317     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t2, para->a, para->montP, opt), ret); // a*Z1^4
318     GOTO_ERR_IF(para->method->bnModNistEccSqr(t2, a->x, para->montP, opt), ret); // X1^2
319     GOTO_ERR_IF(BN_ModAddQuick(t3, t2, t2, para->p, opt), ret); // 2*X1^2
320     GOTO_ERR_IF(BN_ModAddQuick(t2, t3, t2, para->p, opt), ret); // 3*X1^2
321     GOTO_ERR_IF(BN_ModAddQuick(t2, t1, t2, para->p, opt), ret); // t2 = 3*X1^2 + a*Z1^4
322     GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
323     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->y, a->z, para->montP, opt), ret);
324     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->montP, opt), ret);
325     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, r->y, a->x, para->montP, opt), ret);
326 
327     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->montP, opt), ret);
328     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->montP, opt), ret);
329     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->montP, opt), ret);
330     GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret);
331     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret);
332 
333     GOTO_ERR_IF(BN_ModSubQuick(t1, t3, r->x, para->p, opt), ret);
334     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t2, para->montP, opt), ret);
335     GOTO_ERR_IF(BN_ModSubQuick(r->y, t1, r->y, para->p, opt), ret);
336 ERR:
337     BN_Destroy(halfP);
338     BN_OptimizerDestroy(opt); // no need to end opt.
339     return ret;
340 }
341 
342 // Point addition calculation (Jacobian point a plus Jacobian point b)
343 // https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
ECP_PrimePointAddMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)344 int32_t ECP_PrimePointAddMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a,
345     const ECC_Point *b)
346 {
347     bool flag = (para == NULL) || (r == NULL) || (a == NULL) || (b == NULL);
348     if (flag) {
349         return CRYPT_NULL_INPUT;
350     }
351     if (BN_IsZero(a->z)) {
352         return ECC_CopyPoint(r, b);
353     }
354     if (BN_IsZero(b->z)) {
355         return ECC_CopyPoint(r, a);
356     }
357     BN_Optimizer *opt = BN_OptimizerCreate();
358     if (opt == NULL) {
359         return CRYPT_MEM_ALLOC_FAIL;
360     }
361     (void)OptimizerStart(opt);
362     BN_BigNum *t0 = OptimizerGetBn(opt, para->p->size);
363     BN_BigNum *t1 = OptimizerGetBn(opt, para->p->size);
364     BN_BigNum *t2 = OptimizerGetBn(opt, para->p->size);
365     BN_BigNum *t3 = OptimizerGetBn(opt, para->p->size);
366     BN_BigNum *t4 = OptimizerGetBn(opt, para->p->size);
367     BN_BigNum *t5 = OptimizerGetBn(opt, para->p->size);
368     flag = (t0 == NULL) || (t1 == NULL) || (t2 == NULL) || (t3 == NULL) || (t4 == NULL) || (t5 == NULL);
369     if (flag) {
370         BN_OptimizerDestroy(opt); // no need to end opt.
371         return CRYPT_MEM_ALLOC_FAIL;
372     }
373 
374     int32_t ret;
375     GOTO_ERR_IF(para->method->bnModNistEccSqr(t0, a->z, para->montP, opt), ret); // z1z1 = z1^2
376     GOTO_ERR_IF(para->method->bnModNistEccSqr(t5, b->z, para->montP, opt), ret); // z2z2 = z2^2
377     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, a->x, t5, para->montP, opt), ret); // u1 = x1*z2z2
378     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, b->x, t0, para->montP, opt), ret); // u2 = x2*z1z1
379 
380     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, b->z, t5, para->montP, opt), ret); // z2 * z2z2
381     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, a->y, t2, para->montP, opt), ret); // s1 = y1 * z2 * z2z2
382 
383     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, a->z, t0, para->montP, opt), ret); // z1 * z1z1
384     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, b->y, t4, para->montP, opt), ret); // s2 = y2 * z1 * z1z1
385 
386     GOTO_ERR_IF(BN_ModAddQuick(t0, t0, t5, para->p, opt), ret); // z1z1 + z2z2
387     GOTO_ERR_IF(BN_ModSubQuick(t3, t3, t1, para->p, opt), ret); // h = u2 - u1
388     GOTO_ERR_IF(BN_ModSubQuick(t4, t4, t2, para->p, opt), ret); // s2 - s1
389     if (BN_IsZero(t3) && BN_IsZero(t4)) {
390         GOTO_ERR_IF(para->method->pointDouble(para, r, b), ret);
391         goto ERR;
392     }
393     GOTO_ERR_IF(BN_ModAddQuick(t5, t3, t3, para->p, opt), ret); // 2h
394     GOTO_ERR_IF(BN_ModAddQuick(r->y, t4, t4, para->p, opt), ret); // r = 2(s2 - s1)
395     GOTO_ERR_IF(para->method->bnModNistEccSqr(t5, t5, para->montP, opt), ret); // i = (2h)^2
396     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t3, t5, para->montP, opt), ret); // j = h*i
397 
398     GOTO_ERR_IF(para->method->bnModNistEccMul(t5, t1, t5, para->montP, opt), ret); // v = u1 * i
399     GOTO_ERR_IF(BN_ModAddQuick(t1, t5, t5, para->p, opt), ret); // 2 * v
400     GOTO_ERR_IF(BN_ModAddQuick(t1, t1, t4, para->p, opt), ret); // 2 * v + j
401     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, r->y, para->montP, opt), ret); // rr ^ 2
402     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret); // r->x = rr ^ 2 - j - z * v
403 
404     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, t4, para->montP, opt), ret); // s1 * j
405     GOTO_ERR_IF(BN_ModAddQuick(t2, t2, t2, para->p, opt), ret); // 2 * s1 * j
406     GOTO_ERR_IF(BN_ModSubQuick(t5, t5, r->x, para->p, opt), ret); // v = v - x3
407     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, t5, para->montP, opt), ret); // r * (v - x3)
408     GOTO_ERR_IF(BN_ModSubQuick(r->y, r->y, t2, para->p, opt), ret); // r * (v - x3) - 2 * s1 * j
409 
410     GOTO_ERR_IF(BN_ModAddQuick(r->z, a->z, b->z, para->p, opt), ret); // z1 + z2
411     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->z, r->z, para->montP, opt), ret); // (z1 + z2) ^ 2
412     GOTO_ERR_IF(BN_ModSubQuick(r->z, r->z, t0, para->p, opt), ret); // (z1 + z2) ^ 2 - z1z1 - z2z2
413     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->z, t3, para->montP, opt), ret); // r->z * h
414 
415 ERR:
416     BN_OptimizerDestroy(opt); // no need to end opt.
417     return ret;
418 }
419 
420 // Jacobian coordinate multi-double the point: r = (2^m) * pt
ECP_PrimePointMultDoubleMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,uint32_t m)421 int32_t ECP_PrimePointMultDoubleMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, uint32_t m)
422 {
423     if (para == NULL || r == NULL || a == NULL) {
424         return CRYPT_NULL_INPUT;
425     }
426     uint32_t tm = m;
427     int32_t ret;
428     BN_Optimizer *opt = BN_OptimizerCreate();
429     if (opt == NULL) {
430         return CRYPT_MEM_ALLOC_FAIL;
431     }
432     (void)OptimizerStart(opt);
433     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
434     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
435     BN_BigNum *ta = OptimizerGetBn(opt, a->x->room);
436     BN_BigNum *tb = OptimizerGetBn(opt, a->x->room);
437     BN_BigNum *tw = OptimizerGetBn(opt, a->x->room);
438     BN_BigNum *halfP = ECP_HalfPGet(para->p);
439     if (t1 == NULL || t2 == NULL || ta == NULL || tb == NULL || tw == NULL || halfP == NULL) {
440         ret = CRYPT_MEM_ALLOC_FAIL;
441         goto ERR;
442     }
443 
444     GOTO_ERR_IF(BN_Copy(r->x, a->x), ret);
445     GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
446     GOTO_ERR_IF(BN_Copy(r->z, a->z), ret);
447     GOTO_ERR_IF(para->method->bnMontEnc(halfP, para->montP, opt, false), ret);
448 
449     GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, a->z, para->montP, opt), ret);
450     GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, tw, para->montP, opt), ret); // Z^4
451 
452     while (tm > 0) {
453         // A = 3*X^2 + a*W
454         GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, r->x, para->montP, opt), ret); // X^2
455         GOTO_ERR_IF(BN_ModAddQuick(ta, t1, t1, para->p, opt), ret);
456         GOTO_ERR_IF(BN_ModAddQuick(ta, ta, t1, para->p, opt), ret); // 3*X^2
457         GOTO_ERR_IF(para->method->bnModNistEccMul(t2, para->a, tw, para->montP, opt), ret); // a*W
458         GOTO_ERR_IF(BN_ModAddQuick(ta, ta, t2, para->p, opt), ret); // A = 3*X^2 + a*W
459 
460         GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, r->y, para->montP, opt), ret); // t1 = Y^2
461         GOTO_ERR_IF(para->method->bnModNistEccMul(tb, t1, r->x, para->montP, opt), ret); // B = X*Y^2
462 
463         GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, t1, para->montP, opt), ret); // t1 = Y^4
464 
465         GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, ta, para->montP, opt), ret); // A^2
466         GOTO_ERR_IF(BN_ModAddQuick(t2, tb, tb, para->p, opt), ret); // 2*B
467         GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t2, para->p, opt), ret); // X = A^2 - 2*B
468 
469         GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->z, r->y, para->montP, opt), ret);
470 
471         // m = m - 1
472         tm--;
473         if (tm > 0) {
474             GOTO_ERR_IF(para->method->bnModNistEccMul(tw, tw, t1, para->montP, opt), ret);
475         }
476         GOTO_ERR_IF(BN_ModSubQuick(r->y, tb, r->x, para->p, opt), ret);
477         GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, ta, para->montP, opt), ret);
478         GOTO_ERR_IF(BN_ModAddQuick(r->y, r->y, r->y, para->p, opt), ret);
479         GOTO_ERR_IF(BN_ModSubQuick(r->y, r->y, t1, para->p, opt), ret);
480     }
481     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->montP, opt), ret);
482 ERR:
483     BN_Destroy(halfP);
484     BN_OptimizerDestroy(opt);
485     return ret;
486 }
487 
488 /*
489  prime curve point addition r = a + b, , depending on the method->pointDouble point operation.
490  Calculation formula:
491     X3 = (Y2*Z1^3-Y1)^2 - (X2*Z1^2-X1)^2 * (X1+X2*Z1^2)
492     Y3 = (Y2*Z1^3-Y1) * (X1*(X2*Z1^2-X1)^2-X3) - Y1 * (X2*Z1^2-X1)^3
493     Z3 = (X2*Z1^2-X1) * Z1
494 */
ECP_PrimePointAddAffineMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)495 int32_t ECP_PrimePointAddAffineMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, const ECC_Point *b)
496 {
497     if (para == NULL || r == NULL || a == NULL || b == NULL) {
498         return CRYPT_NULL_INPUT;
499     }
500     if (BN_IsZero(a->z)) { // if point a is an infinity point, r = b,
501         return ECC_CopyPoint(r, b);
502     }
503     BN_Optimizer *opt = BN_OptimizerCreate();
504     if (opt == NULL) {
505         return CRYPT_MEM_ALLOC_FAIL;
506     }
507     (void)OptimizerStart(opt);
508     BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
509     BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
510     BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
511     BN_BigNum *t4 = OptimizerGetBn(opt, a->x->room);
512     if (t1 == NULL || t2 == NULL || t3 == NULL || t4 == NULL) {
513         BN_OptimizerDestroy(opt);
514         return CRYPT_MEM_ALLOC_FAIL;
515     }
516     int32_t ret;
517     GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->montP, opt), ret); // Z1^2
518     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t1, a->z, para->montP, opt), ret); // Z1^3
519     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, b->x, para->montP, opt), ret); // X2*Z1^2
520     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, b->y, para->montP, opt), ret); // Y2*Z1^3
521     GOTO_ERR_IF(BN_ModSubQuick(t1, t1, a->x, para->p, opt), ret); // X2*Z1^2 - X1
522     GOTO_ERR_IF(BN_ModSubQuick(t2, t2, a->y, para->p, opt), ret); // Y2*Z1^3 - Y1
523 
524     if (BN_IsZero(t1)) {
525         if (BN_IsZero(t2)) {
526             // If two points are equal, use double for calculation.
527             GOTO_ERR_IF(para->method->pointDouble(para, r, b), ret);
528         } else {
529             // Obtain the infinite point.
530             GOTO_ERR_IF(BN_SetLimb(r->z, 0), ret);
531         }
532         goto ERR;
533     }
534     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, a->z, t1, para->montP, opt), ret); // Z3 = (X2*Z1^2 - X1)*Z1
535 
536     GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, t1, para->montP, opt), ret); // (X2*Z1^2 - X1)^2
537     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t1, t3, para->montP, opt), ret); // (X2*Z1^2 - X1)^3
538     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, a->x, para->montP, opt), ret); // X1*(X2*Z1^2 - X1)^2
539     GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret); // 2*X1*(X2*Z1^2 - X1)^2
540     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->montP, opt), ret); // (Y2*Z1^3 - Y1)^2
541     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret); // (Y2*Z1^3-Y1)^2 - 2*X1*(X2*Z1^2-X1)^2
542     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t4, para->p, opt), ret); // X3
543     GOTO_ERR_IF(BN_ModSubQuick(t3, t3, r->x, para->p, opt), ret); // X1*(X2*Z1^2-X1)^2 - X3
544     // (Y2*Z1^3-Y1)*(X1*(X2*Z1^2-X1)^2-X3)
545     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, t2, para->montP, opt), ret);
546     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t4, a->y, para->montP, opt), ret); // Y1*(X2*Z1^2 - X1)^3
547     GOTO_ERR_IF(BN_ModSubQuick(r->y, t3, t4, para->p, opt), ret); // Y3
548 ERR:
549     BN_OptimizerDestroy(opt);
550     return ret;
551 }
552 #endif
553 
ECP_Point2AffineMont(const ECC_Para * para,ECC_Point * r,const ECC_Point * pt)554 int32_t ECP_Point2AffineMont(const ECC_Para *para, ECC_Point *r, const ECC_Point *pt)
555 {
556     if (pt == NULL || r == NULL || para == NULL) {
557         BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
558         return CRYPT_NULL_INPUT;
559     }
560     if (para->id != r->id || para->id != pt->id) {
561         BSL_ERR_PUSH_ERROR(CRYPT_ECC_POINT_ERR_CURVE_ID);
562         return CRYPT_ECC_POINT_ERR_CURVE_ID;
563     }
564     if (BN_IsZero(pt->z)) {
565         BSL_ERR_PUSH_ERROR(CRYPT_ECC_POINT_AT_INFINITY);
566         return CRYPT_ECC_POINT_AT_INFINITY;
567     }
568     if (BN_IsOne(pt->z)) {
569         return ECC_CopyPoint(r, pt);
570     }
571     uint32_t bits = BN_Bits(para->p);
572     BN_BigNum *inv = BN_Create(bits);
573     BN_BigNum *zz = BN_Create(bits);
574     BN_Optimizer *opt = BN_OptimizerCreate();
575     ECC_Point *base = ECC_DupPoint(pt);
576     int32_t ret;
577     if (inv == NULL || zz == NULL || opt == NULL || base == NULL) {
578         ret = CRYPT_MEM_ALLOC_FAIL;
579         BSL_ERR_PUSH_ERROR(ret);
580         goto ERR;
581     }
582     GOTO_ERR_IF(para->method->modInv(inv, base->z, para->p, opt), ret);
583     GOTO_ERR_IF(para->method->bnMontEnc(base->x, para->montP, opt, false), ret);
584     GOTO_ERR_IF(para->method->bnMontEnc(base->y, para->montP, opt, false), ret);
585     GOTO_ERR_IF(para->method->bnMontEnc(inv, para->montP, opt, false), ret);
586     GOTO_ERR_IF(para->method->bnModNistEccSqr(zz, inv, para->montP, opt), ret);
587     GOTO_ERR_IF(para->method->bnModNistEccMul(r->x, base->x, zz, para->montP, opt), ret);
588     GOTO_ERR_IF(para->method->bnModNistEccMul(zz, zz, inv, para->montP, opt), ret);
589     GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, base->y, zz, para->montP, opt), ret);
590     GOTO_ERR_IF(BN_SetLimb(r->z, 1), ret);
591     para->method->bnMontDec(r->x, para->montP);
592     para->method->bnMontDec(r->y, para->montP);
593 ERR:
594     BN_Destroy(zz);
595     BN_Destroy(inv);
596     ECC_FreePoint(base);
597     BN_OptimizerDestroy(opt);
598     return ret;
599 }
600 
601 /*
602  * XZ coordinates for short Weierstrass curves
603  * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-mladd-2002-bj-3
604  * MontLadderDoubleAndAdd return:
605  *    r2 = 2 * r2
606  *    r3 = r2 + r3
607 */
MontLadderDoubleAndAdd(ECC_Para * para,ECC_Point * r2,ECC_Point * r3,ECC_Point * p,BN_Optimizer * opt)608 static int32_t MontLadderDoubleAndAdd(ECC_Para *para,  ECC_Point *r2, ECC_Point *r3, ECC_Point *p, BN_Optimizer *opt)
609 {
610     int32_t ret;
611     (void)OptimizerStart(opt);
612     BN_BigNum *t0 = OptimizerGetBn(opt, p->x->room);
613     BN_BigNum *t1 = OptimizerGetBn(opt, p->x->room);
614     BN_BigNum *t2 = OptimizerGetBn(opt, p->x->room);
615     BN_BigNum *t3 = OptimizerGetBn(opt, p->x->room);
616     BN_BigNum *t4 = OptimizerGetBn(opt, p->x->room);
617     BN_BigNum *t5 = OptimizerGetBn(opt, p->x->room);
618     if (t0 == NULL || t1 == NULL || t2 == NULL || t3 == NULL || t4 == NULL || t5 == NULL) {
619         OptimizerEnd(opt);
620         return CRYPT_MEM_ALLOC_FAIL; // 不需要释放其他大数，统一交给大数优化器管理
621     }
622     GOTO_ERR_IF(para->method->bnModNistEccSqr(r2->y, r2->x, para->montP, opt), ret); // x2 ^ 2
623     GOTO_ERR_IF(para->method->bnModNistEccSqr(r3->y, r2->z, para->montP, opt), ret); // z2 ^ 2
624     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, r2->x, r2->z, para->montP, opt), ret); // X2 * Z2
625     GOTO_ERR_IF(BN_ModAddQuick(t0, t0, t0, para->p, opt), ret); // 2 * X2 * Z2
626     GOTO_ERR_IF(BN_ModAddQuick(t0, t0, t0, para->p, opt), ret); // 4 * X2 * Z2
627     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, para->a, r3->y, para->montP, opt), ret); // aZZ = a * ZZ
628 
629     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, r2->x, r3->x, para->montP, opt), ret); // X2 * X3
630     GOTO_ERR_IF(para->method->bnModNistEccMul(t3, r2->z, r3->z, para->montP, opt), ret); // Z2 * Z3
631     GOTO_ERR_IF(para->method->bnModNistEccMul(t4, r2->x, r3->z, para->montP, opt), ret); // X2 * Z3
632     GOTO_ERR_IF(para->method->bnModNistEccMul(t5, r2->z, r3->x, para->montP, opt), ret); // Z2 * X3
633 
634     GOTO_ERR_IF(BN_ModSubQuick(r2->x, r2->y, t1, para->p, opt), ret); // XX - aZZ
635     GOTO_ERR_IF(BN_ModAddQuick(r2->z, r2->y, t1, para->p, opt), ret); // XX + aZZ
636     GOTO_ERR_IF(para->method->bnModNistEccMul(r2->z, t0, r2->z, para->montP, opt), ret); // E * (XX + aZZ)
637 
638     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, t0, r3->y, para->montP, opt), ret); // E * ZZ
639     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, t0, para->b, para->montP, opt), ret); // b *  E * ZZ
640     GOTO_ERR_IF(BN_ModAddQuick(t0, t0, t0, para->p, opt), ret); // 2b *  E * ZZ
641 
642     GOTO_ERR_IF(para->method->bnModNistEccSqr(r2->x, r2->x, para->montP, opt), ret); // (XX - aZZ) ^ 2
643     GOTO_ERR_IF(BN_ModSubQuick(r2->x, r2->x, t0, para->p, opt), ret); // (XX - aZZ) ^ 2 - 2b *  E * ZZ
644 
645     GOTO_ERR_IF(para->method->bnModNistEccSqr(r3->y, r3->y, para->montP, opt), ret); // ZZ ^ 2
646     GOTO_ERR_IF(para->method->bnModNistEccMul(r3->y, r3->y, para->b, para->montP, opt), ret); // b * ZZ^2
647     GOTO_ERR_IF(BN_ModAddQuick(r3->y, r3->y, r3->y, para->p, opt), ret); // 2 * b * ZZ^2
648     GOTO_ERR_IF(BN_ModAddQuick(r3->y, r3->y, r3->y, para->p, opt), ret); // 4 * b * ZZ^2
649     GOTO_ERR_IF(BN_ModAddQuick(r2->z, r2->z, r3->y, para->p, opt), ret); // E * (XX + aZZ) + 4 * b * ZZ^2
650 
651     GOTO_ERR_IF(para->method->bnModNistEccMul(r3->x, para->a, t3, para->montP, opt), ret); // a * B
652     GOTO_ERR_IF(BN_ModSubQuick(r3->x, t2, r3->x, para->p, opt), ret); // A - a * B
653     GOTO_ERR_IF(para->method->bnModNistEccSqr(r3->x, r3->x, para->montP, opt), ret); // (A - a * B) ^ 2
654     GOTO_ERR_IF(BN_ModAddQuick(t2, t4, t5, para->p, opt), ret); // C + D
655     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, t3, para->montP, opt), ret); // B * (C + D)
656     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, para->b, para->montP, opt), ret); // b * B * (C + D)
657     GOTO_ERR_IF(BN_ModAddQuick(t2, t2, t2, para->p, opt), ret); // 2 * b * B * (C + D)
658     GOTO_ERR_IF(BN_ModAddQuick(t2, t2, t2, para->p, opt), ret); // 4 * b * B * (C + D)
659     GOTO_ERR_IF(BN_ModSubQuick(r3->x, r3->x, t2, para->p, opt), ret); // (A - a * B) ^ 2 - 4 * b * B * (C + D)
660 
661     GOTO_ERR_IF(BN_ModSubQuick(t4, t4, t5, para->p, opt), ret); // C - D
662     GOTO_ERR_IF(para->method->bnModNistEccSqr(t4, t4, para->montP, opt), ret); // (C - D) ^ 2
663     GOTO_ERR_IF(para->method->bnModNistEccMul(r3->z, p->x, t4, para->montP, opt), ret); // px * (C + D) ^ 2
664 
665  ERR:
666     OptimizerEnd(opt);
667     return ret;
668 }
669 
670 /*
671  * ref <Weierstraß Elliptic Curves and side-Channel Attacks> formula 8.
672  * XZ coordinates [database entry] represent x y as X Z satisfying the following equations:
673  * x = X / Z
674  * MontLadderRecoverYAndToMont return:
675  *    r1->x = r1->x / r1->z
676  *    r1->y = (2b + (a + x*x1)*(x + x1) - x2(x - x1)^2) / (2*y)
677  *          = (2b*z2*(z1^2) + z2(a*z1 + x*x1)(x*z1 + x1) - x2(x*z1 - x1) ^ 2) / (2y*z2*(z1^2))
678  */
MontLadderRecoverYAndToMont(ECC_Para * para,ECC_Point * r1,ECC_Point * r2,ECC_Point * p,BN_Optimizer * opt)679 static int32_t MontLadderRecoverYAndToMont(ECC_Para *para, ECC_Point *r1, ECC_Point *r2, ECC_Point *p,
680     BN_Optimizer *opt)
681 {
682     int32_t ret;
683     if (BN_IsZero(r1->z)) {
684         para->method->bnMontDec(r1->x, para->montP);
685         para->method->bnMontDec(r1->y, para->montP);
686         return CRYPT_SUCCESS;
687     }
688     if (BN_IsZero(r2->z)) {
689         GOTO_ERR_IF(ECC_CopyPoint(r1, p), ret); // r2 = r1 + p = 0 -> r1 = -p
690         GOTO_ERR_IF(BN_Sub(r1->y, para->p, r1->y), ret);
691         para->method->bnMontDec(r1->x, para->montP);
692         para->method->bnMontDec(r1->y, para->montP);
693         GOTO_ERR_IF(BN_SetLimb(r1->z, 1), ret);
694         return CRYPT_SUCCESS;
695     }
696     (void)OptimizerStart(opt);
697     BN_BigNum *t0 = OptimizerGetBn(opt, p->x->room);
698     BN_BigNum *t1 = OptimizerGetBn(opt, p->x->room);
699     BN_BigNum *t2 = OptimizerGetBn(opt, p->x->room);
700     BN_BigNum *t3 = OptimizerGetBn(opt, p->x->room);
701     if (t0 == NULL || t1 == NULL || t2 == NULL || t3 == NULL) {
702         OptimizerEnd(opt);
703         return CRYPT_MEM_ALLOC_FAIL;  // Other bn do not need to be released. They are managed by the opt.
704     }
705     GOTO_ERR_IF(para->method->bnModNistEccSqr(t0, r1->z, para->montP, opt), ret); // t0 = z1 ^ 2
706     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, t0, r2->z, para->montP, opt), ret); // t0 = z2 * z1^2
707 
708     GOTO_ERR_IF(BN_ModAddQuick(t1, para->b, para->b, para->p, opt), ret); // 2b
709     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t0, t1, para->montP, opt), ret); // t1 = 2b*z2*z1^2
710 
711     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, para->a, r1->z, para->montP, opt), ret); // t2 = a*z1
712     GOTO_ERR_IF(para->method->bnModNistEccMul(r2->y, p->x, r1->x, para->montP, opt), ret); // r2->y = x*x1
713     GOTO_ERR_IF(para->method->bnModNistEccMul(r1->y, p->x, r1->z, para->montP, opt), ret); // t4 = x*z1
714     GOTO_ERR_IF(BN_ModAddQuick(t2, t2, r2->y, para->p, opt), ret); // a*z1 + x*x1
715     GOTO_ERR_IF(BN_ModAddQuick(r1->y, r1->y, r1->x, para->p, opt), ret); // x*z1 + x1
716     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, r2->z, para->montP, opt), ret); // (a*z1 + x*x1) * z2
717     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, r1->y, para->montP, opt), ret); // t2=(a*z1+x*x1)*z2*(x*z1+x1)
718 
719     GOTO_ERR_IF(para->method->bnModNistEccMul(r2->y, p->x, r1->z, para->montP, opt), ret); // x * z1
720     GOTO_ERR_IF(BN_ModSubQuick(r2->y, r2->y, r1->x, para->p, opt), ret); // x * z1 - x1
721     GOTO_ERR_IF(para->method->bnModNistEccSqr(r2->y, r2->y, para->montP, opt), ret); // (x * z1 - x1) ^ 2
722     GOTO_ERR_IF(para->method->bnModNistEccMul(r2->y, r2->y, r2->x, para->montP, opt), ret); // x2 * (x * z1 - x1) ^ 2
723     GOTO_ERR_IF(BN_ModAddQuick(t1, t1, t2, para->p, opt), ret); // 2b*z2*z1^2 + t2
724     GOTO_ERR_IF(BN_ModSubQuick(t1, t1, r2->y, para->p, opt), ret); // 2b*z2*z1^2 + t2 - r2->y
725     GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, r1->z, para->montP, opt), ret); // (2b*z2*z1^2 - t2 - r2->y) * z1
726 
727     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t0, p->y, para->montP, opt), ret); // t2 = z2 * z1^2 * y
728     GOTO_ERR_IF(BN_ModAddQuick(t2, t2, t2, para->p, opt), ret); // 2 * y * z2 * z1^2
729 
730     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, r1->x, t2, para->montP, opt), ret); // x * (2 * y * z2 * z1^2)
731     GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, r1->z, para->montP, opt), ret); // (2 * y * z2 * z1^2) * z1
732 
733     para->method->bnMontDec(t2, para->montP);
734     GOTO_ERR_IF(para->method->modInv(t2, t2, para->p, opt), ret); // (2 * y * z2 * z1^2) * -1
735     GOTO_ERR_IF(para->method->bnMontEnc(t2, para->montP, opt, false), ret);
736 
737     GOTO_ERR_IF(para->method->bnModNistEccMul(r1->x, t0, t2, para->montP, opt), ret); // x1 / z1
738     // (2b*z2*z1^2 - t2 - t3) * ((2 * y * z2 * z1^2)
739     GOTO_ERR_IF(para->method->bnModNistEccMul(r1->y, t1, t2, para->montP, opt), ret);
740     para->method->bnMontDec(r1->x, para->montP);
741     para->method->bnMontDec(r1->y, para->montP);
742     GOTO_ERR_IF(BN_SetLimb(r1->z, 1), ret); // x * (2 * y * z2 * z1^2)
743 ERR:
744     OptimizerEnd(opt);
745     return ret;
746 }
747 
748 /*
749  * XZ coordinates for short Weierstrass curves
750  * 2M + 5S + 1*b2 + 1*a + 1*b4
751  * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#doubling-dbl-2002-bj-3
752  * p->z = 1, the above formula can reduce the calculation amount.
753  * MontLadderDouble return:
754  *    r = 2 * p
755 */
MontLadderDouble(const ECC_Para * para,ECC_Point * r,ECC_Point * p,BN_Optimizer * opt)756 static int32_t MontLadderDouble(const ECC_Para *para, ECC_Point *r, ECC_Point *p, BN_Optimizer *opt)
757 {
758     int32_t ret;
759     (void)OptimizerStart(opt);
760     BN_BigNum *t0 = OptimizerGetBn(opt, p->x->room);
761     if (t0 == NULL) {
762         return CRYPT_MEM_ALLOC_FAIL;
763     }
764     GOTO_ERR_IF(para->method->bnModNistEccSqr(t0, p->x, para->montP, opt), ret); // x^2
765     GOTO_ERR_IF(BN_ModAddQuick(r->y, p->x, p->x, para->p, opt), ret); // 2 * x
766     GOTO_ERR_IF(BN_ModAddQuick(r->y, r->y, r->y, para->p, opt), ret); // ry = 4 * x * z = 4 * x (z = 1)
767 
768     GOTO_ERR_IF(BN_ModSubQuick(r->x, t0, para->a, para->p, opt), ret); // t0 - a
769     GOTO_ERR_IF(BN_ModAddQuick(r->z, t0, para->a, para->p, opt), ret); // t0 + a
770 
771     GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, r->x, para->montP, opt), ret); // (t0 - a)^2
772     GOTO_ERR_IF(para->method->bnModNistEccMul(t0, para->b, r->y, para->montP, opt), ret); // b * ry
773     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t0, para->p, opt), ret); // (t0 - a)^2 - b * ry
774     GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t0, para->p, opt), ret); // (t0 - a)^2 - 2 * b * ry
775 
776     GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->y, r->z, para->montP, opt), ret); // ry * (t0 + a)
777     GOTO_ERR_IF(BN_ModAddQuick(t0, para->b, para->b, para->p, opt), ret); // 2 * b
778     GOTO_ERR_IF(BN_ModAddQuick(t0, t0, t0, para->p, opt), ret); // 4 * b
779     GOTO_ERR_IF(BN_ModAddQuick(r->z, r->z, t0, para->p, opt), ret); // ry * (t0 + a) + 4 * b
780 
781 ERR:
782     OptimizerEnd(opt);
783     return ret;
784 }
785 
ECP_PointSwapWithMask(ECC_Point * a,ECC_Point * b,BN_UINT mask)786 static int32_t ECP_PointSwapWithMask(ECC_Point *a, ECC_Point *b, BN_UINT mask)
787 {
788     int32_t ret;
789     GOTO_ERR_IF(BN_SwapWithMask(a->x, b->x, mask), ret);
790     GOTO_ERR_IF(BN_SwapWithMask(a->y, b->y, mask), ret);
791     GOTO_ERR_IF(BN_SwapWithMask(a->z, b->z, mask), ret);
792 ERR:
793     return ret;
794 }
795 
796 /*
797  * ref <Weierstraß Elliptic Curves and side-Channel Attacks>
798  * Montgomery ladder to achieve k * Pt
799  */
ECP_PointMulMont(ECC_Para * para,ECC_Point * r,const BN_BigNum * k,const ECC_Point * pt)800 int32_t ECP_PointMulMont(ECC_Para *para,  ECC_Point *r, const BN_BigNum *k, const ECC_Point *pt)
801 {
802     if (para == NULL || r == NULL || k == NULL) {
803         return CRYPT_NULL_INPUT;
804     }
805     if (((pt != NULL) && (para->id != pt->id)) || (para->id != r->id)) {
806         return CRYPT_ECC_POINT_ERR_CURVE_ID;
807     }
808     if (pt != NULL && BN_IsZero(pt->z)) {
809         return CRYPT_ECC_POINT_AT_INFINITY;
810     }
811     if (BN_IsZero(k)) {
812         BN_Zeroize(r->z);
813         return CRYPT_SUCCESS;
814     }
815     if (BN_Cmp(k, para->n) == 0 && pt != NULL) {
816         return ECP_PointMulFast(para, r, para->n, pt);
817     }
818     int32_t ret;
819     BN_UINT mask1 = 0;
820     BN_UINT mask2 = 0;
821     BN_UINT tmp;
822     uint32_t bits;
823     ECC_Point *base = (pt != NULL) ? ECC_DupPoint(pt) : ECC_GetGFromPara(para);
824     ECC_Point *r1 = ECC_NewPoint(para);
825     BN_Optimizer *opt = BN_OptimizerCreate();
826     if (base == NULL || r1 == NULL || opt == NULL) {
827         ret = CRYPT_MEM_ALLOC_FAIL;
828         BSL_ERR_PUSH_ERROR(ret);
829         goto ERR;
830     }
831     // Convert base to affine.
832     GOTO_ERR_IF(ECP_Point2Affine(para, base, base), ret);
833     GOTO_ERR_IF(ECC_PointToMont(para, base, opt), ret);
834     GOTO_ERR_IF(ECC_CopyPoint(r, base), ret); // r = base
835     GOTO_ERR_IF(MontLadderDouble(para, r1, r, opt), ret);
836     bits = BN_Bits(k);
837     for (uint32_t i = bits - 1; i > 0; i--) {
838         tmp = BN_GetBit(k, i - 1);
839         mask2 = (-tmp) & BN_MASK;
840         GOTO_ERR_IF(ECP_PointSwapWithMask(r, r1, mask2 ^ mask1), ret);
841         GOTO_ERR_IF(MontLadderDoubleAndAdd(para, r, r1, base, opt), ret);
842         mask1 ^= (mask2 ^ mask1);
843     }
844     GOTO_ERR_IF(ECP_PointSwapWithMask(r, r1, mask1), ret);
845     GOTO_ERR_IF(MontLadderRecoverYAndToMont(para, r, r1, base, opt), ret);
846 ERR:
847     BN_OptimizerDestroy(opt);
848     ECC_FreePoint(r1);
849     ECC_FreePoint(base);
850     return ret;
851 }
852 
853 #endif /* HITLS_CRYPTO_ECC */
854