Считаше се, че за разбиването на RSA криптирането, на което се базират почти всички съвременни системи, работещи с конфиденциална информация, е необходим квантов компютър с милиарди кубити. На сега по математичен път бе доказано, че за хакването на RSA са достатъчни 20 милиона кубита и осем часа работа. Математиците, доказали това заявиха, че RSA криптирането гарантирано ще бъде разбито през следващите 25 години.

Появата на квантовите компютри ще постави под въпрос безопасността на редица системи за криптиране. Така например, учените от Националната академия на науките на САЩ считат, че появата на новия тип компютри ще се превърне в „криптографски кошмар“ и трябва да сме готови за него. За тази цел е добре да се знае, кога именно квантовите компютри ще станат достатъчно мощни за решаването на тази задача.

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

Но научната работа в областта на квантовите изчисления, представена от Крейг Хидни (Google) и Мартин Екерой (Кралски институт, Стокхолм), показа по-ефективен начин за разбиването на компютърните системи за криптиране и десеторно намали изискванията към квантовите компютри.

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

Предисторията: алгоритъмът на Шор

През 1994 година американският математик Питър Шор представи квантов алгоритъм, който е по-добър от класическия. В стандартния алгоритъм се използва умножение на прости числа – умножението на две прости числа е лесно, но разделянето на произведението на две прости числа е много по-трудно. Така например, не е трудно да се умножат числата 593 на 829 и да се получи 491 597. Но да се разбере, кои точно прости числа трябва да бъдат умножени, за да се получи 491 597 не е лесно. И колкото е по-голямо числото, толкова по-трудна е задачата. Именно този принцип се използва в популярния алгоритъм за криптиране RSA.

Информатиците отдавна показаха, че за класическият компютър на практика е невъзможно да разбие данните, криптирани с RSA ключ с дължина 2048 бита и нагоре.

През 2012 година физиците успяха с помощта на квантов компютър да разложат на множители числото 143, а през 2014 година числото 56 153. Изглежда че при този темп квантовите компютри скоро ще изпреварят класическите в тази област.

Но засега не могат. Оказва се, че задачата е по-сложна от предполаганото. На работата на квантовия компютър огромно влияние оказват шумовете, които се неутрализират с помощта на допълнителни кубити. През 2015 година учените пресметнаха, че за да се разложат на множители 2048-битови числа ще са необходими милиард кубити. Засега имаме стабилни квантови компютри само със 70 квантови бита.

Да си припомним, че на CES 2019 компанията IBM представи първия комерсиален модел на новия тип компютри, който рано или късно ще се вижда доста по-често извън лабораторните условия.

Малко по-късно D-Wave Systems представи новата архитектура Pegasus. Основното преимущество на архитектурата Pegasus е това, че всеки кубит може да се свързва с 15 други кубита, а не с 6, както бе при архитектурата Chimera. Това означава, че 680-кубитовият процесор Pegasus P6 има еквивалентна изчислителна мощност като процесора Chimera 2000Q, разполагащ с 2048 кубита. Друг важен момент е, че новата архитектура осигурява по-ниско ниво на шума, което силно повишава стабилността и ефективността на работа на цялата квантова система.

Използването на нови технологии и материали е понижило нивото на шума с 5-10 пъти в сравнение с първите компютри на D-Wave. Така например, нивото на квантовия шум в компютъра D-Wave 2000Q бе само три пъти по-нисък в сравнение с нивото на шум на кубитите на D-Wave One. Сега специалистите на компанията са разработили нови вещества и материали, с които нивото на шума се намалява с още три пъти. Тези нови материали ще бъдат използвани в най-новия квантов процесор P16, който ще има 5460 кубита и се разработва в момента.

Хакване на хакването

Смисълът на работата на Хидни и Екер е в това, че те доказаха по математичен път, че за тези изчисления е достатъчен квантов компютър с едва 20 милиона кубита, който да работи в продължение на 8 часа. Необходимите за постигането за тази цел ресурси са с два порядъка по-малко.

Методът на учените се базира на по-ефективното изпълнение на степенуването по модул – математически процес за търсенето на остатък, когато числото се повдига на степен и след това се дели на друго число. Това е и процесът, за който са необходими най-много ресурси и именно той бе оптимизиран.

Освен това математиците пресметнаха, че квантовите устройства с 20 милиона кубита, които са невъзможни днес, ще се появят след около 25 години. И тогава ще ни трябват нови системи за криптиране.

За обикновените потребители това не е проблем. Повечето от нас използват 2048-битово криптиране само при онлайн банкирането. Ако след 25 години тези транзакции бъдат хакнати – то това не е голям проблем.

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