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 }
eucrypt_ch4_rpng 106
eucrypt_ch4_rpng 107 /**
eucrypt_ch4_rpng 108 * Generates a random number that has passed the Miller-Rabin test for primality (see function is_composite above).
eucrypt_ch4_rpng 109 * NB: top 2 bits and bottom bit are ALWAYS 1! (i.e. a mask 11.....1 is applied)
eucrypt_ch4_rpng 110 * a prime of 8*noctets long will have only 8*noctets-3 bits that are randomly chosen
eucrypt_ch4_rpng 111 * NB: this method does NOT allocate space for the requested MPI; it is the caller's responsibility to allocate it!
eucrypt_ch4_rpng 112 * The source of randomness is ENTROPY_SOURCE in eucrypt/smg_rsa/include/knobs.h
eucrypt_ch4_rpng 113 * The number of witnesses checked by Miller-Rabin is M_R_ITERATIONS in eucrypt/smg_rsa/include/knobs.h
eucrypt_ch4_rpng 114 * Preconditions:
eucrypt_ch4_rpng 115 * noctets > 0 (at least one octet!)
eucrypt_ch4_rpng 116 * memory allocated for noctets in output MPI
eucrypt_ch4_rpng 117 * successful access to the entropy source
eucrypt_ch4_rpng 118 */
eucrypt_ch4_rpng 119 void gen_random_prime( unsigned int noctets, MPI output )
eucrypt_ch4_rpng 120 {
eucrypt_ch4_rpng 121 /* precondition: at least one octet long */
eucrypt_ch4_rpng 122 assert(noctets > 0);
eucrypt_ch4_rpng 123
eucrypt_ch4_rpng 124 /* precondition: enough memory allocated for the limbs corresponding to noctets */
eucrypt_ch4_rpng 125 unsigned int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
eucrypt_ch4_rpng 126 assert(mpi_get_alloced(output) >= nlimbs);
eucrypt_ch4_rpng 127
eucrypt_ch4_rpng 128 /* precondition: access to the entropy source */
eucrypt_ch4_rpng 129 int entropy_source = open_entropy_source(ENTROPY_SOURCE); /* source of random bits */
eucrypt_ch4_rpng 130 assert(entropy_source >= 0);
eucrypt_ch4_rpng 131
eucrypt_ch4_rpng 132 unsigned int nbits = 8*noctets; /* length of MPI in bits */
eucrypt_ch4_rpng 133
eucrypt_ch4_rpng 134 /*
eucrypt_ch4_rpng 135 * loop until a prime is found: get noctets of random bits, trim and apply 110...01 mask, check if prime
eucrypt_ch4_rpng 136 */
eucrypt_ch4_rpng 137 unsigned char *p = xmalloc( noctets );
eucrypt_ch4_rpng 138 do {
eucrypt_ch4_rpng 139 get_random_octets_from( noctets, p, entropy_source );
eucrypt_ch4_rpng 140 mpi_set_buffer( output, p, noctets, 0); /* convert to MPI representation */
eucrypt_ch4_rpng 141 mpi_set_highbit( output, nbits - 1 ); /* trim at required size and set top bit */
eucrypt_ch4_rpng 142 mpi_set_bit( output, nbits - 2); /* set second top bit */
eucrypt_ch4_rpng 143 mpi_set_bit( output, 0 ); /* set bottom bit to unsure odd number */
eucrypt_ch4_rpng 144 } while (is_composite(output, M_R_ITERATIONS, entropy_source));
eucrypt_ch4_rpng 145
eucrypt_ch4_rpng 146 /* tidy up, a prime was found */
eucrypt_ch4_rpng 147 xfree(p);
eucrypt_ch4_rpng 148 close(entropy_source);
eucrypt_ch4_rpng 149 }