xref: /openssl/test/exptest.c (revision da1c088f)
1 /*
2  * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9 
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 
14 #include "internal/nelem.h"
15 
16 #include <openssl/bio.h>
17 #include <openssl/bn.h>
18 #include <openssl/rand.h>
19 #include <openssl/err.h>
20 
21 #include "testutil.h"
22 
23 #define NUM_BITS        (BN_BITS2 * 4)
24 
25 #define BN_print_var(v) test_output_bignum(#v, v)
26 
27 /*
28  * Test that r == 0 in test_exp_mod_zero(). Returns one on success,
29  * returns zero and prints debug output otherwise.
30  */
a_is_zero_mod_one(const char * method,const BIGNUM * r,const BIGNUM * a)31 static int a_is_zero_mod_one(const char *method, const BIGNUM *r,
32                              const BIGNUM *a)
33 {
34     if (!BN_is_zero(r)) {
35         TEST_error("%s failed: a ** 0 mod 1 = r (should be 0)", method);
36         BN_print_var(a);
37         BN_print_var(r);
38         return 0;
39     }
40     return 1;
41 }
42 
43 /*
44  * test_mod_exp_zero tests that x**0 mod 1 == 0. It returns zero on success.
45  */
test_mod_exp_zero(void)46 static int test_mod_exp_zero(void)
47 {
48     BIGNUM *a = NULL, *p = NULL, *m = NULL;
49     BIGNUM *r = NULL;
50     BN_ULONG one_word = 1;
51     BN_CTX *ctx = BN_CTX_new();
52     int ret = 0, failed = 0;
53     BN_MONT_CTX *mont = NULL;
54 
55     if (!TEST_ptr(m = BN_new())
56         || !TEST_ptr(a = BN_new())
57         || !TEST_ptr(p = BN_new())
58         || !TEST_ptr(r = BN_new()))
59         goto err;
60 
61     BN_one(m);
62     BN_one(a);
63     BN_zero(p);
64 
65     if (!TEST_true(BN_rand(a, 1024, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)))
66         goto err;
67 
68     if (!TEST_true(BN_mod_exp(r, a, p, m, ctx)))
69         goto err;
70 
71     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp", r, a)))
72         failed = 1;
73 
74     if (!TEST_true(BN_mod_exp_recp(r, a, p, m, ctx)))
75         goto err;
76 
77     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_recp", r, a)))
78         failed = 1;
79 
80     if (!TEST_true(BN_mod_exp_simple(r, a, p, m, ctx)))
81         goto err;
82 
83     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_simple", r, a)))
84         failed = 1;
85 
86     if (!TEST_true(BN_mod_exp_mont(r, a, p, m, ctx, NULL)))
87         goto err;
88 
89     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont", r, a)))
90         failed = 1;
91 
92     if (!TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, ctx, NULL)))
93         goto err;
94 
95     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))
96         failed = 1;
97 
98     if (!TEST_ptr(mont = BN_MONT_CTX_new()))
99         goto err;
100 
101     ERR_set_mark();
102     /* mont is not set but passed in */
103     if (!TEST_false(BN_mod_exp_mont_consttime(r, p, a, m, ctx, mont)))
104         goto err;
105     if (!TEST_false(BN_mod_exp_mont(r, p, a, m, ctx, mont)))
106         goto err;
107     ERR_pop_to_mark();
108 
109     if (!TEST_true(BN_MONT_CTX_set(mont, m, ctx)))
110         goto err;
111 
112     /* we compute 0 ** a mod 1 here, to execute code that uses mont */
113     if (!TEST_true(BN_mod_exp_mont_consttime(r, p, a, m, ctx, mont)))
114         goto err;
115 
116     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))
117         failed = 1;
118 
119     if (!TEST_true(BN_mod_exp_mont(r, p, a, m, ctx, mont)))
120         goto err;
121 
122     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont", r, a)))
123         failed = 1;
124 
125     /*
126      * A different codepath exists for single word multiplication
127      * in non-constant-time only.
128      */
129     if (!TEST_true(BN_mod_exp_mont_word(r, one_word, p, m, ctx, NULL)))
130         goto err;
131 
132     if (!TEST_BN_eq_zero(r)) {
133         TEST_error("BN_mod_exp_mont_word failed: "
134                    "1 ** 0 mod 1 = r (should be 0)");
135         BN_print_var(r);
136         goto err;
137     }
138 
139     ret = !failed;
140  err:
141     BN_free(r);
142     BN_free(a);
143     BN_free(p);
144     BN_free(m);
145     BN_MONT_CTX_free(mont);
146     BN_CTX_free(ctx);
147 
148     return ret;
149 }
150 
test_mod_exp(int round)151 static int test_mod_exp(int round)
152 {
153     BN_CTX *ctx;
154     unsigned char c;
155     int ret = 0;
156     BIGNUM *r_mont = NULL;
157     BIGNUM *r_mont_const = NULL;
158     BIGNUM *r_recp = NULL;
159     BIGNUM *r_simple = NULL;
160     BIGNUM *a = NULL;
161     BIGNUM *b = NULL;
162     BIGNUM *m = NULL;
163 
164     if (!TEST_ptr(ctx = BN_CTX_new()))
165         goto err;
166 
167     if (!TEST_ptr(r_mont = BN_new())
168         || !TEST_ptr(r_mont_const = BN_new())
169         || !TEST_ptr(r_recp = BN_new())
170         || !TEST_ptr(r_simple = BN_new())
171         || !TEST_ptr(a = BN_new())
172         || !TEST_ptr(b = BN_new())
173         || !TEST_ptr(m = BN_new()))
174         goto err;
175 
176     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
177         goto err;
178     c = (c % BN_BITS) - BN_BITS2;
179     if (!TEST_true(BN_rand(a, NUM_BITS + c, BN_RAND_TOP_ONE,
180                            BN_RAND_BOTTOM_ANY)))
181         goto err;
182 
183     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
184         goto err;
185     c = (c % BN_BITS) - BN_BITS2;
186     if (!TEST_true(BN_rand(b, NUM_BITS + c, BN_RAND_TOP_ONE,
187                            BN_RAND_BOTTOM_ANY)))
188         goto err;
189 
190     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
191         goto err;
192     c = (c % BN_BITS) - BN_BITS2;
193     if (!TEST_true(BN_rand(m, NUM_BITS + c, BN_RAND_TOP_ONE,
194                            BN_RAND_BOTTOM_ODD)))
195         goto err;
196 
197     if (!TEST_true(BN_mod(a, a, m, ctx))
198         || !TEST_true(BN_mod(b, b, m, ctx))
199         || !TEST_true(BN_mod_exp_mont(r_mont, a, b, m, ctx, NULL))
200         || !TEST_true(BN_mod_exp_recp(r_recp, a, b, m, ctx))
201         || !TEST_true(BN_mod_exp_simple(r_simple, a, b, m, ctx))
202         || !TEST_true(BN_mod_exp_mont_consttime(r_mont_const, a, b, m, ctx, NULL)))
203         goto err;
204 
205     if (!TEST_BN_eq(r_simple, r_mont)
206         || !TEST_BN_eq(r_simple, r_recp)
207         || !TEST_BN_eq(r_simple, r_mont_const)) {
208         if (BN_cmp(r_simple, r_mont) != 0)
209             TEST_info("simple and mont results differ");
210         if (BN_cmp(r_simple, r_mont_const) != 0)
211             TEST_info("simple and mont const time results differ");
212         if (BN_cmp(r_simple, r_recp) != 0)
213             TEST_info("simple and recp results differ");
214 
215         BN_print_var(a);
216         BN_print_var(b);
217         BN_print_var(m);
218         BN_print_var(r_simple);
219         BN_print_var(r_recp);
220         BN_print_var(r_mont);
221         BN_print_var(r_mont_const);
222         goto err;
223     }
224 
225     ret = 1;
226  err:
227     BN_free(r_mont);
228     BN_free(r_mont_const);
229     BN_free(r_recp);
230     BN_free(r_simple);
231     BN_free(a);
232     BN_free(b);
233     BN_free(m);
234     BN_CTX_free(ctx);
235 
236     return ret;
237 }
238 
test_mod_exp_x2(int idx)239 static int test_mod_exp_x2(int idx)
240 {
241     BN_CTX *ctx;
242     int ret = 0;
243     BIGNUM *r_mont_const_x2_1 = NULL;
244     BIGNUM *r_mont_const_x2_2 = NULL;
245     BIGNUM *r_simple1 = NULL;
246     BIGNUM *r_simple2 = NULL;
247     BIGNUM *a1 = NULL;
248     BIGNUM *b1 = NULL;
249     BIGNUM *m1 = NULL;
250     BIGNUM *a2 = NULL;
251     BIGNUM *b2 = NULL;
252     BIGNUM *m2 = NULL;
253     int factor_size = 0;
254 
255     if (idx <= 100)
256         factor_size = 1024;
257     else if (idx <= 200)
258         factor_size = 1536;
259     else if (idx <= 300)
260         factor_size = 2048;
261 
262     if (!TEST_ptr(ctx = BN_CTX_new()))
263         goto err;
264 
265     if (!TEST_ptr(r_mont_const_x2_1 = BN_new())
266         || !TEST_ptr(r_mont_const_x2_2 = BN_new())
267         || !TEST_ptr(r_simple1 = BN_new())
268         || !TEST_ptr(r_simple2 = BN_new())
269         || !TEST_ptr(a1 = BN_new())
270         || !TEST_ptr(b1 = BN_new())
271         || !TEST_ptr(m1 = BN_new())
272         || !TEST_ptr(a2 = BN_new())
273         || !TEST_ptr(b2 = BN_new())
274         || !TEST_ptr(m2 = BN_new()))
275         goto err;
276 
277     BN_rand(a1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
278     BN_rand(b1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
279     BN_rand(m1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD);
280     BN_rand(a2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
281     BN_rand(b2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
282     BN_rand(m2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD);
283 
284     if (!TEST_true(BN_mod(a1, a1, m1, ctx))
285         || !TEST_true(BN_mod(b1, b1, m1, ctx))
286         || !TEST_true(BN_mod(a2, a2, m2, ctx))
287         || !TEST_true(BN_mod(b2, b2, m2, ctx))
288         || !TEST_true(BN_mod_exp_simple(r_simple1, a1, b1, m1, ctx))
289         || !TEST_true(BN_mod_exp_simple(r_simple2, a2, b2, m2, ctx))
290         || !TEST_true(BN_mod_exp_mont_consttime_x2(r_mont_const_x2_1, a1, b1, m1, NULL,
291                                                    r_mont_const_x2_2, a2, b2, m2, NULL,
292                                                    ctx)))
293         goto err;
294 
295     if (!TEST_BN_eq(r_simple1, r_mont_const_x2_1)
296         || !TEST_BN_eq(r_simple2, r_mont_const_x2_2)) {
297         if (BN_cmp(r_simple1, r_mont_const_x2_1) != 0)
298             TEST_info("simple and mont const time x2 (#1) results differ");
299         if (BN_cmp(r_simple2, r_mont_const_x2_2) != 0)
300             TEST_info("simple and mont const time x2 (#2) results differ");
301 
302         BN_print_var(a1);
303         BN_print_var(b1);
304         BN_print_var(m1);
305         BN_print_var(a2);
306         BN_print_var(b2);
307         BN_print_var(m2);
308         BN_print_var(r_simple1);
309         BN_print_var(r_simple2);
310         BN_print_var(r_mont_const_x2_1);
311         BN_print_var(r_mont_const_x2_2);
312         goto err;
313     }
314 
315     ret = 1;
316  err:
317     BN_free(r_mont_const_x2_1);
318     BN_free(r_mont_const_x2_2);
319     BN_free(r_simple1);
320     BN_free(r_simple2);
321     BN_free(a1);
322     BN_free(b1);
323     BN_free(m1);
324     BN_free(a2);
325     BN_free(b2);
326     BN_free(m2);
327     BN_CTX_free(ctx);
328 
329     return ret;
330 }
331 
setup_tests(void)332 int setup_tests(void)
333 {
334     ADD_TEST(test_mod_exp_zero);
335     ADD_ALL_TESTS(test_mod_exp, 200);
336     ADD_ALL_TESTS(test_mod_exp_x2, 300);
337     return 1;
338 }
339