test/exptest.c

   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     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
 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 }