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_BN_PRIME
18
19 #include <stdint.h>
20 #include "securec.h"
21 #include "bsl_err_internal.h"
22 #include "bsl_sal.h"
23 #include "crypt_errno.h"
24 #include "bn_bincal.h"
25 #include "bn_optimizer.h"
26
27 /*
28 * Differential table of adjacent prime numbers, size = 1024
29 * The times of trial division will affect whether the number enters the Miller-rabin test.
30 * We consider common prime lengths: 1024, 2048, 4096, 8192 bits.
31 * 1024 bits: we choose 128 try times, ref the paper of 'A Performant, Misuse-Resistant API for Primality Testing'.
32 * 2048 bits: 128 try times: 1 (performance baseline)
33 * 384 try times: +0.15
34 * 512 try times: +0.03
35 * 1024 try times: +0.16
36 * 4096 bits: 1024 try times: 0.04 tps
37 * 2048 try times: 0.02 tps
38 * 8192 bits: 1024 try times: 0.02 tps
39 * 2048 try times: 0.02 tps
40 */
41 static const uint8_t PRIME_DIFF_TABLE[1024] = {
42 0, 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
43 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4,
44 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12,
45 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4,
46 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8,
47 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4,
48 6, 12, 2, 18, 6, 10, 6, 6, 2, 6, 10, 6, 6, 2, 6, 6,
49 4, 2, 12, 10, 2, 4, 6, 6, 2, 12, 4, 6, 8, 10, 8, 10,
50 8, 6, 6, 4, 8, 6, 4, 8, 4, 14, 10, 12, 2, 10, 2, 4,
51 2, 10, 14, 4, 2, 4, 14, 4, 2, 4, 20, 4, 8, 10, 8, 4,
52 6, 6, 14, 4, 6, 6, 8, 6, 12, 4, 6, 2, 10, 2, 6, 10,
53 2, 10, 2, 6, 18, 4, 2, 4, 6, 6, 8, 6, 6, 22, 2, 10,
54 8, 10, 6, 6, 8, 12, 4, 6, 6, 2, 6, 12, 10, 18, 2, 4,
55 6, 2, 6, 4, 2, 4, 12, 2, 6, 34, 6, 6, 8, 18, 10, 14,
56 4, 2, 4, 6, 8, 4, 2, 6, 12, 10, 2, 4, 2, 4, 6, 12,
57 12, 8, 12, 6, 4, 6, 8, 4, 8, 4, 14, 4, 6, 2, 4, 6,
58 2, 6, 10, 20, 6, 4, 2, 24, 4, 2, 10, 12, 2, 10, 8, 6,
59 6, 6, 18, 6, 4, 2, 12, 10, 12, 8, 16, 14, 6, 4, 2, 4,
60 2, 10, 12, 6, 6, 18, 2, 16, 2, 22, 6, 8, 6, 4, 2, 4,
61 8, 6, 10, 2, 10, 14, 10, 6, 12, 2, 4, 2, 10, 12, 2, 16,
62 2, 6, 4, 2, 10, 8, 18, 24, 4, 6, 8, 16, 2, 4, 8, 16,
63 2, 4, 8, 6, 6, 4, 12, 2, 22, 6, 2, 6, 4, 6, 14, 6,
64 4, 2, 6, 4, 6, 12, 6, 6, 14, 4, 6, 12, 8, 6, 4, 26,
65 18, 10, 8, 4, 6, 2, 6, 22, 12, 2, 16, 8, 4, 12, 14, 10,
66 2, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10,
67 8, 4, 14, 10, 12, 2, 6, 4, 2, 16, 14, 4, 6, 8, 6, 4,
68 18, 8, 10, 6, 6, 8, 10, 12, 14, 4, 6, 6, 2, 28, 2, 10,
69 8, 4, 14, 4, 8, 12, 6, 12, 4, 6, 20, 10, 2, 16, 26, 4,
70 2, 12, 6, 4, 12, 6, 8, 4, 8, 22, 2, 4, 2, 12, 28, 2,
71 6, 6, 6, 4, 6, 2, 12, 4, 12, 2, 10, 2, 16, 2, 16, 6,
72 20, 16, 8, 4, 2, 4, 2, 22, 8, 12, 6, 10, 2, 4, 6, 2,
73 6, 10, 2, 12, 10, 2, 10, 14, 6, 4, 6, 8, 6, 6, 16, 12,
74 2, 4, 14, 6, 4, 8, 10, 8, 6, 6, 22, 6, 2, 10, 14, 4,
75 6, 18, 2, 10, 14, 4, 2, 10, 14, 4, 8, 18, 4, 6, 2, 4,
76 6, 2, 12, 4, 20, 22, 12, 2, 4, 6, 6, 2, 6, 22, 2, 6,
77 16, 6, 12, 2, 6, 12, 16, 2, 4, 6, 14, 4, 2, 18, 24, 10,
78 6, 2, 10, 2, 10, 2, 10, 6, 2, 10, 2, 10, 6, 8, 30, 10,
79 2, 10, 8, 6, 10, 18, 6, 12, 12, 2, 18, 6, 4, 6, 6, 18,
80 2, 10, 14, 6, 4, 2, 4, 24, 2, 12, 6, 16, 8, 6, 6, 18,
81 16, 2, 4, 6, 2, 6, 6, 10, 6, 12, 12, 18, 2, 6, 4, 18,
82 8, 24, 4, 2, 4, 6, 2, 12, 4, 14, 30, 10, 6, 12, 14, 6,
83 10, 12, 2, 4, 6, 8, 6, 10, 2, 4, 14, 6, 6, 4, 6, 2,
84 10, 2, 16, 12, 8, 18, 4, 6, 12, 2, 6, 6, 6, 28, 6, 14,
85 4, 8, 10, 8, 12, 18, 4, 2, 4, 24, 12, 6, 2, 16, 6, 6,
86 14, 10, 14, 4, 30, 6, 6, 6, 8, 6, 4, 2, 12, 6, 4, 2,
87 6, 22, 6, 2, 4, 18, 2, 4, 12, 2, 6, 4, 26, 6, 6, 4,
88 8, 10, 32, 16, 2, 6, 4, 2, 4, 2, 10, 14, 6, 4, 8, 10,
89 6, 20, 4, 2, 6, 30, 4, 8, 10, 6, 6, 8, 6, 12, 4, 6,
90 2, 6, 4, 6, 2, 10, 2, 16, 6, 20, 4, 12, 14, 28, 6, 20,
91 4, 18, 8, 6, 4, 6, 14, 6, 6, 10, 2, 10, 12, 8, 10, 2,
92 10, 8, 12, 10, 24, 2, 4, 8, 6, 4, 8, 18, 10, 6, 6, 2,
93 6, 10, 12, 2, 10, 6, 6, 6, 8, 6, 10, 6, 2, 6, 6, 6,
94 10, 8, 24, 6, 22, 2, 18, 4, 8, 10, 30, 8, 18, 4, 2, 10,
95 6, 2, 6, 4, 18, 8, 12, 18, 16, 6, 2, 12, 6, 10, 2, 10,
96 2, 6, 10, 14, 4, 24, 2, 16, 2, 10, 2, 10, 20, 4, 2, 4,
97 8, 16, 6, 6, 2, 12, 16, 8, 4, 6, 30, 2, 10, 2, 6, 4,
98 6, 6, 8, 6, 4, 12, 6, 8, 12, 4, 14, 12, 10, 24, 6, 12,
99 6, 2, 22, 8, 18, 10, 6, 14, 4, 2, 6, 10, 8, 6, 4, 6,
100 30, 14, 10, 2, 12, 10, 2, 16, 2, 18, 24, 18, 6, 16, 18, 6,
101 2, 18, 4, 6, 2, 10, 8, 10, 6, 6, 8, 4, 6, 2, 10, 2,
102 12, 4, 6, 6, 2, 12, 4, 14, 18, 4, 6, 20, 4, 8, 6, 4,
103 8, 4, 14, 6, 4, 14, 12, 4, 2, 30, 4, 24, 6, 6, 12, 12,
104 14, 6, 4, 2, 4, 18, 6, 12, 8, 6, 4, 12, 2, 12, 30, 16,
105 2, 6, 22, 14, 6, 10, 12, 6, 2, 4, 8, 10, 6, 6, 24, 14
106 };
107
108 /* Times of trial division. */
DivisorsCnt(uint32_t bits)109 static uint32_t DivisorsCnt(uint32_t bits)
110 {
111 if (bits <= 1024) { /* 1024bit */
112 return 128; /* 128 times check */
113 }
114 return 1024; /* 1024 times check */
115 }
116
117 // Minimum times of checking for Miller-Rabin.
118 // The probability of errors in a check is one quarter. After 64 rounds of check, the error rate is 2 ^ - 128.
MinChecks(uint32_t bits)119 static uint32_t MinChecks(uint32_t bits)
120 {
121 if (bits >= 2048) { /* 2048bit */
122 return 128; /* 128 rounds of verification */
123 }
124 return 64; /* 64 rounds of verification */
125 }
126
127 /* A BigNum mod a limb, limb < (1 << (BN_UINT_BITS >> 1)) */
ModLimbHalf(const BN_BigNum * a,BN_UINT w)128 static BN_UINT ModLimbHalf(const BN_BigNum *a, BN_UINT w)
129 {
130 BN_UINT rem = 0;
131 uint32_t i;
132 for (i = a->size; i > 0; i--) {
133 MOD_HALF(rem, rem, a->data[i - 1], w);
134 }
135 return rem;
136 }
LimbCheck(const BN_BigNum * bn)137 static int32_t LimbCheck(const BN_BigNum *bn)
138 {
139 uint32_t bits = BN_Bits(bn);
140 uint32_t cnt = DivisorsCnt(bits);
141 int32_t ret = CRYPT_SUCCESS;
142 BN_UINT littlePrime = 2;
143 for (uint32_t i = 0; i < cnt; i++) {
144 // Try division. Large prime numbers do not divide small prime numbers.
145 littlePrime += PRIME_DIFF_TABLE[i];
146 BN_UINT mod = ModLimbHalf(bn, littlePrime);
147 if (mod == 0) {
148 if (BN_IsLimb(bn, littlePrime) == false) { // small prime judgement
149 ret = CRYPT_BN_NOR_CHECK_PRIME;
150 }
151 break;
152 }
153 }
154 return ret;
155 }
156 /* The random number increases by 2 each time, and added for n times,
157 so that it is mutually primed to all data in the prime table. */
FillUp(BN_BigNum * rnd,const BN_UINT * mods,uint32_t modsLen)158 static int32_t FillUp(BN_BigNum *rnd, const BN_UINT *mods, uint32_t modsLen)
159 {
160 uint32_t i;
161 uint32_t complete = 0;
162 uint32_t bits = BN_Bits(rnd);
163 uint32_t cnt = modsLen;
164 BN_UINT inc = 0;
165 while (complete == 0) {
166 BN_UINT littlePrime = 2; // the minimum prime = 2
167 for (i = 1; i < cnt; i++) {
168 /* check */
169 littlePrime += PRIME_DIFF_TABLE[i];
170 if ((mods[i] + inc) % littlePrime == 0) {
171 inc += 2; // inc increases by 2 each time
172 break;
173 }
174 if (i == cnt - 1) { // end and exit
175 complete = 1;
176 }
177 }
178 if (inc + 2 == 0) { // inc increases by 2 each time. Check whether the inc may overflow.
179 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
180 return CRYPT_BN_NOR_CHECK_PRIME;
181 }
182 }
183 int32_t ret = BN_AddLimb(rnd, rnd, inc);
184 if (ret != CRYPT_SUCCESS) {
185 BSL_ERR_PUSH_ERROR(ret);
186 return ret;
187 }
188 // If the random number length of a prime number is incorrect, generate a new random number.
189 if (BN_Bits(rnd) != bits) {
190 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
191 return CRYPT_BN_NOR_CHECK_PRIME;
192 }
193 return CRYPT_SUCCESS;
194 }
195
196 /* Generate random numbers that can be mutually primed with the data in the small prime number table. */
ProbablePrime(BN_BigNum * rnd,BN_BigNum * e,uint32_t bits,bool half,BN_Optimizer * opt)197 static int32_t ProbablePrime(BN_BigNum *rnd, BN_BigNum *e, uint32_t bits, bool half, BN_Optimizer *opt)
198 {
199 const int32_t maxCnt = 100; /* try 100 times */
200 int32_t tryCnt = 0;
201 uint32_t i;
202 int32_t ret;
203 uint32_t cnt = DivisorsCnt(bits);
204 ret = OptimizerStart(opt);
205 if (ret != CRYPT_SUCCESS) {
206 return ret;
207 }
208 BN_BigNum *mods = OptimizerGetBn(opt, cnt);
209 if (mods == NULL) {
210 OptimizerEnd(opt);
211 BSL_ERR_PUSH_ERROR(CRYPT_BN_OPTIMIZER_GET_FAIL);
212 return CRYPT_BN_OPTIMIZER_GET_FAIL;
213 }
214
215 uint32_t top = ((half == true) ? BN_RAND_TOP_TWOBIT : BN_RAND_TOP_ONEBIT);
216 do {
217 tryCnt++;
218 if (tryCnt > maxCnt) {
219 /* If it cannot be generated after loop 100 times, a failure message is returned. */
220 OptimizerEnd(opt);
221 /* In this case, the random number may be incorrect. Keep the error information. */
222 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_GEN_PRIME);
223 return CRYPT_BN_NOR_GEN_PRIME;
224 }
225 // 'top' can control whether to set the most two significant bits to 1.
226 // RSA key generation usually focuses on this parameter to ensure the length of p*q.
227 ret = BN_RandEx(opt->libCtx, rnd, bits, top, BN_RAND_BOTTOM_ONEBIT);
228 if (ret != CRYPT_SUCCESS) {
229 BSL_ERR_PUSH_ERROR(ret);
230 OptimizerEnd(opt);
231 return ret;
232 }
233 BN_UINT littlePrime = 2; // the minimum prime = 2
234 // Random number rnd divided by the prime number in the table of small prime numbers, modulo mods.
235 for (i = 1; i < cnt; i++) {
236 littlePrime += PRIME_DIFF_TABLE[i];
237 mods->data[i] = ModLimbHalf(rnd, littlePrime);
238 }
239 // Check the mods and supplement the rnd.
240 ret = FillUp(rnd, mods->data, cnt);
241 if (ret != CRYPT_BN_NOR_CHECK_PRIME && ret != CRYPT_SUCCESS) {
242 BSL_ERR_PUSH_ERROR(ret);
243 OptimizerEnd(opt);
244 return ret;
245 }
246 if (ret != CRYPT_BN_NOR_CHECK_PRIME && e != NULL) {
247 // check if rnd-1 and e are coprime
248 // reference: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf A.1.3
249 BN_BigNum *rnd1 = OptimizerGetBn(opt, BITS_TO_BN_UNIT(bits));
250 BN_BigNum *inv = OptimizerGetBn(opt, e->size);
251 if (rnd1 == NULL || inv == NULL) {
252 OptimizerEnd(opt);
253 BSL_ERR_PUSH_ERROR(CRYPT_BN_OPTIMIZER_GET_FAIL);
254 return CRYPT_BN_OPTIMIZER_GET_FAIL;
255 }
256 ret = BN_SubLimb(rnd1, rnd, 1);
257 if (ret != CRYPT_SUCCESS) {
258 OptimizerEnd(opt);
259 BSL_ERR_PUSH_ERROR(ret);
260 return ret;
261 }
262 ret = BN_ModInv(inv, rnd1, e, opt);
263 }
264 } while (ret == CRYPT_BN_NOR_CHECK_PRIME);
265 OptimizerEnd(opt);
266 return ret;
267 }
268
BnCheck(const BN_BigNum * bnSubOne,const BN_BigNum * bnSubThree,const BN_BigNum * divisor,const BN_BigNum * rnd,const BN_Mont * mont)269 static int32_t BnCheck(const BN_BigNum *bnSubOne, const BN_BigNum *bnSubThree,
270 const BN_BigNum *divisor, const BN_BigNum *rnd, const BN_Mont *mont)
271 {
272 if (bnSubOne == NULL || bnSubThree == NULL || divisor == NULL || rnd == NULL) {
273 BSL_ERR_PUSH_ERROR(CRYPT_BN_OPTIMIZER_GET_FAIL);
274 return CRYPT_BN_OPTIMIZER_GET_FAIL;
275 }
276 if (mont == NULL) {
277 BSL_ERR_PUSH_ERROR(CRYPT_MEM_ALLOC_FAIL);
278 return CRYPT_MEM_ALLOC_FAIL;
279 }
280 return CRYPT_SUCCESS;
281 }
282
GenRnd(void * libCtx,BN_BigNum * rnd,const BN_BigNum * bnSubThree)283 static int32_t GenRnd(void *libCtx, BN_BigNum *rnd, const BN_BigNum *bnSubThree)
284 {
285 int32_t ret = BN_RandRangeEx(libCtx, rnd, bnSubThree);
286 if (ret != CRYPT_SUCCESS) {
287 BSL_ERR_PUSH_ERROR(ret);
288 return ret;
289 }
290 return BN_AddLimb(rnd, rnd, 2); /* bn - 3 + 2 = bn - 1 */
291 }
SumCorrect(BN_BigNum * sum,const BN_BigNum * bnSubOne)292 static bool SumCorrect(BN_BigNum *sum, const BN_BigNum *bnSubOne)
293 {
294 if (BN_IsOne(sum) || BN_Cmp(sum, bnSubOne) == 0) {
295 (void)BN_SetLimb(sum, 1);
296 return true;
297 }
298 return false;
299 }
MillerRabinCheckCore(const BN_BigNum * bn,BN_Mont * mont,BN_BigNum * rnd,const BN_BigNum * divisor,const BN_BigNum * bnSubOne,const BN_BigNum * bnSubThree,uint32_t p,uint32_t checkTimes,BN_Optimizer * opt,BN_CbCtx * cb)300 int32_t MillerRabinCheckCore(const BN_BigNum *bn, BN_Mont *mont, BN_BigNum *rnd,
301 const BN_BigNum *divisor, const BN_BigNum *bnSubOne, const BN_BigNum *bnSubThree,
302 uint32_t p, uint32_t checkTimes, BN_Optimizer *opt, BN_CbCtx *cb)
303 {
304 uint32_t i, j;
305 int32_t ret = CRYPT_SUCCESS;
306 uint32_t checks = (checkTimes == 0) ? MinChecks(BN_Bits(bn)) : checkTimes;
307 BN_BigNum *sum = rnd;
308 for (i = 0; i < checks; i++) {
309 // 3.1 Generate a random number rnd, 2 < rnd < n-1
310 ret = GenRnd(opt->libCtx, rnd, bnSubThree);
311 if (ret != CRYPT_SUCCESS) {
312 BSL_ERR_PUSH_ERROR(ret);
313 return ret;
314 }
315 // 3.2 Calculate base = rnd^divisor mod bn
316 ret = BN_MontExp(sum, rnd, divisor, mont, opt);
317 if (ret != CRYPT_SUCCESS) {
318 BSL_ERR_PUSH_ERROR(ret);
319 return ret;
320 }
321 for (j = 0; j < p; j++) {
322 // If sum is equal to 1 or bn-1, the modulus square result must be 1. Exit directly.
323 if (SumCorrect(sum, bnSubOne)) {
324 break;
325 }
326 // sum < bn
327 ret = MontSqrCore(sum, sum, mont, opt);
328 if (ret != CRYPT_SUCCESS) {
329 BSL_ERR_PUSH_ERROR(ret);
330 return ret;
331 }
332 // Inverse negation of Miller Rabin's theorem, if equal to 1, bn is not a prime number.
333 if (BN_IsOne(sum)) {
334 ret = CRYPT_BN_NOR_CHECK_PRIME;
335 return ret;
336 }
337 }
338 // 3.4 Fermat's little theorem inverse negation if sum = rnd^(bn -1) != 1 mod bn, bn is not a prime number.
339 if (!BN_IsOne(sum)) {
340 ret = CRYPT_BN_NOR_CHECK_PRIME;
341 return ret;
342 }
343 #ifdef HITLS_CRYPTO_BN_CB
344 ret = BN_CbCtxCall(cb, 0, 0);
345 if (ret != CRYPT_SUCCESS) {
346 BSL_ERR_PUSH_ERROR(ret);
347 return ret;
348 }
349 #else
350 (void)cb;
351 #endif
352 }
353 return ret;
354 }
BnSubGet(BN_BigNum * bnSubOne,BN_BigNum * bnSubThree,const BN_BigNum * bn)355 static int32_t BnSubGet(BN_BigNum *bnSubOne, BN_BigNum *bnSubThree, const BN_BigNum *bn)
356 {
357 int32_t ret = BN_SubLimb(bnSubOne, bn, 1); /* bn - 1 */
358 if (ret != CRYPT_SUCCESS) {
359 BSL_ERR_PUSH_ERROR(ret);
360 return ret;
361 }
362 return BN_SubLimb(bnSubThree, bn, 3); /* bn - 3 */
363 }
PrimeLimbCheck(const BN_BigNum * bn)364 static int32_t PrimeLimbCheck(const BN_BigNum *bn)
365 {
366 if (BN_IsLimb(bn, 2) || BN_IsLimb(bn, 3)) { /* 2 and 3 directly determine that the number is a prime number. */
367 return CRYPT_SUCCESS;
368 }
369 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
370 return CRYPT_BN_NOR_CHECK_PRIME;
371 }
GetP(const BN_BigNum * bn)372 static uint32_t GetP(const BN_BigNum *bn)
373 {
374 uint32_t p = 0;
375 while (!BN_GetBit(bn, p)) {
376 p++;
377 }
378 return p;
379 }
380 // CRYPT_SUCCESS is returned for a prime number,
381 // and CRYPT_BN_NOR_CHECK_PRIME is returned for a non-prime number. Other error codes are returned.
MillerRabinPrimeVerify(const BN_BigNum * bn,uint32_t checkTimes,BN_Optimizer * opt,BN_CbCtx * cb)382 static int32_t MillerRabinPrimeVerify(const BN_BigNum *bn, uint32_t checkTimes, BN_Optimizer *opt, BN_CbCtx *cb)
383 {
384 int32_t ret = CRYPT_SUCCESS;
385 uint32_t p;
386 if (PrimeLimbCheck(bn) == CRYPT_SUCCESS) { /* 2 and 3 directly determine that the number is a prime number. */
387 return CRYPT_SUCCESS;
388 }
389 if (!BN_GetBit(bn, 0)) { // even
390 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
391 return CRYPT_BN_NOR_CHECK_PRIME;
392 }
393 ret = OptimizerStart(opt);
394 if (ret != CRYPT_SUCCESS) {
395 return ret;
396 }
397 BN_BigNum *bnSubOne = OptimizerGetBn(opt, bn->size); // bnSubOne = bn - 1
398 BN_BigNum *bnSubThree = OptimizerGetBn(opt, bn->size); // bnSubThree = bn - 3
399 BN_BigNum *divisor = OptimizerGetBn(opt, bn->size); // divisor = bnSubOne / 2^p
400 BN_BigNum *rnd = OptimizerGetBn(opt, bn->size); // rnd to verify bn
401 BN_Mont *mont = BN_MontCreate(bn);
402
403 ret = BnCheck(bnSubOne, bnSubThree, divisor, rnd, mont);
404 if (ret != CRYPT_SUCCESS) {
405 BSL_ERR_PUSH_ERROR(ret);
406 goto err;
407 }
408 ret = BnSubGet(bnSubOne, bnSubThree, bn);
409 if (ret != CRYPT_SUCCESS) {
410 BSL_ERR_PUSH_ERROR(ret);
411 goto err;
412 }
413 // 1. Extract the power p of factor 2 in bnSubOne.
414 p = GetP(bnSubOne);
415 // 2. Number after factor 2 is extracted by bnSubOne. divisor = (bn - 1) / 2^p
416 ret = BN_Rshift(divisor, bnSubOne, p);
417 if (ret != CRYPT_SUCCESS) {
418 BSL_ERR_PUSH_ERROR(ret);
419 goto err;
420 }
421 ret = MillerRabinCheckCore(bn, mont, rnd, divisor, bnSubOne, bnSubThree, p, checkTimes, opt, cb);
422 err:
423 BN_MontDestroy(mont);
424 OptimizerEnd(opt);
425 return ret;
426 }
427
428 // CRYPT_SUCCESS is returned for a prime number,
429 // and CRYPT_BN_NOR_CHECK_PRIME is returned for a non-prime number. Other error codes are returned.
BN_PrimeCheck(const BN_BigNum * bn,uint32_t checkTimes,BN_Optimizer * opt,BN_CbCtx * cb)430 int32_t BN_PrimeCheck(const BN_BigNum *bn, uint32_t checkTimes, BN_Optimizer *opt, BN_CbCtx *cb)
431 {
432 if (bn == NULL || opt == NULL) {
433 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
434 return CRYPT_NULL_INPUT;
435 }
436 int32_t ret;
437 // Check whether the value is 0 or 1.
438 if (BN_IsZero(bn) || BN_IsOne(bn)) {
439 return CRYPT_BN_NOR_CHECK_PRIME;
440 }
441 // Check whether the number is negative.
442 if (bn->sign == 1) {
443 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
444 return CRYPT_BN_NOR_CHECK_PRIME;
445 }
446 ret = LimbCheck(bn);
447 if (ret != CRYPT_SUCCESS) {
448 return ret;
449 }
450 #ifdef HITLS_CRYPTO_BN_CB
451 ret = BN_CbCtxCall(cb, 0, 0);
452 if (ret != CRYPT_SUCCESS) {
453 BSL_ERR_PUSH_ERROR(ret);
454 return ret;
455 }
456 #endif
457 return MillerRabinPrimeVerify(bn, checkTimes, opt, cb);
458 }
GenPrimeLimb(BN_BigNum * bn,uint32_t bits,bool half,BN_Optimizer * opt)459 static int32_t GenPrimeLimb(BN_BigNum *bn, uint32_t bits, bool half, BN_Optimizer *opt)
460 {
461 const BN_UINT baseAll[11] = {0, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309};
462 const BN_UINT cntAll[11] = {2, 2, 2, 5, 7, 13, 23, 43, 75, 137, 255};
463 const BN_UINT baseHalf[11] = {1, 3, 5, 9, 15, 24, 43, 76, 135, 242, 439};
464 const BN_UINT cntHalf[11] = {1, 1, 1, 2, 3, 7, 11, 21, 37, 67, 125};
465 const BN_UINT *base = baseAll;
466 const BN_UINT *cnt = cntAll;
467 if (half == true) {
468 base = baseHalf;
469 cnt = cntHalf;
470 }
471 int32_t ret = OptimizerStart(opt);
472 if (ret != CRYPT_SUCCESS) {
473 BSL_ERR_PUSH_ERROR(ret);
474 return ret;
475 }
476 BN_BigNum *bnCnt = OptimizerGetBn(opt, BITS_TO_BN_UNIT(bits));
477 BN_BigNum *bnRnd = OptimizerGetBn(opt, BITS_TO_BN_UNIT(bits));
478 if (bnCnt == NULL || bnRnd == NULL) {
479 OptimizerEnd(opt);
480 BSL_ERR_PUSH_ERROR(CRYPT_BN_OPTIMIZER_GET_FAIL);
481 return CRYPT_BN_OPTIMIZER_GET_FAIL;
482 }
483 (void)BN_SetLimb(bnCnt, cnt[bits - 2]); /* offset, the minimum bit of the interface is 2. */
484 ret = BN_RandRangeEx(opt->libCtx, bnRnd, bnCnt);
485 if (ret != CRYPT_SUCCESS) {
486 OptimizerEnd(opt);
487 BSL_ERR_PUSH_ERROR(ret);
488 return ret;
489 }
490 BN_UINT rnd = bnRnd->data[0] + base[bits - 2]; /* offset, the minimum bit of the interface is 2. */
491 OptimizerEnd(opt);
492 BN_UINT littlePrime = 2;
493 for (BN_UINT i = 1; i <= rnd; i++) {
494 littlePrime += PRIME_DIFF_TABLE[i];
495 }
496 return BN_SetLimb(bn, littlePrime);
497 }
GenCheck(BN_BigNum * bn,uint32_t bits,const BN_Optimizer * opt)498 static int32_t GenCheck(BN_BigNum *bn, uint32_t bits, const BN_Optimizer *opt)
499 {
500 if (bn == NULL) {
501 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
502 return CRYPT_NULL_INPUT;
503 }
504 if (opt == NULL) {
505 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
506 return CRYPT_NULL_INPUT;
507 }
508 if (bits < 2) { // The number of bits less than 2 can only be 0 or 1. The prime number cannot be generated.
509 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_CHECK_PRIME);
510 return CRYPT_BN_NOR_CHECK_PRIME;
511 }
512 return BnExtend(bn, BITS_TO_BN_UNIT(bits));
513 }
514
515 // If the prime number r is generated successfully, CRYPT_SUCCESS is returned.
516 // If the prime number r fails to be generated, CRYPT_BN_NOR_GEN_PRIME is returned. Other error codes are returned.
517 // If half is 1, the prime number whose two most significant bits are 1 is generated.
BN_GenPrime(BN_BigNum * r,BN_BigNum * e,uint32_t bits,bool half,BN_Optimizer * opt,BN_CbCtx * cb)518 int32_t BN_GenPrime(BN_BigNum *r, BN_BigNum *e, uint32_t bits, bool half, BN_Optimizer *opt, BN_CbCtx *cb)
519 {
520 int32_t time = 0;
521 #ifndef HITLS_CRYPTO_BN_CB
522 (void)cb;
523 const int32_t maxTime = 256; /* The maximum number of cycles is 256. If no prime number is generated after the
524 * maximum number of cycles, the operation fails. */
525 #endif
526 int32_t ret = GenCheck(r, bits, opt);
527 if (ret != CRYPT_SUCCESS) {
528 BSL_ERR_PUSH_ERROR(ret);
529 return ret;
530 }
531 if (bits < 13) { // < 13 is limited by the small prime table of 1024 size.
532 return GenPrimeLimb(r, bits, half, opt);
533 }
534 ret = OptimizerStart(opt);
535 if (ret != CRYPT_SUCCESS) {
536 BSL_ERR_PUSH_ERROR(ret);
537 return ret;
538 }
539 /* To preventing insufficient space in addition operations when the rnd is constructed. */
540 BN_BigNum *rnd = OptimizerGetBn(opt, BITS_TO_BN_UNIT(bits) + 1);
541 if (rnd == NULL) {
542 OptimizerEnd(opt);
543 BSL_ERR_PUSH_ERROR(CRYPT_BN_OPTIMIZER_GET_FAIL);
544 return CRYPT_BN_OPTIMIZER_GET_FAIL;
545 }
546 do {
547 #ifdef HITLS_CRYPTO_BN_CB
548 if (BN_CbCtxCall(cb, time, 0) != CRYPT_SUCCESS) {
549 #else
550 if (time == maxTime) {
551 #endif
552 OptimizerEnd(opt);
553 BSL_ERR_PUSH_ERROR(CRYPT_BN_NOR_GEN_PRIME);
554 return CRYPT_BN_NOR_GEN_PRIME;
555 }
556 // Generate a random number bn that may be a prime.
557 ret = ProbablePrime(rnd, e, bits, half, opt);
558 if (ret != CRYPT_SUCCESS) {
559 BSL_ERR_PUSH_ERROR(ret);
560 OptimizerEnd(opt);
561 return ret;
562 }
563 ret = MillerRabinPrimeVerify(rnd, 0, opt, cb);
564 time++;
565 } while (ret != CRYPT_SUCCESS);
566
567 OptimizerEnd(opt);
568 return BN_Copy(r, rnd);
569 }
570 #endif /* HITLS_CRYPTO_BN_PRIME */
571