Debian Codegraph @

lib/hcrypto/bn.c

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