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

مولد امن اعداد شبه‌تصادفی نوعی مولد اعداد شبه تصادفی است که حایز شرایط ویژه برای استفاده در کاربردهای رمزنگاری باشد.
در رمزنگاری، اعداد تصادفی در موارد مختلفی استفاده می‌گردند، من جمله در الگوریتم تولید کلید و نیز در رمزهای یکبار مصرف. اما حساسیت هر یک از این کاربردها به ویژگی تصادفی بودن متفاوت است.
به صورت ایدئال، اعداد تصادفی مورد نیاز در رمزنگاری باید از منابع با کیفیت بالا مانند مولد سخت‌افزاری اعداد تصادفی یا سیستم‌های پیش‌بینی ناپذیر تامین گردند. اما در سیستم‌های عملی، امکان تولید اعداد کاملا تصادفی وجود ندارد، چرا که حجم اعداد مورد نیاز بسیار بیشتر از میزان بی‌نظمی است که سیستم قابلیت تامین آن را دارد. همچنین تولید چنین اعدادی بسیار به کندی انجام می‌یابد. در چنین شرایطی مولدهای امن اعداد شبه‌تصادفی مورد استفاده قرار می‌گیرند. مولد امن اعداد شبه‌تصادفی، می‌تواند بی‌نظمی موجود در سیستم را به تعداد بیت‌های بیشتری تسری دهد. به عنوان مثال در الگوریتم تولید کلید که از مهم‌ترین کاربردهای اعداد تصادفی در رمزنگاری است، می‌توان با استفاده از یک مولد امن اعداد شبه‌تصادفی، کلید اولیه را به کلیدی با طول بسیار بیشتر گسترش داد.
ویژگی‌های مورد نیاز
ویژگی‌های مورد نیاز برای یک مولد معمولی اعداد شبه‌تصادفی، توسط مولد امن اعداد شبه‌تصادفی نیز ارضا می‌گردند. اما عکس این مطلب صادق نیست. ویژگی‌های خاص مولد امن شبه‌تصادفی به دو دسته تقسیم می‌گردند. اولا این مولدها باید از آزمون‌های آماری بگذرند و ویژگی‌های آماری مورد نیاز برای اعداد تصادفی تولیدشده را برآورده سازند. ثانیا این مولدها باید در برابر حمله‌های احتمالی به اندازه کافی مقاوم باشند؛ حتی اگر قسمتی از حالت اولیه یا جاری آنها به دست مهاجمی بیفتد که قصد حمله دارد.
هر مولد امن اعداد تصادفی باید از آزمون آزمون بیت بعدی بگذرد. این آزمون رشته‌ای از بیت‌های تصادفی را به عنوان ورودی می‌گیرد. برای موفقیت در آزمون، هیچ الگوریتم با مرتبه زمانی چندجمله‌ای نباید وجود داشته باشد که با احتمال بیش از یک دوم، بیت بعدی بلافاصله پس از رشته را پیش‌بینی کند.
در هر مولد امن اعداد شبه‌تصادفی، چنانچه تمام یا قسمتی از یک حالت مولد فاش گردد یا به درستی حدس زده شود، بازسازی جریان اعداد قبلی نباید امکان‌پذیر باشد. علاوه بر این، چنانچه از یک رشته یا مقدار اولیه در مولد امن اعداد تصادفی استفاده می‌گردد، دسترسی به این رشته یا مقدار اولیه نباید به پیش‌بینی حالات بعدی مولد منتهی شود.
اکثر مولدهای اعداد شبه‌تصادفی قابل استفاده به عنوان مولد امن نیستند. چرا که اولا با وجود اینکه ممکن است در مقابل آزمون‌های آماری کاملا امن به نظر برسند، اما در حقیقت در مقابل تکنیک مهندسی معکوس آسیب‌پذیر هستند و می‌توان آزمون‌های آماری خاصی را یافت که اعداد تولیدشده توسط این مولدها را از اعداد واقعا تصادفی متمایز می‌سازند. ثانیا در اکثر مولدهای اعداد شبه‌تصادفی، هنگامی که حالت جاری مولد فاش می‌گردد، همه بیت‌های قبلی قابل بازسازی خواهند بود و حمله کننده از این طریق خواهد توانست به همه پیام‌های قبلی و بعدی دسترسی پیدا کند.
تاریخچه
وزیرانی و سانتا در سال ۱۹۸۴ میلادی ثابت کردند که می‌توان با استفاده از چند رشته شبه‌تصادفی که ویژگی تصادفی بودن ضعیفی دارند، رشته‌ای شبه‌تصادفی با ویژگی قوی‌تر تصادفی بودن ساخت. پیش از آنها جان فن نیومن نشان داده بود که با استفاده از یک الگوریتم ساده می‌توان کیفیت یک رشته شبه‌تصادفی را به طور قابل ملاحظه‌ای افزایش داد. این الگوریتم می‌تواند پیش از ادغام رشته‌ها به روش سانتا-وزیرانی، روی هر رشته اعمال گردد. این مقوله به
اصلاح بی‌نظمی معروف است و همچنان مورد تحقیق قرار می‌گیرد.
طراحی
در این قسمت مولدهای امن اعداد شبه‌تصادفی را به سه کلاس تقسیم می‌کنیم. دسته اول مولدهایی هستند که بر پایه اصول رمزنگاری همچون الگوریتم‌های رمزگذاری یا تابع درهم سازی طراحی می‌شوند. دسته دوم مولدها با استفاده از نظریه اعداد ساخته می‌شوند. در این مولدها فرض سخت بودن حل برخی از مسائل در نظریه اعداد مورد استفاده قرار می‌گیرد. دسته سوم هم شامل مولدهایی می‌شود که برای هدفی خاص طراحی می‌شوند. در این دسته از مولدها معمولا خروجی به طور قطعی بر حسب حالت اولیه معین نمی‌گردد. ویژگی اخیر این امکان را فراهم می‌آورد تا حتی در صورت انتشار حالت اولیه، مولد در مقابل حملات احتمالی امن باشد.
طراحی بر پایه اصول رمزنگاری
هر رمز بلوکی می‌تواند به عنوان مولد امن اعداد شبه‌تصادفی مورد استفاده قرار گیرد. برای این منظور کافی است تا رمز دنباله‌ای را در مد شمارشی مورد استفاده قرار دهیم. به بدان معنا خواهد بود که با استفاده از رمز دنباله‌ای به ترتیب اعداد صفر، یک، دو و … را رمزگذاری کنیم. مقدار اولیه برای شروع این پروسه می‌تواند عددی غیر از صفر هم باشد. به وضوح با استفاده از یک رمز دنباله‌ای nبیتی دوره تناوب مولد برابر ۲ n خواهد بود. همچنین در این مورد باید مقادیر اولیه را نیز مخفی نگاه داشت.
هر تابع درهم سازی امن را می‌توان به مولد امن اعداد شبه‌تصادفی تبدیل کرد. کافی است ورودی مانند حالت بالا را به چنین تابعی وارد سازیم. در این حالت، باید مقدار اولیه مورد استفاده هم عددی تصادفی باشد. به هر صورت، در عمل برای تولید اعداد شبه‌تصادفی از این شیوه چندان استفاده نمی‌گردد.
هر رمز دنباله‌ای نیز می‌تواند به عنوان مولد امن اعداد شبه‌تصادفی به کار گرفته شود. در رمزهای دنباله‌ای، معمولا دنباله‌ای تصادفی با متن اصلی ترکیب می‌شود (معمولا XOR می‌شود) تا متن رمز شده به دست آید. اما چنانچه ورودی شمارشی که در موارد قبلی استفاده نمودیم را با دنباله شبه‌تصادفی ترکیب کنیم، دنباله شبه‌تصادفی جدیدی به دست می‌آید. این دنباله رمز شده نیز تنها زمانی امن خواهد بود که دنباله تصادفی اول امن باشد. در این مورد نیز باید حالت اولیه مخفی نگاه داشته شود.
طراحی بر پایه نظریه اعداد
الگوریتم بلام بلام شاب بر اساس فرض سخت بودن مسئله تجزیه اعداد، یک دنباله شبه‌تصادفی امن پدید می‌آورد.
الگوریتم بلام-میکلی الگوریتمی بسیار کند است که تحت فرض سخت بودن مسئله لگاریتم گسسته امنیت را بدون هیچ شرط اضافه تضمین می‌کند.
طراحی‌های خاص
تعدادی از مولدهای امن تولید اعداد شبه‌تصادفی با طراحی خاص در ذیل عنوان شده‌اند.
الگوریتم یارو می‌کوشد تا کیفیت بی‌نظمی ورودی را معین سازد. این الگوریتم در OpenBSD, FreeBSD و Mac OS X مورد استفاده قرار گرفته است.
الگوریتم Fortuna که پس از الگوریتم یارو عرضه شد و بر خلاف مورد قبلی کیفیت بی‌نظمی ورودی را نمی‌سنجد.
ISAAC که بر مبنای رمز آر سی ۴ ساخته شده است.
AES-CTR DRBG اغلب به عنوان مولد اعداد تصادفی در سیستم‌هایی به کار برده می‌شود که از رمز استاندارد رمزنگاری پیشرفته (AES) استفاده می‌کنند.
استانداردها
تاکنون بسیاری از مولدهای امن اعداد شبه‌تصادفی به عنوان استاندارد معرفی شده‌اند. به عنوان نمونه می‌توان به موارد ذیل اشاره نمود.
NIST SP 800-90A
ANSI X9.17-1985 پیوست C
ANSI X9.31-1998 پیوست A.2.4
یک مناسب در این زمینه توسط موسسه ملی استاندارد و فناوری تهیه شده است.