Nolinchi kriptografiyani kuzatib boring - Trace zero cryptography

1998 yilda Gerxard Frey birinchi bo'lib foydalanishni taklif qildi nol navlarini kuzatish kriptografik maqsadda. Ushbu navlar a ga nisbatan past darajadagi giperelliptik egri chiziq bo'yicha bo'linuvchi sinf guruhining kichik guruhlari cheklangan maydon. Ushbu guruhlardan tashkil etish uchun foydalanish mumkin assimetrik kriptografiya yordamida alohida logaritma kriptografik ibtidoiy sifatida muammo.

Trace nol navlari elliptik egri chiziqlarga qaraganda skalyar ko'paytma ko'rsatkichini yaxshiroq ko'rsatadi. Bu esa elliptik egri chiziqlar bilan taqqoslaganda 3 omil bilan hisob-kitoblarni tezlashtirishi va shu sababli kriptosistemani tezlashtirishi mumkin bo'lgan ushbu guruhlarda tezkor arifmetikani amalga oshirishga imkon beradi.

Yana bir afzallik shundaki, kriptografik jihatdan tegishli o'lchamdagi guruhlar uchun Frobenius endomorfizmining xarakterli polinomidan foydalanib, guruhning tartibini hisoblash mumkin. Bu shunday emas, masalan egri chiziqli kriptografiya asosiy maydon ustidagi elliptik egri chiziqning guruhlari kriptografik maqsadda ishlatilganda.

Biroq iz elementi nol xilligini ifodalash uchun elliptik yoki giperelliptik egri chiziqlar bilan taqqoslaganda ko'proq bitlar kerak bo'ladi. Yana bir kamchilik - bu TZV ning xavfsizligini kamaytirish mumkinligi ¹/₆^th qopqoq hujumi yordamida bit uzunligini.

Matematik fon

A giperelliptik egri chiziq C jins g asosiy maydon ustida ${displaystyle mathbb {F} _ {q}}$ qayerda q = pⁿ (p tub) toq xarakteristikasi quyidagicha aniqlanadi

{displaystyle C: ~ y ^ {2} + h (x) y = f (x),}

qayerda f monik, deg (f) = 2g + 1 va deg (h) G. Egri chiziqda kamida bittasi bor ${displaystyle mathbb {F} _ {q}}$ - ratsional Weierstraßpoint.

The Jacobian xilma-xilligi ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ ning C barcha cheklangan kengaytmalar uchun ${displaystyle mathbb {F} _ {q ^ {n}}}$ ideal sinf guruhiga izomorf ${displaystyle operator nomi {Cl} (C / mathbb {F} _ {q ^ {n}})}$ . Bilan Mumford vakili elementlarini ifodalash mumkin ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ bir juft polinom bilan [u, v], qayerda siz, v ∈ ${displaystyle mathbb {F} _ {q ^ {n}} [x]}$ .

The Frobenius endomorfizmi σ elementda ishlatiladi [u, v] ning ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ ushbu elementning har bir koeffitsientining kuchini oshirish q: σ ([u, v]) = [siz^q(x), v^q(x)]. Ushbu endomorfizmga xos polinom quyidagi shaklga ega:

{displaystyle chi (T) = T ^ {2g} + a_ {1} T ^ {2g-1} + cdots + a_ {g} T ^ {g} + cdots + a_ {1} q ^ {g-1} T + q ^ {g},}

qaerda a_men ℤ ichida

Bilan Xasse-Vayl teoremasi har qanday kengaytma maydonining guruh buyurtmasini olish mumkin ${displaystyle mathbb {F} _ {q ^ {n}}}$ murakkab ildizlardan foydalanib by_men χ (ningT):

{displaystyle | J_ {C} (mathbb {F} _ {q ^ {n}}) | = prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})}

Ruxsat bering D. ning elementi bo'lishi ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ ning C, keyin ning endomorfizmini aniqlash mumkin ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ , deb nomlangan D. izi:

{displaystyle operator nomi {Tr} (D) = sum _ {i = 0} ^ {n-1} sigma ^ {i} (D) = D + sigma (D) + cdots + sigma ^ {n-1} (D )}

Ushbu endomorfizmga asoslanib, Jacobian xilma-xilligini kichik guruhga kamaytirish mumkin G har bir element nolga teng bo'lgan xususiyat bilan:

{displaystyle G = {Din J_ {C} (mathbb {F} _ {q ^ {n}}) ~ | ~ {ext {Tr}} (D) = {extbf {0}}}, ~~~ ({ extbf {0}} {ext {neytral element in}} J_ {C} (mathbb {F} _ {q ^ {n}})}

G iz endomorfizmining yadrosi va shu tariqa G deb nomlangan guruhdir nol (sub) xilma-xilligini kuzatish (TZV) ning ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ .

Ning kesishishi G va ${displaystyle J_ {C} (mathbb {F} _ {q})}$ tomonidan ishlab chiqarilgan n-ning harakatlanish elementlari ${displaystyle J_ {C} (mathbb {F} _ {q})}$ . Agar eng katta umumiy bo'luvchi bo'lsa ${displaystyle gcd (n, | J_ {C} (mathbb {F} _ {q}) |) = 1}$ kesishma bo'sh va guruh tartibini hisoblash mumkin G:

{displaystyle | G | = {dfrac {| J_ {C} (mathbb {F} _ {q ^ {n}}) |} {| J_ {C} (mathbb {F} _ {q}) |}} = {dfrac {prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})} {prod _ {i = 1} ^ {2g} (1- au _ {i})} }}

Kriptografik dasturlarda ishlatiladigan haqiqiy guruh kichik guruhdir G₀ ning G katta buyurtmaning l. Ushbu guruh bo'lishi mumkin G o'zi.^[1]^[2]

TZV uchun uch xil kriptografik ahamiyatga ega bo'lgan holatlar mavjud:^[3]

g = 1, n = 3
g = 1, n = 5
g = 2, n = 3

Arifmetik

TZV guruhida ishlatiladigan arifmetik G₀ butun guruh uchun arifmetikaga asoslangan ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ , Ammo foydalanish mumkin Frobenius endomorfizmi σ skalyar ko'paytishni tezlashtirish uchun. Buni arxivlash mumkin, agar G₀ tomonidan yaratilgan D. tartib l keyin σ (D) = sD, ba'zi bir butun sonlar uchun s. Ushbu TZV holatlari uchun s quyidagicha hisoblash mumkin, qaerda a_men Frobenius endomorfizmining xarakterli polinomidan kelib chiqadi:

Uchun g = 1, n = 3: ${displaystyle s = {dfrac {q-1} {1-a_ {1}}} {mod {ell}}}$
Uchun g = 1, n = 5: ${displaystyle s = {dfrac {q ^ {2} -q-a_ {1} ^ {2} q + a_ {1} q + 1} {q-2a_ {1} q + a_ {1} ^ {3} -a_ {1} ^ {2} + a_ {1} -1}} {mod {ell}}}$
Uchun g = 2, n = 3: ${displaystyle s = - {dfrac {q ^ {2} -a_ {2} + a_ {1}} {a_ {1} q-a_ {2} +1}} {mod {ell}}}$

Buni bilib, har qanday skalar ko'paytmasini almashtirish mumkin mD (| m | ≤ l / 2) bilan:

{displaystyle m_ {0} D + m_ {1} sigma (D) + cdots + m_ {n-1} sigma ^ {n-1} (D), ~~~~ {ext {where}} m_ {i} = O (ell ^ {1 / (n-1)}) = O (q ^ {g})}

Ushbu hiyla bilan ko'p miqdordagi skaler mahsulotni taxminan 1 / (ga) kamaytirish mumkinn − 1)^th hisoblash uchun zarur bo'lgan ikki baravar ko'payish mD, agar nazarda tutilgan doimiylar etarlicha kichik bo'lsa.^[3]^[2]

Xavfsizlik

Hujjatlar natijalariga ko'ra izsiz nol kichik navlarga asoslangan kriptografik tizimlarning xavfsizligi^[2]^[3] past darajadagi giperelliptik egri chiziqlar xavfsizligi bilan solishtirish mumkin g ' ustida ${displaystyle mathbb {F} _ {p '}}$ , qayerda p ' ~ (n − 1)(g / g ' ) uchun | G | ~ 128 bit.

Qaerda bo'lgan holatlar uchun n = 3, g = 2 va n = 5, g = 1 xavfsizlikni kamida 6 bitga kamaytirish mumkin, bu erda | G | ~ 2²⁵⁶, chunki bunga amin bo'lish mumkin emas G 6-sonli egri chiziqning yakobiyanida joylashgan bo'lib, shunga o'xshash maydonlar uchun 4-turdagi egri chiziqlarning xavfsizligi unchalik xavfsiz emas.

Izsiz nolli kripto tizimiga hujumni yoping

Hujum^[4]shuni ko'rsatadiki, 2 yoki 3 dan farqli xarakterli sonli maydonlar bo'yicha 2-turdagi nol guruhlar izidagi DLP va 3-darajali maydon kengaytmasi 0 darajadagi sinf guruhida DLP ga aylanishi mumkin, eng ko'pi 6 dan ortiq jinslar. asosiy maydon. Ushbu yangi sinf guruhida DLP-ga indeksni hisoblash usullari bilan hujum qilish mumkin. Bu bit uzunligini qisqartirishga olib keladi ¹/₆^th.

Izohlar

^ Frey, Gerxard; Lange, Tanja (2005). Ochiq kalit kriptografiyasining matematik asoslari (PDF). Seminarlar va Kongresslar. 11. 41-73 betlar.
^ ^a ^b ^v Lange, Tanja (2003). Kriptosistemalar uchun nol subvarietyni kuzatib boring.
^ ^a ^b ^v Avanzi, Roberto M.; Sezena, Emanuele (2008). "Kriptografik dasturlar uchun xarakteristik 2 maydonlari bo'yicha nol navlarni kuzatib boring" (PDF). Algebraik geometriya va uning qo'llanilishi: 188–215.
^ Diem, Klaus; Scholten, Jasper. Iz-nol kriptosistemaga hujum.

Adabiyotlar

Wienke, Malt; Paar, Kristof (2008 yil 17-fevral). Iz-nol navlari bo'yicha kriptografiya (PDF). Rur universiteti Bochum.
Sutherland, Endryu V. (2007). "101 foydali iz nolli navlari". Massachusets texnologiya instituti.

[1] Frey, Gerxard; Lange, Tanja (2005). Ochiq kalit kriptografiyasining matematik asoslari (PDF). Seminarlar va Kongresslar. 11. 41-73 betlar.

[subvariety-2] v Lange, Tanja (2003). Kriptosistemalar uchun nol subvarietyni kuzatib boring.

[charactistic2-3] v Avanzi, Roberto M.; Sezena, Emanuele (2008). "Kriptografik dasturlar uchun xarakteristik 2 maydonlari bo'yicha nol navlarni kuzatib boring" (PDF). Algebraik geometriya va uning qo'llanilishi: 188–215.

[4] Diem, Klaus; Scholten, Jasper. Iz-nol kriptosistemaga hujum.

[1]

[2]

[3]

[4]