- D5A314BAA0F6D77B60210629541A02F8DD8923A03D0003A2005E46DCAC8022780577CF2D584BB869FD241A367153854838FBE88B46380914EDB6F35946B457DD+ 125731AB93CC7040A8516735C40563958A82EF0484E0F9DF9BC60E33225E39BF919D5F6B277421FED43047FA2B2185C0244378C5568A3623674E8B4ABB015168eucrypt/smg_rsa/primegen.c(103 . 3)(103 . 47)
88
89 return evidence;
90 }
91
92 /**
93 * Generates a random number that has passed the Miller-Rabin test for primality (see function is_composite above).
94 * NB: top 2 bits and bottom bit are ALWAYS 1! (i.e. a mask 11.....1 is applied)
95 * a prime of 8*noctets long will have only 8*noctets-3 bits that are randomly chosen
96 * NB: this method does NOT allocate space for the requested MPI; it is the caller's responsibility to allocate it!
97 * The source of randomness is ENTROPY_SOURCE in eucrypt/smg_rsa/include/knobs.h
98 * The number of witnesses checked by Miller-Rabin is M_R_ITERATIONS in eucrypt/smg_rsa/include/knobs.h
99 * Preconditions:
100 * noctets > 0 (at least one octet!)
101 * memory allocated for noctets in output MPI
102 * successful access to the entropy source
103 */
104 void gen_random_prime( unsigned int noctets, MPI output )
105 {
106 /* precondition: at least one octet long */
107 assert(noctets > 0);
108
109 /* precondition: enough memory allocated for the limbs corresponding to noctets */
110 unsigned int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
111 assert(mpi_get_alloced(output) >= nlimbs);
112
113 /* precondition: access to the entropy source */
114 int entropy_source = open_entropy_source(ENTROPY_SOURCE); /* source of random bits */
115 assert(entropy_source >= 0);
116
117 unsigned int nbits = 8*noctets; /* length of MPI in bits */
118
119 /*
120 * loop until a prime is found: get noctets of random bits, trim and apply 110...01 mask, check if prime
121 */
122 unsigned char *p = xmalloc( noctets );
123 do {
124 get_random_octets_from( noctets, p, entropy_source );
125 mpi_set_buffer( output, p, noctets, 0); /* convert to MPI representation */
126 mpi_set_highbit( output, nbits - 1 ); /* trim at required size and set top bit */
127 mpi_set_bit( output, nbits - 2); /* set second top bit */
128 mpi_set_bit( output, 0 ); /* set bottom bit to unsure odd number */
129 } while (is_composite(output, M_R_ITERATIONS, entropy_source));
130
131 /* tidy up, a prime was found */
132 xfree(p);
133 close(entropy_source);
134 }