Будущее алгоритма RSA в эпоху квантового превосходства

Основу современного безопасного интернета составляет ассиметричное шифрование, с помощью которого возможно производить обмен конфиденциальной информацией. Алгоритмы ассиметричного шифрования основываются на большой сложности решения некоторых математических задач (например факторизации или вычисления дискретного логарифма больших чисел).

Одним из таких алгоритмов является RSA, который был представлен в 1977 году (название RSA — это аббревиатура от фамилий разработчиков Райвест (Rivest), Шамир (Shamir) и Эдльман (Adleman)).

Принцип работы алгоритма сводится к малой теореме Ферма: пусть p — простое число и, а — целое, не делящееся на p, тогда a ^(p-1) ≡ 1 (mod p).

Для того, чтобы зашифровать некоторую конфиденциальную информацию b с помощью алгоритма RSA необходимо:

1. Выбрать некоторые 2 простых целых числа x и y. Для примера возьмем небольшие простые числа, например 29 и 13.
2. Далее необходимо вычислить их произведение N = x ⋅ y = 29 ⋅ 13 = 377, значение функции Эйлера φ(n) = (x-1) ⋅ (y-1) и некоторое число e, взаимно простое со значением φ(n). Малые значения e могут ослабить стойкость алгоритма. В нашем примере значение φ(n) = 28 ⋅ 12 = 336, за значение e возьмём число 257, которое должно быть простым и меньшим значения функции φ(n). Тогда, если нам необходимо зашифровать некоторую информацию b = 215 (b должно удовлетворять условию b e (mod n) = 215 ²⁵⁷ (mod 377) = 128.
3. Вычисляется число d, обратное числу e по модулю φ(n), то есть удовлетворяющее сравнению d ⋅ e ≡ 1 (mod φ(n)). В нашем случае возьмем d=353. Тогда, чтобы получить открытый текст, необходимо вычислить значение D(223) = 128 ³⁵³ (mod 377) = 215.
4. Пару чисел [n, e] называют открытым ключом, данную пару можно передавать по незащищенным каналам. Значения [d, n] — закрытый ключ, который хранится у получателя сообщения в тайне.

Рис. 1 Упрощенная схема работы алгоритма RSA

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

В то же время, группой ученых в 2006 году создан проект CADO-NFS (Crible Algebrique: Distribution, Optimisation — Number Field Sieve — с французского и английского «Общий метод решета числового поля: Распределение, Оптимизация — Сито числового поля»). Авторы проекта, создали алгоритм ускоренного разложения больших чисел на простые множители. В настоящий момент (о результатах объявлено 28 февраля 2020 года) использованием алгоритма CADO-NFS взломан шифра RSA-250 (250 десятичных знаков или 829 бит). При этом рассчитано, что для разложения такого большого числа на простые множители потребуется 2700 эталонных процессоров Intel Xeon Gold 6130, работающих в полную мощность в течение одного года. Предыдущее достижение CADO-NFS, разложение на множители RSA-240 (ноябрь 2019 года) предполагает использование 900 указанных процессоров в течение того же промежутка времени. Теоретически, необходимо лишь постоянно увеличивать длину ключа, ведь достигнуть таких мощностей сложно.

Однако задача факторизации больших чисел с помощью решений CADO-NFS имеет экспоненциальную сложность. Полиномиальную сложность в решении задачи факторизации обеспечивает алгоритм Шора, разработанный профессором Питером Шором в 1994 году. Квантовый алгоритм факторизации позволяет разложить число M на простые множители за полиномиальное время используя полиномиальное число логических кубитов. В 2001 году работоспособность алгоритма была проверена компанией IBM, используя квантовый компьютер с 7 кубитами было разложено на простые множители число 15.

Алгоритм Шора имеет 2 составляющие: квантовую часть и обычную.

Обычная часть может быть выполнена на неквантовом компьютере и состоит из следующих шагов для некоторого числа N, которое необходимо разложить на простые множители:

1. Проверяется, кратно ли N двум; N ⁝ 2?
2. Проверяется, является ли N степенью некоторого числа; N=a ^b ?
3. Выбирается случайное число x = random, при условии,
4. что 2 < x < N-1.
5. Находится наибольший общий делитель чисел x и N; НОД (x;N). Если НОД (x;N) ≠ 1, то задача решена, т. к. из этого условия можно найти остальные множители. Если НОД (x;N) = 1, то переходим к квантовой части алгоритма.

Затем алгоритм возвращается к обычной части:

6. Проверяется, является ли r четным числом, r ⁝ 2? Если нет, то алгоритм возвращается к шагу 3 и повторяется квантовая часть.
7. Если r четное, то выполняется равенство (x ^r/2– 1)(x ^r/2 +1) ≡ 0 (mod N), при этом т. к. r — минимальное, то x ^{r /2} ± 1 ≠ 0 (mod N).
8. Последним шагом необходимо найти НОД (x ^{r /2} ± 1; N), который будет одним из простых делителей числа N. Второй простой делитель находится тривиальным способом: N / (НОД (x ^{r /2} ± 1;N)).

Используя алгоритм Шора и возможности перспективных квантовых компьютеров разложение большого числа на простые множители становится полиномиальной задачей, выполняемой за время, ненамного превышающее время шифрования.

Также, рынок услуг квантовых вычислений растет, квантовые компьютеры перестали быть просто абстрактным достижением больших компаний, а начали приносить им прибыль. Параллельно экономическим процессам, регулярно выходят заявления о прогрессе в построении и применяемых инженерных решениях в квантовых компьютерах. В феврале 2020 Intel совместно с QuTech представила первый управляющий чип для масштабируемых квантовых компьютеров их собственной разработки под названием Horse Ridge. В декабре 2020 было представлено уже второе поколение чипа, более гибкое в управлении и позволяющее в реальном времени считывать состояние кубитов. Horse Ridge II позволяет реализовать «многовентильную пульсацию», т. е. одновременное управление множеством криогенных затворов, что обеспечивает как считывание множества кубитов сразу, так и запутанность этого множества. В мае 2021 те же Intel и QuTech представили альфа-версию масштабируемого квантового компьютера, где для управления N кубитами не требуется N кабелей управления. На данном этапе было показано лишь управление двумя кубитами с помощью одного кабеля, при этом точность вычислений составляет порядка 99,7 %.

Исходя из всех имеющихся фактов, можно сделать следующие выводы:

1. Алгоритм RSA основывается на невозможности факторизации больших чисел с использованием имеющихся вычислительных мощностей в разумные сроки, задача разложения с использованием неквантового компьютера имеет экспоненциальную сложность.
2. Для того, чтобы обойти данные ограничения используется алгоритм Шора, который имеет полиномиальную сложность. Но при этом для его реализации необходимо 2n+3 кубитов, где n — количество бит в исходном числе. Квантовых компьютеров таких мощностей в настоящее время не существует.
3. За последние несколько лет лидерами в области квантовых вычислений Intel и QuTech были сделаны ключевые открытия для реализации масштабируемого квантового компьютера с теоретически неограниченным количеством кубит.
4. Исходя из пункта 3, у алгоритма RSA нет будущего, он отойдет на второй план в течение 25–30 лет, когда мощность коммерческих квантовых компьютеров возрастет до необходимой.

Литература:

1. Коутинхо, С. Введение в теорию чисел. Алгоритм RSA. / С. Коутинхо. — Москва: Постмаркет, 2001. — 328 c. — Текст: непосредственный
2. Intel Debuts 2nd-Gen Horse Ridge Cryogenic Quantum Control Chip. — Текст: электронный // Intel: [сайт]. — URL: https://www.intel.com/content/ www/us/en/newsroom/news/2nd-gen-horse-ridge-cryogenic-quantum-control-chip.html#gs.4kpldd (дата обращения: 29.06.2021).
3. CADO-NFS. — Текст: электронный // CADO-NFS: [сайт]. — URL: https://cado-nfs.gitlabpages.inria.fr/ (дата обращения: 29.06.2021).
4. Shore, P. W. Algorithms for quantum computation / P. W. Shore. — Текст: электронный // ACM Digital Library: [сайт]. — URL: https://dl.acm.org/doi/10.1109/SFCS.1994.365700 (дата обращения: 29.06.2021).