Turli xil

Piter Shor algoritmi qanday halokatga uchraganligi to'g'risida RSA shifrlash

Piter Shor algoritmi qanday halokatga uchraganligi to'g'risida RSA shifrlash

Bu Algoritmlar va Hisoblash bo'yicha etti qismdan iborat to'rtinchi maqola bo'lib, unda biz o'z dunyomizni kuchaytirish uchun oddiy ikkilik raqamlardan qanday foydalanamiz. Birinchi maqola, Algoritmlar biz yashayotgan dunyoni qanday boshqaradi, bu erda topishingiz mumkin.

Sergey Brin va Larri Peyj o'zlarining Google qidiruv tizimini birinchi bo'lib biz bilgan Internetni yaratishda yordam beradigan biznesga qo'shilishidan bir necha yil oldin, Piter Shor hamma narsani xavfsiz saqlashi kerak bo'lgan ulanishlarning barcha qulflarini ochishga mo'ljallangan algoritm haqida maqola nashr etdi.

Piter Shor ba'zi zararli anarxo-hacktivist emas, balki matematik edi AT & T's Bell Labs sohadagi boshqa matematiklar singari qiyin matematik masalani echishga intilmoqda. Uning ma'lum algoritmi Shor algoritmi, nazariy jihatdan deyarli mavjud bo'lmagan texnologiyani talab qildi, juda kam haqiqat, uni 1994 yilda birinchi marta ta'riflaganida.

BOShQALAR: KVANT KOMPYUTERI AYNI NIMA O'ZGARTIRADI?

1990-yillarning oxiri va 2000-yillarning boshlarida biz hech qachon ishonchsizlik haqida qayg'uramiz deb o'ylash uchun hech qanday sabab yo'q edi RSA shifrlash, ammo endi biz haqiqatni bilamiz: RSA shifrlash muvaffaqiyatsizlikka uchragan. Endi Shorning mumkin bo'lmagan texnologiyasi ishlatilgan, kvant hisoblash, nafaqat Mur qonuniga o'xshash sur'atlarda rivojlanib bormoqda, ya'ni bir-ikki o'n yil ichida kvant kompyuterlari ishlash uchun etarlicha kuchga ega bo'ladi. Shor algoritmi va ko'krak ochiq RSA shifrlashShor algoritmi o'zi birinchi navbatda kvant hisoblash tizimini rivojlantirishga yordam berdi.

RSA shifrlash bir marta buzilmasligiga ishongan edi

RSA shifrlash, bu bizning qattiq diskimizdagi fayllardan tortib, maxfiy Internet-trafikgacha bo'lgan narsalarni shifrlash uchun ishlatiladigan tamoyillar asosida qurilgan ochiq kalitlarni almashtirish va hisoblash qiyin bo'lgan muammo asosiy faktorizatsiya.

Klassik kompyuter uchun an samarali algoritm topish uchun asosiy omillar a kompozit raqam mavjud emas, demak, biz qila oladigan eng yaxshisi, javobni nisbatan kamroq dahshatli topishdir eksponent vaqt. RSA shifrlash kabi biroz uzunlik bilan malakaga ega, masalan 128 bit, 256-bitva hokazo, bu ma'lumotlarni shifrlash va parolini hal qilish uchun ishlatiladigan tugmachaning bit uzunligini bildiradi. Shunday qilib, qo'pol kuch algoritmi eksponent vaqt murakkabligi a ustida ishlash 128-bitli shifrlash kaliti urinish kerak bo'ladi 2128 minimal qiymatlar.

Bu teng 340,282,366,920,938,463,463,374,607,431,768,211,456 mumkin bo'lgan kalitlar va RSA shifrlash kalitlari u qadar kichik bo'lmagan 128 bit o'n yildan ko'proq vaqt ichida. RSA shifrlash kaliti uchun joriy standart tavsiya etilgan kalit uzunligi 2048-bit, bu tengdir (340,282,366,920,938,463,463,374,607,431,768,211,456)16 mumkin bo'lgan kalitlar.

Ushbu raqamlar biz uchun tushunarsizdir, ammo bu raqamlarni ishlatib boshqarish va hatto bajarish usuli mavjud, bu modulli arifmetik deb nomlanadi va bu RSA shifrlash algoritmining markazida joylashgan.

A dan foydalanadigan ko'plab mamlakatlarda 12 soatlik soat a o'rniga 24 soatlik soat vaqtni saqlash uchun ular modulli arifmetikadan doimo, so'zma-so'z foydalanadilar. Agar shunday bo'lsa 11.00 va men bilan uchrashishingizni so'rayman to'rt soat, bilasizmi, men uchrashishni istayman 15.00. Buning sababi, biz raqamdan foydalanamiz 12, deb nomlangan modul, yana qachon noldan hisoblashni boshlashni bilish. Modulli arifmetikada xuddi shu jarayon qo'llaniladi, faqat hisoblarni bajarishda yordam beradigan juda katta hajmdagi raqamlar mavjud.

Boshqa har qanday kalit almashish tizimi singari, RSA shifrlash ishlatadi ochiq kalit va a shaxsiy kalit ma'lumotlarni shifrlash va parolini hal qilish uchun, bundan mustasno RSA shifrlash ochiq raqam sifatida ikkita raqamdan foydalanadi, xabarni shifrlash uchun ishlatiladigan umumiy ko'rsatkich va a modul shifr ishlab chiqaradigan shifrlash jarayoni uchun. Bunga nima sabab bo'ladi modul mahsuloti ekanligi juda muhim ikkita juda katta son va ularni bilish ikkita raqam sizga teskari muhandislik qilishga imkon beradi shaxsiy kalit bu shifrlashni ochadi.

Bunga xos bo'lgan qiyinchilik RSA shifrlash ammo ikki baravar: raqamlarning ulkanligi shafqatsiz yo'lni bosib o'tolmasligingizni anglatadi shaxsiy kalit va haqiqat asosiy faktorizatsiya bu aql bovar qilmaydigan darajada katta raqam - yo'q narsa klassik kompyuter bunga umid qilaman trillionlab yillar.

Kvant kompyuterlari va Shor algoritmi RSA shifrlashni qanday mag'lub qiladi

Cheklangan tafsilotlarga aralashmasdan, Shor algoritmi muammosiga uch qismli javobdir asosiy faktorizatsiya uchun har qanday tamsayı, shuning uchun u qancha katta bo'lmasin ishlaydi. The birinchi qism a-da bajariladi klassik kompyuter yilda polinom vaqti, lekin bu faqat uchun sozlangan ikkinchi va eng muhim qism. The ikkinchi qism maxsus qurilgan foydalanishni talab qiladi kvant davrlari bajarish kvant hisoblash topish kerak edi qiymat sizga kerak uchinchi qism, bu sizga topishga imkon beradi asosiy omillar a sonidagi tamsayı klassik kompyuter.

Algoritmning birinchi qismi muammoni o'zgartiradi asosiy faktorizatsiya ichiga teng echilishi mumkin bo'lgan muammo, ya'ni davr a modulli ishlash. Agar topsangiz davr a funktsiyasini olishni istagan tamsayı sifatida ishlatadigan ushbu funktsiyani modul, qo'shimcha omillarni klassik kompyuterda juda tez topishingiz mumkin.

Muammo shu kabi asosiy faktorizatsiya, topish davr bu modulli operatsiya narsa emas klassik kompyuter qila oladi polinom vaqti, lekin Shor ko'rsatdi ikkinchi qism dan foydalanadigan algoritm nazariy kvant kompyuter buni hisoblashingiz mumkin davr va, eng muhimi, u bu qismini matematik ravishda isbotlay oldi kvant algoritmi yugurdi polinom vaqti. Topgandan keyin davr, a klassik kompyuter uni topish uchun ishlatishi mumkin asosiy omillar har qanday butun son.

Piter Shor va Shor algoritmining zarbasi kvant hisoblashni qanday boshlagan

Piter Shor nazariy ekanligini ko'rsatdi kvantli kompyuter echilishi mumkin bo'lmagan matematik muammoni a klassik kompyuter Bir vaqtning o'zida bitta qiymatlarni hisoblash zarurligini hech qachon yonma-yon bosa olmaysiz. Kvant kompyuterlari operatsiyalarni bajarishi mumkin kubitlar yilda superpozitsiya va muammoning vaqt murakkabligini so'zma-so'z kamaytiradi.

Qachon Shor algoritmini o'ylab topdi, kvant hisoblash hech qanday mazmunli tarzda mavjud emas edi. Bu g'oya bir muncha vaqtdan beri mavjud edi, ammo bu umuman nazariy edi, hatto uni qurishga urinish ham amaliy emas edi va hech kim uni yaratishga urinib ko'rganligini ko'rmadi, chunki hech qanday misol yo'q edi. kvantli kompyuter buni qila olardi a klassik kompyuter qila olmadi.

Qanday qilib a kvantli kompyuter aslida foydali bo'lishi mumkin klassik kompyuterlar klassik echilmaydigan muammoni hal qilish bilan qila olmadi polinom vaqti, Piter Shoro'z tadqiqotlarini boshlagan dunyo bo'ylab tadqiqotchilarning qiziqishlarini uyg'otdi kvant hisoblash va hozirda haqiqiy, ishlaydigan kvant kompyuterlari qurilmoqda. Kvant kompyuterining sindirishi uchun etarli kubitlarga ega bo'lishidan kamida o'n yil oldin bo'ladi RSA shifrlash, ammo uning oxiri aniq va allaqachon kriptograflar xavfsizligini ta'minlashi kerak bo'lgan hamma narsani qilishiga ishonch hosil qilish uchun Post-kvant kriptografiyasida yangi tadqiqotlar yo'llarini ochdilar.

Keyin Piter Shorning algoritmi qiyin muammolar ekanligini isbotladi klassik kompyuterlar echilishi mumkin edi, boshqalari kvant kompyuterlari tomonidan hal qilinishi mumkin bo'lgan boshqa qiyin muammolarni ko'rib chiqa boshladilar va bu yaxshi sabablarga ko'ra; hal etilishi kerak bo'lgan ko'plab muammolardan, ularni hal qilish uchun mumkin bo'lgan foyda, muammolarning o'zi kabi juda katta.

Algoritmlar va hisoblashlar seriyasidagi beshinchi maqola, Algoritmlar, optimallashtirish va sayohat qiluvchi sotuvchi muammosi, bu erda topishingiz mumkin.


Videoni tomosha qiling: The RSA Encryption Algorithm 1 of 2: Computing an Example (Yanvar 2022).