Afzallik (kriptografiya) - Advantage (cryptography)

Yilda kriptografiya, dushman afzallik bu kriptografikaga qanchalik muvaffaqiyatli hujum qilishi mumkinligini ko'rsatadigan o'lchovdir algoritm, uni ushbu turdagi algoritmning ideallashtirilgan versiyasidan farqlash orqali. Ushbu kontekstda "dushman "o'zi algoritm va a emas shaxs. Agar biron bir raqib beparvo bo'lmaydigan ustunlikka ega bo'lmasa, raqibning hisoblash resurslarida belgilangan chegaralar mavjud bo'lsa, kriptografik algoritm xavfsiz hisoblanadi. aniq xavfsizlik ). "E'tiborsiz" odatda "ichida" degan ma'noni anglatadi O (2.P) "bu erda p xavfsizlik parametri algoritm bilan bog'liq. Masalan, blokirovka shifridagi bitlar soni p bo'lishi mumkin kalit.

Tushunchaning tavsifi

$ F $ $ an $ bo'lsin oracle o'rganilayotgan funktsiya uchun va G ushbu turdagi idealizatsiya funktsiyasi uchun hal qiluvchi bo'lsin. A raqibi F yoki G ni kiritish sifatida berilgan va 1 yoki 0 ni chiqaradigan ehtimollik algoritmidir. A ning vazifasi - berilgan oracle-ga so'rovlar berishga asoslangan holda F ni G dan ajratishdir. Biz aytamiz:

Misollar

Ning tasodifiy misoli bo'lsin DES blok shifr. Ushbu shifrda 64 bitli bloklar va 56 bitli kalit mavjud. Shuning uchun kalit 2 kishilik oiladan birini tanlaydi56 almashtirishlar 2da64 mumkin bo'lgan 64-bitli bloklar. "Tasodifiy DES misoli" degani, bizning oracle F, ba'zi bir K tugmachasi yordamida DESni hisoblab chiqishini anglatadi (bu raqibga noma'lum), bu erda K tanlangani 2 dan56 teng ehtimollik bilan mumkin bo'lgan tugmachalar.

Biz DES misolini an bilan taqqoslamoqchimiz idealizatsiya qilingan 64-bitli blok shifr, ([2] dan tasodifiy tanlangan almashtirishni anglatadi64)! 64-bitli bloklarda mumkin bo'lgan almashtirishlar. Ushbu tasodifiy tanlangan almashtirishni G. deb nomlang. Eslatma Stirlingning taxminiy qiymati bu (264)! atrofida , shuning uchun qaysi almashtirishni tanlanganligini aniq belgilash har qanday haqiqiy kompyuterda aks ettirish uchun juda katta sonni yozishni talab qiladi. Boshqacha qilib aytganda, G - "kalit uzunligi" 10 ga yaqin bo'lgan "shifr" ning misoli21 yana kompyuterga sig'maydigan juda katta bit. (Ammo, biz $ G $ ni so'rovlar soniga mutanosib bo'lgan saqlash maydoni bilan amalga oshirishimiz mumkin tasodifiy oracle ).

Shuni yodda tutingki, bizga berilgan so'zlar biz tanlagan oddiy matnni shifrlaydi, biz modellashtiramiz ochiq matnli hujum yoki CPA, va biz hisoblayotgan ustunlikni ma'lum bir raqibning CPA-afzalligi deb atash mumkin. Agar bizda ham shifrlarni ochish imkoniyatlari mavjud bo'lsa, biz buni qilardik shifrlangan matn hujumi yoki CCA va raqibning CCA-afzalligini topish.


1-misol: tasodifiy taxmin qiling

Ushbu raqibni A deb nomlang0. U shunchaki tangani aylantiradi va 1 yoki 0 ni teng ehtimollik bilan va hech qanday qo'ng'iroq qilmasdan qaytaradi. Shunday qilib, Pr [A0(F) = 1] va Pr [A0(G) = 1] ikkalasi ham 0,5 ga teng. Ushbu ehtimolliklar orasidagi farq nolga teng, shuning uchun Adv (A)0) nolga teng. Xuddi shu narsa, agar biz har doim 0 ni qaytarsak yoki har doim 1 ni qaytarsak: ehtimollik F va G uchun bir xil, shuning uchun ustunlik nolga teng. Ushbu dushman F va G ni ajrata olmaydi. Agar biz shifr dizaynerlari bo'lsak, bizning xohishimiz (buni amalga oshirish mumkin emas) buni shunday qilishdir hisoblash mumkin emas uchun har qanday raqib bundan sezilarli darajada yaxshiroq qilish. Agar biz qo'pol kuch qidirishdan ko'ra tezroq ajratadigan narsa yo'q shifrni tuza olsak, muvaffaqiyatga erishamiz.

2-misol: Qo'pol kuch bilan qidirish

Ushbu dushman (uni A deb nomlang1) tomonidan kiritilgan ma'lumotlarni kriptanaliz qilishga harakat qiladi qo'pol kuch. Uning o'ziga xos DES dasturi mavjud. U o'z oracle-ga bitta so'rov beradi va barcha nollarning 64-bitli qatorini shifrlashni so'raydi. Olingan shifrlangan matnni chaqiring0. So'ngra u to'liq kalit qidirishni amalga oshiradi va algoritm quyidagicha ko'rinadi:

 E0 = 0,1, ..., 2 ichida k uchun oracle_query (0)56-1: agar DESk(0) == E0: qaytish 1 qaytish 0

Bu 56-bitli DES tugma maydonini qidiradi va agar u mos keladigan kalitni topsa, "1" qiymatini beradi. Amalda, kalitni tasdiqlash uchun bir nechta oddiy matnlar talab qilinadi, chunki ikkita turli xil tugmachalar bitta yoki bir nechta mos matnli-shifrli juftliklarni keltirib chiqarishi mumkin. Agar kalit topilmasa, u 0 ga qaytadi.

Agar kirish oracle DES bo'lsa, bu to'liq qidirish kalitni topishi aniq, shuning uchun Pr [A1(F) = 1] = 1. Agar kirish oracle tasodifiy almashtirish bo'lsa, 2 ga teng64 E ning mumkin bo'lgan qiymatlari0, va ko'pi bilan 256 ulardan DES kalit qidiruvida tekshiriladi. Shunday qilib A ning ehtimolligi1 1-ni qaytarish eng ko'pi 2−8. Anavi:

, shuning uchun

shuning uchun afzallik kamida 0,996 ga teng. Bu deyarli aniq farq qiluvchi narsa, ammo bu xavfsizlik nuqsoni emas, chunki bu qo'pol kuch qidirishdan tezroq emas, axir bu qo'pol kuch qidirish.

Shuningdek qarang

Adabiyotlar