Comment générer de l'aléatoire de hachage SHA1 pour l'utiliser comme IDENTIFIANT dans node.js?

Question

J'utilise cette ligne pour générer un sha1 id pour node.js:

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

Le problème est qu'il est de retour le même id à chaque fois.

Est-il possible de faire générer un id aléatoire à chaque fois donc je peux l'utiliser comme un document de base de données id?

Answer 1

14,615,016,373,300,259,879,912,540,705,229 x plus d'entropie

Je vous recommande d'utiliser de la cryptographie.randomBytes. Ce n'est pas sha1, mais pour l'identification, c'est plus rapide, et tout comme "aléatoire".

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

La chaîne résultante sera deux fois plus long que les octets aléatoires que vous générer; chaque octet codé en hexadécimal est de 2 caractères. 20 octets sera de 40 caractères de l'hexagone.

À l'aide de 20 octets, nous avons 256^20 ou 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 unique de valeurs de sortie. C'est identique pour SHA1 160 bits (20 octets) sorties possibles.

Sachant cela, il n'est pas vraiment important pour nous de shasum notre octets aléatoires. C'est comme rouler un dé deux fois, mais seulement d'accepter le deuxième rouleau; n'importe quoi, vous avez 6 résultats possibles de chaque rouleau, de sorte que le premier rouleau est suffisant.

---

Pourquoi est-ce mieux?

Pour comprendre pourquoi c'est mieux, nous devons d'abord comprendre comment les fonctions de hachage du travail. Les fonctions de hachage (y compris SHA1) se produira toujours la même sortie que si la même entrée est donnée.

Disons que nous voulons générer des Id mais au hasard de notre entrée est générée par un tirage au sort. Nous avons "heads" ou "tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

Si "heads" revient une fois de plus, le SHA1 de sortie sera le même que c'était la première fois

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, donc un tirage au sort n'est pas une bonne ID aléatoire générateur parce que nous n'avons que 2 sorties possibles.

Si l'on utilise une norme de dés à 6 faces, nous avons 6 entrées possibles. Devinez combien de possible SHA1 sorties? 6!

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

Il est facile de se leurrer en pensant simplement parce que la sortie de notre fonction semble très aléatoire, que c' est très aléatoire.

Nous avons tous deux d'accord que d'un tirage au sort ou un dés à 6 faces ferait une mauvaise id aléatoire générateur, car notre possible SHA1 résultats (la valeur que nous utilisons pour l'ID) sont très rares. Mais que faire si nous utilisons quelque chose qui a beaucoup plus de sorties? Comme un timestamp avec millisecondes? Ou du JavaScript Math.random? Ou même une combinaison de ces deux?!

Nous allons calculer combien d'identifiants uniques, nous aurions ...

---

L'unicité d'un timestamp avec millisecondes

Lors de l'utilisation d' (new Date()).valueOf().toString(), vous obtenez un 13-nombre de caractères (par exemple, 1375369309741). Cependant, depuis, d'une manière séquentielle la mise à jour de numéro (par milliseconde), les sorties sont presque toujours les mêmes. Jetons un coup d'oeil

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

Pour être juste, pour des fins de comparaison, dans une minute donnée (un généreux opération de temps d'exécution), vous devrez 60*1000 ou 60000 uniques.

---

L'unicité de l' Math.random

Maintenant, lors de l'utilisation d' Math.random, en raison de la façon JavaScript représente 64 bits des nombres à virgule flottante, vous obtiendrez un nombre dont la longueur n'importe où entre le 13 et le 24 caractères. Un plus, cela signifie plus de chiffres qui signifie plus d'entropie. Tout d'abord, nous avons besoin de savoir qui est le plus probable de la longueur.

Le script ci-dessous permettra de déterminer la longueur de qui est le plus probable. Pour ce faire, nous générer 1 million de nombres aléatoires et en incrémentant un compteur basé sur l' .length de chaque numéro.

// get distribution
var counts = [], rand, len;
for (var i=0; i<1000; 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 });

En divisant chaque compteur de 1 million de dollars, nous obtenons la probabilité que la longueur de la nombre retourné à partir 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

Donc, même si elle n'est pas entièrement vrai, soyons généreux et disons que vous obtenez un 19 caractères aléatoire de sortie; 0.1234567890123456789. Les premiers caractères seront toujours 0 et ., si vraiment nous ne sommes qu'à l'obtention de 17 caractères aléatoires. Ce qui nous laisse avec 10^17 +1 ( 0; voir les notes ci-dessous) ou 100,000,000,000,000,001 uniques.

---

Si le nombre des entrées aléatoires pouvons-nous produire?

Ok, nous avons calculé le nombre de résultats pour une milliseconde d'horodatage et d' Math.random

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

C'est un seul 100,000,000,000,060,001 dérapé meurt. Ou, pour faire de ce nombre, plus humainement digeste, c'est à peu près le même nombre que le laminage 10x 50-dégrossies. Semble assez bon, non?

SHA1 produit une valeur de 20 octets, avec une possible 256^20 résultats. Donc, nous ne sommes pas vraiment en utilisant SHA1 à son plein potentiel. Bien combien sommes-nous à l'aide?

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

Une milliseconde de l'horodatage et des Mathématiques.aléatoire utilise uniquement 6.84 e-30% de SHA1 160 bits potentiel!

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

Saint chats, l'homme! Regardez tous ces zéros. Alors, comment beaucoup mieux est - crypto.randomBytes? 14,615,016,373,300,259,879,912,540,705,229 fois mieux.

---

Notes à propos de l' +1 et la fréquence des zéros

Si vous vous demandez à propos de l' +1, Math.random - retour d'un 0 ce qui signifie qu'il y a 1 plus possible de résultat unique, nous avons à prendre en compte.

Basé sur la discussion qui s'est passé en dessous, j'étais curieux de connaître la fréquence d'un 0 serait venu. Voici un petit script, random_zero.js, je l'ai fait pour obtenir certaines données

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

Ensuite, j'ai couru en 4 fils (j'ai un processeur 4 cœurs), en ajoutant la sortie vers un fichier

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

Ainsi, il s'avère qu'un 0 n'est pas difficile à obtenir. Après 100 valeurs ont été enregistrées, la moyenne était de

1 dans 3,164,854,823 randoms est un 0

Cool! Plus de recherche serait nécessaire pour savoir si le numéro est sur le pair avec une distribution uniforme de la v8 Math.random mise en œuvre

Answer 2

Jetez un oeil ici: Comment dois-je utiliser node.js Crypto pour créer un HMAC-SHA1 hash? Je voudrais créer une table de hachage de l'horodatage actuel + un nombre aléatoire pour assurer l'unicité de hachage:

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

Answer 3

Le faire dans le navigateur, trop !

EDIT: cela ne rentre pas vraiment dans le flux de ma réponse précédente. Je pars ici comme une seconde réponse pour les personnes qui pourraient être à la recherche pour ce faire dans le navigateur.

Vous pouvez le faire côté client dans les navigateurs modernes, si vous le souhaitez

// 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, function(n) { return n.toString(16); }).join("");
}

Ok, nous allons le vérifier !

generateId();
// "82defcf324571e70b0521d79cce2bf3fffccd69"

generateId(20);
// "c1a050a4cd1556948d41"

Configuration requise pour le navigateur

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