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
21 static const int ELEMENT = 0;
22 static const int EXPONENT = 1;
23
24 extern void prime_init();
25 extern void compute_safe_prime(bi_ptr result, int bit_length, int prime_certainty);
26
27 bi_ptr
compute_random_number_star(bi_ptr result,const bi_ptr element)28 compute_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 */
45 void
compute_generator_quadratic_residue(bi_t qr,bi_t n)46 compute_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
64 void
compute_group_element(bi_ptr result[],bi_ptr generator,bi_ptr product_PQprime,bi_ptr n)65 compute_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
85 TSS_RESULT
generate_key_pair(UINT32 num_attributes_issuer,UINT32 num_attributes_receiver,UINT32 base_nameLength,BYTE * base_name,KEY_PAIR_WITH_PROOF_internal ** key_pair_with_proof)86 generate_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);
324 close:
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