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