ساخت رندوم در کامپیوتر چگونه است؟

کامپیوترها ماشین‌حساب‌های خیلی خوبی هستند. با سرعت و دقت محاسبات انجام می‌دهند و جواب را به ما نمایش می‌دهند یا در شبکه ارسال می‌کنند. در طی این سال‌ها در محاسبه بهتر و بهتر هم شده‌اند. حتی با پیشرفت هوش مصنوعی، در حد انسان و بهتر تصمیم‌گیری می‌کنند، انتخاب می‌کنند و بازی می‌کنند. اما یکی از کارهایی که برای کامپیوترها خیلی سخت بوده و هست، تاس انداختن است! دقیق‌تر بگم، ساخت عدد تصادفی.

توزیعِ یکنواخت

زود، تند، سریع یک عدد بین ۱ تا ۱۰ انتخاب کن. انتخاب کردی؟ چند بود؟‌ ۱؟ شاید هم ۱۰. ولی موفق شدی درسته؟ اما آیا این انتخاب کردنت «تصادفی» بود؟ اگر دوباره بگویم انتخاب کن ممکن است همین عدد را بگویی؟ یا حتما یک عدد دیگر را انتخاب می‌کنی؟ یا ممکن است هر دو حالت اتفاق بیفتد؟

می‌خواهم در مورد «توزیع یکنواخت» صحبت کنم. اسم انگلیسیش سخت‌تر هم هست ولی نکته پیچیده‌ای ندارد. کل موضوع به این بر می‌گردد که اگر تعداد خیلی زیادی تاس انداختیم، تعداد ۱ ها با ۲ ها با ۳ ها تا ۶ ها برابر باشند. به بیان دیگر «احتمال آمدن هر یک از حالت‌های دامنه» برابر باشد.

در کتاب آمار و احتمال دبیرستان (اگر هنوز چنین کتابی باشد و به دبیرستان همچنان دبیرستان بگویند) از واژه‌ی «تاس سالم» استفاده می‌کرد. یعنی تاسی که ۶ وجه (۶ حالت مختلف خروجی) دارد و احتمال آمدن هر یک از وجه‌ها دقیقا ۱/۶ است. سوال پیش می‌آید که تاس غیر سالم چگونه است؟ فرض کنید یکی از وجه‌ها را سنگین کنیم. در این حالت احتمال بیش‌تری وجود دارد که آن وجه تاس به سمت زمین بیاید و وجه مخالف احتمال بیشتری برای بالا آمدن دارن. این یک تاس غیر سالم است! یا مثلا سکه‌ای را فرض کنید که به ازای ۱۰۰ بار پرتاب، ۸۰ بار شیر بیاید و ۲۰ بار خط. چنین سکه‌ای مورد قبول است؟ البته می تواند مورد قبول باشد ولی اکثر اوقات می‌خواهیم توزیع یکنواخت داشته باشیم، یعنی احتمال شیر آمدن با خط آمدن یکسان باشد.

در حالت اغراق شده‌ی غیر یکنواخت، می‌توان تاسی را فرض کرد که همواره ۱ می‌آورد. یا سکه‌ای که فقط و فقط شیر می‌آید. (مثل سکه‌ی هاروی‌دنت قبل از اینکه یک طرفش بسوزد!)

غیرقابل پیش‌بینی بودن

اصلا برای چه تاس می‌اندازیم؟ برای اینکه نتیجه را ببینیم. وگرنه مگر بیکاریم در صورتی که جواب را می دانیم تاس بیندازیم. یکی از خاصیت‌های مهم عدد رندوم (که از اسمش هم بر میاد!) غیر قابل پیش‌بینی بودن است.

فرض کنید قرار است یک بازی دو نفره بکنید. قرار است طرف مقابل یک عدد حدس بزند‌ (یا الگویی را مشخص کند) و شما آن را کشف کنید. حالا فرض کنیم این رندوم انتخاب کردن، حالت یکنواختی خوبی دارد و یه بیانی، احتمال انتخاب حالت های مختلف آن یکسان است. آیا همین کافیست؟

مثلا نظرتان درباره بازیکنی که در مقابل شما عدد‌های زیر را انتخاب کند چیست؟

۱ - ۲ - ۳ - ۴ - ۵ - ۶ - ۷ - ۸ - ۹ - ۱۰ - ..

این بازی اصلا هیجانی دارد؟ نه! چون قابل پیش‌بینی است. همین موضوع برای تاس و سکه هم برقرار است. در کاربردهای رندومِ کامپیوتر بسیار مهم‌تر هم می‌شود. مثلا فرض کنید password generatorی که نصب کرده‌اید، پسوردی را برایتان تولید کند که هکر محترم بتواند آن را حدس بزند. به نظر موضوع مهمی می‌آید.

خاصیت دوم رندوم خوبی که کامپیوتر باید تولید کند، غیر قابل پیش‌بینی بودن است. شاید حتی در کاربردهای رمزنگاری از خاصیت اول مهم‌تر هم باشد.

کامپیوترِ قابل پیش‌بینی

مشکل بزرگ اینجاست که کامپیوتر قابل پیش‌بینی است. اصلا کامپیوتر را طراحی کردیم که قابل پیش‌بینی باشد و محاسباتی که جوابش را می‌دانیم سریع تر انجام دهد. پردازنده مرکزی به عنوان مغز متفکر کامپیوتر هیچ‌گونه تصادفی‌بودن (randomness)ی ندارد. دستوری که باید اجرا کند را می‌گیرد، اجرا می‌کند و جواب را در جای مربوطه ذخیره می‌کند. این دستورات هم از ضرب و جمع و منها خارج نیست. رم و مادربورد هم کارشان را انجام می‌دهند. کار هیچ کدام تاس انداختن نیست.

آیا می‌شود الگوریتمی طراحی کرد که با استفاده از جمع و منها و ضرب و ..، عدد تصادفی تولید کرد؟ پاسخ «خیر» است. اما احتمالا می‌گویید نه من با پایتون/سی/جاوا/هرزبانی عدد رندوم ساخته‌ام، هر دو خصوصیتی که ذکر کردی هم داشت، پس داستان چیست؟ به داستان هم می‌رسیم، اصلا هدف مطلب توضیح چگونگیِ کارکرد همان تابع است.

برگردیم به طراحی الگوریتم‌مان. آیا می‌شود با جمع و منها و ضرب و تقسیم الگوریتمی ساخت که خروجی رندوم بدهد؟ متاسفانه از «الگوریتم» هم انتطار داریم قطعی عمل کند. اصلا فرض کنید دوستمان ادعا کرد چنین الگوریتمی نوشته، باید پرسید ورودی الگوریتم چیست؟ اولن جمع/منها را با چه چیزی شروع می‌کنی؟ با یک عدد ثابت؟

اما همین الگوریتمی که دوستمان نوشته را دور نیندازیم، آیا می‌شود یک ورودی بهش بدهیم و خروجی رندوم از آن انتظار داشته باشیم؟ به شرط رندوم بودن ورودی بله! خب اگر ورودی رندوم داشتیم که چه کاری بود الگوریتم بنویسیم؟ موضوع این است که می‌توان بازه خروجی را در محدوده خاصی قرار داد (مثلا اگر کاربرد تاس داریم برد تابع ۱ تا ۶ شود) یا حتی حالت uniform بودن به آن بدهیم.

به این الگوریتم‌ها «الگوریتم ساخت شبه‌رندوم» گفته می‌شود (PRNG)، یکی از مشهورترین (و البته بین جدیدها) مِرسِم توئیستر نام دارد. این پاسخ هم می‌تواند مفید باشد.

ورودی الگوریتم‌های ساخت شِبه‌رندوم

تا اینجا گفتیم کامپیوتر قابل‌ پیش‌بینیست، نمی‌تواند به تنهایی عدد تصادفی تولید کند. دوستمان ادعا کرد که الگوریتمی نوشته که عدد تصادفی تولید می‌کند ولی از او پرسیدیم «ورودی الگوریتمت چیه؟». احتمالا جواب داد که الگوریتم تولید رندوم، یک ورودی رندوم می‌خواهد ولی می‌تواند کیفیت رندومش را بالا ببرد.

حالا به این الگوریتم چه رندوم بی‌کیفیتی بدهیم که کیفیت آن را بالا ببرد؟ به این ورودی seed گفته می‌شود. در واقع seed کلیدی برای حل مشکل رندوم نبودن کامپیوترهایمان است. مشکل به این صورت حل می‌شود که seed را به الگوریتم تولید عدد شبه‌تصادفی می‌دهیم و برایمان عدد شبه‌تصادفی درست می‌کند. (راستی چرا شبه‌تصادفی؟ چرا واقعا تصادفی نه؟)

اما سوالمان همچنان باقیست. seed را چه مقداری بگذاریم تا رندوم خوبی بگیریم؟

اگر با سی عدد رندوم ساخته باشید، معروف است که می‌گویند برای ساخت رندوم باید این دو دستور را بنویسی:

srand(time(0));
long random = rand() % limit;

الان می‌بینیم srand معنی‌اش ررا از کجا گرفته. در واقع داریم به برنامه‌ی سی خودمون می‌گوییم که برای seed رندوم‌ات از time(0) استفاده کن. بعد از تابع رندوم را صدا کرده‌ایم. خروجی تابع time(0) چیست؟ زمان کنونی سیستم به واحد ثانیه از اول ژانویه ۱۹۷۰. (اول ژانویه ۱۹۷۰ برای سی و یونیکس تاریخ مهمیست.)

در این حالت، سیستم زمان کنونی خودش را نگاه می‌کند و از آن به عنوان seed برای تابع رندوم استفاده می‌کند.

مشکل حل شد؟ «تقریبا» به بیانی الان به این حالت رسیدیم که اگر امروز تابع رندوم را فراخوانی کنیم یک جواب می‌دهد. اگر یک ساعت بعد فراخوانی کنیم یک جواب دیگر می‌دهد. اگر فردا فراخوانی کنیم باز هم یه جواب دیگر می‌دهد. همین را می‌خواستیم مگر نه؟ جواب‌ها هم به صورت یکنواخت توزیع‌شده هستند. یعنی احتمال ۱ آمدن تاس با ۲ آمدن برابر است.

ساخت یک عدد رندوم یا ساخت یک دنباله رندوم؟

بیایید فرض کنیم یک seed معین به تابع داده‌ایم. بار اول rand() را صدا می‌زنیم. جواب چه می‌شود؟ مثلا ۵. بار دوم صدا بزنیم چه اتفاقی می‌افتد؟ باز هم از همان seed استفاده می‌کند و باز هم همان ۵ را خروجی می‌دهد؟ اگر بله، می‌توانیم srand(time(0)) را دوباره صدا کنیم تا seed جدیدی بدهد و رندوم دومی ۵ نشود؟ احتمالا نه چون از بار قبلی که صدا کردیم یک ثانیه نگذشته. نمی‌شود که هر دفعه یک ثانیه صبر کنیم تا رندوم بعدی را بسازیم.

برای حل این مشکل، توابع ساخت شبه‌رندوم، یک حالت داخلی در خود نگه می‌دارند. به این معنی که چیزهای محدودی از بار قبل که اجرا شدند یادشان هست. مثلا می‌توان فرض کرد که رندوم دفعه قبلی که ساخته‌اند را به عنوان seed به رندوم این دفعه می‌دهند. به این صورت مشکل گفته‌شده حل می‌شود. یا می‌شود ساده‌تر نگاه کرد، برای بار دوم رندوم ساختن از seed+1 استفاده می‌کنند و برای بار سوم از seed+2. هر چه که باشد، فرض می‌کنید که seed ما باعث تولید و شکل‌گیری «فقط یک عدد رندوم» نمی‌شود. بلکه دنباله‌ای نامتناهی از اعداد تصادفی با استفاده از همین seed اولیه قابل ساخت هستند.

مشکلات استفاده از زمان به عنوان seed

بیاید فرض کنیم در سراسر کشور، خودپردازهایی وجود دارند که سر ساعت ۲ صبح که تراکنش کم‌تر است، یک عدد تصادفی تولید می‌کنند و یک‌سری کار بر اساس عدد تصادفی انجام می‌دهند. همه از یک زبان برنامه‌نویسی و کتاب‌خانه‌های رندوم و سخت‌افزارهای مشابه استفاده می‌کنند. بدیهی‌است که زمانشان هم با دقت بسیار زیادی با هم سینک شده و زمان یکسانی دارند. خب فکر می‌کنید نتیجه رندوم ساختن چی خواهد بود؟ همه‌ی سیستم‌ها عدد تصادفی یکسانی خواهند ساخت! چرا؟ چون برای seed از یک مقدار مشخص (زمان آن لحظه) استفاده کردیم که بین همه مشترک بود. الگوریتم ساخت رندوم هم که بینشان یکی بود. جواب هم یکی در آمد. منطقی ولی ترسناک!

همانطور که دیدیم در شرایطی خاص، ممکن است عددمان اصلا خاصیت تصادفی نداشته باشد! حتی غیرقابل پیش‌بینی هم نیست. اگر n دستگاه خودپرداز ما در سراسر کشور این عدد را فهمیده‌اند، هکر عزیز هم می‌توان همان زمان را به seed رندومش بدهد و عدد ما را پیدا کند.

اما از این تهدید (که جلوتر روش‌های حلش را هم بررسی می‌کنیم) به عنوان فرصت استفاده می‌کنیم. برای دیباگ برنامه‌هایی که رندوم تولید می‌کنند، می‌توانیم از seed ثابت استفاده کنیم. در این صورت مطمئنیم اگر یه باگ رخ داده، به ازای «دنباله رندوم ساخته شده توسط آن seed» بوده، پس اگر seed را همان بگذاریم حتما باز هم رخ می‌دهد و می‌توانیم باگ را پیدا کنیم.

مثلا عجیب نیست که موقع دیباگ نوشته باشیم: srand(5) تا خاصیت رندوم‌بودن را از تابع رندوم بگیریم و بتوانیم دیباگش کنیم.

چرا «شبه‌رندوم»؟ مشکلات این رندوم را چطوری حل کنیم؟

از اول مطلب چندبار به عبارت شبه‌رندوم (Pseudorandomness) اشاره کردم. شبه‌رندوم یعنی دنباله رندوم‌هایمان اگرچه به نظر بی‌قاعده می‌آیند ولی با داشتن seed، کاملا قابل حدس زدن هستند. برای بسیاری از کاربردها همین رندوم مناسب است. همان بازی فکر بکری که اول مطلب مثال زدم، یا انواع بازی‌های کامپیوتری با همینقدر رندوم بودن مشکلشان حل می‌شود. حتی خودپردازهای مذکور را هم می‌توان مشکلشان را حل کرد، مثلا به جای ثانیه‌های گذشته از 1970، ثانیه‌های گذشته از آخرین ریبوت را ورودی بدهیم. یا ترکیبی از زمان ساخت، اسم کوچک آخرین تعمیرکار، کد نزدیک‌ترین شعبه و البته زمان فعلی می‌تواند مشکل را حل کند. بازهم رندوم قابل حدسی داریم ولی با باقی سیستم‌ها متفاوت است.

برای قسمت کوچک (ولی مهم)ی از کارها، نیاز به رندوم واقعی داریم. رندومی که هیچ‌کس نتواند حدس بزند، نه هکر، نه تعمیرکار قبلی، نه کسی که پشت سیستم نشسته است. «کاربردهای عدد تصادفی در رمزنگاری» معمولا به رندوم واقعی نیاز دارند تا آن رمزنگاری قابل اتکا باشد. پس رندوم واقعی چطوری تولید می‌شود؟ یک اپراتور استخدام می‌کنند تا مدام تاس بیندازد و عدد تاس را وارد کند؟

آنتروپی: ساخت رندوم واقعی!

تا اینجا، هر رندومی که می‌ساختیم «شبه رندوم» بود. با استفاده از یک seed مشخص و الگوریتم معینی به جواب‌های قابل پیش‌بینی‌ای می‌رسیدیم. اما اگر یک seed واقعا رندوم به الگوریتم بدهیم چه می‌شود؟ در این صورت واقعا رندوم خواهیم داشت. ورودی غیر قابل پیش‌بینی به خروجی غیرقابل پیش‌بینی منجر می‌شود. اما کامپیوتر با توصیفاتی که در پاراگراف اول از آن کردم، چطوری قرار است رندوم واقعی بسازد؟ با استفاده از آنتروپی سیستم. (دقت کنید ورودی غیرقابل پیش‌بینی یعنی کسی هم به آن دسترسی نداشته باشد و private باشد)

آنتروپی یعنی بی‌نظمی. سیستم کامپیوتری چطوری بی‌نظمی دارد که برای رندوم ساختن از آن استفاده کند؟ از سخت‌افزارش! مثلا صدای فن یا کارکردهای هارددیسک یا حتی حرکات موس. این‌ها ارتباطات سیستم با دنیای بی‌نظم بیرون هستند و باعث می‌شوند کامپیوتر هم بی‌نظمی را تجربه کند. حتی قطعات سخت‌افزاری برای تولید رندوم وجود دارند که رندوم واقعی و امن تولید می‌کنند. احتمالا حدس می‌زنید که برای سرورهایی که عملیات رمزنگاری سنگین انجام می‌دهند توجیه اقتصادی دارد.

لینوکس برای استفاده از این آنتروپی، فایل‌های /dev/random و /dev/urandom را معرفی کرده‌است. تفاوت چیست؟

فرض کنید سیستم به اندازه کافی آنتروپی ندارد ولی ما درخواست داده‌ایم که ۱۰ بایت رندوم تولید کند. چه اتفاقی می‌افتد؟ از همین آنتروپی کم استفاده می‌کند و رندوم بی‌کیفیتی می سازد یا صبر می‌کند آنتروپی کافی داشته باشد تا رندوم با کیفیت مطلوب به ما بدهد؟ هردو امکان را داریم. حالت اول (صبر نمی‌کند ولی کیفیت را هم تضمین نمی‌کند) می‌شود فایل /dev/urandom. این به رندوم non blocking هم می‌گویم چون معطل نمی‌شود. حالت دوم که ممکن است مقدار زیادی صبر کند ولی رندوم با کیفیت می‌دهد /dev/random است.

در سروری که امنیت و رمزنگاری مهم‌ باشد قاعدتا باید از /dev/random استفاده شود ولی اگر کیفیت رندوم خیلی برایمان اهمیتی ندارد همان /dev/urandom هم می‌تواند کافی باشد.

جالب است بدانید که یکی از شیوه‌های کند کردن (و حتی از دسترس خارج کردن) سرور خودمان واداشتنش به تولید مقدار زیادی عدد تصادفی است. در این حالت تمام منابع سیستم آزاد هستند ولی چون سیستم آنتروپی کافی ندارد بلاک می‌شود و صبر می‌کند تا آنتروپی تولید شود.