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 #ifdef HITLS_CRYPTO_ECC
18
19 #include "securec.h"
20 #include "bsl_sal.h"
21 #include "bsl_err_internal.h"
22 #include "crypt_utils.h"
23 #include "crypt_errno.h"
24 #include "ecc_local.h"
25
26 #if defined(HITLS_CRYPTO_CURVE_NISTP224) || defined(HITLS_CRYPTO_CURVE_NISTP256) || \
27 defined(HITLS_CRYPTO_CURVE_NISTP384) || defined(HITLS_CRYPTO_CURVE_NISTP521) || defined(HITLS_CRYPTO_CURVE_SM2)
28
CreatTmpBn(BN_BigNum ** t1,BN_BigNum ** t2,BN_BigNum ** t3,BN_BigNum ** t4,uint32_t bits)29 static int32_t CreatTmpBn(BN_BigNum **t1, BN_BigNum **t2, BN_BigNum **t3, BN_BigNum **t4, uint32_t bits)
30 {
31 *t1 = BN_Create(bits);
32 *t2 = BN_Create(bits);
33 *t3 = BN_Create(bits);
34 *t4 = BN_Create(bits);
35 if (*t1 == NULL || *t2 == NULL || *t3 == NULL || *t4 == NULL) {
36 BSL_ERR_PUSH_ERROR(CRYPT_MEM_ALLOC_FAIL);
37 return CRYPT_MEM_ALLOC_FAIL;
38 }
39 return CRYPT_SUCCESS;
40 }
41
DestroyTmpBn(BN_BigNum * t1,BN_BigNum * t2,BN_BigNum * t3,BN_BigNum * t4)42 static void DestroyTmpBn(
43 BN_BigNum *t1, BN_BigNum *t2, BN_BigNum *t3, BN_BigNum *t4)
44 {
45 BN_Destroy(t1);
46 BN_Destroy(t2);
47 BN_Destroy(t3);
48 BN_Destroy(t4);
49 }
50
51 // Jacobian coordinate double the point
ECP_NistPointDouble(const ECC_Para * para,ECC_Point * r,const ECC_Point * a)52 int32_t ECP_NistPointDouble(const ECC_Para *para, ECC_Point *r, const ECC_Point *a)
53 {
54 if (para == NULL || r == NULL || a == NULL) {
55 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
56 return CRYPT_NULL_INPUT;
57 }
58 int32_t ret;
59 uint32_t bits = BN_Bits(para->p);
60
61 BN_Optimizer *opt = BN_OptimizerCreate();
62 BN_BigNum *t1 = BN_Create(bits);
63 BN_BigNum *t2 = BN_Create(bits);
64 BN_BigNum *t3 = BN_Create(bits);
65 BN_BigNum *halfP = ECP_HalfPGet(para->p);
66 if (t1 == NULL || t2 == NULL || t3 == NULL || halfP == NULL || opt == NULL) {
67 ret = CRYPT_MEM_ALLOC_FAIL;
68 BSL_ERR_PUSH_ERROR(ret);
69 goto ERR;
70 }
71
72 GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->p, opt), ret);
73 GOTO_ERR_IF(BN_ModSubQuick(t2, a->x, t1, para->p, opt), ret);
74 GOTO_ERR_IF(BN_ModAddQuick(t1, a->x, t1, para->p, opt), ret);
75 GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, t1, para->p, opt), ret);
76
77 GOTO_ERR_IF(BN_ModAddQuick(t3, t2, t2, para->p, opt), ret);
78 GOTO_ERR_IF(BN_ModAddQuick(t2, t3, t2, para->p, opt), ret); // t2 = 3*t2
79 GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
80 GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->y, a->z, para->p, opt), ret);
81 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->p, opt), ret);
82 GOTO_ERR_IF(para->method->bnModNistEccMul(t3, r->y, a->x, para->p, opt), ret);
83
84 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->y, r->y, para->p, opt), ret);
85 GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->p, opt), ret);
86 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->p, opt), ret);
87 GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret);
88 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret);
89
90 GOTO_ERR_IF(BN_ModSubQuick(t1, t3, r->x, para->p, opt), ret);
91 GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t2, para->p, opt), ret);
92 GOTO_ERR_IF(BN_ModSubQuick(r->y, t1, r->y, para->p, opt), ret);
93 ERR:
94 BN_Destroy(t1);
95 BN_Destroy(t2);
96 BN_Destroy(t3);
97 BN_Destroy(halfP);
98 BN_OptimizerDestroy(opt);
99 return ret;
100 }
101
102 // Jacobian coordinate multi-double the point: r = (2^m) * pt
ECP_NistPointMultDouble(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,uint32_t m)103 int32_t ECP_NistPointMultDouble(const ECC_Para *para, ECC_Point *r, const ECC_Point *a, uint32_t m)
104 {
105 if (para == NULL || r == NULL || a == NULL) {
106 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
107 return CRYPT_NULL_INPUT;
108 }
109 uint32_t tm = m;
110 int32_t ret;
111 uint32_t bits = BN_Bits(para->p);
112 BN_BigNum *ta = NULL, *tb = NULL, *tc = NULL, *tw = NULL;
113 BN_BigNum *halfP = ECP_HalfPGet(para->p);
114 BN_Optimizer *opt = BN_OptimizerCreate();
115 GOTO_ERR_IF_EX(CreatTmpBn(&ta, &tb, &tc, &tw, bits), ret);
116 if (halfP == NULL || opt == NULL) {
117 ret = CRYPT_MEM_ALLOC_FAIL;
118 BSL_ERR_PUSH_ERROR(ret);
119 goto ERR;
120 }
121
122 GOTO_ERR_IF(BN_Copy(r->x, a->x), ret);
123 GOTO_ERR_IF(BN_ModAddQuick(r->y, a->y, a->y, para->p, opt), ret);
124 GOTO_ERR_IF(BN_Copy(r->z, a->z), ret);
125
126 GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, a->z, para->p, opt), ret);
127 GOTO_ERR_IF(para->method->bnModNistEccSqr(tw, tw, para->p, opt), ret);
128
129 while (tm > 0) {
130 // 3.1
131 // ta = 3*(x^2 - tw)
132 GOTO_ERR_IF(para->method->bnModNistEccSqr(ta, r->x, para->p, opt), ret);
133 GOTO_ERR_IF(BN_ModSubQuick(tc, ta, tw, para->p, opt), ret);
134 GOTO_ERR_IF(BN_ModAddQuick(ta, tc, tc, para->p, opt), ret);
135 GOTO_ERR_IF(BN_ModAddQuick(ta, ta, tc, para->p, opt), ret);
136 // tb = x*(y^2)
137 GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, r->y, para->p, opt), ret);
138 GOTO_ERR_IF(para->method->bnModNistEccMul(tb, tc, r->x, para->p, opt), ret);
139
140 // 3.2
141 // x = ta^2 - 2*tb
142 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, ta, para->p, opt), ret);
143 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, tb, para->p, opt), ret);
144 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, tb, para->p, opt), ret);
145 // z = zy
146 GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, r->z, r->y, para->p, opt), ret);
147
148 // 3.3
149 // tc = y^4
150 GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, r->y, para->p, opt), ret);
151 GOTO_ERR_IF(para->method->bnModNistEccSqr(tc, tc, para->p, opt), ret);
152 // m = m - 1, if bit > 0, tw = tw * (y^4)
153 tm--;
154 if (tm > 0) {
155 GOTO_ERR_IF(para->method->bnModNistEccMul(tw, tw, tc, para->p, opt), ret);
156 }
157 // 3.4
158 // y = 2*ta*(tb - x) - (y^4)
159 GOTO_ERR_IF(BN_ModSubQuick(r->y, tb, r->x, para->p, opt), ret);
160 GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, ta, para->p, opt), ret);
161 GOTO_ERR_IF(BN_ModAddQuick(r->y, r->y, r->y, para->p, opt), ret);
162 GOTO_ERR_IF(BN_ModSubQuick(r->y, r->y, tc, para->p, opt), ret);
163 }
164 GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, r->y, halfP, para->p, opt), ret);
165 ERR:
166 DestroyTmpBn(ta, tb, tc, tw);
167 BN_Destroy(halfP);
168 BN_OptimizerDestroy(opt);
169 return ret;
170 }
171
172 // Point addition calculation (Jacobian point a plus affine point b)
173 // Algorithm Reference ECP_NistPointAddAffineMont.
ECP_NistPointAddAffine(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)174 int32_t ECP_NistPointAddAffine(const ECC_Para *para, ECC_Point *r, const ECC_Point *a,
175 const ECC_Point *b)
176 {
177 if (para == NULL || r == NULL || a == NULL || b == NULL) {
178 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
179 return CRYPT_NULL_INPUT;
180 }
181 if (BN_IsZero(a->z)) {
182 // If point a is an infinity point, r = b
183 return ECC_CopyPoint(r, b);
184 }
185 int32_t ret;
186 uint32_t bits = BN_Bits(para->p);
187
188 BN_Optimizer *opt = BN_OptimizerCreate();
189 BN_BigNum *t1 = NULL, *t2 = NULL, *t3 = NULL, *t4 = NULL;
190 GOTO_ERR_IF_EX(CreatTmpBn(&t1, &t2, &t3, &t4, bits), ret);
191 if (opt == NULL) {
192 ret = CRYPT_MEM_ALLOC_FAIL;
193 BSL_ERR_PUSH_ERROR(ret);
194 goto ERR;
195 }
196
197 GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, a->z, para->p, opt), ret);
198 GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t1, a->z, para->p, opt), ret);
199 GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, b->x, para->p, opt), ret);
200 GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t2, b->y, para->p, opt), ret);
201 GOTO_ERR_IF(BN_ModSubQuick(t1, t1, a->x, para->p, opt), ret);
202 GOTO_ERR_IF(BN_ModSubQuick(t2, t2, a->y, para->p, opt), ret);
203
204 if (BN_IsZero(t1)) {
205 if (BN_IsZero(t2)) {
206 // If two points are equal, use double the point for calculation.
207 GOTO_ERR_IF(ECP_NistPointDouble(para, r, b), ret);
208 goto ERR;
209 } else {
210 // Obtain the infinity point.
211 GOTO_ERR_IF(BN_SetLimb(r->z, 0), ret);
212 goto ERR;
213 }
214 }
215 GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, a->z, t1, para->p, opt), ret);
216
217 GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, t1, para->p, opt), ret);
218 GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t1, t3, para->p, opt), ret);
219 GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, a->x, para->p, opt), ret);
220 GOTO_ERR_IF(BN_ModAddQuick(t1, t3, t3, para->p, opt), ret);
221 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->p, opt), ret);
222 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret);
223 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t4, para->p, opt), ret);
224 GOTO_ERR_IF(BN_ModSubQuick(t3, t3, r->x, para->p, opt), ret);
225 GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, t2, para->p, opt), ret);
226 GOTO_ERR_IF(para->method->bnModNistEccMul(t4, t4, a->y, para->p, opt), ret);
227 GOTO_ERR_IF(BN_ModSubQuick(r->y, t3, t4, para->p, opt), ret);
228 ERR:
229 DestroyTmpBn(t1, t2, t3, t4);
230 BN_OptimizerDestroy(opt);
231 return ret;
232 }
233
234 // Point addition calculation (Jacobian point a plus Jacobian point b)
235 // Algorithm Reference ECP_NistPointAddMont.
ECP_NistPointAdd(const ECC_Para * para,ECC_Point * r,const ECC_Point * a,const ECC_Point * b)236 int32_t ECP_NistPointAdd(const ECC_Para *para, ECC_Point *r, const ECC_Point *a,
237 const ECC_Point *b)
238 {
239 if (para == NULL || r == NULL || a == NULL || b == NULL) {
240 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
241 return CRYPT_NULL_INPUT;
242 }
243 if (BN_IsZero(a->z)) {
244 // If point a is an infinity point, r = b
245 return ECC_CopyPoint(r, b);
246 }
247 if (BN_IsZero(b->z)) {
248 // If point b is an infinity point, r = a
249 return ECC_CopyPoint(r, a);
250 }
251 int32_t ret;
252 BN_Optimizer *opt = BN_OptimizerCreate();
253 if (opt == NULL) {
254 return CRYPT_MEM_ALLOC_FAIL;
255 }
256 (void)OptimizerStart(opt);
257 BN_BigNum *t1 = OptimizerGetBn(opt, a->x->room);
258 BN_BigNum *t2 = OptimizerGetBn(opt, a->x->room);
259 BN_BigNum *t3 = OptimizerGetBn(opt, a->x->room);
260 BN_BigNum *t4 = OptimizerGetBn(opt, a->x->room);
261 BN_BigNum *t5 = OptimizerGetBn(opt, a->x->room);
262 BN_BigNum *t6 = OptimizerGetBn(opt, a->x->room);
263 if (t1 == NULL || t2 == NULL || t3 == NULL || t4 == NULL || t5 == NULL || t6 == NULL) {
264 BSL_ERR_PUSH_ERROR(CRYPT_MEM_ALLOC_FAIL);
265 ret = CRYPT_MEM_ALLOC_FAIL;
266 goto ERR;
267 }
268
269 GOTO_ERR_IF(para->method->bnModNistEccSqr(t1, b->z, para->p, opt), ret); // Z2^2
270 GOTO_ERR_IF(para->method->bnModNistEccMul(t2, t1, b->z, para->p, opt), ret); // Z2^3
271 GOTO_ERR_IF(para->method->bnModNistEccMul(t5, t1, a->x, para->p, opt), ret); // U1 = X1*Z2^2
272 GOTO_ERR_IF(para->method->bnModNistEccMul(t6, t2, a->y, para->p, opt), ret); // S1 = Y1*Z2^3
273 GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, a->z, para->p, opt), ret); // T3 = Z1^2
274
275 GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, a->z, b->y, para->p, opt), ret); // r->y = Y2*Z1
276 GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, a->z, b->z, para->p, opt), ret); // r->z = Z2*Z1
277 GOTO_ERR_IF(para->method->bnModNistEccMul(r->y, t3, r->y, para->p, opt), ret); // S2 = Y2 * Z1^3
278 GOTO_ERR_IF(para->method->bnModNistEccMul(r->x, t3, b->x, para->p, opt), ret); // U2 = Z1^2 * X2
279
280 GOTO_ERR_IF(BN_ModSubQuick(t1, r->x, t5, para->p, opt), ret); // H = U2 - U1
281 GOTO_ERR_IF(BN_ModSubQuick(t2, r->y, t6, para->p, opt), ret); // r = S2 - S1
282 if (BN_IsZero(t1) && BN_IsZero(t2)) {
283 GOTO_ERR_IF(para->method->pointDouble(para, r, b), ret);
284 goto ERR;
285 }
286 GOTO_ERR_IF(para->method->bnModNistEccMul(r->z, t1, r->z, para->p, opt), ret); // r->z = H * Z2*Z1
287 GOTO_ERR_IF(para->method->bnModNistEccSqr(t3, t1, para->p, opt), ret); // t3 = H^2
288
289 GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t3, para->p, opt), ret); // t1 = H^3
290 GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t3, t5, para->p, opt), ret); // t3 = H^2 * U1
291 GOTO_ERR_IF(para->method->bnModNistEccSqr(r->x, t2, para->p, opt), ret); // r->x = r ^ 2
292
293 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t3, para->p, opt), ret); // r ^ 2 - H^2*U1
294 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t3, para->p, opt), ret); // r ^ 2 - 2*H^2 * U1
295 GOTO_ERR_IF(BN_ModSubQuick(r->x, r->x, t1, para->p, opt), ret); // r ^ 2 - 2*H^2*U1 - H^3
296 GOTO_ERR_IF(BN_ModSubQuick(t3, t3, r->x, para->p, opt), ret); // H^2 * U1 - X3
297 GOTO_ERR_IF(para->method->bnModNistEccMul(t3, t2, t3, para->p, opt), ret); // r * (H^2 * U1 - X3)
298 GOTO_ERR_IF(para->method->bnModNistEccMul(t1, t1, t6, para->p, opt), ret); // t1 = H^3 * S1
299 GOTO_ERR_IF(BN_ModSubQuick(r->y, t3, t1, para->p, opt), ret); // r * (H^2 * U1 - X3) - H^3 * S1
300 ERR:
301 BN_OptimizerDestroy(opt);
302 return ret;
303 }
304
305 #endif
306
ECP_ModOrderInv(const ECC_Para * para,BN_BigNum * r,const BN_BigNum * a)307 int32_t ECP_ModOrderInv(const ECC_Para *para, BN_BigNum *r, const BN_BigNum *a)
308 {
309 int32_t ret;
310 BN_Optimizer *opt = NULL;
311 if (para == NULL || r == NULL || a == NULL) {
312 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
313 return CRYPT_NULL_INPUT;
314 }
315
316 opt = BN_OptimizerCreate();
317 if (opt == NULL) {
318 BSL_ERR_PUSH_ERROR(CRYPT_MEM_ALLOC_FAIL);
319 return CRYPT_MEM_ALLOC_FAIL;
320 }
321
322 ret = BN_ModInv(r, a, para->n, opt);
323 BN_OptimizerDestroy(opt);
324 return ret;
325 }
326 #endif /* HITLS_CRYPTO_ECC */
327