At 2/18/13 01:19 AM, Luis wrote:
hat reminds me though... maybe im too artsy to put my head around it but is it really impossible to make things truly 'random' in the programming world... i mean is there such a thing as random to begin with? like when ive told programmers to 'make it random'.... do you like instantly dismiss the idea of 'random' and come up with something that has enough breathing room to feel 'random' or is there a such thing as random... also i might have had some drinks today. but regardless, that has been on my mind. i think about stuff while i goto and come back from work and sit on the train for an hour.
MSG's got most of it down, but i'd like to add some technical mumbo jumbo I learned along my security travels.
so, Here's the thing about computers: They don't do random. You can tell a person to pick a number from 1 to 10, and they'll pick something that we would consider "random" - you tell a computer to spit out a number 100 times, and it'll be the same number over and over again. The essence of "random" is "unpredictable" - and computers are very, very bad at being unpredictable. They live in a world of math and logic. Unpredictability is quite literally impossible in that world.
Now, that isn't to say that you can't have seemingly-random numbers. This is called a pseudo-random number, and the generators that make them are pseudo-random number generator or PRNG. These generally deal in a number as a seed value, and use bitwise operations to create a new value from the seed. This is a very fast operation, but the same seed value will always result in the same output number (as is the case with all PRNGs, secure or not - the same input results in the same output - always)
an example of a PRNG is AS3:
private static var _fastSeed:uint = 1;
public static function fast(seed:uint = 0):Number {
return Math.abs(((seed) ? seed = (seed * 16807) % 2147483647 : _fastSeed = (_fastSeed * 16807) % 2147483647) / 2147483647);
}
this returns a number between 0 and 1. The big issue is that it doesn't do any checks whatsoever, so the number could be (and has a high chance of being) something like 0.0000000000000000000000000000000000000000000000000000000000 000000000000000000000000000001348543564356432657865928374659 4386584365784365464326
which is pretty useless.
so, the big question is: How can you have a PRNG that is hard to guess? This is where a cryptographically secure random-number generator or CSPRNG comes in. An example is the Blum Blum Shub algorithm, which takes two prime numbers and a seed into account. As long as the seed is not known (this generally stems from a timestamp) it is almost impossible to predict. It has the unfortunate drawback of also being very slow, however, as re-calculations must be done every time a limit is reached (even then, there's quite a few steps to it)
Blum Blum Shub in AS3:
private static var _prime1:uint = 0;
private static var _prime2:uint = 0;
private static var _oldSecureSeed:uint = 2;
private static var _sequence:Vector.<Number> = new Vector.<Number>;
public static function secure(seed:uint = 0):Number {
var M:Number;
var xi:int = (seed > 1) ? seed : _secureSeed;
var returnNum:Number;
if (!_prime1 || !_prime2) {
do {
_prime1 = Math.random() * uint.MAX_VALUE;
}while ((_prime1 - 3) % 4 != 0 || !isPrime(_prime1));
do {
_prime2 = Math.random() * uint.MAX_VALUE;
}while ((_prime2 - 3) % 4 != 0 || !isPrime(_prime2));
}
M = _prime1 * _prime2;
xi = (xi * xi) % M;
if (_sequence.indexOf((xi * xi) % M) == -1) {
_sequence.push(xi);
}else {
if (seed <= 1) {
if (_oldSecureSeed == uint.MAX_VALUE) {
_oldSecureSeed = 2;
_prime1 = 0;
_prime2 = 0;
}else {
_oldSecureSeed++;
}
_secureSeed = _oldSecureSeed;
xi = _secureSeed;
returnNum = secure();
if (returnNum) {
return returnNum;
}
return 0;
}else {
seed = (seed == uint.MAX_VALUE) ? 2 : seed + 1;
returnNum = secure(seed);
if (returnNum) {
return returnNum;
}
return 0;
}
}
if (seed <= 1) {
_secureSeed = xi;
}
if (_sequence[_sequence.length - 1] / uint.MAX_VALUE) {
returnNum = Math.abs(_sequence[_sequence.length - 1] / uint.MAX_VALUE);
return returnNum;
}
return 0;
}
private static function isPrime(val:uint):Boolean {
if (val < 2) {
return false;
}
if (!(val % 2) && val != 2) {
return false;
}
for (var i:int = 3; i <= val / i; i += 2) {
if (!(val % i)) {
return false;
}
}
return true;
}
once again, however, this has a small chance of coming up with some ridiculously small number. I fixed all of this by adding a "normalize" function, which slows things down a bit, but will also return better-looking numbers.
here is the full class, if anyone wants it. It took me a few hours and quite a lot of google-fu to get everything working. (I suck at math)
The main reason I created the class is because I wanted random numbers that came out the same every time. It's nice for testing - means you can rule out the possibility of randomness when things go wrong.
