Примерно год назад группа китайских учёных опубликовала статью, в которой сообщила о скорой смерти широко используемого метода RSA-шифрования с открытым ключом. На небольшом квантовом компьютере они показали, что взломать RSA можно с использованием меньшего числа кубитов, чем длина ключа. В этом таилась колоссальная угроза безопасности критически важным данным, что нужно было изучить. Всё оказалось не так просто.

Источник изображения: НИТУ МИСИС

Анализом работы китайских коллег занялась группа учёных Университета МИСИС, РКЦ и «Сбера». Считается, что большинство используемых в настоящее время криптосистем с открытым ключом защищены от атак через обычные компьютеры, но могут быть уязвимы для квантовых платформ. Поскольку компания IBM уже представила 433-кубитовый квантовый процессор Osprey, то ключ RSA-2048 теоретически может быть взломан в любой момент. В работе китайских специалистов доказывалось, что для этого хватит 372 кубитов, а не 20 млн, как считалось ранее.

Китайские исследователи использовали 10-кубитную платформу для разложения на простые множители (факторизацию) 48-битового ключа.

«Основываясь на классическом методе факторизации Шнорра, авторы используют квантовое ускорение для решения задачи поиска короткого вектора в решётке (SVP, shortest vector problem) небольшой размерности — что позволило им сделать сенсационное заявление о том, что для факторизации, т.е. разложения большого числа на множители, требуется меньше кубитов, чем его длина, а также квантовые схемы меньшей глубины, чем считалось ранее», — поясняют в пресс-релизе представители НИТУ МИСИС.

Российские исследователи пришли к выводу, что алгоритм коллег нерабочий из-за «подводных камней» в классической части и сложности реализации квантовой.

«Метод Шнорра не имеет точной оценки сложности. Основная трудность заключается не в решении одной кратчайшей векторной задачи, а в правильном подборе и решении множества таких задач. Из этого следует, что этот способ, вероятно, не подходит для чисел RSA таких размеров, которые используются в современной криптографии», — сказал Алексей Федоров, директор Института физики и квантовой инженерии НИТУ МИСИС, руководитель научной группы «Квантовые информационные технологии» РКЦ.

Предложенный китайскими учёными метод даёт только приближённое решение задачи, которое можно легко получить для небольших чисел и маленьких решёток, но практически невозможно для реальных длинных ключей, что российские учёные подробно объяснили в статье в журнале IEEE Access (ссылка на arxiv.org).

В то же время российские учёные рекомендуют не расслабляться, а готовиться к постквантовой криптографии. Появляются новые платформы и новые алгоритмы, и в один не очень прекрасный день окажется, что надёжные ещё вчера RSA-ключи вдруг перестали защищать ваши данные.

Специалисты компании Fujitsu провели исследование, которое может служить ответом на угрозу взлома RSA-ключей с помощью квантовых компьютеров. По данным компании, эта опасность крайне преувеличена. Запуск алгоритма на 39-кубитовом симуляторе показал, что до появления настоящей угрозы RSA-шифрованию пройдут долгие годы.

Источник изображения: Pixabay

Команда Fujitsu работала с одной из версий алгоритма Шора, который позволяет раскладывать большие числа на простые множители с помощью квантовых вычислителей. В рамках эксперимента удалось факторизовать 96 целых чисел типа RSA (произведение двух различных нечетных простых чисел) от N=15 до N=511 и подтвердить, что программа общего назначения может генерировать правильные квантовые схемы.

Затем специалисты использовали программу для генерации симулятора квантовых схем, с помощью которых они разложили на простые множители несколько RSA-ключей длиной от 10 до 25 бит и оценили требуемые ресурсы квантовых схем для взлома ключа длиной 2048 бит. Согласно расчётам, для факторизации числа RSA-2048 потребуется примерно 10 тыс. кубитов и 2,25 трлн вентилей с ними связанных (логических элементов). При этом отказоустойчивый квантовый компьютер с такой архитектурой должен будет работать 104 дня.

На основе расчётов команда Fujitsu сделала вывод, что до взлома с помощью алгоритмов Шора RSA-ключей криптографически значимой длины пройдут ещё многие годы, поскольку появление системы с 10 тыс. кубитов или классических компьютеров для её симуляции — этот вопрос довольно неблизкого будущего.

Исследование Fujitsu стало ответом на недавнюю статью китайских учёных, которые утверждают о возможности взломать ключ RSA-2048 с помощью квантовой системы на основе всего 372 кубитов. Китайцы использовали для доказательства концепции настоящий квантовый вычислитель на 10 сверхпроводящих кубитах. Они утверждают, что испытали алгоритм, кратно ускоряющий факторизацию. Использовали специалисты Fujitsu подобную оптимизацию или нет, не сообщается. Команда Fujitsu работала на суперкомпьютере Fugaku на архитектуре ARM, что, возможно, могло ограничить её специалистов в выборе алгоритмов.

Позже на этой неделе ожидается более подробный доклад о работе, которая будет представлена на конференции Symposium on Cryptography and Information Security 2023. Возможно мы узнаем больше подробностей.