tree checksum vpatch file split hunks

all signers: diana_coman

antecedents: ch2_truerandom eucrypt_mpi_fix_copy_incr ch1_mpi

press order:

eucrypt_genesisdiana_coman
ch1_mpidiana_coman
eucrypt_mpi_fix_copy_incrdiana_coman
ch2_truerandomdiana_coman
eucrypt_ch3_miller_rabindiana_coman

patch:

- F8B433355F471B6EA164813B4927B36D389177AF169F39E25C04B3A043DE367A88B8F07A6FE6EB92C851B9E20FA1B8EE0D1EC25E53A9F51477914F1A38EC1D5B
+ 36AA7BC45976C3792B00414443B35C0DE1C172B5D2DDF26FF62736CF8642F3D2260FD45216F075DA1024A27CED6E03004A41CC3A7508877462A7A06C11EA4339
eucrypt/mpi/mpi-bit.c
(162 . 11)(162 . 15)
5 bitno = n % BITS_PER_MPI_LIMB;
6
7 if( limbno >= a->nlimbs )
8 return; /* not allocated, so need to clear bits :-) */
9 return; /* not allocated, so no effect */
10
11 for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
12 a->d[limbno] &= ~(A_LIMB_1 << bitno);
13 a->d[limbno] &= ~(A_LIMB_1 << bitno);
14
15 /* adjust nlimbs to clear any leading zero-value limbs (normalize) */
16 a->nlimbs = limbno+1;
17 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- );
18
19 }
20
21 /****************
- 587D20E7235B57076203A9C3B8774F60EAD751978F1A4ED87AE7CC96548A021919E77C0799B8FFF9900A83EDB74E173114BAC8FDDB7FF23FF275472FB0C24603
+ 5EB23A86515CC3CB7E47FCDB287828FA70F21A62026AB715BE5121F7793ABD90F5929FBA94F6DAA9B3FDB62E159D3319920903DFC7183B2890F492265C96E081
eucrypt/mpi/tests/test_mpi.c
(67 . 12)(67 . 59)
26 mpi_free(in);
27 }
28
29 void test_highbit()
30 {
31 MPI in, set_out, clear_out;
32
33 in = mpi_alloc(0);
34 set_out = mpi_alloc(0);
35 clear_out = mpi_alloc(0);
36
37 mpi_fromstr(in, "0x2000000010000002000000004");
38 mpi_fromstr(set_out, "0x2000000010000002000000004");
39 mpi_fromstr(clear_out, "0x2000000010000002000000004");
40
41 mpi_set_highbit(set_out, 91);
42 print_results(in, set_out, "TEST: mpi_set_highbit(in, 91)");
43
44 mpi_fromstr(set_out, "0x2000000010000002000000004");
45 mpi_set_highbit(set_out, 96);
46 print_results(in, set_out, "TEST: mpi_set_highbit(in, 96)");
47
48
49 mpi_clear_highbit(clear_out, 96);
50 print_results(in, clear_out, "TEST: mpi_clear_highbit(in, 96)");
51
52 mpi_fromstr(clear_out, "0x2000000010000002000000004");
53 mpi_clear_highbit(clear_out, 1);
54 print_results(in, clear_out, "TEST: mpi_clear_highbit(in, 1)");
55
56 mpi_free(in);
57 mpi_free(set_out);
58 mpi_free(clear_out);
59 }
60
61 void test_get_nbits()
62 {
63 MPI m;
64 int nbits;
65
66 m = mpi_alloc(0);
67 mpi_fromstr(m, "0x0");
68 nbits = mpi_get_nbits(m);
69 print_results(m, m, "TEST: get_nbits");
70 fprintf(stdout, "nbits: %d\n", nbits);
71 mpi_free(m);
72 }
73
74 int main(int ac, char **av)
75 {
76 MPI a, b, y;
77 int r;
78
79 test_rshift();
80 test_highbit();
81 test_get_nbits();
82
83 r = secmem_init(1000);
84 if (r==0) err("secmem init");
(85 . 7)(132 . 7)
86 mpi_mul(y, a, b);
87 mpi_free(a);
88 mpi_free(b);
89
90
91 fprintf(stdout, "******** TEST: mpi_mul, see README ********");
92 terpri(stdout);
93 mpi_print(stdout, y, 1);
- 39ADDB10B86590187C6F9020DD894B4EFA7256381ACEFDEB2C68ABF8A37CBF011909E9BB9DFDB38FFB2FB4B3F0341AE39CB2C9BE6A1425EC139DA4E47C37B33B
+ FEAFFACD0ECCEEC5B42D086F1755FEDE58DD7244B52B8EF599B7E4AD79B149FCBE55F036A1C46F5BAE0A00DD3C50B1DC7D8C1BDE9958934CBCD8D01862E29B9D
eucrypt/smg_rsa/include/knobs.h
(3 . 5)(3 . 17)
98
99 #define ENTROPY_SOURCE "/dev/ttyUSB0"
100
101 /*
102 * This is the number of witnesses checked by the Miller-Rabin (MR) algorithm for each candidate prime number.
103 * The value of M_R_ITERATIONS directly affects the outer bound of MR which is calculated as 4^(-M_R_ITERATIONS)
104 * S.MG's choice of 16 here means an outer bound of 4^(-16) = 0.0000000002,
105 which is currently considered sufficient for Eulora's needs.
106 If your needs are different, change this knob accordingly.
107 * NB: if you use this to make keys for some serious use, an outer bound of 1e-10 is really not nearly good enough
108 and therefore you'll probably want to *increase* the value of this knob.
109 */
110 #define M_R_ITERATIONS 16
111
112
113 #endif /*SMG_RSA_KNOBS_H*/
114
- 54AFE77A6A278EB793ECF8CA19CD3B1DEC64AE9D59826DCAD3ABC4DF46C0C3BC7A16E178A05690BF930C1935A94DD12EB635E6D37B4F6F89CB478FD92A2A0B7A
+ 69ED0DE509C413D6E911966E2E60DE118D6D8DB4516AC444FEC119C08576153246DA0F6AA27DDFCFE3398290A93E000C4A4B6F296B452ED3DDFE406660247708
eucrypt/smg_rsa/include/smg_rsa.h
(39 . 6)(39 . 30)
119 */
120 int get_random_octets_from(int noctets, unsigned char *out, int from);
121
122 /*********primegen.c*********/
123
124 /*
125 * This is an implementation of the Miller-Rabin probabilistic primality test:
126 * checking the specified number of randomly-chosen candidate witnesses
127 * (i.e. with an outer bound of (1/4)^nwitnesses).
128 * NB: a 1 result from this test means that the given n is indeed composite (non-prime)
129 but a 0 result does not fully guarantee that n is prime!
130 If this doesn't make sense to you, read more on probabilistic primality tests.
131 * @param n the candidate prime number;
132 the function will investigate whether this number is composite or *likely* to be prime.
133 How likely? It depends on the number of witnesses checked, see next parameter.
134 * @param nwitnesses this is the number of randomly chosen candidate witnesses to the compositeness of n
135 that will be checked; the outer bound of the algorithm depends on this.
136 * @param entropy_source the source of entropy (ready to read from) that will be used
137 to choose candidate witnesses to the compositeness of n.
138 * @return 1 if at least one witness to the compositeness of n has been found
139 (i.e. n is certainly composite);
140 0 if no witness to the compositeness of n was found (i.e. it is likely that n is prime)
141 * NB: the probability that n is *not* prime although this function returned 0 is
142 less than (1/4)^nwitnesses, but it is NOT zero.
143 */
144 int is_composite( MPI n, int nwitnesses, int entropy_source);
145
146
147 #endif /*SMG_RSA*/
148
-
+ D5A314BAA0F6D77B60210629541A02F8DD8923A03D0003A2005E46DCAC8022780577CF2D584BB869FD241A367153854838FBE88B46380914EDB6F35946B457DD
eucrypt/smg_rsa/primegen.c
(0 . 0)(1 . 105)
153 /* primegen.c - prime number generation and checks
154 *
155 * S.MG, 2017
156 *
157 */
158
159 #include <stdlib.h>
160 #include <unistd.h>
161 #include <assert.h>
162
163 #include "smg_rsa.h"
164
165 /****************
166 * is_composite
167 * Returns 1 if it finds evidence that n is composite and 0 otherwise.
168 * NB: this is a probabilistic test and its strength is directly linked to:
169 * - the number of witnesses AND
170 * - the quality of the entropy source given as arguments!
171 */
172
173 int is_composite( MPI n, int nwitnesses, int entropy_source) {
174 int evidence = 0;
175 int nlimbs = mpi_get_nlimbs(n); /* see MPI representation */
176 unsigned int nbits = mpi_get_nbits(n); /* used bits */
177 unsigned int noctets = (nbits + 7) / 8; /* source works on octets */
178
179 MPI nminus1 = mpi_alloc(nlimbs); /* n-1 value is used a LOT */
180 MPI mpi2 = mpi_alloc_set_ui(2); /* 2 as MPI */
181 MPI a = mpi_alloc(nlimbs); /* candidate witness */
182 MPI y = mpi_alloc(nlimbs); /* intermediate values */
183 MPI r = mpi_alloc(nlimbs); /* n = 1 + 2^s * r */
184 int s; /* n = 1 + 2^s * r */
185 int j; /* counter for loops */
186 int nread; /* number of random octets actually read */
187
188 /* precondition: n > 3 */
189 assert( nbits > 2 );
190
191 /* nminus1 = n - 1 as MPI */
192 mpi_sub_ui( nminus1, n, 1);
193
194 /*
195 * find r odd and s so that n = 1 + 2^s * r
196 * n-1 = 2^s * r
197 * s is given by the number of trailing zeros of binary n-1
198 * r is then obtained as (n-1) / (2^s)
199 */
200 s = mpi_trailing_zeros( nminus1 );
201 mpi_tdiv_q_2exp(r, nminus1, s);
202
203 /*
204 * Investigate randomly chosen candidate witnesses.
205 * Stop when either:
206 * the specified number of witnesses (nwitnesses) have
207 been investigated OR
208 * a witness for compositeness of n was found
209 */
210 while (nwitnesses > 0 && evidence == 0) {
211 unsigned char *p = xmalloc(noctets);
212 do {
213 nread = get_random_octets_from(noctets, p, entropy_source);
214 } while (nread != noctets);
215
216 mpi_set_buffer(a, p, noctets, 0);
217
218 /* ensure that a < n-1 by making a maximum nbits-1 long:
219 * clear all bits above nbits-2 in a
220 * keep value of bit nbits-2 in a as it was
221 */
222 if (mpi_test_bit(a, nbits - 2))
223 mpi_set_highbit(a, nbits - 2);
224 else
225 mpi_clear_highbit(a, nbits - 2);
226
227 /* ensure that 1 < a < n-1; if not, try another random number
228 * NB: true random means a CAN end up as 0 or 1 here.
229 */
230 if (mpi_cmp(a, nminus1) < 0 && mpi_cmp_ui(a, 1) > 0) {
231 /* calculate y = a^r mod n */
232 mpi_powm(y, a, r, n);
233 if (mpi_cmp_ui(y, 1) && mpi_cmp(y, nminus1)) {
234 j = 1;
235 while ( (j < s) && mpi_cmp(y, nminus1) && (evidence == 0) ) {
236 /* calculate y = y^2 mod n */
237 mpi_powm(y, y, mpi2, n);
238 if (mpi_cmp_ui(y, 1) == 0)
239 evidence = 1;
240 j = j + 1;
241 } /* end while */
242 if (mpi_cmp(y, nminus1))
243 evidence = 1;
244 } /* end if y != 1 and y != n-1 */
245 nwitnesses = nwitnesses - 1;
246 } /* end if 1 < a < n-1 */
247 xfree(p);
248 } /* end while for investigating candidate witnesses */
249
250 mpi_free( nminus1 );
251 mpi_free( mpi2 );
252 mpi_free( a );
253 mpi_free( y );
254 mpi_free( r );
255
256 return evidence;
257 }
- 925D35158574838825AEE8B2269787E17FA2F3C3FC6BC6929EF573BBA3B1477F157FB9F162E627B13C5E60F02D6BEFCCCE395123FC061F8F2317173BD5CE8DC4
+ 0EB9FD7240D16B287C06A319D1D170AEA9AA046B4F443FF1339F509D8E7B42317425FD369CEDB6E7E3D898700BA917B0B56A83305D730A5CD7D5BD09F4809986
eucrypt/smg_rsa/tests/tests.c
(1 . 6)(1 . 8)
262 #include "smg_rsa.h"
263 #include "mpi.h"
264
265 #include <stdlib.h>
266 #include <unistd.h>
267 #include <time.h>
268
269 void err(char *msg)
(28 . 19)(30 . 71)
271 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);
272 }
273
274 void test_is_composite(int nruns, char *hex_number, int expected) {
275 int i;
276 int output;
277 int count_ok = 0;
278 int source = open_entropy_source(ENTROPY_SOURCE);
279 MPI p = mpi_alloc(0);
280
281 mpi_fromstr(p, hex_number);
282 printf("TEST is_composite on MPI(hex) ");
283 mpi_print(stdout, p, 1);
284 for (i=0; i < nruns; i++) {
285 printf(".");
286 fflush(stdout);
287 output = is_composite(p, M_R_ITERATIONS, source);
288 if (output == expected)
289 count_ok = count_ok + 1;
290 }
291 printf("done, with %d out of %d correct runs for expected=%d: %s\n", count_ok, nruns, expected, count_ok==nruns? "PASS":"FAIL");
292 mpi_free(p);
293 close(source);
294 }
295
296 int main(int ac, char **av)
297 {
298 int nruns;
299 int id;
300
301 if (ac<2) {
302 printf("Usage: %s number_of_runs\n", av[0]);
303 printf("Usage: %s number_of_runs [testID]\n", av[0]);
304 return -1;
305 }
306 nruns = atoi(av[1]);
307
308 printf("Timing entropy source...\n");
309 time_entropy_source(nruns,4096);
310 if (ac < 3)
311 id = 0;
312 else
313 id = atoi(av[2]);
314
315 if (id == 0 || id == 1) {
316 printf("Timing entropy source...\n");
317 time_entropy_source(nruns,4096);
318 }
319
320 if (id == 0 || id == 2) {
321
322 /* a few primes (decimal): 65537, 116447, 411949103, 20943302231 */
323 test_is_composite(nruns, "0x10001", 0);
324 test_is_composite(nruns, "0x1C6DF", 0);
325 test_is_composite(nruns, "0x188DD82F", 0);
326 test_is_composite(nruns, "0x4E0516E57", 0);
327 /* a few mersenne primes (decimal): 2^13 - 1 = 8191, 2^17 - 1 = 131071, 2^31 - 1 = 2147483647 */
328 test_is_composite(nruns, "0x1FFF", 0);
329 test_is_composite(nruns, "0x1FFFF", 0);
330 test_is_composite(nruns, "0x7FFFFFFF", 0);
331 /* a few carmichael numbers, in decimal: 561, 60977817398996785 */
332 test_is_composite(nruns, "0x231", 1);
333 test_is_composite(nruns, "0xD8A300793EEF31", 1);
334 /* an even number */
335 test_is_composite(nruns, "0x15A9E672864B1E", 1);
336 /* a phuctor-found non-prime public exponent: 170141183460469231731687303715884105731 */
337 test_is_composite(nruns, "0x80000000000000000000000000000003", 1);
338 }
339
340 if (id > 2)
341 printf("Current test ids: 0 for all, 1 for entropy source test only, 2 for is_composite test only.");
342
343 return 0;
344 }
- 4B729AFBF1B614C0E53367586D7880C27856E0A7A7996735C718091124FC436C3F9003B213B8BA56E80ACC41E4CDF98E5F56D8B3CF1573D6BB699F0B59FD89EC
+ 72A4C1F55A1EF9D853F44A93F1F5396E63739DC4C1C70017DD3F3D2EA6C7E1B843CE0CA60E5D06DDCC742ECDE6F17CDABDDBE833F83AD7BEA2CEBC40B80E332A
eucrypt/smg_rsa/truerandom.c
(68 . 13)(68 . 14)
349 int total = 0;
350
351 while (total < noctets) {
352 errno = 0;
353 nread = read(from, out+total, noctets-total);
354 //on interrupt received just try again
355 if (nread == -1 && errno == EINTR)
356 continue;
357 //on error condition abort
358 if (nread == -1 || nread == 0) {
359 printf("Error reading from entropy source %s: %s\n", ENTROPY_SOURCE, strerror(errno));
360 if (errno != 0 && (nread == -1 || nread == 0)) {
361 printf("Error reading from entropy source %s after %d read: %s\n", ENTROPY_SOURCE, total, strerror(errno));
362 return total; //total read so far
363 }
364