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
47BIGNUM *
48BN_new(void)
49{
50    heim_integer *hi;
51    hi = calloc(1, sizeof(*hi));
52    return (BIGNUM *)hi;
53}
54
55void
56BN_free(BIGNUM *bn)
57{
58    BN_clear(bn);
59    free(bn);
60}
61
62void
63BN_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
73void
74BN_clear_free(BIGNUM *bn)
75{
76    BN_free(bn);
77}
78
79BIGNUM *
80BN_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 */
95int
96BN_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
114int
115BN_num_bytes(const BIGNUM *bn)
116{
117    return ((const heim_integer *)bn)->length;
118}
119
120/*
121 * Ignore negative flag.
122 */
123
124BIGNUM *
125BN_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
152int
153BN_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
160int
161BN_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
193char *
194BN_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
216int
217BN_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
223void
224BN_set_negative(BIGNUM *bn, int flag)
225{
226    ((heim_integer *)bn)->negative = (flag ? 1 : 0);
227}
228
229int
230BN_is_negative(const BIGNUM *bn)
231{
232    return ((const heim_integer *)bn)->negative ? 1 : 0;
233}
234
235static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
236
237int
238BN_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
249int
250BN_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
271int
272BN_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
285int
286BN_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
305unsigned long
306BN_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
320int
321BN_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
370int
371BN_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
426void
427BN_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
434int
435BN_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
446struct 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
459BN_CTX *
460BN_CTX_new(void)
461{
462    struct BN_CTX *c;
463    c = calloc(1, sizeof(*c));
464    return c;
465}
466
467void
468BN_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
477BIGNUM *
478BN_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
499void
500BN_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
513void
514BN_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