1/*	$NetBSD: bn.c,v 1.1.1.1 2011/04/13 18:14:49 elric 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
38
39#include <stdio.h>
40#include <stdlib.h>
41#include <string.h>
42#include <limits.h>
43
44#include <krb5/krb5-types.h>
45#include <krb5/roken.h>
46#include <krb5/rfc2459_asn1.h> /* XXX */
47#include <krb5/der.h>
48
49#include <bn.h>
50#include <rand.h>
51#include <krb5/hex.h>
52
53BIGNUM *
54BN_new(void)
55{
56    heim_integer *hi;
57    hi = calloc(1, sizeof(*hi));
58    return (BIGNUM *)hi;
59}
60
61void
62BN_free(BIGNUM *bn)
63{
64    BN_clear(bn);
65    free(bn);
66}
67
68void
69BN_clear(BIGNUM *bn)
70{
71    heim_integer *hi = (heim_integer *)bn;
72    if (hi->data) {
73	memset(hi->data, 0, hi->length);
74	free(hi->data);
75    }
76    memset(hi, 0, sizeof(*hi));
77}
78
79void
80BN_clear_free(BIGNUM *bn)
81{
82    BN_free(bn);
83}
84
85BIGNUM *
86BN_dup(const BIGNUM *bn)
87{
88    BIGNUM *b = BN_new();
89    if (der_copy_heim_integer((const heim_integer *)bn, (heim_integer *)b)) {
90	BN_free(b);
91	return NULL;
92    }
93    return b;
94}
95
96/*
97 * If the caller really want to know the number of bits used, subtract
98 * one from the length, multiply by 8, and then lookup in the table
99 * how many bits the hightest byte uses.
100 */
101int
102BN_num_bits(const BIGNUM *bn)
103{
104    static unsigned char num2bits[256] = {
105	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,
106	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,
107	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,
108	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,
109	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,
110	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,
111	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,
112	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,
113    };
114    const heim_integer *i = (const void *)bn;
115    if (i->length == 0)
116	return 0;
117    return (i->length - 1) * 8 + num2bits[((unsigned char *)i->data)[0]];
118}
119
120int
121BN_num_bytes(const BIGNUM *bn)
122{
123    return ((const heim_integer *)bn)->length;
124}
125
126/*
127 * Ignore negative flag.
128 */
129
130BIGNUM *
131BN_bin2bn(const void *s, int len, BIGNUM *bn)
132{
133    heim_integer *hi = (void *)bn;
134
135    if (len < 0)
136	return NULL;
137
138    if (hi == NULL) {
139	hi = (heim_integer *)BN_new();
140	if (hi == NULL)
141	    return NULL;
142    }
143    if (hi->data)
144	BN_clear((BIGNUM *)hi);
145    hi->negative = 0;
146    hi->data = malloc(len);
147    if (hi->data == NULL && len != 0) {
148	if (bn == NULL)
149	    BN_free((BIGNUM *)hi);
150	return NULL;
151    }
152    hi->length = len;
153    memcpy(hi->data, s, len);
154    return (BIGNUM *)hi;
155}
156
157int
158BN_bn2bin(const BIGNUM *bn, void *to)
159{
160    const heim_integer *hi = (const void *)bn;
161    memcpy(to, hi->data, hi->length);
162    return hi->length;
163}
164
165int
166BN_hex2bn(BIGNUM **bnp, const char *in)
167{
168    int negative;
169    ssize_t ret;
170    size_t len;
171    void *data;
172
173    len = strlen(in);
174    data = malloc(len);
175    if (data == NULL)
176	return 0;
177
178    if (*in == '-') {
179	negative = 1;
180	in++;
181    } else
182	negative = 0;
183
184    ret = hex_decode(in, data, len);
185    if (ret < 0) {
186	free(data);
187	return 0;
188    }
189
190    *bnp = BN_bin2bn(data, ret, NULL);
191    free(data);
192    if (*bnp == NULL)
193	return 0;
194    BN_set_negative(*bnp, negative);
195    return 1;
196}
197
198char *
199BN_bn2hex(const BIGNUM *bn)
200{
201    ssize_t ret;
202    size_t len;
203    void *data;
204    char *str;
205
206    len = BN_num_bytes(bn);
207    data = malloc(len);
208    if (data == NULL)
209	return 0;
210
211    len = BN_bn2bin(bn, data);
212
213    ret = hex_encode(data, len, &str);
214    free(data);
215    if (ret < 0)
216	return 0;
217
218    return str;
219}
220
221int
222BN_cmp(const BIGNUM *bn1, const BIGNUM *bn2)
223{
224    return der_heim_integer_cmp((const heim_integer *)bn1,
225				(const heim_integer *)bn2);
226}
227
228void
229BN_set_negative(BIGNUM *bn, int flag)
230{
231    ((heim_integer *)bn)->negative = (flag ? 1 : 0);
232}
233
234int
235BN_is_negative(const BIGNUM *bn)
236{
237    return ((const heim_integer *)bn)->negative ? 1 : 0;
238}
239
240static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
241
242int
243BN_is_bit_set(const BIGNUM *bn, int bit)
244{
245    heim_integer *hi = (heim_integer *)bn;
246    unsigned char *p = hi->data;
247
248    if ((bit / 8) > hi->length || hi->length == 0)
249	return 0;
250
251    return p[hi->length - 1 - (bit / 8)] & is_set[bit % 8];
252}
253
254int
255BN_set_bit(BIGNUM *bn, int bit)
256{
257    heim_integer *hi = (heim_integer *)bn;
258    unsigned char *p;
259
260    if ((bit / 8) > hi->length || hi->length == 0) {
261	size_t len = (bit + 7) / 8;
262	void *d = realloc(hi->data, len);
263	if (d == NULL)
264	    return 0;
265	hi->data = d;
266	p = hi->data;
267	memset(&p[hi->length], 0, len);
268	hi->length = len;
269    } else
270	p = hi->data;
271
272    p[hi->length - 1 - (bit / 8)] |= is_set[bit % 8];
273    return 1;
274}
275
276int
277BN_clear_bit(BIGNUM *bn, int bit)
278{
279    heim_integer *hi = (heim_integer *)bn;
280    unsigned char *p = hi->data;
281
282    if ((bit / 8) > hi->length || hi->length == 0)
283	return 0;
284
285    p[hi->length - 1 - (bit / 8)] &= (unsigned char)(~(is_set[bit % 8]));
286
287    return 1;
288}
289
290int
291BN_set_word(BIGNUM *bn, unsigned long num)
292{
293    unsigned char p[sizeof(num)];
294    unsigned long num2;
295    int i, len;
296
297    for (num2 = num, i = 0; num2 > 0; i++)
298	num2 = num2 >> 8;
299
300    len = i;
301    for (; i > 0; i--) {
302	p[i - 1] = (num & 0xff);
303	num = num >> 8;
304    }
305
306    bn = BN_bin2bn(p, len, bn);
307    return bn != NULL;
308}
309
310unsigned long
311BN_get_word(const BIGNUM *bn)
312{
313    heim_integer *hi = (heim_integer *)bn;
314    unsigned long num = 0;
315    int i;
316
317    if (hi->negative || hi->length > sizeof(num))
318	return ULONG_MAX;
319
320    for (i = 0; i < hi->length; i++)
321	num = ((unsigned char *)hi->data)[i] | (num << 8);
322    return num;
323}
324
325int
326BN_rand(BIGNUM *bn, int bits, int top, int bottom)
327{
328    size_t len = (bits + 7) / 8;
329    heim_integer *i = (heim_integer *)bn;
330
331    BN_clear(bn);
332
333    i->negative = 0;
334    i->data = malloc(len);
335    if (i->data == NULL && len != 0)
336	return 0;
337    i->length = len;
338
339    if (RAND_bytes(i->data, i->length) != 1) {
340	free(i->data);
341	i->data = NULL;
342	return 0;
343    }
344
345    {
346	size_t j = len * 8;
347	while(j > bits) {
348	    BN_clear_bit(bn, j - 1);
349	    j--;
350	}
351    }
352
353    if (top == -1) {
354	;
355    } else if (top == 0 && bits > 0) {
356	BN_set_bit(bn, bits - 1);
357    } else if (top == 1 && bits > 1) {
358	BN_set_bit(bn, bits - 1);
359	BN_set_bit(bn, bits - 2);
360    } else {
361	BN_clear(bn);
362	return 0;
363    }
364
365    if (bottom && bits > 0)
366	BN_set_bit(bn, 0);
367
368    return 1;
369}
370
371/*
372 *
373 */
374
375int
376BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b)
377{
378    const heim_integer *ai = (const heim_integer *)a;
379    const heim_integer *bi = (const heim_integer *)b;
380    const unsigned char *ap, *bp;
381    unsigned char *cp;
382    heim_integer ci;
383    int carry = 0;
384    ssize_t len;
385
386    if (ai->negative && bi->negative)
387	return 0;
388    if (ai->length < bi->length) {
389	const heim_integer *si = bi;
390	bi = ai; ai = si;
391    }
392
393    ci.negative = 0;
394    ci.length = ai->length + 1;
395    ci.data = malloc(ci.length);
396    if (ci.data == NULL)
397	return 0;
398
399    ap = &((const unsigned char *)ai->data)[ai->length - 1];
400    bp = &((const unsigned char *)bi->data)[bi->length - 1];
401    cp = &((unsigned char *)ci.data)[ci.length - 1];
402
403    for (len = bi->length; len > 0; len--) {
404	carry = *ap + *bp + carry;
405	*cp = carry & 0xff;
406	carry = (carry & ~0xff) ? 1 : 0;
407	ap--; bp--; cp--;
408    }
409    for (len = ai->length - bi->length; len > 0; len--) {
410	carry = *ap + carry;
411	*cp = carry & 0xff;
412	carry = (carry & ~0xff) ? 1 : 0;
413	ap--; cp--;
414    }
415    if (!carry)
416	memmove(cp, cp + 1, --ci.length);
417    else
418	*cp = carry;
419
420    BN_clear(res);
421    *((heim_integer *)res) = ci;
422
423    return 1;
424}
425
426
427/*
428 * Callback when doing slow generation of numbers, like primes.
429 */
430
431void
432BN_GENCB_set(BN_GENCB *gencb, int (*cb_2)(int, int, BN_GENCB *), void *ctx)
433{
434    gencb->ver = 2;
435    gencb->cb.cb_2 = cb_2;
436    gencb->arg = ctx;
437}
438
439int
440BN_GENCB_call(BN_GENCB *cb, int a, int b)
441{
442    if (cb == NULL || cb->cb.cb_2 == NULL)
443	return 1;
444    return cb->cb.cb_2(a, b, cb);
445}
446
447/*
448 *
449 */
450
451struct BN_CTX {
452    struct {
453	BIGNUM **val;
454	size_t used;
455	size_t len;
456    } bn;
457    struct {
458	size_t *val;
459	size_t used;
460	size_t len;
461    } stack;
462};
463
464BN_CTX *
465BN_CTX_new(void)
466{
467    struct BN_CTX *c;
468    c = calloc(1, sizeof(*c));
469    return c;
470}
471
472void
473BN_CTX_free(BN_CTX *c)
474{
475    size_t i;
476    for (i = 0; i < c->bn.len; i++)
477	BN_free(c->bn.val[i]);
478    free(c->bn.val);
479    free(c->stack.val);
480}
481
482BIGNUM *
483BN_CTX_get(BN_CTX *c)
484{
485    if (c->bn.used == c->bn.len) {
486	void *ptr;
487	size_t i;
488	c->bn.len += 16;
489	ptr = realloc(c->bn.val, c->bn.len * sizeof(c->bn.val[0]));
490	if (ptr == NULL)
491	    return NULL;
492	c->bn.val = ptr;
493	for (i = c->bn.used; i < c->bn.len; i++) {
494	    c->bn.val[i] = BN_new();
495	    if (c->bn.val[i] == NULL) {
496		c->bn.len = i;
497		return NULL;
498	    }
499	}
500    }
501    return c->bn.val[c->bn.used++];
502}
503
504void
505BN_CTX_start(BN_CTX *c)
506{
507    if (c->stack.used == c->stack.len) {
508	void *ptr;
509	c->stack.len += 16;
510	ptr = realloc(c->stack.val, c->stack.len * sizeof(c->stack.val[0]));
511	if (ptr == NULL)
512	    abort();
513	c->stack.val = ptr;
514    }
515    c->stack.val[c->stack.used++] = c->bn.used;
516}
517
518void
519BN_CTX_end(BN_CTX *c)
520{
521    const size_t prev = c->stack.val[c->stack.used - 1];
522    size_t i;
523
524    if (c->stack.used == 0)
525	abort();
526
527    for (i = prev; i < c->bn.used; i++)
528	BN_clear(c->bn.val[i]);
529
530    c->stack.used--;
531    c->bn.used = prev;
532}
533
534