javascript - example - pbkdf2 node

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

Question

Estoy usando esta línea para generar una identificación sha1 para node.js:

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

El problema es que devuelve la misma identificación cada vez.

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

Answer 1

¡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.

Puede hacer este lado del cliente en los navegadores modernos, si lo 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 verlo!

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

Answer 2

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

Recomiendo usar 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.

Utilizando 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 únicos. 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 identificaciones, 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 vuelve a aparecer "heads" , la salida de SHA1 será la misma que la primera vez

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, entonces un lanzamiento de moneda no es un gran generador de ID aleatorio porque solo tenemos 2 salidas posibles.

Si usamos 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ñarse pensando solo porque el resultado de nuestra función es muy aleatorio, 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 Math.random de JavaScript? ¿O incluso una combinación de esos dos?

Calculemos cuántos identificadores únicos obtendríamos ...

La singularidad de una marca de tiempo con milisegundos

Al usar (new Date()).valueOf().toString() , obtendrá 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 ver

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 fines de comparación, en un minuto dado (un tiempo de ejecución de operación generoso), tendrá 60*1000 o 60000 únicos.

La singularidad de Math.random

Ahora, al utilizar Math.random , debido a la forma en que JavaScript representa los números de coma flotante de 64 bits, obtendrá un número con una longitud de entre 13 y 24 caracteres. 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 la .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 por 1 millón, obtenemos la probabilidad de que devuelva la longitud del número 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

Entonces, aunque no sea del todo cierto, seamos generosos y digamos que obtienes una salida aleatoria de 19 caracteres; 0.1234567890123456789 . Los primeros personajes siempre serán 0 y . , entonces realmente solo tenemos 17 personajes aleatorios. Esto nos deja con 10^17 +1 (para posibles 0 , ver notas a continuación) o 100,000,000,000,000,001 únicos.

Entonces, ¿cuántas entradas aleatorias podemos generar?

Bien, calculamos la cantidad 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

Eso es un solo dado de 6,000,000,000,000,000,060,000 caras. O bien, para que este número sea más digerible humanamente, este es aproximadamente 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 bastante 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 usa solo el 4.11e-27 por ciento del potencial de 160 bit de SHA1!

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

¡Santos gatos, amigo! 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 te estás preguntando sobre el +1 , es posible que Math.random devuelva un 0 que significa que hay un único resultado posible más que debemos tener en cuenta.

Basado en la discusión que sucedió a continuación, tenía curiosidad sobre la frecuencia con la que aparecería un 0 . Aquí hay 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);

Luego, lo ejecuté en 4 hilos (tengo un procesador de 4 núcleos), agregando el resultado 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 de registrar 100 valores , el promedio fue

1 en 3,164,854,823 randoms es un 0

¡Guay! Se necesitarían más investigaciones para saber si ese número está a la par con una distribución uniforme de la implementación Math.random de v8 Math.random

Answer 3

Eche un vistazo aquí: ¿Cómo uso node.js Crypto para crear un hash HMAC-SHA1? Crearía un hash de la marca de tiempo actual + un número aleatorio para asegurar 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'');