Kirish dissertatsiya mavzusining dolzarbligi va zarurati

2.2. XL algoritmi

“XL-algoritmi” taniqli chiziqlashtirish usulining umumlashtirilgan shakliga asoslangan polinom tenglamalar tizimini yechish usulidir; Bu usul kriptologiyaga 2000-yil kiritilgan. XL-algoritmdagi tenglamalar bo’shliqlarning o’lchamlari bo’yicha yuqori chegaralarni isbotlaymiz. Bu yuqori chegaralar shuni ko‘rsatadi-ki har qanday qo’zg’almas chekli maydon K va har qanday qo’zg’almas c∈N uchun haqiqiy yechimlarga ega bo‘lgan K taqsim m=n+c kvadrat tenglamasidagi n o’zgaruvchan songa qo‘llanilgan XL algoritmining medianasi n ga subeksponensial emas_.
Algebraik kriptanaliz hujumlar, aniqlangan tizimlar polinom tenglamalari, kengaytirilgan linearizatsiya, Froberg gipotezasiga asosan agar cheklangan maydonlar bo’yicha ko’phadli tenglamalar sistemalarining ayrim turlarini kimdir yechib qo‘yadigan bo’lsa, ko’plab kriptografik tizimlar xavf ostida qolar edi. Misol uchun, agar kimdir 1600 ta o’zgaruvchilardan tashkil topgan aynan sistemalar tizimi va F₂ taqsim 8000 ta kvadrat tenglamalarni yechib qo‘yadigan bo‘lsa, u katta ehtimollik AES-128 ochishi mumkin.
XL-algoritmi
Ildizlari K bo‘lgan va D bo’lgan kvadrat tenglamalarni yechishni ko‘ramiz. XL-algoritmining asosiy maqsadi bu ko‘phad tenglamalarni linearizatsiya yo‘li bilan yechish
, k. (2.1)
Asl XL algoritmi faqat aniqlangan (kvadrat) ko‘phad tenglamalar tizimiga qo’llanilishi kerak, agar maydon chekli va juda katta bo’lmasa, har qanday tizimga qisqartirilgan XL-algoritmini qo’llash mantiqan to’gri bo’ladi Ikkala hisoblash usulining hech biri har bir kirish uchun yetarlicha bo‘lmaydi.
XL-algoritmini tahlil qilishning boshlang’ich ishi tahlil qilishdir bir jinsli polinom sonlar nazariyasi orqali original XL-algoritmning Moh ([13]) tomonidan ta’kidlangan.
XL-algoritmining umumiylashtirilgan va soddalashtirilgan shakli
XL-algoritmining qisqartirilgan ko’phad tenglamalarning kvadratik tizimlariga qaraganda umumiyroq qilib oson umumlashtirish mumkin:
f₁(X₁, . . . , X_n) = 0, . . . , f_m(X₁, . . . , X_n) = 0.
XL-algoritmni umumlashtirish XL algoritm kabi ishlaydi, farqi ba’zi D=2 uchun N, biri Gauss eliminatsiyasini barcha ko’phadning chiziqli tenglamalar tizimiga qo’llaydi
, A=1
Qisqartirilgan XL-algoritmi ham xuddi shunday tarzda umumlashtirilishi mumkin. Bu usulni umumlashmalarni “original" va “reduced" XL-algoritmi deb aytiladi[14].