Файл: MethodFull.doc

Е_К(М)=С

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

D_K(С)=M

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

Е_К(М)=С

D_K(C)=M

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Безопасность алгоритмов

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

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

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

• Полное вскрытие.Криптоаналитик получил ключ, К, такой, что D_K(C) — Р.

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

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

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

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

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

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

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

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

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

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

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