امیر‌حسین
امیر‌حسین
خواندن ۵ دقیقه·۵ سال پیش

چالش تولید اعداد تصادفی در کامپیوتر

اگر حوصله خوندن ندارید، خلاصه ای که در آخر اومده رو بخونید.

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

مثل این!
مثل این!

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

مثل همین قضیه کلید رمزنگاری، جاهایی هست که کامپیوتر ها باید از اعداد تصادفی استفاده کنن. اما برای این کار، اول باید این عدد رو تولید کنن! این کار به نظر ساده میاد. ولی اگر دقت کنیم، می‌بینیم که مشکلی وجود داره. اساساً کاری که کامپیوتر ها انجام می‌دن، انجام یه سری دستورات از پیش تعیین شده (الگوریتم) هست. به ازای یه ورودی ثابت و یه الگوریتم ثابت، یه خروجی ثابت وجود داره؛ و اگر اون ورودی رو هزار میلیارد بار به اون الگوریتم بدیم، در هر هزار میلیارد بار خروجی یکسانی می‌بینیم. پس خروجی یه الگوریتم به ازای یه ورودی خاص، چیزی قابل پیش‌بینی هست. نتیجه می‌شه که خروجی هیچ الگوریتیمی تصادفی نیست؛ پس خروجی کاری که کامپیوتر انجام می‌ده هم تصادفی نیست. پس کامپیوتر نمی‌تونه عدد تصادفی تولید کنه!

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




مولد اعداد شبه تصادفی (PRNG)

درواقع در خیلی از مواقع، همین که یه دنباله عدد بسازیم که تصادفی به نظر بیاد، حتی اگر واقعا تصادفی نباشه، کار ما رو راه می‌اندازه. مثل:

به نظر تصادفی میان. ولی در واقع نظم پنهانی دارن!

  • عدد ۷۵۳۱ رو بردارید.
  • به توان ۲ برسونید. (=۵۶۷۱۵۹۶۱)
  • چهار رقم وسط حاصل رو بردارید. (=۷۱۵۹)

و اینم عدد بعدی! حالا اگر این کار ها رو با ۷۱۵۹ انجام بدید، به ۲۵۱۲ می‌رسید! همینطور به ۳۱۰۱، ۶۱۶۲ و ...

همونطور که می‌بینید، این اعداد کاملا دارای الگو هستن، در حالی که ظاهرا نیستن! این اعداد رو می‌شه با الگوریتم در کامپیوتر ساخت. به چنین الگوریتم هایی میگن "مولد اعداد شبه تصادفی" یا PRNG (Pseudo Random Number Generator). خروجی چنین الگوریتم هایی در نهایت قاعده دارن و قابل پیش‌بینی هستن. ولی در ظاهر شبه تصادفی هستن.

نکته جالب در مورد این الگوریتم ها اینه که بعد از یه مدت، خروجی‌ها‌شون هی تکرار می‌شه! مثلا تو همین مثال بالا اگر الگوریتم رو ۱۰۰ بار اجرا کنیم، به این عددا می‌رسیم:

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

الگوریتمی که تو دو تا مثال بالا استفاده کردیم، از اولین الگوریتم های PRNG هست و اسمش هم هست "میان-مربع" (Middle-square). به دلایل واضحی، این الگوریتم منسوخ شده و دیگه ازش استفاده نمی‌شه.

مولد اعداد تصادفی واقعی (TRNG)

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

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

نکته کوچولو: در لینوکس در فایل dev/random/ می‌تونید بایت های واقعا تصادفی که به این روش تولید شدن رو ببینید.

خروجی dev/random/ که به شکل کاراکتر های تصادفی و عجیب غریب دیده می‌شه. در عمل سرعت تولید این بایت ها خیلی کمتر از چیزی که اینجا دیده می‌شه هست.
خروجی dev/random/ که به شکل کاراکتر های تصادفی و عجیب غریب دیده می‌شه. در عمل سرعت تولید این بایت ها خیلی کمتر از چیزی که اینجا دیده می‌شه هست.


در سایت Random.org می‌تونید اعداد تصادفی واقعی تولید کنید. طبق گفته این سایت، از "نویز جوی" به عنوان یه پدیده فیزیکی تصادفی برای تولید اعداد تصادفی استفاده می‌شه:

RANDOM.ORG uses radio receivers to pick up atmospheric noise, which is then used to generate random numbers.
سایت RANDOM.ORG از گیرنده های رادیویی استفاده می‌کند تا نویز جوی را دریافت کند، که بعدا برای تولید اعداد تصادفی استفاده می‌شود.



خلاصه

پدیده های تصادفی، پدیده‌هایی هستن که نظم و الگوی خاصی ندارن. اعداد تصادفی هم نمونه ای از اون‌ها هستن. ما در خیلی از شرایط به اعداد تصادفی نیاز داریم. مثلا در اینترنت برای انتقال اطلاعات به صورت رمزنگاری شده، نیاز به اعداد تصادفی داریم تا از لو رفتن کلید استفاده شده برای رمزنگاری جلوگیری کنیم. کامپیوترها اساساً نمی‌تونن اعداد تصادفی تولید کنن. چون کامپیوتر ها الگوریتم اجرا می‌کنن؛ و خروجی هر الگوریتمی یه چیز کاملا قابل پیش‌بینی هست. در نتیجه، تولید اعداد تصادفی یه چالش به حساب میاد. یه راه برای دور زدن این چالش، استفاده از الگوریتم‌هایی هست که اعدادی تولید می‌کنن که تصادفی نیستن، اما در ظاهر تصادفی به نظر میان. به چنین الگوریتم هایی "مولد اعداد شبه تصادفی" یا PRNG گفته می‌شه. هرچند برای کاربرد های ساده، این الگوریتم ها جواب می‌دن، اما برای کاربرد های حساس‌تر مثل تولید کلید برای رمزنگاری، که در اون لو نرفتن کلید خیلی مهمه، استفاده از PRNG ها خوب نیست و ما مجبوریم اعداد تصادفی واقعی تولید کنیم. برای تولید اعداد تصادفی واقعی، می‌تونیم پدیده‌های فیزیکی قابل اندازه‌گیری که تصادفی هستن رو اندازه بگیریم و اعداد به دست اومده از اندازه‌گیری ها رو تصادفی در نظر بگیریم.

تصادفیکامپیوترrandomlinuxentropy
دانشجوی مهندسی کامپیوتر در دانشگاه شهید بهشتی
شاید از این پست‌ها خوشتان بیاید