使用 window.crypto.getRandomValues 在 JavaScript 中洗牌扑克牌

一副扑克牌有 52 张牌，因此52!或大致2^226可能的排列。

现在我想完美地洗牌这样一副牌，具有真正随机的结果和均匀的分布，这样你就可以达到这些可能的排列中的每一个，并且每个排列出现的可能性相同。

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

对于游戏来说，也许你并不真正需要完美的随机性，除非有钱可赢。除此之外，人类可能甚至不会察觉到随机性的“差异”。

但如果我没记错的话，如果你使用流行编程语言中常见的混洗函数和 RNG 组件，你通常会得到不超过 32 位的熵，并且2^32状态。因此，你将永远无法达到所有52!洗牌时牌组可能的排列，但仅限于......

0.000000000000000000000000000000000000000000000000000000005324900157%

...可能的排列。这意味着很多可能的游戏could理论上的演奏或模拟永远不会在实践中真正看到。

顺便说一句，如果您不在每次洗牌前重置为默认顺序，而是从上次洗牌的顺序开始，或者在玩完游戏后保持“混乱”并从那里开始洗牌，您可以进一步改善结果。

要求：

因此，为了实现上述目的，据我所知，需要以下三个组件：

1. 一种良好的洗牌算法，可确保均匀分布。
2. 具有至少 226 位内部状态的适当 RNG。由于我们使用的是确定性机器，因此我们只能得到 PRNG，也许这应该是 CSPRNG。
3. 至少具有 226 位熵的随机种子。

解决方案：

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

1. 费舍尔-耶茨洗牌 https://bost.ocks.org/mike/shuffle/据我所知，会好的。
2. The 异或移位7 https://github.com/davidbau/xsrand/blob/master/xorshift7.jsRNG 具有超过所需的 226 位内部状态，应该足够了。
3. Using window.crypto.getRandomValues我们可以生成所需的 226 位熵来用作种子。如果这还不够，我们可以添加更多的熵从其他来源 https://github.com/keybase/more-entropy.

问题：

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

我想我必须更换Math.random在调用 xorshift7 的 Fisher-Yates 洗牌示例中。但是 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 作为种子，我不知道如何修改它以接受这一点。

这是我编写的一个函数，它使用基于来自以下位置的随机字节的 Fisher-Yates 改组window.crypto。由于 Fisher-Yates 要求在不同范围内生成随机数，因此它以 6 位掩码开始（mask=0x3f），但随着所需范围变小（即，每当i是 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年调查 https://www.cryptolux.org/images/7/7f/RNG_Survey.pdf:

• Firefox（第 21 节以上）使用NIST SP 800-90 http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90a.pdf带有 440 位种子。注意：该标准于 2015 年更新，删除了（可能有后门）Dual_EC_DRBG椭圆曲线PRNG算法。

• IE浏览器(v. 11+) 使用以下支持的算法之一BCryptGen随机 https://msdn.microsoft.com/en-us/library/windows/desktop/aa375458(v=vs.85).aspx（种子长度=？）

• Safari、Chrome 和 Opera use an ARC4 https://linux.die.net/man/3/arc4random具有 1024 位种子的流密码。

Edit:

一个更干净的解决方案是添加一个通用的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();