В края на декември група китайски учени представиха работата си върху възможността за разбиване на дълги ключове RSA с помощта на съвременни квантови компютри. В статията се описва първото в историята разбиване на 48-битов ключ чрез система от само 10 свръхпроводящи кюбита. За разбиването на ключ RSA-2048 ще са необходими не повече от 400 кюбита, което вече е в рамките на сегашните възможности. RSA е всичко?
Известно е, че квантовият компютър и квантовият алгоритъм на Шор могат лесно и просто да разлагат (факторизират) големи числа на прости множители, като по този начин декриптират ключа или съобщението много по-бързо, отколкото на класически компютър. Единственият проблем при изпълнението на алгоритъма на Шор е, че той изисква квантови системи от стотици хиляди, ако не и милиони кюбити, за да се факторизират криптографски значими дълги ключове.
Откакто алгоритъмът на Питър Шор стана известен, учените се опитват да го увеличат, така че разбиването на RSA да не изисква толкова много ресурси за квантовите системи. Една от идеите за това е представена от руския физик Алексей Китаев. През 2016 г. екип от физици от Масачузетския технологичен институт и Университета в Инсбрук създаде квантов компютър, който потвърди мащабирането при изпълнението на алгоритъма на Шор. Но това не беше достатъчно за голям пробив.
Китайските учени разполагат с доста скромна квантова система и искат повече. Те се възползваха от съвета на друг експерт по криптография – Клаус-Петер Шнор, който миналата пролет предложи техника, която значително ускорява факторизацията.
Експертите критикуват работата на Шнорр като неспособна да се разшири, за да се разбият дълги ключове, чиято „смърт“ наистина би могла да приключи историята на RSA криптирането. Китайските изследователи обаче твърдят, че са намерили начин да заобиколят това ограничение и са го доказали на практика, като са разбили 48-битов ключ с 10-битова квантова система, и уверяват, че методът работи за разбиване на криптографски значими дължини на ключове.
Всъщност китайците са комбинирали класически техники за факторизация с намаляване на решетката с алгоритъм за квантова апроксимация (QAOA). Според техните изчисления за разбиването на ключ RSA-2048 са необходими само 372 кюбита. Подобна система, например, скоро ще се предлага от IBM. Процесорът IBM Osprey позволява достъп до 433 кюбита. Ако зад думите на китайските учени се крие нещо, то RSA-2048 ще бъде разбит от квантови компютри след не повече от няколко години.