Postkvant kriptografiyasi nima

Postkvant kriptografiya — kriptografiyaning bir sohasi bo‘lib, u kvant kompyuterlari va kvant hujumlari paydo bo‘lganda ham dolzarbligini saqlab qoladi. Kvant kompyuterlari an’anaviy kriptografik algoritmlarni hisoblash tezligi bo‘yicha klassik kompyuter arxitekturalaridan ancha ustun bo‘lgani sababli zamonaviy kriptografik tizimlar kriptografik hujumlarga nisbatan zaiflashishi mumkin. An’anaviy ochiq kalitli kriptotizimlarning aksariyati butun sonlarni ko‘paytuvchilarga ajratish yoki diskret logarifmni hisoblash masalalariga tayanadi. Bunday masalalarni Shor algoritmidan foydalanadigan yetarlicha katta kvant kompyuterlarida oson yechish mumkin bo‘ladi. Hozir ko‘plab kriptograflar kvant hisoblashlariga bog‘liq bo‘lmagan, ya’ni kvant hujumlariga bardoshli algoritmlarni ishlab chiqmoqda.

Hisoblash jihatidan murakkab masalalarga asoslangan an’anaviy kriptotizimlar ham mavjud. Ular yuqorida tilga olingan tizimlardan bir qator muhim jihatlari bilan farqlanadi va ularga asos bo‘lgan masalalarni yechish ancha qiyin. Bunday tizimlar kvant hisoblashlariga bog‘liq emas, shuning uchun ular kvantga bardoshli (quantum-resistant) yoki «postkvant» kriptotizimlar deb hisoblanadi.

Postkvant kriptografiya esa kvant kriptografiyasidan farq qiladi. Kvant kriptografiyasi aloqa kanallarini kvant fizikasi tamoyillari asosida himoyalash usullarini o‘rganadi.

Algoritmlar

Postkvant kriptografik usullar kriptografiyani kvant hujumlaridan himoya qilishi mumkin. Kvant kompyuteri aksariyat an’anaviy algoritmlarni (RSA, DSA, ECDSA) buzib yuborsa ham, yuqori hisoblash tezligi kriptografiyani butunlay yo‘q qila olmaydi. Chunki postkvant kriptografiya kvant hujumlari muammosini hal etishga qaratilgan, asosan, beshta turli yondashuvga tayanadi.

Xesh-funksiyalarga asoslangan kriptografiya

Bunga klassik misol — Merkle imzosi, ya’ni xesh daraxtiga asoslangan ochiq kalitli imzo sxemasi. Ralf Charlz Merkle ushbu raqamli imzo algoritmini 1979-yilda RSA va DSA raqamli imzolariga muqobil qiziqarli yechim sifatida taklif qilgan. Merkle sxemasining asosiy kamchiligi shundaki, ochiq kalit uchun xesh-funksiya asosida hosil qilinadigan imzolar soni tegishli yopiq kalitlar to‘plami bilan cheklanadi. Shu sababli kvant kompyuterlari ta’siriga bardoshli kriptografiyaga ehtiyoj paydo bo‘lgunicha bunday imzolarga qiziqish past bo‘lgan.

Xatolarni tuzatuvchi kodlarga asoslangan kriptografiya

Bu postkvant kriptotizimlar uchun eng istiqbolli yo‘nalishlardan biridir. Shifrlash sxemalarining klassik misollari — McEliece va Niederreiter.

Panjara tuzilmalariga asoslangan kriptografiya

Shifrlash sxemalarining klassik misollariga Ring-Learning with Errors (halqalarda xatolar bilan o‘rganish) yoki avvalroq yaratilgan NTRU, GGH hamda Michchanchoning kriptotizimi.

Ko‘p o‘zgaruvchili kvadratik tizimlarga asoslangan kriptografiya

Eng qiziqarli sxemalardan biri — Jak Patarenning ochiq kalitli HFE imzosi. U 1996-yilda Matsumoto va Imai takliflarini umumlashtirish sifatida taqdim etilgan.

Maxfiy kalit bilan shifrlash

Bunga yorqin misol — Rijndael shifri. U 1998-yilda taklif etilgan va keyinchalik AES (Advanced Encryption Standard — ilg‘or shifrlash standarti) deb qayta nomlangan.

Supersingulyar izogeniyadan foydalangan holda shifrlash

Bu Diffi–Xellman protokolining supersingulyar izogeniyalar grafigi bo‘ylab harakatlanishga asoslangan muqobilidir. U ikki yoki undan ortiq tomonning tinglashdan himoyalanmagan aloqa kanali orqali umumiy maxfiy kalitni hosil qilishiga imkon beradi. Biroq bu turdagi kriptotizimlarga qarshi samarali hujum ma’lum bo‘lgani uchun protokol xavfsiz deb hisoblanmaydi.

RSAga qarshi kriptografik hujumlarga misollar

1978-yilda RSA ochiq kalitli kriptografik algoritmini ishlab chiquvchilar chop etgan hujjatda (RSA nomi qisqartma bo‘lib, Rivest, Shamir va Adleman familiyalaridan olingan) Richard Shreppelning[ingl.] «linear sieve» («chiziqli elak») deb nomlangan yangi algoritmi tilga olingan. U istalgan RSA nmodulini, uzunligi [log2n]+1 bit bo‘lganda, 2(1+o(1))(log2n)1/2(log2log2n)1/2 ta oddiy amal yordamida ko‘paytuvchilarga ajratgan. Demak, bu algoritm kamida 2b ta oddiy amal talab qilishi uchun n uzunligi hech bo‘lmaganda (0,5+o(1))b2/log2b bit bo‘lishi kerak. Chunki 0,5+o(1) ifodasi muayyan kattalikning 0,5 ga yaqinlashishini bildiradi (b→∞ bo‘lganda). Shuning uchun n modulining uzunligini chekli b qiymati uchun to‘g‘ri tanlashda «linear sieve» algoritmining tezligi batafsilroq tahlil qilinishi lozim.

1988-yilda Jon Pollard[ingl.] ko‘paytuvchilarga ajratishning yangi algoritmini taklif qildi. Bu usul umumiy sonlar maydoni elagi usuli deb ataladi. Ushbu algoritm RSA-moduli n ning bit uzunligi log2n bo‘lganda, uni 2(1,9…+o(1))(log2n)1/3(log2log2n)2/3 ta oddiy amal bilan ko‘paytuvchilarga ajratgan. Demak, n uzunligini kamida (0,016…+o(1))b3/(log2b)2 bit qilib tanlash kerak, shunda algoritm kamida 2b ta oddiy amal talab qiladi.

2008-yildan boshlab klassik kompyuter arxitekturalarida ko‘paytuvchilarga ajratishning eng tez algoritmlari kamida 2(const+o(1))(log2n)1/3(log2log2n)2/3 ta oddiy amalni talab qiladi. const qiymatlarida va o(1) tafsilotlarida ayrim yaxshilanishlar bo‘lgan, biroq 1/3 optimal ekanini va n modul uzunligini taxminan b3 bit etib tanlash klassik kompyuterlarda amalga oshiriladigan barcha ehtimoliy hujumlarga bardosh berishini taxmin qilish qiyin emas.

1994-yilda Piter Shor RSA-modulini ko‘paytuvchilarga ajratish algoritmini taklif qildi. Bu algoritm RSA-moduli n ning bit uzunligi b=log2n bo‘lganda, b2+o(1) (aniqrog‘i, b2⋅log⁡(b)⋅log⁡(log⁡(b))) kubit amallarini bajaradi. Buning uchun taxminan 2⋅b1+o(1) kubitli kvant kompyuteri (va klassik kompyuterda oz miqdordagi yordamchi hisoblashlar) kerak bo‘ladi. Shor algoritmini hisobga olganda, n modulning bitlarda ifodalangan uzunligini kamida 2(0,5+o(1))b bit deb tanlashga to‘g‘ri keladi. Bu bizni qiziqtiradigan barcha amaliy holatlar uchun haddan tashqari katta qiymatdir. Bu yerda xavfsizlik parametri — b.

Kriptografik usullarning amaliy qo‘llanilishi

Kvant hujumlariga bardoshli algoritmlar juda kam. Kriptografik mustahkamlik darajasi yuqoriroq bo‘lishiga qaramay, postkvant algoritmlar hozirgi kriptotizimlarni (RSA, DSA, ECDSA va boshqalar) butunlay siqib chiqara olmaydi.

Ochiq kalitli kriptotizimlarga, xususan, McEliece shifrlash algoritmiga qarshi hujumlarni ko‘rib chiqaylik. Bu algoritm ikkilik Goppa kodlaridan foydalanadi. Dastlab Robert Makelis[ingl.] uzunligi n bo‘lgan kodlarni 2(0,5+o(1))n/log2n ta oddiy amal yordamida buzish mumkinligini ko‘rsatuvchi ishlarni taqdim etgan. Demak, n kamida (2+o(1))blog2b bit bo‘lishi kerakki, algoritmni buzish uchun kamida 2b ta oddiy amal talab etilsin. Keyingi bir nechta tadqiqotda hujum uchun zarur amallar soni nlog2n=2(log2n)2 gacha kamaytirildi, ammo (log2n)2 qiymati 0,5n/log2n dan ancha kichik bo‘ladi, agar n katta bo‘lsa. Shu sababli takomillashtirilgan hujumlar hamon 2(0,5+o(1))n/log2n ta oddiy amalni talab qiladi. Kvant kompyuterlaridan foydalanish esa faqat 0,5 doimiysini kamaytiradi, bu esa algoritmni buzish uchun zarur amallar sonini juda oz miqdorda qisqartiradi.

Agar McEliece shifrlash tizimi shunchalik yaxshi himoyalangan bo‘lsa, nega u RSA o‘rnini egallamayapti? Buning sababi samaradorlik, xususan, kalitning o‘lchamidir. McEliece ochiq kaliti taxminan n2/4 ≈ b2(log2b)2 bitdan iborat, RSA ochiq kaliti uchun esa taxminan (0,016…)b3/(log2b)2 bit yetarli. Agar b→∞ bo‘lsa, b2+o(1) bitli McEliece kaliti b3+o(1) bitli RSA kalitidan kichik bo‘ladi. Biroq amaliy xavfsizlik darajalarida, masalan, b=128 kabi holatlarda RSA ochiq kaliti bir necha ming bit bo‘lishi mumkin, McEliece kaliti esa deyarli bir million bitga yetadi.

PQCrypto konferensiyasi

2006-yildan buyon postkvant kriptografiyaga bag‘ishlangan konferensiyalar turkumi o‘tkazib kelinmoqda.

Havolalar