Shifrlash - NTRUEncrypt

The Shifrlash ochiq kalit kriptosistemasi, deb ham tanilgan NTRU shifrlash algoritmi, a panjara asosida muqobil RSA va ECC va ga asoslangan eng qisqa vektor muammosi panjara ichida (uni ishlatish singanligi ma'lum emas kvantli kompyuterlar ).

Bu taxmin qilingan qiyinchiliklarga bog'liq faktoring qisqartirilgan ma'lum polinomlar polinom halqasi juda kichik koeffitsientlarga ega bo'lgan ikki polinomning bir qismiga. Kriptosistemani buzish, agar u teng bo'lmasa ham, algoritmik masalasi bilan chambarchas bog'liqdir panjarani kamaytirish albatta panjaralar. Ba'zi nashr etilgan hujumlarning oldini olish uchun parametrlarni sinchkovlik bilan tanlash kerak.

Ham shifrlash, ham parol hal qilishda oddiy polinom ko'paytmasi qo'llanilganligi sababli, bu operatsiyalar RSA kabi boshqa assimetrik shifrlash sxemalari bilan taqqoslaganda juda tez ElGamal va egri chiziqli kriptografiya. Biroq, NTRUEncrypt hali taqqoslanadigan miqdordagi kriptografik tahlilni joylashtirilgan shaklda o'tkazmagan.

Tegishli algoritm NTRUSign elektron raqamli imzo algoritm.

Xususan, NTRU operatsiyalari kesilgan polinom halqasidagi ob'ektlarga asoslangan konvolyutsiyani ko'paytirish va halqadagi barcha polinomlarga ega tamsayı koeffitsientlar va eng ko'p daraja N-1:

NTRU aslida kriptosistemalarning parametrlangan oilasi; har bir tizim uchta butun parametr bilan belgilanadi (N, p, q) bu maksimal darajani ifodalaydi kesilgan halqadagi barcha polinomlar uchun R, mos ravishda kichik modul va katta modul, bu erda u taxmin qilingan N bu asosiy, q har doimgidan kattaroqdir pva p va q bor koprime; va polinomlarning to'rtta to'plami va (yopiq kalitning polinom qismi, ochiq kalitni yaratish uchun polinom, navbati bilan xabar va ko'r qiymat), ko'pi bilan hamma daraja .

Tarix

NTRUEncrypt ochiq kalitli kriptosistemasi nisbatan yangi kriptosistema bo'lib, oddiygina NTRU deb nomlangan tizimning birinchi versiyasi 1996 yil atrofida uchta matematik tomonidan ishlab chiqilgan (Jeffri Xoffshteyn, Jil Pifer va Jozef X. Silverman ). 1996 yilda bu matematiklar bilan birgalikda Daniel Lieman NTRU Cryptosystems, Inc kompaniyasiga asos solgan va ularga patent berilgan[1] (endi muddati tugagan) kriptosistemada.

So'nggi o'n yil ichida odamlar kriptotizimni takomillashtirish ustida ishlamoqdalar. Kriptosistemaning birinchi taqdimotidan boshlab tizimning ishlashi va xavfsizligini yaxshilash uchun ba'zi o'zgarishlar kiritildi. Ishlashning aksariyat yaxshilanishlari jarayonni tezlashtirishga qaratilgan edi. 2005 yilgacha NTRUEncrypt parolini hal qilishda xatolarni tavsiflovchi adabiyotlarni topish mumkin. Xavfsizlikka kelsak, NTRUEncrypt-ning birinchi versiyasidan boshlab, hozirda ma'lum bo'lgan barcha hujumlar va hisoblash quvvatining oqilona o'sishi uchun xavfsiz ko'rinadigan yangi parametrlar joriy etildi.

Endi tizim IEEE P1363 standartlariga to'r asosidagi ochiq kalitli kriptografiya texnik shartlari bo'yicha to'liq qabul qilindi (IEEE P1363.1 NTRUEncrypt ochiq kalit kriptosistemasining tezligi tufayli (qarang http://bench.cr.yp.to natijalarni taqqoslash uchun) va uning past xotiradan foydalanish (qarang quyida )[shubhali ], u mobil qurilmalar va kabi dasturlarda ishlatilishi mumkin Smart-kartalar. 2011 yil aprel oyida NTRUEncrypt moliyaviy xizmatlar sohasida foydalanish uchun X9.98 standarti sifatida qabul qilindi.[2]

Ochiq kalit yaratish

Elisdan Bobga maxfiy xabar yuborish uchun ommaviy va shaxsiy kalitni yaratish kerak. Ochiq kalitni Elis ham, Bob ham biladi, shaxsiy kalit esa faqat Bobga ma'lum. Ikki polinomni juftligini yaratish uchun f va g, eng yuqori daraja bilan va koeffitsientlar bilan {-1,0,1} talab qilinadi. Ularni polinomlarning qoldiq sinflari vakili sifatida ko'rib chiqish mumkin yilda R. Polinom teskari modul talab qiladigan qo'shimcha talabni qondirishi kerak q va modulo p (yordamida ishlatilgan Evklid algoritmi ) mavjud degan ma'noni anglatadi va ushlab turishi kerak.Shunday qilib tanlanganida f qaytarib bo'lmaydigan, Bob orqaga qaytib, boshqasini sinab ko'rishi kerak f.

Ikkalasi ham f va (va ) Bobning shaxsiy kaliti. Ochiq kalit h miqdorini hisoblashda hosil bo'ladi

Misol: Ushbu misolda parametrlar (N, p, q) qiymatlarga ega bo'ladi N = 11, p = 3 va q = 32 va shuning uchun polinomlar f va g eng ko'p daraja 10. tizim parametrlari (N, p, q) hammaga ma'lum. Polinomlar tasodifiy tanlangan, shuning uchun ular quyidagicha ifodalanadi

Evklid algoritmidan teskari f modul p va modulo qnavbati bilan hisoblab chiqilgan

Qaysi ochiq kalitni yaratadi h (Elis va Bob ham tanilgan) mahsulotni hisoblash

Shifrlash

Bobga maxfiy xabar yubormoqchi bo'lgan Elis o'z xabarini ko'pburchak shaklida qo'yadi m koeffitsientlari bilan . Shifrlashning zamonaviy dasturlarida xabar polinomini ikkilik yoki uchlik ko'rinishda tarjima qilish mumkin.Xabar polinomini yaratgandan so'ng, Elis tasodifiy polinomni tanlaydi r kichik koeffitsientlar bilan ({-1,0,1} to'plami bilan cheklanmagan), bu xabarni yashirishga qaratilgan.

Bobning ochiq kaliti bilan h shifrlangan xabar e hisoblanadi:

Ushbu shifrlangan matn Elisning xabarlarini yashiradi va Bobga xavfsiz tarzda yuborilishi mumkin.

Misol: Elis polinom sifatida yozilishi mumkin bo'lgan xabar yuborishni xohlaydi deb taxmin qiling

va tasodifiy tanlangan "ko'r qiymat" ni quyidagicha ifodalash mumkin

Shifrlangan matn e uning Bobga shifrlangan xabarini ifodalovchi ko'rinishga ega bo'ladi

Parolni hal qilish

Hech kim bilmaydi r xabarni hisoblashi mumkin m baholash orqali e - rh; shunday r Elis tomonidan oshkor qilinmasligi kerak. Ommaviy ma'lumotlardan tashqari, Bob o'zining shaxsiy kalitini ham biladi. U qanday qilib olishi mumkin m: Avval u shifrlangan xabarni ko'paytiradi e va uning shaxsiy kalitining bir qismi f

Polinomlarni qayta yozish orqali ushbu tenglama aslida quyidagi hisoblashni ifodalaydi:

Ning koeffitsientlarini tanlash o'rniga a 0 va q - 1 ular oraliqda tanlanadi [-q/2, q/ 2], asl xabar to'g'ri tiklanmasligi uchun, chunki Elis o'z xabarining koordinatalarini tanlaydi m oralig'ida [-p/2, p/ 2]. Bu shuni anglatadiki, ning barcha koeffitsientlari allaqachon intervalda yotadi [-q/2, q/ 2] chunki polinomlar r, g, f va m va asosiy p barchasi nisbatan kichik koeffitsientlarga ega q. Demak, modulni kamaytirish paytida barcha koeffitsientlar o'zgarishsiz qoladi q va asl xabar to'g'ri tiklanishi mumkin.

Keyingi qadam hisoblash bo'ladi a modul p:

chunki .

Bilish b Bob shaxsiy kalitning boshqa qismidan foydalanishi mumkin ko'paytmasi bilan Elisning xabarini tiklash b va

chunki mulk uchun talab qilingan .

Misol: Shifrlangan xabar e Elisdan Bobgacha polinom bilan ko'paytiriladi f

bu erda Bob intervaldan foydalanadi [-q/2, q/ 2] oralig'i o'rniga [0, q - 1] polinom koeffitsientlari uchun a asl xabar to'g'ri tiklanmasligi uchun.

Ning koeffitsientlarini kamaytirish a mod p natijalar

bu teng .

Oxirgi bosqichda natija ko'paytiriladi Bobning shaxsiy kalitidan asl xabar bilan yakunlanadi m

Elisning Bobga yuborgan asl xabarlari qaysi biri!

Hujumlar

NTRU taklifidan beri NTRUEncrypt ochiq kalit kriptosistemasiga bir nechta hujumlar uyushtirildi. Aksariyat hujumlar maxfiy kalitni topish orqali to'liq tanaffus qilishga qaratilgan f shunchaki xabarni tiklash o'rniga m.Agar f nolga teng bo'lmagan koeffitsientlarning juda ozligi ma'lum qo'pol kuch hujumi uchun barcha qadriyatlarni sinab ko'rish orqali f. Momo Havo yoki yo'qligini bilmoqchi bo'lganida f´ bu maxfiy kalit, u shunchaki hisoblab chiqadi . Agar u kichik koeffitsientlarga ega bo'lsa, bu maxfiy kalit bo'lishi mumkin fva Momo Havo sinovdan o'tkazishi mumkin f´ - bu o'z-o'zidan shifrlangan xabarni parolini ochish uchun foydalanadigan maxfiy kalit. g va agar bo'lsa, sinov qiling kichik qiymatlarga ega.

O'rnatish mumkin o'rtada hujum qaysi biri kuchliroq. Qidiruv vaqtini kvadrat ildiz bilan kesishi mumkin. Hujum mulkka asoslangan .

Momo Havo topmoqchi va shu kabi egalik qiladi va ular mulkka ega bo'ladilar

Agar f bor d bir va N-d nol, keyin Momo Havo barcha imkoniyatlarni yaratadi va unda ularning ikkalasi ham uzunlikka ega (masalan, qamrab oladi ning eng past koeffitsientlari f va eng yuqori) bilan d/ 2 kishi. Keyin u hisoblab chiqadi Barcha uchun va ularni birinchi k koordinatalari asosida qutilarga buyurtma qiladi. Shundan so'ng u barchasini hisoblab chiqadi va ularni faqat birinchi k koordinatalari asosida emas, balki birinchi k koordinatalariga 1 qo'shsangiz nima bo'lishiga qarab ularni qutilarga buyurtma qiladi. Keyin ikkalasini ham o'z ichiga olgan qutilarni tekshirasiz va va mulkni tekshiring ushlab turadi.

Panjarani qisqartirish hujumi NTRUEncryptni buzish uchun eng taniqli va eng amaliy usullardan biridir. Qandaydir tarzda uni RSA da modulni faktorizatsiya qilish bilan taqqoslash mumkin. Panjarani kamaytirish hujumi uchun eng ko'p ishlatiladigan algoritm bu Lenstra-Lenstra-Lovásh algoritmi.Chunki ochiq kalit h ikkalasini ham o'z ichiga oladi f va g ularni olishga harakat qilish mumkin h. Biroq, NTRUEncrypt parametrlari etarlicha xavfsiz tanlanganida, maxfiy kalitni topish juda qiyin. Agar o'lchamlari kattalashib, eng qisqa vektori uzunlashsa, panjarani kamaytirish hujumi qiyinlashadi.

The shifrlangan matn hujumi shuningdek, maxfiy kalitni qaytaradigan usul f va shu bilan umumiy tanaffusga olib keladi. Ushbu hujumda Momo Havo shifrlangan matndan o'z xabarini olishga harakat qiladi va shu bilan maxfiy kalitni olishga harakat qiladi. Ushbu hujumda Momo Havo Bob bilan o'zaro aloqada emas.

U qanday ishlaydi:

Birinchi Momo Havo shifrlangan matn yaratadi shu kabi va Momo Havo e-ni ochish uchun qadamlarni yozganda (u f ni bilmaganligi sababli qiymatlarni hisoblamasdan) topadi :

Qaysi shu kabi

Misol:

Keyin K bo'ladi .

Polinomlarning koeffitsientlarini kamaytirish a mod p ning koeffitsientlarini haqiqatan ham kamaytiradi . Bilan ko'paytirilgandan so'ng , Momo Havo topadi:

$ C $ ko'paytmasi sifatida tanlanganligi sababli p, m sifatida yozilishi mumkin

Buning ma'nosi .

Endi agar f va g bir xil omillarda bir xil bo'lgan oz koeffitsientlarga ega, K nol bo'lmagan koeffitsientlarga ega va shu bilan kichik. Ning turli xil qiymatlarini sinab ko'rish orqali K tajovuzkor o'zini tiklay oladi f.

NTRUEncrypt-ga muvofiq xabarni shifrlash va parolini ochish orqali tajovuzkor funktsiyani tekshirishi mumkin f to'g'ri maxfiy kalit yoki yo'q.

Xavfsizlik va ishlash ko'rsatkichlari yaxshilandi

So'nggi tavsiya etilgan parametrlardan foydalanish (qarang quyida ) NTRUEncrypt ochiq kalit kriptosistemasi ko'plab hujumlarda xavfsizdir. Ammo ishlash va xavfsizlik o'rtasida kurash davom etmoqda. Tezlikni pasaytirmasdan xavfsizlikni yaxshilash qiyin va aksincha.

Algoritm samaradorligiga ziyon etkazmasdan jarayonni tezlashtirishning usullaridan biri bu maxfiy kalitda ba'zi o'zgarishlar qilishdir f.Birinchidan, qurish f shu kabi , unda F kichik polinom (ya'ni koeffitsientlar {-1,0, 1}). Qurilish orqali f Bu yerga, f teskari tartibda p. Aslini olib qaraganda , demak, Bob aslida teskari hisoblashi shart emas va Bob parolni hal qilishning ikkinchi bosqichini bajarishi shart emas. Shuning uchun, qurilish f bu yo'l ko'p vaqtni tejaydi, ammo bu NTRUEncrypt xavfsizligiga ta'sir qilmaydi, chunki uni topish osonroq lekin f qayta tiklash hali ham qiyin.Bu holda f ga ko'paytirilishi sababli -1, 0 yoki 1dan farqli koeffitsientlarga ega p. Ammo Bob ko'paytirgani uchun p ochiq kalitni yaratish hva keyinchalik shifrlangan matn modulini kamaytiradi p, bu shifrlash uslubiga ta'sir qilmaydi.

Ikkinchi, f ko'p polinomlarning ko'paytmasi sifatida yozilishi mumkin, chunki polinomlar juda ko'p nol koeffitsientga ega. Shu tarzda kamroq hisob-kitoblarni o'tkazish kerak.

NTRUEncrypt-ning aksariyat tijorat dasturlarida parametr N= 251 ishlatiladi. Panjara hujumlaridan qochish uchun qo'pol kuch hujumlari va o'rtada uchrashish hujumlari, f va g taxminan 72 nol bo'lmagan koeffitsientga ega bo'lishi kerak.

So'nggi tadqiqotlarga ko'ra [3] quyidagi parametrlar xavfsiz hisoblanadi:

Jadval 1: parametrlar

Nqp
O'rtacha xavfsizlik1671283
Standart xavfsizlik2511283
Yuqori xavfsizlik3471283
Eng yuqori xavfsizlik5032563

Adabiyotlar

  1. ^ "US Patent 6081597 - ochiq kalitli kriptotizim usuli va apparati" - orqali Google patentlari.
  2. ^ "Security Innovation-ning NTRUEncrypt ma'lumotlarini himoya qilish uchun X9 standarti sifatida qabul qilingan". 2011 yil 11 aprel.
  3. ^ "NTRU PKCS parametrlari". 2012 yil 6 iyunda asl nusxasidan arxivlangan. Olingan 2012-07-28.CS1 maint: BOT: original-url holati noma'lum (havola)

Tashqi havolalar