Доказуемая стойкость

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

История развития

Идея формального доказательства безопасности криптографических систем восходит к работам Клода Шеннона 1940-х годов, который ввёл понятие «совершенной стойкости» (например, для одноразового блокнота). Однако практическое применение доказуемой стойкости началось в 1980-х годах с появлением концепции «вычислительной стойкости» и модели случайного оракула.

Ранние этапы

• 1984 год — Шафи Гольдвассер и Сильвио Микали предложили первое строгое определение семантической безопасности для шифрования с открытым ключом.
• 1988 год — Амос Фиат и Ади Шамир разработали протокол аутентификации с нулевым разглашением, который стал основой для многих доказуемо стойких схем.
• 1993 год — Михаэль Блюм, Мануэль Блюм и Майкл Шуб ввели модель «общего случайного оракула», которая упростила доказательства для многих практических алгоритмов.

Современный период

• 2000-е годы — Развитие теории «постквантовой криптографии», где доказуемая стойкость основывается на задачах, устойчивых к атакам квантовых компьютеров (например, решёточные задачи).
• 2010-е годы — Появление стандартов, таких как NIST PQC, где доказуемая стойкость стала обязательным требованием для кандидатов в новые криптографические алгоритмы.

Основные модели безопасности

Доказуемая стойкость всегда формулируется в рамках конкретной модели, которая определяет возможности злоумышленника и цели атаки.

Модель случайного оракула

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

Стандартная модель

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

Модель с общим ключом

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

Классификация по типам атак

Доказуемая стойкость классифицируется по тому, какую атаку может проводить злоумышленник:

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

Примеры доказуемо стойких алгоритмов

Шифрование

• RSA-OAEP — доказуемо стойкий в модели случайного оракула против атак CCA2.
• Cramer-Shoup — доказуемо стойкий в стандартной модели против атак CCA2 на основе предположения о сложности дискретного логарифмирования.
• AES-GCM — доказуемо стойкий в модели случайного оракула при условии, что AES является псевдослучайной перестановкой.

Цифровые подписи

• Schnorr — доказуемо стойкий в модели случайного оракула против атак с выбором сообщения.
• BLS — доказуемо стойкий на основе предположения о сложности билинейных отображений.

Протоколы аутентификации

• Протокол Диффи-Хеллмана — доказуемо стойкий в модели с общим ключом при условии сложности задачи Диффи-Хеллмана.
• Протокол Needham-Schroeder — доказуемо стойкий в модели с идеальным шифрованием.

Критика и ограничения

Несмотря на математическую строгость, доказуемая стойкость имеет ряд ограничений:

• Зависимость от модели — доказательство в модели случайного оракула не гарантирует стойкость в реальной реализации, если хеш-функция не является идеальной.
• Вычислительные предположения — стойкость основана на недоказанных математических гипотезах (например, P ≠ NP). Если эти гипотезы окажутся ложными, доказательства теряют силу.
• Практическая реализация — реализация алгоритма может содержать ошибки (например, утечку побочных каналов), которые не учитываются в формальной модели.
• Постквантовая угроза — многие классические задачи (факторизация, дискретное логарифмирование) становятся разрешимыми с помощью квантовых компьютеров, что требует пересмотра доказательств.

Применение в России

В Российской Федерации доказуемая стойкость учитывается при разработке национальных криптографических стандартов. Например, алгоритмы ГОСТ Р 34.10-2012 (цифровая подпись) и ГОСТ Р 34.11-2012 (хеш-функция «Стрибог») прошли формальный анализ в рамках модели случайного оракула. В 2023 году началась работа над постквантовыми стандартами, где доказуемая стойкость является обязательным требованием.

Источники

• Гольдвассер Ш., Микали С. «Вероятностное шифрование и как играть в покер, сохраняя в секрете любую частичную информацию» (1984)
• Блюм М., Блюм М., Шуб М. «Простая и безопасная аутентификация с нулевым разглашением» (1993)
• Белларе М., Рогауэй П. «Оптимальная асимметричная схема шифрования — как шифровать с помощью RSA» (1994)
• Крамер Р., Шоуп В. «Схема шифрования с открытым ключом, доказуемо стойкая против атак с выбранным шифротекстом» (1998)
• Федеральный закон РФ «О техническом регулировании» (2002) — требования к криптографическим средствам
• Национальный институт стандартов и технологий США (NIST). «Постквантовая криптография: стандартизация» (2023)