243,583,606,221,817,150,598,111,409x większa entropia
Polecam użycie crypto.randomBytes . Nie jest sha1, ale dla celów identyfikacyjnych jest szybszy i równie „losowy”.
var id = crypto.randomBytes(20).toString('hex');
//=> f26d60305dae929ef8640a75e70dd78ab809cfe9
Wynikowy ciąg będzie dwa razy dłuższy niż losowe bajty, które wygenerujesz; każdy bajt zakodowany w kodzie szesnastkowym to 2 znaki. 20 bajtów to 40 znaków szesnastkowych.
Korzystanie 20 bajtów, mamy 256^20lub 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 unikalne wartości wyjściowe. Jest to identyczne z 160-bitowymi (20-bajtowymi) możliwymi wyjściami SHA1.
Wiedząc o tym, nie ma to dla nas znaczenia dla shasumnaszych losowych bajtów. To tak, jakby dwukrotnie rzucić kostką, ale zaakceptować tylko drugi rzut; nie ważne co, masz 6 możliwych wyników w każdym rzucie, więc pierwszy rzut jest wystarczający.
Dlaczego tak jest lepiej?
Aby zrozumieć, dlaczego jest to lepsze, musimy najpierw zrozumieć, jak działają funkcje haszujące. Funkcje haszujące (w tym SHA1) zawsze generują te same dane wyjściowe, jeśli podane są te same dane wejściowe.
Powiedzmy, że chcemy wygenerować identyfikatory, ale nasze losowe dane wejściowe są generowane przez rzut monetą. Mamy "heads"lub"tails"
% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f -
% echo -n "tails" | shasum
71ac9eed6a76a285ae035fe84a251d56ae9485a4 -
Jeśli "heads"pojawi się ponownie, wyjście SHA1 będzie takie samo, jak za pierwszym razem
% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f -
Ok, więc rzut monetą nie jest świetnym generatorem losowych identyfikatorów, ponieważ mamy tylko 2 możliwe wyjścia.
Jeśli używamy standardowej sześciościennej matrycy, mamy 6 możliwych wejść. Zgadnij, ile możliwych wyjść SHA1? 6!
input => (sha1) => output
1 => 356a192b7913b04c54574d18c28d46e6395428ab
2 => da4b9237bacccdf19c0760cab7aec4a8359010b0
3 => 77de68daecd823babbb58edb1c8e14d7106e83bb
4 => 1b6453892473a467d07372d45eb05abc2031647a
5 => ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4
6 => c1dfd96eea8cc2b62785275bca38ac261256e278
Łatwo się oszukać, myśląc tylko dlatego, że wynik naszej funkcji wygląda bardzo przypadkowo, że jest bardzo przypadkowy.
Obaj zgadzamy się, że rzut monetą lub sześciościenna kostka stworzyłby zły generator losowych identyfikatorów, ponieważ nasze możliwe wyniki SHA1 (wartość, której używamy jako ID) są bardzo nieliczne. Ale co, jeśli użyjemy czegoś, co ma o wiele więcej wyników? Jak znacznik czasu z milisekundami? Albo JavaScript Math.random? A może nawet połączenie tych dwóch ?!
Obliczmy, ile unikalnych identyfikatorów otrzymalibyśmy ...
Wyjątkowość sygnatury czasowej z milisekundami
Podczas używania (new Date()).valueOf().toString()otrzymujesz 13-znakową liczbę (np 1375369309741.). Jednak ponieważ jest to numer aktualizowany sekwencyjnie (raz na milisekundę), wyniki są prawie zawsze takie same. Spójrzmy
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
Aby być uczciwym, dla celów porównawczych, w danej minucie (hojny czas wykonania operacji) będziesz mieć unikaty 60*1000lub 60000.
Wyjątkowość Math.random
Teraz, gdy używasz Math.random, ze względu na sposób, w jaki JavaScript reprezentuje 64-bitowe liczby zmiennoprzecinkowe, otrzymasz liczbę o długości od 13 do 24 znaków. Dłuższy wynik oznacza więcej cyfr, co oznacza większą entropię. Najpierw musimy dowiedzieć się, która długość jest najbardziej prawdopodobna.
Poniższy skrypt określi, która długość jest najbardziej prawdopodobna. Robimy to, generując 1 milion liczb losowych i zwiększając licznik na podstawie .lengthkażdej liczby.
// 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 });
Dzieląc każdy licznik przez 1 milion, otrzymujemy prawdopodobieństwo długości zwróconej liczby 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
Tak więc, nawet jeśli nie jest to do końca prawdą, bądźmy hojni i powiedzmy, że otrzymujesz losowe wyjście o długości 19 znaków; 0.1234567890123456789. Pierwsze postacie zawsze będą 0i ., więc tak naprawdę otrzymujemy tylko 17 losowych postaci. To pozostawia nam 10^17 +1(możliwe 0; zobacz uwagi poniżej) lub 100 000 000 000 000 001 unikatów.
Więc ile losowych danych wejściowych możemy wygenerować?
Ok, obliczyliśmy liczbę wyników dla milisekundowego znacznika czasu i Math.random
100,000,000,000,000,001 (Math.random)
* 60,000 (timestamp)
-----------------------------
6,000,000,000,000,000,060,000
To pojedyncza kostka 6,000,000,000,000,000 060,000. Lub, aby uczynić tę liczbę bardziej strawną dla człowieka, jest to mniej więcej taka sama liczba jak
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
Brzmi całkiem nieźle, prawda? Cóż, dowiedzmy się ...
SHA1 generuje 20-bajtową wartość z możliwymi 256 ^ 20 wynikami. Więc naprawdę nie używamy SHA1 do pełnego potencjału. Ile używamy?
node> 6000000000000000060000 / Math.pow(256,20) * 100
Milisekundowy znacznik czasu, a Math.random wykorzystuje tylko 4,11e-27 procent 160-bitowego potencjału SHA1!
generator sha1 potential used
-----------------------------------------------------------------------------
crypto.randomBytes(20) 100%
Date() + Math.random() 0.00000000000000000000000000411%
6-sided die 0.000000000000000000000000000000000000000000000411%
A coin 0.000000000000000000000000000000000000000000000137%
Święte koty, człowieku! Spójrz na te wszystkie zera. Więc o ile lepiej crypto.randomBytes(20)? 243,583,606,221,817,150,598,111,409 razy lepszy.
Uwagi dotyczące +1i częstotliwości zer
Jeśli zastanawiasz się nad tym +1, możliwe Math.randomjest zwrócenie a, 0co oznacza, że istnieje jeszcze jeden możliwy unikalny wynik, który musimy uwzględnić.
Opierając się na dyskusji, która odbyła się poniżej, byłem ciekawy, jaka 0będzie częstotliwość a . Oto mały skrypt, random_zero.jszrobiłem, aby uzyskać dane
#!/usr/bin/env node
var count = 0;
while (Math.random() !== 0) count++;
console.log(count);
Następnie uruchomiłem go w 4 wątkach (mam 4-rdzeniowy procesor), dołączając dane wyjściowe do pliku
$ yes | xargs -n 1 -P 4 node random_zero.js >> zeroes.txt
Okazuje się więc, że 0nie jest to takie trudne. Po zarejestrowaniu 100 wartości średnia wyniosła
1 na 3164,854,823 randoms to 0
Chłodny! Wymagane byłyby dalsze badania, aby dowiedzieć się, czy ta liczba jest równa jednorodnemu rozkładowi Math.randomimplementacji wersji 8