tree checksum vpatch file split hunks
all signers: diana_coman
antecedents: eucrypt_ch4_rpng
press order:
patch:
(15 . 6)(15 . 21)-
5 */
6 static const int KEY_LENGTH_OCTETS = 512;
7
8 typedef struct {
9 MPI n; /* modulus */
10 MPI e; /* public exponent */
11 } RSA_public_key;
12
13 typedef struct {
14 MPI n; /* public modulus */
15 MPI e; /* public exponent */
16 MPI d; /* private exponent: e*d=1 mod phi */
17 MPI p; /* prime p */
18 MPI q; /* prime q */
19 MPI u; /* inverse of p mod q */
20 } RSA_secret_key;
21
22
23 /*********truerandom.c*********/
24
25 /*
(86 . 6)(101 . 68)
27 */
28 void gen_random_prime( unsigned int noctets, MPI output);
29
30 /*********rsa.c*********/
31 /*
32 * Generates a pair of public+private RSA keys using directly the entropy source
33 * specified in eucrypt/smg_rsa/include/knobs.h
34 *
35 * ALL RSA keys are 4096 bits out of 2 2048 bits primes, as per TMSR spec.
36 *
37 * @param sk a fully-allocated structure to hold the generated keypair (secret
38 key structure holds all the elements anyway, public key is a subset of this)
39 *
40 * NB: this procedure does NOT allocate memory for components in sk!
41 * caller should ALLOCATE enough memory for all the MPIs in sk
42 * Precondition:
43 * MPIs in sk have known allocated memory for the nlimbs fitting their TMSR size
44 */
45 void gen_keypair( RSA_secret_key *sk );
46
47 /****************
48 * Public key operation. Encrypt input with pk and store result into output.
49 *
50 * output = input^e mod n , where e,n are elements of pkey.
51 * NB: caller should allocate *sufficient* memory for output to hold the result.
52 * NB: NO checks are made on input!
53 *
54 * @param output MPI with enough allocated memory to hold result of encryption
55 * @param input MPI containing content to encrypt; it *has to be* different from
56 output!
57 * @param pk the public key that will be used to encrypt input
58 *
59 * Precondition:
60 * output != input
61 * Output and input have to be two distinct MPIs because of the sorry state of
62 the underlying mpi lib that can't handle properly the case when those are the
63 same.
64 */
65 void public_rsa( MPI output, MPI input, RSA_public_key *pk );
66
67
68 /****************
69 * Secret key operation. Decrypt input with sk and store result in output.
70 *
71 * output = input^d mod n , where d, n are elements of skey.
72 *
73 * This implementation uses the Chinese Remainder Theorem (CRT):
74 *
75 * out1 = input ^ (d mod (p-1)) mod p
76 * out2 = input ^ (d mod (q-1)) mod q
77 * h = u * (out2 - out1) mod q
78 * output = out1 + h * p
79 *
80 * where out1, out2 and h are intermediate values, d,n,p,q,u are elements of
81 skey. By using CRT, encryption is *faster*. Decide for yourself if this fits
82 your needs though!
83 * NB: it is the caller's responsibility to allocate memory for output!
84 * NB: NO checks are made on input!
85 *
86 * @param output MPI with enough allocated memory to hold result of decryption
87 * @param input MPI containing content to decrypt
88 * @param sk the secret key that will be used to decrypt input
89 */
90 void secret_rsa( MPI output, MPI input, RSA_secret_key *sk );
91
92
93 #endif /*SMG_RSA*/
94
(0 . 0)(1 . 138)
99 /*
100 * An implementation of TMSR RSA
101 * S.MG, 2018
102 */
103
104 #include "smg_rsa.h"
105 #include <assert.h>
106
107 void gen_keypair( RSA_secret_key *sk ) {
108 /* precondition: sk is not null */
109 assert(sk != NULL);
110
111 /* precondition: enough memory allocated, corresponding to key size */
112 int noctets_pq = KEY_LENGTH_OCTETS / 2;
113 unsigned int nlimbs_pq = mpi_nlimb_hint_from_nbytes( noctets_pq);
114 unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
115 assert( mpi_get_alloced( sk->n) >= nlimbs_n);
116 assert( mpi_get_alloced( sk->p) >= nlimbs_pq);
117 assert( mpi_get_alloced( sk->q) >= nlimbs_pq);
118
119 /* helper variables for calculating Euler's totient phi=(p-1)*(q-1) */
120 MPI p_minus1 = mpi_alloc(nlimbs_pq);
121 MPI q_minus1 = mpi_alloc(nlimbs_pq);
122 MPI phi = mpi_alloc(nlimbs_n);
123
124 /* generate 2 random primes, p and q*/
125 /* gen_random_prime sets top 2 bits to 1 so p*q will have KEY_LENGTH bits */
126 /* in the extremely unlikely case that p = q, discard and generate again */
127 do {
128 gen_random_prime( noctets_pq, sk->p);
129 gen_random_prime( noctets_pq, sk->q);
130 } while ( mpi_cmp( sk->p, sk->q) == 0);
131
132 /* swap if needed, to ensure p < q for calculating u */
133 if ( mpi_cmp( sk->p, sk->q) > 0)
134 mpi_swap( sk->p, sk->q);
135
136 /* calculate helper for Chinese Remainder Theorem:
137 u = p ^ -1 ( mod q )
138 this is used to speed-up decryption.
139 */
140 mpi_invm( sk->u, sk->p, sk->q);
141
142 /* calculate modulus n = p * q */
143 mpi_mul( sk->n, sk->p, sk->q);
144
145 /* calculate Euler totient: phi = (p-1)*(q-1) */
146 mpi_sub_ui( p_minus1, sk->p, 1);
147 mpi_sub_ui( q_minus1, sk->q, 1);
148 mpi_mul( phi, p_minus1, q_minus1);
149
150 /* choose random prime e, public exponent, with 3 < e < phi */
151 /* because e is prime, gcd(e, phi) is always 1 so no need to check it */
152 do {
153 gen_random_prime( noctets_pq, sk->e);
154 } while ( (mpi_cmp_ui(sk->e, 3) < 0) || (mpi_cmp(sk->e, phi) > 0));
155
156 /* calculate private exponent d, 1 < d < phi, where e * d = 1 mod phi */
157 mpi_invm( sk->d, sk->e, phi);
158
159 /* tidy up: free locally allocated memory for helper variables */
160 mpi_free(phi);
161 mpi_free(p_minus1);
162 mpi_free(q_minus1);
163 }
164
165 void public_rsa( MPI output, MPI input, RSA_public_key *pk ) {
166
167 /* mpi_powm can't handle output and input being same */
168 assert (output != input);
169
170 mpi_powm( output, input, pk->e, pk->n );
171 }
172
173 void secret_rsa( MPI output, MPI input, RSA_secret_key *skey ) {
174 /* at its simplest, this would be input ^ d (mod n), hence:
175 * mpi_powm( output, input, skey->d, skey->n );
176 * for faster decryption though, we'll use CRT and Garner's algorithm, hence:
177 * u = p ^ (-1) (mod q) , already calculated and stored in skey
178 * dp = d mod (p-1)
179 * dq = d mod (q-1)
180 * m1 = input ^ dp (mod p)
181 * m2 = input ^ dq (mod q)
182 * h = u * (m2 - m1) mod q
183 * output = m1 + h * p
184 * Note that same CRT speed up isn't available for encryption because at
185 encryption time not enough information is available (only e and n are known).
186 */
187
188 /* allocate memory for all local, helper MPIs */
189 MPI p_minus1 = mpi_alloc( mpi_get_nlimbs( skey->p) );
190 MPI q_minus1 = mpi_alloc( mpi_get_nlimbs( skey->q) );
191 int nlimbs = mpi_get_nlimbs( skey->n ) + 1;
192 MPI dp = mpi_alloc( nlimbs );
193 MPI dq = mpi_alloc( nlimbs );
194 MPI m1 = mpi_alloc( nlimbs );
195 MPI m2 = mpi_alloc( nlimbs );
196 MPI h = mpi_alloc( nlimbs );
197
198 /* p_minus1 = p - 1 */
199 mpi_sub_ui( p_minus1, skey->p, 1 );
200
201 /* dp = d mod (p - 1) aka remainder of d / (p - 1) */
202 mpi_fdiv_r( dp, skey->d, p_minus1 );
203
204 /* m1 = input ^ dp (mod p) */
205 mpi_powm( m1, input, dp, skey->p );
206
207 /* q_minus1 = q - 1 */
208 mpi_sub_ui( q_minus1, skey->q, 1 );
209
210 /* dq = d mod (q - 1) aka remainder of d / (q - 1) */
211 mpi_fdiv_r( dq, skey->d, q_minus1 );
212
213 /* m2 = input ^ dq (mod q) */
214 mpi_powm( m2, input, dq, skey->q );
215
216 /* h = u * ( m2 - m1 ) mod q */
217 mpi_sub( h, m2, m1 );
218 if ( mpi_is_neg( h ) )
219 mpi_add ( h, h, skey->q );
220 mpi_mulm( h, skey->u, h, skey->q );
221
222 /* output = m1 + h * p */
223 mpi_mul ( h, h, skey->p );
224 mpi_add ( output, m1, h );
225
226 /* tidy up */
227 mpi_free ( p_minus1 );
228 mpi_free ( q_minus1 );
229 mpi_free ( dp );
230 mpi_free ( dq );
231 mpi_free ( m1 );
232 mpi_free ( m2 );
233 mpi_free ( h );
234
235 }
236
- 25364B546A9EC5983239A7C783B316F704C814EBEE5778CFA595F14F802E64930B7234EE536E0F69E519BF36B558BEA432D62A85D670D0FF62556CC12C6A1DC6(184 . 10)(184 . 234)
241 close(entropy_source);
242 }
243
244 /* Test encryption+decryption on noctets of random data, using sk
245 * Output is written to file.
246 */
247 void test_rsa_keys( RSA_secret_key *sk, unsigned int noctets, FILE *file ) {
248 RSA_public_key pk;
249 MPI test = mpi_alloc ( mpi_nlimb_hint_from_nbytes (noctets) );
250 MPI out1 = mpi_alloc ( mpi_nlimb_hint_from_nbytes (noctets) );
251 MPI out2 = mpi_alloc ( mpi_nlimb_hint_from_nbytes (noctets) );
252
253 pk.n = mpi_copy(sk->n);
254 pk.e = mpi_copy(sk->e);
255 unsigned char *p;
256 p = xmalloc(noctets);
257
258 fprintf(file, "TEST encrypt/decrypt on %d octets of random data\n", noctets);
259 fflush(file);
260 if (get_random_octets( noctets, p) == noctets) {
261 mpi_set_buffer( test, p, noctets, 0 );
262
263 fprintf(file, "TEST data:\n");
264 mpi_print(file, test, 1);
265 fprintf(file, "\n");
266 fflush(file);
267
268 public_rsa( out1, test, &pk );
269 secret_rsa( out2, out1, sk );
270
271 fprintf(file, "ENCRYPTED with PUBLIC key data:\n");
272 mpi_print(file, out1, 1);
273 fprintf(file, "\n");
274 fflush(file);
275
276 fprintf(file, "DECRYPTED with SECRET key:\n");
277 mpi_print(file, out2, 1);
278 fprintf(file, "\n");
279 fflush(file);
280
281 if( mpi_cmp( test, out2 ) )
282 fprintf(file, "FAILED: RSA operation: public(secret) failed\n");
283 else
284 fprintf(file, "PASSED: RSA operation: public(secret) passed\n");
285 fflush(file);
286
287 secret_rsa( out1, test, sk );
288 public_rsa( out2, out1, &pk );
289 if( mpi_cmp( test, out2 ) )
290 fprintf(file, "FAILED: RSA operation: secret(public) failed\n");
291 else
292 fprintf(file, "PASSED: RSA operation: secret(public) passed\n");
293 }
294 else
295 fprintf(file, "FAILED: not enough bits returned from entropy source\n");
296
297 fflush(file);
298 xfree(p);
299 mpi_free( pk.n);
300 mpi_free( pk.e);
301
302 mpi_free( test );
303 mpi_free( out1 );
304 mpi_free( out2 );
305 }
306
307 void test_rsa( int nruns, FILE *fkeys, FILE *fout) {
308 RSA_secret_key sk;
309 int noctets = KEY_LENGTH_OCTETS;
310 int noctets_pq = noctets / 2;
311 int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
312 int nlimbs_pq = mpi_nlimb_hint_from_nbytes(noctets_pq);
313 int i;
314
315 sk.n = mpi_alloc(nlimbs);
316 sk.e = mpi_alloc(nlimbs);
317 sk.d = mpi_alloc(nlimbs);
318 sk.p = mpi_alloc(nlimbs_pq);
319 sk.q = mpi_alloc(nlimbs_pq);
320 sk.u = mpi_alloc(nlimbs_pq);
321
322 printf("TEST RSA key generation and use with %d runs\n", nruns);
323 fflush(stdout);
324
325 for (i = 0;i < nruns; i++) {
326 gen_keypair(&sk);
327 printf(".");
328 fflush(stdout);
329
330 mpi_print(fkeys, sk.n, 1);
331 fwrite("\n", sizeof(char), 1, fkeys);
332
333 mpi_print(fkeys, sk.e, 1);
334 fwrite("\n", sizeof(char), 1, fkeys);
335
336 mpi_print(fkeys, sk.d, 1);
337 fwrite("\n", sizeof(char), 1, fkeys);
338
339 mpi_print(fkeys, sk.p, 1);
340 fwrite("\n", sizeof(char), 1, fkeys);
341
342 mpi_print(fkeys, sk.q, 1);
343 fwrite("\n", sizeof(char), 1, fkeys);
344
345 mpi_print(fkeys, sk.u, 1);
346 fwrite("\n", sizeof(char), 1, fkeys);
347
348 test_rsa_keys(&sk, noctets_pq, fout);
349 printf("*");
350 fflush(stdout);
351 }
352
353 mpi_free(sk.n);
354 mpi_free(sk.e);
355 mpi_free(sk.d);
356 mpi_free(sk.p);
357 mpi_free(sk.q);
358 mpi_free(sk.u);
359
360 }
361
362 void test_rsa_exp() {
363 MPI msg = mpi_alloc(0);
364 MPI expected = mpi_alloc(0);
365 MPI result;
366
367 RSA_public_key pk;
368 pk.n = mpi_alloc(0);
369 pk.e = mpi_alloc(0);
370
371 printf("TEST verify of rsa exponentiation on input data: \n");
372
373 mpi_fromstr(msg, "0x\
374 5B6A8A0ACF4F4DB3F82EAC2D20255E4DF3E4B7C799603210766F26EF87C8980E737579\
375 EC08E6505A51D19654C26D806BAF1B62F9C032E0B13D02AF99F7313BFCFD68DA46836E\
376 CA529D7360948550F982C6476C054A97FD01635AB44BFBDBE2A90BE06F7984AC8534C3\
377 8613747F340C18176E6D5F0C10246A2FCE3A668EACB6165C2052497CA2EE483F4FD8D0\
378 6A9911BD97E9B6720521D872BD08FF8DA11A1B8DB147F252E4E69AE6201D3B374B171D\
379 F445EF2BF509D468FD57CEB5840349B14C6E2AAA194D9531D238B85B8F0DD352D1E596\
380 71539B429849E5D965E438BF9EFFC338DF9AADF304C4130D5A05E006ED855F37A06242\
381 28097EF92F6E78CAE0CB97");
382
383 mpi_fromstr(expected, "0x\
384 1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
385 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
386 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
387 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
388 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003051300\
389 D0609608648016503040203050004406255509399A3AF322C486C770C5F7F6E05E18FC\
390 3E2219A03CA56C7501426A597187468B2F71B4A198C807171B73D0E7DBC3EEF6EA6AFF\
391 693DE58E18FF84395BE");
392 result = mpi_alloc( mpi_get_nlimbs(expected) );
393
394 mpi_fromstr(pk.n, "0x\
395 CDD49A674BAF76D3B73E25BC6DF66EF3ABEDDCA461D3CCB6416793E3437C7806562694\
396 73C2212D5FD5EED17AA067FEC001D8E76EC901EDEDF960304F891BD3CAD7F9A335D1A2\
397 EC37EABEFF3FBE6D3C726DC68E599EBFE5456EF19813398CD7D548D746A30AA47D4293\
398 968BFBAFCBF65A90DFFC87816FEE2A01E1DC699F4DDABB84965514C0D909D54FDA7062\
399 A2037B50B771C153D5429BA4BA335EAB840F9551E9CD9DF8BB4A6DC3ED1318FF3969F7\
400 B99D9FB90CAB968813F8AD4F9A069C9639A74D70A659C69C29692567CE863B88E191CC\
401 9535B91B417D0AF14BE09C78B53AF9C5F494BCF2C60349FFA93C81E817AC682F0055A6\
402 07BB56D6A281C1A04CEFE1");
403
404 mpi_fromstr( pk.e, "0x10001");
405
406 mpi_print( stdout, msg, 1);
407 printf("\n");
408
409 public_rsa( result, msg, &pk);
410 if ( mpi_cmp( result, expected) != 0 )
411 printf( "FAILED\n");
412 else
413 printf( "PASSED\n");
414
415 printf("Expected:\n");
416 mpi_print( stdout, expected, 1);
417 printf("\n");
418
419 printf("Obtained:\n");
420 mpi_print( stdout, result, 1);
421 printf("\n");
422
423 mpi_free( pk.n );
424 mpi_free( pk.e );
425 mpi_free( msg );
426 mpi_free( expected );
427 mpi_free( result );
428 }
429
430 void time_rsa_gen( int nruns ) {
431 struct timespec tstart, tend;
432 long int diff;
433 int i;
434
435 RSA_secret_key sk;
436 int noctets = KEY_LENGTH_OCTETS;
437 int noctets_pq = noctets / 2;
438 int nlimbs = mpi_nlimb_hint_from_nbytes(noctets);
439 int nlimbs_pq = mpi_nlimb_hint_from_nbytes(noctets_pq);
440 sk.n = mpi_alloc(nlimbs);
441 sk.e = mpi_alloc(nlimbs);
442 sk.d = mpi_alloc(nlimbs);
443 sk.p = mpi_alloc(nlimbs_pq);
444 sk.q = mpi_alloc(nlimbs_pq);
445 sk.u = mpi_alloc(nlimbs_pq);
446
447 clock_gettime(CLOCK_MONOTONIC, &tstart);
448 for (i = 0;i < nruns; i++) {
449 gen_keypair(&sk);
450 }
451 clock_gettime(CLOCK_MONOTONIC, &tend);
452
453 diff = tend.tv_sec-tstart.tv_sec;
454
455 printf("TOTAL: %ld seconds for generating %d key pairs\n", diff, nruns);
456 printf("Average (%d runs): %f seconds per TMSR RSA key pair.\n",
457 nruns, diff / (1.0*nruns));
458 mpi_free(sk.n);
459 mpi_free(sk.e);
460 mpi_free(sk.d);
461 mpi_free(sk.p);
462 mpi_free(sk.q);
463 mpi_free(sk.u);
464 }
465
466 int main(int ac, char **av)
467 {
468 int nruns;
469 int id;
470 FILE *fk;
471 FILE *fout;
472
473 if (ac<2) {
474 printf("Usage: %s number_of_runs/octets [testID]\n", av[0]);
(236 . 6)(460 . 25)
476 case 5:
477 time_rpng(nruns);
478 break;
479 case 6:
480 fk = fopen("keys.asc", "a");
481 if ( fk == NULL )
482 err("Failed to open file keys.asc!");
483 fout = fopen("check_keys.asc", "a");
484 if ( fout == NULL ) {
485 fclose(fk);
486 err("Failed to open file keys_check.asc!");
487 }
488 test_rsa(nruns, fk, fout);
489 fclose(fk);
490 fclose(fout);
491 break;
492 case 7:
493 test_rsa_exp();
494 break;
495 case 8:
496 time_rsa_gen(nruns);
497 break;
498 default:
499 printf("Current test ids:\n");
500 printf("0 for timing entropy source\n");
(244 . 6)(487 . 10)
502 printf("3 for timing Miller-Rabin\n");
503 printf("4 for random prime number generator test\n");
504 printf("5 for timing random prime number generator\n");
505 printf("6 for testing rsa key pair generation and use; \
506 writes to keys.asc and check_keys.asc\n");
507 printf("7 for testing rsa exponentiation (fixed data)\n");
508 printf("8 for timing rsa key pair generator\n");
509 }
510
511 return 0;