exptest.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313
  1. /* crypto/bn/exptest.c */
  2. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  3. * All rights reserved.
  4. *
  5. * This package is an SSL implementation written
  6. * by Eric Young (eay@cryptsoft.com).
  7. * The implementation was written so as to conform with Netscapes SSL.
  8. *
  9. * This library is free for commercial and non-commercial use as long as
  10. * the following conditions are aheared to. The following conditions
  11. * apply to all code found in this distribution, be it the RC4, RSA,
  12. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  13. * included with this distribution is covered by the same copyright terms
  14. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15. *
  16. * Copyright remains Eric Young's, and as such any Copyright notices in
  17. * the code are not to be removed.
  18. * If this package is used in a product, Eric Young should be given attribution
  19. * as the author of the parts of the library used.
  20. * This can be in the form of a textual message at program startup or
  21. * in documentation (online or textual) provided with the package.
  22. *
  23. * Redistribution and use in source and binary forms, with or without
  24. * modification, are permitted provided that the following conditions
  25. * are met:
  26. * 1. Redistributions of source code must retain the copyright
  27. * notice, this list of conditions and the following disclaimer.
  28. * 2. Redistributions in binary form must reproduce the above copyright
  29. * notice, this list of conditions and the following disclaimer in the
  30. * documentation and/or other materials provided with the distribution.
  31. * 3. All advertising materials mentioning features or use of this software
  32. * must display the following acknowledgement:
  33. * "This product includes cryptographic software written by
  34. * Eric Young (eay@cryptsoft.com)"
  35. * The word 'cryptographic' can be left out if the rouines from the library
  36. * being used are not cryptographic related :-).
  37. * 4. If you include any Windows specific code (or a derivative thereof) from
  38. * the apps directory (application code) you must include an acknowledgement:
  39. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40. *
  41. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51. * SUCH DAMAGE.
  52. *
  53. * The licence and distribution terms for any publically available version or
  54. * derivative of this code cannot be changed. i.e. this code cannot simply be
  55. * copied and put under another distribution licence
  56. * [including the GNU Public Licence.]
  57. */
  58. #include <stdio.h>
  59. #include <stdlib.h>
  60. #include <string.h>
  61. #include "../e_os.h"
  62. #include <openssl/bio.h>
  63. #include <openssl/bn.h>
  64. #include <openssl/rand.h>
  65. #include <openssl/err.h>
  66. #define NUM_BITS (BN_BITS*2)
  67. static const char rnd_seed[] =
  68. "string to make the random number generator think it has entropy";
  69. /*
  70. * Test that r == 0 in test_exp_mod_zero(). Returns one on success,
  71. * returns zero and prints debug output otherwise.
  72. */
  73. static int a_is_zero_mod_one(const char *method, const BIGNUM *r,
  74. const BIGNUM *a) {
  75. if (!BN_is_zero(r)) {
  76. fprintf(stderr, "%s failed:\n", method);
  77. fprintf(stderr, "a ** 0 mod 1 = r (should be 0)\n");
  78. fprintf(stderr, "a = ");
  79. BN_print_fp(stderr, a);
  80. fprintf(stderr, "\nr = ");
  81. BN_print_fp(stderr, r);
  82. fprintf(stderr, "\n");
  83. return 0;
  84. }
  85. return 1;
  86. }
  87. /*
  88. * test_exp_mod_zero tests that x**0 mod 1 == 0. It returns zero on success.
  89. */
  90. static int test_exp_mod_zero()
  91. {
  92. BIGNUM a, p, m;
  93. BIGNUM r;
  94. BN_ULONG one_word = 1;
  95. BN_CTX *ctx = BN_CTX_new();
  96. int ret = 1, failed = 0;
  97. BN_init(&m);
  98. BN_one(&m);
  99. BN_init(&a);
  100. BN_one(&a);
  101. BN_init(&p);
  102. BN_zero(&p);
  103. BN_init(&r);
  104. if (!BN_rand(&a, 1024, 0, 0))
  105. goto err;
  106. if (!BN_mod_exp(&r, &a, &p, &m, ctx))
  107. goto err;
  108. if (!a_is_zero_mod_one("BN_mod_exp", &r, &a))
  109. failed = 1;
  110. if (!BN_mod_exp_recp(&r, &a, &p, &m, ctx))
  111. goto err;
  112. if (!a_is_zero_mod_one("BN_mod_exp_recp", &r, &a))
  113. failed = 1;
  114. if (!BN_mod_exp_simple(&r, &a, &p, &m, ctx))
  115. goto err;
  116. if (!a_is_zero_mod_one("BN_mod_exp_simple", &r, &a))
  117. failed = 1;
  118. if (!BN_mod_exp_mont(&r, &a, &p, &m, ctx, NULL))
  119. goto err;
  120. if (!a_is_zero_mod_one("BN_mod_exp_mont", &r, &a))
  121. failed = 1;
  122. if (!BN_mod_exp_mont_consttime(&r, &a, &p, &m, ctx, NULL)) {
  123. goto err;
  124. }
  125. if (!a_is_zero_mod_one("BN_mod_exp_mont_consttime", &r, &a))
  126. failed = 1;
  127. /*
  128. * A different codepath exists for single word multiplication
  129. * in non-constant-time only.
  130. */
  131. if (!BN_mod_exp_mont_word(&r, one_word, &p, &m, ctx, NULL))
  132. goto err;
  133. if (!BN_is_zero(&r)) {
  134. fprintf(stderr, "BN_mod_exp_mont_word failed:\n");
  135. fprintf(stderr, "1 ** 0 mod 1 = r (should be 0)\n");
  136. fprintf(stderr, "r = ");
  137. BN_print_fp(stderr, &r);
  138. fprintf(stderr, "\n");
  139. return 0;
  140. }
  141. ret = failed;
  142. err:
  143. BN_free(&r);
  144. BN_free(&a);
  145. BN_free(&p);
  146. BN_free(&m);
  147. BN_CTX_free(ctx);
  148. return ret;
  149. }
  150. int main(int argc, char *argv[])
  151. {
  152. BN_CTX *ctx;
  153. BIO *out = NULL;
  154. int i, ret;
  155. unsigned char c;
  156. BIGNUM *r_mont, *r_mont_const, *r_recp, *r_simple, *a, *b, *m;
  157. RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we
  158. * don't even check its return
  159. * value (which we should) */
  160. ERR_load_BN_strings();
  161. ctx = BN_CTX_new();
  162. if (ctx == NULL)
  163. EXIT(1);
  164. r_mont = BN_new();
  165. r_mont_const = BN_new();
  166. r_recp = BN_new();
  167. r_simple = BN_new();
  168. a = BN_new();
  169. b = BN_new();
  170. m = BN_new();
  171. if ((r_mont == NULL) || (r_recp == NULL) || (a == NULL) || (b == NULL))
  172. goto err;
  173. out = BIO_new(BIO_s_file());
  174. if (out == NULL)
  175. EXIT(1);
  176. BIO_set_fp(out, stdout, BIO_NOCLOSE);
  177. for (i = 0; i < 200; i++) {
  178. RAND_bytes(&c, 1);
  179. c = (c % BN_BITS) - BN_BITS2;
  180. BN_rand(a, NUM_BITS + c, 0, 0);
  181. RAND_bytes(&c, 1);
  182. c = (c % BN_BITS) - BN_BITS2;
  183. BN_rand(b, NUM_BITS + c, 0, 0);
  184. RAND_bytes(&c, 1);
  185. c = (c % BN_BITS) - BN_BITS2;
  186. BN_rand(m, NUM_BITS + c, 0, 1);
  187. BN_mod(a, a, m, ctx);
  188. BN_mod(b, b, m, ctx);
  189. ret = BN_mod_exp_mont(r_mont, a, b, m, ctx, NULL);
  190. if (ret <= 0) {
  191. printf("BN_mod_exp_mont() problems\n");
  192. ERR_print_errors(out);
  193. EXIT(1);
  194. }
  195. ret = BN_mod_exp_recp(r_recp, a, b, m, ctx);
  196. if (ret <= 0) {
  197. printf("BN_mod_exp_recp() problems\n");
  198. ERR_print_errors(out);
  199. EXIT(1);
  200. }
  201. ret = BN_mod_exp_simple(r_simple, a, b, m, ctx);
  202. if (ret <= 0) {
  203. printf("BN_mod_exp_simple() problems\n");
  204. ERR_print_errors(out);
  205. EXIT(1);
  206. }
  207. ret = BN_mod_exp_mont_consttime(r_mont_const, a, b, m, ctx, NULL);
  208. if (ret <= 0) {
  209. printf("BN_mod_exp_mont_consttime() problems\n");
  210. ERR_print_errors(out);
  211. EXIT(1);
  212. }
  213. if (BN_cmp(r_simple, r_mont) == 0
  214. && BN_cmp(r_simple, r_recp) == 0
  215. && BN_cmp(r_simple, r_mont_const) == 0) {
  216. printf(".");
  217. fflush(stdout);
  218. } else {
  219. if (BN_cmp(r_simple, r_mont) != 0)
  220. printf("\nsimple and mont results differ\n");
  221. if (BN_cmp(r_simple, r_mont_const) != 0)
  222. printf("\nsimple and mont const time results differ\n");
  223. if (BN_cmp(r_simple, r_recp) != 0)
  224. printf("\nsimple and recp results differ\n");
  225. printf("a (%3d) = ", BN_num_bits(a));
  226. BN_print(out, a);
  227. printf("\nb (%3d) = ", BN_num_bits(b));
  228. BN_print(out, b);
  229. printf("\nm (%3d) = ", BN_num_bits(m));
  230. BN_print(out, m);
  231. printf("\nsimple =");
  232. BN_print(out, r_simple);
  233. printf("\nrecp =");
  234. BN_print(out, r_recp);
  235. printf("\nmont =");
  236. BN_print(out, r_mont);
  237. printf("\nmont_ct =");
  238. BN_print(out, r_mont_const);
  239. printf("\n");
  240. EXIT(1);
  241. }
  242. }
  243. BN_free(r_mont);
  244. BN_free(r_mont_const);
  245. BN_free(r_recp);
  246. BN_free(r_simple);
  247. BN_free(a);
  248. BN_free(b);
  249. BN_free(m);
  250. BN_CTX_free(ctx);
  251. ERR_remove_thread_state(NULL);
  252. CRYPTO_mem_leaks(out);
  253. BIO_free(out);
  254. printf("\n");
  255. if (test_exp_mod_zero() != 0)
  256. goto err;
  257. printf("done\n");
  258. EXIT(0);
  259. err:
  260. ERR_load_crypto_strings();
  261. ERR_print_errors(out);
  262. #ifdef OPENSSL_SYS_NETWARE
  263. printf("ERROR\n");
  264. #endif
  265. EXIT(1);
  266. return (1);
  267. }