raw
eucrypt_ch3_mille...    1 /* primegen.c - prime number generation and checks
eucrypt_ch3_mille...    2  *
eucrypt_ch3_mille...    3  * S.MG, 2017
eucrypt_ch3_mille...    4  *
eucrypt_ch3_mille...    5  */
eucrypt_ch3_mille...    6 
eucrypt_ch3_mille...    7 #include <stdlib.h>
eucrypt_ch3_mille...    8 #include <unistd.h>
eucrypt_ch3_mille...    9 #include <assert.h>
eucrypt_ch3_mille...   10 
eucrypt_ch3_mille...   11 #include "smg_rsa.h"
eucrypt_ch3_mille...   12 
eucrypt_ch3_mille...   13 /****************
eucrypt_ch3_mille...   14  * is_composite
eucrypt_ch3_mille...   15  * Returns 1 if it finds evidence that n is composite and 0 otherwise.
eucrypt_ch3_mille...   16  * NB: this is a probabilistic test and its strength is directly linked to:
eucrypt_ch3_mille...   17  *	- the number of witnesses AND
eucrypt_ch3_mille...   18  *	- the quality of the entropy source given as arguments!
eucrypt_ch3_mille...   19  */
eucrypt_ch3_mille...   20 
eucrypt_ch3_mille...   21 int is_composite( MPI n, int nwitnesses, int entropy_source) {
eucrypt_ch3_mille...   22 	int evidence = 0;
eucrypt_ch3_mille...   23 	int nlimbs = mpi_get_nlimbs(n);				/* see MPI representation 	*/
eucrypt_ch3_mille...   24 	unsigned int nbits = mpi_get_nbits(n);				/* used bits				*/
eucrypt_ch3_mille...   25 	unsigned int noctets = (nbits + 7) / 8;	/* source works on octets	*/
eucrypt_ch3_mille...   26 
eucrypt_ch3_mille...   27 	MPI nminus1 = mpi_alloc(nlimbs);			/* n-1 value is used a LOT	*/
eucrypt_ch3_mille...   28 	MPI mpi2 = mpi_alloc_set_ui(2);					/* 2 as MPI 							*/
eucrypt_ch3_mille...   29 	MPI a = mpi_alloc(nlimbs);			/* candidate witness					 		*/
eucrypt_ch3_mille...   30 	MPI y = mpi_alloc(nlimbs); 			/* intermediate values 						*/
eucrypt_ch3_mille...   31 	MPI r = mpi_alloc(nlimbs); 			/* n = 1 + 2^s * r  							*/
eucrypt_ch3_mille...   32 	int s;													/* n = 1 + 2^s * r								*/
eucrypt_ch3_mille...   33 	int j;													/* counter for loops 							*/
eucrypt_ch3_mille...   34 	int nread;							/* number of random octets actually read	*/
eucrypt_ch3_mille...   35 
eucrypt_ch3_mille...   36 	/* precondition: n > 3 */
eucrypt_ch3_mille...   37 	assert( nbits > 2 );
eucrypt_ch3_mille...   38 
eucrypt_ch3_mille...   39 	/* nminus1 = n - 1 as MPI 																				*/
eucrypt_ch3_mille...   40 	mpi_sub_ui( nminus1, n, 1);
eucrypt_ch3_mille...   41 
eucrypt_ch3_mille...   42 	/*
eucrypt_ch3_mille...   43    * find r odd and s so that n = 1 + 2^s * r
eucrypt_ch3_mille...   44 	 * n-1 = 2^s * r
eucrypt_ch3_mille...   45 	 * s is given by the number of trailing zeros of binary n-1
eucrypt_ch3_mille...   46    * r is then obtained as (n-1) / (2^s)
eucrypt_ch3_mille...   47    */
eucrypt_ch3_mille...   48 	s = mpi_trailing_zeros( nminus1 );
eucrypt_ch3_mille...   49 	mpi_tdiv_q_2exp(r, nminus1, s);
eucrypt_ch3_mille...   50 
eucrypt_ch3_mille...   51 	/*
eucrypt_ch3_mille...   52 	 * Investigate randomly chosen candidate witnesses.
eucrypt_ch3_mille...   53 	 * Stop when either:
eucrypt_ch3_mille...   54 			* the specified number of witnesses (nwitnesses) have
eucrypt_ch3_mille...   55 				been investigated OR
eucrypt_ch3_mille...   56 			* a witness for compositeness of n was found
eucrypt_ch3_mille...   57 	 */
eucrypt_ch3_mille...   58 	while (nwitnesses > 0 && evidence == 0) {
eucrypt_ch3_mille...   59 		unsigned char *p = xmalloc(noctets);
eucrypt_ch3_mille...   60 		do {
eucrypt_ch3_mille...   61 			nread = get_random_octets_from(noctets, p, entropy_source);
eucrypt_ch3_mille...   62 		} while (nread != noctets);
eucrypt_ch3_mille...   63 
eucrypt_ch3_mille...   64 		mpi_set_buffer(a, p, noctets, 0);
eucrypt_ch3_mille...   65 
eucrypt_ch3_mille...   66 		/* ensure that a < n-1 by making a maximum nbits-1 long:
eucrypt_ch3_mille...   67 				* clear all bits above nbits-2 in a
eucrypt_ch3_mille...   68 				* keep value of bit nbits-2 in a as it was
eucrypt_ch3_mille...   69 		*/
eucrypt_ch3_mille...   70 		if (mpi_test_bit(a, nbits - 2))
eucrypt_ch3_mille...   71 			mpi_set_highbit(a, nbits - 2);
eucrypt_ch3_mille...   72 		else
eucrypt_ch3_mille...   73 			mpi_clear_highbit(a, nbits - 2);
eucrypt_ch3_mille...   74 
eucrypt_ch3_mille...   75 		/* ensure that 1 < a < n-1; if not, try another random number
eucrypt_ch3_mille...   76 		 * NB: true random means a CAN end up as 0 or 1 here.
eucrypt_ch3_mille...   77 		 */
eucrypt_ch3_mille...   78 		if (mpi_cmp(a, nminus1) < 0 && mpi_cmp_ui(a, 1) > 0) {
eucrypt_ch3_mille...   79 			/* calculate y = a^r mod n */
eucrypt_ch3_mille...   80 			mpi_powm(y, a, r, n);
eucrypt_ch3_mille...   81 			if (mpi_cmp_ui(y, 1) && mpi_cmp(y, nminus1)) {
eucrypt_ch3_mille...   82 				j = 1;
eucrypt_ch3_mille...   83 				while ( (j < s)	&& mpi_cmp(y, nminus1) && (evidence == 0) ) {
eucrypt_ch3_mille...   84 					/* calculate y = y^2 mod n */
eucrypt_ch3_mille...   85 					mpi_powm(y, y, mpi2, n);
eucrypt_ch3_mille...   86 					if (mpi_cmp_ui(y, 1) == 0)
eucrypt_ch3_mille...   87 						evidence = 1;
eucrypt_ch3_mille...   88 					j = j + 1;
eucrypt_ch3_mille...   89 				}	/* end while */
eucrypt_ch3_mille...   90 				if (mpi_cmp(y, nminus1))
eucrypt_ch3_mille...   91 					evidence = 1;
eucrypt_ch3_mille...   92 			}	/* end if y != 1 and y != n-1 */
eucrypt_ch3_mille...   93 			nwitnesses = nwitnesses - 1;
eucrypt_ch3_mille...   94 		}	/* end if 1 < a < n-1 */
eucrypt_ch3_mille...   95 		xfree(p);
eucrypt_ch3_mille...   96 	}	/* end while for investigating candidate witnesses */
eucrypt_ch3_mille...   97 
eucrypt_ch3_mille...   98 	mpi_free( nminus1 );
eucrypt_ch3_mille...   99 	mpi_free( mpi2 );
eucrypt_ch3_mille...  100 	mpi_free( a );
eucrypt_ch3_mille...  101 	mpi_free( y );
eucrypt_ch3_mille...  102 	mpi_free( r );
eucrypt_ch3_mille...  103 
eucrypt_ch3_mille...  104 	return evidence;
eucrypt_ch3_mille...  105 }
eucrypt_ch4_rpng      106 
eucrypt_ch4_rpng      107 /**
eucrypt_ch4_rpng      108  * Generates a random number that has passed the Miller-Rabin test for primality (see function is_composite above).
eucrypt_ch4_rpng      109  * NB: top 2 bits and bottom bit are ALWAYS 1! (i.e. a mask 11.....1 is applied)
eucrypt_ch4_rpng      110  *    a prime of 8*noctets long will have only 8*noctets-3 bits that are randomly chosen
eucrypt_ch4_rpng      111  * NB: this method does NOT allocate space for the requested MPI; it is the caller's responsibility to allocate it!
eucrypt_ch4_rpng      112  * The source of randomness is ENTROPY_SOURCE in eucrypt/smg_rsa/include/knobs.h
eucrypt_ch4_rpng      113  * The number of witnesses checked by Miller-Rabin is M_R_ITERATIONS in eucrypt/smg_rsa/include/knobs.h
eucrypt_ch4_rpng      114  * Preconditions:
eucrypt_ch4_rpng      115  *			noctets > 0 (at least one octet!)
eucrypt_ch4_rpng      116  *			memory allocated for noctets in output MPI
eucrypt_ch4_rpng      117  *			successful access to the entropy source
eucrypt_ch4_rpng      118  */
eucrypt_ch4_rpng      119 void gen_random_prime( unsigned int noctets, MPI output )
eucrypt_ch4_rpng      120 {
eucrypt_ch4_rpng      121 	/* precondition: at least one octet long */
eucrypt_ch4_rpng      122 	assert(noctets > 0);
eucrypt_ch4_rpng      123 
eucrypt_ch4_rpng      124 	/* precondition: enough memory allocated for the limbs corresponding to noctets */
eucrypt_ch4_rpng      125 	unsigned int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
eucrypt_ch4_rpng      126 	assert(mpi_get_alloced(output) >= nlimbs);
eucrypt_ch4_rpng      127 
eucrypt_ch4_rpng      128 	/* precondition: access to the entropy source */
eucrypt_ch4_rpng      129 	int entropy_source = open_entropy_source(ENTROPY_SOURCE); /* source of random bits */
eucrypt_ch4_rpng      130 	assert(entropy_source >= 0);
eucrypt_ch4_rpng      131 
eucrypt_ch4_rpng      132 	unsigned int nbits = 8*noctets;														/* length of MPI in bits */
eucrypt_ch4_rpng      133 
eucrypt_ch4_rpng      134 	/*
eucrypt_ch4_rpng      135    * loop until a prime is found: get noctets of random bits, trim and apply 110...01 mask, check if prime
eucrypt_ch4_rpng      136 	 */
eucrypt_ch4_rpng      137 	unsigned char *p = xmalloc( noctets );
eucrypt_ch4_rpng      138 	do {
eucrypt_ch4_rpng      139 		get_random_octets_from( noctets, p, entropy_source );
eucrypt_ch4_rpng      140 		mpi_set_buffer( output, p, noctets, 0);	/* convert to MPI representation */
eucrypt_ch4_rpng      141 		mpi_set_highbit( output, nbits - 1 );		/* trim at required size and set top bit */
eucrypt_ch4_rpng      142 		mpi_set_bit( output, nbits - 2);					/* set second top bit */
eucrypt_ch4_rpng      143 		mpi_set_bit( output, 0 );								/* set bottom bit to unsure odd number */
eucrypt_ch4_rpng      144 	}	while (is_composite(output, M_R_ITERATIONS, entropy_source));
eucrypt_ch4_rpng      145 
eucrypt_ch4_rpng      146 	/* tidy up, a prime was found */
eucrypt_ch4_rpng      147 	xfree(p);
eucrypt_ch4_rpng      148 	close(entropy_source);
eucrypt_ch4_rpng      149 }