test/exptest.c

   1 /*
   2  * Copyright 1995-2021 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 = 1, 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, a, p, m, ctx, mont)))
 104         goto err;
 105     ERR_pop_to_mark();
 106
 107     if (!TEST_true(BN_MONT_CTX_set(mont, m, ctx)))
 108         goto err;
 109
 110     if (!TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, ctx, mont)))
 111         goto err;
 112
 113     if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))
 114         failed = 1;
 115
 116     /*
 117      * A different codepath exists for single word multiplication
 118      * in non-constant-time only.
 119      */
 120     if (!TEST_true(BN_mod_exp_mont_word(r, one_word, p, m, ctx, NULL)))
 121         goto err;
 122
 123     if (!TEST_BN_eq_zero(r)) {
 124         TEST_error("BN_mod_exp_mont_word failed: "
 125                    "1 ** 0 mod 1 = r (should be 0)");
 126         BN_print_var(r);
 127         goto err;
 128     }
 129
 130     ret = !failed;
 131  err:
 132     BN_free(r);
 133     BN_free(a);
 134     BN_free(p);
 135     BN_free(m);
 136     BN_MONT_CTX_free(mont);
 137     BN_CTX_free(ctx);
 138
 139     return ret;
 140 }
 141
 142 static int test_mod_exp(int round)
 143 {
 144     BN_CTX *ctx;
 145     unsigned char c;
 146     int ret = 0;
 147     BIGNUM *r_mont = NULL;
 148     BIGNUM *r_mont_const = NULL;
 149     BIGNUM *r_recp = NULL;
 150     BIGNUM *r_simple = NULL;
 151     BIGNUM *a = NULL;
 152     BIGNUM *b = NULL;
 153     BIGNUM *m = NULL;
 154
 155     if (!TEST_ptr(ctx = BN_CTX_new()))
 156         goto err;
 157
 158     if (!TEST_ptr(r_mont = BN_new())
 159         || !TEST_ptr(r_mont_const = BN_new())
 160         || !TEST_ptr(r_recp = BN_new())
 161         || !TEST_ptr(r_simple = BN_new())
 162         || !TEST_ptr(a = BN_new())
 163         || !TEST_ptr(b = BN_new())
 164         || !TEST_ptr(m = BN_new()))
 165         goto err;
 166
 167     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
 168         goto err;
 169     c = (c % BN_BITS) - BN_BITS2;
 170     if (!TEST_true(BN_rand(a, NUM_BITS + c, BN_RAND_TOP_ONE,
 171                            BN_RAND_BOTTOM_ANY)))
 172         goto err;
 173
 174     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
 175         goto err;
 176     c = (c % BN_BITS) - BN_BITS2;
 177     if (!TEST_true(BN_rand(b, NUM_BITS + c, BN_RAND_TOP_ONE,
 178                            BN_RAND_BOTTOM_ANY)))
 179         goto err;
 180
 181     if (!TEST_int_gt(RAND_bytes(&c, 1), 0))
 182         goto err;
 183     c = (c % BN_BITS) - BN_BITS2;
 184     if (!TEST_true(BN_rand(m, NUM_BITS + c, BN_RAND_TOP_ONE,
 185                            BN_RAND_BOTTOM_ODD)))
 186         goto err;
 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
 230 static int test_mod_exp_x2(int idx)
 231 {
 232     BN_CTX *ctx;
 233     int ret = 0;
 234     BIGNUM *r_mont_const_x2_1 = NULL;
 235     BIGNUM *r_mont_const_x2_2 = NULL;
 236     BIGNUM *r_simple1 = NULL;
 237     BIGNUM *r_simple2 = NULL;
 238     BIGNUM *a1 = NULL;
 239     BIGNUM *b1 = NULL;
 240     BIGNUM *m1 = NULL;
 241     BIGNUM *a2 = NULL;
 242     BIGNUM *b2 = NULL;
 243     BIGNUM *m2 = NULL;
 244     int factor_size = 0;
 245
 246     if (idx <= 100)
 247         factor_size = 1024;
 248     else if (idx <= 200)
 249         factor_size = 1536;
 250     else if (idx <= 300)
 251         factor_size = 2048;
 252
 253     if (!TEST_ptr(ctx = BN_CTX_new()))
 254         goto err;
 255
 256     if (!TEST_ptr(r_mont_const_x2_1 = BN_new())
 257         || !TEST_ptr(r_mont_const_x2_2 = BN_new())
 258         || !TEST_ptr(r_simple1 = BN_new())
 259         || !TEST_ptr(r_simple2 = BN_new())
 260         || !TEST_ptr(a1 = BN_new())
 261         || !TEST_ptr(b1 = BN_new())
 262         || !TEST_ptr(m1 = BN_new())
 263         || !TEST_ptr(a2 = BN_new())
 264         || !TEST_ptr(b2 = BN_new())
 265         || !TEST_ptr(m2 = BN_new()))
 266         goto err;
 267
 268     BN_rand(a1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
 269     BN_rand(b1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
 270     BN_rand(m1, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD);
 271     BN_rand(a2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
 272     BN_rand(b2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
 273     BN_rand(m2, factor_size, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD);
 274
 275     if (!TEST_true(BN_mod(a1, a1, m1, ctx))
 276         || !TEST_true(BN_mod(b1, b1, m1, ctx))
 277         || !TEST_true(BN_mod(a2, a2, m2, ctx))
 278         || !TEST_true(BN_mod(b2, b2, m2, ctx))
 279         || !TEST_true(BN_mod_exp_simple(r_simple1, a1, b1, m1, ctx))
 280         || !TEST_true(BN_mod_exp_simple(r_simple2, a2, b2, m2, ctx))
 281         || !TEST_true(BN_mod_exp_mont_consttime_x2(r_mont_const_x2_1, a1, b1, m1, NULL,
 282                                                    r_mont_const_x2_2, a2, b2, m2, NULL,
 283                                                    ctx)))
 284         goto err;
 285
 286     if (!TEST_BN_eq(r_simple1, r_mont_const_x2_1)
 287         || !TEST_BN_eq(r_simple2, r_mont_const_x2_2)) {
 288         if (BN_cmp(r_simple1, r_mont_const_x2_1) != 0)
 289             TEST_info("simple and mont const time x2 (#1) results differ");
 290         if (BN_cmp(r_simple2, r_mont_const_x2_2) != 0)
 291             TEST_info("simple and mont const time x2 (#2) results differ");
 292
 293         BN_print_var(a1);
 294         BN_print_var(b1);
 295         BN_print_var(m1);
 296         BN_print_var(a2);
 297         BN_print_var(b2);
 298         BN_print_var(m2);
 299         BN_print_var(r_simple1);
 300         BN_print_var(r_simple2);
 301         BN_print_var(r_mont_const_x2_1);
 302         BN_print_var(r_mont_const_x2_2);
 303         goto err;
 304     }
 305
 306     ret = 1;
 307  err:
 308     BN_free(r_mont_const_x2_1);
 309     BN_free(r_mont_const_x2_2);
 310     BN_free(r_simple1);
 311     BN_free(r_simple2);
 312     BN_free(a1);
 313     BN_free(b1);
 314     BN_free(m1);
 315     BN_free(a2);
 316     BN_free(b2);
 317     BN_free(m2);
 318     BN_CTX_free(ctx);
 319
 320     return ret;
 321 }
 322
 323 int setup_tests(void)
 324 {
 325     ADD_TEST(test_mod_exp_zero);
 326     ADD_ALL_TESTS(test_mod_exp, 200);
 327     ADD_ALL_TESTS(test_mod_exp_x2, 300);
 328     return 1;
 329 }