|
Ta'rif 1 (kirish bilan RNG). Kiritilgan RNG algoritmlarning uchligi G = (sozlash, yangilash, keyingi) va uchlik (n, ℓ, p) ∈ N3, bunda n — holat uzunligi, ℓ — chiqish uzunligi va p — G ning kirish uzunligi. :
– oʻrnatish: generator uchun baʼzi umumiy parametrlar urugʻini chiqaradigan ehtimoliy algoritm.
– yangilash: S ∈ {0, 1}n holati va kirish I ∈ {0, 1}p boʻlgan deterministik algoritm, yangi holatni chiqaradi S′ = refresh(seed, S, I) ∈ { 0, 1}n.
– keyingisi: S ∈ {0, 1}n holati va S ∈ {0, 1}n holati berilgan deterministik algoritm. yangi holat va R ∈ {0, 1}ℓ - chiqish.
Xavfsizlik tushunchalarimizni aniqlashga o'tishdan oldin, biz tashvishlanishimiz kerak bo'lgan ikkita raqib mavjudligini payqashimiz kerak: raqib A, uning vazifasi (intuitiv ravishda) RNG chiqishini farqlashdir.
tasodifiy va tarqatish namunasi D, uning vazifasi I1, I2, kirishlarni ishlab chiqarishdir. . . , ular birgalikda yuqori entropiyaga ega, lekin qandaydir tarzda A ga RNG xavfsizligini buzishda yordam beradi. Boshqacha qilib aytganda, tarqatish namunasi bizning RNG ishlashga majbur bo'lgan potentsial raqib muhitni (yoki "tabiatni") modellashtiradi.
3.1 Namuna taqsimoti
Tarqatish tanlanmasi D - statistik ehtimolli algoritm bo'lib, joriy s holatini hisobga olgan holda, kortejni chiqaradi (s, I, g, z), bu erda: (a) s - D uchun yangi holat; (b) I ∈ {0, 1}p - yangilash algoritmi uchun keyingi kiritish; (c) g - quyida muhokama qilinganidek, I ning oxirgi entropiya bahosi; (d) z - bu tajovuzkor A ga bergan ma'lumotlarimning sizib chiqishi. Xavfsizlik o'yinlarimizda D bajarilish sonining yuqori chegarasini qD bilan belgilang va agar H∞(Ij | I1, . . . bo'lsa, D) qonuniy ekanligini ayting. , Ij−1 , Ij+1,..., IqD, z1,..., zqD, g0,..., gqD) ≥ gj barcha j ∈ {1, . . . , qD}, bu yerda (si, Ii, gi, zi) = D(si−1) i ∈ {1, . . . , qD} va s0 = 0,1
Biz[DPR+13] ning entropiya hisobinigjjjjj chiqarishni aniq talab qilish sabablarini tushuntiramiz. Ko‘pchilik murakkab RNGlar tizimga yangi entropiya kiritilmagan uzoq muddatli holatga kirishi mumkin bo‘lgan vaziyatdan xavotirda. Shunga mos ravishda, bunday RNGlar odatda etarli entropiya g∗ (ba'zi bir entropiya chegarasi g∗ uchun) to'planmaguncha, RNGni chiqish qiymatiRj dan maqsadli to'sib qo'yadigan ba'zi maxsus entropiyani baholash protseduralarini o'z ichiga oladi. Afsuski, ma'lumki, hatto taxminan
berilgan taqsimotning entropiyasi hisoblash qiyin masala [SV03]. Bu shuni anglatadiki, agar biz RNG G-dan bunday E protsedurasini aniq taklif qilishni talab qilsak, biz D ga ba'zi muhim cheklovlar (yoki taxminlar) qo'yishimiz yoki ba'zi bir hoc va standart bo'lmagan taxminlarga tayanishimiz kerak. Darhaqiqat, [DPR+13]
Linux RNG entropiyasini baholashga ba'zi hujumlarni ko'rsatib, E entropiyani to'g'ri baholash jarayonini loyihalash qanchalik qiyinligini (yoki, ehtimol, imkonsizmi?) ko'rsating. haqiqiy yangilash va keyingi protseduralar, ma'nosi
ikkinchisi E ning "aniqligi" dan mustaqil ravishda baholanishi mumkin va baholanishi kerak.
Ushbu fikrlardan kelib chiqqan holda, [DPR+13] RNG dizaynining majburiy qismi sifatida hech qanday "entropiyani baholash" protsedurasini talab qilmaydi. Buning o'rniga, ular entropiyani baholash yukini D ning o'ziga yuklaydi. Shunga o'xshab, gj entropiyani baholash E (hozirda D bilan "birlashtirilgan") entropiyani baholash protsedurasidan kelib chiqadi deb o'ylashimiz mumkin, lekin faqat xavfsizlikni ta'minlaydi, agar E bu baholashda to'g'ri bo'lsa (biz bilamizki, bu amalda qiyin va bu yo'nalishdagi kelajakdagi ishlarni rag'batlantiradi).
Shu bilan birga, biz quyidagilarni ta'kidlaymiz: (a) gj entropiya baholari faqat bizning xavfsizlik ta'riflarimizda qo'llaniladi, lekin haqiqiy RNG operatsiyalarining birortasida emas (bu faqat D tomonidan qaytarilgan kiritishdan foydalanadi); (b) biz qonuniy D o'zining keyingi Ij namunasining yangi entropiyasini mukammal baholashi mumkinligini ta'kidlamaymiz, faqat qonuniy bo'lgan pastki chegarani ta'minlaymiz. Misol uchun, D gj = 0 ni xohlagancha ko'p marta o'rnatishi mumkin va bu holda, hatto zj oqishi orqali butun Ij ni A ga oqizishni tanlashi mumkin! Umuman olganda, biz D ga yangi gj entropiyani xohlagancha sekin (va g‘arazli!) kiritishga ruxsat beramiz, lekin tizim2dagi joriy “yangi” entropiyani kuzatuvchi c hisoblagichi ba’zi entropiya chegarasini kesib o‘tgandagina xavfsizlik talab qilinadi g∗ ( chunki aks holda biz har qanday xavfsizlikni kutish uchun "hech qanday sabab" yo'q).
Do'stlaringiz bilan baham: |
