2 * Copyright (c) 2006 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
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.
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.
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
42 #include <krb5-types.h>
43 #include <rfc2459_asn1.h> /* XXX */
54 hi
= calloc(1, sizeof(*hi
));
68 heim_integer
*hi
= (heim_integer
*)bn
;
70 memset(hi
->data
, 0, hi
->length
);
73 memset(hi
, 0, sizeof(*hi
));
77 BN_clear_free(BIGNUM
*bn
)
83 BN_dup(const BIGNUM
*bn
)
86 if (der_copy_heim_integer((const heim_integer
*)bn
, (heim_integer
*)b
)) {
94 * If the caller really want to know the number of bits used, subtract
95 * one from the length, multiply by 8, and then lookup in the table
96 * how many bits the hightest byte uses.
99 BN_num_bits(const BIGNUM
*bn
)
101 static unsigned char num2bits
[256] = {
102 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,
103 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,
104 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,
105 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,
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 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,
108 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,
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,
111 const heim_integer
*i
= (const void *)bn
;
114 return (i
->length
- 1) * 8 + num2bits
[((unsigned char *)i
->data
)[0]];
118 BN_num_bytes(const BIGNUM
*bn
)
120 return ((const heim_integer
*)bn
)->length
;
124 * Ignore negative flag.
128 BN_bin2bn(const void *s
, int len
, BIGNUM
*bn
)
130 heim_integer
*hi
= (void *)bn
;
136 hi
= (heim_integer
*)BN_new();
141 BN_clear((BIGNUM
*)hi
);
143 hi
->data
= malloc(len
);
144 if (hi
->data
== NULL
&& len
!= 0) {
146 BN_free((BIGNUM
*)hi
);
150 memcpy(hi
->data
, s
, len
);
155 BN_bn2bin(const BIGNUM
*bn
, void *to
)
157 const heim_integer
*hi
= (const void *)bn
;
158 memcpy(to
, hi
->data
, hi
->length
);
163 BN_hex2bn(BIGNUM
**bnp
, const char *in
)
181 ret
= hex_decode(in
, data
, len
);
187 *bnp
= BN_bin2bn(data
, ret
, NULL
);
191 BN_set_negative(*bnp
, negative
);
196 BN_bn2hex(const BIGNUM
*bn
)
203 len
= BN_num_bytes(bn
);
208 len
= BN_bn2bin(bn
, data
);
210 ret
= hex_encode(data
, len
, &str
);
219 BN_cmp(const BIGNUM
*bn1
, const BIGNUM
*bn2
)
221 return der_heim_integer_cmp((const heim_integer
*)bn1
,
222 (const heim_integer
*)bn2
);
226 BN_set_negative(BIGNUM
*bn
, int flag
)
228 ((heim_integer
*)bn
)->negative
= (flag
? 1 : 0);
232 BN_is_negative(const BIGNUM
*bn
)
234 return ((const heim_integer
*)bn
)->negative
? 1 : 0;
237 static const unsigned char is_set
[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
240 BN_is_bit_set(const BIGNUM
*bn
, int bit
)
242 heim_integer
*hi
= (heim_integer
*)bn
;
243 unsigned char *p
= hi
->data
;
245 if ((bit
/ 8) > hi
->length
|| hi
->length
== 0)
248 return p
[hi
->length
- 1 - (bit
/ 8)] & is_set
[bit
% 8];
252 BN_set_bit(BIGNUM
*bn
, int bit
)
254 heim_integer
*hi
= (heim_integer
*)bn
;
257 if ((bit
/ 8) > hi
->length
|| hi
->length
== 0) {
258 size_t len
= (bit
+ 7) / 8;
259 void *d
= realloc(hi
->data
, len
);
264 memset(&p
[hi
->length
], 0, len
);
269 p
[hi
->length
- 1 - (bit
/ 8)] |= is_set
[bit
% 8];
274 BN_clear_bit(BIGNUM
*bn
, int bit
)
276 heim_integer
*hi
= (heim_integer
*)bn
;
277 unsigned char *p
= hi
->data
;
279 if ((bit
/ 8) > hi
->length
|| hi
->length
== 0)
282 p
[hi
->length
- 1 - (bit
/ 8)] &= (unsigned char)(~(is_set
[bit
% 8]));
288 BN_set_word(BIGNUM
*bn
, unsigned long num
)
290 unsigned char p
[sizeof(num
)];
294 for (num2
= num
, i
= 0; num2
> 0; i
++)
299 p
[i
- 1] = (num
& 0xff);
303 bn
= BN_bin2bn(p
, len
, bn
);
308 BN_get_word(const BIGNUM
*bn
)
310 heim_integer
*hi
= (heim_integer
*)bn
;
311 unsigned long num
= 0;
314 if (hi
->negative
|| hi
->length
> sizeof(num
))
317 for (i
= 0; i
< hi
->length
; i
++)
318 num
= ((unsigned char *)hi
->data
)[i
] | (num
<< 8);
323 BN_rand(BIGNUM
*bn
, int bits
, int top
, int bottom
)
325 size_t len
= (bits
+ 7) / 8;
326 heim_integer
*i
= (heim_integer
*)bn
;
331 i
->data
= malloc(len
);
332 if (i
->data
== NULL
&& len
!= 0)
336 if (RAND_bytes(i
->data
, i
->length
) != 1) {
345 BN_clear_bit(bn
, j
- 1);
352 } else if (top
== 0 && bits
> 0) {
353 BN_set_bit(bn
, bits
- 1);
354 } else if (top
== 1 && bits
> 1) {
355 BN_set_bit(bn
, bits
- 1);
356 BN_set_bit(bn
, bits
- 2);
362 if (bottom
&& bits
> 0)
373 BN_uadd(BIGNUM
*res
, const BIGNUM
*a
, const BIGNUM
*b
)
375 const heim_integer
*ai
= (const heim_integer
*)a
;
376 const heim_integer
*bi
= (const heim_integer
*)b
;
377 const unsigned char *ap
, *bp
;
383 if (ai
->negative
&& bi
->negative
)
385 if (ai
->length
< bi
->length
) {
386 const heim_integer
*si
= bi
;
391 ci
.length
= ai
->length
+ 1;
392 ci
.data
= malloc(ci
.length
);
396 ap
= &((const unsigned char *)ai
->data
)[ai
->length
- 1];
397 bp
= &((const unsigned char *)bi
->data
)[bi
->length
- 1];
398 cp
= &((unsigned char *)ci
.data
)[ci
.length
- 1];
400 for (len
= bi
->length
; len
> 0; len
--) {
401 carry
= *ap
+ *bp
+ carry
;
403 carry
= (carry
& ~0xff) ? 1 : 0;
406 for (len
= ai
->length
- bi
->length
; len
> 0; len
--) {
409 carry
= (carry
& ~0xff) ? 1 : 0;
413 memmove(cp
, cp
+ 1, --ci
.length
);
418 *((heim_integer
*)res
) = ci
;
425 * Callback when doing slow generation of numbers, like primes.
429 BN_GENCB_set(BN_GENCB
*gencb
, int (*cb_2
)(int, int, BN_GENCB
*), void *ctx
)
432 gencb
->cb
.cb_2
= cb_2
;
437 BN_GENCB_call(BN_GENCB
*cb
, int a
, int b
)
439 if (cb
== NULL
|| cb
->cb
.cb_2
== NULL
)
441 return cb
->cb
.cb_2(a
, b
, cb
);
465 c
= calloc(1, sizeof(*c
));
470 BN_CTX_free(BN_CTX
*c
)
473 for (i
= 0; i
< c
->bn
.len
; i
++)
474 BN_free(c
->bn
.val
[i
]);
480 BN_CTX_get(BN_CTX
*c
)
482 if (c
->bn
.used
== c
->bn
.len
) {
486 ptr
= realloc(c
->bn
.val
, c
->bn
.len
* sizeof(c
->bn
.val
[0]));
490 for (i
= c
->bn
.used
; i
< c
->bn
.len
; i
++) {
491 c
->bn
.val
[i
] = BN_new();
492 if (c
->bn
.val
[i
] == NULL
) {
498 return c
->bn
.val
[c
->bn
.used
++];
502 BN_CTX_start(BN_CTX
*c
)
504 if (c
->stack
.used
== c
->stack
.len
) {
507 ptr
= realloc(c
->stack
.val
, c
->stack
.len
* sizeof(c
->stack
.val
[0]));
512 c
->stack
.val
[c
->stack
.used
++] = c
->bn
.used
;
516 BN_CTX_end(BN_CTX
*c
)
518 const size_t prev
= c
->stack
.val
[c
->stack
.used
- 1];
521 if (c
->stack
.used
== 0)
524 for (i
= prev
; i
< c
->bn
.used
; i
++)
525 BN_clear(c
->bn
.val
[i
]);