Изображение: Блог Sedicomm
В конце декабря была представлена работа группы китайских учёных, которая продемонстрировала возможность взлома достаточно длинных RSA-ключей с помощью современных квантовых компьютеров. В работе рассказано о первом в истории взломе 48-битного ключа системой всего из 10 сверхпроводящих кубитов. Для взлома ключа RSA-2048 потребуется не более 400 кубитов, что уже находится в диапазоне современных возможностей.
Как известно, с помощью квантового компьютера и квантового алгоритма Шора можно легко и просто разложить (факторизовать) большие числа на простые множители и, тем самым, намного быстрее, чем на классическом компьютере расшифровать ключ или сообщение. Единственная проблема с запуском алгоритма Шора в том, что для факторизации криптографически значимых длинных ключей требуются квантовые системы из сотен тысяч, если не миллионов кубитов.
С тех пор, как алгоритм Питера Шора стал известен, учёные пытаются масштабировать его, чтобы взлом RSA не был таким ресурсоёмким для квантовых систем. Одну из идей как это сделать в своё время выдвинул российский физик Алексей Китаев. В 2016 году группа физиков Массачусетского технологического института и Инсбрукского университета создала квантовый компьютер, который подтвердил масштабирование при выполнении алгоритма Шора. Но для серьёзного прорыва этого было недостаточно.
Китайские учёные располагали достаточно скромной квантовой системой и хотели большего. Они воспользовались рекомендациями другого специалиста по криптографии — Клауса-Питера Шнорра, который весной прошлого года предложил методику, значительно ускоряющую факторизацию.
Работа Шнорра была раскритикована специалистами, как неспособная выдержать масштабирование до взлома длинных ключей, «смерть» которых действительно могла бы закрыть историю с RSA-шифрованием. Но китайские исследователи утверждают, что нашли возможность обойти это ограничение и на практике это доказали, взломав 48-битный ключ 10-кубитной квантовой системой, а также уверяют, что метод работает для взлома ключей криптографически значимой длины.
Фактически ученые объединили классические методы факторизации с уменьшением решетки с алгоритмом квантовой приближенной оптимизации (QAOA). Согласно их расчётам, для взлома ключа RSA-2048 потребуется всего 372 кубита. Подобная система, например, скоро будет у компании IBM. Процессор IBM Osprey открывает доступ к 433 кубитам.