1/* 2 * Licensed Materials - Property of IBM 3 * 4 * trousers - An open source TCG Software Stack 5 * 6 * (C) Copyright International Business Machines Corp. 2006 7 * 8 */ 9 10#include <stdlib.h> 11#include <stdio.h> 12#include <string.h> 13#include <errno.h> 14 15#include "bi.h" 16#include "list.h" 17#include "daa_structs.h" 18#include "daa_parameter.h" 19#include "issuer.h" 20 21static const int ELEMENT = 0; 22static const int EXPONENT = 1; 23 24extern void prime_init(); 25extern void compute_safe_prime(bi_ptr result, int bit_length, int prime_certainty); 26 27bi_ptr 28compute_random_number_star( bi_ptr result, const bi_ptr element) 29{ 30 bi_t bi_tmp; 31 32 bi_new(bi_tmp); 33 do { 34 compute_random_number(result, element); 35 } while (!bi_equals_si(bi_gcd(bi_tmp, result, element), 1)); 36 37 bi_free(bi_tmp); 38 39 return result; 40} 41 42/* Compute a generator of the group of quadratic residue modulo n. The 43 * generator will not be part of the subgroup of size 2. 44 * n: modulus */ 45void 46compute_generator_quadratic_residue(bi_t qr, bi_t n) 47{ 48 bi_t bi_tmp, bi_tmp1; 49 50 bi_new(bi_tmp); 51 bi_new(bi_tmp1); 52 53 do { 54 compute_random_number(qr, n); 55 // qr = (qr ^ bi_2) % n 56 bi_mod_exp(qr, qr, bi_2, n); 57 } while (bi_cmp_si(qr, 1) == 0 || 58 bi_cmp_si(bi_gcd(bi_tmp, n, bi_sub_si(bi_tmp1, qr, 1)), 1) != 0); 59 60 bi_free(bi_tmp); 61 bi_free(bi_tmp1); 62} 63 64void 65compute_group_element(bi_ptr result[], 66 bi_ptr generator, 67 bi_ptr product_PQprime, 68 bi_ptr n) 69{ 70 bi_t bi_tmp; 71 72 bi_new(bi_tmp); 73 compute_random_number(bi_tmp, product_PQprime); 74 75 // bi_tmp++ 76 bi_inc(bi_tmp); 77 78 // result[ELEMENT] := (generator ^ bi_tmp) mod n 79 bi_mod_exp(result[ELEMENT], generator, bi_tmp, n); 80 bi_set(result[EXPONENT], bi_tmp); 81 bi_free(bi_tmp); 82} 83 84 85TSS_RESULT 86generate_key_pair(UINT32 num_attributes_issuer, 87 UINT32 num_attributes_receiver, 88 UINT32 base_nameLength, 89 BYTE* base_name, 90 KEY_PAIR_WITH_PROOF_internal** key_pair_with_proof) 91{ 92 TSS_RESULT result = TSS_SUCCESS; 93 int length_mod = DAA_PARAM_SIZE_RSA_MODULUS; 94 int length; 95 int i; 96 TSS_DAA_PK_internal *public_key = NULL; 97 BYTE *buffer = NULL; 98 bi_ptr pPrime = NULL; 99 bi_ptr qPrime = NULL; 100 bi_ptr n = NULL; 101 bi_ptr p = NULL; 102 bi_ptr q = NULL; 103 bi_ptr capital_s = NULL; 104 bi_ptr capital_z = NULL; 105 bi_ptr product_PQprime = NULL; 106 bi_ptr pair[2] = {NULL, NULL}; 107 bi_ptr xz = NULL; 108 bi_ptr capital_r0 = NULL; 109 bi_ptr x0 = NULL; 110 bi_ptr capital_r1 = NULL; 111 bi_ptr x1 = NULL; 112 bi_array_ptr x = NULL; 113 bi_array_ptr capital_r = NULL; 114 bi_array_ptr capitalRReceiver = NULL; 115 bi_array_ptr capitalRIssuer = NULL; 116 bi_ptr gamma = NULL; 117 bi_ptr capital_gamma = NULL; 118 bi_ptr rho = NULL; 119 bi_ptr r = NULL; 120 bi_ptr rho_double = NULL; 121 bi_t bi_tmp, bi_tmp1, bi_tmp2; 122 123 bi_new(bi_tmp); 124 bi_new(bi_tmp1); 125 bi_new(bi_tmp2); 126 *key_pair_with_proof = NULL; 127 128 // STEP 1 129 LogDebug("Step 1 of 8 - compute modulus n (please wait: long process)\n"); 130 131 // FUTURE USAGE if( IS_DEBUG==0) 132 prime_init(); 133 p = bi_new_ptr(); 134 q = bi_new_ptr(); 135 n = bi_new_ptr(); 136 137 do { 138 // FUTURE USAGE 139 /* compute_safe_prime( p, length_mod / 2); 140 do { 141 compute_safe_prime( q, 142 length_mod - (length_mod >> 1)); 143 } while( bi_cmp( p, q) ==0); 144 } else */ 145 { 146 bi_generate_safe_prime(p, length_mod / 2); 147 bi_generate_safe_prime(q, length_mod - (length_mod / 2)); 148 LogDebug("."); 149 } 150 // n = p*q 151 bi_mul(n, p, q); 152 } while(bi_length(n) != length_mod); 153 154 pPrime = bi_new_ptr(); 155 bi_sub(pPrime, p, bi_1); 156 157 // pPrime = (p - 1) >> 1 158 bi_shift_right(pPrime, pPrime, 1); 159 qPrime = bi_new_ptr(); 160 bi_sub(qPrime, q, bi_1); 161 162 // qPrime = (q - 1) >> 1 163 bi_shift_right( qPrime, qPrime, 1); 164 if (bi_is_probable_prime(pPrime) == 0) { 165 LogError("!! pPrime not a prime number: %s", bi_2_hex_char(pPrime)); 166 result = TSPERR(TSS_E_INTERNAL_ERROR); 167 goto close; 168 } 169 if (bi_is_probable_prime(qPrime) == 0) { 170 LogError("!! qPrime not a prime number: %s", bi_2_hex_char(qPrime)); 171 result = TSPERR(TSS_E_INTERNAL_ERROR); 172 goto close; 173 } 174 LogDebug("p=%s", bi_2_hex_char(p)); 175 LogDebug("q=%s", bi_2_hex_char(q)); 176 LogDebug("n=%s", bi_2_hex_char(n)); 177 178 // STEP 2 179 LogDebug("Step 2 - choose random generator of QR_n"); 180 capital_s = bi_new_ptr(); 181 compute_generator_quadratic_residue(capital_s, n); 182 LogDebug("capital_s=%s", bi_2_hex_char(capital_s)); 183 184 // STEP 3 & 4 185 LogDebug("Step 3 & 4 - compute group elements"); 186 product_PQprime = bi_new_ptr(); 187 bi_mul( product_PQprime, pPrime, qPrime); 188 pair[ELEMENT] = bi_new_ptr(); 189 pair[EXPONENT] = bi_new_ptr(); 190 191 LogDebug("product_PQprime=%s [%ld]", bi_2_hex_char(product_PQprime), 192 bi_nbin_size(product_PQprime)); 193 194 compute_group_element(pair, capital_s, product_PQprime, n); 195 capital_z = bi_new_ptr(); 196 bi_set(capital_z, pair[ELEMENT]); 197 xz = bi_new_ptr(); 198 bi_set(xz, pair[EXPONENT]); 199 200 // attributes bases 201 compute_group_element(pair, capital_s, product_PQprime, n); 202 capital_r0 = bi_new_ptr(); 203 bi_set(capital_r0, pair[ELEMENT]); 204 x0 = bi_new_ptr(); 205 bi_set(x0, pair[EXPONENT]); 206 207 compute_group_element(pair, capital_s, product_PQprime, n); 208 capital_r1 = bi_new_ptr(); 209 bi_set(capital_r1, pair[ELEMENT]); 210 x1 = bi_new_ptr(); 211 bi_set(x1, pair[EXPONENT]); 212 213 // additional attribute bases 214 length = num_attributes_issuer + num_attributes_receiver; 215 x = ALLOC_BI_ARRAY(); 216 bi_new_array(x, length); 217 capital_r = ALLOC_BI_ARRAY(); 218 bi_new_array(capital_r, length); 219 220 for (i = 0; i < length; i++) { 221 compute_group_element(pair, capital_s, product_PQprime, n); 222 bi_set(capital_r->array[i], pair[ELEMENT]); 223 bi_set(x->array[i], pair[EXPONENT]); 224 } 225 226 // split capitalR into Receiver and Issuer part 227 capitalRReceiver = ALLOC_BI_ARRAY(); 228 bi_new_array2(capitalRReceiver, num_attributes_receiver); 229 for (i = 0; i < num_attributes_receiver; i++) 230 capitalRReceiver->array[i] = capital_r->array[i]; 231 capitalRIssuer = ALLOC_BI_ARRAY(); 232 bi_new_array2(capitalRIssuer, num_attributes_issuer); 233 for (i = 0; i < num_attributes_issuer; i++) 234 capitalRIssuer->array[i] = capital_r->array[i + num_attributes_receiver]; 235 236 // STEP 6a 237 LogDebug("Step 6"); 238 gamma = bi_new_ptr(); 239 capital_gamma = bi_new_ptr(); 240 rho = bi_new_ptr(); 241 r = bi_new_ptr(); 242 rho_double = bi_new_ptr(); 243 244 bi_generate_prime(rho, DAA_PARAM_SIZE_RHO); 245 if (bi_length(rho) != DAA_PARAM_SIZE_RHO) { 246 LogError("rho bit length=%ld", bi_length(rho)); 247 result = TSPERR(TSS_E_INTERNAL_ERROR); 248 goto close; 249 } 250 251 do { 252 length = DAA_PARAM_SIZE_MODULUS_GAMMA - DAA_PARAM_SIZE_RHO; 253 do { 254 bi_urandom(r, length); 255 } while(bi_length(r) != length || bi_equals_si(bi_mod(bi_tmp, r, rho), 0)); 256 257 // rho is not a dividor of r 258 bi_mul( capital_gamma, rho, r); 259 // capital_gamma ++ 260 bi_inc( capital_gamma); 261#ifdef DAA_DEBUG 262 if (bi_length(capital_gamma) != DAA_PARAM_SIZE_MODULUS_GAMMA) { 263 printf("|"); fflush(stdout); 264 } else { 265 printf("."); fflush(stdout); 266 } 267#endif 268 } while (bi_length(capital_gamma) != DAA_PARAM_SIZE_MODULUS_GAMMA || 269 bi_is_probable_prime(capital_gamma) == 0 ); 270 271 // STEP 6b 272 if (bi_equals(bi_sub_si(bi_tmp, capital_gamma, 1), 273 bi_mod(bi_tmp1, bi_mul(bi_tmp2, rho, r), n)) == 0) { 274 LogWarn("capital_gamma-1 != (rho * r) mod n tmp=%s tmp1=%s", 275 bi_2_hex_char(bi_tmp), bi_2_hex_char(bi_tmp1)); 276 } 277 278 if (bi_equals(bi_div(bi_tmp, bi_sub_si(bi_tmp1, capital_gamma, 1), rho), r ) == 0) { 279 LogWarn("( capital_gamma - 1)/rho != r"); 280 } 281 282 LogDebug("capital_gamma=%s\n", bi_2_hex_char(capital_gamma)); 283 do { 284 compute_random_number_star(gamma, capital_gamma); 285 // gamma = (gamma ^ r) mod capital_gamma 286 bi_mod_exp(gamma, gamma, r, capital_gamma); 287 } while (bi_equals(gamma, bi_1)); 288 // STEP 7 289 buffer = (BYTE *)malloc(base_nameLength); 290 if (buffer == NULL) { 291 LogError("malloc of %u bytes failed", base_nameLength); 292 result = TSPERR(TSS_E_OUTOFMEMORY); 293 goto close; 294 } 295 memcpy(buffer, base_name, base_nameLength); 296 // all fields are linked to the struct with direct reference 297 public_key = create_DAA_PK(n, capital_s, capital_z, capital_r0, capital_r1, gamma, 298 capital_gamma, rho, capitalRReceiver, capitalRIssuer, 299 base_nameLength, buffer); 300 301 // STEP 8 302 // TODO dynamically load DAAKeyCorrectnessProof 303 LogDebug("Step 8: generate proof (please wait: long process)"); 304 TSS_DAA_PK_PROOF_internal *correctness_proof = generate_proof(product_PQprime, public_key, 305 xz, x0, x1, x); 306 if (correctness_proof == NULL) { 307 LogError("creation of correctness_proof failed"); 308 result = TSPERR(TSS_E_OUTOFMEMORY); 309 goto close; 310 } 311 312 *key_pair_with_proof = (KEY_PAIR_WITH_PROOF_internal *) 313 malloc(sizeof(KEY_PAIR_WITH_PROOF_internal)); 314 if (*key_pair_with_proof == NULL) { 315 LogError("malloc of %zd bytes failed", sizeof(KEY_PAIR_WITH_PROOF_internal)); 316 result = TSPERR(TSS_E_OUTOFMEMORY); 317 goto close; 318 } 319 320 (*key_pair_with_proof)->pk = public_key; 321 (*key_pair_with_proof)->proof = correctness_proof; 322 // all fields are linked to the struct with direct reference 323 (*key_pair_with_proof)->private_key = create_TSS_DAA_PRIVATE_KEY(pPrime, qPrime); 324close: 325 if (result != TSS_SUCCESS) { 326 // remove everything, even numbers that should be stored in a struct 327 FREE_BI(pPrime); // kept if no error 328 FREE_BI(qPrime); // kept if no error 329 FREE_BI(n); // kept if no error 330 // FREE_BI( p); 331 // FREE_BI( q); 332 FREE_BI(capital_s); // kept if no error 333 FREE_BI(capital_z); // kept if no error 334 // FREE_BI(product_PQprime); 335 // FREE_BI(pair[ELEMENT]); 336 // FREE_BI(pair[EXPONENT]); 337 // FREE_BI(xz); 338 FREE_BI(capital_r0); // kept if no error 339 // FREE_BI(x0); 340 FREE_BI(capital_r1); // kept if no error 341 // FREE_BI( x1); 342 // bi_array_ptr x = NULL; 343 // bi_array_ptr capital_r = NULL; 344 // bi_array_ptr capitalRReceiver = NULL; 345 // bi_array_ptr capitalRIssuer = NULL; 346 FREE_BI( gamma); // kept if no error 347 FREE_BI( capital_gamma); // kept if no error 348 FREE_BI( rho); // kept if no error 349 // FREE_BI( r); 350 // FREE_BI( rho_double); 351 if (buffer!=NULL) 352 free(buffer); 353 354 if (public_key != NULL) 355 free(public_key); 356 357 if (*key_pair_with_proof != NULL) 358 free(*key_pair_with_proof); 359 } 360 /* 361 Fields kept by structures 362 TSS_DAA_PK: n 363 capital_s 364 capital_z 365 capital_r0 366 capital_r1 367 gamma 368 capital_gamma 369 rho 370 capitalRReceiver 371 capitalRIssuer 372 base_nameLength 373 buffer 374 TSS_DAA_PRIVATE_KEY: 375 pPrime 376 qPrime 377 */ 378 bi_free(bi_tmp); 379 bi_free(bi_tmp1); 380 bi_free(bi_tmp2); 381 FREE_BI(p); 382 FREE_BI(q); 383 FREE_BI(product_PQprime); 384 FREE_BI(pair[ELEMENT]); 385 FREE_BI(pair[EXPONENT]); 386 FREE_BI(xz); 387 FREE_BI(x0); 388 FREE_BI(x0); 389 // bi_array_ptr x = NULL; 390 // bi_array_ptr capital_r = NULL; 391 // bi_array_ptr capitalRReceiver = NULL; 392 // bi_array_ptr capitalRIssuer = NULL; 393 FREE_BI(r); 394 FREE_BI(rho_double); 395 396 return result; 397} 398