exptest.c 9.3 KB

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