daa/daa_issuer/prime_gen.c

2  * Licensed Materials - Property of IBM
4  * trousers - An open source TCG Software Stack
6  * (C) Copyright International Business Machines Corp. 2004, 2005
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include <string.h>
14 #include "bi.h"
15 #include "list.h"
16 #include "tsplog.h"
21 /* Generates a random number of bit_length bit length. The first two bits and the last bit of this
22  * number are always set, therefore the number is odd and >= (2^(bit_length-1)+2^(bit_length-2)+1)
24  * bit_length: The length of the number to be generated, in bits
25  * return: a random number of bitLength bit length with first and last bits set
30 	if (bit_length > 0) {
33 		bi_setbit(bi, 0);
34 		bi_setbit(bi, bit_length - 1);
35 		bi_setbit(bi, bit_length - 2);
39 /* This method generates small prime numbers up to a specified bounds using the Sieve of
40  * Eratosthenes algorithm.
42  * prime_bound: the upper bound for the primes to be generated
43  * starting_prime: the first prime in the list of primes that is returned
44  * return: list of primes up to the specified bound. Each prime is of type bi_ptr
52 	int i;
53 	int k;
57 	primes_length = 0;
58 	res = list_new();
59 	if (allocs == NULL) {
63 	if ((prime_bound <= 1) || (starting_prime > prime_bound))
66 	if (starting_prime <= 2) {
67 		starting_prime = 2;
70 	length = (prime_bound - 1) >> 1; // length = (prime_bound -1) / 2;
71 	is_primes = (int *)malloc(sizeof(int)*length);
72 	if (is_primes == NULL) {
73 		LogError("malloc of %zd bytes failed", sizeof(int) * length);
77 	for (i = 0; i < length; i++)
78 		is_primes[i] = 1;
80 	for (i = 0; i < length; i++) {
81 		if (is_primes[i] == 1) {
82 			prime = 2 * i + 3;
83 			for (k = i + prime; k < length; k+= prime)
84 				is_primes[k] = 0;
86 			if (prime >= starting_prime) {
88 				primes_length++;
92 	// converti the list to a table
93 	current = res->head; // go to first node
94 	primes  = (unsigned long *)malloc(sizeof(unsigned long) * primes_length);
95 	if (primes == NULL) {
96 		LogError("malloc of %d bytes failed",
101 	i = 0;
102 	while (current != NULL) {
103 		primes[i++] = (unsigned long)current->obj;
104 		current = current->next; // traverse through the list
114 	generate_small_primes(16384, 3);
117 /* Test whether the provided pDash or p = 2*pDash + 1 are divisible by any of the small primes
118  * saved in the listOfSmallPrimes. A limit for the largest prime to be tested against can be
119  * specified, but it will be ignored if it exeeds the number of precalculated primes.
121  * p_dash: the number to be tested (p_dash)
122  * prime_bound: the limit for the small primes to be tested against.
127 	int sievePassed = 1;
128 	unsigned long r;
132 	small_prime = 1;
133 	int i = 0;
134 	while (i < primes_length && small_prime < prime_bound ) {
135 		small_prime = primes[i++];
136 		// r = p_dash % small_prime
138 		r = bi_get_si(temp);
139 		// test if pDash = 0 (mod smallPrime)
140 		if (r == 0) {
141 			sievePassed = 0;
144 		// test if p = 0 (mod smallPrime) (or r == smallPrime - r - 1)
145 		if (r == (small_prime - r - 1)) {
146 			sievePassed = 0;
155 /* Tests if a is a Miller-Rabin witness for n
157  * a: number which is supposed to be the witness
158  * n: number to be tested against
159  * return: true if a is Miller-Rabin witness for n, false otherwise
162 is_miller_rabin_witness(const bi_ptr a, const bi_ptr n)
167 	bi_t u;
170 	int t = -1;
171 	int i;
176 	bi_new(u);
178 	// n1 = n - 1
179 	bi_sub_si(n_1, n, 1);
181 	// test if n-1 = 2^t*u with t >= 1 && u even
183 		t++;
184 		// _2_power_t = bi_1 << t  ( ==  2 ^ t)
185 		bi_shift_left(_2_power_t, bi_1, t);
186 		// u = n_1 / (2 ^ t)
187 		bi_div(u, n_1, _2_power_t);
188 	} while (bi_equals_si(bi_mod(temp, u, bi_2), 0));
193 	// x1 = (a ^ u ) % n
194 	bi_mod_exp(x1, a, u, n);
196 	// finished to use u, _2_power_t and temp
197 	bi_free(u);
200 	for (i = 0; i < t; i++) {
203 		// x1 = (x0 ^ 2) % n
204 		bi_mod_exp(x1, x0, bi_2, n);
205 		if (bi_equals_si(x1, 1) && !bi_equals_si(x0, 1) && !bi_equals(x0, n_1) != 0) {
209 			return 1;
218 		return 1;
220 	return 0;
228 		bi_generate_prime(result, bit_length-1);
229 		bi_shift_left(result, result, 1);	// result := result << 1
230 		bi_add_si(result, result, 1);	// result := result -1
231 		if (getenv("TSS_DEBUG_OFF") == NULL) {
232 			printf(".");
235 	} while (bi_is_probable_prime(result)==0);
240 /* The main method to compute a random safe prime of the specified bit length.
241  * IMPORTANT: The computer prime will have two first bits and the last bit set to 1 !!
242  * i.e. > (2^(bitLength-1)+2^(bitLength-2)+1). This is done to be sure that if two primes of
243  * bitLength n are multiplied, the result will have the bitLenght of 2*n exactly This
245  * Schemes Based on the strong RSA Assumption" May 9, 2000.
247  * bitLength: the bit length of the safe prime to be computed.
248  * return: a number which is considered to be safe prime
251 compute_safe_prime(bi_ptr p, int bit_length)
259 	LogDebug("compute Safe Prime: length: %d bits\n", bit_length);
261 	p_dash = bi_new_ptr();
262 	temp_p = bi_new_ptr();
263 	p_minus_1 = bi_new_ptr();
266 	 * number of Miller-Rabin primality tests at the end */
267 	if (bit_length <= 256) {
268 		prime_bound = 768;
269 	} else if (bit_length <= 512) {
270 		prime_bound = 3072;
271 	} else if (bit_length <= 768) {
272 		prime_bound = 6144;
273 	} else if (bit_length <= 1024) {
274 		prime_bound = 1024;
276 		prime_bound = 16384;
280 		stop = 0;
281 		/* p_dash = generated random with basic bit settings (odd) */
282 		random_odd_bi(p_dash, bit_length - 1);
284 		if (test_small_prime_factors(p_dash, prime_bound) == 0)  {
285 			LogDebugFn("1");
288 		/* test if p_dash or p are divisible by some small primes */
290 			LogDebugFn("2");
293 		/* test if 2^(pDash) = +1/-1 (mod p)
294 		 * bi can not handle negative operation, we compare to (p-1) instead of -1
295 		 * calculate p = 2*pDash+1 -> (pDash << 1) + 1
297 		bi_shift_left(p, p_dash, 1);
298 		bi_add(p, p, bi_1);
300 		// p_minus_1:= p - 1
301 		bi_sub(p_minus_1, p, bi_1);
303 		//  temp_p := ( 2 ^ p_dash ) mod p
304 		bi_mod_exp(temp_p, bi_2, p_dash, p);
305 		if (!bi_equals_si(temp_p, 1)  && !bi_equals(temp_p, p_minus_1) ) {
306 			LogDebugFn("3");
310 		// test if pDash or p are divisible by some small primes
312 			LogDebugFn("4");
317 			stop = 1;
318 	} while (stop == 0);
324 	LogDebug("found Safe Prime: %s bits", bi_2_hex_char(p));
326 	return p;