1/* 2 * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (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 */ 31static 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 */ 46static 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 151static 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 RAND_bytes(&c, 1); 177 c = (c % BN_BITS) - BN_BITS2; 178 BN_rand(a, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 179 180 RAND_bytes(&c, 1); 181 c = (c % BN_BITS) - BN_BITS2; 182 BN_rand(b, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY); 183 184 RAND_bytes(&c, 1); 185 c = (c % BN_BITS) - BN_BITS2; 186 BN_rand(m, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD); 187 188 if (!TEST_true(BN_mod(a, a, m, ctx)) 189 || !TEST_true(BN_mod(b, b, m, ctx)) 190 || !TEST_true(BN_mod_exp_mont(r_mont, a, b, m, ctx, NULL)) 191 || !TEST_true(BN_mod_exp_recp(r_recp, a, b, m, ctx)) 192 || !TEST_true(BN_mod_exp_simple(r_simple, a, b, m, ctx)) 193 || !TEST_true(BN_mod_exp_mont_consttime(r_mont_const, a, b, m, ctx, NULL))) 194 goto err; 195 196 if (!TEST_BN_eq(r_simple, r_mont) 197 || !TEST_BN_eq(r_simple, r_recp) 198 || !TEST_BN_eq(r_simple, r_mont_const)) { 199 if (BN_cmp(r_simple, r_mont) != 0) 200 TEST_info("simple and mont results differ"); 201 if (BN_cmp(r_simple, r_mont_const) != 0) 202 TEST_info("simple and mont const time results differ"); 203 if (BN_cmp(r_simple, r_recp) != 0) 204 TEST_info("simple and recp results differ"); 205 206 BN_print_var(a); 207 BN_print_var(b); 208 BN_print_var(m); 209 BN_print_var(r_simple); 210 BN_print_var(r_recp); 211 BN_print_var(r_mont); 212 BN_print_var(r_mont_const); 213 goto err; 214 } 215 216 ret = 1; 217 err: 218 BN_free(r_mont); 219 BN_free(r_mont_const); 220 BN_free(r_recp); 221 BN_free(r_simple); 222 BN_free(a); 223 BN_free(b); 224 BN_free(m); 225 BN_CTX_free(ctx); 226 227 return ret; 228} 229 230int setup_tests(void) 231{ 232 ADD_TEST(test_mod_exp_zero); 233 ADD_ALL_TESTS(test_mod_exp, 200); 234 return 1; 235} 236