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