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

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

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

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

Дано: Ci=Ek(Pi), C2=Ek(P2), . . . Ci=Ek(Pi)

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

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

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

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

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

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

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

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

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

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

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

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

Получить: 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. Местная (или локальная) дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста.

4. Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или откр ы-том тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее.

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

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

1. Сложность данных. Объем данных, используемых на входе операции вскрытия .

2. Сложность обработки. Время, нужное для проведения вскрытия. Часто называется коэффициентом работы.

3. Требования к памяти. Объем памяти, необходимый для вскрытия.

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

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

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

Исторические термины

Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фразу "ПОВОРОТ НАЛЕВО НА 90 ГРАДУСОВ", слово "ЛЕДЕНЕЦ" - фразу "ПОВОРОТ НАПРАВО НА 90 ГРАДУСОВ", а слова "ПОДСТАВЬ УХО" могут кодировать слово "ГАУБИЦА". Коды такого типа не рассматриваются в данной кн иге, см. [794,795]. Коды полезны только при определенных обстоятельствах. Если у вас нет кода для "МУРАВЬЕДЫ", вы не сможете передать это понятие. А используя шифр можно сказать все.

1.2 Стеганография

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

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

Имитационные функции Питера Уэйнера (Peter Wayner) маскируют сообщения. Эти функции изменяют сообщение так, что его статистический профиль становится похожим на что-нибудь еще: раздел The New York