Вычислительная стойкость

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

История и предпосылки

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

В 1970-х годах, с развитием компьютерных сетей и необходимостью защищать данные в открытых каналах, возникла потребность в практичных криптосистемах. В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали работу «Новые направления в криптографии», где ввели понятие односторонней функции с потайным входом и заложили основы криптографии с открытым ключом. Именно в этой парадигме вычислительная стойкость стала центральным понятием: безопасность алгоритмов, таких как RSA, основывается на сложности решения определённых математических задач (факторизация больших чисел, дискретное логарифмирование), а не на недоступности информации.

Классификация стойкости

В криптографии принято различать несколько уровней стойкости по отношению к вычислительным возможностям атакующего:

• Информационно-теоретическая (абсолютная) стойкость: Шифротекст не содержит никакой информации об открытом тексте, даже при наличии неограниченных вычислительных мощностей. Пример — шифр Вернама (одноразовый блокнот).
• Вычислительная стойкость: Взлом алгоритма требует выполнения не менее N операций, где N — число, значительно превышающее возможности современных и прогнозируемых в обозримом будущем компьютеров (например, 2¹²⁸ операций). Стойкость основана на предположении, что не существует алгоритма, решающего задачу быстрее, чем за экспоненциальное время.
• Доказуемая стойкость: Стойкость алгоритма строго сводится к сложности решения некоторой хорошо изученной математической проблемы (например, задачи факторизации или дискретного логарифмирования). Это подвид вычислительной стойкости, где утверждение о безопасности имеет математическое доказательство в рамках определённой модели (например, модели случайного оракула).

Математические основы

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

• Задача факторизации: Разложение большого составного числа (произведения двух больших простых чисел) на множители. Лежит в основе алгоритма RSA.
• Задача дискретного логарифмирования: Нахождение показателя степени в конечном поле или на эллиптической кривой. Используется в алгоритмах Диффи-Хеллмана, DSA, ECDSA.
• Задача о рюкзаке: Некоторые варианты (например, Меркла-Хеллмана) были взломаны, но другие варианты остаются стойкими.
• Задача обучения с ошибками (LWE): Стойкость многих постквантовых криптосистем (например, на решётках) основана на сложности решения этой задачи.

Для оценки вычислительной стойкости используется понятие битовой стойкости. Например, ключ длиной 128 бит в симметричном шифре (AES) обеспечивает стойкость 2¹²⁸ операций. Для асимметричных систем, из-за наличия математической структуры, эквивалентная стойкость достигается при значительно большей длине ключа: для RSA это 3072 бита, для эллиптических кривых — 256 бит.

Практические аспекты и ограничения

Вычислительная стойкость не является абсолютной гарантией. Она зависит от нескольких факторов:

• Прогресс в вычислительной технике: Развитие квантовых компьютеров может сделать многие современные алгоритмы (RSA, ECDSA) нестойкими. Квантовый алгоритм Шора решает задачи факторизации и дискретного логарифмирования за полиномиальное время. В ответ на это разрабатывается постквантовая криптография, основанная на задачах, устойчивых к квантовым атакам (решетки, коды, хэш-функции).
• Криптоанализ: Открытие новых математических методов или уязвимостей в реализации может снизить вычислительную стойкость. Например, атаки на основе побочных каналов (время выполнения, энергопотребление) могут позволить восстановить ключ быстрее, чем при полном переборе.
• Параметры безопасности: Стойкость алгоритма напрямую зависит от длины ключа. Рекомендуемые длины ключей периодически пересматриваются (например, NIST, АНБ, российский ГОСТ Р 34.10-2012). На 2024 год для симметричных шифров минимальной считается стойкость 128 бит, для асимметричных — 2048 бит (RSA) или 256 бит (эллиптические кривые).

Применение в современных системах

Вычислительная стойкость лежит в основе всех современных криптографических протоколов:

• TLS/SSL: Защита веб-трафика (HTTPS).
• SSH: Безопасное удалённое управление серверами.
• IPsec: Защита сетевого трафика на уровне IP.
• Электронная подпись: Подтверждение подлинности документов (например, в российском ГОСТ Р 34.10-2012).
• Блокчейн и криптовалюты: Безопасность транзакций и хранения средств (например, алгоритм ECDSA в биткойне).

Критика и альтернативы

Основная критика вычислительной стойкости связана с её зависимостью от недоказанных математических гипотез. Ни для одной из используемых односторонних функций не доказано, что она действительно является односторонней. В случае, если P = NP, многие из них могут быть взломаны за полиномиальное время.

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

Интересные факты

• В 2017 году Google объявила о начале тестирования постквантовых алгоритмов в своих браузерах (Chrome) для защиты от будущих квантовых атак.
• Российский стандарт криптографической защиты ГОСТ Р 34.10-2012 использует эллиптические кривые над полем характеристики 2 и обеспечивает вычислительную стойкость до 256 бит.
• В 2022 году NIST объявил о выборе первых четырёх алгоритмов для постквантовой стандартизации, включая CRYSTALS-Kyber (шифрование) и CRYSTALS-Dilithium (подпись).

Источники

• Шеннон, К. «Теория связи в секретных системах» (1949).
• Диффи, У., Хеллман, М. «Новые направления в криптографии» (1976).
• Менезес, А., ван Орсхот, П., Ванстон, С. «Справочник по прикладной криптографии» (1996).
• NIST. «Post-Quantum Cryptography: Status and Updates» (2023).
• ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».