bn_rand.c (76866) | bn_rand.c (89837) |
---|---|
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 * --- 41 unchanged lines hidden (view full) --- 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 */ | 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 * --- 41 unchanged lines hidden (view full) --- 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 */ |
|
58 59#include <stdio.h> 60#include <time.h> 61#include "cryptlib.h" 62#include "bn_lcl.h" 63#include <openssl/rand.h> 64 65static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) --- 101 unchanged lines hidden (view full) --- 167#if 1 168int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) 169 { 170 return bnrand(2, rnd, bits, top, bottom); 171 } 172#endif 173 174/* random number r: 0 <= r < range */ | 111 112#include <stdio.h> 113#include <time.h> 114#include "cryptlib.h" 115#include "bn_lcl.h" 116#include <openssl/rand.h> 117 118static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) --- 101 unchanged lines hidden (view full) --- 220#if 1 221int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) 222 { 223 return bnrand(2, rnd, bits, top, bottom); 224 } 225#endif 226 227/* random number r: 0 <= r < range */ |
175int BN_rand_range(BIGNUM *r, BIGNUM *range) | 228static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range) |
176 { | 229 { |
230 int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand; |
|
177 int n; 178 179 if (range->neg || BN_is_zero(range)) 180 { 181 BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE); 182 return 0; 183 } 184 185 n = BN_num_bits(range); /* n > 0 */ 186 | 231 int n; 232 233 if (range->neg || BN_is_zero(range)) 234 { 235 BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE); 236 return 0; 237 } 238 239 n = BN_num_bits(range); /* n > 0 */ 240 |
241 /* BN_is_bit_set(range, n - 1) always holds */ 242 |
|
187 if (n == 1) 188 { 189 if (!BN_zero(r)) return 0; 190 } | 243 if (n == 1) 244 { 245 if (!BN_zero(r)) return 0; 246 } |
191 else if (BN_is_bit_set(range, n - 2)) | 247 else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) |
192 { | 248 { |
193 do 194 { 195 /* range = 11..._2, so each iteration succeeds with probability >= .75 */ 196 if (!BN_rand(r, n, -1, 0)) return 0; 197 } 198 while (BN_cmp(r, range) >= 0); 199 } 200 else 201 { 202 /* range = 10..._2, | 249 /* range = 100..._2, |
203 * so 3*range (= 11..._2) is exactly one bit longer than range */ 204 do 205 { | 250 * so 3*range (= 11..._2) is exactly one bit longer than range */ 251 do 252 { |
206 if (!BN_rand(r, n + 1, -1, 0)) return 0; | 253 if (!bn_rand(r, n + 1, -1, 0)) return 0; |
207 /* If r < 3*range, use r := r MOD range 208 * (which is either r, r - range, or r - 2*range). 209 * Otherwise, iterate once more. 210 * Since 3*range = 11..._2, each iteration succeeds with 211 * probability >= .75. */ 212 if (BN_cmp(r ,range) >= 0) 213 { 214 if (!BN_sub(r, r, range)) return 0; 215 if (BN_cmp(r, range) >= 0) 216 if (!BN_sub(r, r, range)) return 0; 217 } 218 } 219 while (BN_cmp(r, range) >= 0); 220 } | 254 /* If r < 3*range, use r := r MOD range 255 * (which is either r, r - range, or r - 2*range). 256 * Otherwise, iterate once more. 257 * Since 3*range = 11..._2, each iteration succeeds with 258 * probability >= .75. */ 259 if (BN_cmp(r ,range) >= 0) 260 { 261 if (!BN_sub(r, r, range)) return 0; 262 if (BN_cmp(r, range) >= 0) 263 if (!BN_sub(r, r, range)) return 0; 264 } 265 } 266 while (BN_cmp(r, range) >= 0); 267 } |
268 else 269 { 270 do 271 { 272 /* range = 11..._2 or range = 101..._2 */ 273 if (!bn_rand(r, n, -1, 0)) return 0; 274 } 275 while (BN_cmp(r, range) >= 0); 276 } |
|
221 222 return 1; 223 } | 277 278 return 1; 279 } |
280 281 282int BN_rand_range(BIGNUM *r, BIGNUM *range) 283 { 284 return bn_rand_range(0, r, range); 285 } 286 287int BN_pseudo_rand_range(BIGNUM *r, BIGNUM *range) 288 { 289 return bn_rand_range(1, r, range); 290 } |
|