Рандомизированный ответ¶

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

¶История

Концепция рандомизированного ответа впервые была формально описана в 1984 году Шафи Гольдвассером, Сильвио Микали и Чарльзом Ракоффом в их работе «Knowledge Complexity of Interactive Proof-Systems». В этой статье авторы ввели понятие интерактивных доказательств и показали, что для некоторых задач можно доказать знание решения, не раскрывая его самого, используя случайные элементы. Позднее, в 1985 году, Гольдвассер и Микали применили принцип рандомизации к криптографическим примитивам, предложив вероятностное шифрование. До этого большинство классических шифров (например, RSA) были детерминированными: одно и то же сообщение при одном и том же ключе всегда давало одинаковый шифротекст, что делало их уязвимыми для атак по выбранному открытому тексту.

В 1990-х годах рандомизированный ответ стал стандартным элементом многих криптосистем, включая стандарт шифрования IEEE P1363. В 2000-х годах он был интегрирован в протоколы анонимной связи, такие как Tor (The Onion Router), где используется для скрытия длины сообщений и предотвращения анализа трафика.

¶Принцип работы

Рандомизированный ответ основан на добавлении случайной строки (называемой «солью» или «nonce») к открытому тексту перед шифрованием. Эта случайная строка генерируется каждый раз заново, даже если шифруется одно и то же сообщение. В результате шифротекст становится вероятностным: при каждом шифровании одного и того же сообщения получается разный результат.

¶Математическая модель

Пусть \( E \) — алгоритм шифрования, \( D \) — алгоритм расшифрования, \( k \) — ключ, \( m \) — открытый текст, а \( r \) — случайная строка. Тогда рандомизированное шифрование можно записать как:

\[ c = E_k(m, r) \]

где \( c \) — шифротекст. Расшифрование выполняется как:

\[ m = D_k(c) \]

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

¶Свойства

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

¶Классификация

¶По способу генерации случайности

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

¶По области применения

• Криптографический рандомизированный ответ: используется в алгоритмах шифрования (RSA-OAEP, Эль-Гамаля, Пэйе) и подписи (DSA, ECDSA).
• Сетевой рандомизированный ответ: применяется в протоколах анонимной связи (Tor, I2P) для скрытия длины пакетов и предотвращения анализа трафика.
• Доказательный рандомизированный ответ: используется в протоколах доказательств с нулевым разглашением, где случайные элементы позволяют верификатору убедиться в правильности утверждения без раскрытия секрета.

¶Применение

¶Криптосистемы с открытым ключом

• RSA-OAEP (Optimal Asymmetric Encryption Padding) — стандарт шифрования, использующий рандомизированное дополнение для предотвращения атак по выбранному шифротексту. Включает случайную строку в сообщение перед возведением в степень.
• Криптосистема Эль-Гамаля — вероятностное шифрование на основе задачи дискретного логарифмирования. Для каждого сообщения генерируется случайное число \( k \), которое используется для вычисления общей секретной точки.
• Криптосистема Пэйе — гомоморфное шифрование, где случайная строка \( r \) входит в формулу шифрования: \( c = g^m \cdot r^n \mod n^2 \).

¶Анонимная связь

• Tor — сеть луковой маршрутизации, где каждый пакет дополняется случайными данными до фиксированной длины, чтобы скрыть реальный размер сообщения. Это предотвращает атаки по размеру пакета.
• I2P (Invisible Internet Project) — использует рандомизированные ответы для создания туннелей, где каждый сегмент данных дополняется случайным шумом.

¶Доказательства с нулевым разглашением

• Протокол Гольдвассера-Микали-Ракоффа — интерактивное доказательство для задачи изоморфизма графов, где рандомизированный ответ позволяет верификатору убедиться в знании изоморфизма без его раскрытия.
• zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) — используют рандомизированные ответы для генерации доказательств, которые могут быть проверены без раскрытия секретных данных.

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

• Увеличение размера данных: добавление случайной строки увеличивает размер шифротекста, что может быть критично для систем с ограниченной пропускной способностью.
• Зависимость от качества случайности: если генератор случайных чисел предсказуем, рандомизированный ответ теряет свои защитные свойства. В 2013 году было показано, что в некоторых реализациях RSA-OAEP использовались слабые генераторы, что делало систему уязвимой.
• Вычислительная сложность: генерация случайных строк и их обработка требуют дополнительных вычислительных ресурсов, что может быть проблемой для встраиваемых устройств.
• Атаки по времени: в некоторых реализациях время выполнения рандомизированного ответа может зависеть от данных, что позволяет проводить атаки по сторонним каналам.

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

• В 2012 году исследователи из Массачусетского технологического института показали, что рандомизированный ответ может быть использован для создания «квантово-устойчивых» криптосистем, основанных на задачах решёток.
• В протоколе Tor рандомизированный ответ используется не только для скрытия длины сообщений, но и для предотвращения атак по времени: каждый пакет задерживается на случайное время перед отправкой.
• В криптосистеме Пэйе рандомизированный ответ позволяет выполнять гомоморфные операции: сложение зашифрованных чисел соответствует умножению шифротекстов, что используется в системах электронного голосования.

¶Источники

• Goldwasser, S., Micali, S., & Rackoff, C. (1989). «The Knowledge Complexity of Interactive Proof-Systems». SIAM Journal on Computing, 18(1), 186–208.
• Goldwasser, S., & Micali, S. (1984). «Probabilistic Encryption». Journal of Computer and System Sciences, 28(2), 270–299.
• Bellare, M., & Rogaway, P. (1994). «Optimal Asymmetric Encryption». Advances in Cryptology — EUROCRYPT ’94, 92–111.
• Paillier, P. (1999). «Public-Key Cryptosystems Based on Composite Degree Residuosity Classes». Advances in Cryptology — EUROCRYPT ’99, 223–238.
• Dingledine, R., Mathewson, N., & Syverson, P. (2004). «Tor: The Second-Generation Onion Router». Proceedings of the 13th USENIX Security Symposium.