Квантовите компютри: краят на криптографията?

реклама

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

Квантовото изчисление като идея съществува от известно време - теоретичната възможност е първоначално въведена от Юри Манин и Ричард Фейнман през 1982 г. През последните няколко години обаче, полето се очертава притеснително по-близо до практичността.

Компании като Google и Microsoft, както и правителствени агенции като NSA всички години трескаво преследват квантовите компютри. Компания, наречена D-Wave, произвежда и продава устройства, които (въпреки че не са подходящи компютри и могат изпълняват само няколко алгоритми) използват квантови свойства и са поредната стъпка по пътя към a напълно Тюринг-пълен Какво е тестът на Тюринг и ще бъде ли някога бит?Тестът на Тюринг има за цел да определи дали машините мислят. Дали програмата Eugene Goostman наистина премина теста на Тюринг или създателите просто изневериха? Прочетете още квантова машина.

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

Така че защо всички лихви? Защо трябва да се грижиш? Компютрите стават по-бързи през цялото време Какво е законът на Мур и какво общо има с теб? [MakeUseOf обяснява]Лошият късмет няма нищо общо със закона на Мур. Ако това е асоциацията, която сте имали, бъркате го със Закона на Мърфи. Въпреки това не бяхте далеч, защото законът на Мур и законът на Мърфи ... Прочетете още - какво е толкова специално в квантовите компютри?

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

Какво е сложност на изпълнение?

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

Някои алгоритми увеличават общото време за изпълнение много, много бързо с увеличаване на размера на проблема - някои алгоритми могат бързо да бъдат завършени дадени 100 точки от данни, но за да се изпълни алгоритъмът, дал 1000 точки от данни, ще изисква компютър с размер на Земята, който работи за милиард години. Сложността на изпълнение е формализация на тази идея: тя разглежда кривата на това колко бързо нараства сложността на даден проблем и използва формата на тази крива, за да класифицира алгоритъма.

По принцип тези класове на трудност се изразяват като функции. Алгоритъм, който става пропорционално по-труден, когато наборът от данни работи, нараства (като обикновена функция за броене), се казва, че е функция със сложност на изпълнение от „н" (както в, отнема н единици време за обработка н точки от данни).

Като алтернатива може да се нарече „линейна“, защото когато я графирате, получавате права линия. Други функции могат да бъдат п ^ 2 или 2 ^ п или н! (n факториален). Това са полиноми и експоненциални. В последните два случая експоненциалните нарастват толкова бързо, че в почти всички случаи те не могат да бъдат решени за нищо, освен за много тривиални примери.

Сложност на изпълнение и криптография

Ако чувате тези неща за първи път и ви звучат безсмислено и тайнствено, нека се опитаме да обосновете тази дискусия. Сложността на изпълнение е от решаващо значение за криптографията, която разчита на това, че прави декриптирането много по-лесно за хората, които знаят секретен ключ, отколкото за тези, които не го правят. В идеална криптографска схема декриптирането трябва да е линейно, ако имате ключа и 2 ^ к (където k е броят на битовете в ключа), ако не сте.

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

За симетричната ключова криптография (в която двете страни имат шанса да обменят секретно сигурно преди да започнат комуникация) това е доста лесно. За асиметричната криптография е по-трудно.

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

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

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

Най-известният алгоритъм за разпределяне на големи числа в техните първични компоненти се нарича общото сито с числово поле и има сложност на изпълнение, която расте малко по-бавно от 2 ^ п. В резултат на това ключовете трябва да бъдат около десет пъти по-дълги, за да осигурят подобна сигурност, което е нещо, което хората обикновено толерират като разходи за правене на бизнес. Лошата новина е, че цялото игрално поле се променя, когато квантовите компютри се хвърлят в сместа.

Квантови компютри: Промяна на крипто играта

Квантовите компютри работят, защото могат да имат множество вътрешни състояния едновременно, чрез квантово явление, наречено „суперпозиция“. Това означава, че те могат да атакуват различни части на проблем едновременно и да се разделят на възможни версии на Вселената. Те също могат да бъдат конфигурирани така, че клоните, които решават проблема, да се навиват с най-голяма амплитуда, така че когато отворите кутията на Котката на Schrodinger, версията на вътрешното състояние, с която най-вероятно сте представени, е котка на самодоволство, която държи декриптирана съобщение.

За повече информация за квантовите компютри, вижте последната ни статия по темата Как работят оптичните и квантовите компютри?Настъпва епохата на екзаскелите. Знаете ли как работят оптичните и квантовите компютри и ще станат ли тези нови технологии нашето бъдеще? Прочетете още !

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

За конкретен пример, Алгоритъмът на Shor, който може да бъде изпълнен само на квантов компютър, може да разпредели големи числа в log (n) ^ 3 време, което е драстично по-добро от най-добрата класическа атака. Използването на общото поле на сито за число за определяне на число с 2048 бита отнема около 10 ^ 41 единици време, което работи до повече от трилион трилиона трилиона. Използвайки алгоритъма на Shor, същият проблем отнема само около 1000 единици време.

Ефектът става по-изразен, колкото по-дълги са клавишите. Това е силата на квантовите компютри.

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

Това каза, че тяхната роля в криптографията ще бъде катастрофална. Технологиите за криптиране, които позволяват на нашия свят да продължи да функционира, зависят от проблема за цялостно факторизиране, който е трудно разрешим. RSA и свързаните с тях схеми за криптиране са това, което ви позволява да се доверите на правилния уебсайт, че файловете, които вие изтеглянето не е натъпкано със злонамерен софтуер и хората не шпионират в браузъра ви в Интернет (ако използвате Tor).

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

И така, квантовият апокалипсис е неизбежен? Може ли да направим нещо по въпроса? Както се оказва... да.

Поствантова криптография

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

Обещаващите кандидати включват криптиране въз основа на решетка, като Ring-Learning With Error, което извлича сигурността си от демонстративно сложен проблем с машинното обучение и многовариантна криптография, която извлича своята сигурност от трудността при решаването на много големи системи от прости уравнения. Можете да прочетете повече по тази тема в Статия в Уикипедия. Внимавайте: много от тези неща са сложни и може да откриете, че вашият математически произход трябва да бъде значително подобрен, преди да можете наистина да се вкопаете в детайлите.

Извличането на много от това е, че пост-квантовите криптосхеми са много готини, но и много млади. Те се нуждаят от повече работа, за да бъдат ефикасни и практични, а също и да демонстрират, че са сигурни. Причината да можем да се доверим на криптосистемите е, че сме хвърлили достатъчно клинично параноични гении в тях достатъчно дълго че всички очевидни недостатъци щяха да бъдат открити досега, а изследователите доказаха различни характеристики, които ги правят силен.

Съвременната криптография зависи от светлината като дезинфектант и повечето пост-квантови криптографски схеми са просто твърде нови, за да се доверят на световната сигурност. Те обаче стигат до там и с малко късмет и малко подготовка експертите по сигурността могат да завършат превключването преди първият квантов компютър да се появи на линия.

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

Притеснявате ли се от несигурността на криптографията към квантовите компютри? Какво ти е? Споделете мислите си в коментарите по-долу!

Кредити за изображения: Бинарна кълбо Via Shutterstock