-
+ 992C1ED9B3037031C841DB0BB5D6467D2142ACCE1E9B67DDF91D1661D7A9731452D2F2D95222AAC51EE7672A781FD2BB195692D3949E14EAF46B8E29D2243FE0
smg_comms/rsa/primegen.c

(0 . 0)(1 . 152)
/* primegen.c - prime number generation and checks
 *
 * S.MG, 2017
 *
 */

#include <stdlib.h>
#include <unistd.h>
#include <assert.h>

#include "smg_rsa.h"

/****************
 * is_composite
 * Returns 1 if it finds evidence that n is composite and 0 otherwise.
 * NB: this is a probabilistic test and its strength is directly linked to:
 *	- the number of witnesses AND
 *	- the quality of the entropy source given as arguments!
 */

int is_composite( MPI n, int nwitnesses, int entropy_source) {
	int evidence = 0;
	int nlimbs = mpi_get_nlimbs(n);				/* see MPI representation 	*/
	unsigned int nbits = mpi_get_nbits(n);				/* used bits				*/
	unsigned int noctets = (nbits + 7) / 8;	/* source works on octets	*/

	MPI nminus1 = mpi_alloc(nlimbs);			/* n-1 value is used a LOT	*/
	MPI mpi2 = mpi_alloc_set_ui(2);					/* 2 as MPI 							*/
	MPI a = mpi_alloc(nlimbs);			/* candidate witness					 		*/
	MPI y = mpi_alloc(nlimbs); 			/* intermediate values 						*/
	MPI r = mpi_alloc(nlimbs); 			/* n = 1 + 2^s * r  							*/
	int s;													/* n = 1 + 2^s * r								*/
	int j;													/* counter for loops 							*/
	int nread;							/* number of random octets actually read	*/

	/* precondition: n > 3 */
	assert( nbits > 2 );

	/* nminus1 = n - 1 as MPI 																				*/
	mpi_sub_ui( nminus1, n, 1);

	/*
   * find r odd and s so that n = 1 + 2^s * r
	 * n-1 = 2^s * r
	 * s is given by the number of trailing zeros of binary n-1
   * r is then obtained as (n-1) / (2^s)
   */
	s = mpi_trailing_zeros( nminus1 );
	mpi_tdiv_q_2exp(r, nminus1, s);

	/*
	 * Investigate randomly chosen candidate witnesses.
	 * Stop when either:
			* the specified number of witnesses (nwitnesses) have
				been investigated OR
			* a witness for compositeness of n was found
	 */
	while (nwitnesses > 0 && evidence == 0) {
		unsigned char *p = xmalloc(noctets);
		do {
			nread = get_random_octets_from(noctets, p, entropy_source);
		} while (nread != noctets);

		mpi_set_buffer(a, p, noctets, 0);

		/* ensure that a < n-1 by making a maximum nbits-1 long:
				* clear all bits above nbits-2 in a
				* keep value of bit nbits-2 in a as it was
		*/
		if (mpi_test_bit(a, nbits - 2))
			mpi_set_highbit(a, nbits - 2);
		else
			mpi_clear_highbit(a, nbits - 2);

		/* ensure that 1 < a < n-1; if not, try another random number
		 * NB: true random means a CAN end up as 0 or 1 here.
		 */
		if (mpi_cmp(a, nminus1) < 0 && mpi_cmp_ui(a, 1) > 0) {
			/* calculate y = a^r mod n */
			mpi_powm(y, a, r, n);
			if (mpi_cmp_ui(y, 1) && mpi_cmp(y, nminus1)) {
				j = 1;
				while ( (j < s)	&& mpi_cmp(y, nminus1) && (evidence == 0) ) {
					/* calculate y = y^2 mod n */
					mpi_powm(y, y, mpi2, n);
					if (mpi_cmp_ui(y, 1) == 0)
						evidence = 1;
					j = j + 1;
				}	/* end while */
				if (mpi_cmp(y, nminus1))
					evidence = 1;
			}	/* end if y != 1 and y != n-1 */
			nwitnesses = nwitnesses - 1;
		}	/* end if 1 < a < n-1 */
		xfree(p);
	}	/* end while for investigating candidate witnesses */

	mpi_free( nminus1 );
	mpi_free( mpi2 );
	mpi_free( a );
	mpi_free( y );
	mpi_free( r );

	return evidence;
}

/**
 * Generates a random number that has passed the Miller-Rabin test for primality (see function is_composite above).
 * NB: top 2 bits and bottom bit are ALWAYS 1! (i.e. a mask 11.....1 is applied)
 *    a prime of 8*noctets long will have only 8*noctets-3 bits that are randomly chosen
 * NB: this method does NOT allocate space for the requested MPI; it is the caller's responsibility to allocate it!
 * The source of randomness is ENTROPY_SOURCE in eucrypt/smg_rsa/include/knobs.h
 * The number of witnesses checked by Miller-Rabin is M_R_ITERATIONS in eucrypt/smg_rsa/include/knobs.h
 * Preconditions:
 *			noctets > 0 (at least one octet!)
 *			memory allocated for noctets in output MPI
 *			successful access to the entropy source
 */
void gen_random_prime( unsigned int noctets, MPI output )
{
	/* precondition: at least one octet long */
	assert(noctets > 0);

	/* precondition: enough memory allocated for the limbs corresponding to noctets */
	unsigned int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
	assert(mpi_get_alloced(output) >= nlimbs);

	/* precondition: access to the entropy source */
	int entropy_source = open_entropy_source(ENTROPY_SOURCE); /* source of random bits */
	assert(entropy_source >= 0);

	unsigned int nbits = 8*noctets;														/* length of MPI in bits */

	/*
   * loop until a prime is found: get noctets of random bits, trim and apply 110...01 mask, check if prime
	 */
	unsigned char *p = xmalloc( noctets );
  int nread;
	do {
    do {
      nread = get_random_octets_from( noctets, p, entropy_source );
    } while ( nread != noctets );
		mpi_set_buffer( output, p, noctets, 0);	/* convert to MPI representation */
		mpi_set_highbit( output, nbits - 1 );		/* trim at required size and set top bit */
		mpi_set_bit( output, nbits - 2);					/* set second top bit */
		mpi_set_bit( output, 0 );								/* set bottom bit to unsure odd number */
	}	while (is_composite(output, M_R_ITERATIONS, entropy_source));

	/* tidy up, a prime was found */
	xfree(p);
	close(entropy_source);
}