Издаваемый Национальной академией наук США (NAS) престижный рецензируемый журнал Proceedings of the National Academy of Sciences присудил ежегодно учреждаемую премию Cozzarelli Award группе математиков во главе с исследователем из США Кеном Оно (Ken Ono) из Университета Вирджинии. Кен с коллегами нашли прямую связь между простыми числами — основой RSA-ключей — и уравнениями 1800-летней давности, что стало прорывом в области защиты данных.

Источник изображения: ИИ-генерация Grok 3/3DNews

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

Таким образом, учёным надо научиться находить всё большие простые числа (сейчас самое большое найденное простое число состоит из 41 млн цифр), а также искать иные подходы для определения таковых. Проделанная коллективом Кена Оно работа из таких — они нашли неизвестную ранее взаимосвязь между так называемыми диофантовыми уравнениями и простыми числами.

Открытие диофантовых уравнений приписывают математику III века Диофанту Александрийскому. Они могут быть невероятно сложными, но если полученный ответ окажется верным, это означает, что число будет простым. По сути, это новый способ исследования простых чисел, который никогда ранее не использовался.

«Простые числа, составляющие основу мультипликативной теории чисел, являются решениями бесконечно многих специальных “диофантовых уравнений” в хорошо изученных статистических разбиениях, — пишут авторы. — Другими словами, целочисленные разбиения позволяют находить простые числа бесконечно многими естественными способами».

Проделанная учёными работа могла быть сделана 20, 30 и 80 лет назад, когда стала понятна важность шифрования данных, и в любом случае она бы произвела фурор среди специалистов. Удивительно, до сих пор её никто не делал, подчёркивают авторы исследования и добавляют, что теперь открывается возможность подключить к анализу простых чисел ряд статистических методов. Тем самым RSA-шифрование может получить второе дыхание и ещё окажет сопротивление квантовым компьютерам через пять, десять или больше лет.

Исследование Google показало, что 2048-битный ключ шифрования RSA — современный стандарт для онлайн-безопасности — может быть взломан за несколько дней квантовым компьютером с менее чем миллионом кубитов. Это открытие резко снизило требования к конфигурации квантового компьютера по сравнению с прежними оценками, которые всего несколько лет назад предполагали необходимость как минимум 20 миллионов кубитов.

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

Квантовый компьютер с миллионом кубитов пока представляется скорее фантастикой, нежели реальностью. Однако темпы прогресса в этой области требуют уже сейчас начать переход к мерам безопасности, устойчивым к квантовым технологиям. Исследование, проведённое для Google Крейгом Гидни (Craig Gidney) подробно описывает будущие атаки с применением квантовых компьютеров и призывает мировое ИТ-сообщество уже сейчас готовиться к постквантовому миру.

Выводы Гидни являются результатом достижений как в квантовых алгоритмах, так и в методах исправления ошибок. С тех пор как Питер Шор в 1994 году открыл, что квантовые компьютеры могут факторизовать большие числа гораздо эффективнее классических компьютеров, учёные стремились точно определить, какая конфигурация квантового оборудования потребуется для взлома реального шифрования.

Источник изображений: IBM

Последняя работа Гидни основана на недавних алгоритмических прорывах, таких как использование приближенного модульного возведения в степень, которое значительно сокращает количество требуемых логических кубитов. Исследование также включает более плотную модель для хранения кубитов с исправленными ошибками, используя такие методы, как «коды с ярмовой поверхностью» (yoked surface codes) и «выращивание магического состояния» (magic state cultivation) для сокращения требуемых ресурсов.

Гипотетическая машина, располагающая миллионом кубитов, для взлома 2048-битных ключей шифрования RSA должна будет работать непрерывно в течение пяти дней, поддерживать чрезвычайно низкий уровень ошибок и координировать миллиарды логических операций без перерыва. Современные квантовые компьютеры работают только с сотнями или тысячами кубитов, что намного меньше отметки в миллион кубитов. Например, IBM Condor и Google Sycamore с 1121 и 53 кубитами соответственно иллюстрируют текущие возможности квантовых вычислений.

Компания D-Wave недавно представила самый мощный в мире квантовый компьютер — систему Advantage2 с более чем 4400 кубитами. Как и все предыдущие системы D-Wave (за исключением компьютеров первых поколений), Advantage2 будет доступна только через облако. Поставки физических систем клиентам начнутся позже — с платформ, насчитывающих не менее 7000 кубитов, время которых ещё не пришло.

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

20 мая компания NVIDIA объявила об открытии Глобального центра исследований и разработок для бизнеса в области искусственного интеллекта на базе квантовых технологий (Global Research and Development Center for Business by Quantum-AI Technology, G-QuAT). На этой площадке размещена система ABCI-Q — крупнейший в мире исследовательский суперкомпьютер, предназначенный для квантовых исследований. Система интегрирована с тремя квантовыми компьютерами.

Крупные компании, разрабатывающие квантовое оборудование, планируют масштабировать свои компьютеры до уровня миллиона кубитов в течение следующего десятилетия. IBM в партнёрстве с Токийским и Чикагским университетами собираются построить квантовый компьютер на 100 000 кубитов к 2033 году. Компания Quantinuum заявила о цели по созданию полностью отказоустойчивого универсального квантового компьютера Apollo к концу 2020-х годов.

Последствия появления следующего поколения квантовых компьютеров для информационной безопасности крайне болезненны. RSA и аналогичные криптографические системы лежат в основе большей части защищённых коммуникаций в мире, от банковского дела до цифровых подписей. Результаты исследования Гидни подтверждают срочность перехода на постквантовую криптографию (PQC) — новые стандарты, разработанные для противостояния атакам квантовых компьютеров. В прошлом году Национальный институт стандартов и технологий США опубликовал алгоритмы PQC и рекомендовал поэтапно отказаться от уязвимых систем после 2030 года.

Новые стандарты должны стать важным элементом криптографической защиты данных. Предыдущие стандарты криптографии NIST, разработанные в 1970-х годах, используются практически во всех устройствах, включая интернет-маршрутизаторы, телефоны и ноутбуки. Руководитель группы криптографии NIST Лили Чен (Lily Chen) уверена в необходимости массовой миграции с RSA на новые методы шифрования: «Сегодня криптография с открытым ключом используется везде и во всех устройствах, наша задача — заменить протокол в каждом устройстве, что нелегко».

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

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

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

Исследование Гидни подчёркивает важность упреждающего планирования. Оно также напоминает о вечном соревновании «снаряда и брони» — по мере развития технологий развиваются и методы их взлома. Улучшения алгоритмов и лучшая интеграция оборудования и программного обеспечения продолжают снижать барьеры для потенциальных злоумышленников.

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

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

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

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

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

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

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

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

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