- F8B433355F471B6EA164813B4927B36D389177AF169F39E25C04B3A043DE367A88B8F07A6FE6EB92C851B9E20FA1B8EE0D1EC25E53A9F51477914F1A38EC1D5B
+ 36AA7BC45976C3792B00414443B35C0DE1C172B5D2DDF26FF62736CF8642F3D2260FD45216F075DA1024A27CED6E03004A41CC3A7508877462A7A06C11EA4339
eucrypt/mpi/mpi-bit.c

(162 . 11)(162 . 15)
    bitno  = n % BITS_PER_MPI_LIMB;

    if( limbno >= a->nlimbs )
	return; /* not allocated, so need to clear bits :-) */
			return; /* not allocated, so no effect */

    for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
	a->d[limbno] &= ~(A_LIMB_1 << bitno);
			a->d[limbno] &= ~(A_LIMB_1 << bitno);

		/* adjust nlimbs to clear any leading zero-value limbs (normalize) */
    a->nlimbs = limbno+1;
    for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- );

}

/****************

- 587D20E7235B57076203A9C3B8774F60EAD751978F1A4ED87AE7CC96548A021919E77C0799B8FFF9900A83EDB74E173114BAC8FDDB7FF23FF275472FB0C24603
+ 5EB23A86515CC3CB7E47FCDB287828FA70F21A62026AB715BE5121F7793ABD90F5929FBA94F6DAA9B3FDB62E159D3319920903DFC7183B2890F492265C96E081
eucrypt/mpi/tests/test_mpi.c

(67 . 12)(67 . 59)
	mpi_free(in);
}

void test_highbit()
{
	MPI in, set_out, clear_out;

	in = mpi_alloc(0);
	set_out = mpi_alloc(0);
	clear_out = mpi_alloc(0);

  mpi_fromstr(in, "0x2000000010000002000000004");
  mpi_fromstr(set_out, "0x2000000010000002000000004");
  mpi_fromstr(clear_out, "0x2000000010000002000000004");

	mpi_set_highbit(set_out, 91);
	print_results(in, set_out, "TEST: mpi_set_highbit(in, 91)");

  mpi_fromstr(set_out, "0x2000000010000002000000004");
	mpi_set_highbit(set_out, 96);
	print_results(in, set_out, "TEST: mpi_set_highbit(in, 96)");


	mpi_clear_highbit(clear_out, 96);
	print_results(in, clear_out, "TEST: mpi_clear_highbit(in, 96)");

  mpi_fromstr(clear_out, "0x2000000010000002000000004");
	mpi_clear_highbit(clear_out, 1);
	print_results(in, clear_out, "TEST: mpi_clear_highbit(in, 1)");

	mpi_free(in);
	mpi_free(set_out);
	mpi_free(clear_out);
}

void test_get_nbits()
{
	MPI m;
	int nbits;

	m = mpi_alloc(0);
	mpi_fromstr(m, "0x0");
	nbits = mpi_get_nbits(m);
	print_results(m, m, "TEST: get_nbits");
	fprintf(stdout, "nbits: %d\n", nbits);
	mpi_free(m);
}

int main(int ac, char **av)
{
  MPI a, b, y;
  int r;

	test_rshift();
	test_highbit();
	test_get_nbits();
  
  r = secmem_init(1000);
  if (r==0) err("secmem init");
(85 . 7)(132 . 7)
  mpi_mul(y, a, b);
  mpi_free(a);
  mpi_free(b);
  

	fprintf(stdout, "******** TEST: mpi_mul, see README ********");
	terpri(stdout);
  mpi_print(stdout, y, 1);

- 39ADDB10B86590187C6F9020DD894B4EFA7256381ACEFDEB2C68ABF8A37CBF011909E9BB9DFDB38FFB2FB4B3F0341AE39CB2C9BE6A1425EC139DA4E47C37B33B
+ FEAFFACD0ECCEEC5B42D086F1755FEDE58DD7244B52B8EF599B7E4AD79B149FCBE55F036A1C46F5BAE0A00DD3C50B1DC7D8C1BDE9958934CBCD8D01862E29B9D
eucrypt/smg_rsa/include/knobs.h

(3 . 5)(3 . 17)

#define ENTROPY_SOURCE "/dev/ttyUSB0"

/*
 * This is the number of witnesses checked by the Miller-Rabin (MR) algorithm for each candidate prime number.
 * The value of M_R_ITERATIONS directly affects the outer bound of MR which is calculated as 4^(-M_R_ITERATIONS)
 * S.MG's choice of 16 here means an outer bound of 4^(-16) = 0.0000000002,
		which is currently considered sufficient for Eulora's needs.
		If your needs are different, change this knob accordingly.
 * NB: if you use this to make keys for some serious use, an outer bound of 1e-10 is really not nearly good enough
		and therefore you'll probably want to *increase* the value of this knob.
 */
#define M_R_ITERATIONS 16


#endif /*SMG_RSA_KNOBS_H*/

- 54AFE77A6A278EB793ECF8CA19CD3B1DEC64AE9D59826DCAD3ABC4DF46C0C3BC7A16E178A05690BF930C1935A94DD12EB635E6D37B4F6F89CB478FD92A2A0B7A
+ 69ED0DE509C413D6E911966E2E60DE118D6D8DB4516AC444FEC119C08576153246DA0F6AA27DDFCFE3398290A93E000C4A4B6F296B452ED3DDFE406660247708
eucrypt/smg_rsa/include/smg_rsa.h

(39 . 6)(39 . 30)
 */
int get_random_octets_from(int noctets, unsigned char *out, int from);

/*********primegen.c*********/

/*
 * This is an implementation of the Miller-Rabin probabilistic primality test:
 *   checking the specified number of randomly-chosen candidate witnesses
 *	  (i.e. with an outer bound of (1/4)^nwitnesses).
 * NB: a 1 result from this test means that the given n is indeed composite (non-prime)
		but a 0 result does not fully guarantee that n is prime!
		If this doesn't make sense to you, read more on probabilistic primality tests.
 * @param n the candidate prime number;
		the function will investigate whether this number is composite or *likely* to be prime.
		How likely? It depends on the number of witnesses checked, see next parameter.
 * @param nwitnesses this is the number of randomly chosen candidate witnesses to the compositeness of n
			that will be checked; the outer bound of the algorithm depends on this.
 * @param entropy_source the source of entropy (ready to read from) that will be used
		to choose candidate witnesses to the compositeness of n.
 * @return 1 if at least one witness to the compositeness of n has been found
			(i.e. n is certainly composite);
			0 if no witness to the compositeness of n was found (i.e. it is likely that n is prime)
 * NB: the probability that n is *not* prime although this function returned 0 is
			less than (1/4)^nwitnesses, but it is NOT zero.
 */
int is_composite( MPI n, int nwitnesses, int entropy_source);


#endif /*SMG_RSA*/

-
+ 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;
}

- 925D35158574838825AEE8B2269787E17FA2F3C3FC6BC6929EF573BBA3B1477F157FB9F162E627B13C5E60F02D6BEFCCCE395123FC061F8F2317173BD5CE8DC4
+ 0EB9FD7240D16B287C06A319D1D170AEA9AA046B4F443FF1339F509D8E7B42317425FD369CEDB6E7E3D898700BA917B0B56A83305D730A5CD7D5BD09F4809986
eucrypt/smg_rsa/tests/tests.c

(1 . 6)(1 . 8)
#include "smg_rsa.h"
#include "mpi.h"

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

void err(char *msg)
(28 . 19)(30 . 71)
	printf("ENTROPY source timing: %d kB in %ld seconds, at an average speed of %f kB/s over %d runs of %d octets each\n", nruns*noctets, diff, kbps, nruns, noctets);
}

void test_is_composite(int nruns, char *hex_number, int expected) {
	int i;
	int output;
	int count_ok = 0;
	int source = open_entropy_source(ENTROPY_SOURCE);
	MPI p = mpi_alloc(0);

	mpi_fromstr(p, hex_number);
	printf("TEST is_composite on MPI(hex) ");
	mpi_print(stdout, p, 1);
	for (i=0; i < nruns; i++) {
		printf(".");
		fflush(stdout);
		output = is_composite(p, M_R_ITERATIONS, source);
		if (output == expected)
			count_ok = count_ok + 1;
	}
	printf("done, with %d out of %d correct runs for expected=%d: %s\n", count_ok, nruns, expected, count_ok==nruns? "PASS":"FAIL");
	mpi_free(p);
	close(source);
}

int main(int ac, char **av)
{
	int nruns;
	int id;

	if (ac<2) {
		printf("Usage: %s number_of_runs\n", av[0]);
		printf("Usage: %s number_of_runs [testID]\n", av[0]);
		return -1;
	}
	nruns = atoi(av[1]);

	printf("Timing entropy source...\n");
	time_entropy_source(nruns,4096);
	if (ac < 3)
		id = 0;
	else
		id = atoi(av[2]);

	if (id == 0 || id == 1) {
		printf("Timing entropy source...\n");
		time_entropy_source(nruns,4096);
	}

	if (id == 0 || id == 2) {

		/* a few primes (decimal): 65537, 116447, 411949103, 20943302231 */
		test_is_composite(nruns, "0x10001", 0);
		test_is_composite(nruns, "0x1C6DF", 0);
		test_is_composite(nruns, "0x188DD82F", 0);
		test_is_composite(nruns, "0x4E0516E57", 0);
		/* a few mersenne primes (decimal): 2^13 - 1 = 8191, 2^17 - 1 = 131071, 2^31 - 1 = 2147483647 */
		test_is_composite(nruns, "0x1FFF", 0);
		test_is_composite(nruns, "0x1FFFF", 0);
		test_is_composite(nruns, "0x7FFFFFFF", 0);
		/* a few carmichael numbers, in decimal: 561, 60977817398996785 */
		test_is_composite(nruns, "0x231", 1);
		test_is_composite(nruns, "0xD8A300793EEF31", 1);
		/* an even number */
		test_is_composite(nruns, "0x15A9E672864B1E", 1);
		/* a phuctor-found non-prime public exponent: 170141183460469231731687303715884105731 */
		test_is_composite(nruns, "0x80000000000000000000000000000003", 1);
	}

	if (id > 2)
		printf("Current test ids: 0 for all, 1 for entropy source test only, 2 for is_composite test only.");

  return 0;
}

- 4B729AFBF1B614C0E53367586D7880C27856E0A7A7996735C718091124FC436C3F9003B213B8BA56E80ACC41E4CDF98E5F56D8B3CF1573D6BB699F0B59FD89EC
+ 72A4C1F55A1EF9D853F44A93F1F5396E63739DC4C1C70017DD3F3D2EA6C7E1B843CE0CA60E5D06DDCC742ECDE6F17CDABDDBE833F83AD7BEA2CEBC40B80E332A
eucrypt/smg_rsa/truerandom.c

(68 . 13)(68 . 14)
	int total = 0;

	while (total < noctets) {
		errno = 0;
		nread = read(from, out+total, noctets-total);
		//on interrupt received just try again
		if (nread == -1 && errno == EINTR)
			continue;
		//on error condition abort
		if (nread == -1 || nread == 0) {
			printf("Error reading from entropy source %s: %s\n", ENTROPY_SOURCE, strerror(errno));
		if (errno != 0 && (nread == -1 || nread == 0)) {
			printf("Error reading from entropy source %s after %d read: %s\n", ENTROPY_SOURCE, total, strerror(errno));
			return total;		//total read so far
		}