Защита информации 2 5 (стр. 12 из 14)

Дано:

,

где криптоаналитик может выбирать

Определить: либо

, либо алгоритм восстановления из .

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

Кроме перечисленных типов известны так же, по крайней мере, еще три типа криптоаналитических атак.

1) Атака на основе подобранного шифротекста.Криптоаналитик может выбирать различные шифротексты для расшифрования. А так же имеет доступ к расшифрованным открытым текстам. Например, у криптоаналитика есть доступ к «черному ящику», выполняющему автоматическое расшифровывание. Его задача состоит в раскрытии ключа.

Дано:

.

Получить:

.

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

2) Атака на основе подобранного ключа.Такой тип вскрытия не означает, что криптоаналитик может выбирать ключ – просто он кое-что знает о связях между различными ключами.

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

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

10.2 Взлом шифров с открытым ключом на основе подобранного шифротекста

СЦЕНАРИЙ №1.Еве, подслушивающей линии связи Алисы, удалось перехватить сообщение

,зашифрованное с помощью RSAоткрытым ключом Алисы. Ева хочет прочитать сообщение , т.е. необходимо узнать .

(11.1)

Для вскрытия

она сначала выбирает первое случайное число r, меньшее n и достает открытый ключ Алисы . Затем она вычисляет:

(11.2)

Если

, то

.

Далее Ева просит подписать Алису y её закрытым ключом, тем самым расшифровав y. (Алиса должна подписать сообщение, а не его хесл-значение). Алиса никогда раньше не видела y. Алиса посылает Еве:

(11.3)

После этого Ева вычисляет:

(11.4)

Ева получает

.

СЦЕНАРИЙ №2. Трент – компьютер-нотариус. Если Алиса хочет заверить документ, она посылает Тренту. Трент подписывает его цифровой подписью RSAи отправляет обратно. (Однонаправленные хеш-функции не используются, Трент шифрует своим закрытым ключом все сообщение). Ева хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он никогда не подпишет. Это сообщение может содержать фальшивую временную метку, или же автором этого сообщения может являться другое лицо. Какой бы не была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение

. Сначала Ева выбирает произвольное значение x и вычисляет:

(11.5)

Значение

– это открытый ключ Трента, который должен быть опубликован. Далее Ева вычисляет

(11.6)

и посылает Тренту на подпись. Трент возвращает

.Теперь Ева вычисляет значение

(11.7)

которое и является подписью

СЦЕНАРИЙ №3.Ева хочет, чтобы Алиса подписала сообщение

.Она создает два сообщения , ,такие, что:

(11.8)

Если Ева сможет заставить Алису подписать

и ,она сможет вычислить подпись для :

(11.9)

Вывод: Никогда не используйте алгоритм RSAдля подписи случайных документов, подсунутых вас посторонними. Вначале всегда следует воспользоваться однонаправленной хеш-функцией. Формат блоков, предлагаемый ISO 9796, предотвращает описанное вскрытие.

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

Возможна реализация RSA, в которой всем пользователям раздается одинаковый модуль

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

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

– открытый текст сообщения, и – два ключа шифрования, а – общий модуль. Шифротекстами сообщения являются:

()

Криптоаналитик знает

. Сообщение он находит по следующему алгоритму.

Так как

и – взаимно простые числа, то с помощью расширенного алгоритма Евклида можно найти и , для которых

()

Считая

отрицательным (здесь или , или должны быть отрицательными, положим, что отрицательным будет ), воспользуемся расшифрованным алгоритмом Евклида для вычисления .Затем