使用window.crypto.getRandomValues在JavaScript中随机播放扑克牌组

Question

扑克牌有52张牌,因此52!或大致2^226可能的排列.

现在我想要完美地洗牌这样一副牌,真正随机的结果和均匀的分布,这样你就可以达到每一个可能的排列,每个都可能出现.

为什么这实际上是必要的？

或许,对于游戏来说,你并不需要完美的随机性,除非有钱可以获胜.除此之外,人类可能甚至不会察觉到随机性的"差异".

但是如果我没有弄错的话,如果你使用通常内置于流行编程语言中的混洗函数和RNG组件,你通常会获得不超过32位的熵和2^32状态.因此,52!当你洗牌时,你永远无法达到牌组的所有可能的排列,但只有......

0.000000000000000000000000000000000000000000000000000000005324900157%

...可能的排列.这意味着一大堆的所有可能的游戏可以在理论上可以播放或模拟永远不会真正在实践中可以看出.

顺便说一句,你可以进一步提高的结果,如果你不每次都重新设置为默认顺序洗牌前,而是与订单开始从上一次洗牌或保持"烂摊子"游戏已经被播放后,并从那里洗牌.

要求:

因此,为了完成上述操作,我需要了解以下三个组件:据我所知:

1. 一种良好的混洗算法,可确保均匀分布.
2. 具有至少226位内部状态的适当RNG.由于我们在确定性机器上,PRNG将是我们所能得到的,也许这应该是CSPRNG.
3. 具有至少226位熵的随机种子.

解决方案:

现在这可以实现吗？我们有什么？

1. 就我所见,Fisher-Yates shuffle会很好.
2. 该xorshift7 RNG具有比内部状态的所需要的226位的更多和应该足够了.
3. 使用window.crypto.getRandomValues我们可以生成所需的226位熵作为我们的种子.如果仍然不够,我们可以从其他来源添加更多的熵.

题:

上述解决方案(以及要求)是否正确？那么如何在实践中使用JavaScript中的这些解决方案实现改组呢？如何将这三个组件组合成一个可行的解决方案？

我想我必须Math.random通过调用xorshift7 替换Fisher-Yates shuffle示例中的用法.但是RNG在[0, 1)浮点范围内输出一个值,而我需要[1, n]整数范围.缩放该范围时,我不想失去均匀分布.而且,我想要大约226位的随机性.如果我的RNG仅输出一个Number,那么随机性是否有效地降低到2 ^ 53(或2 ^ 64)位,因为输出没有更多的可能性？

为了生成RNG的种子,我想做这样的事情:

var randomBytes = generateRandomBytes(226);

function generateRandomBytes(n) {
    var data = new Uint8Array(
        Math.ceil(n / 8)
    );
    window.crypto.getRandomValues(data);

    return data;
}

它是否正确？我不知道如何randomBytes以任何方式将RNG作为种子传递给我,我不知道如何修改它以接受它.

Answer 1

这是我写的一个函数,它使用基于随机字节的Fisher-Yates shuffling window.crypto.由于Fisher-Yates要求在不同的范围内生成随机数,因此它以6位掩码(mask=0x3f)开始,但随着所需范围变小(即,无论何时i功率为1 ),都会逐渐减少此掩码中的位数. 2).

function shuffledeck() {
    var cards = Array("A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
                      "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
                      "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
                      "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??");
    var rndbytes = new Uint8Array(100);
    var i, j, r=100, tmp, mask=0x3f;

    /* Fisher-Yates shuffle, using uniform random values from window.crypto */
    for (i=51; i>0; i--) {
        if ((i & (i+1)) == 0) mask >>= 1;
        do {
            /* Fetch random values in 100-byte blocks. (We probably only need to do */
            /* this once.) The `mask` variable extracts the required number of bits */
            /* for efficient discarding of random numbers that are too large. */
            if (r == 100) {
                window.crypto.getRandomValues(rndbytes);
                r = 0;
            }
            j = rndbytes[r++] & mask;
        } while (j > i);

        /* Swap cards[i] and cards[j] */
        tmp = cards[i];
        cards[i] = cards[j];
        cards[j] = tmp;
    }
    return cards;
}

对window.crypto图书馆的评估确实值得拥有自己的问题,但无论如何......

由window.crypto.getRandomValues()任何目的提供的伪随机流应该是足够随机的,但是由不同浏览器中的不同机制生成.根据2013年的一项调查:

• Firefox(v.21 +)使用带有440位种子的NIST SP 800-90.注意:该标准在2015年更新,以删除(可能是后向的)Dual_EC_DRBG椭圆曲线PRNG算法.

• Internet Explorer(v.11 +)使用BCryptGenRandom支持的算法之一(种子长度=？)

• Safari,Chrome和Opera使用带有1024位种子的ARC4流密码.

编辑:

更简洁的解决方案是shuffle()为Javascript的数组原型添加通用方法:

// Add Fisher-Yates shuffle method to Javascript's Array type, using
// window.crypto.getRandomValues as a source of randomness.

if (Uint8Array && window.crypto && window.crypto.getRandomValues) {
    Array.prototype.shuffle = function() {
        var n = this.length;

        // If array has <2 items, there is nothing to do
        if (n < 2) return this;
        // Reject arrays with >= 2**31 items
        if (n > 0x7fffffff) throw "ArrayTooLong";

        var i, j, r=n*2, tmp, mask;
        // Fetch (2*length) random values
        var rnd_words = new Uint32Array(r);
        // Create a mask to filter these values
        for (i=n, mask=0; i; i>>=1) mask = (mask << 1) | 1;

        // Perform Fisher-Yates shuffle
        for (i=n-1; i>0; i--) {
            if ((i & (i+1)) == 0) mask >>= 1;
            do {
                if (r == n*2) {
                    // Refresh random values if all used up
                    window.crypto.getRandomValues(rnd_words);
                    r = 0;
                }
                j = rnd_words[r++] & mask;
            } while (j > i);
            tmp = this[i];
            this[i] = this[j];
            this[j] = tmp;
        }
        return this;
    }
} else throw "Unsupported";

// Example:
deck = [ "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
         "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
         "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??",
         "A??","2??","3??","4??","5??","6??","7??","8??","9??","10??","J??","Q??","K??"];

deck.shuffle();