1*0957b409SSimon J. Gerraty /* 2*0957b409SSimon J. Gerraty * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> 3*0957b409SSimon J. Gerraty * 4*0957b409SSimon J. Gerraty * Permission is hereby granted, free of charge, to any person obtaining 5*0957b409SSimon J. Gerraty * a copy of this software and associated documentation files (the 6*0957b409SSimon J. Gerraty * "Software"), to deal in the Software without restriction, including 7*0957b409SSimon J. Gerraty * without limitation the rights to use, copy, modify, merge, publish, 8*0957b409SSimon J. Gerraty * distribute, sublicense, and/or sell copies of the Software, and to 9*0957b409SSimon J. Gerraty * permit persons to whom the Software is furnished to do so, subject to 10*0957b409SSimon J. Gerraty * the following conditions: 11*0957b409SSimon J. Gerraty * 12*0957b409SSimon J. Gerraty * The above copyright notice and this permission notice shall be 13*0957b409SSimon J. Gerraty * included in all copies or substantial portions of the Software. 14*0957b409SSimon J. Gerraty * 15*0957b409SSimon J. Gerraty * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16*0957b409SSimon J. Gerraty * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17*0957b409SSimon J. Gerraty * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18*0957b409SSimon J. Gerraty * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19*0957b409SSimon J. Gerraty * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20*0957b409SSimon J. Gerraty * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21*0957b409SSimon J. Gerraty * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22*0957b409SSimon J. Gerraty * SOFTWARE. 23*0957b409SSimon J. Gerraty */ 24*0957b409SSimon J. Gerraty 25*0957b409SSimon J. Gerraty #include <stdio.h> 26*0957b409SSimon J. Gerraty #include <stdlib.h> 27*0957b409SSimon J. Gerraty #include <string.h> 28*0957b409SSimon J. Gerraty #include <stdarg.h> 29*0957b409SSimon J. Gerraty #include <time.h> 30*0957b409SSimon J. Gerraty 31*0957b409SSimon J. Gerraty #include <gmp.h> 32*0957b409SSimon J. Gerraty 33*0957b409SSimon J. Gerraty #include "bearssl.h" 34*0957b409SSimon J. Gerraty #include "inner.h" 35*0957b409SSimon J. Gerraty 36*0957b409SSimon J. Gerraty /* 37*0957b409SSimon J. Gerraty * Pointers to implementations. 38*0957b409SSimon J. Gerraty */ 39*0957b409SSimon J. Gerraty typedef struct { 40*0957b409SSimon J. Gerraty uint32_t word_size; 41*0957b409SSimon J. Gerraty void (*zero)(uint32_t *x, uint32_t bit_len); 42*0957b409SSimon J. Gerraty void (*decode)(uint32_t *x, const void *src, size_t len); 43*0957b409SSimon J. Gerraty uint32_t (*decode_mod)(uint32_t *x, 44*0957b409SSimon J. Gerraty const void *src, size_t len, const uint32_t *m); 45*0957b409SSimon J. Gerraty void (*reduce)(uint32_t *x, const uint32_t *a, const uint32_t *m); 46*0957b409SSimon J. Gerraty void (*decode_reduce)(uint32_t *x, 47*0957b409SSimon J. Gerraty const void *src, size_t len, const uint32_t *m); 48*0957b409SSimon J. Gerraty void (*encode)(void *dst, size_t len, const uint32_t *x); 49*0957b409SSimon J. Gerraty uint32_t (*add)(uint32_t *a, const uint32_t *b, uint32_t ctl); 50*0957b409SSimon J. Gerraty uint32_t (*sub)(uint32_t *a, const uint32_t *b, uint32_t ctl); 51*0957b409SSimon J. Gerraty uint32_t (*ninv)(uint32_t x); 52*0957b409SSimon J. Gerraty void (*montymul)(uint32_t *d, const uint32_t *x, const uint32_t *y, 53*0957b409SSimon J. Gerraty const uint32_t *m, uint32_t m0i); 54*0957b409SSimon J. Gerraty void (*to_monty)(uint32_t *x, const uint32_t *m); 55*0957b409SSimon J. Gerraty void (*from_monty)(uint32_t *x, const uint32_t *m, uint32_t m0i); 56*0957b409SSimon J. Gerraty void (*modpow)(uint32_t *x, const unsigned char *e, size_t elen, 57*0957b409SSimon J. Gerraty const uint32_t *m, uint32_t m0i, uint32_t *t1, uint32_t *t2); 58*0957b409SSimon J. Gerraty } int_impl; 59*0957b409SSimon J. Gerraty 60*0957b409SSimon J. Gerraty static const int_impl i31_impl = { 61*0957b409SSimon J. Gerraty 31, 62*0957b409SSimon J. Gerraty &br_i31_zero, 63*0957b409SSimon J. Gerraty &br_i31_decode, 64*0957b409SSimon J. Gerraty &br_i31_decode_mod, 65*0957b409SSimon J. Gerraty &br_i31_reduce, 66*0957b409SSimon J. Gerraty &br_i31_decode_reduce, 67*0957b409SSimon J. Gerraty &br_i31_encode, 68*0957b409SSimon J. Gerraty &br_i31_add, 69*0957b409SSimon J. Gerraty &br_i31_sub, 70*0957b409SSimon J. Gerraty &br_i31_ninv31, 71*0957b409SSimon J. Gerraty &br_i31_montymul, 72*0957b409SSimon J. Gerraty &br_i31_to_monty, 73*0957b409SSimon J. Gerraty &br_i31_from_monty, 74*0957b409SSimon J. Gerraty &br_i31_modpow 75*0957b409SSimon J. Gerraty }; 76*0957b409SSimon J. Gerraty static const int_impl i32_impl = { 77*0957b409SSimon J. Gerraty 32, 78*0957b409SSimon J. Gerraty &br_i32_zero, 79*0957b409SSimon J. Gerraty &br_i32_decode, 80*0957b409SSimon J. Gerraty &br_i32_decode_mod, 81*0957b409SSimon J. Gerraty &br_i32_reduce, 82*0957b409SSimon J. Gerraty &br_i32_decode_reduce, 83*0957b409SSimon J. Gerraty &br_i32_encode, 84*0957b409SSimon J. Gerraty &br_i32_add, 85*0957b409SSimon J. Gerraty &br_i32_sub, 86*0957b409SSimon J. Gerraty &br_i32_ninv32, 87*0957b409SSimon J. Gerraty &br_i32_montymul, 88*0957b409SSimon J. Gerraty &br_i32_to_monty, 89*0957b409SSimon J. Gerraty &br_i32_from_monty, 90*0957b409SSimon J. Gerraty &br_i32_modpow 91*0957b409SSimon J. Gerraty }; 92*0957b409SSimon J. Gerraty 93*0957b409SSimon J. Gerraty static const int_impl *impl; 94*0957b409SSimon J. Gerraty 95*0957b409SSimon J. Gerraty static gmp_randstate_t RNG; 96*0957b409SSimon J. Gerraty 97*0957b409SSimon J. Gerraty /* 98*0957b409SSimon J. Gerraty * Get a random prime of length 'size' bits. This function also guarantees 99*0957b409SSimon J. Gerraty * that x-1 is not a multiple of 65537. 100*0957b409SSimon J. Gerraty */ 101*0957b409SSimon J. Gerraty static void 102*0957b409SSimon J. Gerraty rand_prime(mpz_t x, int size) 103*0957b409SSimon J. Gerraty { 104*0957b409SSimon J. Gerraty for (;;) { 105*0957b409SSimon J. Gerraty mpz_urandomb(x, RNG, size - 1); 106*0957b409SSimon J. Gerraty mpz_setbit(x, 0); 107*0957b409SSimon J. Gerraty mpz_setbit(x, size - 1); 108*0957b409SSimon J. Gerraty if (mpz_probab_prime_p(x, 50)) { 109*0957b409SSimon J. Gerraty mpz_sub_ui(x, x, 1); 110*0957b409SSimon J. Gerraty if (mpz_divisible_ui_p(x, 65537)) { 111*0957b409SSimon J. Gerraty continue; 112*0957b409SSimon J. Gerraty } 113*0957b409SSimon J. Gerraty mpz_add_ui(x, x, 1); 114*0957b409SSimon J. Gerraty return; 115*0957b409SSimon J. Gerraty } 116*0957b409SSimon J. Gerraty } 117*0957b409SSimon J. Gerraty } 118*0957b409SSimon J. Gerraty 119*0957b409SSimon J. Gerraty /* 120*0957b409SSimon J. Gerraty * Print out a GMP integer (for debug). 121*0957b409SSimon J. Gerraty */ 122*0957b409SSimon J. Gerraty static void 123*0957b409SSimon J. Gerraty print_z(mpz_t z) 124*0957b409SSimon J. Gerraty { 125*0957b409SSimon J. Gerraty unsigned char zb[1000]; 126*0957b409SSimon J. Gerraty size_t zlen, k; 127*0957b409SSimon J. Gerraty 128*0957b409SSimon J. Gerraty mpz_export(zb, &zlen, 1, 1, 0, 0, z); 129*0957b409SSimon J. Gerraty if (zlen == 0) { 130*0957b409SSimon J. Gerraty printf(" 00"); 131*0957b409SSimon J. Gerraty return; 132*0957b409SSimon J. Gerraty } 133*0957b409SSimon J. Gerraty if ((zlen & 3) != 0) { 134*0957b409SSimon J. Gerraty k = 4 - (zlen & 3); 135*0957b409SSimon J. Gerraty memmove(zb + k, zb, zlen); 136*0957b409SSimon J. Gerraty memset(zb, 0, k); 137*0957b409SSimon J. Gerraty zlen += k; 138*0957b409SSimon J. Gerraty } 139*0957b409SSimon J. Gerraty for (k = 0; k < zlen; k += 4) { 140*0957b409SSimon J. Gerraty printf(" %02X%02X%02X%02X", 141*0957b409SSimon J. Gerraty zb[k], zb[k + 1], zb[k + 2], zb[k + 3]); 142*0957b409SSimon J. Gerraty } 143*0957b409SSimon J. Gerraty } 144*0957b409SSimon J. Gerraty 145*0957b409SSimon J. Gerraty /* 146*0957b409SSimon J. Gerraty * Print out an i31 or i32 integer (for debug). 147*0957b409SSimon J. Gerraty */ 148*0957b409SSimon J. Gerraty static void 149*0957b409SSimon J. Gerraty print_u(uint32_t *x) 150*0957b409SSimon J. Gerraty { 151*0957b409SSimon J. Gerraty size_t k; 152*0957b409SSimon J. Gerraty 153*0957b409SSimon J. Gerraty if (x[0] == 0) { 154*0957b409SSimon J. Gerraty printf(" 00000000 (0, 0)"); 155*0957b409SSimon J. Gerraty return; 156*0957b409SSimon J. Gerraty } 157*0957b409SSimon J. Gerraty for (k = (x[0] + 31) >> 5; k > 0; k --) { 158*0957b409SSimon J. Gerraty printf(" %08lX", (unsigned long)x[k]); 159*0957b409SSimon J. Gerraty } 160*0957b409SSimon J. Gerraty printf(" (%u, %u)", (unsigned)(x[0] >> 5), (unsigned)(x[0] & 31)); 161*0957b409SSimon J. Gerraty } 162*0957b409SSimon J. Gerraty 163*0957b409SSimon J. Gerraty /* 164*0957b409SSimon J. Gerraty * Check that an i31/i32 number and a GMP number are equal. 165*0957b409SSimon J. Gerraty */ 166*0957b409SSimon J. Gerraty static void 167*0957b409SSimon J. Gerraty check_eqz(uint32_t *x, mpz_t z) 168*0957b409SSimon J. Gerraty { 169*0957b409SSimon J. Gerraty unsigned char xb[1000]; 170*0957b409SSimon J. Gerraty unsigned char zb[1000]; 171*0957b409SSimon J. Gerraty size_t xlen, zlen; 172*0957b409SSimon J. Gerraty int good; 173*0957b409SSimon J. Gerraty 174*0957b409SSimon J. Gerraty xlen = ((x[0] + 31) & ~(uint32_t)31) >> 3; 175*0957b409SSimon J. Gerraty impl->encode(xb, xlen, x); 176*0957b409SSimon J. Gerraty mpz_export(zb, &zlen, 1, 1, 0, 0, z); 177*0957b409SSimon J. Gerraty good = 1; 178*0957b409SSimon J. Gerraty if (xlen < zlen) { 179*0957b409SSimon J. Gerraty good = 0; 180*0957b409SSimon J. Gerraty } else if (xlen > zlen) { 181*0957b409SSimon J. Gerraty size_t u; 182*0957b409SSimon J. Gerraty 183*0957b409SSimon J. Gerraty for (u = xlen; u > zlen; u --) { 184*0957b409SSimon J. Gerraty if (xb[xlen - u] != 0) { 185*0957b409SSimon J. Gerraty good = 0; 186*0957b409SSimon J. Gerraty break; 187*0957b409SSimon J. Gerraty } 188*0957b409SSimon J. Gerraty } 189*0957b409SSimon J. Gerraty } 190*0957b409SSimon J. Gerraty good = good && memcmp(xb + xlen - zlen, zb, zlen) == 0; 191*0957b409SSimon J. Gerraty if (!good) { 192*0957b409SSimon J. Gerraty size_t u; 193*0957b409SSimon J. Gerraty 194*0957b409SSimon J. Gerraty printf("Mismatch:\n"); 195*0957b409SSimon J. Gerraty printf(" x = "); 196*0957b409SSimon J. Gerraty print_u(x); 197*0957b409SSimon J. Gerraty printf("\n"); 198*0957b409SSimon J. Gerraty printf(" ex = "); 199*0957b409SSimon J. Gerraty for (u = 0; u < xlen; u ++) { 200*0957b409SSimon J. Gerraty printf("%02X", xb[u]); 201*0957b409SSimon J. Gerraty } 202*0957b409SSimon J. Gerraty printf("\n"); 203*0957b409SSimon J. Gerraty printf(" z = "); 204*0957b409SSimon J. Gerraty print_z(z); 205*0957b409SSimon J. Gerraty printf("\n"); 206*0957b409SSimon J. Gerraty exit(EXIT_FAILURE); 207*0957b409SSimon J. Gerraty } 208*0957b409SSimon J. Gerraty } 209*0957b409SSimon J. Gerraty 210*0957b409SSimon J. Gerraty /* obsolete 211*0957b409SSimon J. Gerraty static void 212*0957b409SSimon J. Gerraty mp_to_br(uint32_t *mx, uint32_t x_bitlen, mpz_t x) 213*0957b409SSimon J. Gerraty { 214*0957b409SSimon J. Gerraty uint32_t x_ebitlen; 215*0957b409SSimon J. Gerraty size_t xlen; 216*0957b409SSimon J. Gerraty 217*0957b409SSimon J. Gerraty if (mpz_sizeinbase(x, 2) > x_bitlen) { 218*0957b409SSimon J. Gerraty abort(); 219*0957b409SSimon J. Gerraty } 220*0957b409SSimon J. Gerraty x_ebitlen = ((x_bitlen / 31) << 5) + (x_bitlen % 31); 221*0957b409SSimon J. Gerraty br_i31_zero(mx, x_ebitlen); 222*0957b409SSimon J. Gerraty mpz_export(mx + 1, &xlen, -1, sizeof *mx, 0, 1, x); 223*0957b409SSimon J. Gerraty } 224*0957b409SSimon J. Gerraty */ 225*0957b409SSimon J. Gerraty 226*0957b409SSimon J. Gerraty static void 227*0957b409SSimon J. Gerraty test_modint(void) 228*0957b409SSimon J. Gerraty { 229*0957b409SSimon J. Gerraty int i, j, k; 230*0957b409SSimon J. Gerraty mpz_t p, a, b, v, t1; 231*0957b409SSimon J. Gerraty 232*0957b409SSimon J. Gerraty printf("Test modular integers: "); 233*0957b409SSimon J. Gerraty fflush(stdout); 234*0957b409SSimon J. Gerraty 235*0957b409SSimon J. Gerraty gmp_randinit_mt(RNG); 236*0957b409SSimon J. Gerraty mpz_init(p); 237*0957b409SSimon J. Gerraty mpz_init(a); 238*0957b409SSimon J. Gerraty mpz_init(b); 239*0957b409SSimon J. Gerraty mpz_init(v); 240*0957b409SSimon J. Gerraty mpz_init(t1); 241*0957b409SSimon J. Gerraty mpz_set_ui(t1, (unsigned long)time(NULL)); 242*0957b409SSimon J. Gerraty gmp_randseed(RNG, t1); 243*0957b409SSimon J. Gerraty for (k = 2; k <= 128; k ++) { 244*0957b409SSimon J. Gerraty for (i = 0; i < 10; i ++) { 245*0957b409SSimon J. Gerraty unsigned char ep[100], ea[100], eb[100], ev[100]; 246*0957b409SSimon J. Gerraty size_t plen, alen, blen, vlen; 247*0957b409SSimon J. Gerraty uint32_t mp[40], ma[40], mb[40], mv[60], mx[100]; 248*0957b409SSimon J. Gerraty uint32_t mt1[40], mt2[40], mt3[40]; 249*0957b409SSimon J. Gerraty uint32_t ctl; 250*0957b409SSimon J. Gerraty uint32_t mp0i; 251*0957b409SSimon J. Gerraty 252*0957b409SSimon J. Gerraty rand_prime(p, k); 253*0957b409SSimon J. Gerraty mpz_urandomm(a, RNG, p); 254*0957b409SSimon J. Gerraty mpz_urandomm(b, RNG, p); 255*0957b409SSimon J. Gerraty mpz_urandomb(v, RNG, k + 60); 256*0957b409SSimon J. Gerraty if (mpz_sgn(b) == 0) { 257*0957b409SSimon J. Gerraty mpz_set_ui(b, 1); 258*0957b409SSimon J. Gerraty } 259*0957b409SSimon J. Gerraty mpz_export(ep, &plen, 1, 1, 0, 0, p); 260*0957b409SSimon J. Gerraty mpz_export(ea, &alen, 1, 1, 0, 0, a); 261*0957b409SSimon J. Gerraty mpz_export(eb, &blen, 1, 1, 0, 0, b); 262*0957b409SSimon J. Gerraty mpz_export(ev, &vlen, 1, 1, 0, 0, v); 263*0957b409SSimon J. Gerraty 264*0957b409SSimon J. Gerraty impl->decode(mp, ep, plen); 265*0957b409SSimon J. Gerraty if (impl->decode_mod(ma, ea, alen, mp) != 1) { 266*0957b409SSimon J. Gerraty printf("Decode error\n"); 267*0957b409SSimon J. Gerraty printf(" ea = "); 268*0957b409SSimon J. Gerraty print_z(a); 269*0957b409SSimon J. Gerraty printf("\n"); 270*0957b409SSimon J. Gerraty printf(" p = "); 271*0957b409SSimon J. Gerraty print_u(mp); 272*0957b409SSimon J. Gerraty printf("\n"); 273*0957b409SSimon J. Gerraty exit(EXIT_FAILURE); 274*0957b409SSimon J. Gerraty } 275*0957b409SSimon J. Gerraty mp0i = impl->ninv(mp[1]); 276*0957b409SSimon J. Gerraty if (impl->decode_mod(mb, eb, blen, mp) != 1) { 277*0957b409SSimon J. Gerraty printf("Decode error\n"); 278*0957b409SSimon J. Gerraty printf(" eb = "); 279*0957b409SSimon J. Gerraty print_z(b); 280*0957b409SSimon J. Gerraty printf("\n"); 281*0957b409SSimon J. Gerraty printf(" p = "); 282*0957b409SSimon J. Gerraty print_u(mp); 283*0957b409SSimon J. Gerraty printf("\n"); 284*0957b409SSimon J. Gerraty exit(EXIT_FAILURE); 285*0957b409SSimon J. Gerraty } 286*0957b409SSimon J. Gerraty impl->decode(mv, ev, vlen); 287*0957b409SSimon J. Gerraty check_eqz(mp, p); 288*0957b409SSimon J. Gerraty check_eqz(ma, a); 289*0957b409SSimon J. Gerraty check_eqz(mb, b); 290*0957b409SSimon J. Gerraty check_eqz(mv, v); 291*0957b409SSimon J. Gerraty 292*0957b409SSimon J. Gerraty impl->decode_mod(ma, ea, alen, mp); 293*0957b409SSimon J. Gerraty impl->decode_mod(mb, eb, blen, mp); 294*0957b409SSimon J. Gerraty ctl = impl->add(ma, mb, 1); 295*0957b409SSimon J. Gerraty ctl |= impl->sub(ma, mp, 0) ^ (uint32_t)1; 296*0957b409SSimon J. Gerraty impl->sub(ma, mp, ctl); 297*0957b409SSimon J. Gerraty mpz_add(t1, a, b); 298*0957b409SSimon J. Gerraty mpz_mod(t1, t1, p); 299*0957b409SSimon J. Gerraty check_eqz(ma, t1); 300*0957b409SSimon J. Gerraty 301*0957b409SSimon J. Gerraty impl->decode_mod(ma, ea, alen, mp); 302*0957b409SSimon J. Gerraty impl->decode_mod(mb, eb, blen, mp); 303*0957b409SSimon J. Gerraty impl->add(ma, mp, impl->sub(ma, mb, 1)); 304*0957b409SSimon J. Gerraty mpz_sub(t1, a, b); 305*0957b409SSimon J. Gerraty mpz_mod(t1, t1, p); 306*0957b409SSimon J. Gerraty check_eqz(ma, t1); 307*0957b409SSimon J. Gerraty 308*0957b409SSimon J. Gerraty impl->decode_reduce(ma, ev, vlen, mp); 309*0957b409SSimon J. Gerraty mpz_mod(t1, v, p); 310*0957b409SSimon J. Gerraty check_eqz(ma, t1); 311*0957b409SSimon J. Gerraty 312*0957b409SSimon J. Gerraty impl->decode(mv, ev, vlen); 313*0957b409SSimon J. Gerraty impl->reduce(ma, mv, mp); 314*0957b409SSimon J. Gerraty mpz_mod(t1, v, p); 315*0957b409SSimon J. Gerraty check_eqz(ma, t1); 316*0957b409SSimon J. Gerraty 317*0957b409SSimon J. Gerraty impl->decode_mod(ma, ea, alen, mp); 318*0957b409SSimon J. Gerraty impl->to_monty(ma, mp); 319*0957b409SSimon J. Gerraty mpz_mul_2exp(t1, a, ((k + impl->word_size - 1) 320*0957b409SSimon J. Gerraty / impl->word_size) * impl->word_size); 321*0957b409SSimon J. Gerraty mpz_mod(t1, t1, p); 322*0957b409SSimon J. Gerraty check_eqz(ma, t1); 323*0957b409SSimon J. Gerraty impl->from_monty(ma, mp, mp0i); 324*0957b409SSimon J. Gerraty check_eqz(ma, a); 325*0957b409SSimon J. Gerraty 326*0957b409SSimon J. Gerraty impl->decode_mod(ma, ea, alen, mp); 327*0957b409SSimon J. Gerraty impl->decode_mod(mb, eb, blen, mp); 328*0957b409SSimon J. Gerraty impl->to_monty(ma, mp); 329*0957b409SSimon J. Gerraty impl->montymul(mt1, ma, mb, mp, mp0i); 330*0957b409SSimon J. Gerraty mpz_mul(t1, a, b); 331*0957b409SSimon J. Gerraty mpz_mod(t1, t1, p); 332*0957b409SSimon J. Gerraty check_eqz(mt1, t1); 333*0957b409SSimon J. Gerraty 334*0957b409SSimon J. Gerraty impl->decode_mod(ma, ea, alen, mp); 335*0957b409SSimon J. Gerraty impl->modpow(ma, ev, vlen, mp, mp0i, mt1, mt2); 336*0957b409SSimon J. Gerraty mpz_powm(t1, a, v, p); 337*0957b409SSimon J. Gerraty check_eqz(ma, t1); 338*0957b409SSimon J. Gerraty 339*0957b409SSimon J. Gerraty /* 340*0957b409SSimon J. Gerraty br_modint_decode(ma, mp, ea, alen); 341*0957b409SSimon J. Gerraty br_modint_decode(mb, mp, eb, blen); 342*0957b409SSimon J. Gerraty if (!br_modint_div(ma, mb, mp, mt1, mt2, mt3)) { 343*0957b409SSimon J. Gerraty fprintf(stderr, "division failed\n"); 344*0957b409SSimon J. Gerraty exit(EXIT_FAILURE); 345*0957b409SSimon J. Gerraty } 346*0957b409SSimon J. Gerraty mpz_sub_ui(t1, p, 2); 347*0957b409SSimon J. Gerraty mpz_powm(t1, b, t1, p); 348*0957b409SSimon J. Gerraty mpz_mul(t1, a, t1); 349*0957b409SSimon J. Gerraty mpz_mod(t1, t1, p); 350*0957b409SSimon J. Gerraty check_eqz(ma, t1); 351*0957b409SSimon J. Gerraty 352*0957b409SSimon J. Gerraty br_modint_decode(ma, mp, ea, alen); 353*0957b409SSimon J. Gerraty br_modint_decode(mb, mp, eb, blen); 354*0957b409SSimon J. Gerraty for (j = 0; j <= (2 * k + 5); j ++) { 355*0957b409SSimon J. Gerraty br_int_add(mx, j, ma, mb); 356*0957b409SSimon J. Gerraty mpz_add(t1, a, b); 357*0957b409SSimon J. Gerraty mpz_tdiv_r_2exp(t1, t1, j); 358*0957b409SSimon J. Gerraty check_eqz(mx, t1); 359*0957b409SSimon J. Gerraty 360*0957b409SSimon J. Gerraty br_int_mul(mx, j, ma, mb); 361*0957b409SSimon J. Gerraty mpz_mul(t1, a, b); 362*0957b409SSimon J. Gerraty mpz_tdiv_r_2exp(t1, t1, j); 363*0957b409SSimon J. Gerraty check_eqz(mx, t1); 364*0957b409SSimon J. Gerraty } 365*0957b409SSimon J. Gerraty */ 366*0957b409SSimon J. Gerraty } 367*0957b409SSimon J. Gerraty printf("."); 368*0957b409SSimon J. Gerraty fflush(stdout); 369*0957b409SSimon J. Gerraty } 370*0957b409SSimon J. Gerraty mpz_clear(p); 371*0957b409SSimon J. Gerraty mpz_clear(a); 372*0957b409SSimon J. Gerraty mpz_clear(b); 373*0957b409SSimon J. Gerraty mpz_clear(v); 374*0957b409SSimon J. Gerraty mpz_clear(t1); 375*0957b409SSimon J. Gerraty 376*0957b409SSimon J. Gerraty printf(" done.\n"); 377*0957b409SSimon J. Gerraty fflush(stdout); 378*0957b409SSimon J. Gerraty } 379*0957b409SSimon J. Gerraty 380*0957b409SSimon J. Gerraty #if 0 381*0957b409SSimon J. Gerraty static void 382*0957b409SSimon J. Gerraty test_RSA_core(void) 383*0957b409SSimon J. Gerraty { 384*0957b409SSimon J. Gerraty int i, j, k; 385*0957b409SSimon J. Gerraty mpz_t n, e, d, p, q, dp, dq, iq, t1, t2, phi; 386*0957b409SSimon J. Gerraty 387*0957b409SSimon J. Gerraty printf("Test RSA core: "); 388*0957b409SSimon J. Gerraty fflush(stdout); 389*0957b409SSimon J. Gerraty 390*0957b409SSimon J. Gerraty gmp_randinit_mt(RNG); 391*0957b409SSimon J. Gerraty mpz_init(n); 392*0957b409SSimon J. Gerraty mpz_init(e); 393*0957b409SSimon J. Gerraty mpz_init(d); 394*0957b409SSimon J. Gerraty mpz_init(p); 395*0957b409SSimon J. Gerraty mpz_init(q); 396*0957b409SSimon J. Gerraty mpz_init(dp); 397*0957b409SSimon J. Gerraty mpz_init(dq); 398*0957b409SSimon J. Gerraty mpz_init(iq); 399*0957b409SSimon J. Gerraty mpz_init(t1); 400*0957b409SSimon J. Gerraty mpz_init(t2); 401*0957b409SSimon J. Gerraty mpz_init(phi); 402*0957b409SSimon J. Gerraty mpz_set_ui(t1, (unsigned long)time(NULL)); 403*0957b409SSimon J. Gerraty gmp_randseed(RNG, t1); 404*0957b409SSimon J. Gerraty 405*0957b409SSimon J. Gerraty /* 406*0957b409SSimon J. Gerraty * To test corner cases, we want to try RSA keys such that the 407*0957b409SSimon J. Gerraty * lengths of both factors can be arbitrary modulo 2^32. Factors 408*0957b409SSimon J. Gerraty * p and q need not be of the same length; p can be greater than 409*0957b409SSimon J. Gerraty * q and q can be greater than p. 410*0957b409SSimon J. Gerraty * 411*0957b409SSimon J. Gerraty * To keep computation time reasonable, we use p and q factors of 412*0957b409SSimon J. Gerraty * less than 128 bits; this is way too small for secure RSA, 413*0957b409SSimon J. Gerraty * but enough to exercise all code paths (since we work only with 414*0957b409SSimon J. Gerraty * 32-bit words). 415*0957b409SSimon J. Gerraty */ 416*0957b409SSimon J. Gerraty for (i = 64; i <= 96; i ++) { 417*0957b409SSimon J. Gerraty rand_prime(p, i); 418*0957b409SSimon J. Gerraty for (j = i - 33; j <= i + 33; j ++) { 419*0957b409SSimon J. Gerraty uint32_t mp[40], mq[40], mdp[40], mdq[40], miq[40]; 420*0957b409SSimon J. Gerraty 421*0957b409SSimon J. Gerraty /* 422*0957b409SSimon J. Gerraty * Generate a RSA key pair, with p of length i bits, 423*0957b409SSimon J. Gerraty * and q of length j bits. 424*0957b409SSimon J. Gerraty */ 425*0957b409SSimon J. Gerraty do { 426*0957b409SSimon J. Gerraty rand_prime(q, j); 427*0957b409SSimon J. Gerraty } while (mpz_cmp(p, q) == 0); 428*0957b409SSimon J. Gerraty mpz_mul(n, p, q); 429*0957b409SSimon J. Gerraty mpz_set_ui(e, 65537); 430*0957b409SSimon J. Gerraty mpz_sub_ui(t1, p, 1); 431*0957b409SSimon J. Gerraty mpz_sub_ui(t2, q, 1); 432*0957b409SSimon J. Gerraty mpz_mul(phi, t1, t2); 433*0957b409SSimon J. Gerraty mpz_invert(d, e, phi); 434*0957b409SSimon J. Gerraty mpz_mod(dp, d, t1); 435*0957b409SSimon J. Gerraty mpz_mod(dq, d, t2); 436*0957b409SSimon J. Gerraty mpz_invert(iq, q, p); 437*0957b409SSimon J. Gerraty 438*0957b409SSimon J. Gerraty /* 439*0957b409SSimon J. Gerraty * Convert the key pair elements to BearSSL arrays. 440*0957b409SSimon J. Gerraty */ 441*0957b409SSimon J. Gerraty mp_to_br(mp, mpz_sizeinbase(p, 2), p); 442*0957b409SSimon J. Gerraty mp_to_br(mq, mpz_sizeinbase(q, 2), q); 443*0957b409SSimon J. Gerraty mp_to_br(mdp, mpz_sizeinbase(dp, 2), dp); 444*0957b409SSimon J. Gerraty mp_to_br(mdq, mpz_sizeinbase(dq, 2), dq); 445*0957b409SSimon J. Gerraty mp_to_br(miq, mp[0], iq); 446*0957b409SSimon J. Gerraty 447*0957b409SSimon J. Gerraty /* 448*0957b409SSimon J. Gerraty * Compute and check ten public/private operations. 449*0957b409SSimon J. Gerraty */ 450*0957b409SSimon J. Gerraty for (k = 0; k < 10; k ++) { 451*0957b409SSimon J. Gerraty uint32_t mx[40]; 452*0957b409SSimon J. Gerraty 453*0957b409SSimon J. Gerraty mpz_urandomm(t1, RNG, n); 454*0957b409SSimon J. Gerraty mpz_powm(t2, t1, e, n); 455*0957b409SSimon J. Gerraty mp_to_br(mx, mpz_sizeinbase(n, 2), t2); 456*0957b409SSimon J. Gerraty br_rsa_private_core(mx, mp, mq, mdp, mdq, miq); 457*0957b409SSimon J. Gerraty check_eqz(mx, t1); 458*0957b409SSimon J. Gerraty } 459*0957b409SSimon J. Gerraty } 460*0957b409SSimon J. Gerraty printf("."); 461*0957b409SSimon J. Gerraty fflush(stdout); 462*0957b409SSimon J. Gerraty } 463*0957b409SSimon J. Gerraty 464*0957b409SSimon J. Gerraty printf(" done.\n"); 465*0957b409SSimon J. Gerraty fflush(stdout); 466*0957b409SSimon J. Gerraty } 467*0957b409SSimon J. Gerraty #endif 468*0957b409SSimon J. Gerraty 469*0957b409SSimon J. Gerraty int 470*0957b409SSimon J. Gerraty main(void) 471*0957b409SSimon J. Gerraty { 472*0957b409SSimon J. Gerraty printf("===== i32 ======\n"); 473*0957b409SSimon J. Gerraty impl = &i32_impl; 474*0957b409SSimon J. Gerraty test_modint(); 475*0957b409SSimon J. Gerraty printf("===== i31 ======\n"); 476*0957b409SSimon J. Gerraty impl = &i31_impl; 477*0957b409SSimon J. Gerraty test_modint(); 478*0957b409SSimon J. Gerraty /* 479*0957b409SSimon J. Gerraty test_RSA_core(); 480*0957b409SSimon J. Gerraty */ 481*0957b409SSimon J. Gerraty return 0; 482*0957b409SSimon J. Gerraty } 483