Разни

Как алгоритъмът на Peter Shor обрича RSA криптирането на неуспех

Как алгоритъмът на Peter Shor обрича RSA криптирането на неуспех

Това е четвъртата статия от серия от седем части за Алгоритми и изчисления, която изследва как използваме прости двоични числа за захранване на нашия свят. Първата статия, Как алгоритмите управляват света, в който живеем, можете да намерите тук.

Няколко години преди Сергей Брин и Лари Пейдж за първи път да включат своята търсачка на Google в бизнеса, който спомогна за изграждането на Интернет, какъвто го познаваме, Питър Шор публикува статия за алгоритъма, който беше предопределен да отвори всички ключалки на връзките, които трябваше да запазят цялата работа в безопасност.

Питър Шор не беше някакъв злонамерен анархо-хактивист, а математик, работещ за Bell Labs на AT&T търси да реши труден математически проблем като всеки друг математик в областта. Неговият алгоритъм, известен като Алгоритъм на Шор, изискваше технология, която едва съществуваше на теория, още по-малко реалност, когато той я описа за първи път през 1994 г.

СВЪРЗАНИ: КАКВО ТОЧНО ЩЕ ПРОМЕНИ КВАНТОВИТЕ ИЗЧИСЛЕНИЯ?

Нямаше причина да мислим в края на 90-те и началото на 2000-те, че някога ще трябва да се тревожим за несигурността на RSA криптиране, но сега знаем истината: RSA криптиране е предопределено да се провали. Сега, невероятната технология, използвана от Shor, квантови изчисления, не само напредва със скорост, подобна на закона на Мур - което означава, че в рамките на десетилетие или две квантовите компютри ще бъдат достатъчно мощни, за да работят Алгоритъм на Шор и бюст отворен RSA криптиранеАлгоритъм на Шор на първо място помогна да се вдъхнови развитието на квантовите изчисления.

Шифроването на RSA някога се е смятало за неразрушимо

RSA криптиране, който се използва за криптиране на всичко от файлове на нашите твърди дискове до поверителен интернет трафик, е изграден на принципите на обмен на публичен ключ и изчислително труден проблем на главна факторизация.

За класически компютър, ефективен алгоритъм за намиране на основни фактори на а съставно число не съществува, което означава, че най-доброто, което можем да направим, е да намерим отговор малко по-малко ужасен от експоненциално време. RSA криптиране обикновено се квалифицира с битова дължина, като 128 бита, 256 битаи др., което представлява битовата дължина на ключа, използван за криптиране и декриптиране на данни. Така че алгоритъм за груба сила с експоненциална времева сложност работи по a 128-битов ключ за криптиране ще трябва да се опита 2128 стойности минимум.

Това е равно на 340,282,366,920,938,463,463,374,607,431,768,211,456 възможните ключове и RSA ключовете за криптиране не са толкова малки, колкото 128 бита за повече от десетилетие. Настоящата стандартна препоръчителна дължина на ключа за RSA ключ за криптиране е 2048-битова, което е равно на (340,282,366,920,938,463,463,374,607,431,768,211,456)16 възможни ключове.

Тези числа са непонятни за нас, но има начин да се управляват и дори да се извършват операции, като се използват тези числа, нещо известно като модулна аритметика и именно тези операции са в основата на алгоритъма за криптиране на RSA.

В много страни, които използват a 12-часов часовник а не а 24-часов часовник за да запазят времето, те използват модулна аритметика през цялото време, буквално. Ако е 11 часа и ви моля да се срещнете с мен четири часа, знаете, че искам да се срещнем в 15:00. Това е така, защото използваме числото 12, наречен модул, за да знаете кога отново да започнете да броите от нула. Модулната аритметика използва същия процес, само с числа с огромен размер, за да подпомогне извършването на изчисления.

Както всяка друга система за обмен на ключове, RSA криптиране използва a публичен ключ и а частен ключ за криптиране и декриптиране на данни, с изключение на RSA криптиране използва две числа като публичен ключ, публичен експонент, който да се използва за криптиране на съобщение и a модул за операцията за криптиране, която произвежда шифъра. Какво прави това модул толкова важен е фактът, че е продукт на две много големи прости числа и знаейки тези две числа ще ви позволи да извършите обратно проектиране на частен ключ което отключва криптирането.

Трудността, присъща на RSA криптиране обаче е двоен: огромността на включените числа означава, че не можете да насилвате пътя си към частен ключ и факта, че главна факторизация от този невероятно голям брой е нещо не класически компютър мога да се надявам да направя в трилиони години.

Как Quantum Computers и Shor’s Algorithm побеждават RSA криптирането

Без да се затъвам в крайните подробности, Алгоритъм на Шор е отговор от три части на проблема с главна факторизация за всякакви цяло число, така че работи, независимо колко голямо е цялото число. The първа част се извършва на a класически компютър в многочленно време, но това е само настройката за втора и най-важна част. The втора част изисква използването на специално конструирани квантови вериги за изпълнение на квантово изчисление необходими за намиране на стойност имате нужда от трета част, който ви позволява да намерите основни фактори от цялото число на a класически компютър.

Първата част на алгоритъма трансформира проблема на главна факторизация в еквивалентен проблем, който е разрешим, а именно намирането на Период на а модулна работа. Ако можете да намерите Период на тази функция, използвайки като цяло число, което искате да разчетете като a модул, можете да намерите основните фактори доста бързо на класически компютър с някои допълнителни изчисления.

Проблемът е, че, като главна факторизация, намиране на Период от тази модулна операция не е нещо a класически компютър може да направи в многочленно време, но Кратко показа в втора част на алгоритъма, който използва a теоретичен квантов компютър можете да изчислите това Период и, най-важното, той успя да докаже математически, че тази част от квантов алгоритъм налетя многочленно време. След намирането на Период, а класически компютър може да го използва, за да намери основни фактори на всяко цяло число.

Как Peter Shor и Shor’s Algorithm Kick започнаха квантовите изчисления

Питър Шор показа, че теоретична квантов компютър може да реши неразрешим математически проблем по начини, които а класически компютър никога не би могъл да отстрани необходимостта от изчисляване на единични стойности наведнъж. Квантови компютри може да извършва операции на кубити в суперпозиция и буквално намаляват сложността във времето на проблема експоненциално.

Кога Кратко измисли своя алгоритъм, квантови изчисления не съществуваше по никакъв смислен начин. Идеята съществуваше от известно време, но беше напълно теоретично, непрактично дори да се прави опит за изграждане и никой не можеше да види полезността при опитите за изграждане на такава, тъй като нямаше пример за нещо квантов компютър може да направи това а класически компютър Не можех.

Като показва как a квантов компютър всъщност може да бъде полезно по начин, който класически компютри не можеше чрез решаване на класически неразрешим проблем в многочленно време, Питър Шорпредизвика интересите на изследователи от цял ​​свят, които започнаха свои собствени изследвания квантови изчисления и сега се изграждат действителни, работещи квантови компютри. Ще мине десетилетие поне преди квантовият компютър да има достатъчно кубита, за да се счупи RSA криптиране, но краят му е сигурен и вече криптографите откриха нови пътища за изследване на пост-квантовата криптография, за да се уверят, че всичко, което трябва да бъде защитено, прави.

След Питър Шор алгоритъм доказа, че трудни проблеми за класически компютри могат да бъдат решени, други започнаха да разглеждат други трудни проблеми, които също могат да бъдат решени от квантовите компютри, и с добра причина; от многото проблеми, които остават да бъдат решени, потенциалната полза от решаването им е също толкова огромна, колкото самите проблеми.

Петата статия от нашата поредица за алгоритми и изчисления, Алгоритми, оптимизация и проблем на пътуващия продавач, можете да намерите тук.


Гледай видеото: Paul Dirac Interview, Göttingen 1982 (Октомври 2021).