I have an application that needs long random bit sequences.
Because I rely on these sequences being "truly random", I want to use SecureRandom.
Sadly, I need each such sequence twice.
I cannot keep them in the RAM, because they're too long.
I don't want to write them to the Hard Drive, because writing to and reading from the Hard Drive costs time and Hard Drive space and makes the code unnecessarily complex.
However, since the "random" bit sequence generated by some Generator deterministically depends on the state the Generator was in when it was created, one (maybe) may be able to save and recreate the state a newly generated SecureRandom object was in, allowing for recreation of the bit sequence.
The main question is:
(How) Can you save the entire state of a SecureRandom random number generator? Is cloning enough? (there could be some OS states that also play a role, for example, the current time) Are there any other strong RNGs you can clone so that the original and the clone create the same output?
Also, I'm interested in what sorts of patterns the normal Random number generators create, making them insecure, and whether one can save and recover their state as described above.
Edit:
I created a LCG for this purpose.
However, I think it does not work properly.
Does it create a "strong" pseudorandom bit sequence?
It got suspicious when it yielded the same value several times in a row. For example:
false false true true true true false true false false false true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true
public class DeterministicRandom{
private BigInteger state;
private BigInteger a;
private BigInteger c;
private static final int o=32;
private static final BigInteger m=BigInteger.ONE.shiftLeft(o*8);
public DeterministicRandom(){
a=RandomUtils.randomBigInt(o);
c=RandomUtils.randomBigInt(o);
state=RandomUtils.randomBigInt(o);
}
public DeterministicRandom(DeterministicRandom r){
a=r.a;
c=r.c;
state=r.state;
}
public boolean nextBoolean(){
boolean r=state.testBit(o*8-7);
state=state.multiply(a).add(c).mod(m);
return r;
}
}
public class RandomUtils {
private static Random random = new Random();
public static byte[] nextBytes(byte[] d){
random.nextBytes(d);
return d;
}
public boolean randomBit(){
return random.nextBoolean();
}
public static BigInteger randomBigInt(int bytes){
byte[] d=new byte[bytes+1];
random.nextBytes(d);
d[0]=0;
BigInteger x=new BigInteger(d);
return x;
}
}
I don't think you can rely in general on a SecureRandom instance being cloneable, or on the clone providing the same sequence as the original.
The problem is that a typical Java platform provides multiple implementations of secure random, and when you call new SecureRandom() you get the default implementation. This could be a PRNG or it could be a RNG that uses a source of "real" randomness. In the latter case, even if clone() was supported by the class, the clone object wouldn't give the same random sequence as the original.
I can think of couple of solutions (in general).
The first solution is to create your own Random class that wraps a SecureRandom instance. The special sauce is that your wrapper class needs to record the stream of random numbers that it hands out. Then you need a reset() method that causes your PRNG to switch to using the recorded numbers.
The downside is that you need enough memory to hold all of the numbers. (Depending on the representation, that could be a lot of memory. For example if you record N integers in an ArrayList<Integer>, the worst case is N x 24 bytes for the Integer objects and a peak of 3 x N x 8 bytes for the ArrayList. An int[] is much more dense, but more difficult to manage.)
I see that you have said that the sequences will be too long to hold in memory in your use-case. You could consider writing them to a file, but even that doesn't scale indefinitely.
The second solution is to make use of the SecureRandom classes ability to select an algorithm and reseed itself.
SecureRandom seeder = new SecureRandom();
byte[] seed = seeder.generateSeed(NOS_BYTES);
SecureRandom prng = SecureRandom.getInstance("SHA1PRNG");
prng.setSeed(seed);
SecureRandom prng2 = SecureRandom.getInstance("SHA1PRNG");
prng2.setSeed(seed);
// prng1 and prng2 created as above should generate the same sequences
Set NOS_BYTES to the number of bytes of seed that you want to use. Or you could generate a seed "by hand", or read it from a file.
Note that you cannot reliably set the seed like that on an instance you obtain using new SecureRandom(), and you cannot reliably re-seed an existing instance1.
There may be other PRNG algorithms that you could use, depending on your Java platforms configured Security Providers.
Please refer to the SecureRandom javadoc for more information.
I tested the above approach and on my machine with Java 11, the prng and prng2 objects generated the same sequence of int values ... until I hit ^C.
1 - The crux of the problem is that the javadoc for setSeed says this: "The given seed supplements, rather than replaces, the existing seed.". Elsewhere, it says that the constructors return an object that has been seeded. Fortunately, it also says that the getInstance methods return objects that have not been seeded.
Finally, I see from your updated question that you are considering using a "roll-your-own" PRNG implemented using BigInteger.
Beware!
It is very easy to implement a PRNG that is not as good as you think. I wouldn't do that. But if you decide to go down that route, you should read up on the theory of PRNGs and their properties and run a batch of (relevant) statistical tests on your implementation.
(And if you intend to publish your results, your paper should mention that you implemented your own PRNG, and you should make the PRNG source code and the statistical test results available for readers to check. For the sake of openness and scientific reproducibility. In my opinion.)