6- ma'ruza. To'liq va qisman tanlash algoritmlari reja

6- ma'ruza . To'liq va qisman tanlash algoritmlari
REJA:

1. 
   Qo'pol kuch algoritmlari
   
2. 
   Qisman sanash algoritmlari
   

Asosiy tushunchalar : qo'pol kuch, qo'pol kuch, kriptografik kuch , qo'pol kuch, xiralik , kriptografik hujumlar, qo'pol kuch.
1. Qo'pol kuch algoritmlari
Qidiruv - bu turli xil muammolarni hal qilish usuli bo'lib, u barcha mumkin bo'lgan variantlarni ko'rib chiqish orqali yechim topish usullarini anglatadi .
Qo'pol kuch - matematik muammolarni hal qilish usuli . U barcha mumkin bo'lgan variantlarni ishga solib, yechim topish usullari sinfiga kiradi . To'liq qidiruvning murakkabligi muammoning barcha mumkin bo'lgan echimlari soniga bog'liq. Agar yechim maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yillar yoki hatto asrlar davomida natija bermasligi mumkin.
NP sinfidagi har qanday muammoni to'liq qidirish orqali hal qilish mumkin. Shu bilan birga, masalaning har bir aniq mumkin bo'lgan yechimidan maqsad funktsiyasini hisoblash barcha mumkin bo'lgan echimlar soniga qarab ko'pnomli vaqtda amalga oshirilishi mumkin bo'lsa ham, to'liq sanab o'tish eksponensial ish vaqtini talab qilishi mumkin.
Kriptografiyada to'liq qidiruvning hisoblash murakkabligi shifrlarning kriptografik kuchini baholash uchun ishlatiladi. Xususan, shafqatsiz qidiruvdan sezilarli darajada tezroq "yorilish" usuli bo'lmasa , shifr xavfsiz deb aytiladi . Shafqatsiz kuch kriptografik hujumlar eng ko'p qirrali, lekin ayni paytda eng uzundir.
"Chalqash usuli" turli usullarning butun sinfini o'z ichiga oladi. Odatda, masalaning qo'yilishi har bir holatni mustaqil tahlil qilish orqali mantiqiy fikrning haqiqatini aniqlash uchun berilgan mantiqiy tizimning cheklangan sonli holatlarini ko'rib chiqishni nazarda tutadi. Tasdiqni isbotlash usuli ikki qismdan iborat:

1. 
   Har bir variantni tekshirish va ko'rib chiqilayotgan variant muammoni hal qilish yoki yo'qligini isbotlash.
   
2. 
   Tizimning barcha holatlarini tugatish imkoniyatini isbotlash. Tizimning har qanday o'ziga xos holati, masalan, isbotlanayotgan mantiqiy ifodaning qiymati ko'rib chiqilayotgan nomzod echimlarning kamida bittasiga mos kelishini ko'rsatish talab qilinadi.
   

“Bo‘l va bo‘ysun” tushunchasi bilan munosabati. Algoritmlar nazariyasida keng qo'llaniladigan bir qancha umumiy tushunchalar mavjud. Shafqatsiz kuch usuli ulardan biridir. Darhaqiqat, to'liq qidiruvdan biz holatlarni osongina tahlil qilish mumkin bo'lgan diskret deterministik tizim bilan shug'ullanadigan holatlarda foydalanish mumkin.
Algoritmlar nazariyasidagi fundamental tushunchaning yana bir yorqin misoli “bo‘l va hukmronlik qil” tamoyilidir. Ushbu kontseptsiya tizimni tuzilishi dastlabki tizimga o'xshash ko'plab quyi tizimlarga bo'linishi mumkin bo'lgan hollarda qo'llaniladi. Bunday hollarda, quyi tizimlar ham ajralishga mos keladi yoki ahamiyatsizdir. Bunday tizimlar uchun dastlab qo'yilgan muammo ahamiyatsiz. Shunday qilib, "bo'l va zabt et" kontseptsiyasini amalga oshirish rekursivdir.
O'z navbatida, rekursiya o'ziga xos to'liq qidiruvdir. Demak, rekursiya faqat diskret tizimlar uchun amal qiladi. Biroq, bu talab ma'lum bir tizimning holatlariga emas, balki uning quyi tuzilishiga taalluqlidir. Barcha darajalarni izchil ko'rib chiqish butun diskret tizim uchun qo'yilgan muammoni to'liq hal qiladi.
To'liq sanab o'tishning boshqa misollari bilan taqqoslaganda, rekursiya usulining o'ziga xos xususiyati shundaki, yakuniy yechim bir nechta arzimas quyi tizimlarga asoslangan. Umumiy holda, yechim quyi tizimlarning butun majmuasi asosida shakllanadi.
Klassik “bo‘l va zabt et” muammolarining quyidagi misollari uchun qo‘pol kuch ma’lum bo‘lgan yagona yechim yoki qo‘shimcha optimallashtirilgan asl dastur hisoblanadi:

• 
  Eng yaqin qo'shni muammosini topish
  
• 
  Matritsalarning zanjirli mahsuloti
  
• 
  Xesh to'qnashuvini aniqlash
  
• 
  Eng katta pastki qatorni topish
  

Qo'pol kuch hujumi. Kriptografiyada shafqatsiz kriptografik hujum yoki qo'pol kuch qo'pol kuchga asoslanadi . shafqatsiz kuch hujum - barcha mumkin bo'lgan asosiy variantlarni sanab, parolni buzish . Uning xususiyati amalda qo'llaniladigan har qanday istisno shifriga, ya'ni axborot nazariyasi nuqtai nazaridan xavfsizlikka nisbatan qo'llash qobiliyatidir.
Biroq, bu imkoniyat faqat nazariy jihatdan mavjud bo'lib, ko'pincha real bo'lmagan vaqt va resurs xarajatlarini talab qiladi. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda bunday hujum bir necha yillar yoki hatto asrlar davomida muvaffaqiyatsiz bo'lishi mumkin. Qo'pol kuch hujumidan foydalanish, hujum qilinayotgan shifrlash tizimining zaif tomonlarini topishning iloji bo'lmagan yoki ko'rib chiqilayotgan shifrlash tizimida zaif nuqtalar mavjud bo'lmagan hollarda eng ko'p oqlanadi. Bunday kamchiliklar aniqlanganda, ularning xususiyatlaridan kelib chiqqan holda kriptoanaliz usullari ishlab chiqiladi , bu esa xakerliklarni soddalashtirishga yordam beradi.
Qo'pol kuch hujumiga qarshilik kriptotizimda ishlatiladigan shifrlash kalitini aniqlaydi. Shunday qilib, kalit uzunligining oshishi bilan ushbu usul bilan yorilishning murakkabligi eksponent ravishda oshadi. Eng oddiy holatda, N bit uzunlikdagi shifr, eng yomon holatda, 2N ga proportsional vaqt ichida buziladi. Bu holda o'rtacha xakerlik vaqti ikki baravar kamroq va 2N -1 ni tashkil qiladi. Shifrning " qo'pol " ga qarshiligini oshirish usullari mavjud shifrlangan ma'lumotlarni shifrlangan ma'lumotlarni shifrlanmagan ma'lumotlardan ajratishni ahamiyatsiz qiladi .
chalkashtirib yuborish - bu dasturning dastlabki matnini yoki bajariladigan kodini uning funksionalligini saqlaydigan, lekin tahlil qilish, ishlash algoritmlarini tushunish va dekompilyatsiya paytida o'zgartirishni qiyinlashtiradigan shaklga keltirishdir .
"Qo'pol kuch" usuliga asoslangan kriptografik hujumlar eng ko'p qirrali, lekin ayni paytda eng sekin. Asosan yangi boshlanuvchi xakerlar tomonidan qo'llaniladi. Oddiy shifrlash algoritmlari va 64 bitgacha bo'lgan kalitlar uchun samarali. Uzunligi 128 bit yoki undan ko'p bo'lgan zamonaviy kalitlar uchun ba'zan kalit uchun ko'p sonli 200 ta raqam omillashtiriladi, bu samarasiz. Har qanday parolni to'liq qidiruv orqali taxmin qilish mumkin. Shu bilan birga, agar muammoning har bir aniq mumkin bo'lgan yechimidan maqsad funktsiyasini hisoblash barcha mumkin bo'lgan echimlar soniga qarab ko'p nomli vaqtda amalga oshirilishi mumkin bo'lsa ham, hujum eksponensial ishlash vaqtini talab qilishi mumkin.