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 #if defined(HITLS_CRYPTO_CURVE_NISTP256_ASM) && defined(HITLS_CRYPTO_NIST_ECC_ACCELERATE)
18
19 #include <stdint.h>
20 #include "crypt_errno.h"
21 #include "crypt_bn.h"
22 #include "ecp_nistp256.h"
23 #include "crypt_ecc.h"
24 #include "ecc_local.h"
25 #include "bsl_err_internal.h"
26 #include "asm_ecp_nistp256.h"
27
28 static const Coord g_rrModOrder = {{
29 0x83244c95be79eea2,
30 0x4699799c49bd6fa6,
31 0x2845b2392b6bec59,
32 0x66e12d94f3d95620
33 }};
34
ECP256_ModOrderInvCheck(const ECC_Para * para,const BN_BigNum * r,const BN_BigNum * a)35 static int32_t ECP256_ModOrderInvCheck(const ECC_Para *para, const BN_BigNum *r, const BN_BigNum *a)
36 {
37 if (para == NULL || r == NULL || a == NULL) {
38 BSL_ERR_PUSH_ERROR(CRYPT_NULL_INPUT);
39 return CRYPT_NULL_INPUT;
40 }
41
42 if (para->id != CRYPT_ECC_NISTP256) {
43 BSL_ERR_PUSH_ERROR(CRYPT_ECC_POINT_ERR_CURVE_ID);
44 return CRYPT_ECC_POINT_ERR_CURVE_ID;
45 }
46
47 if (BN_IsZero(a)) {
48 BSL_ERR_PUSH_ERROR(CRYPT_ECC_INVERSE_INPUT_ZERO);
49 return CRYPT_ECC_INVERSE_INPUT_ZERO;
50 }
51
52 return CRYPT_SUCCESS;
53 }
54
Bn2CoordArray(const ECC_Para * para,Coord * aArr,const BN_BigNum * a)55 static int32_t Bn2CoordArray(const ECC_Para *para, Coord *aArr, const BN_BigNum *a)
56 {
57 int32_t ret = CRYPT_SUCCESS;
58 uint32_t bits = BN_Bits(para->n);
59 BN_Optimizer *opt = BN_OptimizerCreate();
60 BN_BigNum *aTemp = BN_Create(bits);
61 if (opt == NULL || aTemp == NULL) {
62 ret = CRYPT_MEM_ALLOC_FAIL;
63 BSL_ERR_PUSH_ERROR(ret);
64 goto EXIT;
65 }
66
67 if (BN_Cmp(a, para->n) >= 0) {
68 ret = BN_Mod(aTemp, a, para->n, opt);
69 if (ret != CRYPT_SUCCESS) {
70 BSL_ERR_PUSH_ERROR(ret);
71 goto EXIT;
72 }
73 if (BN_IsZero(aTemp)) { // If x and m are coprime, the module inverse cannot be obtained.
74 BSL_ERR_PUSH_ERROR(CRYPT_BN_ERR_NO_INVERSE);
75 ret = CRYPT_BN_ERR_NO_INVERSE;
76 goto EXIT;
77 }
78 } else {
79 ret = BN_Copy(aTemp, a);
80 if (ret != CRYPT_SUCCESS) {
81 BSL_ERR_PUSH_ERROR(ret);
82 goto EXIT;
83 }
84 }
85 (void)BN_BN2Array(aTemp, aArr->value, P256_SIZE);
86 EXIT:
87 BN_OptimizerDestroy(opt);
88 BN_Destroy(aTemp);
89 return ret;
90 }
91
92 // r = a^(-1) mod n, a cannot be 0
93 // a^(-1) mod n = a^(n-2) mod n
94 // n = 0xffffffff 00000000 ffffffff ffffffff bce6faad a7179e84 f3b9cac2 fc632551
95 // n-2 = 0xffffffff 00000000 ffffffff ffffffff bce6faad a7179e84 f3b9cac2 fc63254f
96 // Split the file into binary files as follows:
97 // 11111111111111111111111111111111---------0xffffffff
98 // 00000000000000000000000000000000---------0x00000000
99 // 11111111111111111111111111111111---------0xffffffff
100 // 11111111111111111111111111111111---------0xffffffff
101 // 101111 00 111 00 11 0 1111 10101 0 101 101
102 // 101 00 111 000 101111 00 1111 0 1 0000 1 00
103 // 1111 00 111 0 111 00 111 00 101 0 11 0000 10(1111): append four 1s
104 // (1111) 11 000 11 000 11 00 1 00 10101 00 1111
105 // To calculate the power of a, the exponent list is { 1, 10, 11, 101, 111, 1010, 1111, 10101, 101010, 101111, ffffffff}
106 // To calculate a^(0xffffffff), a^(0xffff) is required. The former requires a^(0xff), the latter requires a^(0x3f).
107 // The above is the optimal multiplication chain of a^(n-2)
108 // https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion
ECP256_ModOrderInv(const ECC_Para * para,BN_BigNum * r,const BN_BigNum * a)109 int32_t ECP256_ModOrderInv(const ECC_Para *para, BN_BigNum *r, const BN_BigNum *a)
110 {
111 int32_t ret = ECP256_ModOrderInvCheck(para, r, a);
112 if (ret != CRYPT_SUCCESS) {
113 return ret;
114 }
115 const Coord one = {{1}};
116 Coord aArr, res;
117 Coord table[14];
118 enum {
119 bin1 = 0, bin10, bin11, bin101, bin111, bin1010, bin1111,
120 bin10101, bin101010, bin101111, hex3f, hexff, hexffff, hexffffffff
121 };
122 static const uint8_t mulMap[26] = { // The lower 128 bits of n-2 can be split into 26 binary numbers.
123 bin101111, bin111, bin11, bin1111, bin10101, bin101,
124 bin101, bin101, bin111, bin101111, bin1111, bin1,
125 bin1, bin1111, bin111, bin111, bin111, bin101,
126 bin11, bin101111, bin11, bin11, bin11, bin1,
127 bin10101, bin1111
128 };
129 static const uint8_t sqrRep[26] = { // The lower 128 bits of n-2 can be split into 26 binary numbers.
130 6, 5, 4, 5, 5, 4,
131 3, 3, 5, 9, 6, 2,
132 5, 6, 5, 4, 5, 5,
133 3, 10, 2, 5, 5, 3,
134 7, 6
135 };
136
137 ret = Bn2CoordArray(para, &aArr, a);
138 if (ret != CRYPT_SUCCESS) {
139 return ret;
140 }
141
142 ECP256_OrdMul(&table[bin1], &aArr, &g_rrModOrder); // table[bin1] = a, to the field with Montgomery
143
144 ECP256_OrdSqr(&table[bin10], &table[bin1], 1); // table[bin10] = a^(0b10)
145 ECP256_OrdMul(&table[bin11], &table[bin1], &table[bin10]); // table[bin11] = a^(0b11)
146 ECP256_OrdMul(&table[bin101], &table[bin11], &table[bin10]); // table[bin101] = a^(0b101)
147 ECP256_OrdMul(&table[bin111], &table[bin101], &table[bin10]); // table[bin111] = a^(0b111)
148
149 ECP256_OrdSqr(&table[bin1010], &table[bin101], 1); // table[bin1010] = a^(0b1010)
150
151 ECP256_OrdMul(&table[bin1111], &table[bin1010], &table[bin101]); // table[bin1111] = a^(0b1111)
152
153 ECP256_OrdSqr(&table[bin10101], &table[bin1010], 1); // table[bin10101] = a^(0b10100)
154 ECP256_OrdMul(&table[bin10101], &table[bin10101], &table[bin1]); // table[bin10101] = a^(0b10101)
155
156 ECP256_OrdSqr(&table[bin101010], &table[bin10101], 1); // table[bin101010] = a^(0b101010)
157
158 ECP256_OrdMul(&table[bin101111], &table[bin101010], &table[bin101]); // table[bin101111] = a^(0b101111)
159
160 ECP256_OrdMul(&table[hex3f], &table[bin101010], &table[bin10101]); // table[hex3f] = a^(0b0011 1111) = a^(0x3f)
161
162 ECP256_OrdSqr(&table[hexff], &table[hex3f], 2); // left shift by 2 bits, table[hexff] = a^(0b1111 1100) = a^(0xfc)
163 ECP256_OrdMul(&table[hexff], &table[hexff], &table[bin11]); // table[hexff] = a^(0b1111 1111) = a^(0xff)
164
165 ECP256_OrdSqr(&table[hexffff], &table[hexff], 8); // left shift by 8 bits, table[hexffff] = a^(0xff00)
166 ECP256_OrdMul(&table[hexffff], &table[hexffff], &table[hexff]); // table[hexffff] = a^(0xffff)
167
168 // left shift by 16 bits, table[hexffffffff] = a^(0xffff0000)
169 ECP256_OrdSqr(&table[hexffffffff], &table[hexffff], 16);
170 ECP256_OrdMul(&table[hexffffffff], &table[hexffffffff], &table[hexffff]); // table[hexffffffff] = a^(0xffffffff)
171
172 ECP256_OrdSqr(&res, &table[hexffffffff], 64); // res = a^(0xffffffff 00000000 00000000), left shift by 64 bits
173 ECP256_OrdMul(&res, &res, &table[hexffffffff]); // res = a^(0xffffffff 00000000 ffffffff)
174
175 ECP256_OrdSqr(&res, &res, 32); // res = a^(0xffffffff 00000000 ffffffff 00000000), left shift by 32 bits
176 ECP256_OrdMul(&res, &res, &table[hexffffffff]); // res = a^(0xffffffff 00000000 ffffffff ffffffff)
177
178 for (uint32_t i = 0; i < sizeof(mulMap); i++) {
179 ECP256_OrdSqr(&res, &res, sqrRep[i]);
180 ECP256_OrdMul(&res, &res, &table[mulMap[i]]);
181 }
182
183 // Multiplied by 1 can be converted back to the normal real number field, which is equivalent to a reduce.
184 // For details, see Montgomery modular multiplication.
185 ECP256_OrdMul(&res, &res, &one);
186
187 (void)BN_Array2BN(r, res.value, P256_SIZE);
188 return ret;
189 }
190 #endif