bn_rand.c 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289
  1. /* crypto/bn/bn_rand.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. /* ====================================================================
  59. * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
  60. *
  61. * Redistribution and use in source and binary forms, with or without
  62. * modification, are permitted provided that the following conditions
  63. * are met:
  64. *
  65. * 1. Redistributions of source code must retain the above copyright
  66. * notice, this list of conditions and the following disclaimer.
  67. *
  68. * 2. Redistributions in binary form must reproduce the above copyright
  69. * notice, this list of conditions and the following disclaimer in
  70. * the documentation and/or other materials provided with the
  71. * distribution.
  72. *
  73. * 3. All advertising materials mentioning features or use of this
  74. * software must display the following acknowledgment:
  75. * "This product includes software developed by the OpenSSL Project
  76. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  77. *
  78. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  79. * endorse or promote products derived from this software without
  80. * prior written permission. For written permission, please contact
  81. * openssl-core@openssl.org.
  82. *
  83. * 5. Products derived from this software may not be called "OpenSSL"
  84. * nor may "OpenSSL" appear in their names without prior written
  85. * permission of the OpenSSL Project.
  86. *
  87. * 6. Redistributions of any form whatsoever must retain the following
  88. * acknowledgment:
  89. * "This product includes software developed by the OpenSSL Project
  90. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  91. *
  92. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  93. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  94. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  95. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  96. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  97. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  98. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  99. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  100. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  101. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  102. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  103. * OF THE POSSIBILITY OF SUCH DAMAGE.
  104. * ====================================================================
  105. *
  106. * This product includes cryptographic software written by Eric Young
  107. * (eay@cryptsoft.com). This product includes software written by Tim
  108. * Hudson (tjh@cryptsoft.com).
  109. *
  110. */
  111. #include <stdio.h>
  112. #include <time.h>
  113. #include "cryptlib.h"
  114. #include "bn_lcl.h"
  115. #include <openssl/rand.h>
  116. static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
  117. {
  118. unsigned char *buf = NULL;
  119. int ret = 0, bit, bytes, mask;
  120. time_t tim;
  121. if (bits == 0) {
  122. BN_zero(rnd);
  123. return 1;
  124. }
  125. bytes = (bits + 7) / 8;
  126. bit = (bits - 1) % 8;
  127. mask = 0xff << (bit + 1);
  128. buf = (unsigned char *)OPENSSL_malloc(bytes);
  129. if (buf == NULL) {
  130. BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE);
  131. goto err;
  132. }
  133. /* make a random number and set the top and bottom bits */
  134. time(&tim);
  135. RAND_add(&tim, sizeof(tim), 0.0);
  136. if (pseudorand) {
  137. if (RAND_pseudo_bytes(buf, bytes) == -1)
  138. goto err;
  139. } else {
  140. if (RAND_bytes(buf, bytes) <= 0)
  141. goto err;
  142. }
  143. #if 1
  144. if (pseudorand == 2) {
  145. /*
  146. * generate patterns that are more likely to trigger BN library bugs
  147. */
  148. int i;
  149. unsigned char c;
  150. for (i = 0; i < bytes; i++) {
  151. RAND_pseudo_bytes(&c, 1);
  152. if (c >= 128 && i > 0)
  153. buf[i] = buf[i - 1];
  154. else if (c < 42)
  155. buf[i] = 0;
  156. else if (c < 84)
  157. buf[i] = 255;
  158. }
  159. }
  160. #endif
  161. if (top != -1) {
  162. if (top) {
  163. if (bit == 0) {
  164. buf[0] = 1;
  165. buf[1] |= 0x80;
  166. } else {
  167. buf[0] |= (3 << (bit - 1));
  168. }
  169. } else {
  170. buf[0] |= (1 << bit);
  171. }
  172. }
  173. buf[0] &= ~mask;
  174. if (bottom) /* set bottom bit if requested */
  175. buf[bytes - 1] |= 1;
  176. if (!BN_bin2bn(buf, bytes, rnd))
  177. goto err;
  178. ret = 1;
  179. err:
  180. if (buf != NULL) {
  181. OPENSSL_cleanse(buf, bytes);
  182. OPENSSL_free(buf);
  183. }
  184. bn_check_top(rnd);
  185. return (ret);
  186. }
  187. int BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
  188. {
  189. return bnrand(0, rnd, bits, top, bottom);
  190. }
  191. int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
  192. {
  193. return bnrand(1, rnd, bits, top, bottom);
  194. }
  195. #if 1
  196. int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
  197. {
  198. return bnrand(2, rnd, bits, top, bottom);
  199. }
  200. #endif
  201. /* random number r: 0 <= r < range */
  202. static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
  203. {
  204. int (*bn_rand) (BIGNUM *, int, int, int) =
  205. pseudo ? BN_pseudo_rand : BN_rand;
  206. int n;
  207. int count = 100;
  208. if (range->neg || BN_is_zero(range)) {
  209. BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
  210. return 0;
  211. }
  212. n = BN_num_bits(range); /* n > 0 */
  213. /* BN_is_bit_set(range, n - 1) always holds */
  214. if (n == 1)
  215. BN_zero(r);
  216. else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
  217. /*
  218. * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
  219. * than range
  220. */
  221. do {
  222. if (!bn_rand(r, n + 1, -1, 0))
  223. return 0;
  224. /*
  225. * If r < 3*range, use r := r MOD range (which is either r, r -
  226. * range, or r - 2*range). Otherwise, iterate once more. Since
  227. * 3*range = 11..._2, each iteration succeeds with probability >=
  228. * .75.
  229. */
  230. if (BN_cmp(r, range) >= 0) {
  231. if (!BN_sub(r, r, range))
  232. return 0;
  233. if (BN_cmp(r, range) >= 0)
  234. if (!BN_sub(r, r, range))
  235. return 0;
  236. }
  237. if (!--count) {
  238. BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
  239. return 0;
  240. }
  241. }
  242. while (BN_cmp(r, range) >= 0);
  243. } else {
  244. do {
  245. /* range = 11..._2 or range = 101..._2 */
  246. if (!bn_rand(r, n, -1, 0))
  247. return 0;
  248. if (!--count) {
  249. BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
  250. return 0;
  251. }
  252. }
  253. while (BN_cmp(r, range) >= 0);
  254. }
  255. bn_check_top(r);
  256. return 1;
  257. }
  258. int BN_rand_range(BIGNUM *r, const BIGNUM *range)
  259. {
  260. return bn_rand_range(0, r, range);
  261. }
  262. int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
  263. {
  264. return bn_rand_range(1, r, range);
  265. }