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 */ 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 */ 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 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 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 /* 256 * Currently only 1024-bit factor size is supported. 257 */ 258 if (idx <= 100) 259 factor_size = 1024; 260 261 if (!TEST_ptr(ctx = BN_CTX_new())) 262 goto err; 263 264 if (!TEST_ptr(r_mont_const_x2_1 = BN_new()) 265 || !TEST_ptr(r_mont_const_x2_2 = BN_new()) 266 || !TEST_ptr(r_simple1 = BN_new()) 267 || !TEST_ptr(r_simple2 = BN_new()) 268 || !TEST_ptr(a1 = BN_new()) 269 || !TEST_ptr(b1 = BN_new()) 270 || !TEST_ptr(m1 = BN_new()) 271 || !TEST_ptr(a2 = BN_new()) 272 || !TEST_ptr(b2 = BN_new()) 273 || !TEST_ptr(m2 = BN_new())) 274 goto err; 275 276 BN_rand(a1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 277 BN_rand(b1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 278 BN_rand(m1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD); 279 BN_rand(a2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 280 BN_rand(b2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 281 BN_rand(m2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD); 282 283 if (!TEST_true(BN_mod(a1, a1, m1, ctx)) 284 || !TEST_true(BN_mod(b1, b1, m1, ctx)) 285 || !TEST_true(BN_mod(a2, a2, m2, ctx)) 286 || !TEST_true(BN_mod(b2, b2, m2, ctx)) 287 || !TEST_true(BN_mod_exp_simple(r_simple1, a1, b1, m1, ctx)) 288 || !TEST_true(BN_mod_exp_simple(r_simple2, a2, b2, m2, ctx)) 289 || !TEST_true(BN_mod_exp_mont_consttime_x2(r_mont_const_x2_1, a1, b1, m1, NULL, 290 r_mont_const_x2_2, a2, b2, m2, NULL, 291 ctx))) 292 goto err; 293 294 if (!TEST_BN_eq(r_simple1, r_mont_const_x2_1) 295 || !TEST_BN_eq(r_simple2, r_mont_const_x2_2)) { 296 if (BN_cmp(r_simple1, r_mont_const_x2_1) != 0) 297 TEST_info("simple and mont const time x2 (#1) results differ"); 298 if (BN_cmp(r_simple2, r_mont_const_x2_2) != 0) 299 TEST_info("simple and mont const time x2 (#2) results differ"); 300 301 BN_print_var(a1); 302 BN_print_var(b1); 303 BN_print_var(m1); 304 BN_print_var(a2); 305 BN_print_var(b2); 306 BN_print_var(m2); 307 BN_print_var(r_simple1); 308 BN_print_var(r_simple2); 309 BN_print_var(r_mont_const_x2_1); 310 BN_print_var(r_mont_const_x2_2); 311 goto err; 312 } 313 314 ret = 1; 315 err: 316 BN_free(r_mont_const_x2_1); 317 BN_free(r_mont_const_x2_2); 318 BN_free(r_simple1); 319 BN_free(r_simple2); 320 BN_free(a1); 321 BN_free(b1); 322 BN_free(m1); 323 BN_free(a2); 324 BN_free(b2); 325 BN_free(m2); 326 BN_CTX_free(ctx); 327 328 return ret; 329 } 330 331 int setup_tests(void) 332 { 333 ADD_TEST(test_mod_exp_zero); 334 ADD_ALL_TESTS(test_mod_exp, 200); 335 ADD_ALL_TESTS(test_mod_exp_x2, 100); 336 return 1; 337 } 338