Как создать случайный SHA1-хеш для использования в качестве идентификатора в node.js? - PullRequest
Новая
       51

Как создать случайный SHA1-хеш для использования в качестве идентификатора в node.js?

119 голосов
/ 23 февраля 2012

Я использую эту строку для генерации идентификатора sha1 для node.js: 

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

Проблема в том, что он каждый раз возвращает один и тот же идентификатор.

Возможно ли, чтобы он генерировал случайный идентификатор каждый раз, чтобы я мог использовать его в качестве идентификатора документа базы данных?

Ответы [ 3 ]

574 голосов
/ 14 февраля 2013

243,583,606,221,817,150,598,111,409x больше энтропии

Я бы рекомендовал использовать crypto.randomBytes . Это не sha1, но для идентификаторов это быстрее и просто как «случайный». 

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 уникальные выходные значения. Это идентично 160-битным (20-байтовым) возможным выходам SHA1.

Зная это, для нас не имеет смысла shasum наши случайные байты. Это как бросить кубик дважды, но только принять второй бросок; несмотря ни на что, у вас есть 6 возможных результатов каждого броска, поэтому первого броска достаточно.

Почему это лучше?

Чтобы понять, почему это лучше, мы сначала должны понять, как работают функции хеширования. Функции хеширования (включая SHA1) всегда будут генерировать один и тот же вывод, если дан один и тот же ввод.

Скажем, мы хотим генерировать идентификаторы, но наш случайный ввод генерируется броском монеты. У нас есть "heads" или "tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

Если "heads" появится снова, выход SHA1 будет таким же , как это было в первый раз 

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Хорошо, значит, бросок монеты не является хорошим генератором случайных идентификаторов, потому что у нас есть только 2 возможных выхода.

Если мы используем стандартный 6-сторонний кристалл, у нас есть 6 возможных входов. Угадайте, сколько возможных выходов SHA1? 6! 

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

Легко обмануть себя, думая только потому, что вывод нашей функции выглядит очень случайным, что является очень случайным.

Мы оба согласны с тем, что бросок монеты или шестигранный кубик могли бы стать плохим генератором случайных идентификаторов, потому что наших возможных результатов SHA1 (значение, которое мы используем для идентификатора) очень мало. Но что, если мы используем что-то, что имеет гораздо больше результатов? Как отметка времени с миллисекундами? Или JavaScript Math.random? Или даже комбинацию из этих двух?!

Давайте посчитаем, сколько уникальных идентификаторов мы получим ...

Уникальность отметки времени с миллисекундами

При использовании (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 символов. Более длинный результат означает больше цифр, что означает больше энтропии. Сначала нам нужно выяснить, какая длина наиболее вероятна.

Сценарий ниже определит, какая длина наиболее вероятна. Мы делаем это, генерируя 1 миллион случайных чисел и увеличивая счетчик на основе .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 });

Путем деления каждого счетчика на 1 миллион, мы получаем вероятность длины числа, возвращаемого из 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 000 000 000 001 уникальных.

Так сколько случайных входов мы можем сгенерировать?

Хорошо, мы рассчитали количество результатов для отметки времени в миллисекундах и 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 использует только 4,11e-27 процентов 160-битного потенциала SHA1! 

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, что означает, что есть еще 1 возможный уникальный результат, который мы должны учитывать.

Основываясь на обсуждении, которое произошло ниже, мне было интересно узнать о частоте 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 значений были записаны, среднее значение было

1 в 3,164,854,823 случайных чисел 0

Круто!Потребовались бы дополнительные исследования, чтобы узнать, соответствует ли это число равномерному распределению реализации Math.random v8

53 голосов
/ 23 февраля 2012

Посмотрите здесь: Как я могу использовать node.js Crypto для создания хэша HMAC-SHA1? Я бы создал хеш текущей временной метки + случайное число, чтобы гарантировать уникальность хеша: 

var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');
25 голосов
/ 16 октября 2014

Сделайте это и в браузере!

РЕДАКТИРОВАТЬ: это действительно не вписывалось в поток моего предыдущего ответа.Я оставляю это здесь в качестве второго ответа для людей, которые могут делать это в браузере.

Вы можете сделать это на стороне клиента в современных браузерах, если хотите 

// str byteToHex(uint8 byte)
//   converts a single byte to a hex string 
function byteToHex(byte) {
  return ('0' + byte.toString(16)).slice(-2);
}

// str generateId(int len);
//   len - must be an even number (default: 40)
function generateId(len = 40) {
  var arr = new Uint8Array(len / 2);
  window.crypto.getRandomValues(arr);
  return Array.from(arr, byteToHex).join("");
}

console.log(generateId())
// "1e6ef8d5c851a3b5c5ad78f96dd086e4a77da800"

console.log(generateId(20))
// "d2180620d8f781178840"

Требования к браузеру 

Browser    Minimum Version
--------------------------
Chrome     11.0
Firefox    21.0
IE         11.0
Opera      15.0
Safari     5.1
...