1 /* $NetBSD: bn.c,v 1.3 2023/06/19 21:41:43 christos Exp $ */
2
3 /*
4 * Copyright (c) 2006 Kungliga Tekniska Högskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * 3. Neither the name of the Institute nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 #include <config.h>
37 #include <krb5/roken.h>
38
39 #include <krb5/krb5-types.h>
40 #include <krb5/rfc2459_asn1.h> /* XXX */
41 #include <krb5/der.h>
42
43 #include <bn.h>
44 #include <rand.h>
45 #include <krb5/hex.h>
46
47 BIGNUM *
BN_new(void)48 BN_new(void)
49 {
50 heim_integer *hi;
51 hi = calloc(1, sizeof(*hi));
52 return (BIGNUM *)hi;
53 }
54
55 void
BN_free(BIGNUM * bn)56 BN_free(BIGNUM *bn)
57 {
58 BN_clear(bn);
59 free(bn);
60 }
61
62 void
BN_clear(BIGNUM * bn)63 BN_clear(BIGNUM *bn)
64 {
65 heim_integer *hi = (heim_integer *)bn;
66 if (hi->data) {
67 memset(hi->data, 0, hi->length);
68 free(hi->data);
69 }
70 memset(hi, 0, sizeof(*hi));
71 }
72
73 void
BN_clear_free(BIGNUM * bn)74 BN_clear_free(BIGNUM *bn)
75 {
76 BN_free(bn);
77 }
78
79 BIGNUM *
BN_dup(const BIGNUM * bn)80 BN_dup(const BIGNUM *bn)
81 {
82 BIGNUM *b = BN_new();
83 if (der_copy_heim_integer((const heim_integer *)bn, (heim_integer *)b)) {
84 BN_free(b);
85 return NULL;
86 }
87 return b;
88 }
89
90 /*
91 * If the caller really want to know the number of bits used, subtract
92 * one from the length, multiply by 8, and then lookup in the table
93 * how many bits the hightest byte uses.
94 */
95 int
BN_num_bits(const BIGNUM * bn)96 BN_num_bits(const BIGNUM *bn)
97 {
98 static unsigned char num2bits[256] = {
99 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
100 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
101 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
102 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
103 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
107 };
108 const heim_integer *i = (const void *)bn;
109 if (i->length == 0)
110 return 0;
111 return (i->length - 1) * 8 + num2bits[((unsigned char *)i->data)[0]];
112 }
113
114 int
BN_num_bytes(const BIGNUM * bn)115 BN_num_bytes(const BIGNUM *bn)
116 {
117 return ((const heim_integer *)bn)->length;
118 }
119
120 /*
121 * Ignore negative flag.
122 */
123
124 BIGNUM *
BN_bin2bn(const void * s,int len,BIGNUM * bn)125 BN_bin2bn(const void *s, int len, BIGNUM *bn)
126 {
127 heim_integer *hi = (void *)bn;
128
129 if (len < 0)
130 return NULL;
131
132 if (hi == NULL) {
133 hi = (heim_integer *)BN_new();
134 if (hi == NULL)
135 return NULL;
136 }
137 if (hi->data)
138 BN_clear((BIGNUM *)hi);
139 hi->negative = 0;
140 hi->data = malloc(len);
141 if (hi->data == NULL && len != 0) {
142 if (bn == NULL)
143 BN_free((BIGNUM *)hi);
144 return NULL;
145 }
146 hi->length = len;
147 if (len)
148 memcpy(hi->data, s, len);
149 return (BIGNUM *)hi;
150 }
151
152 int
BN_bn2bin(const BIGNUM * bn,void * to)153 BN_bn2bin(const BIGNUM *bn, void *to)
154 {
155 const heim_integer *hi = (const void *)bn;
156 memcpy(to, hi->data, hi->length);
157 return hi->length;
158 }
159
160 int
BN_hex2bn(BIGNUM ** bnp,const char * in)161 BN_hex2bn(BIGNUM **bnp, const char *in)
162 {
163 int negative;
164 ssize_t ret;
165 size_t len;
166 void *data;
167
168 len = strlen(in);
169 data = malloc(len);
170 if (data == NULL)
171 return 0;
172
173 if (*in == '-') {
174 negative = 1;
175 in++;
176 } else
177 negative = 0;
178
179 ret = hex_decode(in, data, len);
180 if (ret < 0) {
181 free(data);
182 return 0;
183 }
184
185 *bnp = BN_bin2bn(data, ret, NULL);
186 free(data);
187 if (*bnp == NULL)
188 return 0;
189 BN_set_negative(*bnp, negative);
190 return 1;
191 }
192
193 char *
BN_bn2hex(const BIGNUM * bn)194 BN_bn2hex(const BIGNUM *bn)
195 {
196 ssize_t ret;
197 size_t len;
198 void *data;
199 char *str;
200
201 len = BN_num_bytes(bn);
202 data = malloc(len);
203 if (data == NULL)
204 return 0;
205
206 len = BN_bn2bin(bn, data);
207
208 ret = hex_encode(data, len, &str);
209 free(data);
210 if (ret < 0)
211 return 0;
212
213 return str;
214 }
215
216 int
BN_cmp(const BIGNUM * bn1,const BIGNUM * bn2)217 BN_cmp(const BIGNUM *bn1, const BIGNUM *bn2)
218 {
219 return der_heim_integer_cmp((const heim_integer *)bn1,
220 (const heim_integer *)bn2);
221 }
222
223 void
BN_set_negative(BIGNUM * bn,int flag)224 BN_set_negative(BIGNUM *bn, int flag)
225 {
226 ((heim_integer *)bn)->negative = (flag ? 1 : 0);
227 }
228
229 int
BN_is_negative(const BIGNUM * bn)230 BN_is_negative(const BIGNUM *bn)
231 {
232 return ((const heim_integer *)bn)->negative ? 1 : 0;
233 }
234
235 static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
236
237 int
BN_is_bit_set(const BIGNUM * bn,int bit)238 BN_is_bit_set(const BIGNUM *bn, int bit)
239 {
240 heim_integer *hi = (heim_integer *)bn;
241 unsigned char *p = hi->data;
242
243 if ((bit / 8) >= hi->length || hi->length == 0)
244 return 0;
245
246 return p[hi->length - 1 - (bit / 8)] & is_set[bit % 8];
247 }
248
249 int
BN_set_bit(BIGNUM * bn,int bit)250 BN_set_bit(BIGNUM *bn, int bit)
251 {
252 heim_integer *hi = (heim_integer *)bn;
253 unsigned char *p;
254
255 if ((bit / 8) > hi->length || hi->length == 0) {
256 size_t len = bit == 0 ? 1 : (bit + 7) / 8;
257 void *d = realloc(hi->data, len);
258 if (d == NULL)
259 return 0;
260 hi->data = d;
261 p = hi->data;
262 memset(&p[hi->length], 0, len);
263 hi->length = len;
264 } else
265 p = hi->data;
266
267 p[hi->length - 1 - (bit / 8)] |= is_set[bit % 8];
268 return 1;
269 }
270
271 int
BN_clear_bit(BIGNUM * bn,int bit)272 BN_clear_bit(BIGNUM *bn, int bit)
273 {
274 heim_integer *hi = (heim_integer *)bn;
275 unsigned char *p = hi->data;
276
277 if ((bit / 8) > hi->length || hi->length == 0)
278 return 0;
279
280 p[hi->length - 1 - (bit / 8)] &= (unsigned char)(~(is_set[bit % 8]));
281
282 return 1;
283 }
284
285 int
BN_set_word(BIGNUM * bn,unsigned long num)286 BN_set_word(BIGNUM *bn, unsigned long num)
287 {
288 unsigned char p[sizeof(num)];
289 unsigned long num2;
290 int i, len;
291
292 for (num2 = num, i = 0; num2 > 0; i++)
293 num2 = num2 >> 8;
294
295 len = i;
296 for (; i > 0; i--) {
297 p[i - 1] = (num & 0xff);
298 num = num >> 8;
299 }
300
301 bn = BN_bin2bn(p, len, bn);
302 return bn != NULL;
303 }
304
305 unsigned long
BN_get_word(const BIGNUM * bn)306 BN_get_word(const BIGNUM *bn)
307 {
308 heim_integer *hi = (heim_integer *)bn;
309 unsigned long num = 0;
310 int i;
311
312 if (hi->negative || hi->length > sizeof(num))
313 return ULONG_MAX;
314
315 for (i = 0; i < hi->length; i++)
316 num = ((unsigned char *)hi->data)[i] | (num << 8);
317 return num;
318 }
319
320 int
BN_rand(BIGNUM * bn,int bits,int top,int bottom)321 BN_rand(BIGNUM *bn, int bits, int top, int bottom)
322 {
323 size_t len = (bits + 7) / 8;
324 heim_integer *i = (heim_integer *)bn;
325
326 BN_clear(bn);
327
328 i->negative = 0;
329 i->data = malloc(len);
330 if (i->data == NULL && len != 0)
331 return 0;
332 i->length = len;
333
334 if (RAND_bytes(i->data, i->length) != 1) {
335 free(i->data);
336 i->data = NULL;
337 return 0;
338 }
339
340 {
341 size_t j = len * 8;
342 while(j > bits) {
343 BN_clear_bit(bn, j - 1);
344 j--;
345 }
346 }
347
348 if (top == -1) {
349 ;
350 } else if (top == 0 && bits > 0) {
351 BN_set_bit(bn, bits - 1);
352 } else if (top == 1 && bits > 1) {
353 BN_set_bit(bn, bits - 1);
354 BN_set_bit(bn, bits - 2);
355 } else {
356 BN_clear(bn);
357 return 0;
358 }
359
360 if (bottom && bits > 0)
361 BN_set_bit(bn, 0);
362
363 return 1;
364 }
365
366 /*
367 *
368 */
369
370 int
BN_uadd(BIGNUM * res,const BIGNUM * a,const BIGNUM * b)371 BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b)
372 {
373 const heim_integer *ai = (const heim_integer *)a;
374 const heim_integer *bi = (const heim_integer *)b;
375 const unsigned char *ap, *bp;
376 unsigned char *cp;
377 heim_integer ci;
378 int carry = 0;
379 ssize_t len;
380
381 if (ai->negative && bi->negative)
382 return 0;
383 if (ai->length < bi->length) {
384 const heim_integer *si = bi;
385 bi = ai; ai = si;
386 }
387
388 ci.negative = 0;
389 ci.length = ai->length + 1;
390 ci.data = malloc(ci.length);
391 if (ci.data == NULL)
392 return 0;
393
394 ap = &((const unsigned char *)ai->data)[ai->length - 1];
395 bp = &((const unsigned char *)bi->data)[bi->length - 1];
396 cp = &((unsigned char *)ci.data)[ci.length - 1];
397
398 for (len = bi->length; len > 0; len--) {
399 carry = *ap + *bp + carry;
400 *cp = carry & 0xff;
401 carry = (carry & ~0xff) ? 1 : 0;
402 ap--; bp--; cp--;
403 }
404 for (len = ai->length - bi->length; len > 0; len--) {
405 carry = *ap + carry;
406 *cp = carry & 0xff;
407 carry = (carry & ~0xff) ? 1 : 0;
408 ap--; cp--;
409 }
410 if (!carry)
411 memmove(cp, cp + 1, --ci.length);
412 else
413 *cp = carry;
414
415 BN_clear(res);
416 *((heim_integer *)res) = ci;
417
418 return 1;
419 }
420
421
422 /*
423 * Callback when doing slow generation of numbers, like primes.
424 */
425
426 void
BN_GENCB_set(BN_GENCB * gencb,int (* cb_2)(int,int,BN_GENCB *),void * ctx)427 BN_GENCB_set(BN_GENCB *gencb, int (*cb_2)(int, int, BN_GENCB *), void *ctx)
428 {
429 gencb->ver = 2;
430 gencb->cb.cb_2 = cb_2;
431 gencb->arg = ctx;
432 }
433
434 int
BN_GENCB_call(BN_GENCB * cb,int a,int b)435 BN_GENCB_call(BN_GENCB *cb, int a, int b)
436 {
437 if (cb == NULL || cb->cb.cb_2 == NULL)
438 return 1;
439 return cb->cb.cb_2(a, b, cb);
440 }
441
442 /*
443 *
444 */
445
446 struct BN_CTX {
447 struct {
448 BIGNUM **val;
449 size_t used;
450 size_t len;
451 } bn;
452 struct {
453 size_t *val;
454 size_t used;
455 size_t len;
456 } stack;
457 };
458
459 BN_CTX *
BN_CTX_new(void)460 BN_CTX_new(void)
461 {
462 struct BN_CTX *c;
463 c = calloc(1, sizeof(*c));
464 return c;
465 }
466
467 void
BN_CTX_free(BN_CTX * c)468 BN_CTX_free(BN_CTX *c)
469 {
470 size_t i;
471 for (i = 0; i < c->bn.len; i++)
472 BN_free(c->bn.val[i]);
473 free(c->bn.val);
474 free(c->stack.val);
475 }
476
477 BIGNUM *
BN_CTX_get(BN_CTX * c)478 BN_CTX_get(BN_CTX *c)
479 {
480 if (c->bn.used == c->bn.len) {
481 void *ptr;
482 size_t i;
483 c->bn.len += 16;
484 ptr = realloc(c->bn.val, c->bn.len * sizeof(c->bn.val[0]));
485 if (ptr == NULL)
486 return NULL;
487 c->bn.val = ptr;
488 for (i = c->bn.used; i < c->bn.len; i++) {
489 c->bn.val[i] = BN_new();
490 if (c->bn.val[i] == NULL) {
491 c->bn.len = i;
492 return NULL;
493 }
494 }
495 }
496 return c->bn.val[c->bn.used++];
497 }
498
499 void
BN_CTX_start(BN_CTX * c)500 BN_CTX_start(BN_CTX *c)
501 {
502 if (c->stack.used == c->stack.len) {
503 void *ptr;
504 c->stack.len += 16;
505 ptr = realloc(c->stack.val, c->stack.len * sizeof(c->stack.val[0]));
506 if (ptr == NULL)
507 abort();
508 c->stack.val = ptr;
509 }
510 c->stack.val[c->stack.used++] = c->bn.used;
511 }
512
513 void
BN_CTX_end(BN_CTX * c)514 BN_CTX_end(BN_CTX *c)
515 {
516 const size_t prev = c->stack.val[c->stack.used - 1];
517 size_t i;
518
519 if (c->stack.used == 0)
520 abort();
521
522 for (i = prev; i < c->bn.used; i++)
523 BN_clear(c->bn.val[i]);
524
525 c->stack.used--;
526 c->bn.used = prev;
527 }
528
529