ایجاد توالی تصادفی با یک قانون احتمالی معین و بررسی کفایت آنها از مهمترین مشکلات رمزنگاری مدرن است. ژنراتورهای توالی تصادفی در سیستم های رمزنگاری موجود برای تولید اطلاعات کلیدی و تنظیم تعدادی از پارامترهای سیستم رمزنگاری استفاده می شوند. اهمیت علمی و عملی این مشکل به حدی است که تک نگاری های جداگانه ای در زمینه رمزنگاری به آن اختصاص داده شده است، بخش هایی در مجلات علمی "Journal of Cryptology"، "Cryptologia" و جلسات ویژه در کنفرانس های علمی بین المللی "Eurocrypt" سازماندهی شده است. "، "Asiacrypt"، "Crypto" و غیره.

در آغاز قرن بیستم، توالی‌های تصادفی با استفاده از ساده‌ترین آزمایش‌های تصادفی تقلید شدند: پرتاب یک سکه یا یک تاس، برداشتن توپ از کوزه، چیدن کارت‌ها، رولت، و غیره. در سال 1927، L. Tippet جداولی حاوی بیش از 40000 جدول منتشر کرد. اعداد تصادفی برای اولین بار. "به طور خودسرانه از گزارش های سرشماری استخراج شده است". در سال 1939، M. J. Kendall و B. Babington-Smith با استفاده از یک دستگاه مکانیکی طراحی شده ویژه - یک مولد اعداد تصادفی، جدولی را ایجاد کردند که شامل 10 5 اعداد تصادفی بود. در سال 1946، ریاضیدان آمریکایی جان فون نویمان برای اولین بار یک الگوریتم کامپیوتری برای تولید اعداد تصادفی پیشنهاد کرد. در سال 1955، شرکت RAND جداول بسیار محبوبی را منتشر کرد که حاوی 10 رقم تصادفی کامپیوتری بود.

در حال حاضر تقاضا برای مولدهای توالی های تصادفی با توزیع احتمال داده شده و همچنین برای خود توالی های تصادفی به حدی افزایش یافته است که شرکت های علمی و تولیدی در خارج از کشور ظاهر شده اند که به تولید و فروش آرایه های بزرگ اعداد تصادفی مشغول هستند. به عنوان مثال، از سال 1996 CD-ROM "The Marsaglia random number CDROM" در جهان توزیع شده است که حاوی 4.8 میلیارد بیت "تصادفی واقعی" است.

اکثریت قریب به اتفاق سیستم‌های رمزنگاری مدرن از الگوریتم‌های جریان یا بلوک مبتنی بر انواع مختلف رمزهای جایگزین و جایگشت استفاده می‌کنند. متأسفانه تقریباً همه الگوریتم‌های مورد استفاده در سیستم‌های رمزنگاری جریانی برای استفاده در سیستم‌های ارتباطی نظامی و دولتی و همچنین در برخی موارد برای محافظت از اطلاعات تجاری در نظر گرفته شده‌اند که کاملاً طبیعی است که آنها را مخفی و غیرقابل دسترسی برای بررسی می‌کند. تنها الگوریتم‌های استاندارد برای رمزگذاری متقارن جریان، استاندارد DES آمریکایی (حالت‌های CFB و OFB) و استاندارد روسی GOST 28147-89 (حالت گاما) هستند.

اساس عملکرد سیستم های رمزنگاری جریانی، مولد توالی های تصادفی یا شبه تصادفی است. بیایید این سوال را با جزئیات بیشتری در نظر بگیریم.

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

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

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

مولد اعداد شبه تصادفی(PRNG، انگلیسی شبه تصادفی مولد اعداد، PRNG) الگوریتمی است که دنباله ای از اعداد را تولید می کند که عناصر آن تقریباً مستقل از یکدیگر هستند و از توزیع معین (معمولاً یکنواخت) تبعیت می کنند.

امکان فرموله کردن سه شرط اساسی وجود دارد که مولدهای رمزنگاری قوی دنباله‌های تصادفی شبه یا گاما باید برآورده شوند.

1. دوره گاما باید به اندازه کافی بزرگ باشد تا پیام هایی با طول های مختلف رمزگذاری شود.

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

3. تولید گاما نباید با مشکلات فنی و سازمانی بزرگ همراه باشد.

مهمترین ویژگی یک مولد اعداد شبه تصادفی طول اطلاعات دوره آن است که پس از آن اعداد یا به سادگی تکرار می شوند یا قابل پیش بینی هستند. این طول عملاً تعداد ممکن کلیدهای سیستم رمزنگاری را تعیین می کند. هر چه این طول بیشتر باشد، برداشتن کلید دشوارتر می شود.

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

و در نهایت، شرط سوم باید امکان اجرای عملی مولدهای توالی شبه تصادفی را با در نظر گرفتن سرعت مورد نیاز و سهولت استفاده عملی تضمین کند. اکنون چند روش عملی برای بدست آوردن اعداد شبه تصادفی را در نظر می گیریم.

3 روش برای بدست آوردن اعداد شبه تصادفی

یکی از اولین این روشها روشی بود که در سال 1946 توسط D. von Neumann پیشنهاد شد. این روش بر این اساس استوار بود که هر عدد بعدی در یک دنباله شبه تصادفی با مربع کردن عدد قبلی و کنار گذاشتن ارقام از دو انتها تشکیل می‌شد. با این حال، این روش غیرقابل اعتماد بود و به سرعت کنار گذاشته شد. روش دیگر روش به اصطلاح متجانس است.

3.1 روش همخوانی خطی

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

این الگوریتم شامل کاربرد تکراری فرمول زیر است:

که در آن a>0، c>0، m>0 برخی از ثابت های عدد صحیح هستند. دنباله حاصل به انتخاب شماره شروع بستگی دارد x0و برای مقادیر مختلف آن، دنباله های متفاوتی از اعداد تصادفی به دست می آید. در همان زمان، بسیاری از خواص دنباله Xjبا انتخاب ضرایب در فرمول تعیین می شوند و به انتخاب شماره شروع بستگی ندارند. واضح است که دنباله اعداد تولید شده توسط چنین الگوریتمی تناوبی است و دوره ای از آن تجاوز نمی کند. متر. در این مورد، طول دوره است متراگر و تنها اگر:

gcd (c, m) = 1 (یعنی c و m coprime هستند).

· a - 1 مضرب p برای همه p - مقسوم علیه های m است.

a - 1 مضرب 4 است اگر m مضرب 4 باشد.

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

جدول زیر متداول ترین پارامترهای مورد استفاده مولدهای همخوانی خطی، به ویژه، در کتابخانه های استاندارد کامپایلرهای مختلف (تابع rand) را نشان می دهد.

3.2 روش فیبوناچی

دسته جالبی از مولدهای توالی شبه تصادفی مبتنی بر استفاده از دنباله های فیبوناچی است. یک مثال کلاسیک از چنین دنباله ای (0،1،1،2،3،5،8،13،21،34 ...) - به استثنای دو جمله اول آن، هر جمله بعدی برابر است با مجموع دو قبلی

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

در این راستا، الگوریتم همخوانی خطی به تدریج محبوبیت خود را از دست داد و جای آن را خانواده الگوریتم های فیبوناچی اشغال کردند که می توان آن را برای استفاده در الگوریتم هایی که برای کیفیت اعداد تصادفی حیاتی هستند، توصیه کرد. در ادبیات انگلیسی، سنسورهای فیبوناچی از این نوع معمولاً "Subtract-with-borrow Generators" (SWBG) نامیده می شوند.

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

یکی از گیج های فیبوناچی پرکاربرد بر اساس فرمول تکراری زیر است:

جایی که ایکس k - اعداد واقعی از محدوده )