Supersingular izogeniya kalitlari almashinuvi - Supersingular isogeny key exchange - Wikipedia

Supersingular izogeniya Diffie - Hellman kalit almashinuvi (SIDH) a kvantdan keyingi kriptografik algoritm boshqa tomon uchun xavfli bo'lgan aloqa kanali orqali ikki tomon o'rtasida maxfiy kalitni o'rnatish uchun ishlatiladi. Bu o'xshash Diffie-Hellman kalit almashinuvi, lekin a yurishlariga asoslanadi supersingular izogeniya grafigi va qarshilik ko'rsatish uchun mo'ljallangan kriptanalitik hujum egalik qilgan dushman tomonidan a kvantli kompyuter. SIDH kvantdan keyingi barcha kalit almashinuvlarning eng kichik o'lchamlaridan biriga ega; siqish bilan SIDH 2688-bitdan foydalanadi^[1] 128 bitli kvantdagi ochiq kalitlar xavfsizlik darajasi. SIDH shu kabi tizimlardan o'zini ajratib turadi NTRU va Ring-LWE qo'llab-quvvatlash orqali oldinga mukammal maxfiylik, buzilgan uzoq muddatli kalitlarning eski aloqa seanslarining maxfiyligini buzishiga to'sqinlik qiluvchi xususiyat. Ushbu xususiyatlar SIDHni almashtirish uchun tabiiy nomzodga aylantiradi Diffie-Hellman (DHE) va Diffie-Hellman elliptik egri chizig'i (ECDHE), ular Internet-aloqada keng qo'llaniladi.

Kirish

Muayyan sinflar uchun ishlaydigan algoritmlar kvantli kompyuterlar tabiiy ravishda pastroqqa erishishga qodir vaqtning murakkabligi klassik kompyuterlarga qaraganda. Anavi, kvant algoritmlari an'anaviy kompyuterda ishlaydigan eng samarali algoritmga qaraganda ma'lum muammolarni tezroq hal qilishi mumkin. Masalan, Shor algoritmi butun sonni omil qilishi mumkin N yilda polinom vaqti, eng taniqli faktoring klassik algoritmi bo'lsa-da umumiy sonli elak, ishlaydi sub-eksponent vaqt. Bu juda muhimdir ochiq kalit kriptografiyasi chunki xavfsizligi RSA faktoring butun sonlarini bajarib bo'lmaydiganligiga bog'liq butun sonni faktorizatsiya qilish muammosi. Shor algoritmi ham samarali hal qilishi mumkin diskret logarifma muammosi, bu xavfsizlik uchun asosdir Diffie-Hellman, Diffie-Hellman elliptik egri chizig'i, elliptik egri chiziq DSA, Egri chiziq 25519, ed25519 va ElGamal. Kvant kompyuterlari hozirda yangi boshlang'ich bosqichida bo'lishiga qaramay, kvant kompyuterlarining doimiy rivojlanishi va zamonaviy kriptografik protokollarni buzish uchun nazariy qobiliyati (masalan TLS / SSL ) kvantdan keyingi kriptografiyaning rivojlanishiga turtki bo'ldi.^[2]

SIDH 2011 yilda De Feo, Jao va Plut tomonidan yaratilgan.^[3] Bu an'anaviy foydalanadi elliptik egri chiziq operatsiyalar va patentlanmagan. SIDH beradi oldinga mukammal maxfiylik va shuning uchun uzoq muddatli shaxsiy kalitlarning xavfsizligiga ishonmaydi. Oldinga maxfiylik shifrlangan kommunikatsiyalarning uzoq muddatli xavfsizligini yaxshilaydi va himoyalanishga yordam beradi ommaviy kuzatuv va shunga o'xshash zaifliklar ta'sirini kamaytiradi Yurak qoni.^[4][5]

Fon

The j-o'zgarmas Vayderstrass tenglamasi tomonidan berilgan elliptik egri chiziq ${ displaystyle y ^ {2} = x ^ {3} + ax + b}$ quyidagi formula bilan berilgan:

${ displaystyle j (E) = 1728 { frac {4a ^ {3}} {4a ^ {3} + 27b ^ {2}}}}$.

Izomorfik egri chiziqlar bir xil j-invariantga ega; algebraik yopiq maydon ustida bir xil j-invariantli ikkita egri chiziq izomorfdir.

Supersingular izogeniya Diffie-Hellman protokoli (SIDH) tepalari (izomorfizm sinflari) bo'lgan grafik bilan ishlaydi. supersingular elliptik egri chiziqlar va ularning egri chiziqlari bu egri chiziqlar orasidagi izogeniyalardir. An izogeniya ${ displaystyle phi: E dan E '}$ elliptik egri chiziqlar orasida ${ displaystyle E}$ va ${ displaystyle E '}$ a ratsional xarita bu ham guruh homomorfizmi. Agar ajratiladigan, ${ displaystyle phi}$ uning bilan belgilanadi yadro nishon egri izomorfizmigacha ${ displaystyle E '}$.

SIDH-ni o'rnatish formaning asosiy qismidir ${ displaystyle p = l_ {A} ^ {e_ {A}} cdot l_ {B} ^ {e_ {B}} cdot f mp 1}$, har xil (kichik) tub sonlar uchun ${ displaystyle l_ {A}}$ va ${ displaystyle l_ {B}}$, (katta) ko'rsatkichlar ${ displaystyle e_ {A}}$ va ${ displaystyle e_ {B}}$va kichik kofaktor ${ displaystyle f}$, supersingular elliptik egri bilan birga ${ displaystyle E}$ aniqlangan ${ displaystyle mathbb {F} _ {p ^ {2}}}$. Bunday egri chiziqda ikkita katta burama kichik guruh mavjud, ${ displaystyle E [l_ {A} ^ {e_ {A}}]}$ va ${ displaystyle E [l_ {B} ^ {e_ {B}}]}$, obuna ko'rsatilgandek, mos ravishda Elis va Bobga tayinlangan. Har bir tomon protokolni o'zlarining torsion kichik guruhining (maxfiy) tasodifiy tsiklik kichik guruhini tanlash va tegishli (maxfiy) izogeniyasini hisoblash bilan boshlaydi. Keyin ular boshqa tomonga o'z izogeniyalarining maqsadli egri chizig'idagi tenglamani va shu izogeniya ostidagi boshqa tomonning burama kichik guruhi tasviri to'g'risidagi ma'lumotlarni nashr etishadi yoki taqdim etishadi. Bu ikkalasiga ham yangi izogeniyalarni xususiy ravishda hisoblash imkonini beradi ${ displaystyle E}$ ularning yadrolari birgalikda ikkita maxfiy tsiklik kichik guruhlar tomonidan ishlab chiqariladi. Ushbu ikkita yangi izogeniyaning yadrolari bir-biriga mos kelganligi sababli ularning maqsad egri chiziqlari izomorfdir. Ushbu maqsad egri chiziqlarining umumiy j-o'zgarmasligi keyinchalik kerakli umumiy sir sifatida qabul qilinishi mumkin.

Sxemaning xavfsizligi kichikroq burama kichik guruhga bog'liq bo'lgani uchun, tanlash tavsiya etiladi ${ displaystyle l_ {A} ^ {e_ {A}} taxminan l_ {B} ^ {e_ {B}}}$.

De Feo-ning "Izogeniya asosidagi kriptografiya matematikasi" maqolasi ushbu mavzu uchun ajoyib ma'lumotdir.^[6]

Xavfsizlik

SIDH xavfsizligi bir xil sonli nuqtalarga ega bo'lgan ikkita supersingular elliptik egri chiziqlar orasidagi izogenez xaritasini topish muammosi bilan chambarchas bog'liq. De Feo, Jao va Plut, SIDHga qarshi eng yaxshi hujum bu bog'liqlikni hal qilishni taklif qilmoqda tirnoqlarni topish muammosi, shuning uchun murakkablik O (p.)^1/4) klassik kompyuterlar va O uchun (p.)^1/6) uchun kvantli kompyuterlar. Bu 768-bitli (p) SIDH 128-bit xavfsizlik darajasiga ega bo'lishidan dalolat beradi.^[3] 2014 yilda Delfs va Galbrayt tomonidan izogeniya xaritalash muammosini o'rganish O (p.) Ni tasdiqladi^1/4) klassik kompyuterlar uchun xavfsizlik tahlili.^[7] Klassik xavfsizlik, O (p.)^1/4), SIDH ning Biasse, Jao va Sankar hamda Galbrayt, Petit, Shani va Ti ishlarida tasdiqlangan.^[8][9]

Samaradorlik

Kalit almashinuvi jarayonida A va B sub'ektlari har biri 2 koeffitsientli ma'lumotlarni uzatadi (mod p²) elliptik egri chiziq va 2 elliptik egri nuqtani aniqlash. Har bir elliptik egri koeffitsienti jurnalni talab qiladi₂p² bitlar. Har bir elliptik egri nuqtani jurnalga uzatish mumkin₂p²+1 bit, shuning uchun uzatish 4log₂p² + 4 bit. Bu 768-bitli modul uchun 6144 bit (128-bit xavfsizlik). Biroq, bu kalitlarni siqish texnikasi yordamida 2640 bitgacha (330 bayt) qisqartirilishi mumkin, ulardan eng so'nggii mualliflar Kostello, Jao, Longa, Naehrig, Renes va Urbanikning so'nggi ishlarida uchraydi.^[10] Ushbu siqish texnikasi bilan SIDH an'anaviy 3072-bitli RSA imzolari yoki Diffie-Hellman kalit almashinuviga o'xshash tarmoqli kengligi talabiga ega. Ushbu kichik bo'shliq talablari, masalan, qattiq bo'shliq talabiga ega bo'lgan kontekstga SIDH-ni qo'llaydi Bitcoin yoki Tor. Torning ma'lumotlar kataklari uzunligi 517 baytdan kam bo'lishi kerak, shuning uchun ular 330 baytli SIDH tugmachalarini saqlashlari mumkin. Aksincha, NTRUEncrypt 128 bitli xavfsizlikka erishish uchun taxminan 600 baytni almashishi kerak va Tor ichida hujayra hajmini oshirmasdan foydalanib bo'lmaydi.^[11]

2014 yilda Vaterloo universiteti tadqiqotchilari SIDH dasturiy ta'minotini ishlab chiqdilar. Ular qisman optimallashtirilgan kodlarini 2,4 gigagertsli tezlikda ishlaydigan x86-64 protsessorida ishlashdi. 768-bitli modul uchun ular 200 millisekundalarda kalit almashinuv hisob-kitoblarini bajarishga muvaffaq bo'lishdi, shu bilan SIDH hisoblashda amaliy ekanligini namoyish etishdi.^[12]

2016 yilda Microsoft tadqiqotchilari doimiy ravishda ishlaydigan SIDH dasturini joylashtirdilar (shu bilan vaqt hujumlaridan himoya qiladi) va hozirgi kungacha eng samarali dastur hisoblanadi. Ular quyidagilarni yozmoqdalar: "Ochiq kalitlarning hajmi atigi 564 baytni tashkil etadi, bu kvantdan keyingi mashhur kalit almashinuv alternativalarining aksariyat qismidan sezilarli darajada kichik. Oxir oqibat bizning dasturiy ta'minotimizning hajmi va tezligi SIDH ning post-kvant sifatida kuchli potentsialini namoyish etadi asosiy almashinuv nomzodi va biz ushbu natijalar yanada kengroq kriptanalitik harakatlarni rag'batlantiradi deb umid qilamiz.^[13] Ularning dasturiy ta'minoti bu erda joylashtirilgan.

2016 yilda Florida Atlantika universiteti tadqiqotchilari SIDH ning samarali ARM dasturlarini ishlab chiqdilar va afine va proektiv koordinatalarni taqqoslashni ta'minladilar.^[14][15] 2017 yilda Florida Atlantika universiteti tadqiqotchilari SIDHning birinchi FPGA dasturlarini ishlab chiqdilar.^[16]

Supersingular izogeniya Diffie-Hellman usuli

SIDHning bir necha bosqichlari murakkab izogeniya hisob-kitoblarini o'z ichiga olgan bo'lsa, A va B tomonlari uchun SIDHning umumiy oqimi Diffie-Hellman kalit almashinuvi yoki uning elliptik egri variantini yaxshi biladiganlar uchun to'g'ri keladi.

Sozlash

Bular tarmoqdagi hamma baham ko'rishi mumkin bo'lgan umumiy parametrlar yoki sessiya boshida A va B tomonlari bilan kelishib olishlari mumkin.

1. Shaklning asosiy qismi ${ displaystyle p = w_ {A} ^ {e_ {A}} cdot w_ {B} ^ {e_ {B}} cdot f pm 1.}$
2. Supersingular elliptik egri chiziq ${ displaystyle E}$ ustida ${ displaystyle mathbb {F} _ {p ^ {2}}}$.
3. Ruxsat etilgan elliptik nuqtalar ${ displaystyle P_ {A}, Q_ {A}, P_ {B}, Q_ {B}}$ kuni ${ displaystyle E}$.
4. Ning tartibi ${ displaystyle P_ {A}}$ va ${ displaystyle Q_ {A}}$ bu ${ displaystyle (w_ {A}) ^ {e_ {A}}}$. Ning tartibi ${ displaystyle P_ {B}}$ va ${ displaystyle Q_ {B}}$ bu ${ displaystyle (w_ {B}) ^ {e_ {B}}}$.

Kalit almashinuvi

Kalit almashinuvida A va B tomonlar har biri umumiy Eliptik egri chiziqdan izogeniya hosil qiladi. Ularning har biri buni o'z izogeniyasining yadrosi bo'ladigan tasodifiy nuqta yaratish orqali amalga oshiradi. Ularning izogenezining yadrosi kengaytiriladi ${ displaystyle R_ {A}}$ va ${ displaystyle R_ {B}}$ navbati bilan. Amaldagi turli xil juftliklar A va B tomonlarning turli xil, almashinmaydigan izogeniyalarni yaratishini ta'minlaydi. Tasodifiy nuqta (${ displaystyle R_ {A}}$, yoki ${ displaystyle R_ {B}}$) izogeniyalar yadrosida nuqtalarning tasodifiy chiziqli birikmasi sifatida yaratilgan ${ displaystyle P_ {A}}$, ${ displaystyle Q_ {A}}$ va ${ displaystyle P_ {B}}$, ${ displaystyle Q_ {B}}$.

Foydalanish ${ displaystyle R_ {A}}$, yoki ${ displaystyle R_ {B}}$, A va B partiyalar izogeniyalar yaratish uchun Velu formulalaridan foydalanadilar ${ displaystyle phi _ {A}}$ va ${ displaystyle phi _ {B}}$ navbati bilan. Shundan kelib chiqib ular juftliklar tasvirini hisoblaydilar ${ displaystyle P_ {A}}$, ${ displaystyle Q_ {A}}$ yoki ${ displaystyle P_ {B}}$, ${ displaystyle Q_ {B}}$ ostida ${ displaystyle phi _ {B}}$ va ${ displaystyle phi _ {A}}$ navbati bilan izogeniyalar.

Natijada, A va B ikkitadan juftlikka ega bo'ladi ${ displaystyle phi _ {B} (P_ {A})}$, ${ displaystyle phi _ {B} (Q_ {A})}$ va ${ displaystyle phi _ {A} (P_ {B})}$, ${ displaystyle phi _ {A} (Q_ {B})}$ navbati bilan. Endi A va B ushbu juft juftlarni aloqa kanali orqali almashadilar.

Endi A va B yangi izogeniya yadrosi uchun asos sifatida olgan juftlikdan foydalanadi. Ular yaratgan izogeniya yadrosida nuqta hosil qilish uchun ular olgan ballari bilan yuqorida ishlatgan chiziqli koeffitsientlardan foydalanadilar. Ularning har biri ballarni hisoblashadi ${ displaystyle S_ {BA}}$ va ${ displaystyle S_ {AB}}$ va foydalaning Velu formulalari yangi izogeniyalarni yaratish.

Kalit almashinuvini yakunlash uchun A va B ushbu ikkita yangi izogeniya ostida ikkita yangi elliptik egri chiziqlar koeffitsientlarini hisoblab chiqadi. Keyin ular bu egri chiziqlarning j-o'zgarmasligini hisoblaydilar. Agar uzatishda xatolar bo'lmasa, A hosil qilgan egri chiziqning j-o'zgarmasligi B hosil qilgan egri chiziqning j-o'zgarmasligiga teng bo'ladi.

Notatsion ravishda A va B tomonlari o'rtasida SIDH kalit almashinuvi quyidagicha ishlaydi:

1A. A tasodifiy ikkita butun sonni hosil qiladi ${ displaystyle m_ {A}, n_ {A} <(w_ {A}) ^ {e_ {A}}.}$

2A. A ishlab chiqaradi ${ displaystyle R_ {A}: = m_ {A} cdot (P_ {A}) + n_ {A} cdot (Q_ {A}).}$

3A. A nuqtadan foydalanadi ${ displaystyle R_ {A}}$ izogeniya xaritasini yaratish ${ displaystyle phi _ {A}: E rightarrow E_ {A}}$ va egri chiziq ${ displaystyle E_ {A}}$ uchun izogen ${ displaystyle E.}$

4A. A amal qiladi ${ displaystyle phi _ {A}}$ ga ${ displaystyle P_ {B}}$ va ${ displaystyle Q_ {B}}$ ikkita nuqtani shakllantirish ${ displaystyle E_ {A}: phi _ {A} (P_ {B})}$ va ${ displaystyle phi _ {A} (Q_ {B}).}$

5A. A B ga yuboradi ${ displaystyle E_ {A}, phi _ {A} (P_ {B})}$va ${ displaystyle phi _ {A} (Q_ {B}).}$

1B - 4B: A1 dan A4 gacha, ammo A va B obunalari almashtirilgan.

5B. B A ga yuboradi ${ displaystyle E_ {B}, phi _ {B} (P_ {A})}$va ${ displaystyle phi _ {B} (Q_ {A}).}$

6A. A bor ${ displaystyle m_ {A}, n_ {A}, phi _ {B} (P_ {A})}$va ${ displaystyle phi _ {B} (Q_ {A})}$ va shakllari ${ displaystyle S_ {BA}: = m_ {A} ( phi _ {B} (P_ {A})) + n_ {A} ( phi _ {B} (Q_ {A})).}$

7A. A foydalanadi ${ displaystyle S_ {BA}}$ izogeniya xaritasini yaratish ${ displaystyle psi _ {BA}}$.

8A. A foydalanadi ${ displaystyle psi _ {BA}}$ elliptik egri chiziq hosil qilish uchun ${ displaystyle E_ {BA}}$ uchun izogen bo'lgan ${ displaystyle E}$.

9A. Hisoblash ${ displaystyle K: = { text {j-invariant}} (j_ {BA})}$ egri chiziq ${ displaystyle E_ {BA}}$.

6B. Xuddi shunday, B ham bor ${ displaystyle m_ {B}, n_ {B}, phi _ {A} (P_ {B})}$va ${ displaystyle phi _ {A} (Q_ {B})}$ va shakllari ${ displaystyle S_ {AB} = m_ {B} ( phi _ {A} (P_ {B})) + n_ {B} ( phi _ {A} (Q_ {B}))}$.

7B. B foydalanadi ${ displaystyle S_ {AB}}$ izogeniya xaritasini yaratish ${ displaystyle psi _ {AB}}$.

8B. B foydalanadi ${ displaystyle psi _ {AB}}$ elliptik egri chiziq hosil qilish uchun ${ displaystyle E_ {AB}}$ uchun izogen bo'lgan ${ displaystyle E}$.

9B. B hisoblab chiqadi ${ displaystyle K: = { text {j-invariant}} (j_ {AB})}$ egri chiziq ${ displaystyle E_ {AB}}$.

Egri chiziqlar ${ displaystyle E_ {AB}}$ va ${ displaystyle E_ {BA}}$ bir xil j-invariantga ega bo'lishi kafolatlanadi. Funktsiyasi ${ displaystyle K}$ umumiy kalit sifatida ishlatiladi.^[3]

Namuna parametrlari

Quyidagi parametrlar De Feo va boshqalar tomonidan misol sifatida olingan:^[3]

w bilan kalit almashinish uchun p = prime_A = 2, w_B = 3, e_A = 63, e_B = 41, va f = 11. Shunday qilib p = (2⁶³·3⁴¹·11) - 1.

E₀ = kalit almashinuvi uchun asosiy (boshlang'ich) egri = y² = x³ + x

Kalit almashinuvni belgilaydigan hujjat mualliflaridan biri Luka De Feo ushbu va boshqa parametrlar uchun kalit almashinuvni amalga oshiradigan dasturni joylashtirdi.^[17]

Shunga o'xshash tizimlar, imzolar va ulardan foydalanish

SIDH uchun salafiy 2006 yilda Rostovtsev va Stolbunov tomonidan nashr etilgan. Ular elliptik egri izogeniyalar asosida birinchi Diffie-Hellman o'rnini bosdilar. De Feo, Jao va Plut usullaridan farqli o'laroq, Rostovtsev va Stolbunov usuli oddiy elliptik egri chiziqlardan foydalangan.^[18] va subekspentsial kvant hujumiga ega ekanligi aniqlandi.^[19]

2014 yil mart oyida Integrated Service Network uchun Xitoy Davlat Key Laboratoriyasi va Xidian universiteti tadqiqotchilari SIDH xavfsizligini raqamli imzo shaklida kuchli belgilangan tekshirgich bilan kengaytirdilar.^[20] 2014 yil oktyabr oyida Vaterloo Universitetidan Jao va Souxarev elliptik egri izogeniyalar yordamida belgilangan tekshirgich bilan inkor etib bo'lmaydigan imzolarni yaratishning muqobil usulini taqdim etdilar.^[21]

Adabiyotlar