1/* 2 * Copyright (c) 2011-12 Apple Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24/* 25 * Copyright (c) 2006 Kungliga Tekniska Högskolan 26 * (Royal Institute of Technology, Stockholm, Sweden). 27 * All rights reserved. 28 * 29 * Redistribution and use in source and binary forms, with or without 30 * modification, are permitted provided that the following conditions 31 * are met: 32 * 33 * 1. Redistributions of source code must retain the above copyright 34 * notice, this list of conditions and the following disclaimer. 35 * 36 * 2. Redistributions in binary form must reproduce the above copyright 37 * notice, this list of conditions and the following disclaimer in the 38 * documentation and/or other materials provided with the distribution. 39 * 40 * 3. Neither the name of the Institute nor the names of its contributors 41 * may be used to endorse or promote products derived from this software 42 * without specific prior written permission. 43 * 44 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 47 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 54 * SUCH DAMAGE. 55 */ 56 57#ifndef _OSSL_BN_H_ 58#define _OSSL_BN_H_ 1 59 60#include <stdio.h> 61 62/* symbol renaming */ 63#define BN_GENCB_call ossl_BN_GENCB_call 64#define BN_GENCB_set ossl_BN_GENCB_set 65#define BN_add ossl_BN_add 66#define BN_add_word ossl_BN_add_word 67#define BN_bin2bn ossl_BN_bin2bn 68#define BN_bn2bin ossl_BN_bn2bin 69#define BN_bn2dec ossl_BN_bn2dec 70#define BN_bn2hex ossl_BN_bn2hex 71#define BN_clear ossl_BN_clear 72#define BN_clear_bit ossl_BN_clear_bit 73#define BN_clear_free ossl_BN_clear_free 74#define BN_cmp ossl_BN_cmp 75#define BN_copy ossl_BN_copy 76#define BN_dec2bn ossl_BN_dec2bn 77#define BN_div ossl_BN_div 78#define BN_dup ossl_BN_dup 79#define BN_free ossl_BN_free 80#define BN_gcd ossl_BN_gcd 81#define BN_generate_prime_ex ossl_BN_generate_prime_ex 82#define BN_init ossl_BN_init 83#undef BN_is_negative 84#define BN_is_negative(a) ((a)->neg != 0) 85#define BN_get_word ossl_BN_get_word 86#define BN_hex2bn ossl_BN_hex2bn 87#define BN_is_bit_set ossl_BN_is_bit_set 88#undef BN_abs_is_word 89#define BN_abs_is_word(a, w) \ 90 ((((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) || \ 91 (((w) == 0) && ((a)->top == 0))) 92#undef BN_is_one 93#define BN_is_one(a) (BN_abs_is_word((a), 1) && !(a)->neg) 94#define BN_is_prime_ex ossl_BN_is_prime_ex 95#define BN_is_prime_fasttest_ex ossl_BN_is_prime_fasttest_ex 96#undef BN_is_zero 97#define BN_is_zero(a) ((a)->top == 0) 98#undef BN_is_word 99#define BN_is_word(a, w) (BN_abs_is_word((a), (w)) && (!(w) || !(a)->neg)) 100#undef BN_is_odd 101#define BN_is_odd(a) (((a)->top > 0) && ((a)->d[0] & 1)) 102#define BN_lshift ossl_BN_lshift 103#define BN_lshift1 ossl_BN_lshift1 104#undef BN_set_flags 105#define BN_set_flags(b, n) ((b)->flags |= (n)) 106#undef BN_get_flags 107#define BN_get_flags(b, n) ((b)->flags&(n)) 108 109#define BN_mask_bits ossl_BN_mask_bits 110#undef BN_mod 111#define BN_mod ossl_BN_mod 112#define BN_mod_exp ossl_BN_mod_exp 113#define BN_mod_exp_mont ossl_BN_mod_exp_mont 114#define BN_mod_exp2_mont ossl_BN_mod_exp2_mont 115#define BN_mod_exp_mont_consttime ossl_BN_mod_exp_mont_consttime 116#define BN_mod_exp_mont_word ossl_BN_mod_exp_mont_word 117#define BN_mod_inverse ossl_BN_mod_inverse 118#define BN_mod_word ossl_BN_mod_word 119#define BN_mul ossl_BN_mul 120#define BN_new ossl_BN_new 121#define BN_num_bits ossl_BN_num_bits 122#define BN_num_bits_word ossl_BN_num_bits_word 123#define BN_num_bytes ossl_BN_num_bytes 124#define BN_print_fp ossl_BN_print_fp 125#define BN_rand ossl_BN_rand 126#define BN_pseudo_rand ossl_BN_pseudo_rand 127#define BN_rand_range ossl_BN_rand_range 128#define BN_pseudo_rand_range ossl_BN_pseudo_rand_range 129#define BN_rshift ossl_BN_rshift 130#define BN_rshift1 ossl_BN_rshift1 131#define BN_set_bit ossl_BN_set_bit 132#define BN_set_negative ossl_BN_set_negative 133#define BN_set_word ossl_BN_set_word 134#define BN_sqr ossl_BN_sqr 135#define BN_sub ossl_BN_sub 136#define BN_sub_word ossl_BN_sub_word 137#define BN_uadd ossl_BN_uadd 138#define BN_ucmp ossl_BN_ucmp 139#define BN_usub ossl_BN_usub 140#define BN_value_one ossl_BN_value_one 141#define BN_CTX_new ossl_BN_CTX_new 142#define BN_CTX_free ossl_BN_CTX_free 143#define BN_CTX_get ossl_BN_CTX_get 144#define BN_CTX_start ossl_BN_CTX_start 145#define BN_CTX_end ossl_BN_CTX_end 146 147#define BN_mod_mul_montgomery ossl_BN_mod_mul_montgomery 148#define BN_from_montgomery ossl_BN_from_montgomery 149#define BN_MONT_CTX_new ossl_BN_MONT_CTX_new 150#define BN_MONT_CTX_init ossl_BN_MONT_CTX_init 151#define BN_MONT_CTX_free ossl_BN_MONT_CTX_free 152#define BN_MONT_CTX_set ossl_BN_MONT_CTX_set 153#define BN_MONT_CTX_copy ossl_BN_MONT_CTX_copy 154#define BN_MONT_CTX_set_locked ossl_BN_MONT_CTX_set_locked 155 156#define BN_to_montgomery(r, a, mont, ctx) \ 157 BN_mod_mul_montgomery((r), (a), &((mont)->RR), (mont), (ctx)) 158 159#define BN_zero(a) (BN_set_word((a), 0)) 160#define BN_one(a) (BN_set_word((a), 1)) 161 162#undef BN_with_flags 163 164/* get a clone of a BIGNUM with changed flags, for *temporary* use only 165 * * (the two BIGNUMs cannot not be used in parallel!) */ 166#define BN_with_flags(dest, b, n) \ 167 ((dest)->d = (b)->d, \ 168 (dest)->top = (b)->top, \ 169 (dest)->dmax = (b)->dmax, \ 170 (dest)->neg = (b)->neg, \ 171 (dest)->flags = (((dest)->flags & BN_FLG_MALLOCED) \ 172 | ((b)->flags & ~BN_FLG_MALLOCED) \ 173 | BN_FLG_STATIC_DATA \ 174 | (n))) 175 176 177#if defined(__LP64__) && defined(__x86_64__) 178 179# define SIXTY_FOUR_BIT_LONG 1 180 181# define BN_ULLONG unsigned long long 182# define BN_ULONG unsigned long 183# define BN_LONG long 184# define BN_BITS 128 185# define BN_BYTES 8 186# define BN_BITS2 64 187# define BN_BITS4 32 188# define BN_MASK (0xffffffffffffffffffffffffffffffffLL) 189# define BN_MASK2 (0xffffffffffffffffL) 190# define BN_MASK2l (0xffffffffL) 191# define BN_MASK2h (0xffffffff00000000L) 192# define BN_MASK2h1 (0xffffffff80000000L) 193# define BN_TBIT (0x8000000000000000L) 194# define BN_DEC_CONV (10000000000000000000UL) 195# define BN_DEC_FMT1 "%lu" 196# define BN_DEC_FMT2 "%019lu" 197# define BN_DEC_NUM 19 198 199#elif !defined(__LP64__) && defined(__i386__) 200 201# define THIRTY_TWO_BIT 1 202 203# define BN_ULLONG unsigned long long 204# define BN_ULONG unsigned long 205# define BN_LONG long 206# define BN_BITS 64 207# define BN_BYTES 4 208# define BN_BITS2 32 209# define BN_BITS4 16 210# define BN_MASK (0xffffffffffffffffLL) 211# define BN_MASK2 (0xffffffffL) 212# define BN_MASK2l (0xffff) 213# define BN_MASK2h1 (0xffff8000L) 214# define BN_MASK2h (0xffff0000L) 215# define BN_TBIT (0x80000000L) 216# define BN_DEC_CONV (1000000000L) 217# define BN_DEC_FMT1 "%lu" 218# define BN_DEC_FMT2 "%09lu" 219# define BN_DEC_NUM 9 220 221#else 222 223# error "Unknown arch" 224 225#endif /* ! __LP64__ */ 226 227 228/* 229 * 230 */ 231 232typedef struct bignum_ctx BN_CTX; 233typedef struct bignum_gencb_st BN_GENCB; 234typedef struct bn_mont_ctx_st BN_MONT_CTX; 235typedef struct BN_BLINDING BN_BLINDING; 236 237typedef struct bignum_st { 238 BN_ULONG * d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ 239 int top; /* Index of last used d +1. */ 240 /* The next are internal book keeping for bn_expand. */ 241 int dmax; /* Size of the d array. */ 242 int neg; /* one if the number is negative */ 243 int flags; 244} BIGNUM; 245 246/* BIGNUM flags: */ 247#define BN_FLG_MALLOCED 0x01 /* d has been malloc()'ed */ 248#define BN_FLG_STATIC_DATA 0x02 /* static or constant data */ 249#define BN_FLG_CONSTTIME 0x04 /* avoid timing attacks */ 250 251#define BN_prime_checks 0 /* default */ 252 253struct bignum_gencb_st { 254 unsigned int ver; 255 void * arg; 256 union { 257 int (*cb_2)(int, int, BN_GENCB *); 258 } 259 cb; 260}; 261 262struct bn_mont_ctx_st { 263 int ri; /* number of bits in R */ 264 BIGNUM RR; /* used to convert to montgomery form */ 265 BIGNUM N; /* The modulus */ 266 BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 267 * (Ni is only stored for bignum algorithm) */ 268 BN_ULONG n0; /* least significant word of Ni */ 269 int flags; 270}; 271 272 273/* 274 * 275 */ 276 277BIGNUM *BN_new(void); 278void BN_init(BIGNUM *); 279void BN_free(BIGNUM *); 280void BN_clear_free(BIGNUM *); 281void BN_clear(BIGNUM *); 282BIGNUM *BN_dup(const BIGNUM *); 283BIGNUM *BN_copy(BIGNUM *, const BIGNUM *); 284 285int BN_num_bits(const BIGNUM *); 286 287int BN_num_bits_word(BN_ULONG); 288int BN_num_bytes(const BIGNUM *); 289 290int BN_cmp(const BIGNUM *, const BIGNUM *); 291int BN_ucmp(const BIGNUM *, const BIGNUM *); 292 293void BN_set_negative(BIGNUM *, int); 294 295int BN_is_bit_set(const BIGNUM *, int); 296int BN_set_bit(BIGNUM *, int); 297int BN_clear_bit(BIGNUM *, int); 298int BN_mask_bits(BIGNUM *, int); 299 300int BN_set_word(BIGNUM *, BN_ULONG); 301BN_ULONG BN_get_word(const BIGNUM *); 302int BN_add_word(BIGNUM *a, BN_ULONG num); 303int BN_sub_word(BIGNUM *a, BN_ULONG num); 304 305BN_ULONG BN_div_word(BIGNUM *, BN_ULONG); 306BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w); 307 308int BN_mul_word(BIGNUM *, BN_ULONG); 309 310int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, 311 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont); 312int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, 313 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont); 314int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, 315 const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, 316 BN_CTX *ctx, BN_MONT_CTX *in_mont); 317int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, 318 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont); 319 320int BN_lshift(BIGNUM *, const BIGNUM *, int); 321int BN_lshift1(BIGNUM *, const BIGNUM *); 322int BN_rshift(BIGNUM *, const BIGNUM *, int); 323int BN_rshift1(BIGNUM *, const BIGNUM *); 324 325BIGNUM *BN_bin2bn(const unsigned char *, int len, BIGNUM *); 326int BN_bn2bin(const BIGNUM *, unsigned char *); 327int BN_hex2bn(BIGNUM **, const char *); 328char *BN_bn2hex(const BIGNUM *); 329int BN_print(void *fp, const BIGNUM *a); 330int BN_print_fp(FILE *, const BIGNUM *); 331 332int BN_uadd(BIGNUM *, const BIGNUM *, const BIGNUM *); 333int BN_usub(BIGNUM *, const BIGNUM *, const BIGNUM *); 334int BN_sub(BIGNUM *, const BIGNUM *, const BIGNUM *); 335int BN_add(BIGNUM *, const BIGNUM *, const BIGNUM *); 336 337int BN_div(BIGNUM *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 338int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); 339 340int BN_mod(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 341int BN_mod_mul(BIGNUM *, const BIGNUM *, const BIGNUM *, 342 const BIGNUM *, BN_CTX *); 343int BN_mod_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, 344 const BIGNUM *, BN_CTX *); 345BIGNUM *BN_mod_inverse(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *ctx); 346 347int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); 348 349int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb); 350int BN_is_prime_fasttest_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx, 351 int do_trial_division, BN_GENCB *cb); 352 353const BIGNUM *BN_value_one(void); 354 355int BN_rand(BIGNUM *, int, int, int); 356int BN_pseudo_rand(BIGNUM *, int, int, int); 357int BN_rand_range(BIGNUM *, const BIGNUM *); 358int BN_pseudo_rand_range(BIGNUM *, const BIGNUM *); 359 360int BN_generate_prime_ex(BIGNUM *, int, int, const BIGNUM *, const BIGNUM *, BN_GENCB *); 361int BN_gcd(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 362 363void BN_GENCB_set(BN_GENCB *, int (*)(int, int, BN_GENCB *), void *); 364int BN_GENCB_call(BN_GENCB *, int, int); 365 366BN_CTX *BN_CTX_new(void); 367void BN_CTX_free(BN_CTX *); 368BIGNUM *BN_CTX_get(BN_CTX *); 369void BN_CTX_start(BN_CTX *); 370void BN_CTX_end(BN_CTX *); 371 372int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 373 BN_MONT_CTX *mont, BN_CTX *ctx); 374int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, 375 BN_MONT_CTX *mont, BN_CTX *ctx); 376BN_MONT_CTX *BN_MONT_CTX_new(void); 377void BN_MONT_CTX_init(BN_MONT_CTX *ctx); 378void BN_MONT_CTX_free(BN_MONT_CTX *mont); 379int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx); 380BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from); 381BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, 382 const BIGNUM *mod, BN_CTX *ctx); 383 384int BN_dec2bn(BIGNUM **a, const char *str); 385char *BN_bn2dec(const BIGNUM *a); 386 387#endif /* _OSSL_BN_H_ */ 388