Home | History | Annotate | Download | only in bignum
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License (the "License").
      6  * You may not use this file except in compliance with the License.
      7  *
      8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
      9  * or http://www.opensolaris.org/os/licensing.
     10  * See the License for the specific language governing permissions
     11  * and limitations under the License.
     12  *
     13  * When distributing Covered Code, include this CDDL HEADER in each
     14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     15  * If applicable, add the following below this CDDL HEADER, with the
     16  * fields enclosed by brackets "[]" replaced with your own identifying
     17  * information: Portions Copyright [yyyy] [name of copyright owner]
     18  *
     19  * CDDL HEADER END
     20  */
     21 /*
     22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
     23  * Use is subject to license terms.
     24  */
     25 
     26 #ifndef _BIGNUM_H
     27 #define	_BIGNUM_H
     28 
     29 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     30 
     31 #ifdef	__cplusplus
     32 extern "C" {
     33 #endif
     34 
     35 #include <sys/types.h>
     36 
     37 #ifndef __sparcv9
     38 #define	BIGNUM_CHUNK_32
     39 #else
     40 #ifndef UMUL64
     41 #define	UMUL64
     42 #endif
     43 #endif
     44 
     45 
     46 #define	BITSINBYTE	8
     47 
     48 #ifdef BIGNUM_CHUNK_32
     49 #define	BIG_CHUNK_SIZE		32
     50 #define	BIG_CHUNK_TYPE		uint32_t
     51 #define	BIG_CHUNK_TYPE_SIGNED	int32_t
     52 #define	BIG_CHUNK_HIGHBIT	0x80000000
     53 #define	BIG_CHUNK_ALLBITS	0xffffffff
     54 #define	BIG_CHUNK_LOWHALFBITS	0xffff
     55 #define	BIG_CHUNK_HALF_HIGHBIT	0x8000
     56 #else
     57 #define	BIG_CHUNK_SIZE		64
     58 #define	BIG_CHUNK_TYPE		uint64_t
     59 #define	BIG_CHUNK_TYPE_SIGNED	int64_t
     60 #define	BIG_CHUNK_HIGHBIT	0x8000000000000000ULL
     61 #define	BIG_CHUNK_ALLBITS	0xffffffffffffffffULL
     62 #define	BIG_CHUNK_LOWHALFBITS	0xffffffffULL
     63 #define	BIG_CHUNK_HALF_HIGHBIT	0x80000000ULL
     64 #endif
     65 
     66 #define	BITLEN2BIGNUMLEN(x)	(((x) + BIG_CHUNK_SIZE - 1) / BIG_CHUNK_SIZE)
     67 #define	CHARLEN2BIGNUMLEN(x)	(((x) + sizeof (BIG_CHUNK_TYPE) - 1) / \
     68 				sizeof (BIG_CHUNK_TYPE))
     69 
     70 #define	BIGNUM_WORDSIZE	(BIG_CHUNK_SIZE / BITSINBYTE)  /* word size in bytes */
     71 #define	BIG_CHUNKS_FOR_160BITS	((160 + BIG_CHUNK_SIZE - 1) / BIG_CHUNK_SIZE)
     72 
     73 
     74 /*
     75  * leading 0's are permitted
     76  * 0 should be represented by size>=1, size>=len>=1, sign=1,
     77  * value[i]=0 for 0<i<len
     78  */
     79 typedef struct {
     80 	/* size and len in units of BIG_CHUNK_TYPE words  */
     81 	int size; /* size of memory allocated for value   */
     82 	int len;  /* number of words that hold valid data in value */
     83 	int sign; /* 1 for nonnegative, -1 for negative   */
     84 	int malloced; /* 1 if value was malloced 0 if not */
     85 	BIG_CHUNK_TYPE *value;
     86 } BIGNUM;
     87 
     88 #define	BIGTMPSIZE 65
     89 
     90 #define	BIG_TRUE 1
     91 #define	BIG_FALSE 0
     92 
     93 typedef int BIG_ERR_CODE;
     94 
     95 /* error codes */
     96 #define	BIG_OK 0
     97 #define	BIG_NO_MEM -1
     98 #define	BIG_INVALID_ARGS -2
     99 #define	BIG_DIV_BY_0 -3
    100 #define	BIG_NO_RANDOM -4
    101 #define	BIG_GENERAL_ERR	-5
    102 #define	BIG_TEST_FAILED -6
    103 #define	BIG_BUFFER_TOO_SMALL -7
    104 
    105 
    106 #define	arraysize(x) (sizeof (x) / sizeof (x[0]))
    107 
    108 typedef BIG_ERR_CODE (*big_modexp_ncp_func_ptr)(BIGNUM *result,
    109     BIGNUM *ma, BIGNUM *e, BIGNUM *n,
    110     BIGNUM *tmp, BIG_CHUNK_TYPE n0, void *ncp, void *req);
    111 
    112 typedef struct {
    113 	big_modexp_ncp_func_ptr	func;
    114 	void			*ncp;
    115 	void 			*reqp;
    116 } big_modexp_ncp_info_t;
    117 
    118 
    119 #ifdef USE_FLOATING_POINT
    120 void conv_d16_to_i32(uint32_t *i32, double *d16, int64_t *tmp, int ilen);
    121 void conv_i32_to_d32(double *d32, uint32_t *i32, int len);
    122 void conv_i32_to_d16(double *d16, uint32_t *i32, int len);
    123 void conv_i32_to_d32_and_d16(double *d32, double *d16,
    124     uint32_t *i32, int len);
    125 void mont_mulf_noconv(uint32_t *result, double *dm1, double *dm2, double *dt,
    126     double *dn, uint32_t *nint, int nlen, double dn0);
    127 #endif /* USE_FLOATING_POINT */
    128 
    129 extern BIGNUM big_One;
    130 extern BIGNUM big_Two;
    131 
    132 
    133 void printbignum(char *aname, BIGNUM *a);
    134 
    135 BIG_ERR_CODE big_init(BIGNUM *number, int size);
    136 BIG_ERR_CODE big_extend(BIGNUM *number, int size);
    137 void big_finish(BIGNUM *number);
    138 void bytestring2bignum(BIGNUM *bn, uchar_t *kn, size_t len);
    139 void bignum2bytestring(uchar_t *kn, BIGNUM *bn, size_t len);
    140 BIG_ERR_CODE big_mont_rr(BIGNUM *result, BIGNUM *n);
    141 BIG_ERR_CODE big_modexp(BIGNUM *result, BIGNUM *a, BIGNUM *e,
    142     BIGNUM *n, BIGNUM *n_rr);
    143 BIG_ERR_CODE big_modexp_ext(BIGNUM *result, BIGNUM *a, BIGNUM *e,
    144     BIGNUM *n, BIGNUM *n_rr, big_modexp_ncp_info_t *info);
    145 BIG_ERR_CODE big_modexp_crt(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
    146     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
    147     BIGNUM *p_rr, BIGNUM *q_rr);
    148 BIG_ERR_CODE big_modexp_crt_ext(BIGNUM *result, BIGNUM *a, BIGNUM *dmodpminus1,
    149     BIGNUM *dmodqminus1, BIGNUM *p, BIGNUM *q, BIGNUM *pinvmodq,
    150     BIGNUM *p_rr, BIGNUM *q_rr, big_modexp_ncp_info_t *info);
    151 int big_cmp_abs(BIGNUM *a, BIGNUM *b);
    152 BIG_ERR_CODE randombignum(BIGNUM *r, int length);
    153 BIG_ERR_CODE big_div_pos(BIGNUM *result, BIGNUM *remainder,
    154     BIGNUM *aa, BIGNUM *bb);
    155 BIG_ERR_CODE big_ext_gcd_pos(BIGNUM *gcd, BIGNUM *cm, BIGNUM *ce,
    156     BIGNUM *m, BIGNUM *e);
    157 BIG_ERR_CODE big_add(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
    158 BIG_ERR_CODE big_add_abs(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
    159 BIG_ERR_CODE big_mul(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
    160 void big_shiftright(BIGNUM *result, BIGNUM *aa, int offs);
    161 BIG_ERR_CODE big_nextprime_pos(BIGNUM *result, BIGNUM *n);
    162 BIG_ERR_CODE big_nextprime_pos_ext(BIGNUM *result, BIGNUM *n,
    163     big_modexp_ncp_info_t *info);
    164 BIG_ERR_CODE big_sub_pos(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
    165 BIG_ERR_CODE big_copy(BIGNUM *dest, BIGNUM *src);
    166 BIG_ERR_CODE big_sub(BIGNUM *result, BIGNUM *aa, BIGNUM *bb);
    167 int big_bitlength(BIGNUM *n);
    168 BIG_ERR_CODE big_init1(BIGNUM *number, int size,
    169     BIG_CHUNK_TYPE *buf, int bufsize);
    170 BIG_ERR_CODE big_mont_mul(BIGNUM *ret,
    171     BIGNUM *a, BIGNUM *b, BIGNUM *n, BIG_CHUNK_TYPE n0);
    172 int big_is_zero(BIGNUM *n);
    173 BIG_CHUNK_TYPE big_n0(BIG_CHUNK_TYPE n);
    174 
    175 
    176 #if defined(HWCAP)
    177 
    178 #if (BIG_CHUNK_SIZE != 32)
    179 #error HWCAP works only with 32-bit bignum chunks
    180 #endif
    181 
    182 #define	BIG_MUL_SET_VEC(r, a, len, digit) \
    183 	(*big_mul_set_vec_impl)(r, a, len, digit)
    184 #define	BIG_MUL_ADD_VEC(r, a, len, digit) \
    185 	(*big_mul_add_vec_impl)(r, a, len, digit)
    186 #define	BIG_MUL_VEC(r, a, alen, b, blen) \
    187 	(*big_mul_vec_impl)(r, a, alen, b, blen)
    188 #define	BIG_SQR_VEC(r, a, len) \
    189 	(*big_sqr_vec_impl)(r, a, len)
    190 
    191 extern BIG_CHUNK_TYPE (*big_mul_set_vec_impl)
    192 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
    193 extern BIG_CHUNK_TYPE (*big_mul_add_vec_impl)
    194 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE digit);
    195 extern void (*big_mul_vec_impl)
    196 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen, BIG_CHUNK_TYPE *b,
    197 	    int blen);
    198 extern void (*big_sqr_vec_impl)
    199 	(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
    200 
    201 #else /* ! HWCAP */
    202 
    203 #define	BIG_MUL_SET_VEC(r, a, len, digit) big_mul_set_vec(r, a, len, digit)
    204 #define	BIG_MUL_ADD_VEC(r, a, len, digit) big_mul_add_vec(r, a, len, digit)
    205 #define	BIG_MUL_VEC(r, a, alen, b, blen) big_mul_vec(r, a, alen, b, blen)
    206 #define	BIG_SQR_VEC(r, a, len) big_sqr_vec(r, a, len)
    207 
    208 extern BIG_CHUNK_TYPE big_mul_set_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a,
    209     int len, BIG_CHUNK_TYPE d);
    210 extern BIG_CHUNK_TYPE big_mul_add_vec(BIG_CHUNK_TYPE *r,
    211     BIG_CHUNK_TYPE *a, int len, BIG_CHUNK_TYPE d);
    212 extern void big_mul_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int alen,
    213     BIG_CHUNK_TYPE *b, int blen);
    214 extern void big_sqr_vec(BIG_CHUNK_TYPE *r, BIG_CHUNK_TYPE *a, int len);
    215 
    216 #endif /* HWCAP */
    217 
    218 #ifdef	__cplusplus
    219 }
    220 #endif
    221 
    222 #endif	/* _BIGNUM_H */
    223