bn_rand.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
  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. {
  123. BN_zero(rnd);
  124. return 1;
  125. }
  126. bytes=(bits+7)/8;
  127. bit=(bits-1)%8;
  128. mask=0xff<<(bit+1);
  129. buf=(unsigned char *)OPENSSL_malloc(bytes);
  130. if (buf == NULL)
  131. {
  132. BNerr(BN_F_BNRAND,ERR_R_MALLOC_FAILURE);
  133. goto err;
  134. }
  135. /* make a random number and set the top and bottom bits */
  136. time(&tim);
  137. RAND_add(&tim,sizeof(tim),0.0);
  138. if (pseudorand)
  139. {
  140. if (RAND_pseudo_bytes(buf, bytes) == -1)
  141. goto err;
  142. }
  143. else
  144. {
  145. if (RAND_bytes(buf, bytes) <= 0)
  146. goto err;
  147. }
  148. #if 1
  149. if (pseudorand == 2)
  150. {
  151. /* generate patterns that are more likely to trigger BN
  152. library bugs */
  153. int i;
  154. unsigned char c;
  155. for (i = 0; i < bytes; i++)
  156. {
  157. RAND_pseudo_bytes(&c, 1);
  158. if (c >= 128 && i > 0)
  159. buf[i] = buf[i-1];
  160. else if (c < 42)
  161. buf[i] = 0;
  162. else if (c < 84)
  163. buf[i] = 255;
  164. }
  165. }
  166. #endif
  167. if (top != -1)
  168. {
  169. if (top)
  170. {
  171. if (bit == 0)
  172. {
  173. buf[0]=1;
  174. buf[1]|=0x80;
  175. }
  176. else
  177. {
  178. buf[0]|=(3<<(bit-1));
  179. }
  180. }
  181. else
  182. {
  183. buf[0]|=(1<<bit);
  184. }
  185. }
  186. buf[0] &= ~mask;
  187. if (bottom) /* set bottom bit if requested */
  188. buf[bytes-1]|=1;
  189. if (!BN_bin2bn(buf,bytes,rnd)) goto err;
  190. ret=1;
  191. err:
  192. if (buf != NULL)
  193. {
  194. OPENSSL_cleanse(buf,bytes);
  195. OPENSSL_free(buf);
  196. }
  197. bn_check_top(rnd);
  198. return(ret);
  199. }
  200. int BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
  201. {
  202. return bnrand(0, rnd, bits, top, bottom);
  203. }
  204. int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
  205. {
  206. return bnrand(1, rnd, bits, top, bottom);
  207. }
  208. #if 1
  209. int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
  210. {
  211. return bnrand(2, rnd, bits, top, bottom);
  212. }
  213. #endif
  214. /* random number r: 0 <= r < range */
  215. static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range)
  216. {
  217. int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;
  218. int n;
  219. int count = 100;
  220. if (range->neg || BN_is_zero(range))
  221. {
  222. BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
  223. return 0;
  224. }
  225. n = BN_num_bits(range); /* n > 0 */
  226. /* BN_is_bit_set(range, n - 1) always holds */
  227. if (n == 1)
  228. BN_zero(r);
  229. else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))
  230. {
  231. /* range = 100..._2,
  232. * so 3*range (= 11..._2) is exactly one bit longer than range */
  233. do
  234. {
  235. if (!bn_rand(r, n + 1, -1, 0)) return 0;
  236. /* If r < 3*range, use r := r MOD range
  237. * (which is either r, r - range, or r - 2*range).
  238. * Otherwise, iterate once more.
  239. * Since 3*range = 11..._2, each iteration succeeds with
  240. * probability >= .75. */
  241. if (BN_cmp(r ,range) >= 0)
  242. {
  243. if (!BN_sub(r, r, range)) return 0;
  244. if (BN_cmp(r, range) >= 0)
  245. if (!BN_sub(r, r, range)) return 0;
  246. }
  247. if (!--count)
  248. {
  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. else
  256. {
  257. do
  258. {
  259. /* range = 11..._2 or range = 101..._2 */
  260. if (!bn_rand(r, n, -1, 0)) return 0;
  261. if (!--count)
  262. {
  263. BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
  264. return 0;
  265. }
  266. }
  267. while (BN_cmp(r, range) >= 0);
  268. }
  269. bn_check_top(r);
  270. return 1;
  271. }
  272. int BN_rand_range(BIGNUM *r, BIGNUM *range)
  273. {
  274. return bn_rand_range(0, r, range);
  275. }
  276. int BN_pseudo_rand_range(BIGNUM *r, BIGNUM *range)
  277. {
  278. return bn_rand_range(1, r, range);
  279. }