https://virgool.ir/feed/@fadingintomoonfa2026-11-12 22:37:11https://virgool.ir/images/default-avatar.jpghttps://virgool.ir/@fadingintomoonhttps://virgool.ir/@fadingintomoon/اعداد-شبه-تصادفی-در-رمزنگاری-الگوریتم-ها-آزمون-ها-و-مولد-اعداد-s3x1jbu7ynm9مقدمهچگونه می‌توان دنباله‌ای یکنواخت از اعداد تصادفی تولید کرد؟ تصادفی بودن هیچ‌گاه به آن صورت که در طبیعت مشاهده می‌شود برای انسان قابل دستیابی نبوده است. قدیمی‌ترین تاس شناخته شده در معبدی متعلق به قرن بیست و چهارم پیش از میلاد در خاورمیانه کشف شده است. موردی از آن جدیدتر مربوط به سال ۱۱۰۰ پیش از میلاد در چین می باشد که پوسته لاک پشت را با استفاده از ابزاری حرارت می دادند تا از یک نقطه تصادفی ترک بردارد و سپس یک پیشگو شروع به تعبیر ترک‌های تصادفی می‌کرده است.تصویر ۱ - تاس های اولیهاما در میانه دهه ۴۰ میلادی جهان مدرن به تعداد بسیار بیشتری از اعداد تصادفی نیاز داشت که قابل استخراج از یک تاس یا ابزار مشابه نبودند. شرکت هایی مانند RAND و Intel و دانشمندانی مانند الن تورینگ، روش‌ها و ماشین‌های گوناگونی برای تولید اعداد تصادفی معرفی کردند که در بخش تاریخچه به آنها پرداخته خواهد شد. امروزه نیز اعداد تصادقی نقش مهمی در استفاده از رمزگذاری برای تامین امنیت دیجیتال دارند.در مواقع زیادی در رمزنگاری، تولید اعداد یا رشته های بیتی تصادفی اهمیت بسیاری دارد. به عنوان مثال کلیدهای مورد استفاده در رمزنگاری معمولا اعدادی هستند که به صورت تصادفی از یک فضای مشخص و از پیش تعریف شده به دست آمده اند. تولید اعداد تصادفی با استفاده از تاس یا سایر فرآیندهای فیزیکی، زمان گیر و هزینه بر است. از این رو ،در عمل از مولدهای اعداد شبه تصادفی استفاده می شود.در متن پیش رو به معرفی کاربرد اعداد تصادفی در رمزنگاری، با تمرکز بر تولید اعداد شبه تصادفی خواهیم پرداخت.تاریخچهدر دهه ۴۰ میلادی شرکت RAND موفق به ساخت ماشینی شد که قادر به تولید اعداد با استفاده از یک مولد پالس تصادفی بود. برای نخستین بار یک دنباله طولانی از اعداد تصادفی در اختیار افرادی قرار گرفت که به آن نیاز داشتند. افرادی مانند محققین و دانشمندان.در سال ۱۹۵۱، پدیده تصادفی بودن توسط رایانه Ferranti Mark 1 رسمیت یافت. این رایانه با استفاده از دستورالعملی که الن تورینگ آن را طراحی کرده بود و با بهره گیری از اختلال الکتریکی قادر به تولید ۲۰ بیت تصادفی در هر زمان بود. اما این دستورالعمل چندان هم مورد پسند برنامه نویسان زمان خود قرار نگرفت. چراٰکه در فضایی که خود غیر قابل پیش بینی بود، عدم قطعیت بسیاری به وجود می آورد.تصویر ۲ - الن تورینگ و همکارانش در حال کار با رایانه Ferranti Mark 1اندیشه استفاده از مولدهای اعداد شبه تصادفی مسیر ممکنی را فراهم کرد. یک مولد اعداد شبه تصادفی نوعی مولد اعداد تصادفی است که از آن به عنوان یک تابع ریاضی قطعی یاد می‌شود. اولین مولد اعداد شبه تصادفی در حدود سال ۱۹۴۶ میلادی توسط جان فون نویمان توسعه یافت. ایده نویمان به این صورت بود که مولد یک عدد تصادفی اولیه را به توان ۲ برساند و ارقام میانی حاصل را برگزیند. اگر فرآیند یاد شده به طور مرتب برای ارقام میانی گزینش شده انجام شود، در نهایت به دنباله ای از اعداد با ویژگی های آماری تصادفی خواهیم رسید. الگوریتم رمزنگاری SSL نیز در سال ۱۹۹۵ معرفی شد و برای رویه رمزنگاری خود به یک مولد اعداد شبه تصادفی با کیفیت نیاز داشت.مطلب اصلیقبل از پرداختن به موضوع تولید اعداد شبه تصادفی، به برخی از کاربردهای اعداد تصادفی دودویی در تامین امنیت دیجیتال از طریق الگوریتم ها و پروتکل های رمزنگاری اشاره می کنیم:توزیع کلید و رویه های احراز هویت متقابل: دو طرف درگیر در یک ارتباط از طریق تبادل پیام برای توزیع کلید یا احراز هویت با هم همکاری می کنند. در موارد بسیاری نیز از nonce ها (عددی تصادفی یا شبه تصادفی که تنها یک دفعه در یک ارتباط میتوان از آن استفاده کرد) پیش از شروع ارتباط برای پیشگیری از حملات سایبری استفاده می شود.تولید رشته ای از بیت ها برای رمزنگاری stream متقارنتولید کلید برای الگوریتم RSAکاربردهای یاد شده منجر به ایجاد ۲ نیازمندی برای هر دنباله ای از اعداد تصادفی شده اند؛ تصادفی و غیر قابل پیش بینی بودن.تصادفی بودن: یکی از دغدغه های اصلی برای تولید دنباله ای از اعداد تصادفی، اطمینان حاصل کردن از این موضوع است که تصادفی بودن اعداد در دنباله، از لحاظ آماری قابل تعریف باشد. ۲ معیار برای این علت معرفی شده اند:توزیع یکنواخت: توزیع اعداد (یا بیت ها) در دنباله باید یکنواخت باشد. به عبارتی فرکانس مشاهده یا رخداد یک بیت باید با سایر بیت ها یکسان باشد.استقلال: هیچ ۲ زیر دنباله ای از دنباله اصلی نباید قابل استنتاج از هم باشند.غیر قابل پیش بینی بودن: در دنباله هایی با اعداد واقعا تصادفی، هر عدد از لحاظ آماری مستقل از سایر اعداد در دنباله و در نتیجه غیر قابل پیش بینی است. با این وجود که در برخی زمینه ها از چنین اعدادی استفاده می شود اما این کار با محدودیت هایی نیز رو به رو می باشد، از جمله عدم بهینگی. از این رو پیاده سازی الگوریتم هایی که دنباله هایی در ظاهر تصادفی تولید می کنند متداول تر است.امروزه در رمزنگاری معمولا از تکنیک های الگوریتمی برای تولید اعداد تصادفی استفاده می شود. الگوریتم هایی قطعی که دنباله هایی تولید می کنند که از لحاظ آماری تصادفی محسوب نمی شوند. آزمون هایی وجود دارند که میزان تصادفی بودن دنباله های تولیدی را طبق معیارهایی می سنجند و اگر الگوریتم تولید دنباله اعداد به قدر کافی خوب طراحی شده باشد، دنباله حاصل آزمون های بسیاری را می گذراند. در این صورت به دنباله ای از اعداد شبه تصادفی رسیده ایم. اندیشه استفاده از اعداد شبه تصادفی به جای اعداد تصادفی می تواند تا حدودی گیج کننده باشد چرا که در تولید اعداد شبه تصادفی از توابعی قطعی استفاده می شود، با این حال در اکثر مواقع اعداد شبه تصادفی عملکردی مشابه با اعداد تصادفی دارند.یک تولید کننده اعداد شبه تصادفی (یا یک PRNG به اختصار) مقدار ثابت اولیه ای که به آن بذر یا seed نیز گفته می شود را به عنوان ورودی می گیرد و با استفاده از یک الگوریتم قطعی دنباله ای از اعداد شبه تصادفی را به عنوان خروجی تولید می کند.تصویر ۳ - تولید کننده اعداد شبه تصادفیبه طور معمول همانطور که در تصویر ۳ نیز مشاهده می شود، یک مسیر بازخورد در PRNG وجود دارد که از طریق آن بخشی از خروجی الگوریتم مجددا به عنوان ورودی به آن داده می شود. یک نکته مهم در مورد این مولد امکان تولید مجدد دنباله توسط یک فرد سودجو و مخرب است. چرا که فرد با داشتن بذر و اطلاع از چگونگی کارکرد الگوریتم می تواند رشته بیتی خروجی را به طور کامل تولید کند.می توان بیان کرد که یکی از نیازمندی های چنین مولدی اطمینان حاصل کردن از این موضوع است که فرد مخرب بدون داشتن بذر، قادر به تولید رشته بیتی خروجی نیست.اکنون به نیازمندی های دیگر این مولد می پردازیم.تصادفی بودن: نیاز است که رشته بیتی خروجی مولد با وجود اینکه خروجی یک تابع قطعی است، تصادفی به نظر برسد. برای این منظور آزمون هایی طراحی شده اند. اگر خروجی مولد آزمون های متعددی را بگذراند، می توان آن را تصادفی تلقی کرد. این آزمون ها باید به دنبال تعیین ۳ ویژگی در رشته خروجی باشند:یکنواختی: در حین تولید رشته، احتمال رخداد هر بیت باید برابر باشد. در نتیجه هر کدام از بیت های ۰ و ۱ باید احتمال ۱/۲ را داشته باشند. پس تعداد هر بیت در رشته خروجی نیز باید برابر با بیت دیگر باشد.مقیاس پذیری:‌ هر آزمونی که بر روی رشته خروجی انجام می شود باید قابل انجام بر روی هر زیر رشته تصادفی از رشته اصلی نیز باشد. اگر رشته خروجی تصادفی باشد، در نتیجه هر زیر رشته ای از آن نیز تصادفی خواهد بود.ثبات: رفتار مولد در ازای ورودی های اولیه متفاوت (بذر) باید یکسان باشد. از طرفی نیز صحیح نیست که تصادفی بودن یا نبودن خروجی مولد را تنها از روی یک حالت ورودی نتیجه گرفت.مورد از آزمون های یاد شده در ادامه معرفی شده اند:آزمون فرکانس: به عنوان پایه ای ترین آزمون شناخته می شود. هدف این آزمون بررسی این موضوع است که آیا تعداد صفر و یک‌های یک رشته همانند آنچه در یک رشته تصادفی رخ می دهد برابر است یا خیر.آزمون ترتیب (runs): تمرکز این آزمون بر روی تعداد run ها در یک رشته است. یک run دنباله ای متوالی از بیت های مشابه است که در بین ۲ بیت متفاوت قرار گرفته اند. هدف این آزمون بررسی این موضوع است که آیا تعداد run ها در رشته با تعداد معمول آنها در یک دنباله تصادفی هم خوانی دارد یا خیر.غیر قابل پیش بینی بودن: یک رشته از اعداد شبه تصادفی باید از ۲ جهت غیر قابل پیش بینی باشد:رو به جلو: در صورت ناشناخته بودن بذر، بیت بعدی در رشته خروجی باید غیر قابل پیش بینی باشد حتی اگر اطلاعی از آخرین بیت خروجی قبل از آن داشته باشیم.رو به عقب: همچنین نباید امکان پی بردن به بذر وجود داشته باشد. حتی در شرایطی که دانشی درباره رشته تولید شده داریم.یکی از تکنیک هایی که به کرات از آن برای تولید اعداد شبه تصادفی استفاده می شود الگوریتمی است به نام مولد همگرای خطی (یا Linear Congruential Generator). دنباله اعداد توسط معادله زیر به دست می آید:طبق این معادله برای محاسبه یک عدد (Xn+1) به عدد قبل از آن (Xn) در دنباله نیاز است. انتخاب مقادیر مناسب برایm، a و c اهمیت بسیاری دارد. ترجیح این است که m بسیار بزرگ باشد تا این تابع دوره تناوب بزرگ تری داشته باشد چرا که در این صورت شانس بیشتری برای تولید اعداد بیشتر داریم و در نتیجه دنباله خروجی می تواند بیشتر باب میل ما باشد. یک معیار به این صورت است که m برابر با بزرگ‌ترین عدد صحیح قابل نمایش توسط رایانه باشد و نتیجتا مقدار این پارامتر معمولا نزدیک به یا برابر با ۲ به توان ۳۱ می باشد.برای الگوریتم یاد شده نیز آزمون هایی طراحی شده اند که میزان صحیح بودن مقادیر انتخابی برای پارامترها را می سنجند. این آزمون ها بیان می کنند که تابع یا مولد باید تمام مقادیر بین ۰ تا ۱ را تولید کند، دنباله تولید شده باید تصادفی به نظر برسد و در آخر مولد باید به صورت بهینه ای در معماری ۳۲ بیتی قابل پیاده سازی باشد. با انتخاب مقادیر مناسب برای این پارامترهای m، a و c، مولد می تواند این آزمون ها را بگذراند. به عنوان مثال مقدار ۱۶۸۰۷ برای a اکثر این آزمون ها را می گذراند.یک فرد مخرب با داشتن اطلاعاتی از قبیل اینکه از این الگوریتم مشخص استفاده شده است (همراه با مقادیر پارامترها) و همچنین داشتن تنها یکی از جملات دنباله، می تواند تمام جملات دیگر را بازسازی کند. در حالتی دیگر حتی با داشتن این دانش که از الگوریتم مورد بحث استفاده شده (بدون دانستن مقادیر پارامترها) و داشتن جمله اول، فرد می تواند از طریق حل ۳ معادله ۳ مجهولی سایر پارامتر ها (m، a و c) را بیابد:در نتیجه با وجود اینکه استفاده از یک PRNG خوب بسیار خوشایند است، اما در حالت مطلوب برای دنباله تولیدی نباید امکان تولید مجدد وجود داشته باشد. به این صورت که یک فرد مخرب با داشتن اطلاعاتی درباره تنها بخشی از دنباله، نتواند جملات دیگر دنباله را نیز بیابد. یک راه میتواند استفاده از یک ساعت باشد که در داخل سیستم تعبیه شده است و از آن برای اصلاح جریان تولید اعداد تصادفی استفاده کرد. به عنوان مثال به این صورت که عدد نمایش داده شده توسط ساعت، مقداری باشد که به هر جمله در یک زمان مشخص اضافه می شود. با این کار عنصری که حقیقتا تصادفی است وارد فرآیند تولید دنباله می شود.بررسی بیشتریک رویکرد رایج و ایمن برای تولید اعداد شبه تصادفی استفاده از الگوریتم Blum Blum Shub Generator (یا مولد BBS به اختصار) است. روش کار الگوریتم به این صورت است: ابتدا ۲ عدد اول را که در تقسیم بر ۴ باقیمانده ای برابر با ۳ دارند را می‌یابیم ( p و q). یا به عبارت دیگر:‌ p =q = 3 (mod 4)سپس عدد دیگری به نام n تعریف میکنیم برابر با حاصل ضرب p در q. در مرحله بعد عدد دیگری به نام s را میابیم به نحوی که s نسب به n اول باشد. سپس دنباله ای از بیت ها طبق الگوریتم زیر تولید می شود:همانطور که در شبه کد بالا مشاهده می شود، در هر تکرار کم ارزش ترین بیت برای اضافه شدن به دنباله انتخاب می شود.از این الگوریتم به عنوان یک مولد شبه تصادفی اعدادی یاد می شود که از لحاظ رمزنگاری ایمن محسوب می شود (یا CSPRBG به اختصار). یک CSPRBG آزمون بیت بعدی (next-bit test) را می گذراند. یک مولد می تواند این آزمون را در صورتی بگذراند که الگوریتمی وجود نداشته باشد که در یک زمان چند جمله ای و با داشتن k بیت اولیه دنباله خروجی، بیت k+1ام دنباله را با احتمالی بزرگتر از ۱/۲ تعیین کند.بررسی چالش ها و جمع بندیدو هدف اصلی برای مولد های اعداد شبه تصادفی تعریف شده است؛ آن ها باید سریع و ایمن باشند. داشتن این ۲ ویژگی در کنار هم می تواند کمی تناقض ایجاد کند. اکثر مولدها در شبیه سازی ها سریع عمل می کنند اما در زمینه رمزنگاری عملکرد ضعیف تری نشان می دهند.یک مولد در صورتی ایمن است که در یک زمان چند جمله ای امکان تشخیص خروجی آن از یک دنباله واقعا تصادفی وجود نداشته باشد که این در صورتی ممکن است که در دنباله خروجی، یکنواختی وجود داشته باشد. به عبارتی زمانی که به تعداد نصف طول رشته بیت ۱ و به همان تعداد نیز بیت ۰ در رشته موجود باشد. در این صورت می توان حدس زد که رشته ای که در دست داریم، دنباله ای از اعداد تصادفی است و نه خروجی یک الگوریتم قطعی.در این متن درباره تولید اعداد شبه تصادفی بحث شد. به مباحثی از جمله تاریخچه ای درباره تلاش انسان برای دستیابی به اعداد تصادفی، مولد اعداد شبه تصادفی، آزمون ها و معیارهایی برای تعیین تصادفی بودن یا نبودن رشته خروجی مولد و ۲ الگوریتم که از جمله معروف ترین تکنیک ها برای تولید دنباله ای از اعداد شبه تصادفی هستند اشاره شد.این مطلب در راستای درس رمزنگاری و امنیت در دانشگاه تحصیلات تکمیلی علوم پایه زنجان نوشته شده است.مراجعاگر به موضوعاتی که مورد بحث قرار گرفتند علاقمند هستید می‌توانید از این دو کتاب کمک بگیرید:Douglas R. Stinson. Cryptography, Theory and Practice. Chapman and Hall/CRC, 2006William Stallings. Cryptography and Network Security: Principles and Practice. Pearson, 2014در صورتی که می‌خواهید اطلاعات بیشتری درمورد تاریخچه تلاش انسان برای دستیابی به اعداد تصادفی به دست بیاورید به این نوشته مراجعه کنید:https://www.freecodecamp.org/news/a-brief-history-of-random-numbers-9498737f5b6c/این لینک نیز توضیحاتی درباره تصویر ۲ دارد:https://blog.sciencemuseum.org.uk/alan-m-turing-and-colleagues-working-on-the-ferranti-mark-i-comp/fadingintomoonfadingintomoonFri, 21 Aug 2020 14:01:43 +0430