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 }