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

مولّد اعداد شبه تصادفی (انگلیسی: Pseudorandom number generator)، که به مولد قطعی (deterministic) اعداد شبه تصادفی نیز، معروف است [۱]، الگوریتمی است که دنباله‌ای از اعداد را که با تقریب خوبی تصادفی هستند، تولید می‌کند. در واقع دنبالهٔ تولیدشده، واقعاً تصادفی نیست، بلکه به‌طور کامل قابل پیش‌بینی، و از روی حالت اولیهٔ الگوریتم، قابل محاسبه‌ است.

مولدهای اعداد تصادفی، مهم و کاربردی هستند. علت کاربرد گستردهٔ آن‌ها، توانایی تولید دوبارهٔ اعداد تولیدشدۀ قبلی و سرعت بالای تولید است. برای همین، از این الگوریتم‌ها در شبیه‌سازی‌ها (مثلاً روش مونت‌کارلورمزنگاری، و بازی‌های کامپیوتری بسیار استفاده می‌شود. بیشتر الگوریتم‌های رمزنگاری نیاز دارند که خروجی‌شان غیرقابل پیش‌بینی باشد و این امر جز با استفاده از اعداد شبه تصادفی، میسر نمی‌شود.

در حالت کلی، بررسی‌های دقیق ریاضی لازم است تا تضمین شود که الگوریتمی، اعدادی تولید می‌کند که تا حد معقولی تصادفی هستند. جان فُون نُویمان به سوءبرداشت از الگوریتم‌های تولیدکنندهٔ اعداد تصادفی، اشاره کرده‌است و هشدار داده که همواره باید به تفاوت آن‌ها توجه کرد.[۲]

مشکلات بالقوه با مولد های قطعیویرایش

تجربه نشان می‌دهد خروجی‌های تولیدشده، به علت خطاهای موجود، راضی‌کننده نیستند و تعداد کمی از تست‌های آماری را به خوبی می‌گذرانند. می‌توان به تعدادی از این نقص‌ها، اشاره کرد؛

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

مولد های اعداد شبه تصادفی نقص های زیادی داشتند از نقص هایی که زیاد قابل توجه نبود گرفته تا نقص های بسیار آشکار. برای مثال RANDU که یک الگوریتم تولید اعداد تصادفی است ده ها برای رایانه هایmainframe استفاده میشد. این الگوریتم نقص های فراوانی داشت، با این وجود برای مدت بسیاری طولانی این نقص ها کشف نشدند.

در بسیار از زمینه ها، تحقیقاتی قبل از قرن بیست و یکم صورت گرفت که در آنها به انتخاب تصادفی یا شبیه سازی مونت کارلو متکلی بوده اند و یا به روش های دیگر وابسته به PRNG ها بودند. در این موارد اطمینان بسیار کمتر از حالتی است که از PRNG (مولد های اعداد شبه تصادفی)های بی کیفیت استفاده شود.[۳] حتی امروزه، برای احتیاط لازم است، هشداری که در زیر نشان داده شده است که در دایره المعارف بین المللی علوم آماری 2010 آمده است را نیز جدی گرفت.[۴]


مواردی از مولد هایی که باید بلااستفاده شوند و دور ریخته شوند بسیار بیشتر از مولد هایی های خوب است.بنابراین به فروشندگان نرام افزار بدون آگاهی اعتماد نکنید. RNG پیش فرض نرم افزار مورد علاقه ی تان را بررسی کنید. همچنین در صورت نیاز برای تعویض آن آماده باشید. این توصیه بارها طی 40 سال اخیر صورت گرفته است. امروز به طور شگفت آوری همان اندازه مرتبط و لازم است.

برای درک بهتر، زبان های برنامه نویسی را که به طور گسترده استفاده میشود را درنظر بگیرید. از سال 2017، جاوا هنوز برای تولید اعداد تصادفی، به یک مولد خطی سازگار (LCG)که کیفیت پایینی دارد، متکی است.[۵] [۶]

یکی از مولد های اعداد شبه تصادفی شناخته شده برای جلوگیری از بروز مشکلات بنیادی و همچین داشتن قابلیت اجرای نسبتا سریع، مرسن توئیستر (در ادامه مورد بحث است) بود که در سال 1998 منتشر شد. سایر مولد های تولید اعداد شبه تصادفی که کیفیت بالاتری در جهات محاسبات و کارایی آماری داشتند، قبل و بعد از این تاریخ توسعه یافتند. این موارد را لیست مولد های اعداد شبه تصادفی یافت.

مولد برمبنای بازگشتی های خطیویرایش

در نیمه ی دوم قرن بیستم، الگوریتم های کلاس استانداری که برای PRNG ها استفاده میشد، مولدهای سازگار خطی را تشکیل می داد.کیفیت LCG ها کافی نبود اما روش های بهتری نیز وجود نداشت.Press et al در سال 2007  نتایج را اینگونه توصیف میکند:"اگر تمامی مقالات عملی ای که به علت LCG ها و موارد مرتبط در شک و شبه هستند، ناپدید شوند، در هر قفسه ی کتابخانه ها شکاف های بزرگی به‌وجود خواهد آمد."[۷]

هنگامی پیشرفت اصلی در ساخت مولد های اعداد شبه تصادفی به‌وجود آمد که تکنیک های مبتنی بر بازگشت خطی پدیدآمدند. چنین ژنراتورها مربوط به رجیسترهای تغییر فیدبک خطی هستند .

هنگامی پیشرفت اصلی در ساخت مولد های اعداد شبه تصادفی به‌وجود آمد که تکنیک های مبتنی بر بازگشت خطی پدیدآمدند. آنها مولد هایی هستند که دارای ثبات(رجیستر) های تغییر بازخورد خطی اند.

به طور ویژه اختراع مرسن چرخان ، [۸] در سال 1997، از بسیار از مشکلات مولد های پیشین جلوگیری کرد. مرسن چرخان دوره ای از    تکرار (≈4.3×106001)را دارد که ثابت شده است در 623 بعد (برای اعدا 32 بیتی) توزیع شده است. در آن زمان این شیوه از سایر مولد های آماری سریع تر بود.

در سال 2003، جورج Marsaglia خانواده ی مولد های xorshift را که مجددا بر اساس بازگشت خطی بود معرفی کرد. [۹] چنین مولدهایی بسیار سریع هستند و به همراه عملیات های غیرخطی آزمایش های آماری قوی و سختی را پشت سر گذاشتند. [۱۰] [۱۱] [۱۲]

در سال 2006 خانواده ی مولدهای WELL توسعه یافتند. [۱۳] مولد های خانواده ی well کیفیت مرسن توئیستر را در برخی جنبه ها بهبود دادند. Mersenne Twister دارای فضای حالتی بسیار بزرگ و سرعت بازیابی کمی بود که این بازیابی کند در فضاهای حالتی که تعداد زیادی صفر داشتند رخ میداد.

مولدهای شماره شبه تصادفی با رمزنگاری ایمنویرایش

PRNG مناسب برای کاربردهای رمزنگاری ، یک PRNG با رمزنگاری ایمن (CSPRNG) نامیده میشود. یک الزام برای CSPRNG این است که طرفی که seed را نداند، تنها شانس بسیار ناچیزی برای تشخیص و تمایز توالی خروجی مولد از یک دنباله تصادفی دارد. به عبارت دیگر ، در حالی که یک PRNG فقط باید آزمون های آماری را پشت سر بگذارد ، یک CSPRNG باید تمام آزمون های آماری محدود شده به زمان چند جمله ای را در اندازه seed را بگذراند. گرچه اثبات این خاصیت فراتر از توانایی فعلی نظریه پیچیدگی محاسباتی است ، اما ممکن است با کاهش CSPRNG به مسئله ای که فرض بر آن است که از لحاظ محاسباتی سخت است ، مانند فاکتورسازی عدد صحیح ، شواهد محکمی بدست آید. [۱۴] به طور کلی ، ممکن سالها بررسی برای اینکه یک الگوریتم به عنوان CSPRNG تأیید شود، مورد نیاز باشد.

برخی از کلاس های CSPRNG شامل موارد زیر است:

  • رمزهای دنباله ای
  • رمزگذارهای قالبی که در مدهای کاری رمزهای قطعه‌ای [۱۵] یا در حالت بازخورد خروجی عمل میکنند.
  • PRNG هایی که به‌طور خاص برای ایمن سازی رمزنگاری طراحی شده اند ، مانند تابع رابط برنامه نویسی برنامه نویسی کاربرد رمزنگاری مایکروسافت CryptGenRandom ، الگوریتم Yarrow (در سیستم عامل Mac X X و FreeBSD ) و Fortuna
  • ترکیبی از PRNG که سعی در ترکیب چندین الگوریتم PRNG اولیه برای از بین بردن هرگونه عدم تصادف قابل تشخیص دارند.
  • طرح های ویژه مبتنی بر فرضیات سختی ریاضی: نمونه ها شامل مولد Micali-Schnorr ، [۱۶] عملکرد شبه تصادفی Naor-Reingold و الگوریتم Blum Blum Shub ، که یک اثبات امنیتی قوی را ارائه می دهند (چنین الگوریتم هایی نسبت به سازه های سنتی برای بسیاری از کاربرد ها نسبتاً کند و غیر عملی هستند.)
  • PRNG های عمومی: در حالی که نشان داده شده است که یک PRNG ایمن (رمزنگاری شده) می تواند به‌طور کلی از هر تابع یک طرفه ساخته شود ، [۱۷] این ساختار عمومی در عمل بسیار کند است ، بنابراین عمدتاً مورد توجه در موارد تئوری است.

نشان داده شده است که به احتمال زیاد آژانس امنیت ملی آمریکا یک درپشتی نامتقارن به NIST قرار داده بود. NIST مولد اعداد شبه تصادفی Dual_EC_DRBG را گواهی میکند. [۱۸]

اکثر الگوریتم های PRNG توالی هایی تولید می کنند که به طور یکنواخت توسط آزمون های گوناگون توزیع میشوند. این یک سؤال بدون پاسخ است ، و یک موضوع اصلی برای تئوری و عمل رمزنگاری است که آیا راهی برای تمایز خروجی یک PRNG با کیفیت بالا از یک دنباله واقعاً تصادفی وجود دارد؟ در این تنظیم ، تشخیص دهنده می داند که یا از الگوریتم شناخته شده PRNG استفاده شده است (اما نه وضعیتی که با آن آغاز شد) یا از یک الگوریتم واقعاً تصادفی استفاده شده است ، و باید بین این دو تفاوت قایل شود. [۱۹] امنیت اکثر الگوریتم های رمزنگاری و پروتکل های با استفاده از PRNG برفرض آن بناشده اند که تشخیص استفاده از PRNG مناسب از استفاده از یک توالی واقعاً غیرممکن است. ساده ترین نمونه های این وابستگی ، رمزنگاری های جریانی هستند ، که (اغلب) با یای انحصاری بین متن ساده (رمزنشده) پیام و خروجی PRNG کار می کنند و متن رمزشده را تولید می کنند. طراحی PRNG های مناسب از نظر رمزنگاری بسیار دشوار است زیرا آنها باید معیارهای بیشتری را رعایت کنند. اندازه دوره ی تناوب آنها یک عامل مهم تعیین میزان مناسب بودن رمزنگاری یک PRNG است ، اما به تنهایی کافی نیست.

معیارهای ارزیابی BSIویرایش

دفتر امنیت اطلاعات فدرال آلمان ( Bundesamt für Sicherheit in der Informationstechnik ، BSI) چهار معیار برای ارزیابی کیفیت مولد های اعداد تصادفی قطعی تعیین کرده است. [۲۰] این موارد به صورت زیر خلاصه می شوند:

  • K1 - احتمال متفاوت بودن اعداد متوالی تولید شده از یکدیگر، زیاد است.
  • K2 -اعداد متوالی تولید شده طبق آزمون های مخصوص آماری، از اعداد " واقعا تصادفی " قابل تشخیص نیست. این آزمون ها عبارتند از آزمون monobit (تعداد مساوی صفرها و یک ها در یک توالی)، آزمون poker (نمونه ی خاص آزمون chi-square )، آزمون runs (تعداد دفعات اجرا در طول های متفاوت را محاسبه می کند) ، آزمون Longruns (ارزیابی اینکه در 20000 بیت متوالی آیا بیشتر یا مساوی 34 run به‌وجود آمده است یا خیر)- از BSI [۲۰] و NIST ، آزمون autocorrelation (آزمون همبستگی). در اصل این نیازمندی ها جهت ارزیابی کیفیت دنباله ی بیت ها هستند: آیا تعداد صفرها و یک ها اکثرا مساوی است؟ بعد از دنباله ای از صفرهای متوالی(یا یک های متوالی) بیت یک بعدی (یا صفر بعدی) با احتمال 0.5 ظاهر میشود؟ آیا هر زیرمجموعه ی انتخاب شده از بیت ها اطلاعاتی درباره ی بیت یا بیت های بعدی میدهند؟
  • K3 - برای مهاجمان در حالت واقعی و عملی، غیرممکن باشد که از هر زیرمجموعه از بیت ها هرگونه اطلاعی از مقادیر قبلی یا بعدی را محاسبه کند یا اینکه حالت فعلی مولد را تعیین کند.
  • K4 - برای هر منظور و هدف عملی غیر ممکن باشد که مهاجم بتواند از حالت درونی مولد هرعدد قبلی در دنباله ی اعداد تولید شده یا حالت قبلی مولد را محاسبه کند یا حدس بزند.

برای کاربرد های رمزنگاری، فقط مولد هایی که موارد K3 و K4 را رعایت کنند، قابل قبول میباشند.

تعریف ریاضیویرایش

داده شده (در صورتی که)

  •   - توزیع احتمال   (جایی که   مجموعه استاندارد Borel بر روی خط واقعی است)
  •   - مجموعه ای غیر تهی از مجموعه های بورل   ، به عنوان مثال   . اگر   مشخص نشده است ، ممکن است یا   باشد یا   که بسته به متن تعیین میشود.
  •   - یک مجموعه غیر تهی (لزوماً یک مجموعه Borel). غالبا  یک مجموعه بین تکیه گاه  و درون (توپولوژی) آن؛ به عنوان مثال ، اگر   توزیع یکنواخت در فاصله   باشد،   میتواند   باشد . اگر   مشخص نشده باشد، فرض بر این است که مجموعه ای است که همه ی اعضایش در تکیه گاه  موجود اند و شامل توپولوژی اش میباشد.

ما یک تابع   (جایی که   مجموعه اعداد صحیح مثبت است) را یک مولد عدد شبه تصادفی برای   به طوری که   مقادیر   را میگیرد مینامیم اگر و تنها اگر

  •  
  •  

(   نشان دهنده تعداد اعضای مجموعه متناهی S است. )

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

رویکردهای اولیهویرایش

یکی از روش‌های اولیهٔ مبتنی بر کامپیوتر، به وسیلهٔ فُون نویمان در سال ۱۹۴۶ ارائه شد. این روش به روش «میان-مربع» (Middle-Square) معروف است («میانِ مربع» یا «مربعِ میانی» خوانده نشود)؛ یک عدد دلخواه در نظر گرفته، آن را به توان ۲ برسانید (مربع کنید)، ۴ رقم میانی آن را به عنوان یک عدد تصادفی جدید در نظر بگیرید و آن‌ را به‌عنوان عدد بعدی در الگوریتم استفاده کنید و به این کار ادامه دهید.

مثلاً با شروع از عدد ۱۱۱۱، عدد ۱۲۳۴۳۲۱ حاصل می‌شود، که اگر آن را به صورت هشت رقمی بنویسیم، ۰۱۲۳۴۳۲۱ به دست می‌آید. عدد ۲۳۴۳ به عنوان یک عدد تصادفی به دست می‌آید. با تکرار این عمل روی ۲۳۴۳ به ۴۸۹۶ به عنوان عدد تصادفی بعدی خواهیم رسید. می‌توان همین روند را ادامه داد. اگر در روش اصلی از اعداد ۵ رقمی استفاده می‌شد، روند کاملاً مشابه می‌بود.

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

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

از آن زمان ، روش مربع میانی توسط مولدهای دقیق تر تعویض شد.

یک نوآوری تازه ترکیب مربع میانه با دنباله Weyl میباشد . این روش در مدت زمان طولانی تولید خروجی به کیفیت بالا دست میابد (رجوع کنید به توالی PRNG دنباله میدانی Weyl ).

مولد های غیر یکنواختویرایش

تعداد انتخاب شده از توزیع احتمال غیر یکنواخت را می توان با استفاده از یک توزیع PRNG یکنواخت و تابعی که مربوط به این دو توزیع باشد ، تولید کرد.

اعداد انتخاب شده از یک توزیع احتمالاتی غیریکنواخت میتواند توسط یک توزیع یکنواخت PRNG و یک تابع که دو توزیع را به هم مرتبط کند، تولید شود.

ابتدا به تایع توزیع تجمعی نیاز داریم   توزیع هدف   (تابع F توزیع تجمعی f است):

 

توجه داشته باشید که   . با استفاده از عدد تصادفی c که از توزیع یکنواخت آمده است ،به عنوان چگالی احتمال، دریافت می کنیم:

 

در نتیجه

 

عددی است که به طور تصادفی از توزیع   انتخاب شده است .

به طور مثال، وارونه توزیع گاوی تجمعی   با یک PRNG یکنواخت ایده آل با دامنه (0 ، 1) که ورودی   توالی از مقادیر (فقط مثبت) با توزیع گاوسی را تولید می کند. با این حال

  • زمانی که از نمایش عدد عملی استفاده میکنیم، "دم" های نامتناهی توزیع باید به مقادیر محدود قطع شوند.
  • محاسبه تکراری   باید از طریق الگوریتم زیگورات صورت بگیرد تا تولید اعداد سریع تر شود.

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

همچنین ببینیدویرایش

منابعویرایش

  1. Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.
  2. "Pseudorandom number generators". Khan Academy. Retrieved 2016-01-11.
  3. Press et al. (2007), chap.7
  4. L'Ecuyer, Pierre (2010). "Uniform random number generators". In Lovric, Miodrag. International Encyclopedia of Statistical Science. Springer. p. 1629. ISBN 3-642-04897-8.
  5. Random (Java Platform SE 8), Java Platform Standard Edition 8 Documentation.
  6. Random.java at OpenJDK.
  7. Press et  al. (2007) §7.1
  8. Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3–30. doi:10.1145/272991.272995.
  9. Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14).
  10. S.Vigna. "xorshift*/xorshift+ generators and the PRNG shootout".
  11. Vigna S. (2016), "An experimental exploration of Marsaglia’s xorshift generators", ACM Transactions on Mathematical Software, 42; doi:10.1145/2845077.
  12. Vigna S. (2017), "Further scramblings of Marsaglia’s xorshift generators", Journal of Computational and Applied Mathematics, 315; doi:10.1016/j.cam.2016.11.006.
  13. Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. doi:10.1145/1132973.1132974.
  14. Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. p. 73. ISBN 978-0-387-48741-0.
  15. Niels Ferguson, Bruce Schneier, Tadayoshi Kohno (2010). "Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator" (PDF).
  16. Klaus Pommerening (2016). "IV.4 Perfect Random Generators". Cryptology. uni-mainz.de. Retrieved 2017-11-12. The MICALI-SCHNORR generator
  17. Pass, Rafael. "Lecture 11: The Goldreich-Levin Theorem" (PDF). COM S 687 Introduction to Cryptography. Retrieved 20 July 2016.
  18. Matthew Green. "The Many Flaws of Dual_EC_DRBG".
  19. Katz, Jonathan; Yehuda, Lindell (2014). Introduction to modern cryptography. CRC press. p. 70.
  20. ۲۰٫۰ ۲۰٫۱ Schindler, Werner (2 December 1999). "Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators" (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. pp. 5–11. Retrieved 19 August 2013.

کتابشناسی - فهرست کتبویرایش

لینک های خارجیویرایش