6

We had been using Math.random to get random numbers between 4000-64000.:

Math.floor(Math.random() * 60000 + 4000);

We have to now replace this with a more cryptographically secure random number generator. After searching on this issue we have decided to go with window.crypto.getRandomValues. I am not able to figure out how to use this to get a random number between a particular range. Can someone please help out.

Sid
  • 1,224
  • 3
  • 23
  • 48
  • See also http://dimitri.xyz/random-ints-from-random-bits/ and https://crypto.stackexchange.com/questions/8826/map-bytes-to-number and https://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-random-octet-string – caw Nov 10 '17 at 05:12

2 Answers2

11

For a given min and max, the formula u \cdot \left ( 1 - {2^u \boldsymbol{\textup{mod}} (max-min) \over 2^u} \right ) \sum_{i=0}^{\infty} \left( 2^u \boldsymbol{\textup{mod}} (max-min) \over 2^u \right )^i (i + 1) describes how many bits you'll use on average if you request u bits at once and retry if returning the result would introduce bias.

Fortunately, the optimal strategy is simply requesting ceil(log2(max - min + 1)) bits at once. We can only get full bytes with crypto.getRandomValues anyways, so if we have one call of crypto.getRandomValues per function call, the best we can do is:

// Generate a random integer r with equal chance in  min <= r < max.
function randrange(min, max) {
    var range = max - min;
    if (range <= 0) {
        throw new Exception('max must be larger than min');
    }
    var requestBytes = Math.ceil(Math.log2(range) / 8);
    if (!requestBytes) { // No randomness required
        return min;
    }
    var maxNum = Math.pow(256, requestBytes);
    var ar = new Uint8Array(requestBytes);

    while (true) {
        window.crypto.getRandomValues(ar);

        var val = 0;
        for (var i = 0;i < requestBytes;i++) {
            val = (val << 8) + ar[i];
        }

        if (val < maxNum - maxNum % range) {
            return min + (val % range);
        }
    }
}

If you generate many values, you may consider some optimizations, namely requesting more bytes (i.e. a larger array) in advance. If your range becomes smaller (say you want to flip a coin), than it may also be beneficial to work in a bit-based manner, i.e. request many bits upfront and then only use up the random bits you really need.

phihag
  • 278,196
  • 72
  • 453
  • 469
  • This is really cool, but I noticed kind of like infinite loop for `randrange(0, 1)`. Why is that so? – Deele Aug 08 '17 at 13:21
  • @Deele I do apologize, there was a bug if `max - min == 1` - the previous code requested no randomness, and then the next steps don't make any sense. I have added a check that catches this special case. Note that `randrange(0, 1)` always returns 0. – phihag Aug 08 '17 at 14:08
  • And how would you increase array size (for your example) and approximately at what conditions that should be done? – Deele Aug 08 '17 at 14:35
  • 1
    @Deele The code in this answer does scale the array size automatically. Requesting randomness in larger chunks and extracting it more carefully may be useful if you generate a lot of random numbers, and if the range is quite small. It's hard to pin down concrete numbers, but I'd start optimizing at, say, 100 requests per second, or 10/s if you're just flipping coins. – phihag Aug 08 '17 at 15:18
  • This does differ slightly from `Diceware.prototype.random` in https://github.com/EFForg/OpenWireless/blob/master/app/js/diceware.js which uses a similar construction. That other variant uses recursion instead of another loop, which should be equivalent, but doesn't terminate for inputs that this solution here does terminate. Are there any differences that make one solution superior (or the other one wrong)? – caw Nov 09 '17 at 22:56
  • 1
    @caw I think you got most differences. Since JavaScript interpreters don't always implement tail-recursive calls, a recursive solution may come against stack boundaries. Recursion is also oftentimes slower, since without optimization a stack frame is allocated. The diceware.js solution also redoes all the calculations in each recursion step, which is unnecessary. By using the identity `2^8x = 256^x`, my solution saves a variable and a couple of instructions. Their code needs more tries on average: For min=1 max=3 there is a 1/4 chance that they have to retry. My code only retries in 1/256. – phihag Nov 09 '17 at 23:28
  • Sorry to be bothering you (again), but could you (or someone else) perhaps explain the arithmetic operations at the end, please? I see that you join the random bytes to a single number, but how do the final condition `val + range - (val % range) < maxNum` and the result `min + (val % range)` work then, exactly? I thought that modulo and remainder operations would introduce bias. The other implementation just discards all bits that are not needed and then checks if the resulting number is in the range or too large. Thank you! – caw Nov 10 '17 at 02:37
  • 1
    Especially, how is that final condition `val + range - (val % range) < maxNum` equivalent to `val < (Math.floor(maxNum / range) * range)`? I see that it is rejection sampling with an extended range and this must be the condition that we can safely apply modulo without introducing bias. But I don't see how these conditions are equivalent. Sorry, that was the last comment! ;) – caw Nov 10 '17 at 05:11
  • 1
    @caw As far as I understand their [README](https://github.com/EFForg/OpenWireless/blob/master/README.md), the OpenWireless project is dead. Your suggestion (or its simpler equivalent `val < maxNum - maxNum % range`) is correct. My original check does not introduce sampling bias, but discards results that could be taken (for instance `val=255 range=1 maxNum=256`. I have updated the answer. [Here is the test code to verify it is correct](https://gist.github.com/phihag/dc209bf12a5faa0f26be92874d1b5d3f). – phihag Nov 10 '17 at 16:20
  • 3
    The function in this answer excludes `max` from the range, but includes `min`. To fix this, change `var range = max - min;` to `var range = max - min + 1;` – Andrew Ensley Nov 29 '17 at 17:59
  • @AndrewEnsley It says right in the very first line `Generate a random integer r with equal chance in min <= r < max.`, so I don't believe there is anything to fix. This definition simplifies the common case of wanting one array element - you pass in `array.length`. – phihag Nov 29 '17 at 21:29
  • @phihag Fair enough. I just thought it was a caveat worth mentioning. I didn't notice the `<` vs `<=` in that comment before. Your solution does match `Math.random()`'s functionality, so most people are probably expecting that anyway. – Andrew Ensley Nov 30 '17 at 21:51
  • A concrete example of what Andew Ensley pointed out is that randrange(0,1); Always returns zero, instead of both 1 and 0. I understand that phihag intended this to simply working with arrays, but it is indeed "worth mentioning". – Lonnie Best Sep 29 '18 at 02:37
7

A simple replacement for Math.random might look like this:

/**
 * Return values in the range of [0, 1)
 */
const randomFloat = function () {
  const int = window.crypto.getRandomValues(new Uint32Array(1))[0]
  return int / 2**32
}

To extend this to integers:


/**
 * Return integers in the range of [min, max)
 *
 * @todo check that min is <= max.
 */
const randomInt = function (min, max) {
  const range = max - min
  return Math.floor(randomFloat() * range + min)
}

To extend this to arrays of integers:


/**
 * Generate an array of integers in the range of [min, max).
 */
const randomIntArray = function (length, min, max) {
  return new Array(length).fill(0).map(() => randomInt(min, max))
}

Generate an array of ten integers from 0 to 2 inclusive:

randomIntArray(10, 0, 3)

[0, 2, 1, 2, 0, 0, 1, 0, 1, 0]
t.888
  • 3,862
  • 3
  • 25
  • 31