Был ли RSA только что уничтожен немецким математиком на пенсии?

Огромная часть цифрового мира полагается на шифрование RSA для обеспечения конфиденциальности и безопасности. Недавняя математическая статья, которая «уничтожает криптосистему RSA», взбудоражила криптографов. Правильно ли они беспокоятся?

Что такое шифрование RSA?

Криптосистема Rivest-Shamir-Adleman (RSA) решила проблему шифрования данных, чтобы их мог расшифровать только предполагаемый получатель. В 1977 году соавторы — Рон Ривест, Ади Шамир и Леонард Адлеман — предложили элегантное решение, основанное на новом способе использования ключей шифрования. Проще говоря, ключи шифрования — это очень большие значения, используемые в математических процессах, применяемых к данным для их шифрования. Прорывом, который RSA привнес в мир криптографии, стало использование закрытых и открытых ключей.

Следует также упомянуть Клиффорда Кокса, главного математика в штаб-квартире правительственных коммуникаций Великобритании (GCHQ), который в 1973 году применил шифрование/дешифрование с открытым и закрытым ключами к криптографии. Информация была засекречена и оставалась секретной. Его рассекретили только в 1997 году. Очевидно, великие умы думают одинаково.

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

Сертификат открытого ключа используется для подтверждения личности владельца открытого ключа. Двумя распространенными примерами сертификатов открытых ключей являются сертификаты Secure Socket Layer и Transport Layer (SSL/TLS). Открытые ключи могут передаваться между людьми, которые хотят общаться, или их можно получать с серверов ключей, таких как сервер ключей OpenPGP.

Secure Shell (SSH), OpenPGP, S/MIME и SSL/TSL используют шифрование RSA, и все браузеры используют его. Некоторые криптовалюты используют его. Практически весь мир электронной коммерции так или иначе зависит от RSA. Все, что угрожает целостности криптосистемы RSA, требует тщательного изучения.

Угрозы криптографии RSA

Центральным элементом алгоритмов шифрования является необратимость. Математические преобразования, которые выполняются с данными, должны быть необратимыми для всех практических целей.

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

Факторинг становится намного сложнее очень быстро, поскольку числа становятся больше. Чтобы взломать этот тип шифрования, потребуется непомерно много времени — по некоторым оценкам, триллионы лет. Это обеспечивает безопасную псевдонеобратимость. На самом деле это не является необратимым, но на это уйдет так много времени, что это может быть действительно необратимым.

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

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

Ошибки в реализации RSA вызывали проблемы в прошлом. Теоретическая RSA должна быть преобразована в работающую программную реализацию, прежде чем она станет полезной, а сложное программное обеспечение часто содержит ошибки. В алгоритмы, используемые в криптосистеме RSA, были внесены изменения и замены, поскольку в реализации были обнаружены недостатки. Старые версии устарели и заменены новыми версиями.

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

Что представляет собой новая угроза?

Профессор Клаус Петер Шнорр – математик и криптограф на пенсии. Он был профессором кафедры математики и информатики Университета Иоганна Вольфганга Гёте во Франкфурте-на-Майне.

Препринт статьи Шнорра (препринт означает, что он находится на поздней стадии разработки, но еще не прошел рецензирование) предлагает новый метод факторизации простых целых чисел на современных вычислительных платформах со значительно ускоренной скоростью. Статья называется «Быстрый факторинг целых чисел с помощью алгоритмов SVP». SVP расшифровывается как задача о кратчайших векторах. Аннотация заканчивается провокационным предложением «Это разрушает криптосистему RSA».

Сокращая очень сложную часть работы в простое утверждение, мы получаем улучшение на порядок скорости факторинга. Увеличение скорости будет достигнуто за счет усовершенствования некоторых ранних работ Шнорра. Очевидно, что революционное сокращение факторинговых целых чисел окажет значительное влияние на криптосистему RSA. То есть, если теоретическая статья фактически верна и если практическая реализация может подтвердить гипотезу.

В статье продвигается метод факторинга с использованием математических структур, называемых решетками. Профессор Шнорр является широко признанным экспертом в этой области и ее применении в криптографии. В документе утверждается, что новый метод значительно быстрее, чем алгоритм общего числового поля (GNFS), который считается самым быстрым современным методом для разложения больших чисел на множители.

Анализ угрозы

Работа Шорра носит теоретический характер. Нет ни таймингов, ни результатов от внедрений. Теоретический выигрыш в скорости по сравнению с GNFS звучит впечатляюще на бумаге, но выдерживают ли теория и математика проверку со стороны тех, кто действительно понимает это на уровне, необходимом для осмысленного комментирования?

Д-р Лео Дука – исследователь группы криптографии в Centrum Wiskunde & Informatica (CWI). CWI — национальный исследовательский институт математики и информатики в Нидерландах. Дука защитил докторскую диссертацию. в 2013 году на тему «Сигнатуры на основе решетки: атаки, анализ и оптимизация». Он работал с решетками на протяжении всей своей карьеры. Он также криптограф, так что он в высшей степени способен рецензировать статью Шнорра.

Что еще лучше для наших целей, доктор Лео Дюкас — программист. Если вы хотите поиграть в Cryptris, его асимметричную криптографическую игру, вперед. Его академический исходный код разбросан по GitHub. Некоторые из них находятся в его собственном репозитории, а гораздо больше находится в репозиториях других проектов с несколькими авторами, над которыми он работал.

Он выполнил обзор и анализ статьи Шнорра. Он также создал реализацию алгоритмов Шнорра в виде скрипта SageMath. Он назвал его SchnorrGate. Дукас также указывает на обсуждение криптографии StackExchange. Это исследует ошибку в одной из формул в статье, которая, если ее использовать в печатном виде, дает очень неточные результаты. С исправлением этой формулы метод факторинга Шнорра действительно работает, но гораздо медленнее, чем он предсказывает.

Выводы Дука из его тестов SageMath подтверждают это. Они показывают, что алгоритмы факторинга Шнорра действительно работают, но гораздо медленнее, чем лучшие методы, доступные сегодня.

Мы все снова можем дышать

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

Возможно, наступила бы эра криптографии на эллиптических кривых (ECC).