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

Определение 1.1

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

Так как отображение инъективно, существует обратное к нему отображение. Обозначим его через . Разумеется, означает шифрование (encryption или enciphering), a — дешифрование (decryption или deciphering). Имеем

для всех открытых текстов и всех .

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

Боб может дешифровать , вычисляя

.

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

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

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

Попытка криптоанализа называется вскрытием.Основное предположение криптоанализа, впервые сформулированное в девятнадцатом веке Датчманом А. Керкхофсом (Dutchman A. Kerckhoffs), состоит в том, что безопасность полностью определяется ключом. Керкхофс предполагает, что у криптоаналитика есть полное описание алгоритма и его реализации. Хотя в реальном мире криптоаналитики не всегда обладают подробной информацией, такое предположение является хорошей рабочей гипотезой. Если противник не сможет взломать алгоритм, даже зная, как он работает, то тем более враг не сможет вскрыть алгоритм без этого знания.

Криптоаналитик (скажем, Ева), подсоединившийся к линии связи, может быть

· пассивным (перехватчиком): криптоаналитик пытается найти (a еще лучше ), исходя из (и любых знаний, которыми он обладает). Определив , можно вскрыть последующие шифртексты.

· активным (злоумышленником): криптоаналитик пытается активно манипулировать передаваемыми данными. Например, он передает собственный шифртекст, вновь передает старый шифртекст, подставляет свои собственные тексты вместо передаваемых шифртекстов и т.п.

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

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

Дано: C1=Ek(P1), C2=Ek(P2), …, Ci=Ek(Pi)

Получить: Либо P1, …,Pi; k; либо алгоритм, как получать Pi+1;из Ci+1=Ek(Pi+1)

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

Дано: P1, C1=Ek(P1), P2, C2=Ek(P2), …, Pi, Ci=Ek(Pi)

Получить: Либо P1, P2,…,Pi; k; либо алгоритм, как получать Pi+1;из Ci+1=Ek(Pi+1).

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

Дано: P1, C1=Ek(P1), P2, C2=Ek(P2), …, Pi, Ci=Ek(Pi), где криптоаналитик может выбирать P1, P2,…,Pi.

Получить: Либо P1, P2,…,Pi; k; либо алгоритм, как получать Pi+1;из Ci+1=Ek(Pi+1).

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

Существует, по крайней мере, еще три дополнительных типа криптоаналитического вскрытия.

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

Дано: С1, P1=Dk(C1), C2, P2=Dk(C2),..., Ci, Pi=Dk(Ci)

Получить: k

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

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

6. Бандитский криптоанализ.Криптоаналитик угрожает, шантажирует или пытает кого-нибудь, пока не получит ключ. Взяточничество иногда называется вскрытием с покупкой ключа.Это очень мощные способы вскрытия, часто являющиеся наилучшим путем взломать алгоритм.

Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Не является невозможным для криптоаналитика добыть открытый текст шифрованного сообщения или подкупить кого-нибудь, кто зашифрует выбранное сообщение. Может и не потребоваться никого подкупать - передав письмо послу, вы, возможно, обнаружите, что письмо будет зашифровано и отправлено в его страну для изучения. Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода: функции, циклические структуры и так далее.

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

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

Хорошие криптографы опираются на мнение других, отделяя хорошие алгоритмы от плохих.