Javascript CS-PRNG - 64-bit random

Question

Hi,

I need to generate a cryptographically secure 64-bit unsigned random integer in Javascript. The first problem is that Javascript only allows 64-bit signed integers, so 9223372036854775808 is the biggest supported integer without going into floating point use I think? To fix this I can use a big number library, no problem.

My Method:

var randNum = SHA256( randBigInt(128, 0) ) % 2^64;

Where SHA256() is a secure hash function and randBigInt() is defined below as a non-crypto PRNG, im giving it a 128bit seed so brute force shouldn't be a problem.

randBigInt(n,s) //return an n-bit random BigInt (n>=1).  If s=1, then the most significant of those n bits is set to 1.

Is this a secure method to generate a cryptographically secure 64-bit random int? And importantly does taking the 2^64 mod guarantee 100% I have a 64-bit number?

An abstract example, say this number is prime (it isn't i know), I will use it in the Galois Field [2^p], where p must be 64bits so that every possible 1-63bit number is a field element. In this query, my random int must be larger than any 63-bit number. And Im not sure im correct in taking the 2^64 mod of a 256bit hash output.

Thanks (hope that makes sense)

Answer 1

All JavaScript numbers are actually IEEE 754 doubles, which means you can only exactly represent integers with magnitude <= 2^53. See this answer. So you will need a bignum library.

Taking the mod (%) gives you a number >= 0 and <= 2^64 - 1. 2^64 - 1 is the largest 63-bit number.

Finally, if you feed non-random input into SHA256, you'll get non-random output. In the extreme, if randBigInt always returns 0, than SHA256 will always return the same thing.

Answer 2

You can't turn a non-crypto-secure PRNG into a secure one simply by hashing the output in this way. You've only got as much entropy as you provided as input to seed the PRNG. Sure, the output looks random, but if the attacker knows your scheme (and you ought to assume they do, taking Kerchoffs' principles as axiomatic) then they can guess and/or brute force the inputs.

Also, you seem a little unclear over what you want by a "64-bit number". Do you want 64 bits of random data - in which case the chance of the highest bit being set should be 50% - or do you want some other property like a number between 2^63 and 2^64-1? What are you trying to do, anyway?

The output of a crypto-secure hash function (careful: I'm not sure that SHA256 on its own is ideal as a PRNG) is supposed to pass statistical tests, so you can be pretty sure that the probability of every individual bit being 1 is (very close to) 50%. This is great for generating symmetric keys, but that's not what you're hinting at here? (As you go on to say, if you're talking about GF(2^p) you do indeed need a prime of a given size. If that's what you're doing, there are algorithms which generate probably and provably prime numbers, and you should look into those instead.)

Answer 3

Go to:

http://www.number.com.pt/index.html

And on

PRECISION AND IMPLEMENTATION

Get 1000 decimal pseudorandom numbers and see the code.