-
+ D5A314BAA0F6D77B60210629541A02F8DD8923A03D0003A2005E46DCAC8022780577CF2D584BB869FD241A367153854838FBE88B46380914EDB6F35946B457DD
eucrypt/smg_rsa/primegen.c

(0 . 0)(1 . 105)
/* 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;
}