Yashirin maydon tenglamalari - Hidden Field Equations - Wikipedia

Yashirin maydonlar tenglamalari (HFE), shuningdek, nomi bilan tanilgan HFE trapdoor funktsiyasi, a ochiq kalit kriptotizim da kiritilgan Evrokript 1996 yilda va tomonidan taklif qilingan (frantsuz tilida) Jak Patarin g'oyasiga amal qilish Matsumoto va Imai tizimi. Bunga asoslanadi polinomlar ustida cheklangan maydonlar ${ displaystyle mathbb {F} _ {q}}$ o'rtasidagi munosabatlarni yashirish uchun turli o'lchamdagi shaxsiy kalit va ochiq kalit. HFE aslida asosiy HFE va HFE ning kombinatorial versiyalaridan iborat bo'lgan oiladir. Kriptotizimlarning HFE oilasi ko'p o'zgaruvchan tizimga echim topish muammosining qattiqligiga asoslangan. kvadrat tenglamalar (MQ muammosi deb ataladi), chunki u xususiy foydalanadi afinaviy transformatsiyalar kengaytma maydonini va xususiyni yashirish uchun polinomlar. Yashirin maydon tenglamalari raqamli imzo sxemalarini tuzishda ham ishlatilgan, masalan. Kvarts va Sflash.^[1]

Matematik fon

Yashirin maydon tenglamalari qanday ishlashini tushunishning asosiy tushunchalaridan biri bu ikkita kengaytma maydonida ko'rishdir ${ displaystyle mathbb {F} _ {q ^ {n}}}$ ${ displaystyle mathbb {F} _ {q ^ {m}}}$ bir xil asosiy maydon ustida ${ displaystyle mathbb {F} _ {q}}$ tizimini izohlash mumkin ${ displaystyle m}$ ko'p o'zgaruvchan polinomlar yilda ${ displaystyle n}$ o'zgaruvchilar tugadi ${ displaystyle mathbb {F} _ {q}}$ funktsiya sifatida ${ displaystyle mathbb {F} _ {q ^ {n}} to mathbb {F} _ {q ^ {m}}}$ mos foydalanib asos ning ${ displaystyle mathbb {F} _ {q ^ {n}}}$ ustida ${ displaystyle mathbb {F} _ {q}}$. Deyarli barcha dasturlarda polinomlar kvadratik, ya'ni ular 2 darajaga ega.^[2] Biz eng sodda polinomlardan, ya'ni monomiallardan boshlaymiz va ularning kvadratik tenglamalar tizimiga qanday olib kelishini ko'rsatamiz.

A ni ko'rib chiqing cheklangan maydon ${ displaystyle mathbb {F} _ {q}}$, qayerda ${ displaystyle q}$ 2 kuchi va kengaytma maydoni ${ displaystyle K}$. Ruxsat bering ${ displaystyle 0$ shu kabi ${ displaystyle h = q ^ { theta} +1}$ kimdir uchun ${ displaystyle theta}$ va gcd${ displaystyle (h, q ^ {n} -1) = 1}$. Vaziyat gcd${ displaystyle (h, q ^ {n} -1) = 1}$ xaritani talab qilishga teng ${ displaystyle u dan u ^ {h}}$ kuni ${ displaystyle K}$ bittadan bittasi va teskari xaritadir ${ displaystyle u to u ^ {h '}}$ qayerda ${ displaystyle h '}$ ning multiplikativ teskarisidir ${ displaystyle h { bmod {q}} ^ {n} -1}$.

Tasodifiy elementni oling ${ displaystyle u in mathbb {F} _ {q ^ {n}}}$. Aniqlang ${ displaystyle w in mathbb {F} _ {q ^ {n}}}$ tomonidan

${ displaystyle w = u ^ {h} = u ^ {q ^ { theta}} u (1)}$

Ruxsat bering ${ displaystyle beta _ {1}, ..., beta _ {n}}$ bo'lish a asos ning ${ displaystyle K}$ sifatida ${ displaystyle mathbb {F} _ {q}}$ vektor maydoni. Biz vakillik qilamiz ${ displaystyle u}$ kabi asosga nisbatan ${ displaystyle u = (u_ {1}, ..., u_ {n})}$ va ${ displaystyle w = (w_ {1}, ..., w_ {n})}$. Ruxsat bering ${ displaystyle A ^ {(k)} = {a_ {ij} ^ {(k)}}}$ chiziqli transformatsiyaning matritsasi bo'ling ${ displaystyle u to u ^ {q ^ {k}}}$ asosga nisbatan ${ displaystyle beta _ {1}, ..., beta _ {n}}$, ya'ni shunday

${ displaystyle beta _ {i} ^ {q ^ {k}} = sum _ {j = 1} ^ {n} a_ {ij} ^ {k} beta _ {j}, a_ {ij } ^ {k} in mathbb {F} _ {q}}$

uchun ${ displaystyle 1 leq i, k leq n}$. Bundan tashqari, bazaviy elementlarning barcha mahsulotlarini asos bo'yicha yozing, ya'ni:

${ displaystyle beta _ {i} beta _ {j} = sum _ {l = 1} ^ {n} m_ {ijl} beta _ {l}, m_ {ijl} in mathbb { F} _ {q}}$

har biriga ${ displaystyle 1 leq i, j leq n}$. Tizimi ${ displaystyle n}$ da aniq ko'rsatilgan tenglamalar ${ displaystyle w_ {i}}$ va ichida kvadratik ${ displaystyle u_ {j}}$ kengaytirib (1) va ning koeffitsientlarini nolga tenglashtirib olish mumkin ${ displaystyle beta _ {i}}$.

Ikki maxfiy affinatsiyani tanlang ${ displaystyle S}$ va ${ displaystyle T}$ , ya'ni ikkita teskari ${ displaystyle n times n}$ matritsalar ${ displaystyle M_ {S} = {S_ {ij} }}$ va ${ displaystyle M_ {T} = {T_ {ij} }}$ yozuvlari bilan ${ displaystyle mathbb {F} _ {q}}$ va ikkita vektor ${ displaystyle v_ {S}}$ va ${ displaystyle v_ {T}}$ uzunlik ${ displaystyle n}$ ustida ${ displaystyle mathbb {F} _ {q}}$ va aniqlang ${ displaystyle x}$ va ${ displaystyle y}$ orqali:

${ displaystyle u = Sx = M_ {S} x + v_ {S} w = Ty = M_ {T} y + v_ {T} (2)}$

O'rniga (2) -dagi affine munosabatlari yordamida ${ displaystyle u_ {j}, w_ {i}}$ bilan ${ displaystyle x_ {k}, y_ {l}}$, tizimi ${ displaystyle n}$ tenglamalar chiziqli ichida ${ displaystyle y_ {l}}$ va 2 daraja ${ displaystyle x_ {k}}$. Qo'llash chiziqli algebra beradi ${ displaystyle n}$ aniq tenglamalar, har biri uchun bittadan ${ displaystyle y_ {l}}$ da 2 darajali polinomlar sifatida ${ displaystyle x_ {k}}$.^[3]

Ko'p o'zgaruvchan kriptotizim

Buni HFE oilasining ko'p o'zgaruvchilardan foydalanishning asosiy g'oyasi kriptotizim dan boshlab maxfiy kalitni yaratishdir polinom ${ displaystyle P}$ birida noma'lum ${ displaystyle x}$ ba'zilari ustidan cheklangan maydon ${ displaystyle mathbb {F} _ {q ^ {n}}}$ (odatda qiymat ${ displaystyle q = 2}$ ishlatilgan). Bu polinom osongina teskari o'girilishi mumkin ${ displaystyle mathbb {F} _ {q ^ {n}}}$, ya'ni tenglamaning biron bir echimini topish mumkin ${ displaystyle P (x) = y}$ bunday echim mavjud bo'lganda. Yashirin o'zgarish ham parolni hal qilish va / yoki imzo ushbu inversiyaga asoslangan. Yuqorida aytib o'tilganidek ${ displaystyle P}$ tizimi bilan aniqlanishi mumkin ${ displaystyle n}$ tenglamalar ${ displaystyle (p_ {1}, ..., p_ {n})}$ sobit asos yordamida. Qurish uchun kriptotizim The polinom ${ displaystyle (p_ {1}, ..., p_ {n})}$ ommaviy axborot asl tuzilishini yashirishi va inversiyani oldini olish uchun o'zgartirilishi kerak. Bu ko'rish orqali amalga oshiriladi cheklangan maydonlar ${ displaystyle mathbb {F} _ {q ^ {n}}}$ kabi vektor maydoni ustida ${ displaystyle mathbb {F} _ {q}}$ va ikkita chiziqli tanlash orqali afinaviy transformatsiyalar ${ displaystyle S}$ va ${ displaystyle T}$. Uchlik ${ displaystyle (S, P, T)}$ shaxsiy kalitni tashkil qiladi. Xususiy polinom ${ displaystyle P}$ ustidan aniqlanadi ${ displaystyle mathbb {F} _ {q ^ {n}}}$.^[1][4] Ochiq kalit ${ displaystyle (p_ {1}, ..., p_ {n})}$. Quyida MQ-trapdoor uchun diagramma berilgan ${ displaystyle (S, P, T)}$ HFE-da

${ displaystyle { text {input}} x to x = (x_ {1}, ..., x_ {n}) { overset {{ text {secret}}: S} { to}} x '{ overset {{ text {secret}}: P} { to}} y' { overset {{ text {secret}}: T} { to}} { text {output}} y}$

HFE polinom

Xususiy polinom ${ displaystyle P}$ daraja bilan ${ displaystyle d}$ ustida ${ displaystyle mathbb {F} _ {q ^ {n}}}$ ning elementidir ${ displaystyle mathbb {F} _ {q ^ {n}} [x]}$. Agar shartlari polinom ${ displaystyle P}$ ko'pi bor kvadratik muddati tugadi ${ displaystyle mathbb {F} _ {q}}$ u holda umumiy polinom kichik bo'ladi.^[1] Ish shunday ${ displaystyle P}$ shakl monomiallaridan iborat ${ displaystyle x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}$, ya'ni 2 kuch bilan ${ displaystyle q}$ exponentis-ning asosiy versiyasi HFE, ya'ni ${ displaystyle P}$ sifatida tanlanadi

${ displaystyle P (x) = sum c_ {i} x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}$

Darajasi ${ displaystyle d}$ ning polinom xavfsizlik parametri sifatida ham tanilgan va uning qiymati qanchalik katta bo'lsa, xavfsizlik uchun yaxshiroq bo'ladi, chunki hosil bo'lgan kvadrat tenglamalar to'plami tasodifiy tanlangan kvadrat tenglamalarga o'xshaydi. Boshqa tomondan katta ${ displaystyle d}$ dehifrlashni sekinlashtiradi. Beri ${ displaystyle P}$ a polinom eng ko'p daraja ${ displaystyle d}$ ning teskarisi ${ displaystyle P}$, bilan belgilanadi ${ displaystyle P ^ {- 1}}$ hisoblash mumkin ${ displaystyle d ^ {2} ( ln d) ^ {O (1)} n ^ {2} mathbb {F} _ {q}}$ operatsiyalar.^[5]

Shifrlash va parolni hal qilish

Ochiq kalit ${ displaystyle n}$ ko'p o'zgaruvchan polinomlar ${ displaystyle (p_ {1}, ..., p_ {n})}$ ustida ${ displaystyle mathbb {F} _ {q}}$. Shunday qilib, xabarni uzatish kerak ${ displaystyle M}$ dan ${ displaystyle mathbb {F} _ {q ^ {n}} to mathbb {F} _ {q} ^ {n}}$ uni shifrlash uchun, ya'ni biz buni taxmin qilamiz ${ displaystyle M}$ bu vektor ${ displaystyle (x_ {1}, ..., x_ {n}) in mathbb {F} _ {q} ^ {n}}$. Xabarni shifrlash uchun ${ displaystyle M}$ biz har birini baholaymiz ${ displaystyle p_ {i}}$ da ${ displaystyle (x_ {1}, ..., x_ {n})}$. Shifrlangan matn ${ displaystyle (p_ {1} (x_ {1}, ..., x_ {n}), p_ {2} (x_ {1}, ..., x_ {n}), ..., p_ { n} (x_ {1}, ..., x_ {n})) in mathbb {F} _ {q} ^ {n}}$.

Shifrlashni tushunish uchun shifrlashni quyidagicha ifoda etamiz ${ displaystyle S, T, P}$. Shunga e'tibor bering emas jo'natuvchi uchun mavjud. Baholash orqali ${ displaystyle p_ {i}}$ biz birinchi murojaat qilgan xabarda ${ displaystyle S}$, ni natijasida ${ displaystyle x '}$. Mazkur holatda ${ displaystyle x '}$ dan uzatiladi ${ displaystyle mathbb {F} _ {q ^ {n}} to mathbb {F} _ {q ^ {n}}}$ shuning uchun biz xususiy polinomni qo'llashimiz mumkin ${ displaystyle P}$ tugadi ${ displaystyle mathbb {F} _ {q ^ {n}}}$ va bu natija bilan belgilanadi ${ displaystyle y ' in mathbb {F} _ {q ^ {n}}}$. Yana bir marta, ${ displaystyle y '}$ vektorga o'tkaziladi ${ displaystyle (y_ {1} ', ..., y_ {n}')}$ va transformatsiya ${ displaystyle T}$ qo'llaniladi va yakuniy chiqish ${ displaystyle y in mathbb {F} _ {q ^ {n}}}$ dan ishlab chiqarilgan ${ displaystyle (y_ {1}, ..., y_ {n}) in mathbb {F} _ {q} ^ {n}}$.

Shifrni ochish uchun ${ displaystyle y}$, yuqoridagi amallar teskari tartibda amalga oshiriladi. Shaxsiy kalit bo'lsa, bu mumkin ${ displaystyle (S, P, T)}$ ma'lum. Dehifrlashdagi hal qiluvchi qadam teskari emas ${ displaystyle S}$ va ${ displaystyle T}$ aksincha ning echimini hisoblash ${ displaystyle P (x ') = y'}$. Beri ${ displaystyle P}$ bijection shart emas, chunki bu inversiya uchun bir nechta echim topilishi mumkin (ko'pi bilan d xil echimlar mavjud ${ displaystyle X '= (x_ {1}', ..., x_ {d} ') in mathbb {F} _ {q ^ {n}}}$ beri ${ displaystyle P}$ d) darajadagi polinom hisoblanadi. Ishdan bo'shatish deb belgilangan ${ displaystyle r}$ xabarning birinchi qadamida qo'shiladi ${ displaystyle M}$ o'ngni tanlash uchun ${ displaystyle M}$ echimlar to'plamidan ${ displaystyle X '}$.^[1][3][6] Quyidagi diagrammada shifrlash uchun asosiy HFE ko'rsatilgan.

${ displaystyle M { overset {+ r} { to}} x { overset {{ text {secret}}: S} { to}} x '{ overset {{ text {secret}}: P} { to}} y '{ overset {{ text {secret}}: T} { to}} y}$

HFE o'zgarishlari

Yashirin maydon tenglamalari to'rtta asosiy o'zgarishlarga ega +, -, v va f va ularni har xil tarzda birlashtirish mumkin. Asosiy printsip quyidagilar:

01. The + belgisi ommaviy tenglamalarni ba'zi tasodifiy tenglamalar bilan chiziqli aralashtirishdan iborat.

02. The - belgisi tufayli Adi Shamir va ommaviy tenglamalarning "r" ortiqcha miqdorini olib tashlash niyatida.

03. The f belgisi ba'zi birlarini tuzatishdan iborat ${ displaystyle f}$ ochiq kalitning o'zgaruvchan parametrlari.

04. The v ishorasi sirka o'zgaruvchisi deb ataladigan o'zgaruvchilarning ba'zi bir vlari aniqlangan taqdirdagina funktsiyalarning teskarisini topish mumkin bo'lgan qurilish va ba'zan juda murakkab deb ta'riflanadi. Ushbu g'oya Jak Pataringa bog'liq.

Yuqoridagi operatsiyalar ma'lum darajada funktsiyani tuzoqdagi echuvchanligini saqlaydi.

HFE- va HFEv imzo sxemalarida juda foydalidir, chunki ular imzolarni ishlab chiqarishni sekinlashishiga yo'l qo'ymaydi, shuningdek HFE-ning umumiy xavfsizligini kuchaytiradi shifrlash ham HFE- va ham HFEv juda sekin olib keladi parolni hal qilish juda ko'p tenglamalarni o'chirib bo'lmaydi (HFE-) va juda ko'p o'zgaruvchilar qo'shilmasligi kerak (HFEv). Kvarsni olish uchun HFE- va HFEv ishlatilgan.

Shifrlash uchun HFE + bilan vaziyat yaxshiroqdir parolni hal qilish jarayon bir xil vaqtni oladi, ammo ochiq kalit o'zgaruvchilardan ko'ra ko'proq tenglamalarga ega.^[1][2]

HFE hujumlari

HFE-ga ikkita mashhur hujum mavjud:

Shaxsiy kalitni tiklash (Shomir -Kipnis): Ushbu hujumning asosiy maqsadi - bu shaxsiy kalitni kengaytma maydonida siyrak o'zgarmas polinomlar sifatida tiklash. ${ displaystyle mathbb {F} _ {q ^ {n}}}$. Hujum faqat asosiy HFE uchun ishlaydi va uning barcha o'zgarishlari uchun muvaffaqiyatsiz bo'ladi.

Tez Grobner asoslari (Fugère): g'oyasi Fujer Hujumlari - tez hisoblash algoritmidan foydalanish Gröbner asoslari polinom tenglamalari tizimining. Fugère 2002 yilda 96 soat ichida HFE chaqirig'ini 1 marta buzgan, 2003 yilda esa Fujere va Joux HFE xavfsizligi bo'yicha birgalikda ishlagan.^[1]

Adabiyotlar

• Nikolas T. Kurtua, Magnus Daum va Patrik Felke, HFE, HFEv- va Kvarts xavfsizligi to'g'risida
• Andrey Sidorenko, Yashirin dala tenglamalari, EIDMA seminari 2004 Technische Universiteit Eindhoven
• Yvo G. Desmet, Public Key Cryptography-PKC 2003 yil, ISBN  3-540-00324-X