2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
37 * Pointers to implementations.
41 void (*zero)(uint32_t *x, uint32_t bit_len);
42 void (*decode)(uint32_t *x, const void *src, size_t len);
43 uint32_t (*decode_mod)(uint32_t *x,
44 const void *src, size_t len, const uint32_t *m);
45 void (*reduce)(uint32_t *x, const uint32_t *a, const uint32_t *m);
46 void (*decode_reduce)(uint32_t *x,
47 const void *src, size_t len, const uint32_t *m);
48 void (*encode)(void *dst, size_t len, const uint32_t *x);
49 uint32_t (*add)(uint32_t *a, const uint32_t *b, uint32_t ctl);
50 uint32_t (*sub)(uint32_t *a, const uint32_t *b, uint32_t ctl);
51 uint32_t (*ninv)(uint32_t x);
52 void (*montymul)(uint32_t *d, const uint32_t *x, const uint32_t *y,
53 const uint32_t *m, uint32_t m0i);
54 void (*to_monty)(uint32_t *x, const uint32_t *m);
55 void (*from_monty)(uint32_t *x, const uint32_t *m, uint32_t m0i);
56 void (*modpow)(uint32_t *x, const unsigned char *e, size_t elen,
57 const uint32_t *m, uint32_t m0i, uint32_t *t1, uint32_t *t2);
60 static const int_impl i31_impl = {
66 &br_i31_decode_reduce,
76 static const int_impl i32_impl = {
82 &br_i32_decode_reduce,
93 static const int_impl *impl;
95 static gmp_randstate_t RNG;
98 * Get a random prime of length 'size' bits. This function also guarantees
99 * that x-1 is not a multiple of 65537.
102 rand_prime(mpz_t x, int size)
105 mpz_urandomb(x, RNG, size - 1);
107 mpz_setbit(x, size - 1);
108 if (mpz_probab_prime_p(x, 50)) {
110 if (mpz_divisible_ui_p(x, 65537)) {
120 * Print out a GMP integer (for debug).
125 unsigned char zb[1000];
128 mpz_export(zb, &zlen, 1, 1, 0, 0, z);
133 if ((zlen & 3) != 0) {
135 memmove(zb + k, zb, zlen);
139 for (k = 0; k < zlen; k += 4) {
140 printf(" %02X%02X%02X%02X",
141 zb[k], zb[k + 1], zb[k + 2], zb[k + 3]);
146 * Print out an i31 or i32 integer (for debug).
154 printf(" 00000000 (0, 0)");
157 for (k = (x[0] + 31) >> 5; k > 0; k --) {
158 printf(" %08lX", (unsigned long)x[k]);
160 printf(" (%u, %u)", (unsigned)(x[0] >> 5), (unsigned)(x[0] & 31));
164 * Check that an i31/i32 number and a GMP number are equal.
167 check_eqz(uint32_t *x, mpz_t z)
169 unsigned char xb[1000];
170 unsigned char zb[1000];
174 xlen = ((x[0] + 31) & ~(uint32_t)31) >> 3;
175 impl->encode(xb, xlen, x);
176 mpz_export(zb, &zlen, 1, 1, 0, 0, z);
180 } else if (xlen > zlen) {
183 for (u = xlen; u > zlen; u --) {
184 if (xb[xlen - u] != 0) {
190 good = good && memcmp(xb + xlen - zlen, zb, zlen) == 0;
194 printf("Mismatch:\n");
199 for (u = 0; u < xlen; u ++) {
200 printf("%02X", xb[u]);
212 mp_to_br(uint32_t *mx, uint32_t x_bitlen, mpz_t x)
217 if (mpz_sizeinbase(x, 2) > x_bitlen) {
220 x_ebitlen = ((x_bitlen / 31) << 5) + (x_bitlen % 31);
221 br_i31_zero(mx, x_ebitlen);
222 mpz_export(mx + 1, &xlen, -1, sizeof *mx, 0, 1, x);
230 mpz_t p, a, b, v, t1;
232 printf("Test modular integers: ");
235 gmp_randinit_mt(RNG);
241 mpz_set_ui(t1, (unsigned long)time(NULL));
242 gmp_randseed(RNG, t1);
243 for (k = 2; k <= 128; k ++) {
244 for (i = 0; i < 10; i ++) {
245 unsigned char ep[100], ea[100], eb[100], ev[100];
246 size_t plen, alen, blen, vlen;
247 uint32_t mp[40], ma[40], mb[40], mv[60], mx[100];
248 uint32_t mt1[40], mt2[40], mt3[40];
253 mpz_urandomm(a, RNG, p);
254 mpz_urandomm(b, RNG, p);
255 mpz_urandomb(v, RNG, k + 60);
256 if (mpz_sgn(b) == 0) {
259 mpz_export(ep, &plen, 1, 1, 0, 0, p);
260 mpz_export(ea, &alen, 1, 1, 0, 0, a);
261 mpz_export(eb, &blen, 1, 1, 0, 0, b);
262 mpz_export(ev, &vlen, 1, 1, 0, 0, v);
264 impl->decode(mp, ep, plen);
265 if (impl->decode_mod(ma, ea, alen, mp) != 1) {
266 printf("Decode error\n");
275 mp0i = impl->ninv(mp[1]);
276 if (impl->decode_mod(mb, eb, blen, mp) != 1) {
277 printf("Decode error\n");
286 impl->decode(mv, ev, vlen);
292 impl->decode_mod(ma, ea, alen, mp);
293 impl->decode_mod(mb, eb, blen, mp);
294 ctl = impl->add(ma, mb, 1);
295 ctl |= impl->sub(ma, mp, 0) ^ (uint32_t)1;
296 impl->sub(ma, mp, ctl);
301 impl->decode_mod(ma, ea, alen, mp);
302 impl->decode_mod(mb, eb, blen, mp);
303 impl->add(ma, mp, impl->sub(ma, mb, 1));
308 impl->decode_reduce(ma, ev, vlen, mp);
312 impl->decode(mv, ev, vlen);
313 impl->reduce(ma, mv, mp);
317 impl->decode_mod(ma, ea, alen, mp);
318 impl->to_monty(ma, mp);
319 mpz_mul_2exp(t1, a, ((k + impl->word_size - 1)
320 / impl->word_size) * impl->word_size);
323 impl->from_monty(ma, mp, mp0i);
326 impl->decode_mod(ma, ea, alen, mp);
327 impl->decode_mod(mb, eb, blen, mp);
328 impl->to_monty(ma, mp);
329 impl->montymul(mt1, ma, mb, mp, mp0i);
334 impl->decode_mod(ma, ea, alen, mp);
335 impl->modpow(ma, ev, vlen, mp, mp0i, mt1, mt2);
336 mpz_powm(t1, a, v, p);
340 br_modint_decode(ma, mp, ea, alen);
341 br_modint_decode(mb, mp, eb, blen);
342 if (!br_modint_div(ma, mb, mp, mt1, mt2, mt3)) {
343 fprintf(stderr, "division failed\n");
346 mpz_sub_ui(t1, p, 2);
347 mpz_powm(t1, b, t1, p);
352 br_modint_decode(ma, mp, ea, alen);
353 br_modint_decode(mb, mp, eb, blen);
354 for (j = 0; j <= (2 * k + 5); j ++) {
355 br_int_add(mx, j, ma, mb);
357 mpz_tdiv_r_2exp(t1, t1, j);
360 br_int_mul(mx, j, ma, mb);
362 mpz_tdiv_r_2exp(t1, t1, j);
385 mpz_t n, e, d, p, q, dp, dq, iq, t1, t2, phi;
387 printf("Test RSA core: ");
390 gmp_randinit_mt(RNG);
402 mpz_set_ui(t1, (unsigned long)time(NULL));
403 gmp_randseed(RNG, t1);
406 * To test corner cases, we want to try RSA keys such that the
407 * lengths of both factors can be arbitrary modulo 2^32. Factors
408 * p and q need not be of the same length; p can be greater than
409 * q and q can be greater than p.
411 * To keep computation time reasonable, we use p and q factors of
412 * less than 128 bits; this is way too small for secure RSA,
413 * but enough to exercise all code paths (since we work only with
416 for (i = 64; i <= 96; i ++) {
418 for (j = i - 33; j <= i + 33; j ++) {
419 uint32_t mp[40], mq[40], mdp[40], mdq[40], miq[40];
422 * Generate a RSA key pair, with p of length i bits,
423 * and q of length j bits.
427 } while (mpz_cmp(p, q) == 0);
429 mpz_set_ui(e, 65537);
430 mpz_sub_ui(t1, p, 1);
431 mpz_sub_ui(t2, q, 1);
432 mpz_mul(phi, t1, t2);
433 mpz_invert(d, e, phi);
436 mpz_invert(iq, q, p);
439 * Convert the key pair elements to BearSSL arrays.
441 mp_to_br(mp, mpz_sizeinbase(p, 2), p);
442 mp_to_br(mq, mpz_sizeinbase(q, 2), q);
443 mp_to_br(mdp, mpz_sizeinbase(dp, 2), dp);
444 mp_to_br(mdq, mpz_sizeinbase(dq, 2), dq);
445 mp_to_br(miq, mp[0], iq);
448 * Compute and check ten public/private operations.
450 for (k = 0; k < 10; k ++) {
453 mpz_urandomm(t1, RNG, n);
454 mpz_powm(t2, t1, e, n);
455 mp_to_br(mx, mpz_sizeinbase(n, 2), t2);
456 br_rsa_private_core(mx, mp, mq, mdp, mdq, miq);
472 printf("===== i32 ======\n");
475 printf("===== i31 ======\n");