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");