Texgologiyalari universiteti

I. KVANT KRIPTOGRFIYASI VA KRIPTOANALIZI

1.1 Кvant kompyuterlari va ularning imkoniyatlari

Kvant kompyuterlari va an'anaviy tranzistorlar o'rtasidagi asosiy farq bugungi kunda biz foydalanadigan ma'lumotlar. Bizga tanish bo'lgan qurilmalar - smartfonlar va noutbuklardan tortib, Deep Blue shaxmat superkompyuteriga qadar hamma narsani bitlarda saqlaydi, bu eng kichik ma'lumot birligiga shunday nomlangan. Bit ikkita qiymatdan birini olishi mumkin: 0 yoki 1.

Lampochkani ko'rib chiqing: u (1) yoki o'chirilgan (0). Kompyuter diskidagi fayl lampochkalar to'plamiga o'xshaydi, ba'zilari yoqilgan, boshqalari o'chirilgan. Ko'plab bunday lampochkalar bilan qurollanib, siz "Albert bu erda edi" iborasi yoki Mona Lizaning tasviri kabi ma'lumotlarni kodlashingiz mumkin.

Ikki holatli qurilma muammoni hal qilganda, u ushbu lampochkalarni doimiy ravishda yoqib o'chirishi kerak, ularning xotirasini to'sib qo'ymaslik uchun oraliq hisob-kitoblarning natijalarini yozib o'chirib tashlaydi. Bu vaqt talab etadi, shuning uchun agar vazifa juda murakkab bo'lsa, kompyuter uzoq va uzoq vaqt o'ylaydi.

Kvant kompyuterlari, katta qarindoshlaridan farqli o'laroq, ma'lumotlarni qisqacha kvant bit yoki kubit yordamida saqlaydi va qayta ishlaydi. Ular nafaqat "yoqilgan" va "o'chirilgan" bo'lishi mumkin, balki o'tish davri holatida yoki hatto bir vaqtning o'zida yoqilishi va o'chirilishi mumkin. Lampochka o'xshashligini davom ettirsangiz, kubit siz o'chirgan chiroqqa o'xshaydi, lekin miltillayveradi. Yoki bir vaqtning o'zida ham tirik, ham o'lik deb hisoblanadigan Shredingerning mushuki kabi.

Kvant kompyuteridagi lampalar yoqilganda ham, o'chirilganida ham ko'p vaqtni tejaydi. Shuning uchun kvant kompyuteri hatto eng kuchli an'anaviy qurilmadan ham murakkab muammolarni ancha tezroq hal qila oladi. Google o'zining kvant mashinasi Sycamore 3 minut ichida hisob-kitoblarni oddiy superkompyuterga 10 ming yil sarf qilishi mumkinligini aytdi. Bu erda "ustunlik" atamasi paydo bo'ladi.

Haqiqiy hayotda kvantli kompyuterlar

Biz juda murakkab muammolarni hal qilishda kvant kompyuterlari juda aniq ekanligini aniqladik. Xo'sh, nega tranzistor davri allaqachon tarix kitoblariga qo'shilmagan? Kvant texnologiyasi hali ham yosh bo'lgani uchun va "miltillovchi lampochka" holati juda beqaror - tizim qancha kubitni o'z ichiga olsa, barqarorlikni saqlash shunchalik qiyin bo'ladi. Va murakkab hisob-kitoblarning maqsadga muvofiqligi, xususan, kubitlar soniga bog'liq: Ikkita lampochkada, hatto yuqori qismida ham Mona Lizani chizmaysiz.

Boshqa sabablar kvant kompyuterlarining o'zlarining oldingilarini butunlay siqib chiqarishlariga to'sqinlik qiladi. Shuni yodda tutingki, ular ma'lumotni tubdan boshqacha tarzda qayta ishlashadi. Demak, ular uchun dasturiy ta'minot noldan ishlab 0chiqilishi kerak. Siz Windows-ni faqat kvant kompyuteriga o'rnatolmaysiz; sizga butunlay yangi kvant operatsion tizimi va kvant dasturlari kerak edi.

Garchi olimlar va IT gigantlari barmoqlarini kvant suvlariga botirayotgan bo'lsalar-da, hozircha kvant kompyuterlari oddiy kompyuterlarga ulangan va boshqariladigan tashqi qattiq disklar kabi ishlaydi. Ular vodorod atomini modellashtirish yoki ma'lumotlar bazalarini qidirish kabi tor doiradagi muammolarni hal qilish uchun ishlatiladi. Kvant hisoblash kuchiga qaramay, siz hali ham Internetga kirish va skeytbordda mushuklarning videolarini tomosha qilish uchun foydalana olmaysiz.

Shunga qaramay, ko'pchilik kelajak kvant hisoblashiga tegishli deb hisoblaydi. Birinchi kvant kompyuterlar bozorda 1999 yilda paydo bo'lgan. Bugungi kunda Google, Honeywell va IBM kabi yirik tashkilotlar (ikkinchisi allaqachon mijozlarga o'zining kvant kompyuterlariga bulutli kirishni taklif qilmoqda), Toshiba, Alibaba va Baidu bu sohaga katta mablag 'sarflamoqda. .

Ammo shuni ta'kidlash joizki, Google echgan vazifa kvant hisoblash imkoniyatlarini namoyish etishdan boshqa amaliy foydasi yo'q. Biz mitti-grittiga chuqur kirib bormaymiz, chunki u haqiqatan ham juda murakkab va kundalik foydalanuvchi uchun juda zarur emas. Ammo tafsilotlarni o'rganishni istasangiz, Google hisobotini ko'rib chiqing.

Aytgancha, hamma ham Google kompaniyasining 10 ming yillik da'vosiga qo'shilmaydi. Masalan, IBM, superkompyuter xuddi shu vazifani 3 daqiqada, 48 soatdan ko'p bo'lmagan vaqt ichida hal qilishi mumkinligiga amin. Ammo shunga qaramay, agar bu taxmin aniqroq bo'lsa ham, matematik bo'lmaganlar ham kvant va an'anaviy kompyuterlar o'rtasida sezilarli tezlik farqini sezadilar.

Kvant kompyuterlari (hali) tahdid emas

Ko'rib turganingizdek, kvant kompyuterlari iste'molchilar uchun mo'ljallangan qurilmalar yoki xakerlar vositalaridan ko'ra ko'proq olimlar uchun hali ham ko'proq narsadir. Ammo bu, albatta, ular yanada amaliy (va xavfli) bo'lib qolmasliklarini anglatmaydi. Shuni hisobga olib, ma'lumotlar xavfsizligi bo'yicha mutaxassislar allaqachon jang rejalarini tuzmoqdalar.

Zamonaviy kompyuter dunyomizda xabarlarni shifrlash nafaqat ba'zi ma'lumotlarni boshqalardan sir tutish uchun zarur, balki Bitcoin kabi kriptovalyutalar kabi texnologiyalarning asosiy qismidir. Bundan tashqari, razvedka idoralarining keng qamoqdagi tinglashlari bilan bog'liq mojarolar dunyoga aslida bugungi kunda qo'llanilayotgan tartiblarning hech biri xavfsiz emasligini ko'rsatdi. Ammo men sizga o'n yil ichida barcha aloqa xavfsiz bo'ladi, deb aytgan bo'lsam-chi, chunki kvant kriptografiyasi bilan shifrlangan aloqani tinglashning iloji yo'q.

Keling, bir necha qadam orqaga chekinamiz va bugungi kunda Internetdagi kriptografiya qanday amalga oshirilayotganini ko'rib chiqaylik. Joriy shifrlash RSA algoritmiga asoslangan (uning uchta ixtirochisi Rivest, Shamir va Adleman nomlari berilgan), bu "assimetrik" shifrlash tizimi bo'lib, ochiq kalit (siz hammaga beradigan kod) va shaxsiy kalit kombinatsiyasidan foydalaniladi. (o'zingiz saqlaydigan kod). Bu raqamlar nazariyasiga asoslangan va algoritm tub sonlar tushunchasiga asoslanadi. Xabarni kompyuteringiz bilan shifrlashda, shunchaki shaxsiy kalitingiz va qabul qiluvchining ochiq kaliti bergan raqamlarni ko'paytirish kifoya (bu juda oson ish). Qabul qilgich sizga yuborgan ko'p sonli raqamlarning shaxsiy va ochiq kalitlari yordamida parolini ochishi mumkin.

"Asimmetriya" xususiy kalitlarni bilmasdan xabarni parolini ochishga urinish qiyinligidan kelib chiqadi: bu jarayonni tinglash orqali ko'p sonli raqamni olish oson, ammo keyin katta sonni ikkita tub songa ajratish umuman imkonsizdir. kalitlari etarlicha uzun! Klassik kompyuterda juda katta sonni faktorizatsiya qilish juda uzoq vaqtni talab qilishi (hatto mavjud bo'lgan eng katta superkompyuterlar bilan ham) davom etishi sababli, har kimning urinishini to'xtatish kifoya. Faktorizatsiyaning matematik ma'noda "qiyin muammo" ekanligi, ya'ni uni polinomial kompyuter vaqtida hal qiladigan biron bir algoritm mavjud emasligi qat'iy isbotlanmagan bo'lsa ham, bunday algoritmlar hali topilmagan va ular mavjud emas deb ishoniladi. Darhaqiqat, ma'lum bo'lgan barcha klassik algoritmlar juda katta miqdordagi kompyuter vaqtini oladi.

Hatto eng yaxshi klassik algoritm ham kalitning uzunligiga qarab eksponentsial miqyosda, Shor algoritmi esa bir xil masalani kompyuterning polinomial vaqtida hal qilishi mumkin. (E'tibor bering, o'qlar ikki logaritmik miqyosda, ya'ni polinom funktsiyalari to'g'ri chiziqlardir.)

Uzoq kalit hozirgi kompyuterlarning shifrlashni buzib bo'lmasligini ta'minlasa, bu RSA matematik jihatdan xavfsiz bo'lmagan algoritm, ya'ni kattaroq kompyuterlar mavjud bo'lsa ham buzilishi mumkinligini anglatadi. Xavfsizlikning bu turini ba'zida hisoblash xavfsiz deb ham atashadi, ya'ni agar kalit uzunligi etarlicha katta tanlangan bo'lsa, u holda hatto superkompyuterlar ham xabarni buzish uchun yuzlab yoki minglab yillarni talab qiladi.

Kvant kompyuterlari

Yuqorida biz RSA shifrlash ko'lamini vaqt bo'yicha eksponentsial ravishda sindirish uchun eng yaxshi algoritmlarni ham klassik ravishda o'rnatdik. Ammo, 1997 yilda katta yutuq yuz berdi! Piter Shor kvantli kompyuterda polinom vaqtidagi sonlarni qanday ko'paytirishi mumkinligini seminal qog'ozda ko'rsatdi.