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

138

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

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

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

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

Эйси
источник
2
Не используйте sha1. Он больше не считается безопасным (устойчивым к столкновениям). Вот почему ответ Наомика лучше.
Нильс Абильдгаард

Ответы:

62

Посмотрите здесь: Как использовать 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');
Габи Пуркару
источник
45
Для гораздо лучшего подхода см. Ответ @ naomik ниже.
Габи Пуркару
2
Это тоже был отличный ответ, Габи, только чуть быстрее, примерно на 15%. Отличная работа! Мне действительно нравится видеть Date () в соли, это дает разработчику легкую уверенность в том, что это будет уникальное значение во всех ситуациях, кроме самых безумных параллельных вычислений. Я знаю, что его глупый и randomBytes (20) будет уникальным, но это просто уверенность, которую мы можем иметь, потому что мы, возможно, не знакомы с внутренними механизмами случайной генерации другой библиотеки.
Дмитрий R117 05
647

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; см. Примечания ниже) или 100000000000000001 уникальный посетитель.


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

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

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

Получается, что получить a 0не так уж и сложно. После записи 100 значений среднее значение было

1 из 3 164 854 823 случайных чисел - это 0

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

Спасибо
источник
2
Пожалуйста, посмотрите мое обновление; даже миллисекунда - это долгий срок в мире скоростных JavaScript! Если серьезно, то первые 10 цифр номера остаются неизменными каждую секунду; это то, что мешает Dateвыращивать хорошие семена.
Спасибо
1
Верный. Хотя на самом деле я включил только те, которые дали наибольший вклад в другой ответ, чтобы продемонстрировать, что 20 случайных байтов по-прежнему доминируют с точки зрения энтропии. Я не думаю, Math.randomчто когда-нибудь выпустил бы0.
Спасибо
8
В 14 раз больше голосов, чем принятый ответ ... но кто считает? :)
zx81
2
@moka, кости - это форма множественного числа от die . Я использую единственное число.
Спасибо
2
crypto.randomBytesопределенно
Спасибо
28

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

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

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

// 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
Спасибо
источник
3
Number.toString(radix)не всегда гарантирует двузначное значение (например: (5).toString(16)= "5", а не "05"). Это не имеет значения, если только вы не зависите от того, что ваш окончательный результат будет содержать ровно lenсимволы. В этом случае вы можете использовать return ('0'+n.toString(16)).slice(-2);внутри своей карты функцию.
The Brawny Man
1
Отличный код, спасибо. Просто хотел добавить: если вы собираетесь использовать его для значения idатрибута, убедитесь, что идентификатор начинается с буквы: [A-Za-z].
GijsjanB
Отличный ответ (и комментарии) - очень признателен за то, что вы также включили в ответ требования к браузеру!
kevlarr
Требования к браузеру неверны. Array.from () не поддерживается в IE11.
T_Conroy
1
Он был взят из вики во время этого ответа. Вы можете отредактировать этот ответ, если хотите, но кого действительно волнует IE? Если вы пытаетесь его поддержать, вам все равно придется полифилить половину JavaScript ...
Спасибо
0

Использование crypto- хороший подход, потому что это собственный и стабильный модуль, но есть случаи, когда вы можете использовать его, bcryptесли хотите создать действительно надежный и безопасный хеш. Я использую его для паролей, у него много методов хеширования, создания соли и сравнения паролей.

Метод 1 (генерировать соль и хеш для отдельных вызовов функций)

const salt = bcrypt.genSaltSync(saltRounds);
const hash = bcrypt.hashSync(myPlaintextPassword, salt);

Метод 2 (автогенерация соли и хеша):

const hash = bcrypt.hashSync(myPlaintextPassword, saltRounds);

Дополнительные примеры вы можете найти здесь: https://www.npmjs.com/package/bcrypt

Эдуард
источник