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
22 gmp_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 */
28 static int reps = 20;
29
30 static int initialized = 0;
31 void * (*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> */
bi_nbin_size(const bi_ptr i)40 long 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> */
bi_2_nbin(int * length,const bi_ptr i)49 unsigned 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 */
bi_2_nbin1(int * length,unsigned char * buffer,const bi_ptr i)59 void 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> */
bi_set_as_nbin(const unsigned long length,const unsigned char * buffer)64 INLINE_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> */
bi_multi_mod_exp(bi_ptr result,const int n,const bi_t g[],const long e[],const int m)79 bi_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 */
bi_generate_prime(bi_ptr result,const long length)108 INLINE_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 */
bi_generate_safe_prime(bi_ptr result,long length)122 INLINE_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 */
bi_is_probable_prime(bi_ptr i)139 INLINE_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>) */
bi_gcd(bi_ptr result,bi_ptr a,bi_ptr b)150 INLINE_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
162 if define as NULL, a stdlib malloc() will be used */
bi_init(void * (* bi_alloc_p)(size_t size))163 void 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
bi_release(void)226 void 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 }
bi_flush_memory(void)235 void 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
bi_is_initialized(void)257 int bi_is_initialized(void) {
258 return initialized;
259 }
260
261 #endif
262