Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Сообщения и шифрование Само сообщение называется открытым текстом (иногда используется термин клер). Изменение вида сооб- щения так, чтобы спрятать его суть называется шифрованием. Шифрованное сообщение называется шифро- текстом. Процесс преобразования шифротекста в открытый текст называется дешифрированием. Эта после- довательность показана на 0th. (Если вы хотите следовать стандарту ISO 7498-2, то в английских текстах используйте термины "enchipher" вместо " encrypt" ("зашифровывать") и "dechipher" вместо " decrypt" ("дешифровывать")). Искусство и наука безопасных сообщений, называемая криптографией, воплощается в жизнь криптогра- фами. Криптоаналитиками называются те, кто постоянно используют криптоанализ, искусство и науку взламывать шифротекст, то есть, раскрывать, что находится под маской . Отрасль математики, охватывающая криптографию и криптоанализ, называется криптологией, а люди, которые ей занимаются, - криптологами. Современным криптологам приходится неплохо знать математику . Шифрование Дешифрирование Первоначальный открытый текст Открытый текст Шифротекст Рис. 1-1. Шифрование и дешифрирование Обозначим открытый текст как M (от message, сообщение), или P (от plaintext, открытый текст). Это может быть поток битов, текстовый файл, битовое изображение, оцифрованный звук, цифровое видеоизображение… да что угодно. Для компьютера M - это просто двоичные данные. (Во всех следующих главах этой книги ра с- сматриваются только двоичные данные и компьютерная криптография .) Открытый текст может быть создан для хранения или передачи. В любом случае , M - это сообщение, которое должно быть зашифровано . Обозначим шифротекст как C (от ciphertext). Это тоже двоичные данные, иногда того же размера, что и M, иногда больше. (Если шифрование сопровождается сжатием, C может быть меньше чем M. Однако, само шиф- рование не обеспечивает сжатие информации .) Функция шифрования E действует на M, создавая C. Или, в ма- тематической записи: E(M) = C В обратном процессе функция дешифрирования D действует на C, восстанавливая M: D(C) = M Поскольку смыслом шифрования и последующего дешифрирования сообщения является восстановление пе р- воначального открытого текста, должно выполняться следующее равенство : D(E(M)) = M Проверка подлинности, целостность и неотрицание авторства Кроме обеспечения конфиденциальности криптография часто используется для других функций : — Проверка подлинности. Получатель сообщения может проверить его источник, злоумышленник не сможет замаскироваться под кого-либо. — Целостность. Получатель сообщения может проверить, не было ли сообщение изменено в процессе доставки, злоумышленник не сможет подменить правильное сообщение ложным. — Неотрицание авторства. Отправитель не сможет ложно отрицать отправку сообщения. Существуют жизненно важные требования к общению при помощи компьютеров, также как существуют ана- логичные требования при общении лицом к лицу. То, что кто-то является именно тем, за кого он себя выдает … что чьи-то документы - водительские права, медицинская степень или паспорт - настоящие … что документ, по- лученный от кого-то, получен именно от этого человека… Как раз это обеспечивают проверка подлинности, целостность и неотрицание авторства. Алгоритмы и ключи Криптографический алгоритм, также называемый шифром, представляет собой математическую фун к- цию, используемую для шифрования и дешифрирования . (Обычно это две связанных функции: одна для ши ф- рования, а другая для дешифрирования.) Если безопасность алгоритма основана на сохранении самого алгоритма в тайне, это ограниченный алго- ритм. Ограниченные алгоритмы представляют только исторический интерес, но они совершенно не соответс т- вуют сегодняшним стандартам. Большая или изменяющаяся группа пользователей не может использовать такие алгоритмы, так как всякий раз, когда пользователь покидает группу, ее члены должны переходить на другой алгоритм. Алгоритм должен быть заменен и, если кто-нибудь извне случайно узнает секрет. Что еще хуже, ограниченные алгоритмы не допускают качественного контроля или стандартизации. У ка ж- дой группы пользователей должен быть свой уникальный алгоритм . Такие группы не могут использовать от- крытые аппаратные или программные продукты - злоумышленник может купить такой же продукт и раскрыть алгоритм. Им приходится разрабатывать и реализовывать собственные алгоритмы. Если в группе нет хорошего криптографа, то как ее члены проверят, что они пользуются безопасным алгоритмом? Несмотря на эти основные недостатки ограниченные алгоритмы необычайно популярны для приложений с низким уровнем безопасности. Пользователи либо не понимают проблем, связанных с безопасностью своих систем, либо не заботятся о них. Современная криптография решает эти проблемы с помощью ключа K. Такой ключ может быть любым значением, выбранным из большого множества. Множество возможных ключей называют пространством ключей. И шифрование, и дешифрирование этот ключ (то есть, они зависят от ключа, что обозначается инде к- сом K), и теперь эти функции выглядят как: E K (M)=C D K (C)=M При этом выполняется следующее равенство (см -1-й): D K (E K (M))=M Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи (см -2-й). То есть ключ шифрования, К 1 , отличается от соответствующего ключа дешифрирования, K 2 . В этом случае: E (M)=C D (C)=M D (E (M))=M K K K K 1 2 2 1 Безопасность этих алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован. Продукты, использующие этот алгоритм, могут широко тиражироваться. Не имеет значения, что злоумышленнику известен ваш алгоритм, если ему не известен ко н- кретный ключ, то он не сможет прочесть ваши сообщения . Криптосистема представляет собой алгоритм плюс все возможные открытые тексты, шифротексты и ключи . Шифрование Дешифрирование Первоначальный открытый текст Открытый текст Шифротекст Ключ Ключ Рис. 1-2. Шифрование и дешифрирование с ключом Шифрование Дешифрирование Первоначальный открытый текст Открытый текст Шифротекст Ключ шифрования Ключ дешифрирования Рис. 1-3. Шифрование и дешифрирование с двумя различными ключами Симметричные алгоритмы Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом . Симметричные алгоритмы, иногда называемые условными алгоритмами , представляют собой алгоритмы, в которых ключ шифрования может быть рассчитан по ключу дешифрирования и наоборот . В большинстве сим- метричных алгоритмов кличи шифрования и дешифрирования одни и те же . Эти алгоритмы, также называемые алгоритмами с секретным ключом или алгоритмами с одним ключом, требуют, чтобы отправитель и получатель согласовали используемый ключ перед началом безопасной передачи сообщений . Безопасность симметричного алгоритма определяется ключом, раскрытие ключа означает, что кто угодно сможет шифровать и дешифрир о- вать сообщения. Пока передаваемые сообщения должны быть тайными, ключ должен храниться в секрете . Шифрование и дешифрирование с использованием симметричного алгоритма обозначается как : E K (M)=C D K (C)=M Симметричные алгоритмы делятся на две категории . Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмами или потоковыми шифрами. Другие работаю с группами битов открытого текста. Группы битов называются блоками, а алгоритмы - блочными алгоритмами или блочными шифрами. Для алгоритмов, используемых в компьютерных модемах, типичный размер блока составляет 64 бита - достаточно большое значение, чтобы помешать анализу, и достаточно небольшое и удобное для работы. (До появления компьютеров алгоритмы обычно обрабатывали открытый текст посимвольно . Такой вариант может рассматриваться как потоковый алгоритм, обрабатывающий поток символов .) Алгоритмы с открытым ключом Алгоритмы с открытым ключом (называемые асимметричными алгоритмами ) разработаны таким обра- зом, что ключ, используемый для шифрования, отличается от ключа дешифрирования . Более того, ключ де- шифрирования не может быть (по крайней мере в течение разумного интервала времени ) рассчитан по ключу шифрования. Алгоритмы называются "с открытым ключом", потому что ключ шифрования может быть откры- тым: кто угодно может использовать ключ шифрования для шифрования сообщения, но только конкретный ч е- ловек с соответствующим ключом дешифрирования может расшифровать сообщение. В этих системах ключ шифрования часто называется открытым ключом, а ключ дешифрирования - закрытым. Закрытый ключ ино- гда называется секретным ключом, но чтобы не было путаницы с симметричными алгоритмами, этот термин не используется в данной книге. Шифрование с открытым ключом K обозначается как: E K (M)=C Хотя открытый и закрытый ключи различны, дешифрирование с соответствующим закрытым ключом об о- значается как: D K (C)=M Иногда сообщения шифруются закрытым ключом, а дешифрируются открытым, что используется для ци ф- ровой подписи (см. раздел 2.6). Несмотря на возможную путаницу эти операции, соответственно, обозначаю т- ся как: E K (M)=C D K (C)=M Криптоанализ Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от зл о- умышленников (также называемых взломщиками , соперниками, врагами, перехватчиками ). Предполагается, что злоумышленники полностью контролируют линии связи между отправителем и получателем . Криптоанализ - это наука получения открытого текста, не имея ключа . Успешно проведенный криптоанализ может раскрыть открытый текст или ключ . Он также может обнаружить слабые места в криптосистемах, что в конце концов приведет к предыдущему результату . (Раскрытие ключа не криптологическими способами наз ы- вается компрометацией.) Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сфо р- мулированное в девятнадцатом веке Датчманом А. Керкхофсом ( Dutchman A. Kerckhoffs), iсостоит в том, что безопасность полностью определяется ключом [794]. Керкхофс предполагает, что у криптоаналитика есть по л- ное описание алгоритма и его реализации . (Конечно же, у ЦРУ не в обычае сообщать Моссад о своих крипт о- графических алгоритмах, но Моссад возможно все равно добудет их .) Хотя в реальном мире криптоаналитики не всегда обладают подробной информацией, такое предположение является хорошей рабочей гипотезой . Если противник не сможет взломать алгоритм, даже зная, как он работает, то тем более враг не сможет вскрыть а л- горитм без этого знания. Существует четыре основных типа криптоаналитического вскрытия . Для каждого из них, конечно, предпо- лагается, что криптоаналитик обладает всей полнотой знания об используемом алгоритме шифрования : 1. Вскрытие с использованием только шифротекста. У криптоаналитика есть шифротексты нескол ь- ких сообщений, зашифрованных одним и тем же алгоритмом шифрования . Задача криптоаналитика состоит в раскрытии открытого текста как можно большего числа сообщений или, что лучше, получ е- нии ключа (ключей), использованного для шифрования сообщений, для дешифрировании других с о- общений, зашифрованных теми же ключами. Дано: C 1 =E k (P 1 ), C 2 =E k (P 2 ), . . . C i =E k (P i ) Получить: Либо P 1 , P 2 , . . . P i ; k; либо алгоритм, как получать P i+1 из C i+1 =E k (P i+1 ) 2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифр о- текстам нескольких сообщений, но и к открытому тексту этих сообщений . Его задача состоит в полу- чении ключа (или ключей), использованного для шифрования сообщений, для дешифрировании др у- гих сообщений, зашифрованных тем же ключом (ключами) . Дано: P 1 , C 1 =E k (P 1 ), P 2 , C 2 =E k (P 2 ), . . . P i , C i =E k (P i ) Получить: Либо k; либо алгоритм, как получать P i+1 из C i+1 =E k (P i+1 ) 3. Вскрытие с использованием выбранного открытого текста. У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать о т- крытый текст для шифрования. Это предоставляет больше вариантов чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать шифруемые блоки открытого текста, что может дать больше информации о ключе . Его задача состоит в получении ключа (или ключей), и с- пользованного для шифрования сообщений, или алгоритма, позволяющего дешифрировать новые с о- общения, зашифрованные тем же ключом (или ключами) . Дано: P 1 , C 1 =E k (P 1 ), P 2 , C 2 =E k (P 2 ), . . . P i , C i =E k (P i ) где криптоаналитик может выбирать P 1 , P 2 , . . . P i Получить: Либо k; либо алгоритм, как получать P i+1 из C i+1 =E k (P i+1 ) 4. Адаптивное вскрытие с использованием открытого текста. Это частный случай вскрытия с ис- пользованием выбранного открытого текста . Криптоаналитик не только может выбирать шифруемый текст, но также может строить свой последующий выбор на базе полученных результатов шифрования. При вскрытии с использованием выбранного открытого текста криптоаналитик мог вы- брать для шифрования только один большой блок открытого текста, при адаптивном вскрытии с и с- пользованием выбранного открытого текста он может выбрать меньший блок открытого текста, затем выбрать следующий блок, используя результаты первого выбора и так далее . Существует по крайней мере еше три типа криптоаналитической вскрытия . 5. Вскрытие с использованием выбранного шифротекста. Криптоаналитик может выбрать различ- ные шифротексты для дешифрирования и имеет доступ к дешифрированным открытым текстам . На- пример, у криптоаналитика есть доступ к "черному ящику", который выполняет автоматическое д е- шифрирование. Его задача состоит в получении ключа. Дано: C 1 , P 1 =D k (C 1 ), C 2 , P 2 =D k (C 2 ), . . . C i , P i =D k (C i ) Получить: k Такой тип вскрытия обычно применим к алгоритмам с открытым ключом и обсуждается в разделе 19.3. Вскрытие с использование выбранного шифротекста иногда также эффективно против симме т- ричных алгоритмов. (Иногда вскрытие с использованием выбранного открытого текста и вскрытие с использованием выбранного шифротекста вместе называют вскрытием с использованием выбранного текста.) 6. Вскрытие с использованием выбранного ключа. Такой тип вскрытия означает не то, что крипто а- налитик может выбирать ключ, а что у него есть некоторая информация о связи между различными ключами. Этот странный, запутанный и не очень практичный тип вскрытия обсуждается в разделе 12.4. 7. Бандитский криптоанализ. Криптоаналитик угрожает, шантажирует или пытает кого-нибудь, пока не получит ключ. Взяточничество иногда называется вскрытием с покупкой ключа. Это очень мощные способы вскрытия, часто являющиеся наилучшим путем взломать алгоритм . Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Не является невозможным для криптоаналитика добыть открытый текст шифр о- ванного сообщения или подкупить кого-нибудь, кто зашифрует выбранное сообщение . Может и не потребо- ваться никого подкупать - передав письмо послу, вы, возможно, обнаружите, что письмо будет зашифровано и отправлено в его страну для изучения. Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода : функции, циклические структуры и так далее. Вскрытия с известным открытым текстом (и вскрытия с выбранным шиф- ротекстом) успешно использовались в борьбе с немцами и японцами в ходе Второй мировой войны . Историче- ские примеры вскрытий такого типа можно найти в книгах Дэвида Кана [794,795,796]. И не забывайте о предположении Керкхофса : если мощь вашей новой криптосистемы опирается на то, что взломщик не знает, как работает алгоритм, вы пропали . Если вы считаете, что хранение принципа работы а л- горитма в секрете лучше защитит вашу криптосистему, чем предложение академическому сообществу проан а- лизировать алгоритм, вы ошибаетесь. А если вы думаете, что кто-то не сможет дезассемблировать ваш исхо д- ный код и восстановить ваш алгоритм, вы наивны . (В 1994 году такое произошло с алгоритмом RC4, см. раз- дел 17.1.) Нашими лучшими алгоритмами являются те, которые были разработаны открыто, годами взламыв а- лись лучшими криптографами мира и все еще несокрушимы . (Агентство Национальной Безопасности хранит свои алгоритмы в секрете, но у них работают лучшие криптографы мира, а у вас - нет. Кроме того, они обсу ж- дают свои алгоритмы друг с другом, полагаясь на способность товарища обнаружить все слабости в своей р а- боте.) У криптоаналитиков не всегда есть доступ к алгоритмам (например, вскрытие в ходе Второй мировой войны Соединенными Штатами японского дипломатического кода PURPLE [794]), но часто они его получают. Если алгоритм используется в коммерческой программе безопасности, то это просто вопрос времени и денег, удас т- ся ли дезассемблировать программу и раскрыть алгоритм . Если же алгоритм используется в военной системе связи, то это просто вопрос времени и денег купить (или украсть) аппаратуру и реконструировать алгоритм . Те, кто стремится получить нераскрываемый шифр, считая этот шифр таковым только потому, что они сами не смогли его взломать, либо гении, либо дураки . К несчастью, последних в мире достаточно много . Остере- гайтесь людей, расхваливающих надежность своих алгоритмов, но отказывающихся их опубликовать. Дов е- рять таким алгоритмам нельзя. Хорошие криптографы опираются на мнение других, отделяя хорошие алгоритмы от плохих . Безопасность алгоритмов Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных, |