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