rng

rng

关注
发信
关注(28)粉丝(399)

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

本文介绍了使用window.crypto.getRandomValues在JavaScript中随机播放扑克牌组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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



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



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



对于游戏，也许，你不需要完美的随机性，除非有钱可以获胜。除此之外，人类可能甚至不会察觉到随机性的差异。



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



0.000000000000000000000000000000000000000000000000000000005324900157％



...可能的排列。这意味着很多可能可能在理论上被播放或模拟的游戏在实践中永远不会被实际看到。



由如果你没有在每次洗牌之前没有重置为默认顺序，而是从最后一次洗牌的顺序开始，或者在游戏播放后保持混乱并从那里随机播放，你可以进一步改善结果。 / p>

要求：



因此，为了做上述事情，需要以下三个组成部分，据我所知：


  1. 一种良好的改组算法，可确保均匀分布。

  2. 具有至少226位内部状态的合适RNG。由于我们处于确定性机器上，PRNG将是我们所能得到的，也许这应该是一个CSPRNG。

  3. 一个至少有226位熵的随机种子。

解决方案：



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


  1. 会很好。

  2. RNG具有超过所需的226位内部状态并且应该足够了。

  3. 使用 window.crypto.getRandomValues 我们可以生成所需的226位熵作为我们的种子。如果仍然不够，我们可以从其他来源添加更多熵。

问题：



是解决方案（还有）上面提到的要求）对吗？那么如何在实践中使用JavaScript中的这些解决方案实现改组呢？如何将这三个组件组合成一个可行的解决方案？



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



为了生成RNG的种子，我想做这样的事情：

  var randomBytes = generateRandomBytes（226）; 
 
函数generateRandomBytes（n）{
 var data = new Uint8Array（
 Math.ceil（n / 8）
）; 
 window.crypto.getRandomValues（data）; 
 
返回数据; 
}

这是正确的吗？我不知道如何以任何方式将 randomBytes 作为种子传递给RNG，我不知道如何修改它以接受它。

解决方案

这是我写的一个函数，它使用基于来自 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随机播放，使用来自window.crypto * / 
的统一随机值（i = 51; i> 0; i--）{
 if（
 if（ （i&（i + 1））== 0）mask>> = 1; 
 do {
 / *获取100字节块中的随机值。 （我们可能只需要执行* / 
 / *一次。）`mask`变量提取所需的位数* / 
 / *，以便有效地丢弃太大的随机数。 * / 
 if（r == 100）{
 window.crypto.getRandomValues（rndbytes）; 
 r = 0; 
} 
 j = rndbytes [r ++]&面具; 
} while（j> i）; 
 
 / *交换卡[i]和卡[j] * / 
 tmp = cards [i]; 
 cards [i] = cards [j]; 
 cards [j] = tmp; 
} 
退卡; 
}





评估 window.crypto 库确实值得拥有自己的问题，但无论如何......



由<$ c $提供的伪随机流c> window.crypto.getRandomValues（）出于任何目的应该足够随机，但是由不同浏览器中的不同机制生成。根据：




  • Firefox （v.21 +）使用，带有440位种子。注意：此标准于2015年更新，以删除（可能是后向的） Dual_EC_DRBG 椭圆曲线PRNG算法。


  • Internet Explorer （v。11+）使用（种子长度=？）


  • Safari， Chrome和Opera 使用带有1024位种子的流密码。






编辑：



一个更干净的解决方案是在Javascript的数组原型中添加一个通用的 shuffle（）方法：

  //使用
 // window.crypto.getRandomValues作为随机源，将Fisher-Yates shuffle方法添加到Javascript的Array类型。 
 
 if（Uint8Array&& window.crypto&& window.crypto.getRandomValues）{
 Array.prototype.shuffle = function（）{
 var n = this.length; 
 
 //如果数组有< 2项，如果（n ; 
 //拒绝数组> = 2 ** 31项
 if（n> 0x7fffffff）抛出ArrayTooLong; 
 
 var i，j，r = n * 2，tmp，mask; 
 //获取（2 *长度）随机值
 var rnd_words = new Uint32Array（r）; 
 //创建一个掩码来过滤这些值
 for（i = n，mask = 0; i; i>> = 1）mask =（mask<< 1）| 1; 
 
 //执行Fisher-Yates shuffle 
 for（i = n-1; i> 0; i--）{
 if（（i&（i + 1） ））== 0）mask>> = 1; 
 do {
 if（r == n * 2）{
 //刷新随机值，如果全部用完了
 window.crypto.getRandomValues（rnd_words）; 
 r = 0; 
} 
 j = rnd_words [r ++]&面具; 
} while（j> i）; 
 tmp = this [i]; 
 this [i] = this [j]; 
这[j] = tmp; 
} 
返回此; 
} 
}否则抛出不支持; 
 
 //示例：
 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（）;


A poker deck has 52 cards and thus 52! or roughly 2^226 possible permutations.

Now I want to shuffle such a deck of cards perfectly, with truly random results and a uniform distribution, so that you can reach every single one of those possible permutations and each is equally likely to appear.

Why is this actually necessary?

For games, perhaps, you don't really need perfect randomness, unless there's money to be won. Apart from that, humans probably won't even perceive the "differences" in randomness.

But if I'm not mistaken, if you use shuffling functions and RNG components commonly built into popular programming languages, you will often get no more than 32 bits of entropy and 2^32 states. Thus, you will never be able to reach all 52! possible permutations of the deck when shuffling, but only about ...

0.000000000000000000000000000000000000000000000000000000005324900157 %

... of the possible permutations. That means a whole lot of all the possible games that could be played or simulated in theory will never actually be seen in practice.

By the way, you can further improve the results if you don't reset to the default order every time before shuffling but instead start with the order from the last shuffle or keep the "mess" after a game has been played and shuffle from there.

Requirements:

So in order to do what is described above, one needs all of the following three components, as far as I have understood:

  1. A good shuffling algorithm that ensures a uniform distribution.
  2. A proper RNG with at least 226 bits of internal state. Since we're on deterministic machines, a PRNG will be all we'll get, and perhaps this should be a CSPRNG.
  3. A random seed with at least 226 bits of entropy.

Solutions:

Now is this achievable? What do we have?

  1. Fisher-Yates shuffle will be fine, as far as I can see.
  2. The xorshift7 RNG has more than the required 226 bits of internal state and should suffice.
  3. Using window.crypto.getRandomValues we can generate the required 226 bits of entropy to be used as our seed. If that still isn't enough, we can add some more entropy from other sources.

Question:

Are the solutions (and also the requirements) mentioned above correct? How can you implement shuffling using these solutions in JavaScript in practice then? How do you combine the three components to a working solution?

I guess I have to replace the usage of Math.random in the example of the Fisher-Yates shuffle with a call to xorshift7. But that RNG outputs a value in the [0, 1) float range and I need the [1, n] integer range instead. When scaling that range, I don't want to lose the uniform distribution. Moreover, I wanted about 226 bits of randomness. If my RNG outputs just a single Number, isn't that randomness effectively reduced to 2^53 (or 2^64) bits because there are no more possibilities for the output?

In order to generate the seed for the RNG, I wanted to do something like this:

var randomBytes = generateRandomBytes(226);

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

    return data;
}

Is this correct? I don't see how I could pass randomBytes to the RNG as a seed in any way, and I don't know how I could modify it to accep this.

解决方案

Here's a function I wrote that uses Fisher-Yates shuffling based on random bytes sourced from window.crypto. Since Fisher-Yates requires that random numbers are generated over varying ranges, it starts out with a 6-bit mask (mask=0x3f), but gradually reduces the number of bits in this mask as the required range gets smaller (i.e., whenever i is a power of 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;
}

An assessment of window.crypto libraries really deserves its own question, but anyway...

The pseudorandom stream provided by window.crypto.getRandomValues() should be sufficiently random for any purpose, but is generated by different mechanisms in different browsers. According to a 2013 survey:

  • Firefox (v. 21+) uses NIST SP 800-90 with a 440-bit seed. Note: This standard was updated in 2015 to remove the (possibly backdoored) Dual_EC_DRBG elliptic curve PRNG algorithm.

  • Internet Explorer (v. 11+) uses one of the algorithms supported by BCryptGenRandom (seed length = ?)

  • Safari, Chrome and Opera use an ARC4 stream cipher with a 1024-bit seed.

Edit:

A cleaner solution would be to add a generic shuffle() method to Javascript's array prototype:

// 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();

这篇关于使用window.crypto.getRandomValues在JavaScript中随机播放扑克牌组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

09-25 17:45
Powered by LMLPHP ©2024 rng 0.005492