1 /*
2 * Copyright (c) 2022-2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #include <stdlib.h>
16 #include "hvb_crypto.h"
17 #include "hvb_util.h"
18 #include "hvb_rsa.h"
19
20 enum {
21 RESULT_OK = 0,
22 ERROR_MEMORY_EMPTY,
23 ERROR_MEMORY_NO_ENOUGH,
24 ERROR_WORDLEN_ZERO,
25 };
26
27 #ifndef __WORDSIZE
28 #if defined(__LP64__)
29 #define __WORDSIZE 64
30 #elif defined(__LP32__)
31 #define __WORDSIZE 32
32 #else
33 #error "not support word size "
34 #endif
35 #endif
36
37 #define WORD_BYTE_SIZE sizeof(unsigned long)
38 #define WORD_BIT_SIZE (WORD_BYTE_SIZE * 8)
39 #define WORD_BIT_MASK (((1UL << WORD_BIT_SIZE) - 1))
40 #define byte2bit(byte) ((byte) << 3)
41 #define SWORD_BIT_SIZE (WORD_BIT_SIZE / 2)
42 #define SWORD_BIT_MASK ((1UL << SWORD_BIT_SIZE) - 1)
43
lin_clear(struct long_int_num * p_a)44 static void lin_clear(struct long_int_num *p_a)
45 {
46 hvb_memset(p_a->data_mem, 0, p_a->mem_size);
47 }
48
lin_copy(struct long_int_num * p_src,struct long_int_num * p_dst)49 static int lin_copy(struct long_int_num *p_src, struct long_int_num *p_dst)
50 {
51 if (p_src->valid_word_len > p_dst->mem_size) {
52 return ERROR_MEMORY_NO_ENOUGH;
53 }
54
55 hvb_memcpy(p_dst->p_uint, p_src->p_uint, p_src->valid_word_len * WORD_BYTE_SIZE);
56
57 p_dst->valid_word_len = p_src->valid_word_len;
58
59 return RESULT_OK;
60 }
61
lin_compare(struct long_int_num * p_a,struct long_int_num * p_b)62 static int lin_compare(struct long_int_num *p_a, struct long_int_num *p_b)
63 {
64 int i;
65
66 if (p_a->valid_word_len != p_b->valid_word_len) {
67 return p_a->valid_word_len - p_b->valid_word_len;
68 }
69
70 for (i = p_a->valid_word_len - 1; i >= 0; --i) {
71 if (p_a->p_uint[i] != p_b->p_uint[i]) {
72 if (p_a->p_uint[i] > p_b->p_uint[i]) {
73 return 1;
74 }
75 return -1;
76 }
77 }
78 return 0;
79 }
80
lin_calloc(struct long_int_num * p_long_int,uint32_t word_len)81 static int lin_calloc(struct long_int_num *p_long_int, uint32_t word_len)
82 {
83 unsigned long *p_data = NULL;
84
85 if (word_len == 0) {
86 return ERROR_WORDLEN_ZERO;
87 }
88 p_data = hvb_malloc(word_len * WORD_BYTE_SIZE);
89 if (p_data == NULL) {
90 return ERROR_MEMORY_EMPTY;
91 }
92
93 hvb_memset(p_data, 0, word_len * WORD_BYTE_SIZE);
94
95 p_long_int->data_mem = p_data;
96 p_long_int->mem_size = word_len * WORD_BYTE_SIZE;
97 p_long_int->p_uint = p_data;
98 p_long_int->valid_word_len = 0;
99
100 return RESULT_OK;
101 }
102
lin_create(uint32_t word_len)103 struct long_int_num *lin_create(uint32_t word_len)
104 {
105 struct long_int_num *p_res = NULL;
106
107 p_res = hvb_malloc(sizeof(struct long_int_num));
108 if (p_res == NULL) {
109 return NULL;
110 }
111
112 if (lin_calloc(p_res, word_len) > 0) {
113 hvb_free(p_res);
114 return NULL;
115 }
116 p_res->valid_word_len = 0;
117 return p_res;
118 }
119
lin_free(struct long_int_num * p_long_int)120 void lin_free(struct long_int_num *p_long_int)
121 {
122 if (!p_long_int) {
123 return;
124 }
125 if (p_long_int->p_uint != NULL) {
126 hvb_free(p_long_int->data_mem);
127 p_long_int->p_uint = NULL;
128 }
129 hvb_free(p_long_int);
130
131 return;
132 }
133
lin_update_valid_len(struct long_int_num * p_a)134 void lin_update_valid_len(struct long_int_num *p_a)
135 {
136 unsigned long *p_data = NULL;
137 uint32_t i;
138
139 if (!p_a) {
140 return;
141 }
142
143 p_data = p_a->p_uint + p_a->valid_word_len - 1;
144 for (i = 0; i < p_a->valid_word_len; ++i) {
145 if (*p_data != 0) {
146 break;
147 }
148 --p_data;
149 }
150 p_a->valid_word_len -= i;
151 }
152
lin_mul_word(unsigned long a,unsigned long b,unsigned long * res_hi,unsigned long * res_low)153 static void lin_mul_word(unsigned long a, unsigned long b, unsigned long *res_hi, unsigned long *res_low)
154 {
155 #if defined(__aarch64__)
156 unsigned long hi = 0;
157 *res_low = a * b;
158 __asm__ volatile ("umulh %0, %1, %2" : "+r"(hi) : "r"(a), "r"(b) :);
159 *res_hi = hi;
160 #else
161
162 #if defined(__uint128_t)
163 #if __WORDSIZE == 32
164 unsigned long long aa;
165 #elif __WORDSIZE == 64
166 __uint128_t aa, bb;
167 #else
168 #error "not support word size "
169 #endif
170 aa = a;
171 bb = b;
172 aa = aa * bb;
173 *res_hi = aa >> WORD_BIT_SIZE;
174 *res_low = aa & WORD_BIT_MASK;
175 #else
176 unsigned long a_h, a_l;
177 unsigned long b_h, b_l;
178 unsigned long res_h, res_l;
179 unsigned long c, t;
180 a_h = a >> SWORD_BIT_SIZE;
181 a_l = a & SWORD_BIT_MASK;
182 b_h = b >> SWORD_BIT_SIZE;
183 b_l = b & SWORD_BIT_MASK;
184
185 res_h = a_h * b_h;
186 res_l = a_l * b_l;
187
188 c = a_h * b_l;
189 res_h += c >> SWORD_BIT_SIZE;
190 t = res_l;
191 res_l += c << SWORD_BIT_SIZE;
192 res_h += t > res_l;
193
194 c = a_l * b_h;
195 res_h += c >> SWORD_BIT_SIZE;
196 t = res_l;
197 res_l += c << SWORD_BIT_SIZE;
198 res_h += t > res_l;
199 *res_hi = res_h;
200 *res_low = res_l;
201 #endif
202 #endif
203 }
204
lin_sub(struct long_int_num * p_a,struct long_int_num * p_b)205 static void lin_sub(struct long_int_num *p_a, struct long_int_num *p_b)
206 {
207 uint32_t i;
208 unsigned long c;
209 unsigned long t;
210
211 c = 0;
212 for (i = 0; i < p_b->valid_word_len; ++i) {
213 t = p_a->p_uint[i] < c;
214 p_a->p_uint[i] = p_a->p_uint[i] - c;
215
216 c = (p_a->p_uint[i] < p_b->p_uint[i]) + t;
217 p_a->p_uint[i] = p_a->p_uint[i] - p_b->p_uint[i];
218 }
219 for (; i < p_a->valid_word_len && c; ++i) {
220 t = p_a->p_uint[i] < c;
221 p_a->p_uint[i] = p_a->p_uint[i] - c;
222 c = t;
223 }
224 lin_update_valid_len(p_a);
225 }
226
227 #define dword_add_word(a, b, r) \
228 do { \
229 r##_l = a##_l + (b); \
230 r##_h = a##_h + (r##_l < (b)); \
231 } while (0)
232
montgomery_mul_add(struct long_int_num * p_a,unsigned long b,struct long_int_num * p_n,unsigned long n_n0_i,struct long_int_num * p_res)233 static void montgomery_mul_add(struct long_int_num *p_a, unsigned long b, struct long_int_num *p_n,
234 unsigned long n_n0_i, struct long_int_num *p_res)
235 {
236 unsigned long x_h, x_l;
237 unsigned long d0;
238 unsigned long y_h, y_l;
239 unsigned long t_h, t_l;
240 unsigned long *p_ad = p_a->p_uint;
241 unsigned long *p_nd = p_n->p_uint;
242 unsigned long *p_rd = p_res->p_uint;
243 uint32_t i;
244
245 lin_mul_word(p_a->p_uint[0], b, &x_h, &x_l);
246
247 dword_add_word(x, p_rd[0], x);
248
249 d0 = x_l * n_n0_i;
250
251 lin_mul_word(d0, p_nd[0], &y_h, &y_l);
252 dword_add_word(y, x_l, y);
253
254 for (i = 1; i < p_a->valid_word_len; ++i) {
255 lin_mul_word(p_ad[i], b, &t_h, &t_l);
256 dword_add_word(t, p_rd[i], t);
257 dword_add_word(t, x_h, x);
258
259 lin_mul_word(d0, p_nd[i], &t_h, &t_l);
260 dword_add_word(t, x_l, t);
261 dword_add_word(t, y_h, y);
262
263 p_rd[i - 1] = y_l;
264 }
265
266 p_rd[i - 1] = x_h + y_h;
267
268 p_res->valid_word_len = p_n->valid_word_len;
269 if (p_rd[i - 1] < x_h) {
270 lin_sub(p_res, p_n);
271 }
272 }
273
montgomery_mod_mul(struct long_int_num * p_a,struct long_int_num * p_b,struct long_int_num * p_n,unsigned long n_n0_i,struct long_int_num * p_res)274 static void montgomery_mod_mul(struct long_int_num *p_a, struct long_int_num *p_b, struct long_int_num *p_n,
275 unsigned long n_n0_i, struct long_int_num *p_res)
276 {
277 uint32_t i;
278
279 lin_clear(p_res);
280
281 for (i = 0; i < p_b->valid_word_len; ++i) {
282 montgomery_mul_add(p_a, p_b->p_uint[i], p_n, n_n0_i, p_res);
283 }
284 }
285
montgomery_mod_exp(struct long_int_num * p_m,struct long_int_num * p_n,unsigned long n_n0_i,struct long_int_num * p_rr,uint32_t exp)286 struct long_int_num *montgomery_mod_exp(struct long_int_num *p_m, struct long_int_num *p_n, unsigned long n_n0_i,
287 struct long_int_num *p_rr, uint32_t exp)
288 {
289 struct long_int_num *p_res = NULL;
290 struct long_int_num *p_mr = NULL;
291 struct long_int_num *p_square = NULL;
292 int i;
293 if ((exp & 1UL) == 0) {
294 goto fail_final;
295 }
296
297 p_mr = lin_create(p_n->valid_word_len);
298 if (p_mr == NULL) {
299 goto fail_final;
300 }
301
302 p_square = lin_create(p_n->valid_word_len);
303 if (p_square == NULL) {
304 goto fail_final;
305 }
306
307 p_res = lin_create(p_n->valid_word_len);
308 if (p_res == NULL) {
309 goto fail_final;
310 }
311
312 montgomery_mod_mul(p_m, p_rr, p_n, n_n0_i, p_mr);
313 i = byte2bit(sizeof(exp)) - 1;
314 for (; i >= 0; --i) {
315 if (exp & (1UL << i)) {
316 break;
317 }
318 }
319
320 lin_copy(p_mr, p_res);
321
322 for (--i; i > 0; --i) {
323 montgomery_mod_mul(p_res, p_res, p_n, n_n0_i, p_square);
324 if (exp & (1UL << i)) {
325 montgomery_mod_mul(p_mr, p_square, p_n, n_n0_i, p_res);
326 } else {
327 lin_copy(p_square, p_res);
328 }
329 }
330 montgomery_mod_mul(p_res, p_res, p_n, n_n0_i, p_square);
331 montgomery_mod_mul(p_m, p_square, p_n, n_n0_i, p_res);
332
333 if (lin_compare(p_res, p_n) >= 0) {
334 lin_sub(p_res, p_n);
335 }
336
337 fail_final:
338 lin_free(p_mr);
339 lin_free(p_square);
340
341 return p_res;
342 }
343
lin_get_bitlen(struct long_int_num * p_a)344 int lin_get_bitlen(struct long_int_num *p_a)
345 {
346 int i;
347 int bit_len;
348 unsigned long *p_data = NULL;
349 unsigned long value;
350
351 if (!p_a) {
352 return 0;
353 }
354 p_data = p_a->p_uint;
355 for (i = p_a->valid_word_len - 1; i >= 0; --i) {
356 if (p_data[i] != 0) {
357 break;
358 }
359 }
360
361 bit_len = (i + 1) * WORD_BIT_SIZE;
362
363 if (bit_len == 0) {
364 return 0;
365 }
366
367 for (value = p_data[i]; ((signed long)value) > 0; value = value << 1) {
368 --bit_len;
369 }
370
371 return bit_len;
372 }
373