Инструменты пользователя

Инструменты сайта


examination:mszki:question49

Криптоанализ и основные методы криптоанализа

Криптоанализ — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа. Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году. Неформально криптоанализ называют также взломом шифра. В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов.

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

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

Атаки на основе шифротекста

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

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

Атака на основе открытых текстов и соответствующих шифротекстов

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

1. Найти ключ, использованный для преобразования открытого текста в шифротекст

2. Создать алгоритм, способный дешифровать любое сообщение, закодированное с помощью этого ключа

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

В случае взлома переписки можно сделать предположение, что письмо имеет структуру типа:

• «Приветствие»

• «Основной текст»

• «Заключительная форма вежливости»

• «Подпись»

Следовательно, атака может быть организована путём подбора различных видов «Приветствия» (например, «Здравствуйте!», «Добрый день» и т. д.) и/или «Заключительной формы вежливости» (таких как «С уважением», «Искренне Ваш» и т. п.). Легко заметить, что данная атака сильнее атаки на основе одного лишь шифротекста.

Атака на основе подобранного открытого текста

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

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

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

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

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

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

Атаки на основе адаптивно подобранного открытого текста

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

Алгоритм атаки.

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

1. Выбирается пара открытых текстов с подобранной разностью

2. Тексты подаются на шифрующее устройство

3. Соответствующие шифртексты так же будут иметь некоторую разность

4. Набирается статистика из пар вида открытый текст — шифртекст

5. Сопоставляются разность между открытыми текстами с разностью между шифртекстами

6. На основе собранных данных делается предположение о ключе системы

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

Атака на основе подобранного шифротекста

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

Сжато сформулировать эту задачу можно таким образом: Дано: С1, P1=Dk(С1), С2, P2=Dk(С2), С3, P3=Dk(С3), …, Сn, Pn=Dk(Сn), где Сn — n-ый имеющийся шифротекст, Pn — соответствующий Сn открытый текст, а Dk — функция дешифрования при помощи ключа k. Найти: используемый ключ шифрования k. Интересным может быть тот факт, что атака на основе подобранного шифротекста также может носить название «Атаки в обеденное время» (lunchtime attack) или «Ночной атаки» (midnight attack). Скажем, в названии «Атаки в обеденное время» отражается тот факт, что легитимный пользователь может оставит свой компьютер с функцией дешифрования без присмотра на время обеда, а криптоаналитик может этим воспользоваться.

Атака на основе подобранного ключа

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

examination/mszki/question49.txt · Последние изменения: 2014/01/15 12:20 (внешнее изменение)