جاوااسکریپت - چگونه یک هش SHA1 تصادفی برای استفاده به عنوان شناسه در node.js تولید کنیم؟

من از این خط برای تولید یک شناسه sha1 برای node.js استفاده میکنم:

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

مشکل این است که هر بار همان شناسه را برمیگرداند.

آیا ممکن است که هر بار یک شناسهی تصادفی تولید کند تا من بتوانم از آن به عنوان شناسه سند پایگاه داده استفاده کنم؟

پاسخ شماره ۱

۲۴۳,۵۸۳,۶۰۶,۲۲۱,۸۱۷,۱۵۰,۵۹۸,۱۱۱,۴۰۹ برابر بیشتر آنتروپی

من استفاده از crypto.randomBytes را پیشنهاد میکنم. این sha1 نیست، اما برای مقاصد شناسه، سریعتر است و به همان اندازه «تصادفی» است.

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

رشته حاصل دو برابر طول بایتهای تصادفی است که تولید میکنید؛ هر بایت به صورت هگزادسیمال ۲ کاراکتر میشود. ۲۰ بایت برابر با ۴۰ کاراکتر هگزادسیمال خواهد بود.

با استفاده از ۲۰ بایت، ما 256^20 یا 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 مقدار خروجی منحصربهفرد داریم. این دقیقاً مشابه خروجیهای ممکن ۱۶۰ بیتی (۲۰ بایتی) SHA1 است.

با دانستن این، واقعاً معنی ندارد که ما shasum بگیریم از بایتهای تصادفیمان. این مثل این است که دوبار تاس بیندازید اما فقط دور دوم را قبول کنید؛ مهم نیست چه اتفاقی بیفتد، هر بار پرتاب ۶ نتیجه ممکن دارد، بنابراین پرتاب اول کافی است.

چرا این بهتر است؟

برای درک اینکه چرا این بهتر است، ابتدا باید بفهمیم که توابع هش چگونه کار میکنند. توابع هش (از جمله SHA1) همیشه همان خروجی را تولید میکنند اگر ورودی یکسان داده شود.

فرض کنید میخواهیم شناسهها را تولید کنیم اما ورودی تصادفی ما با پرتاب سکه تولید میشود. ما "شیر" یا "پیش" داریم

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

اگر "heads" دوباره بیاید، خروجی SHA1 همان خواهد بود که بار اول بود

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

باشه، پس پرتاب سکه یک تولیدکننده شناسه تصادفی عالی نیست چون ما فقط ۲ خروجی ممکن داریم.

اگر از یک تاس استاندارد ۶ وجهی استفاده کنیم، ۶ ورودی ممکن داریم. حدس بزنید چند خروجی SHA1 ممکن وجود دارد؟ ۶!

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

آسان است که خودمان را فریب دهیم و فکر کنیم فقط به این دلیل که خروجی تابع ما به نظر میرسد بسیار تصادفی است، واقعاً بسیار تصادفی است.

ما هر دو موافقیم که پرتاب سکه یا یک تاس شش وجهی تولیدکننده شناسه تصادفی مناسبی نخواهند بود، زیرا نتایج احتمالی SHA1 ما (مقداری که برای شناسه استفاده میکنیم) بسیار کم هستند. اما اگر چیزی استفاده کنیم که خروجیهای زیادی داشته باشد چه؟ مانند یک علامت زمانی با میلیثانیه؟ یا تابع Math.random در جاوااسکریپت؟ یا حتی ترکیبی از این دو؟!

بیایید محاسبه کنیم که دقیقاً چند شناسه منحصر به فرد خواهیم داشت...

منحصر به فرد بودن یک مهر زمانی با میلیثانیهها

وقتی از (new Date()).valueOf().toString() استفاده میکنید، یک عدد ۱۳ رقمی دریافت میکنید (مثلاً 1375369309741). با این حال، از آنجایی که این یک عدد بهروزرسانی شونده متوالی است (یک بار در هر میلیثانیه)، خروجیها تقریباً همیشه یکسان هستند. بیایید نگاهی بیندازیم

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

برای انصاف، برای مقاصد مقایسه، در یک دقیقه مشخص (زمان اجرای عملیات سخاوتمندانه)، شما 60*1000 یا 60000 منحصر به فرد خواهید داشت.

منحصر به فرد بودن Math.random

اکنون، هنگام استفاده از Math.random، به دلیل نحوه نمایش اعداد شناور ۶۴ بیتی در جاوا اسکریپت، شما عددی با طولی بین ۱۳ تا ۲۴ کاراکتر دریافت خواهید کرد. نتیجه طولانیتر به معنای ارقام بیشتر است که به معنای آنتروپی بیشتر است. ابتدا باید بفهمیم که احتمالیترین طول کدام است.

اسکریپت زیر طولی که بیشترین احتمال را دارد تعیین خواهد کرد. ما این کار را با ایجاد ۱ میلیون عدد تصادفی و افزایش شمارنده بر اساس .length هر عدد انجام میدهیم.

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

با تقسیم هر شمارنده بر ۱ میلیون، احتمال طول عدد بازگشتی از 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

بنابراین، حتی اگر کاملاً درست نباشد، بیایید سخاوتمند باشیم و بگوییم شما یک خروجی تصادفی ۱۹ کاراکتری دریافت میکنید؛ 0.1234567890123456789. کاراکترهای اول همیشه 0 و . خواهند بود، بنابراین واقعاً ما فقط ۱۷ کاراکتر تصادفی دریافت میکنیم. این ما را با 10^17 +1 (برای احتمال 0؛ به یادداشتهای پایین مراجعه کنید) یا ۱۰۰,۰۰۰,۰۰۰,۰۰۰,۰۰۰,۰۰۱ مقدار یکتا میگذارد.

پس چند ورودی تصادفی میتوانیم تولید کنیم؟

باشه، ما تعداد نتایج برای یک زمانسنج میلیثانیهای و Math.random را محاسبه کردیم

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

این یک تاس با ۶٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۶۰٬۰۰۰ وجه است. یا، برای اینکه این عدد برای انسان قابل هضمتر شود، این تقریباً همان عدد است که

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

خیلی خوب به نظر میرسد، نه؟ خوب، بیایید بفهمیم...

SHA1 یک مقدار ۲۰ بایتی تولید میکند، با ۲۵۶^۲۰ نتیجه ممکن. بنابراین ما واقعاً از SHA1 به تمام ظرفیت آن استفاده نمیکنیم. خب، چقدر از آن استفاده میکنیم؟

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

مهر زمانی در میلی ثانیه و Math.random تنها از 4.11e-27 درصد از پتانسیل 160 بیتی SHA1 استفاده می کند!

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

وای خدای من! به همه این صفرها نگاه کن. پس crypto.randomBytes(20) چقدر بهتر است؟ 243,583,606,221,817,150,598,111,409 برابر بهتر.

یادداشتهایی درباره +1 و فرکانس صفرها

اگر درباره +1 کنجکاو هستید، ممکن است Math.random مقداری 0 بازگرداند که به این معنی است که یک نتیجه یکتا دیگر وجود دارد که باید در نظر بگیریم.

بر اساس بحثی که در زیر اتفاق افتاد، من کنجکاو بودم که ببینم یک 0 چند بار ظاهر میشود. این یک اسکریپت کوچک است، random_zero.js، که من برای جمعآوری دادهها ساختهام

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

سپس، آن را در ۴ رشته اجرا کردم (من یک پردازنده ۴ هستهای دارم) و خروجی را به یک فایل افزودم

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

بنابراین مشخص شد که گرفتن یک 0 چندان سخت نیست. پس از ثبت 100 مقدار، متوسط به دست آمد

1 در 3,164,854,823 تصادفیها برابر با 0 است

عالی! برای دانستن اینکه آیا آن عدد با توزیع یکنواخت پیادهسازی Math.random در v8 مطابقت دارد یا نه، نیاز به تحقیقات بیشتری خواهد بود

پاسخ شماره ۲

اینجا نگاهی بیندازید: چگونه از node.js Crypto برای ایجاد یک هش HMAC-SHA1 استفاده کنم؟ من میخواهم یک هش از زمان فعلی + یک عدد تصادفی ایجاد کنم تا یکتایی هش تضمین شود:

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

پاسخ شماره ۳

این کار را هم در مرورگر انجام بده!

ویرایش: این واقعاً با روند پاسخ قبلی من همخوانی نداشت. من آن را اینجا بهعنوان یک پاسخ دوم برای افرادی که ممکن است بخواهند این کار را در مرورگر انجام دهند، میگذارم.

اگر بخواهید، میتوانید این کار را در سمت کاربر در مرورگرهای مدرن انجام دهید

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

الزامات مرورگر

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