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 
53 BIGNUM *
BN_new(void)54 BN_new(void)
55 {
56     heim_integer *hi;
57     hi = calloc(1, sizeof(*hi));
58     return (BIGNUM *)hi;
59 }
60 
61 void
BN_free(BIGNUM * bn)62 BN_free(BIGNUM *bn)
63 {
64     BN_clear(bn);
65     free(bn);
66 }
67 
68 void
BN_clear(BIGNUM * bn)69 BN_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 
79 void
BN_clear_free(BIGNUM * bn)80 BN_clear_free(BIGNUM *bn)
81 {
82     BN_free(bn);
83 }
84 
85 BIGNUM *
BN_dup(const BIGNUM * bn)86 BN_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  */
101 int
BN_num_bits(const BIGNUM * bn)102 BN_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 
120 int
BN_num_bytes(const BIGNUM * bn)121 BN_num_bytes(const BIGNUM *bn)
122 {
123     return ((const heim_integer *)bn)->length;
124 }
125 
126 /*
127  * Ignore negative flag.
128  */
129 
130 BIGNUM *
BN_bin2bn(const void * s,int len,BIGNUM * bn)131 BN_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 
157 int
BN_bn2bin(const BIGNUM * bn,void * to)158 BN_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 
165 int
BN_hex2bn(BIGNUM ** bnp,const char * in)166 BN_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 
198 char *
BN_bn2hex(const BIGNUM * bn)199 BN_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 
221 int
BN_cmp(const BIGNUM * bn1,const BIGNUM * bn2)222 BN_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 
228 void
BN_set_negative(BIGNUM * bn,int flag)229 BN_set_negative(BIGNUM *bn, int flag)
230 {
231     ((heim_integer *)bn)->negative = (flag ? 1 : 0);
232 }
233 
234 int
BN_is_negative(const BIGNUM * bn)235 BN_is_negative(const BIGNUM *bn)
236 {
237     return ((const heim_integer *)bn)->negative ? 1 : 0;
238 }
239 
240 static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
241 
242 int
BN_is_bit_set(const BIGNUM * bn,int bit)243 BN_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 
254 int
BN_set_bit(BIGNUM * bn,int bit)255 BN_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 
276 int
BN_clear_bit(BIGNUM * bn,int bit)277 BN_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 
290 int
BN_set_word(BIGNUM * bn,unsigned long num)291 BN_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 
310 unsigned long
BN_get_word(const BIGNUM * bn)311 BN_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 
325 int
BN_rand(BIGNUM * bn,int bits,int top,int bottom)326 BN_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 
375 int
BN_uadd(BIGNUM * res,const BIGNUM * a,const BIGNUM * b)376 BN_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 
431 void
BN_GENCB_set(BN_GENCB * gencb,int (* cb_2)(int,int,BN_GENCB *),void * ctx)432 BN_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 
439 int
BN_GENCB_call(BN_GENCB * cb,int a,int b)440 BN_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 
451 struct 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 
464 BN_CTX *
BN_CTX_new(void)465 BN_CTX_new(void)
466 {
467     struct BN_CTX *c;
468     c = calloc(1, sizeof(*c));
469     return c;
470 }
471 
472 void
BN_CTX_free(BN_CTX * c)473 BN_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 
482 BIGNUM *
BN_CTX_get(BN_CTX * c)483 BN_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 
504 void
BN_CTX_start(BN_CTX * c)505 BN_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 
518 void
BN_CTX_end(BN_CTX * c)519 BN_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