1 /* 2 * Copyright 2003-2004 The Apache Software Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package org.apache.commons.math.random; 18 19 import java.io.Serializable; 20 import java.security.MessageDigest; 21 import java.security.SecureRandom; 22 import java.security.NoSuchAlgorithmException; 23 import java.security.NoSuchProviderException; 24 import java.util.Collection; 25 26 /** 27 * Implements the {@link RandomData} interface using a {@link RandomGenerator} 28 * instance to generate non-secure data and a 29 * {@link java.security.SecureRandom} instance to provide data for the 30 * <code>nextSecureXxx</code> methods. If no <code>RandomGenerator</code> 31 * is provided in the constructor, the default is to use a generator based on 32 * {@link java.util.Random}. To plug in a different implementation, 33 * either implement <code>RandomGenerator</code> directly or extend 34 * {@link AbstractRandomGenerator}. 35 * <p> 36 * Supports reseeding the underlying pseudo-random number generator (PRNG). 37 * The <code>SecurityProvider</code> and <code>Algorithm</code> 38 * used by the <code>SecureRandom</code> instance can also be reset. 39 * <p> 40 * For details on the default PRNGs, see {@link java.util.Random} and 41 * {@link java.security.SecureRandom}. 42 * <p> 43 * <strong>Usage Notes</strong>: <ul> 44 * <li> 45 * Instance variables are used to maintain <code>RandomGenerator</code> and 46 * <code>SecureRandom</code> instances used in data generation. Therefore, 47 * to generate a random sequence of values or strings, you should use just 48 * <strong>one</strong> <code>RandomDataImpl</code> instance repeatedly.</li> 49 * <li> 50 * The "secure" methods are *much* slower. These should be used only when a 51 * cryptographically secure random sequence is required. A secure random 52 * sequence is a sequence of pseudo-random values which, in addition to being 53 * well-dispersed (so no subsequence of values is an any more likely than other 54 * subsequence of the the same length), also has the additional property that 55 * knowledge of values generated up to any point in the sequence does not make 56 * it any easier to predict subsequent values.</li> 57 * <li> 58 * When a new <code>RandomDataImpl</code> is created, the underlying random 59 * number generators are <strong>not</strong> intialized. If you do not 60 * explicitly seed the default non-secure generator, it is seeded with the current time 61 * in milliseconds on first use. The same holds for the secure generator. 62 * If you provide a <code>RandomGenerator</code> to the constructor, however, 63 * this generator is not reseeded by the constructor nor is it reseeded on 64 * first use. </li> 65 * <li> 66 * The <code>reSeed</code> and <code>reSeedSecure</code> methods delegate 67 * to the corresponding methods on the underlying <code>RandomGenerator</code> 68 * and<code>SecureRandom</code> instances. Therefore, 69 * <code>reSeed(long)</code> fully resets the initial state of the non-secure 70 * random number generator (so that reseeding with a specific value always 71 * results in the same subsequent random sequence); whereas reSeedSecure(long) 72 * does <strong>not</strong> reinitialize the secure random number generator 73 * (so secure sequences started with calls to reseedSecure(long) won't be 74 * identical).</li> 75 * <li> 76 * This implementation is not synchronized. 77 * </ul> 78 * 79 * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $ 80 */ 81 public class RandomDataImpl implements RandomData, Serializable { 82 83 /** Serializable version identifier */ 84 private static final long serialVersionUID = -626730818244969716L; 85 86 /** underlying random number generator */ 87 private RandomGenerator rand = null; 88 89 /** underlying secure random number generator */ 90 private SecureRandom secRand = null; 91 92 /** 93 * Construct a RandomDataImpl. 94 */ 95 public RandomDataImpl() { 96 } 97 98 /** 99 * Construct a RandomDataImpl using the supplied {@link RandomGenerator} 100 * as the source of (non-secure) random data. 101 * 102 * @param rand the source of (non-secure) random data 103 * @since 1.1 104 */ 105 public RandomDataImpl(RandomGenerator rand) { 106 super(); 107 this.rand = rand; 108 } 109 110 /** 111 * <strong>Algorithm Description:</strong> hex strings are generated 112 * using a 2-step process. <ol> 113 * <li> 114 * len/2+1 binary bytes are generated using the underlying Random</li> 115 * <li> 116 * Each binary byte is translated into 2 hex digits</li></ol> 117 * @param len the desired string length. 118 * @return the random string. 119 */ 120 public String nextHexString(int len) { 121 if (len <= 0) { 122 throw new IllegalArgumentException("length must be positive"); 123 } 124 125 //Get a random number generator 126 RandomGenerator ran = getRan(); 127 128 //Initialize output buffer 129 StringBuffer outBuffer = new StringBuffer(); 130 131 //Get int(len/2)+1 random bytes 132 byte[] randomBytes = new byte[(len / 2) + 1]; 133 ran.nextBytes(randomBytes); 134 135 //Convert each byte to 2 hex digits 136 for (int i = 0; i < randomBytes.length; i++) { 137 Integer c = new Integer(randomBytes[i]); 138 139 /* Add 128 to byte value to make interval 0-255 before 140 * doing hex conversion. 141 * This guarantees <= 2 hex digits from toHexString() 142 * toHexString would otherwise add 2^32 to negative arguments. 143 */ 144 String hex = Integer.toHexString(c.intValue() + 128); 145 146 // Make sure we add 2 hex digits for each byte 147 if (hex.length() == 1) { 148 hex = "0" + hex; 149 } 150 outBuffer.append(hex); 151 } 152 return outBuffer.toString().substring(0, len); 153 } 154 155 /** 156 * Generate a random int value uniformly distributed between 157 * <code>lower</code> and <code>upper</code>, inclusive. 158 * 159 * @param lower the lower bound. 160 * @param upper the upper bound. 161 * @return the random integer. 162 */ 163 public int nextInt(int lower, int upper) { 164 if (lower >= upper) { 165 throw new IllegalArgumentException 166 ("upper bound must be > lower bound"); 167 } 168 RandomGenerator rand = getRan(); 169 return lower + (int) (rand.nextDouble() * (upper - lower + 1)); 170 } 171 172 /** 173 * Generate a random long value uniformly distributed between 174 * <code>lower</code> and <code>upper</code>, inclusive. 175 * 176 * @param lower the lower bound. 177 * @param upper the upper bound. 178 * @return the random integer. 179 */ 180 public long nextLong(long lower, long upper) { 181 if (lower >= upper) { 182 throw new IllegalArgumentException 183 ("upper bound must be > lower bound"); 184 } 185 RandomGenerator rand = getRan(); 186 return lower + (long) (rand.nextDouble() * (upper - lower + 1)); 187 } 188 189 /** 190 * <strong>Algorithm Description:</strong> hex strings are generated in 191 * 40-byte segments using a 3-step process. <ol> 192 * <li> 193 * 20 random bytes are generated using the underlying 194 * <code>SecureRandom</code>.</li> 195 * <li> 196 * SHA-1 hash is applied to yield a 20-byte binary digest.</li> 197 * <li> 198 * Each byte of the binary digest is converted to 2 hex digits.</li></ol> 199 * 200 * @param len the length of the generated string 201 * @return the random string 202 */ 203 public String nextSecureHexString(int len) { 204 if (len <= 0) { 205 throw new IllegalArgumentException("length must be positive"); 206 } 207 208 // Get SecureRandom and setup Digest provider 209 SecureRandom secRan = getSecRan(); 210 MessageDigest alg = null; 211 try { 212 alg = MessageDigest.getInstance("SHA-1"); 213 } catch (NoSuchAlgorithmException ex) { 214 return null; // gulp FIXME? -- this *should* never fail. 215 } 216 alg.reset(); 217 218 //Compute number of iterations required (40 bytes each) 219 int numIter = (len / 40) + 1; 220 221 StringBuffer outBuffer = new StringBuffer(); 222 for (int iter = 1; iter < numIter + 1; iter++) { 223 byte[] randomBytes = new byte[40]; 224 secRan.nextBytes(randomBytes); 225 alg.update(randomBytes); 226 227 //Compute hash -- will create 20-byte binary hash 228 byte hash[] = alg.digest(); 229 230 //Loop over the hash, converting each byte to 2 hex digits 231 for (int i = 0; i < hash.length; i++) { 232 Integer c = new Integer(hash[i]); 233 234 /* Add 128 to byte value to make interval 0-255 235 * This guarantees <= 2 hex digits from toHexString() 236 * toHexString would otherwise add 2^32 to negative 237 * arguments 238 */ 239 String hex = Integer.toHexString(c.intValue() + 128); 240 241 //Keep strings uniform length -- guarantees 40 bytes 242 if (hex.length() == 1) { 243 hex = "0" + hex; 244 } 245 outBuffer.append(hex); 246 } 247 } 248 return outBuffer.toString().substring(0, len); 249 } 250 251 /** 252 * Generate a random int value uniformly distributed between 253 * <code>lower</code> and <code>upper</code>, inclusive. This algorithm 254 * uses a secure random number generator. 255 * 256 * @param lower the lower bound. 257 * @param upper the upper bound. 258 * @return the random integer. 259 */ 260 public int nextSecureInt(int lower, int upper) { 261 if (lower >= upper) { 262 throw new IllegalArgumentException 263 ("lower bound must be < upper bound"); 264 } 265 SecureRandom sec = getSecRan(); 266 return lower + (int) (sec.nextDouble() * (upper - lower + 1)); 267 } 268 269 /** 270 * Generate a random long value uniformly distributed between 271 * <code>lower</code> and <code>upper</code>, inclusive. This algorithm 272 * uses a secure random number generator. 273 * 274 * @param lower the lower bound. 275 * @param upper the upper bound. 276 * @return the random integer. 277 */ 278 public long nextSecureLong(long lower, long upper) { 279 if (lower >= upper) { 280 throw new IllegalArgumentException 281 ("lower bound must be < upper bound"); 282 } 283 SecureRandom sec = getSecRan(); 284 return lower + (long) (sec.nextDouble() * (upper - lower + 1)); 285 } 286 287 /** 288 * Generates a random long value from the Poisson distribution with the 289 * given mean. 290 * <p> 291 * <strong>Algorithm Description</strong>: 292 * Uses simulation of a Poisson process using Uniform deviates, as 293 * described 294 * <a href="http://irmi.epfl.ch/cmos/Pmmi/interactive/rng7.htm"> 295 * here.</a> 296 * <p> 297 * The Poisson process (and hence value returned) is bounded by 298 * 1000 * mean. 299 * 300 * @param mean mean of the Poisson distribution. 301 * @return the random Poisson value. 302 */ 303 public long nextPoisson(double mean) { 304 if (mean <= 0) { 305 throw new IllegalArgumentException("Poisson mean must be > 0"); 306 } 307 double p = Math.exp(-mean); 308 long n = 0; 309 double r = 1.0d; 310 double rnd = 1.0d; 311 RandomGenerator rand = getRan(); 312 while (n < 1000 * mean) { 313 rnd = rand.nextDouble(); 314 r = r * rnd; 315 if (r >= p) { 316 n++; 317 } else { 318 return n; 319 } 320 } 321 return n; 322 } 323 324 /** 325 * Generate a random value from a Normal (a.k.a. Gaussian) distribution 326 * with the given mean, <code>mu</code> and the given standard deviation, 327 * <code>sigma</code>. 328 * 329 * @param mu the mean of the distribution 330 * @param sigma the standard deviation of the distribution 331 * @return the random Normal value 332 */ 333 public double nextGaussian(double mu, double sigma) { 334 if (sigma <= 0) { 335 throw new IllegalArgumentException("Gaussian std dev must be > 0"); 336 } 337 RandomGenerator rand = getRan(); 338 return sigma * rand.nextGaussian() + mu; 339 } 340 341 /** 342 * Returns a random value from an Exponential distribution with the given 343 * mean. 344 * <p> 345 * <strong>Algorithm Description</strong>: Uses the 346 * <a href="http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node5.html"> 347 * Inversion Method</a> to generate exponentially distributed random values 348 * from uniform deviates. 349 * 350 * @param mean the mean of the distribution 351 * @return the random Exponential value 352 */ 353 public double nextExponential(double mean) { 354 if (mean < 0.0) { 355 throw new IllegalArgumentException 356 ("Exponential mean must be >= 0"); 357 } 358 RandomGenerator rand = getRan(); 359 double unif = rand.nextDouble(); 360 while (unif == 0.0d) { 361 unif = rand.nextDouble(); 362 } 363 return -mean * Math.log(unif); 364 } 365 366 /** 367 * <strong>Algorithm Description</strong>: scales the output of 368 * Random.nextDouble(), but rejects 0 values (i.e., will generate another 369 * random double if Random.nextDouble() returns 0). 370 * This is necessary to provide a symmetric output interval 371 * (both endpoints excluded). 372 * 373 * @param lower the lower bound. 374 * @param upper the upper bound. 375 * @return a uniformly distributed random value from the interval (lower, upper) 376 */ 377 public double nextUniform(double lower, double upper) { 378 if (lower >= upper) { 379 throw new IllegalArgumentException 380 ("lower bound must be <= upper bound"); 381 } 382 RandomGenerator rand = getRan(); 383 384 // ensure nextDouble() isn't 0.0 385 double u = rand.nextDouble(); 386 while(u <= 0.0){ 387 u = rand.nextDouble(); 388 } 389 390 return lower + u * (upper - lower); 391 } 392 393 /** 394 * Returns the RandomGenerator used to generate non-secure 395 * random data. 396 * <p> 397 * Creates and initializes a default generator if null. 398 * 399 * @return the Random used to generate random data 400 * @since 1.1 401 */ 402 private RandomGenerator getRan() { 403 if (rand == null) { 404 rand = new JDKRandomGenerator(); 405 rand.setSeed(System.currentTimeMillis()); 406 } 407 return rand; 408 } 409 410 /** 411 * Returns the SecureRandom used to generate secure random data. 412 * <p> 413 * Creates and initializes if null. 414 * 415 * @return the SecureRandom used to generate secure random data 416 */ 417 private SecureRandom getSecRan() { 418 if (secRand == null) { 419 secRand = new SecureRandom(); 420 secRand.setSeed(System.currentTimeMillis()); 421 } 422 return secRand; 423 } 424 425 /** 426 * Reseeds the random number generator with the supplied seed. 427 * <p> 428 * Will create and initialize if null. 429 * 430 * @param seed the seed value to use 431 */ 432 public void reSeed(long seed) { 433 if (rand == null) { 434 rand = new JDKRandomGenerator(); 435 } 436 rand.setSeed(seed); 437 } 438 439 /** 440 * Reseeds the secure random number generator with the current time 441 * in milliseconds. 442 * <p> 443 * Will create and initialize if null. 444 */ 445 public void reSeedSecure() { 446 if (secRand == null) { 447 secRand = new SecureRandom(); 448 } 449 secRand.setSeed(System.currentTimeMillis()); 450 } 451 452 /** 453 * Reseeds the secure random number generator with the supplied seed. 454 * <p> 455 * Will create and initialize if null. 456 * 457 * @param seed the seed value to use 458 */ 459 public void reSeedSecure(long seed) { 460 if (secRand == null) { 461 secRand = new SecureRandom(); 462 } 463 secRand.setSeed(seed); 464 } 465 466 /** 467 * Reseeds the random number generator with the current time 468 * in milliseconds. 469 */ 470 public void reSeed() { 471 if (rand == null) { 472 rand = new JDKRandomGenerator(); 473 } 474 rand.setSeed(System.currentTimeMillis()); 475 } 476 477 /** 478 * Sets the PRNG algorithm for the underlying SecureRandom instance 479 * using the Security Provider API. The Security Provider API is defined in 480 * <a href="http://java.sun.com/j2se/1.3/docs/guide/security/CryptoSpec.html#AppA"> 481 * Java Cryptography Architecture API Specification & Reference.</a> 482 * <p> 483 * <strong>USAGE NOTE:</strong> This method carries <i>significant</i> 484 * overhead and may take several seconds to execute. 485 * </p> 486 * 487 * @param algorithm the name of the PRNG algorithm 488 * @param provider the name of the provider 489 * @throws NoSuchAlgorithmException if the specified algorithm 490 * is not available 491 * @throws NoSuchProviderException if the specified provider 492 * is not installed 493 */ 494 public void setSecureAlgorithm(String algorithm, String provider) 495 throws NoSuchAlgorithmException, NoSuchProviderException { 496 secRand = SecureRandom.getInstance(algorithm, provider); 497 } 498 499 /** 500 * Uses a 2-cycle permutation shuffle to generate a random permutation. 501 * The shuffling process is described 502 * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html"> 503 * here</a>. 504 * @param n the population size. 505 * @param k the number to choose. 506 * @return the random permutation. 507 */ 508 public int[] nextPermutation(int n, int k) { 509 if (k > n) { 510 throw new IllegalArgumentException 511 ("permutation k exceeds n"); 512 } 513 if (k == 0) { 514 throw new IllegalArgumentException 515 ("permutation k must be > 0"); 516 } 517 518 int[] index = getNatural(n); 519 shuffle(index, n - k); 520 int[] result = new int[k]; 521 for (int i = 0; i < k; i++) { 522 result[i] = index[n - i - 1]; 523 } 524 525 return result; 526 } 527 528 /** 529 * Uses a 2-cycle permutation shuffle to generate a random permutation. 530 * <strong>Algorithm Description</strong>: Uses a 2-cycle permutation 531 * shuffle to generate a random permutation of <code>c.size()</code> and 532 * then returns the elements whose indexes correspond to the elements of 533 * the generated permutation. 534 * This technique is described, and proven to generate random samples, 535 * <a href="http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node83.html"> 536 * here</a> 537 * @param c Collection to sample from. 538 * @param k sample size. 539 * @return the random sample. 540 */ 541 public Object[] nextSample(Collection c, int k) { 542 int len = c.size(); 543 if (k > len) { 544 throw new IllegalArgumentException 545 ("sample size exceeds collection size"); 546 } 547 if (k == 0) { 548 throw new IllegalArgumentException 549 ("sample size must be > 0"); 550 } 551 552 Object[] objects = c.toArray(); 553 int[] index = nextPermutation(len, k); 554 Object[] result = new Object[k]; 555 for (int i = 0; i < k; i++) { 556 result[i] = objects[index[i]]; 557 } 558 return result; 559 } 560 561 //------------------------Private methods---------------------------------- 562 563 /** 564 * Uses a 2-cycle permutation shuffle to randomly re-order the last elements 565 * of list. 566 * 567 * @param list list to be shuffled 568 * @param end element past which shuffling begins 569 */ 570 private void shuffle(int[] list, int end) { 571 int target = 0; 572 for (int i = list.length - 1 ; i >= end; i--) { 573 if (i == 0) { 574 target = 0; 575 } else { 576 target = nextInt(0, i); 577 } 578 int temp = list[target]; 579 list[target] = list[i]; 580 list[i] = temp; 581 } 582 } 583 584 /** 585 * Returns an array representing n. 586 * 587 * @param n the natural number to represent 588 * @return array with entries = elements of n 589 */ 590 private int[] getNatural(int n) { 591 int[] natural = new int[n]; 592 for (int i = 0; i < n; i++) { 593 natural[i] = i; 594 } 595 return natural; 596 } 597 }