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