КлючКлюч

шифрованиядешифрирования

Первоначальный

Открытый текст ± Шифротекст I открытый текст

-»Шифрование -► Дешифрирование-►

Рис. 1-3. Шифрование и дешифрирование с двумя различными ключами

Симметричные алгоритмы

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

Ek(M)=C

Dk(C)=M

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

Алгоритмы с открытым ключом

Алгоритмы с открытым ключом (называемые асимметричными алгоритмами) разработаны таким образом, что ключ, используемый для шифрования, отличается от ключа дешифрирования . Более того, ключ дешифрирования не может быть (по крайней мере в течение разумного интервала времени ) рассчитан по ключу шифрования. Алгоритмы называются "с открытым ключом", потому что ключ шифрования может быть открытым: кто угодно может использовать ключ шифрования для шифрования сообщения, но только конкретный ч е-ловек с соответствующим ключом дешифрирования может расшифровать сообщение. В этих системах ключ шифрования часто называется открытым ключом, а ключ дешифрирования - закрытым. Закрытый ключ иногда называется секретным ключом, но чтобы не было путаницы с симметричными алгоритмами, этот термин не используется в данной книге. Шифрование с открытым ключом K обозначается как:

Ek(M)=C

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

Dk(C)=M

Иногда сообщения шифруются закрытым ключом, а дешифрируются открытым, что используется для ци ф-ровой подписи (см. раздел 2.6). Несмотря на возможную путаницу эти операции, соответственно, обозначаю т-ся как:

Ek(M)=C

Dk(C)=M

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

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

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

вается компрометацией.)

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

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

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

Дано: C]=Ek(P]), C2=Ek(P2), . . . C,=Ek(P.)

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

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

Дано: P], C]=Ek(P]), P2, C2=Ek(P2), . . . Pi, CP,)

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

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

Дано: P], C]=Ek(P]), P2, C2=Ek(P2), . . . P„ C,=Ek(P.)

где криптоаналитик может выбирать P], P2, . . . Pi

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

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

Существует по крайней мере еше три типа криптоаналитической вскрытия .

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

Дано: C], P1=Dk(C1), C2, P2=Dk(C2), . . . C„ P,=Dk(Q)

Получить: k

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

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

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

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

И не забывайте о предположении Керкхофса: если мощь вашей новой криптосистемы опирается на то, что взломщик не знает, как работает алгоритм, вы пропали . Если вы считаете, что хранение принципа работы алгоритма в секрете лучше защитит вашу криптосистему, чем предложение академическому сообществу проан а-лизировать алгоритм, вы ошибаетесь . А если вы думаете, что кто-то не сможет дезассемблировать ваш исхо д-ный код и восстановить ваш алгоритм, вы наивны. (В 1994 году такое произошло с алгоритмом RC4, см. раздел 17.1.) Нашими лучшими алгоритмами являются те, которые были разработаны открыто, годами взламыв а-лись лучшими криптографами мира и все еще несокрушимы . (Агентство Национальной Безопасности хранит свои алгоритмы в секрете, но у них работают лучшие криптографы мира, а у вас - нет. Кроме того, они обсу ж-дают свои алгоритмы друг с другом, полагаясь на способность товарища обнаружить все слабости в своей р а-боте.)

У криптоаналитиков не всегда есть доступ к алгоритмам (например, вскрытие в ходе Второй мировой войны Соединенными Штатами японского дипломатического кода PURPLE [794]), но часто они его получают. Если алгоритм используется в коммерческой программе безопасности, то это просто вопрос времени и денег, удас т-ся ли дезассемблировать программу и раскрыть алгоритм . Если же алгоритм используется в военной системе связи, то это просто вопрос времени и денег купить (или украсть) аппаратуру и реконструировать алгоритм .

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

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

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

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

Ларс Кнудсен (Lars Knudsen) разбил вскрытия алгоритмов по следующим категориям, приведенным в порядке убывания значимости [858]:

1.Полное вскрытие. Криптоаналитик получил ключ, K, такой, что DK(C) = P.

2.Глобальная дедукция. Криптоаналитик получил альтернативный алгоритм, A, эквивалентный DK(C) без знания K.

3.Местная (или локальная) дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста.