تصادفی بودن و شبهتصادفی بودن
تصادفی بودن شریان حیاتی رمزنگاری است — کلیدها، نانسها و چالشها باید غیرقابل پیشبینی باشند — و شبهتصادفی بودن اجازه میدهد تا یک بذر تصادفی واقعی کوتاه به دنبالههای طولانی تبدیل شود که از نظر هر مهاجم کارآمدی، از تصادفی بودن قابل تشخیص نیستند.
Definition
شبهتصادفی بودن خاصیتی است که از نظر محاسباتی از تصادفی بودن واقعی قابل تشخیص نیست؛ یک مولد شبهتصادفی به طور قطعی یک بذر تصادفی کوتاه را به یک خروجی طولانیتر گسترش میدهد که هیچ الگوریتم کارآمدی نمیتواند آن را از تصادفی بودن تشخیص دهد.
Scope
این موضوع نقش تصادفی بودن در رمزنگاری را پوشش میدهد: الزامات مربوط به منابع آنتروپی و مولدهای اعداد تصادفی واقعی، تعاریف و ساختارهای مولدهای شبهتصادفی امن رمزنگاری و توابع شبهتصادفی، و پیامدهای فاجعهبار تصادفی بودن ضعیف یا استفاده مجدد از آن. این موضوع به چگونگی رسمیسازی اصول اولیه متقارن توسط اشیاء شبهتصادفی میپردازد. این مبحث شامل رمزهای خاص و فرضیات سختی نمیشود که در موضوعات مرتبط دیگر بررسی میشوند.
Core questions
- چرا رمزنگاری به تصادفی بودن غیرقابل پیشبینی نیاز دارد و بدون آن چه مشکلاتی پیش میآید؟
- چه چیزی یک مولد امن رمزنگاری را از یک مولد آماری متمایز میکند؟
- چگونه میتوان یک بذر تصادفی واقعی کوتاه را به خروجی شبهتصادفی طولانی تبدیل کرد؟
- توابع و جایگشتهای شبهتصادفی چه هستند و چگونه رمزها را مدلسازی میکنند؟
- چگونه آنتروپی با کیفیت بالا در سیستمهای واقعی جمعآوری و پردازش میشود؟
Key concepts
- آنتروپی و تصادفی بودن واقعی
- مولدهای اعداد تصادفی
- مولد شبهتصادفی (PRG)
- تابع شبهتصادفی (PRF)
- جایگشت شبهتصادفی (PRP)
- غیرقابل تشخیص بودن محاسباتی
- بذر و استخراج کلید
- شکستهای ناشی از استفاده مجدد از تصادفی بودن
- پردازش آنتروپی
Key theories
- مولدهای شبهتصادفی
- یک مولد شبهتصادفی یک بذر کوتاه را به یک رشته طولانیتر گسترش میدهد که برای هر متمایزکننده کارآمدی از تصادفی بودن یکنواخت قابل تشخیص نیست؛ چنین مولدهایی تنها در صورتی وجود دارند که توابع یکطرفه وجود داشته باشند، که شبهتصادفی بودن را به مبانی رمزنگاری پیوند میدهد.
- توابع و جایگشتهای شبهتصادفی
- یک خانواده تابع شبهتصادفی، که از هر مولد شبهتصادفی قابل ساخت است، برای یک مهاجم که آن را پرس و جو میکند، از یک تابع واقعاً تصادفی قابل تشخیص نیست؛ این شیء زیربنای مدلسازی امنیتی رمزهای قالبی و کدهای احراز هویت پیام است.
Mechanisms
یک مولد اعداد تصادفی واقعی، آنتروپی فیزیکی (نویز حرارتی، لرزش زمانبندی) را جمعآوری میکند که پس از پردازش، برای بذردهی یک مولد شبهتصادفی امن رمزنگاری استفاده میشود. این مولد به طور قطعی تمام بیتهای شبهتصادفی مورد نیاز یک سیستم را تولید میکند. توابع شبهتصادفی از مولدها (ساختار GGM) ساخته میشوند و اصول اولیه کلیددار را مدلسازی میکنند؛ یک رمز قالبی به عنوان یک جایگشت شبهتصادفی در نظر گرفته میشود. تعاریف امنیتی ایجاب میکنند که هیچ مهاجم کارآمدی، با داشتن خروجیها، نتواند بیتهای بعدی را پیشبینی کند یا آنها را از تصادفی بودن تشخیص دهد.
Clinical relevance
شکستهای تصادفی بودن منبع مکرر شکستهای فاجعهبار در دنیای واقعی هستند: باگ OpenSSL دبیان در سال ۲۰۰۸ تولید کلید را مختل کرد، نانسهای قابل پیشبینی ECDSA کلیدهای خصوصی را فاش کردند (پلیاستیشن ۳ سونی، برخی کیف پولهای بیتکوین)، و آنتروپی ضعیف دستگاههای تعبیهشده کلیدهای قابل حدس را در مقیاس وسیع تولید کرد. بنابراین، تصادفی بودن قوی — جمعآوری صحیح آنتروپی و مولدهای شبهتصادفی تأیید شده — برای هر استقرار رمزنگاری ضروری است.
Evidence & guidelines
استانداردهای NIST SP 800-90A/B/C مولدهای بیت تصادفی قطعی تأیید شده، اعتبارسنجی منبع آنتروپی و راهنماییهای ساخت را مشخص میکنند. بهترین روش استفاده از RNG رمزنگاری تأیید شده سیستم عامل (به جای ساختن RNG شخصی)، اطمینان از آنتروپی کافی قبل از تولید کلیدها و هرگز استفاده مجدد از نانسها است. مجموعههای آزمون آماری به شناسایی نقصهای بزرگ کمک میکنند اما نمیتوانند قدرت رمزنگاری را اثبات کنند.
History
نظریه محاسباتی شبهتصادفی بودن توسط بلوم و میکالی و توسط یائو در حدود سال ۱۹۸۲ پایهگذاری شد و غیرقابل پیشبینی بودن و غیرقابل تشخیص بودن را تعریف کرد. گلدریچ، گلدواسر و میکالی در سال ۱۹۸۶ نشان دادند که چگونه میتوان توابع شبهتصادفی را از مولدها ساخت، و هاستاد، ایمپالیازو، لوین و لوبی بعدها اثبات کردند که اگر توابع یکطرفه وجود داشته باشند، مولدهای شبهتصادفی نیز وجود دارند. فجایع عملی مکرر ناشی از تصادفی بودن ضعیف، کیفیت آنتروپی و RNG را به یک نگرانی مهندسی مرکزی تبدیل کرده است.
Key figures
- Oded Goldreich
- Shafi Goldwasser
- Silvio Micali
- Manuel Blum
- Andrew Yao
Related topics
Seminal works
- goldreich1986
- goldreich2001
- katz2020
Frequently asked questions
- چرا نمیتوانم از یک تابع تصادفی معمولی مانند rand() برای رمزنگاری استفاده کنم؟
- مولدهای اعداد تصادفی معمولی برای یکنواختی آماری و سرعت ساخته شدهاند، نه غیرقابل پیشبینی بودن؛ خروجی آنها را میتوان از چند نمونه پیشبینی کرد. رمزنگاری به مولدهایی نیاز دارد که پیشبینی خروجی آینده آنها حتی با داشتن خروجی گذشته نیز غیرممکن باشد، که این امر به یک RNG امن رمزنگاری که با آنتروپی واقعی بذردهی شده باشد، نیاز دارد.
- تفاوت بین تصادفی بودن واقعی و شبهتصادفی بودن چیست؟
- تصادفی بودن واقعی از یک منبع فیزیکی و غیرقابل پیشبینی میآید و عرضه آن محدود است. شبهتصادفی بودن به طور قطعی از یک بذر تصادفی واقعی کوتاه تولید میشود و میتوان آن را به صورت انبوه تولید کرد؛ تنها کافی است که برای هر مهاجم کارآمدی از تصادفی بودن واقعی قابل تشخیص نباشد، که برای استفاده رمزنگاری کافی است.