如何生成随机 SHA1 哈希以用作 node.js 中的 ID？

Question

我正在使用这一行为 node.js 生成一个 sha1 id：

 crypto.createHash('sha1').digest('hex');

问题是它每次都返回相同的 id。

是否可以让它每次生成一个随机 ID，以便我可以将其用作数据库文档 ID？

原文由 ajsie 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

看看这里： How do I use node.js Crypto to create a HMAC-SHA1 hash? 我将创建一个当前时间戳的哈希值 + 一个随机数以确保哈希值的唯一性：

 var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');

原文由 Gabi Purcaru 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

243,583,606,221,817,150,598,111,409 倍的熵

我建议使用 crypto.randomBytes 。它不是 sha1 ，但出于 id 目的，它更快，就像“随机”一样。

 var id = crypto.randomBytes(20).toString('hex');
//=> f26d60305dae929ef8640a75e70dd78ab809cfe9

生成的字符串将是您生成的随机字节的两倍长；编码为十六进制的每个字节是 2 个字符。 20 个字节将是 40 个十六进制字符。

使用 20 个字节，我们有 256^20 或 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 个 唯一输出值。这 与 SHA1 的 160 位（20 字节）可能输出相同。

知道了这一点，我们的随机字节 shasum 就没有真正的意义了。这就像掷骰子两次，但只接受第二次掷骰；无论如何，每次掷骰都有 6 种可能的结果，所以第一次掷骰就足够了。

---

为什么这样更好？

要理解为什么这样更好，我们首先必须了解哈希函数的工作原理。如果给定相同的输入，哈希函数（包括 SHA1）将始终生成相同的输出。

假设我们想要生成 ID，但我们的随机输入是通过掷硬币生成的。我们有 "heads" 或 "tails"

 % echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

% echo -n "tails" | shasum
71ac9eed6a76a285ae035fe84a251d56ae9485a4  -

如果 "heads" 再次出现，SHA1 输出将与第一次 相同

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

好吧，所以抛硬币并不是一个很好的随机 ID 生成器，因为我们只有 2 个可能的输出。

如果我们使用标准的 6 面骰子，我们有 6 个可能的输入。猜猜有多少种可能的 SHA1 输出？ 6！

 input => (sha1) => output
1 => 356a192b7913b04c54574d18c28d46e6395428ab
2 => da4b9237bacccdf19c0760cab7aec4a8359010b0
3 => 77de68daecd823babbb58edb1c8e14d7106e83bb
4 => 1b6453892473a467d07372d45eb05abc2031647a
5 => ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4
6 => c1dfd96eea8cc2b62785275bca38ac261256e278

很容易自欺欺人地认为我们函数的输出 看起来 非常随机，它 是 非常随机的。

我们都同意抛硬币或 6 面骰子会产生一个糟糕的随机 ID 生成器，因为我们可能的 SHA1 结果（我们用于 ID 的值）很少。但是如果我们使用输出更多的东西呢？像带有毫秒的时间戳？或者 JavaScript 的 Math.random ？甚至是这两者的 _结合_？！

让我们计算一下我们将获得多少个唯一 ID …

---

毫秒时间戳的唯一性

使用 (new Date()).valueOf().toString() 时，您会得到一个 13 个字符的数字（例如 1375369309741 ）。然而，由于这是一个顺序更新的数字（每毫秒一次），输出几乎总是相同的。让我们来看看

for (var i=0; i<10; i++) {
  console.log((new Date()).valueOf().toString());
}
console.log("OMG so not random");

// 1375369431838
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431840
// 1375369431840
// OMG so not random

公平地说，出于比较目的， 在给定的一分钟内（一个慷慨的操作执行时间），您将拥有 60*1000 或 60000 。

---

Math.random 的唯一性

现在，当使用 Math.random 时，由于 JavaScript 表示 64 位浮点数的方式，您将得到一个长度介于 13 到 24 个字符之间的数字。更长的结果意味着更多的数字，这意味着更多的熵。首先，我们需要找出最可能的长度。

下面的脚本将确定最有可能的长度。我们通过生成 100 万个随机数并根据每个数字的 .length 递增计数器来实现这一点。

 // get distribution
var counts = [], rand, len;
for (var i=0; i<1000000; i++) {
  rand = Math.random();
  len  = String(rand).length;
  if (counts[len] === undefined) counts[len] = 0;
  counts[len] += 1;
}

// calculate % frequency
var freq = counts.map(function(n) { return n/1000000 *100 });

通过将每个计数器除以 100 万，我们得到从 Math.random 返回的数字长度的概率。

 len   frequency(%)
------------------
13    0.0004
14    0.0066
15    0.0654
16    0.6768
17    6.6703
18    61.133  <- highest probability
19    28.089  <- second highest probability
20    3.0287
21    0.2989
22    0.0262
23    0.0040
24    0.0004

所以，尽管这不完全正确，但让我们大方一点，假设您得到一个 19 个字符长的随机输出； 0.1234567890123456789 。第一个字符总是 0 和 . ，所以实际上我们只得到 17 个随机字符。这给我们留下了 10^17 +1 （对于可能的 0 ；见下面的注释）或 100,000,00,010s unique

---

那么我们可以生成多少个随机输入呢？

好的，我们计算了毫秒时间戳的结果数和 Math.random

       100,000,000,000,000,001 (Math.random)
*                      60,000 (timestamp)
-----------------------------
6,000,000,000,000,000,060,000

那是一个 6,000,000,000,000,000,060,000 面的骰子。或者，为了让这个数字更容易被人类 消化，这个数字与

input                                            outputs
------------------------------------------------------------------------------
( 1×) 6,000,000,000,000,000,060,000-sided die    6,000,000,000,000,000,060,000
(28×) 6-sided die                                6,140,942,214,464,815,497,21
(72×) 2-sided coins                              4,722,366,482,869,645,213,696

听起来不错，对吧？好吧，让我们找出…

SHA1 产生一个 20 字节的值，可能有 256^20 个结果。所以我们真的没有充分发挥 SHA1 的潜力。那么我们用了多少？

 node> 6000000000000000060000 / Math.pow(256,20) * 100

毫秒时间戳和 Math.random 仅使用 SHA1 160 位潜力的 4.11e-27%！

 generator               sha1 potential used
-----------------------------------------------------------------------------
crypto.randomBytes(20)  100%
Date() + Math.random()    0.00000000000000000000000000411%
6-sided die               0.000000000000000000000000000000000000000000000411%
A coin                    0.000000000000000000000000000000000000000000000137%

圣猫，伙计！看看所有那些零。那么 crypto.randomBytes(20) 有多好？ 243,583,606,221,817,150,598,111,409 倍更好。

---

关于 +1 和零频率的注释

如果您想知道 +1 ， Math.random 可能会返回 0 ，这意味着我们必须考虑更多可能的独特结果。

根据下面发生的讨论，我很好奇 a 0 出现的频率。这是一个小脚本， random_zero.js ，我做了一些数据

#!/usr/bin/env node
var count = 0;
while (Math.random() !== 0) count++;
console.log(count);

然后，我在 4 个线程中运行它（我有一个 4 核处理器），将输出附加到一个文件

$ yes | xargs -n 1 -P 4 node random_zero.js >> zeroes.txt

所以事实证明 0 并不难获得。记录 100 个值 后，取平均值

3,164,854,823 个随机数中有 1 个是 0

凉爽的！需要更多的研究才能知道这个数字是否与 v8 的均匀分布 Math.random 实现相当

原文由 Mulan 发布，翻译遵循 CC BY-SA 3.0 许可协议