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