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
rand_prime(mpz_t x,int size)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
print_z(mpz_t z)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
print_u(uint32_t * x)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
check_eqz(uint32_t * x,mpz_t z)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
test_modint(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
main(void)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