diff -uNr a/eucrypt/mpi/mpi-bit.c b/eucrypt/mpi/mpi-bit.c --- a/eucrypt/mpi/mpi-bit.c f8b433355f471b6ea164813b4927b36d389177af169f39e25c04b3a043de367a88b8f07a6fe6eb92c851b9e20fa1b8ee0d1ec25e53a9f51477914f1a38ec1d5b +++ b/eucrypt/mpi/mpi-bit.c 36aa7bc45976c3792b00414443b35c0de1c172b5d2ddf26ff62736cf8642f3d2260fd45216f075da1024a27ced6e03004a41cc3a7508877462a7a06c11ea4339 @@ -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-- ); + } /**************** diff -uNr a/eucrypt/mpi/tests/test_mpi.c b/eucrypt/mpi/tests/test_mpi.c --- a/eucrypt/mpi/tests/test_mpi.c 587d20e7235b57076203a9c3b8774f60ead751978f1a4ed87ae7cc96548a021919e77c0799b8fff9900a83edb74e173114bac8fddb7ff23ff275472fb0c24603 +++ b/eucrypt/mpi/tests/test_mpi.c 5eb23a86515cc3cb7e47fcdb287828fa70f21a62026ab715be5121f7793abd90f5929fba94f6daa9b3fdb62e159d3319920903dfc7183b2890f492265c96e081 @@ -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); diff -uNr a/eucrypt/smg_rsa/include/knobs.h b/eucrypt/smg_rsa/include/knobs.h --- a/eucrypt/smg_rsa/include/knobs.h 39addb10b86590187c6f9020dd894b4efa7256381acefdeb2c68abf8a37cbf011909e9bb9dfdb38ffb2fb4b3f0341ae39cb2c9be6a1425ec139da4e47c37b33b +++ b/eucrypt/smg_rsa/include/knobs.h feaffacd0ecceec5b42d086f1755fede58dd7244b52b8ef599b7e4ad79b149fcbe55f036a1c46f5bae0a00dd3c50b1dc7d8c1bde9958934cbcd8d01862e29b9d @@ -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*/ diff -uNr a/eucrypt/smg_rsa/include/smg_rsa.h b/eucrypt/smg_rsa/include/smg_rsa.h --- a/eucrypt/smg_rsa/include/smg_rsa.h 54afe77a6a278eb793ecf8ca19cd3b1dec64ae9d59826dcad3abc4df46c0c3bc7a16e178a05690bf930c1935a94dd12eb635e6d37b4f6f89cb478fd92a2a0b7a +++ b/eucrypt/smg_rsa/include/smg_rsa.h 69ed0de509c413d6e911966e2e60de118d6d8db4516ac444fec119c08576153246da0f6aa27ddfcfe3398290a93e000c4a4b6f296b452ed3ddfe406660247708 @@ -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*/ diff -uNr a/eucrypt/smg_rsa/primegen.c b/eucrypt/smg_rsa/primegen.c --- a/eucrypt/smg_rsa/primegen.c false +++ b/eucrypt/smg_rsa/primegen.c d5a314baa0f6d77b60210629541a02f8dd8923a03d0003a2005e46dcac8022780577cf2d584bb869fd241a367153854838fbe88b46380914edb6f35946b457dd @@ -0,0 +1,105 @@ +/* primegen.c - prime number generation and checks + * + * S.MG, 2017 + * + */ + +#include +#include +#include + +#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; +} diff -uNr a/eucrypt/smg_rsa/tests/tests.c b/eucrypt/smg_rsa/tests/tests.c --- a/eucrypt/smg_rsa/tests/tests.c 925d35158574838825aee8b2269787e17fa2f3c3fc6bc6929ef573bba3b1477f157fb9f162e627b13c5e60f02d6befccce395123fc061f8f2317173bd5ce8dc4 +++ b/eucrypt/smg_rsa/tests/tests.c 0eb9fd7240d16b287c06a319d1d170aea9aa046b4f443ff1339f509d8e7b42317425fd369cedb6e7e3d898700ba917b0b56a83305d730a5cd7d5bd09f4809986 @@ -1,6 +1,8 @@ #include "smg_rsa.h" +#include "mpi.h" #include +#include #include 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; } diff -uNr a/eucrypt/smg_rsa/truerandom.c b/eucrypt/smg_rsa/truerandom.c --- a/eucrypt/smg_rsa/truerandom.c 4b729afbf1b614c0e53367586d7880c27856e0a7a7996735c718091124fc436c3f9003b213b8ba56e80acc41e4cdf98e5f56d8b3cf1573d6bb699f0b59fd89ec +++ b/eucrypt/smg_rsa/truerandom.c 72a4c1f55a1ef9d853f44a93f1f5396e63739dc4c1c70017dd3f3d2ea6c7e1b843ce0ca60e5d06ddcc742ecde6f17cdabddbe833f83ad7bea2cebc40b80e332a @@ -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 }