/* * Copyright 2005, Nick Galbreath -- nickg [at] modp [dot] com * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of the modp.com nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * This is the standard "new" BSD license: * http://www.opensource.org/licenses/bsd-license.php */ package gtPlusPlus.api.objects; import java.util.Random; import gtPlusPlus.api.interfaces.IRandomGenerator; import gtPlusPlus.core.util.Utils; import java.security.SecureRandom; import java.math.BigInteger; /** * The Blum-Blum-Shub random number generator. * *

* The Blum-Blum-Shub is a "cryptographically secure" random number * generator. It has been proven that predicting the ouput * is equivalent to factoring n, a large integer generated * from two prime numbers. *

* *

* The Algorithm: *

*
    *
  1. * (setup) generate two secret prime numbers p, q such that * p ≠ q, p ≡ 3 mod 4, q ≡ 3 mod 4. *
    2. *
  2. (setup) compute n = pq. n can be re-used, but * p, and q are secret and should be disposed of.
    3. *
  3. Generate a (secure) random seed s in the range [1, n -1] * such that gcd(s, n) = 1. *
  4. Compute x = s2 mod n
    5. *
  5. Compute a single random bit with: *
      *
    1. x = x2 mod n
      2. *
    2. return Least-Significant-Bit(x) (i.e. x & 1)
      3. *
    * Repeat as necessary. *
    6. *
* *

* The code originally appeared in Cryptography for * Internet and Database Applications , Chapter 4, pages 174-177 *

*

* More details are in the Handbook of Applied Cryptography, * Section 5.5.2 *

* * @author Nick Galbreath -- nickg [at] modp [dot] com * @version 3 -- 06-Jul-2005 * */ public class CSPRNG extends Random implements IRandomGenerator { // pre-compute a few values private static final BigInteger two = BigInteger.valueOf(2L); private static final BigInteger three = BigInteger.valueOf(3L); private static final BigInteger four = BigInteger.valueOf(4L); /** * main parameter */ private BigInteger n; private BigInteger state; /** * Generate appropriate prime number for use in Blum-Blum-Shub. * * This generates the appropriate primes (p = 3 mod 4) needed to compute the * "n-value" for Blum-Blum-Shub. * * @param bits Number of bits in prime * @param rand A source of randomness */ private static BigInteger getPrime(int bits, Random rand) { BigInteger p; while (true) { p = new BigInteger(bits, 100, rand); if (p.mod(four).equals(three)) break; } return p; } /** * This generates the "n value" -- the multiplication of two equally sized * random prime numbers -- for use in the Blum-Blum-Shub algorithm. * * @param bits * The number of bits of security * @param rand * A random instance to aid in generating primes * @return A BigInteger, the n. */ public static BigInteger generateN(int bits, Random rand) { BigInteger p = getPrime(bits/2, rand); BigInteger q = getPrime(bits/2, rand); // make sure p != q (almost always true, but just in case, check) while (p.equals(q)) { q = getPrime(bits, rand); } return p.multiply(q); } /** * Constructor, specifing bits for n * * @param bits number of bits */ public CSPRNG(int bits) { this(bits, new Random()); } /** * Constructor, generates prime and seed * * @param bits * @param rand */ public CSPRNG(int bits, Random rand) { this(generateN(bits, rand)); } /** * A constructor to specify the "n-value" to the Blum-Blum-Shub algorithm. * The inital seed is computed using Java's internal "true" random number * generator. * * @param n * The n-value. */ public CSPRNG(BigInteger n) { this(n, SecureRandom.getSeed(n.bitLength() / 8)); } /** * A constructor to specify both the n-value and the seed to the * Blum-Blum-Shub algorithm. * * @param n * The n-value using a BigInteger * @param seed * The seed value using a byte[] array. */ public CSPRNG(BigInteger n, byte[] seed) { this.n = n; setSeed(seed); } /** * Sets or resets the seed value and internal state * * @param seedBytes * The new seed. */ public void setSeed(byte[] seedBytes) { // ADD: use hardwired default for n BigInteger seed = new BigInteger(1, seedBytes); state = seed.mod(n); } /** * Returns up to numBit random bits * * @return int */ public int next(int numBits) { // TODO: find out how many LSB one can extract per cycle. // it is more than one. int result = 0; for (int i = numBits; i != 0; --i) { state = state.modPow(two, n); result = (result << 1) | (state.testBit(0) == true ? 1 : 0); } return result; } public static CSPRNG generate(){ return generate(512); } /** * @return CSPRNG * @Author Draknyte1/Alkalus */ public static CSPRNG generate(int bitsize){ // First use the internal, stock "true" random number // generator to get a "true random seed" SecureRandom r = Utils.generateSecureRandom(); r.nextInt(); // need to do something for SR to be triggered. // Use this seed to generate a n-value for Blum-Blum-Shub // This value can be re-used if desired. BigInteger nval = CSPRNG.generateN(bitsize, r); // now get a seed byte[] seed = new byte[bitsize/8]; r.nextBytes(seed); // now create an instance of BlumBlumShub CSPRNG bbs = new CSPRNG(nval, seed); return bbs; } /** * @return CSPRNG * @Author Draknyte1/Alkalus */ public static CSPRNG generate(Random aRandom){ return generate(512, aRandom); } /** * @return CSPRNG * @Author Draknyte1/Alkalus */ public static CSPRNG generate(int aBitSize, Random aRandom){ // First use the internal, stock "true" random number // generator to get a "true random seed" SecureRandom r = Utils.generateSecureRandom(); r.nextInt(); // need to do something for SR to be triggered. // Use this seed to generate a n-value for Blum-Blum-Shub // This value can be re-used if desired. int bitsize = aBitSize; // now create an instance of BlumBlumShub // do everything almost automatically CSPRNG bbs = new CSPRNG(bitsize, aRandom); return bbs; } }