用window.crypto.getRandomValues在JavaScript中洗牌
一副扑克牌有52张牌，因此52!或大体上是2^226可能的排列。
现在我想完美地洗一副这样的牌，具有真正随机的结果和均匀的分布，这样你就可以达到这些可能的排列中的每一个，并且每个排列都有可能出现。
为什么这实际上是必要的？
也许，对于游戏来说，你并不真的需要完美的随机性，除非有钱可以赢。除此之外，人类可能甚至不会察觉到随机性中的“差异”。
但是如果我没有记错的话，如果您使用混洗函数和通常内置于流行编程语言中的RNG组件，您通常会得到不超过32位的熵和2^32状态。因此，在洗牌时，你永远不能到达所有可能的52!排列，而只能...
0.000000000000000000000000000000000000000000000000000000005324900157 %
..。可能的排列。这意味着在理论上可以玩或模拟的所有可能的游戏实际上永远看不到。
顺便说一句，如果你不是每次在洗牌前都重置为默认顺序，而是从最后一次洗牌的顺序开始，或者在玩完游戏后保持“混乱”，那么你可以进一步改善结果。
要求：
因此，据我所知，为了完成上面描述的工作，需要以下三个组件：
一种良好的混洗算法，可确保至少226位内部状态的统一distribution.
- A正确的
- 。由于我们是在确定性机器上，PRNG将是我们将得到的全部，也许这应该是CSPRNG。
- 至少具有226位熵的随机种子。
解决方案：
现在这是可以实现的吗？我们有什么？
- Fisher-Yates shuffle将会很好，据我所知，
- xorshift7 RNG的内部状态超过了所需的226位，并且如果
- 我们可以生成所需的226位的熵来用作我们的种子。如果这还不够，我们可以添加更多的熵from other sources.
问题：
上面提到的解决方案(以及需求)是否正确？那么，在实践中，如何在JavaScript中使用这些解决方案实现混洗呢？如何将这三个组件组合成一个有效的解决方案？
我想我必须用一个对xorshift7的调用来替换Fisher-Yates shuffle示例中Math.random的用法。但是该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，我也不知道如何修改它来接受这一点。
回答 3
Stack Overflow用户
发布于 2017-11-09 21:58:57
这是我写的一个函数，它使用基于来自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 survey的说法
- Firefox (v. 21+)使用带有440位种子的NIST SP 800-90。注:该标准在2015年更新，删除了(可能是后置的)
Dual_EC_DRBG椭圆曲线PRNG算法。
- Internet资源管理器 (v. 11+)使用BCryptGenRandom (seed length = ?)
支持的算法之一
- Safari，Chrome和Opera使用带有1024位种子的ARC4流密码。
编辑：
一个更简洁的解决方案是在Javascript的数组原型中添加一个通用的shuffle()方法：
// 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();Stack Overflow用户
发布于 2017-11-13 04:38:37
将这里的this answer与another question的this answer结合起来，似乎可以成为一个更通用、更模块化(尽管不太优化)的版本：
// Fisher-Yates
function shuffle(array) {
var i, j;
for (i = array.length - 1; i > 0; i--) {
j = randomInt(0, i + 1);
swap(array, i, j);
}
}
// replacement for:
// Math.floor(Math.random() * (max - min)) + min
function randomInt(min, max) {
var range = max - min;
var bytesNeeded = Math.ceil(Math.log2(range) / 8);
var randomBytes = new Uint8Array(bytesNeeded);
var maximumRange = Math.pow(Math.pow(2, 8), bytesNeeded);
var extendedRange = Math.floor(maximumRange / range) * range;
var i, randomInteger;
while (true) {
window.crypto.getRandomValues(randomBytes);
randomInteger = 0;
for (i = 0; i < bytesNeeded; i++) {
randomInteger <<= 8;
randomInteger += randomBytes[i];
}
if (randomInteger < extendedRange) {
randomInteger %= range;
return min + randomInteger;
}
}
}
function swap(array, first, second) {
var temp;
temp = array[first];
array[first] = array[second];
array[second] = temp;
}Stack Overflow用户
发布于 2017-11-18 23:35:28
我个人认为你可以稍微跳出框框。如果你那么担心随机性，你可以查看来自random.org ( https://api.random.org/json-rpc/1/ )的API key，或者像这样从一个链接中解析出来：https://www.random.org/integer-sets/?sets=1&num=52&min=1&max=52&seqnos=on&commas=on&order=index&format=html&rnd=new。
当然，你的数据集可能会被截获，但如果你得到几十万个数据集，然后对这些数据集进行混洗，那就没问题了。
https://stackoverflow.com/questions/47194034
复制相似问题
腾讯云开发者
