¿Cómo generar hash aleatorio SHA1 para usar como ID en node.js?

Question

estoy usando esta línea para generar un identificador de SHA1 para Node.js:

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

El problema es que está devolviendo el mismo id cada vez.

¿Es posible que genere un ID aleatorio cada vez para que pueda usarlo como una identificación de documento de base de datos?

Answer 1

un vistazo aquí: How do I use node.js Crypto to create a HMAC-SHA1 hash? que crearía un hash de la fecha y hora actual + un número aleatorio para garantizar la singularidad de hash:

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

Answer 2

243,583,606,221,817,150,598,111,409x más entropía

me gustaría recomendar el uso crypto.randomBytes. No es sha1, pero para fines de identificación, es más rápido e igual de "aleatorio".

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

La cadena resultante será el doble de larga que los bytes aleatorios que genere; cada byte codificado en hex es de 2 caracteres. 20 bytes serán 40 caracteres de hex.

El uso de 20 bytes, tenemos 256^20 o 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 valores de salida únicas. Esto es idéntico a las salidas posibles de SHA1 de 160 bits (20 bytes).

Sabiendo esto, no es realmente significativo para nosotros shasum nuestros bytes aleatorios. Es como lanzar un dado dos veces pero solo aceptar el segundo lanzamiento; no importa qué, tienes 6 resultados posibles en cada tirada, por lo que la primera tirada es suficiente.

---

¿Por qué es esto mejor?

Para entender por qué esto es mejor, primero tenemos que entender cómo funcionan las funciones hash. Las funciones hash (incluido SHA1) siempre generarán el mismo resultado si se proporciona la misma entrada.

Digamos que queremos generar ID pero nuestra entrada aleatoria se genera con un lanzamiento de moneda. Tenemos "heads" o "tails"

% echo -n "heads" | shasum 
c25dda249cdece9d908cc33adcd16aa05e20290f - 

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

Si "heads" viene de nuevo, la salida SHA1 será el misma ya que era la primera vez

% echo -n "heads" | shasum 
c25dda249cdece9d908cc33adcd16aa05e20290f - 

Ok, por lo que un lanzamiento de la moneda no es un gran generador de ID aleatorio porque solo tenemos 2 salidas posibles.

Si utilizamos un dado estándar de 6 caras, tenemos 6 entradas posibles. Adivina cuántas posibles salidas SHA1? 6!

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

Es fácil engañarnos pensando sólo porque la salida de nuestra función se ve muy aleatorio, que es muy aleatorio.

Ambos estamos de acuerdo en que un lanzamiento de moneda o un dado de 6 caras sería un generador de identificación aleatorio malo, porque nuestros posibles resultados de SHA1 (el valor que usamos para la ID) son muy pocos. ¿Pero qué pasa si utilizamos algo que tiene muchas más salidas? ¿Como una marca de tiempo con milisegundos? O JavaScript Math.random? O incluso una combinación de esos dos ?!

vamos a calcular cuántos identificadores únicos que se pueden conseguir ...

---

La singularidad de una marca de tiempo con milisegundos

Al utilizar (new Date()).valueOf().toString(), que está recibiendo un número de 13 caracteres (por ejemplo, 1375369309741). Sin embargo, dado que se trata de un número de actualización secuencial (una vez por milisegundo), las salidas son casi siempre las mismas. Vamos a echar un vistazo

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 justos, a efectos comparativos, en un minuto determinado (una operación de tiempo de ejecución generoso), tendrá 60*1000 o 60000 únicos.

---

La singularidad de Math.random

Ahora, cuando se utiliza Math.random, debido a la forma JavaScript representa números de punto flotante de 64 bits, obtendrá un número con longitud en cualquier lugar entre 13 y 24 caracteres largo. Un resultado más largo significa más dígitos, lo que significa más entropía. Primero, necesitamos averiguar cuál es la longitud más probable.

El siguiente script determinará qué longitud es la más probable. Hacemos esto generando 1 millón de números aleatorios e incrementando un contador basado en el .length 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 }); 

Al dividir cada contador en 1 millón, obtenemos la probabilidad de la longitud del número de regresar de 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 

Así, a pesar de que no es del todo cierto, seamos generosos y decir se obtiene una salida aleatoria de 19 caracteres de longitud; 0.123456789. Los primeros personajes siempre serán 0 y ., así que realmente solo tenemos 17 caracteres aleatorios. Esto nos deja con 10^17+1 (para posibles 0, ver notas a continuación) o 100,000,000,000,000,001 uniques.

---

Entonces, ¿cuántas entradas aleatorias podemos generar?

Ok, se calculó el número de resultados para una marca de tiempo de milisegundos y Math.random

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

Esa es una matriz única 6,000,000,000,000,000,060,000 unilateral.O bien, para que este número sea más digerible humanamente, esto es más o menos el mismo 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 

Suena bien, ¿verdad? Bueno, descubramos ...

SHA1 produce un valor de 20 bytes, con posibles resultados de 256^20. Así que realmente no estamos usando SHA1 a su máximo potencial. Bueno, ¿cuánto estamos usando?

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

Una marca de tiempo de milisegundos y Math.random utiliza sólo 4.11e-27 por ciento del potencial de 160 bits de SHA1!

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

Holy cats, man! Mira todos esos ceros. Entonces, ¿cuánto mejor es crypto.randomBytes(20)? 243,583,606,221,817,150,598,111,409 veces mejor.

---

Notas sobre el +1 y la frecuencia de ceros

Si usted se está preguntando acerca de la +1, es posible que Math.random para regresar el 0 que significa que hay 1 más posible resultado único que tenemos que tener en cuenta para.

Basado en la discusión que sucedió a continuación, tenía curiosidad acerca de la frecuencia con la que aparecería 0. He aquí un pequeño script, random_zero.js, que hice para obtener algunos datos

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

Entonces, me encontré en 4 hilos (tengo un procesador de 4 núcleos), añadiendo la salida a un archivo

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

Entonces resulta que un 0 no es tan difícil de conseguir. Después 100 values se registraron, el promedio fue de

1 en randoms es un 0

fresco! Se necesitarán más investigaciones para saber si ese número está a la par con una distribución uniforme de la implementación dede v8

Answer 3

¡Hágalo también en el navegador!

EDITAR: esto realmente no encajaba en el flujo de mi respuesta anterior. Lo dejo aquí como una segunda respuesta para las personas que podrían estar buscando hacer esto en el navegador.

Usted puede hacer esto en el lado del cliente los navegadores modernos, si desea

// 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) { 
    var arr = new Uint8Array((len || 40)/2); 
    window.crypto.getRandomValues(arr); 
    return [].map.call(arr, byteToHex).join(""); 
} 

Ok, vamos a echarle un vistazo!

generateId(); 
// "1e6ef8d5c851a3b5c5ad78f96dd086e4a77da800" 

generateId(20); 
// "d2180620d8f781178840" 

Requisitos del navegador

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