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