密码安全阵列shuffle

Question

我试图使用加密安全的熵源来对阵列进行洗牌.

我发现了一个类似的问题,关于在这里改组数组如何随机化(shuffle)一个JavaScript数组？.然而,几乎所有解决方案都使用Math.random,这是不安全的.不幸的是,我没有在这个问题上发表评论/发帖的声誉.

这是我提出的解决方案,它使用Durstenfeld shuffling与CSPRNG配对,在给定范围内生成随机整数(由random-number-csprng lib提供).

const randomNumber = require("random-number-csprng");

async function secureShuffleArray(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = await randomNumber(0, i);
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

这种实施是否正确且无偏见？

笔记:

• 为了我的目的,该数组最多包含~100个元素
• 运行nodejs v6.10.3 LTS(已编译)

Answer 1

经过广泛审查后，我得出结论，该解决方案是正确的，是 Durstenfeld shuffle 的逐字实现。

然而，Durstenfeld / Fisher-Yates 洗牌的随机性取决于其 RNG 来源。我的解决方案依赖于random-number-csprng CSPRNG 库，该库使用crypto.randomBytesAsync，因此对于大多数用途来说都是加密安全的（请参阅crypto#randomBytes 的随机性如何？）。

更新：我在这里发布了该解决方案的功能等效但更高效的版本crypto-secure-shuffle，也可以作为 npm 包提供。下面是相关的实现：

const secureRandomInRange = require("random-number-csprng");

async function secureShuffle(array) {
    const promises = [];

    // asynchronously generate an array of random numbers using a CSPRNG
    for (let i = array.length - 1; i > 0; i--) {
        promises.push(secureRandomInRange(0, i));
    }

    const randomNumbers = await Promise.all(promises);

    // apply durstenfeld shuffle with previously generated random numbers
    for (let i = array.length - 1; i > 0; i--) {
        const j = randomNumbers[array.length - i - 1];
        const temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return array;
}