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