Como gerar o hash SHA1 aleatório para usar como ID no node.js?

137

Estou usando esta linha para gerar um ID sha1 para node.js:

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

O problema é que ele está retornando o mesmo ID todas as vezes.

É possível gerar uma identificação aleatória a cada vez para que eu possa usá-la como identificação de documento de banco de dados?

ajsie
fonte
2
Não use sha1. Não é mais considerado seguro (resistente a colisões). É por isso que a resposta da naomik é melhor.
Niels Abildgaard

Respostas:

60

Dê uma olhada aqui: Como uso o node.js Crypto para criar um hash HMAC-SHA1? Eu criaria um hash do timestamp atual + um número aleatório para garantir a exclusividade do hash:

var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');
Gabi Purcaru
fonte
44
Para uma abordagem muito melhor, consulte a resposta da @ naomik abaixo.
Gabi Purcaru
2
Essa também foi uma ótima resposta para Gabi, e um pouco mais rápida, cerca de 15%. Ótimo trabalho para ambos! Na verdade, eu gosto de ver um Date () no sal, isso dá ao desenvolvedor uma confiança fácil de que esse valor será único em todas as situações de computação paralela, exceto as mais insanas. Eu sei que seu bobo e randomBytes (20) serão únicos, mas é apenas uma confiança que podemos ter, pois podemos não estar familiarizados com os elementos internos da geração aleatória de outra biblioteca.
precisa saber é o seguinte
635

243.583.606.221.817.150.598.111.409x mais entropia

Eu recomendo usar crypto.randomBytes . Não é sha1, mas para fins de identificação, é mais rápido e tão "aleatório".

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

A sequência resultante será duas vezes maior que os bytes aleatórios que você gerar; cada byte codificado em hexadecimal tem 2 caracteres. 20 bytes terão 40 caracteres hexadecimais.

Usando 20 bytes, temos 256^20ou 1.461.501.637.330.902.918.203.684.832.716.283.019.655.932.542.976 valores de saída exclusivos. Isso é idêntico às saídas possíveis de 160 bits (20 bytes) do SHA1.

Sabendo disso, não é realmente significativo para nós shasumnossos bytes aleatórios. É como jogar um dado duas vezes, mas apenas aceitar o segundo lançamento; não importa o que aconteça, você tem 6 resultados possíveis a cada lançamento; portanto, o primeiro lançamento é suficiente.


Por que isso é melhor?

Para entender por que isso é melhor, primeiro precisamos entender como as funções de hash funcionam. As funções de hash (incluindo SHA1) sempre geram a mesma saída se a mesma entrada for fornecida.

Digamos que queremos gerar IDs, mas nossa entrada aleatória é gerada por um sorteio. Nós temos "heads"ou"tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

Se "heads"surgir novamente, a saída SHA1 será a mesma da primeira vez

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, então um sorteio não é um ótimo gerador de ID aleatório, porque só temos 2 saídas possíveis.

Se usarmos um dado de 6 lados padrão, teremos 6 entradas possíveis. Adivinha quantas saídas SHA1 possíveis? 6!

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

É fácil nos iludir pensando apenas porque o resultado de nossa função parece muito aleatório, que é muito aleatória.

Nós dois concordamos que um sorteio ou um dado de 6 lados seria um gerador de identificação aleatória ruim, porque nossos possíveis resultados SHA1 (o valor que usamos para o ID) são muito poucos. Mas e se usarmos algo que tem muito mais resultados? Como um carimbo de data / hora com milissegundos? Ou JavaScript Math.random? Ou mesmo uma combinação desses dois ?!

Vamos calcular quantos IDs únicos obteríamos ...


A exclusividade de um carimbo de data / hora com milissegundos

Ao usar (new Date()).valueOf().toString(), você recebe um número de 13 caracteres (por exemplo, 1375369309741). No entanto, como esse é um número atualizado seqüencialmente (uma vez por milissegundo), as saídas são quase sempre as mesmas. Vamos dar uma olhada

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

Para ser justo, para fins de comparação, em um determinado minuto (um tempo de execução da operação generoso), você terá 60*1000ou será 60000único.


A singularidade de Math.random

Agora, ao usar Math.random, devido à maneira como o JavaScript representa números de ponto flutuante de 64 bits, você obterá um número com comprimento entre 13 e 24 caracteres. Um resultado mais longo significa mais dígitos, o que significa mais entropia. Primeiro, precisamos descobrir qual é o comprimento mais provável.

O script abaixo determinará qual comprimento é mais provável. Fazemos isso gerando 1 milhão de números aleatórios e incrementando um contador com base no .lengthnúmero de cada número.

// 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 });

Ao dividir cada contador por 1 milhão, obtemos a probabilidade do tamanho do número retornado 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

Portanto, mesmo que não seja totalmente verdade, sejamos generosos e digamos que você obtém uma saída aleatória de 19 caracteres; 0.1234567890123456789. Os primeiros caracteres sempre serão 0e ., na verdade, estamos recebendo apenas 17 caracteres aleatórios. Isso nos deixa com 10^17 +1(para possível 0; veja as notas abaixo) ou 100.000.000.000.000.001 únicos.


Então, quantas entradas aleatórias podemos gerar?

Ok, calculamos o número de resultados para um carimbo de data / hora de milissegundo e Math.random

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

Esse é um dado de 6.000.000.000.000.000.060.000 lados. Ou, para tornar este número mais humanamente digerível, esse é aproximadamente o mesmo número que

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

Parece muito bom, certo? Bem, vamos descobrir ...

SHA1 produz um valor de 20 bytes, com possíveis 256 ^ 20 resultados. Portanto, não estamos realmente usando o SHA1 em todo o seu potencial. Bem, quanto estamos usando?

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

Um registro de data e hora em milissegundos e Math.random usam apenas 4,11 e 27 por cento do potencial de 160 bits do SHA1!

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

Gatos sagrados, cara! Veja todos esses zeros. Então, quanto melhor é crypto.randomBytes(20)? 243.583.606.221.817.150.598.111.409 vezes melhor.


Notas sobre +1e frequência de zeros

Se você está se perguntando sobre o +1possível, é possível Math.randomretornar um, o 0que significa que há mais um resultado único possível que devemos considerar.

Com base na discussão que aconteceu a seguir, eu estava curioso sobre a frequência de um 0viria para cima. Aqui está um pequeno script random_zero.js, eu fiz para obter alguns dados

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

Em seguida, executei-o em 4 threads (eu tenho um processador de 4 núcleos), anexando a saída a um arquivo

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

Acontece que 0não é tão difícil de obter. Após 100 valores registrados, a média foi

1 em 3.164.854.823 randoms é 0

Legal! Mais pesquisas seriam necessárias para saber se esse número está a par com uma distribuição uniforme da Math.randomimplementação da v8

Obrigado
fonte
2
Por favor, veja minha atualização; mesmo um milissegundo é muito tempo em terras javascript de velocidade da luz! Em uma nota mais séria, os 10 primeiros dígitos do número permanecem os mesmos a cada segundo; é isso que torna Dateterrível a produção de boas sementes.
Obrigado
1
Corrigir. Embora eu realmente tenha incluído apenas aqueles que dão a maior contribuição à outra resposta para demonstrar que 20 bytes aleatórios ainda dominam em termos de entropia. Eu acho Math.randomque nunca iria produzir um0.
Obrigado
8
Votos 14x mais positivos do que a resposta aceita ... mas quem está contando? :)
ZX81
2
@moka, dado é a forma plural de dado . Eu estou usando a forma singular.
Obrigado
2
crypto.randomBytesé definitivamente o caminho a seguir ^^
Obrigado
28

Faça isso também no navegador!

EDIT: isso realmente não se encaixava no fluxo da minha resposta anterior. Estou deixando aqui como uma segunda resposta para pessoas que desejam fazer isso no navegador.

Você pode fazer isso do lado do cliente em navegadores modernos, se desejar

// 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"

Requisitos do navegador

Browser    Minimum Version
--------------------------
Chrome     11.0
Firefox    21.0
IE         11.0
Opera      15.0
Safari     5.1
Obrigado
fonte
3
Number.toString(radix)nem sempre garante um valor de 2 dígitos (ex: (5).toString(16)= "5", não "05"). Isso não importa, a menos que você esteja dependendo de sua saída final com exatamente lencaracteres. Nesse caso, você pode usar return ('0'+n.toString(16)).slice(-2);dentro da sua função de mapa.
O Brawny Man
1
Ótimo código, obrigado. Só queria adicionar: se você for usá-lo para o valor de um idatributo, verifique se o ID começa com uma letra: [A-Za-z].
GijsjanB 10/01/19
Ótima resposta (e comentários) - apreciei muito que você também incluísse os requisitos do navegador na resposta!
kevlarr 15/03
Os requisitos do navegador estão incorretos. Array.from () não é suportado no IE11.
Prefixo
1
Foi retirado de um wiki no momento desta resposta. Você pode editar esta resposta, se quiser, mas quem realmente se importa com o IE? Se você está tentando apoiá-lo, precisa preencher metade do JavaScript de qualquer maneira ...
Obrigado