•   SAFETY   •

  • Таинственная наука о тайнописи

  • - Что ж! - сказал я, возвращая Леграну пергамент. - Меня это не подвинуло бы ни на шаг. За все алмазы Голконды я не возьмусь решать подобную головоломку.

    - И все же, - сказал Легран. - она не столь трудна, как может показаться. Эти знаки, конечно, - шифр; иными словами, они скрывают словесную запись.
    Алан Эдгар По. Золотой жук

    KRKRX FLOTT ENCHE FANAN OKMM XXTOR... (Попадание торпеды в корму. Управление потеряно...). Это часть шифрограммы с «карманного» линкора «Бисмарк», атакованного англичанами.

    Проблемы криптографии и криптоанализа наиболее остро вставали в период геополитической нестабильности, в частности в период мировых войн. Поединок криптологов и криптоаналитиков иногда называли «тайной войной». Однако несмотря на то что в этой области во время Второй мировой войны работали лучшие умы и уже ЭВМ, взломать шифр зачастую удавалось из-за элементарных нарушений дисциплины ведения переписки. Так, к примеру, японские сообщения удалось расшифровать благодаря присущей этой нации вежливости: все шифрограммы начинались словами «Имею честь сообщить Вашему превосходительству...». А «Бисмарк» удалось обнаружить потому, что одно и то же сообщение было послано дважды под разными кодами, один из которых был известен англичанам.

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

    Традиционно криптография использовалась военными и дипломатами и считалась исключительным правом государства. И сейчас большинство правительств контролируют если не сами исследования в этой области, то, по меньшей мере, производство шифрующей аппаратуры. Так, в США до недавнего времени экспортные ограничения на криптографическое оборудование и системы вооружений были одинаковы. Но с развитием международной электронной торговли, появлением банковских карточек, цифровых подписей, электронных денег и вообще любых подобных платежных систем правительства вынуждены были либерализовать политику в отношении распространения средств шифрования. Технологии,считавшиеся стратегическими, ныне доступны практически всем нуждающимся и являются основой информационной безопасности в Internet. Шифрование необходимо при проведении любого сеанса удаленной связи, так как позволяет удостовериться, что разговор ведется с нужным абонентом. В меню многих средств навигации Сети задается вопрос, нужен ли режим шифрования, и если ответить «нужен», начинается процедура выработки ключа. Посему пользователю полезно, а разработчику программных средств иногда просто необходимо иметь представление о криптографии. Итак, попытаемся провести не располагающего большим запасом времени читателя к пониманию основ современной криптологии между «Сциллой» математики и «Харибдой» профанации предмета, избегая того и другого в меру наших сил.

    Термин «криптология» восходит к Геродоту, его примерный смысл — «наука о тайнописи». Шифрами пользовались спартанцы и римляне. И все же криптология тех далеких эпох была скорее искусством, нежели наукой. Даже дипломатические шифры начала нашего столетия кажутся сегодня наивными. Например, в криптологических службах Англии лишь в ходе второй мировой войны (!) осознали, что профессиональные математики могут быть им полезны. Тогда, кстати, на службу ее Величества в качестве специалиста по криптологии был, среди прочих, призван Алан Тьюринг. Много столетий назад различали криптографию (т. е. шифрование) и криптоанализ. Криптограф ищет стойкие шифры, а криптоаналитик пытается их взломать. Однако, если необходимость в шифровании конфиденциальной информации всегда воспринималась как аксиома, то отношение к криптоанализу бывало неоднозначным. «Джентльмены не читают чужих писем», — заявил госсекретарь США Генри Стимсон (Henry Stimson) в 1929 г., узнав, что «черный кабинет» государственного департамента занимается раскрытием шифрованных дипломатических телеграмм, и упразднил отдел. Только в 1940 г., будучи на посту военного министра, Стимсон оценил криптоанализ (тогда были раскрыты военные шифры императорской Японии). Сегодня это столь же уважаемое занятие, как и криптография. «Дружественный крип-тоаналитик» может обнаружить уязвимые места шифров, что позволит исправить их или вообще отказаться от использования. Например, в 1984 г. Ади Шамир (Adi Shamir) предложил весьма остроумное решение задачи «об укладке ранца», чем предотвратил вероятное практическое применение на первый взгляд очень удобного шифра Меркля—Хеллмана, а вместе с тем и возможный успех лица, предпочитающего более осязаемое вознаграждение, нежели научное признание.

    Исходное сообщение, подлежащее шифрованию, в крипто-логии называют открытым текстом, а результат - шифртек-стом, или криптограммой. Управление процессом шифрования осуществляется секретным ключом. Для прочтения сообщения адресат также в нем нуждается, поэтому ключ ему пересылали заранее (например, заслуживающим доверия курьером). При разработке шифров руководствуются правилом, сформулированным в конце XIX ст. голландским математиком Керкхоф-фом: стойкость шифра определяется только стойкостью ключа. Иными словами, предполагается, что механизм шифрования известен недружественному крипто-аналитику, равно как и сама криптограмма. В действительности для некоторых применений (главным образом в военных, дипломатических и разведывательных ведомствах) для разработчика криптосистемы нет никаких причин для того, чтобы открыто описывать характер ее алгоритмов. Сохраняя эту информацию в тайне, можно обеспечить даже некоторую дополнительную безопасность. Однако это не является решающим обстоятельством, позволяющим по

    лагаться на такую систему, поскольку неизвестно, когда она может быть скомпрометирована. Более того, на практике существуют ситуации, когда «противник» может догадываться о характере передаваемых сведений. Поэтому криптограф допускает, что криптоаналитик способен «подставить» свой открытый текст и получить правильную криптограмму, что, естественно, повышает его шансы раскрыть секретный ключ и расшифровать все последующие сообщения. В первом и втором случаях принято говорить о стойкости криптосистемы на основе только шифрованного текста и о стойкости на основе выбранного открытого текста соответственно.

    Эру научной криптологии в 1949 г. открыла публикация работы Клода Шеннона «Теория связи в секретных системах», построенной на положениях созданной им же теории информации. На вопрос, существуют ли шифры, обеспечивающие «совершенную секретность», Шеннон ответил утвердительно. Он представил доказательство возможности построения такого шифра при однократном использовании ключа, если длина последнего не меньше длины шифруемого текста, ключ формируется случайным образом (например, датчиком случайных чисел) и используется однократно. В этом случае раскрыть информацию без знания ключа невозможно. Естественно, такой шифр может найти весьма ограниченное применение (например, когда респондент лишь однажды выйдет на связь и объем сообщения невелик). Поэтому стойкость реально применяемых шифров опирается не на теоретическую невозможность их раскрытия, а на практическую сложность такового. Теоретическую стойкость оценивают функцией ненадежности ключа и расстоянием единственности (разъяснение этих понятий требует привлечения элементов теории информации, что выходит за рамки обзора. Впрочем, для практического шифрования с их помощью ни разу не удалось получить содержательную оценку).

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

    ШИФРЫ С СЕКРЕТНЫМИ КЛЮЧАМИ

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

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

    ПРИМЕР:

    (открытый текст) с о о б е щ е н и е

    (ключ) 4 7 9 2 3 5 1 6 8

    (криптограмма) н б щ с е и о е о

    Подстановки еще называют методом замены. Символы исходного текста, записанные в одном алфавите, заменяются символами другого алфавита в соответствии с принятым ключом преобразования. Очень примитивным, по нынешним меркам, примером является шифр, которым более 2000 лет назад Цезарь писал Цицерону и другим друзьям в Риме. Буквы открытого текста он заменял третьей по счету (циклически) буквой латинского алфавита. Так, из латинского Gaius Julius Caesar получался шифртекст JDLYV MYO LYV FDHVDU. Более криптостой-кой реализацией метода подстановок была схема шифрования, основанная на таблице Вижинера. Вместо регулярных замен, используемых в шифре Цезаря, применялись рандомизированные подстановки с достаточно сложным «эквивалентным» ключом. Современный вариант основан на матричной алгебре: псевдослучайная матрица ключа умножается на вектор сообщения (блок открытого текста). Криптограмма — результат умножения. (Ясно, что вместо символов алфавита сообщения используются их цифровые эквиваленты.) Дешифрирование выполняется по тем же правилам, но операндами будут сама криптограмма и обратная матрица ключа. Одним из вариантов подстановок является гаммирование, где шифрование производится сложением символов исходного текста и ключа по модулю, равному числу букв в алфавите. Чаще используются двоичный алфавит и сложение по модулю 2. (Напомним, что принято называть числа а и Ь, дающие одинаковые остатки при делении на m, сравнимыми по модулю m, и обозначать это а =b(mod m).)

    Заметим, при простых подстановках распределение частот символов в шифртексте сохраняется, что дает богатый материал криптоаналитику, как это произошло в упомянутом в эпиграфе произведении Эдгара По. Анализируя статистику букв, встречающихся в шифртексте, можно сделать, например, вывод о том, что наиболее часто встречающийся символ соответствует (в русском алфавите) букве «Е», а встречающийся наименее часто — букве «Ф» и так далее. Однако, если подстановка делается в очень большом алфавите, а вероятность повторения каждого символа открытого текста в течение времени использования одного ключа мала, то статистические свойства шифртекста дают мало информации для криптоанализа, и такой шифр становится очень хорошим. Криптограф достигает этого, применяя подстановку к отдельным символам, содержащим несколько символов из алфавита исходного открытого текста. Например, при шифровании имени Caesar с использованием подстановки, при которой заменяются пары латинских букв (СА заменяется на WK, ES на LB, a AR на UT), получится WKLBUT.

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

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

    Специальная комиссия сената выяснила, что длина ключа DES была ограничена 56 битами по настоянию некоторых должностных лиц из Агентства национальной безопасности (NSA), что ранее отрицали и IBM, и NBS. NSA также засекретило принципы, использованные фирмой IBM при выборе конкретных подстановок, применяемых в алгоритме DES. В неправительственных ассоциациях криптологов неоднократно высказывалось мнение о возможности встраивания потайных входов («люков») в подобные алгоритмы. 17 июня 1997 г. шифр DES был взломан за 140 дней работы локальной вычислительной сети. Затраченный ресурс составил приблизительно 450 MIPS-лет (при этом было протестировано около 25% всех возможных ключей). Это, безусловно, выдающееся достижение, которое постепенно приведет к утрате DES роли стандарта шифрования. Вероятным претендентом на замену DES является технология матричного шифрования VME фирмы Meganet. Компания IBM после тщательного ее изучения обратилась к ряду государственных учреждений (quot;Л Т ТА с настоятельными рекомендациями по скорейшему принятию VME в качестве национального стандарта. Meganet предложила 1 млн. долл. тому. кто сможет «взломать» эту технологию. Уже предпринято более 55 тыс. безуспешных попыток.

    Одним из лучших примеров такого криптоалгоритма является DES (Data Encryption Standard). Он был представлен фирмой IBM в 1974 г. в ответ на обращение Национального бюро стандартов США (NBS) к специалистам по вопросу об алгоритмах для стандарта шифрования данных в государственных и частных учреждениях. Одним из требований NBS было — возможность публикации алгоритма без ущерба для его стойкости (Керк-хофф был бы в восторге от этого требования). В DES открытый блок текста X, криптограмма Y и ключ Z — двоичные последовательности длиной соответственно М= 64, N = 64 и К = 56. В сущности, DES является подстановкой в гигантском алфавите, содержащем 264 «символов» (79 квадриллионов комбинаций!). При использовании DES в режиме, называемом электронной кодовой книгой, следующие друг за другом 64-битовые «блоки» открытого текста шифруются с использованием одного ключа, но независимо. Криптоал-горитм является суперпозицией шифров, состоящей из 16-ти последовательных «циклов», в которых довольно простые перестановки сочетаются с подстановками в 4-битовых группах. В каждом проходе используются лишь 48 битов ключа, однако они выбираются внешне случайным образом из полного 56-битового ключа. Заметим, пока все попытки описать влияние отдельных битов открытого текста или ключа на шифртекст были безуспешными (хорошее рассеивание), как и попытки анализа статистических зависимостей между открытым и шифрованным текстом (хорошее перемешивание). В 1987 г. был принят международный стандарт на основе DES (ISO 8372).

    Почти с самого момента своего появления DES стал объектом полемики. Уитфрид Диффи (Witfrid Diffie) и Мартин Хеллман (Martin Hellman), специалисты по крипто-логии из Стенфордского университета, возглавили группу скептиков, сомневавшихся в нем по причине малого размера секретного ключа. При 256= 1017 ключей силовая атака (полный перебор ключей до тех пор, пока из криптограммы не получится осмысленный текст) уже тогда лишь с небольшим запасом превышала возможности ЭВМ. Диффи и Хеллман опубликовали проект специализированного многопроцессорного компьютера стоимостью около 20 млн. долл., который мог бы раскрыть DES путем полного перебора примерно за 12 часов (не забудем, что речь шла о технике 20-летней давности). В известном смысле DES оправдал надежды своих сторонников. Несмотря на интенсивные и тщательные исследования алгоритма, еще никто не сообщил об уязвимых местах, на основе которых можно было бы предложить метод криптоанализа, существенно лучший, чем полный перебор. Официальное мнение специалистов остается таким: DES — очень хороший шифр, хотя и с малым ключом.



    В базе данных с 1999-01-28
    продолжение

    next
    pre
    start


  • Разное




    Hosted by uCoz