1
2/*
3 * Licensed Materials - Property of IBM
4 *
5 * trousers - An open source TCG Software Stack
6 *
7 * (C) Copyright International Business Machines Corp. 2006
8 *
9 */
10
11#ifdef BI_GMP
12
13#include <time.h>
14#include <stdio.h>
15#include <stdlib.h>
16
17#include <bi.h>
18
19#undef INLINE_DECL
20#define INLINE_DECL
21
22gmp_randstate_t state;
23
24/*
25 reps controls how many  tests should be done in mpz_probable_prime_p:
26 5 to 10 are reasonable number
27*/
28static int reps = 20;
29
30static int initialized = 0;
31void * (*bi_alloc)(size_t size);
32
33/***********************************************************************************
34	BITS OPERATION
35*************************************************************************************/
36
37// for conversion from and to byte[] see mpz_export and mpz_import
38
39/* return the size of a network byte order representation of <i>  */
40long bi_nbin_size(const bi_ptr i) {
41	int word_size = 1; // 1 byte per word
42	int numb = 8 * word_size - 0;
43	int count = (mpz_sizeinbase ( i, 2) + numb-1) / numb;
44
45	return count * word_size;
46}
47
48/* return a BYTE * - in network byte order -  and update the length <length> */
49unsigned char *bi_2_nbin( int *length, const bi_ptr i) {
50	unsigned char *buffer = (unsigned char *)bi_alloc( bi_nbin_size( i));
51
52	if( buffer == NULL) return NULL;
53	mpz_export(buffer, length, 1, 1, 1, 0, i);
54	return buffer;
55}
56
57/* return a BYTE * - in network byte order -  and update the length <length>  */
58/* different from bi_2_nbin: you should reserve enough memory for the storage */
59void bi_2_nbin1( int *length, unsigned char *buffer, const bi_ptr i) {
60	mpz_export(buffer, length, 1, 1, 1, 0, i);
61}
62
63/* return a bi_ptr that correspond to the big endian encoded BYTE array of length <n_length> */
64INLINE_DECL bi_ptr bi_set_as_nbin( const unsigned long length, const unsigned char *buffer) {
65	bi_ptr ret = bi_new_ptr();
66
67	if( ret == NULL) return NULL;
68	mpz_import( ret, length, 1, 1, 1, 0, buffer);
69	return ret;
70}
71
72
73/***********************************************************************************
74	BASIC MATH OPERATION
75*************************************************************************************/
76
77/* multiple-exponentiation */
78/* <result> := mod( Multi( <g>i, <e>i), number of byte <m>) with  0 <= i <= <n> */
79bi_ptr bi_multi_mod_exp( bi_ptr result,
80			const int n,
81			const bi_t g[],
82			const long e[],
83			const int m) {
84	mpz_t temp, bi_m;
85	int i;
86
87	mpz_init( temp);
88	mpz_init( bi_m);
89	mpz_set_si( bi_m, m);
90	// result := (g[0] ^ e[0]) mod m
91	mpz_powm_ui( result, g[0], e[0], bi_m);
92	for( i=1; i<n; i++) {
93		//  temp := (g[i] ^ e[i]) mod bi_m
94		mpz_powm_ui( temp, g[i], e[i], bi_m);
95		//  result := result * temp
96		mpz_mul( result, result, temp);
97	}
98	mpz_mod_ui( result, result, m);
99	mpz_clear( bi_m);
100	mpz_clear( temp);
101	return result;
102}
103
104/***********************************************************************************
105	NUMBER THEORIE OPERATION
106*************************************************************************************/
107/* generate prime number of <length> bits  */
108INLINE_DECL bi_ptr bi_generate_prime( bi_ptr result, const long length) {
109	do {
110		mpz_urandomb( result, state, length);	// i := random( length)
111		bi_setbit( result, 0);
112		bi_setbit( result, length - 1);
113		bi_setbit( result, length - 2);
114		mpz_nextprime( result, result);	// i := nextPrime( i)
115	} while( mpz_sizeinbase( result, 2) != (unsigned long)length &&
116			bi_is_probable_prime( result) );
117	return result;
118}
119
120/* generate a safe prime number of <length> bits  */
121/* by safe we mean a prime p so that (p-1)/2 is also prime */
122INLINE_DECL bi_ptr bi_generate_safe_prime( bi_ptr result, long length) {
123	mpz_t temp;
124
125	mpz_init(temp);
126	do {
127		bi_generate_prime( result, length);
128		mpz_sub_ui( temp, result, 1); // temp := result - 1
129		mpz_div_2exp( temp, temp, 1); // temp := temp / 2
130	} while( mpz_probab_prime_p( temp, 10) == 0);
131#ifdef BI_DEBUG
132	printf("GENERATE SAFE PRIME DONE");fflush(stdout);
133#endif
134	mpz_clear( temp);
135	return result;
136}
137
138/* return true if <i> is a probably prime  */
139INLINE_DECL int bi_is_probable_prime( bi_ptr i) {
140	/*
141	This function does some trial divisions and after some Miller-Rabin probabilistic
142	primality tests. The second parameter controls how many  tests should be done,
143	5 to 10 are reasonable number
144	*/
145	return mpz_probab_prime_p( i, reps)>=1 ? 1 : 0;
146}
147
148/* return in <result> the greatest common divisor of <a> and <b> */
149/* <result> := gcd( <a>, <b>) */
150INLINE_DECL bi_ptr bi_gcd( bi_ptr result, bi_ptr a, bi_ptr b) {
151	// result := gcd( a, b)
152	mpz_gcd( result, a, b);
153	return result;
154}
155
156
157/***********************************************************************************
158	INIT/RELEASE LIBRARY
159*************************************************************************************/
160
161/* bi_alloc_p allocation function used only for exporting a bi struct, so for bi_2_nbin
162if define as NULL, a stdlib malloc() will be used */
163void bi_init( void * (*bi_alloc_p)(size_t size)) {
164	time_t start;
165	unsigned long seed;
166	FILE *f;
167#ifdef INTERACTIVE
168	int c, i;
169#endif
170
171	if( initialized == 1) return;
172	if( bi_alloc_p == NULL) bi_alloc = &malloc;
173	else bi_alloc = bi_alloc_p;
174	mpz_init( bi_0);
175	mpz_set_ui( bi_0, 0);
176	mpz_init( bi_1);
177	mpz_set_ui( bi_1, 1);
178	mpz_init( bi_2);
179	mpz_set_ui( bi_2, 2);
180	allocs = list_new();
181	if( allocs == NULL) {
182		LogError("malloc of list failed");
183		return;
184	}
185#ifdef BI_DEBUG
186	printf("bi_init() -> gmp lib\n");
187#endif
188	time( &start);
189	// first try /dev/random, the most secure random generator
190	f = fopen("/dev/random", "r");
191	// in case of failure, but les secure :(
192	if( f== NULL) f = fopen("/dev/urandom", "r");
193	if( f != NULL) {
194		fread( &seed, sizeof(unsigned long int), 1, f);
195		fclose(f);
196	}
197#ifdef INTERACTIVE
198	else {
199		printf("! devices /dev/random and /dev/urandom not found\n");
200		printf("type some characters to generate a random seed (follow by enter)\n");
201		fflush(stdout);
202		i=0;
203		while( (c = fgetc(stdin)) != 10) {
204			time_t temps;
205			time( &temps);
206			seed += temps +( c << i);
207			i++;
208		}
209		time_t temps;
210		time( &temps);
211		seed += temps;
212#ifdef BI_DEBUG
213		printf("temps=%lx\n", temps - start);
214#endif // BI_DEBUG
215		seed = (long)( temps * start);
216	}
217#endif // INTERACTIVE
218#ifdef BI_DEBUG
219	printf("seed=%lx\n", seed);
220#endif
221	gmp_randinit_default( state);
222	gmp_randseed_ui( state, seed);
223	initialized = 1;
224}
225
226void bi_release(void) {
227	if( initialized) {
228		bi_flush_memory();
229		bi_free( bi_0);
230		bi_free( bi_1);
231		bi_free( bi_2);
232		initialized = 0;
233	}
234}
235void bi_flush_memory(void) {
236	node_t *current;
237	list_ptr list = allocs;
238
239	if( list->head == NULL) return; // list is empty
240	else {
241		current = list->head; // go to first node
242		do {
243			LogDebug("[flush memory] free %lx\n", current->obj);
244			free( current->obj);
245			current = current->next; // traverse through the list
246		} while(current != NULL); // until current node is NULL
247	}
248	list_freeall( allocs);
249	allocs = list_new();
250	if( allocs == NULL) {
251		LogError("malloc of list failed");
252		return;
253	}
254}
255
256
257int bi_is_initialized(void) {
258	return initialized;
259}
260
261#endif
262