/src/boringssl/crypto/bn/convert.cc
Line | Count | Source |
1 | | // Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. |
2 | | // |
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 | | // https://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 <openssl/bn.h> |
16 | | |
17 | | #include <assert.h> |
18 | | #include <ctype.h> |
19 | | #include <limits.h> |
20 | | #include <stdio.h> |
21 | | |
22 | | #include <algorithm> |
23 | | |
24 | | #include <openssl/bio.h> |
25 | | #include <openssl/bytestring.h> |
26 | | #include <openssl/err.h> |
27 | | #include <openssl/mem.h> |
28 | | |
29 | | #include "../fipsmodule/bn/internal.h" |
30 | | |
31 | | |
32 | | using namespace bssl; |
33 | | |
34 | 40.5k | int BN_bn2cbb_padded(CBB *out, size_t len, const BIGNUM *in) { |
35 | 40.5k | uint8_t *ptr; |
36 | 40.5k | return CBB_add_space(out, &ptr, len) && BN_bn2bin_padded(ptr, len, in); |
37 | 40.5k | } |
38 | | |
39 | | static const char hextable[] = "0123456789abcdef"; |
40 | | |
41 | 884 | char *BN_bn2hex(const BIGNUM *bn) { |
42 | 884 | int width = bn_minimal_width(bn); |
43 | 884 | char *buf = reinterpret_cast<char *>( |
44 | 884 | OPENSSL_malloc(1 /* leading '-' */ + 1 /* zero is non-empty */ + |
45 | 884 | width * BN_BYTES * 2 + 1 /* trailing NUL */)); |
46 | 884 | if (buf == nullptr) { |
47 | 0 | return nullptr; |
48 | 0 | } |
49 | | |
50 | 884 | char *p = buf; |
51 | 884 | if (bn->neg) { |
52 | 483 | *(p++) = '-'; |
53 | 483 | } |
54 | | |
55 | 884 | if (BN_is_zero(bn)) { |
56 | 0 | *(p++) = '0'; |
57 | 0 | } |
58 | | |
59 | 884 | int z = 0; |
60 | 6.09k | for (int i = width - 1; i >= 0; i--) { |
61 | 46.8k | for (int j = BN_BITS2 - 8; j >= 0; j -= 8) { |
62 | | // strip leading zeros |
63 | 41.6k | int v = ((int)(bn->d[i] >> (long)j)) & 0xff; |
64 | 41.6k | if (z || v != 0) { |
65 | 38.7k | *(p++) = hextable[v >> 4]; |
66 | 38.7k | *(p++) = hextable[v & 0x0f]; |
67 | 38.7k | z = 1; |
68 | 38.7k | } |
69 | 41.6k | } |
70 | 5.21k | } |
71 | 884 | *p = '\0'; |
72 | | |
73 | 884 | return buf; |
74 | 884 | } |
75 | | |
76 | | // decode_hex decodes `in_len` bytes of hex data from `in` and updates `bn`. |
77 | 0 | static int decode_hex(BIGNUM *bn, const char *in, int in_len) { |
78 | 0 | if (in_len > INT_MAX / 4) { |
79 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
80 | 0 | return 0; |
81 | 0 | } |
82 | | // `in_len` is the number of hex digits. |
83 | 0 | if (!bn_expand(bn, in_len * 4)) { |
84 | 0 | return 0; |
85 | 0 | } |
86 | | |
87 | 0 | int i = 0; |
88 | 0 | while (in_len > 0) { |
89 | | // Decode one `BN_ULONG` at a time. |
90 | 0 | int todo = BN_BYTES * 2; |
91 | 0 | if (todo > in_len) { |
92 | 0 | todo = in_len; |
93 | 0 | } |
94 | |
|
95 | 0 | BN_ULONG word = 0; |
96 | 0 | int j; |
97 | 0 | for (j = todo; j > 0; j--) { |
98 | 0 | uint8_t hex = 0; |
99 | 0 | if (!OPENSSL_fromxdigit(&hex, in[in_len - j])) { |
100 | | // This shouldn't happen. The caller checks `OPENSSL_isxdigit`. |
101 | 0 | assert(0); |
102 | 0 | } |
103 | 0 | word = (word << 4) | hex; |
104 | 0 | } |
105 | | |
106 | 0 | bn->d[i++] = word; |
107 | 0 | in_len -= todo; |
108 | 0 | } |
109 | 0 | assert(i <= bn->dmax); |
110 | 0 | bn->width = i; |
111 | 0 | return 1; |
112 | 0 | } |
113 | | |
114 | | // decode_dec decodes `in_len` bytes of decimal data from `in` and updates `bn`. |
115 | 0 | static int decode_dec(BIGNUM *bn, const char *in, int in_len) { |
116 | 0 | int i, j; |
117 | 0 | BN_ULONG l = 0; |
118 | | |
119 | | // Decode `BN_DEC_NUM` digits at a time. |
120 | 0 | j = BN_DEC_NUM - (in_len % BN_DEC_NUM); |
121 | 0 | if (j == BN_DEC_NUM) { |
122 | 0 | j = 0; |
123 | 0 | } |
124 | 0 | l = 0; |
125 | 0 | for (i = 0; i < in_len; i++) { |
126 | 0 | l *= 10; |
127 | 0 | l += in[i] - '0'; |
128 | 0 | if (++j == BN_DEC_NUM) { |
129 | 0 | if (!BN_mul_word(bn, BN_DEC_CONV) || !BN_add_word(bn, l)) { |
130 | 0 | return 0; |
131 | 0 | } |
132 | 0 | l = 0; |
133 | 0 | j = 0; |
134 | 0 | } |
135 | 0 | } |
136 | 0 | return 1; |
137 | 0 | } |
138 | | |
139 | | typedef int (*decode_func)(BIGNUM *bn, const char *in, int in_len); |
140 | | typedef int (*char_test_func)(int c); |
141 | | |
142 | | static int bn_x2bn(BIGNUM **outp, const char *in, decode_func decode, |
143 | 0 | char_test_func want_char) { |
144 | 0 | BIGNUM *ret = nullptr; |
145 | 0 | int neg = 0, i; |
146 | 0 | int num; |
147 | |
|
148 | 0 | if (in == nullptr || *in == 0) { |
149 | 0 | return 0; |
150 | 0 | } |
151 | | |
152 | 0 | if (*in == '-') { |
153 | 0 | neg = 1; |
154 | 0 | in++; |
155 | 0 | } |
156 | |
|
157 | 0 | for (i = 0; want_char((unsigned char)in[i]) && i + neg < INT_MAX; i++) { |
158 | 0 | } |
159 | |
|
160 | 0 | num = i + neg; |
161 | 0 | if (outp == nullptr) { |
162 | 0 | return num; |
163 | 0 | } |
164 | | |
165 | | // in is the start of the hex digits, and it is 'i' long |
166 | 0 | if (*outp == nullptr) { |
167 | 0 | ret = BN_new(); |
168 | 0 | if (ret == nullptr) { |
169 | 0 | return 0; |
170 | 0 | } |
171 | 0 | } else { |
172 | 0 | ret = *outp; |
173 | 0 | BN_zero(ret); |
174 | 0 | } |
175 | | |
176 | 0 | if (!decode(ret, in, i)) { |
177 | 0 | goto err; |
178 | 0 | } |
179 | | |
180 | 0 | bn_set_minimal_width(ret); |
181 | 0 | if (!BN_is_zero(ret)) { |
182 | 0 | ret->neg = neg; |
183 | 0 | } |
184 | |
|
185 | 0 | *outp = ret; |
186 | 0 | return num; |
187 | | |
188 | 0 | err: |
189 | 0 | if (*outp == nullptr) { |
190 | 0 | BN_free(ret); |
191 | 0 | } |
192 | |
|
193 | 0 | return 0; |
194 | 0 | } |
195 | | |
196 | 0 | int BN_hex2bn(BIGNUM **outp, const char *in) { |
197 | 0 | return bn_x2bn(outp, in, decode_hex, OPENSSL_isxdigit); |
198 | 0 | } |
199 | | |
200 | 893 | char *BN_bn2dec(const BIGNUM *a) { |
201 | | // It is easier to print strings little-endian, so we assemble it in reverse |
202 | | // and fix at the end. |
203 | 893 | ScopedCBB cbb; |
204 | 893 | if (!CBB_init(cbb.get(), 16) || // |
205 | 893 | !CBB_add_u8(cbb.get(), 0 /* trailing NUL */)) { |
206 | 0 | return nullptr; |
207 | 0 | } |
208 | | |
209 | 893 | if (BN_is_zero(a)) { |
210 | 20 | if (!CBB_add_u8(cbb.get(), '0')) { |
211 | 0 | return nullptr; |
212 | 0 | } |
213 | 873 | } else { |
214 | 873 | UniquePtr<BIGNUM> copy(BN_dup(a)); |
215 | 873 | if (copy == nullptr) { |
216 | 0 | return nullptr; |
217 | 0 | } |
218 | | |
219 | 1.74k | while (!BN_is_zero(copy.get())) { |
220 | 873 | BN_ULONG word = BN_div_word(copy.get(), BN_DEC_CONV); |
221 | 873 | if (word == (BN_ULONG)-1) { |
222 | 0 | return nullptr; |
223 | 0 | } |
224 | | |
225 | 873 | const int add_leading_zeros = !BN_is_zero(copy.get()); |
226 | 4.58k | for (int i = 0; i < BN_DEC_NUM && (add_leading_zeros || word != 0); i++) { |
227 | 3.71k | if (!CBB_add_u8(cbb.get(), '0' + word % 10)) { |
228 | 0 | return nullptr; |
229 | 0 | } |
230 | 3.71k | word /= 10; |
231 | 3.71k | } |
232 | 873 | assert(word == 0); |
233 | 873 | } |
234 | 873 | } |
235 | | |
236 | 893 | if (BN_is_negative(a) && // |
237 | 525 | !CBB_add_u8(cbb.get(), '-')) { |
238 | 0 | return nullptr; |
239 | 0 | } |
240 | | |
241 | 893 | uint8_t *data; |
242 | 893 | size_t len; |
243 | 893 | if (!CBB_finish(cbb.get(), &data, &len)) { |
244 | 0 | return nullptr; |
245 | 0 | } |
246 | | |
247 | 893 | std::reverse(data, data + len); |
248 | 893 | return reinterpret_cast<char *>(data); |
249 | 893 | } |
250 | | |
251 | 0 | int BN_dec2bn(BIGNUM **outp, const char *in) { |
252 | 0 | return bn_x2bn(outp, in, decode_dec, OPENSSL_isdigit); |
253 | 0 | } |
254 | | |
255 | 0 | int BN_asc2bn(BIGNUM **outp, const char *in) { |
256 | 0 | const char *const orig_in = in; |
257 | 0 | if (*in == '-') { |
258 | 0 | in++; |
259 | 0 | } |
260 | |
|
261 | 0 | if (in[0] == '0' && (in[1] == 'X' || in[1] == 'x')) { |
262 | 0 | if (!BN_hex2bn(outp, in + 2)) { |
263 | 0 | return 0; |
264 | 0 | } |
265 | 0 | } else { |
266 | 0 | if (!BN_dec2bn(outp, in)) { |
267 | 0 | return 0; |
268 | 0 | } |
269 | 0 | } |
270 | | |
271 | 0 | if (*orig_in == '-' && !BN_is_zero(*outp)) { |
272 | 0 | (*outp)->neg = 1; |
273 | 0 | } |
274 | |
|
275 | 0 | return 1; |
276 | 0 | } |
277 | | |
278 | 0 | int BN_print(BIO *bp, const BIGNUM *a) { |
279 | 0 | if (a->neg && BIO_write(bp, "-", 1) != 1) { |
280 | 0 | return 0; |
281 | 0 | } |
282 | | |
283 | 0 | if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1) { |
284 | 0 | return 0; |
285 | 0 | } |
286 | | |
287 | 0 | int z = 0; |
288 | 0 | for (int i = bn_minimal_width(a) - 1; i >= 0; i--) { |
289 | 0 | for (int j = BN_BITS2 - 4; j >= 0; j -= 4) { |
290 | | // strip leading zeros |
291 | 0 | int v = ((int)(a->d[i] >> (long)j)) & 0x0f; |
292 | 0 | if (z || v != 0) { |
293 | 0 | if (BIO_write(bp, &hextable[v], 1) != 1) { |
294 | 0 | return 0; |
295 | 0 | } |
296 | 0 | z = 1; |
297 | 0 | } |
298 | 0 | } |
299 | 0 | } |
300 | 0 | return 1; |
301 | 0 | } |
302 | | |
303 | 0 | int BN_print_fp(FILE *fp, const BIGNUM *a) { |
304 | 0 | BIO *b = BIO_new_fp(fp, BIO_NOCLOSE); |
305 | 0 | if (b == nullptr) { |
306 | 0 | return 0; |
307 | 0 | } |
308 | | |
309 | 0 | int ret = BN_print(b, a); |
310 | 0 | BIO_free(b); |
311 | 0 | return ret; |
312 | 0 | } |
313 | | |
314 | | |
315 | 0 | size_t BN_bn2mpi(const BIGNUM *in, uint8_t *out) { |
316 | 0 | const size_t bits = BN_num_bits(in); |
317 | 0 | const size_t bytes = (bits + 7) / 8; |
318 | | // If the number of bits is a multiple of 8, i.e. if the MSB is set, |
319 | | // prefix with a zero byte. |
320 | 0 | int extend = 0; |
321 | 0 | if (bytes != 0 && (bits & 0x07) == 0) { |
322 | 0 | extend = 1; |
323 | 0 | } |
324 | |
|
325 | 0 | const size_t len = bytes + extend; |
326 | 0 | if (len < bytes || 4 + len < len || (len & 0xffffffff) != len) { |
327 | | // If we cannot represent the number then we emit zero as the interface |
328 | | // doesn't allow an error to be signalled. |
329 | 0 | if (out) { |
330 | 0 | OPENSSL_memset(out, 0, 4); |
331 | 0 | } |
332 | 0 | return 4; |
333 | 0 | } |
334 | | |
335 | 0 | if (out == nullptr) { |
336 | 0 | return 4 + len; |
337 | 0 | } |
338 | | |
339 | 0 | out[0] = len >> 24; |
340 | 0 | out[1] = len >> 16; |
341 | 0 | out[2] = len >> 8; |
342 | 0 | out[3] = len; |
343 | 0 | if (extend) { |
344 | 0 | out[4] = 0; |
345 | 0 | } |
346 | 0 | BN_bn2bin(in, out + 4 + extend); |
347 | 0 | if (in->neg && len > 0) { |
348 | 0 | out[4] |= 0x80; |
349 | 0 | } |
350 | 0 | return len + 4; |
351 | 0 | } |
352 | | |
353 | 0 | BIGNUM *BN_mpi2bn(const uint8_t *in, size_t len, BIGNUM *out) { |
354 | 0 | if (len < 4) { |
355 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING); |
356 | 0 | return nullptr; |
357 | 0 | } |
358 | 0 | const size_t in_len = ((size_t)in[0] << 24) | // |
359 | 0 | ((size_t)in[1] << 16) | // |
360 | 0 | ((size_t)in[2] << 8) | // |
361 | 0 | ((size_t)in[3]); |
362 | 0 | if (in_len != len - 4) { |
363 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING); |
364 | 0 | return nullptr; |
365 | 0 | } |
366 | | |
367 | 0 | int out_is_alloced = 0; |
368 | 0 | if (out == nullptr) { |
369 | 0 | out = BN_new(); |
370 | 0 | if (out == nullptr) { |
371 | 0 | return nullptr; |
372 | 0 | } |
373 | 0 | out_is_alloced = 1; |
374 | 0 | } |
375 | | |
376 | 0 | if (in_len == 0) { |
377 | 0 | BN_zero(out); |
378 | 0 | return out; |
379 | 0 | } |
380 | | |
381 | 0 | in += 4; |
382 | 0 | if (BN_bin2bn(in, in_len, out) == nullptr) { |
383 | 0 | if (out_is_alloced) { |
384 | 0 | BN_free(out); |
385 | 0 | } |
386 | 0 | return nullptr; |
387 | 0 | } |
388 | 0 | out->neg = ((*in) & 0x80) != 0; |
389 | 0 | if (out->neg) { |
390 | 0 | BN_clear_bit(out, BN_num_bits(out) - 1); |
391 | 0 | } |
392 | 0 | return out; |
393 | 0 | } |
394 | | |
395 | 0 | int BN_bn2binpad(const BIGNUM *in, uint8_t *out, int len) { |
396 | 0 | if (len < 0 || // |
397 | 0 | !BN_bn2bin_padded(out, (size_t)len, in)) { |
398 | 0 | return -1; |
399 | 0 | } |
400 | 0 | return len; |
401 | 0 | } |
402 | | |
403 | 0 | int BN_bn2lebinpad(const BIGNUM *in, uint8_t *out, int len) { |
404 | 0 | if (len < 0 || // |
405 | 0 | !BN_bn2le_padded(out, (size_t)len, in)) { |
406 | 0 | return -1; |
407 | 0 | } |
408 | 0 | return len; |
409 | 0 | } |