Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
вы, скорее всего, в безопасности. Если время взлома алгоритма больше, чем время, в течение которого заши ф- рованные данные должны сохраняться в секрете, то вы также, скорее всего, в безопасности . Если объем дан- ных, зашифрованных одним ключом, меньше, чем объем данных, необходимый для взлома алгоритма, и тогда вы, скорее всего, в безопасности. Я говорю "скорее всего", потому что существует вероятность новых прорывов в криптоанализе . С другой стороны, значимость большинства данных падает со временем . Важно, чтобы значимость данных всегда ост а- валась меньше, чем стоимость взлома системы безопасности, защищающей данные . Ларс Кнудсен (Lars Knudsen) разбил вскрытия алгоритмов по следующим категориям, приведенным в п о- рядке убывания значимости [858]: 1. Полное вскрытие. Криптоаналитик получил ключ, K, такой, что D K (C) = P. 2. Глобальная дедукция. Криптоаналитик получил альтернативный алгоритм, A, эквивалентный D K (C) без знания K. 3. Местная (или локальная) дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста. 4. Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или откр ы- том тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее. Алгоритм является безусловно безопасным, если, независимо от объема шифротекстов у криптоаналитика, информации для получения открытого текста недостаточно . По сути, только шифрование одноразовыми блок- нотами (см. раздел 1.5) невозможно вскрыть при бесконечных ресурсах . Все остальные криптосистемы под- вержены вскрытию с использованием только шифротекста простым перебором возможных ключей и прове р- кой осмысленности полученного открытого текста . Это называется вскрытием грубой силой (см. раздел 7.1). Криптография больше интересуется криптосистемами, которые тяжело взломать вычислительным способом . Алгоритм считается вычислительно безопасным (или, как иногда называют, сильным), если он не может быть взломан с использованием доступных ресурсов сейчас или в будущем . Термин "доступные ресурсы" явля- ется достаточно расплывчатым. Сложность вскрытия можно измерить (см раздел 11.1) различными способ ами: 1. Сложность данных. Объем данных, используемых на входе операции вскрытия . 2. Сложность обработки. Время, нужное для проведения вскрытия. Часто называется коэффициентом работы. 3. Требования к памяти. Объем памяти, необходимый для вскрытия . В качестве эмпирического метода сложность вскрытия определяется по максимальному из этих трех коэфф и- циентов. Ряд операций вскрытия предполагают взаимосвязь коэффициентов : более быстрое вскрытие возможно за счет увеличения требований к памяти. Сложность выражается порядком величины . Если сложность обработки для данного алгоритма составляет 2 128 , то 2 128 операций требуется для вскрытия алгоритма . (Эти операции могут быть сложными и длительными .) Так, если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в с е- кунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет у вас свыше 10 19 лет, что в миллиард раз превышает время существования вселенной . В то время, как сложность вскрытия остается постоянной (пока какой-нибудь криптоаналитик не придумает лучшего способа вскрытия), мощь компьютеров растет . За последние полвека вычислительные мощности ф е- номенально выросли, и нет никаких причин подозревать, что эта тенденция не будет продолжена . Многие крип- тографические взломы пригодны для параллельных компьютеров: задача разбивается на миллиарды маленьких кусочков, решение которых не требует межпроцессорного взаимодействия . Объявление алгоритма безопасным просто потому, что его нелегко взломать, используя современную технику, в лучшем случае ненадежно. Хор о- шие криптосистемы проектируются устойчивыми к взлому с учетом развития вычислительных средств на много лет вперед. Исторические термины Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фразу "ПОВОРОТ НАЛЕВО НА 90 ГРАДУСОВ", слово "ЛЕДЕНЕЦ" - фразу "ПОВОРОТ НАПРАВО НА 90 ГРАДУСОВ", а слова "ПОДСТАВЬ УХО" могут кодировать слово "ГАУБИЦА". Коды такого типа не рассматриваются в данной кн и- ге, см. [794,795]. Коды полезны только при определенных обстоятельствах . Если у вас нет кода для "МУРАВЬЕДЫ", вы не сможете передать это понятие. А используя шифр можно сказать все. 1.2 Стеганография Стеганография служит для передачи секретов в других сообщениях, так что спрятано само существование секрета. Как правило отправитель пишет какое-нибудь неприметное сообщение, а затем прячет секретное соо б- щение на том же листе бумаги. Исторические приемы включают невидимые чернила, невидимые простому гл а- зу пометки у букв, плохо заметные отличия в написании букв, пометки карандашом машинописных символов, решетки, покрывающие большую часть сообщения кроме нескольких символов и тому подобное. Ближе к сегодняшнему дню люди начали прятать секреты в графических изображениях, заменяя младший значащий бит изображения битом сообщения. Графическое изображение при этом менялось совсем незаметно - большинство графических стандартов определяют больше цветовых градаций, чем способен различить челов е- ческий глаз - и сообщение извлекалось на противоположном конце . Так в черно-белой картинке 1024х1024 пи к- села можно спрятать можно спрятать сообщение в 64 Кбайт . Многие общедоступные программы могут прод е- лывать подобный фокус. Имитационные функции Питера Уэйнера (Peter Wayner) маскируют сообщения. Эти функции изменяют сообщение так, что его статистический профиль становится похожим на что-нибудь еще: раздел The New York Times, a пьесу Шекспира или телеконференцию в Internet [1584,1585]. Этот тип стеганографии не одурачит че- ловека, но может обмануть большой компьютер, ищущий нужную информацию в Internet. 1.3 Подстановочные и перестановочные шифры До появления компьютеров криптография состояла из алгоритмов на символьной основе . Различные крипто- графические алгоритмы либо заменяли одни символы другими, либо переставляли символы. Лучшие алгоритмы делали и то, и другое, и по много раз. Сегодня все значительно сложнее, но философия остается прежней. Первое изменение заключается в том, что алгоритмы стали работать с битами, а не символами. Это важно хотя бы с точки зрения размера алфавита - с 26 элементов до двух. Большинство хороших криптографических алгоритмов до сих пор комбинирует подст а- новки и перестановки. Подстановочные шифры Подстановочным шифром называется шифр, который каждый символ открытого текста в шифротексте з а- меняет другим символом. Получатель инвертирует подстановку шифротекста, восстанавливая открытый текст . В классической криптографии существует четыре типа подстановочных шифров : — Простой подстановочный шифр, или моноалфавитный шифр, - это шифр, который каждый символ открытого текста заменяет соответствующим символом шифротекста . Простыми подстановочными шиф- рами являются криптограммы в газетах . — Однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключ е- нием того, что один символ открытого текста отображается на несколько символов шифротекста . Напри- мер, "A" может соответствовать 5, 13, 25 или 56, "B" - 7, 19, 31 или 42 и так далее. — Полиграмный подстановочный шифр - это шифр, который блоки символов шифрует по группам . На- пример, "ABA" может соответствовать "RTQ", "ABB" может соответствовать "SLL" и так далее. — Полиалфавитный подстановочный шифр состоит из нескольких простых подстановочных шифров . Например, могут быть использованы пять различных простых подстановочных фильтров ; каждый сим- вол открытого текста заменяется с использованием одного конкретного шифра . Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящег о- ся тремя символами правее по модулю 26 ("A" заменяется на "D," "B" - на "E", ... "W" - на " Z ", "X" - на "A", "Y" - на "B", "Z" - на "C"), представляет собой простой подстановочный фильтр . Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открыт о- го текста ROTI3 - это простая шифровальная программа, обычно поставляемая с системами UNIX. Она также являет- ся простым подстановочным шифром. В этом шифре "A" заменяется на "N," "B" - на "O" и так далее. Каждая буква смещается на 13 мест. Шифрование файла программой ROTI3 дважды восстанавливает первоначальный файл. P = ROT13 (ROT13 (P)) ROTI3 не используется для безопасности, она часто применяется в почте, закрывая потенциально неприя т- ный текст, решение головоломки и тому подобное . Простые подстановочные шифры легко раскрываются, так как шифр не прячет частоты использования ра з- личных символов в открытом тексте. Чтобы восстановить открытый текст, хорошему криптоаналитику требуе т- ся только знать 26 символов английского алфавита [1434]. Алгоритм вскрытия таких шифров можно найти в [578, 587, 1600, 78, 1475, 1236, 880]. Хороший компьютерный алгоритм приведен в [703]. Однозвучные подстановочные шифры использовались уже в 1401 году в герцогстве Мантуа [794]. Они более сложны для вскрытия, чем простые подстановочные шифры, хотя и они не скрывают всех статистических свойств языка открытого текста. При помощи вскрытия с известным открытым текстом эти шифры раскрыв а- ются тривиально. Вскрытие с использованием только шифротекста более трудоемко, но и оно занимает на ко м- пьютере лишь несколько секунд. Подробности приведены в [1261]. Полиграмные подстановочные шифры - это шифры, которые кодируют сразу группы символов . Шифр Play- fair ("Честная игра"), изобретенный в 1854 году, использовался англичанами в Первой мировой войне [794]. Он шифрует пары символов, и его криптоанализ обсуждается в [587,1475,880]. Другим примером полиграмного подстановочного шифра является шифр Хилла ( Hill) [732]. Иногда можно видеть как вместо шифра используе т- ся кодирование по Хаффману (Huffman), это небезопасный полиграмный подстановочный шифр . Полиалфавитные подстановочные шифры были изобретены Лином Баттистой ( Lean Battista) в 1568 году [794]. Они использовались армией Соединенных Штатов в ходе Гражданской войны в Америке . Несмотря на то, что они легко могут быть взломаны [819, 577, 587, 794] (особенно с помощью компьютеров), многие ком- мерческие продукты компьютерной безопасности используют такие шифры [1387,1390, 1502]. (Подробности того, как вскрыть эту схему шифрования, используемую программой WordPerfect, можно найти в [135,139].) Шифр Вигенера (Vigenere), впервые опубликованный в 1586 году, и шифр Бофора (Beaufort) также являются примерами полиалфавитных подстановочных шифров. У полиалфавитных подстановочных шифров множественные однобуквенные ключи, каждый из которых и с- пользуется для шифрования одного символа открытого текста . Первым ключом шифруется первый символ о т- крытого текста, вторым ключом - второй символ, и так далее . После использования всех ключей они повтор я- ются циклически. Если применяется 20 однобуквенных ключей, то каждая двадцатая буква шифруется тем же ключом. Этот параметр называется периодом шифра. В классической криптографии шифры с длинным перио- дом было труднее раскрыть, чем шифры с коротким периодом. Использование компьютеров позволяет легко раскрыть подстановочные шифры с очень длинным периодом . Шифр с бегущим ключом (иногда называемый книжным шифром), использующий один текст для шифр о- вания другого текста, представляет собой другой пример подобного шифра . И хотя период этого шифра равен длине текста, он также может быть легко взломан [576,794]. Перестановочные шифры В перестановочном шифре меняется не открытый текст, а порядок символов. В простом столбцовом пе- рестановочном шифре открытый текст пишется горизонтально на разграфленном листе бумаги фиксирова н- ной ширины, а шифротекст считывается по вертикали (см. -3-й). Дешифрирование представляет собой запись шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывание откр ы- того текста горизонтально. Криптоанализ этих шифров обсуждается в [587,1475]. Так как символы шифротекста те же, что и в откр ы- том тексте, частотный анализ шифротекста покажет, что каждая буква встречается приблизительно с той же частотой, что и обычно. Это даст криптоаналитику возможность применить различные методы, определяя пр а- вильный порядок символов для получения открытого текста . Применение к шифротексту второго перестаново ч- ного фильтра значительно повысит безопасность . Существуют и еще более сложные перестановочные фильтры, но компьютеры могут раскрыть почти все из них . Немецкий шифр ADFCVX, использованный в ходе Первой мировой войны , представлял собой перестано- вочный фильтр в сочетании с простой подстановкой . Этот для своего времени очень сложный алгоритм был раскрыт Жоржем Пенвэном (Georges Painvin), французским криптоаналитиком [794]. Хотя многие современные алгоритмы используют перестановку, с этим связана проблема использования большого объема памяти, а также иногда требуется работа с сообщениями определенного размера . Подстановка более обычна. Роторные машины В 1920-х годах для автоматизации процесса шифрования были изобретены различные механические устро й- ства. Большинство использовало понятие ротора, механического колеса, используемого для выполнения по д- становки. Роторная машина, включающая клавиатуру и набор роторов , реализует вариант шифра Вигенера. Каждый ротор представляет собой произвольное размещение алфавита, имеет 26 позиций и выполняет простую подст а- новку. Например, ротор может быть использован для замены "A" на " F", "B" на "U", "C'' на "I" и так далее. Вы- ходные штыри одного ротора соединены с входными штырями следующего ротора. Открытый текст: COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST IT'S EXPENSIVE. COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE Шифротекст: CAELP OPSEE MHLAN PIOSS UCWTI TCBIV EMUTE RATSG YAERB TX Рис. 1-4. Столбцовый перестановочный фильтр. Например, в четырехроторной машине первый ротор может заменять "A" на " F", второй - "F" на "Y", третий - "Y" на "E" и четвертый - "E" на "C", "C" и будет конечным шифротекстом . Затем некоторые роторы смеща- ются, и в следующий раз подстановки будут другими . Именно комбинация нескольких роторов и механизмов, движущих роторами, и обеспечивает безопасность машины. Так как роторы вращаются с различной скоростью, период для n-роторной машины равен 26 n . Неко- торые роторные машины также могут иметь различные положения для каждого ротора, что делает криптоан а- лиз еще более бессмысленным. Самым известным роторным устройство является Энигма ( Enigma). Энигма использовалась немцами во Второй мировой войне. Сама идея пришла в голову Артуру Шербиусу ( Arthur Scherbius) и Арвиду Герхарду Дамму (Arvid Gerhard Damm) в Европе. В Соединенных Штатах она была запатентована Артуром Шербиусом [1383]. Немцы значительно усовершенствовали базовый проект для использования во время войны . У немецкой Энигмы было три ротора, котроые можно было выбрать из пяти возможных, коммутатор, кот о- рый слегка тасовал открытый текст, и отражающий ротор, который заставлял каждый ротор обрабатывать о т- крытый текст каждого письма дважды. Несмотря на сложность Энигмы, она была взломана в течение Второй мировой войны. Сначала группа польских криптографов взломала немецкую Энигму и объяснила раскрытый алгоритм англичанам. В ходе войны немцы модифицировали Энигму , а англичане продолжали криптоанализ новых версий. Объяснение работы роторных шифров и способов их раскрытия можно найти в [794, 86, 448, 498, 446, 880, 1315, 1587, 690]. В двух следующих отчетах увлекательно рассказывается о взломе Энигмы [735, 796]. Для дальнейшего чтения Данная книга не является книгой по классической криптографии, поэтому далее я не буду подробно остана в- ливаться на этих предметах. Прекрасными книгами по докомпьютерной криптологии являются [587, 1475]. [448] содержит современный криптоанализ шифровальных машин . Дороти Деннинг (Dorothy Denning) рассмат- ривает многие из этих шифров в [456], а [880] содержит беспристрастный сложный математический анализ тех же самых шифров. Другим описанием старой криптографии, описывающим аналоговую криптографию, являе т- ся [99]. Прекрасный обзор выполнен в статье [579]. Великолепны также книги по исторической криптографии Дэвида Кана [794, 795, 796]. 1.4 Простое XOR XOR представляет собой операцию "исключающее или" : '^' в языке C или Q в математической нотации. Это обычная операция над битами: 0 ? 0 = 0 0 ? 1 = 1 1 ? 0 = 1 1 ? 1 = 0 Также заметим, что: a ? a = 0 a ? b ? b = a Казалось бы, запутанный алгоритм простого XOR по сути является ничем иным, как полиалфавитным ши ф- ром Вигенера. Здесь он упоминается только из-за распространенности в коммерческих программных продуктах, по крайней мере в мире MS-DOS и Macintosh [1502, 1387]. К сожалению, если о программе компьютерной безопасности заявляется, что это "патентованный" алгоритм шифрования, значительно более быстрый, чем DES, то скорее всего используется какой-то вариант следующего . /* Использование: crypto key input_file output_file */ void main (int argc, char *argv[]) { FILE *fl, *fo; char *cp; int c; if ((cp = argv[l]) && *cp!= '\0') { if ((fi = fopen(argvl[2], "rb")) != NULL) { if ((fo = fopen(argv[3], "wb")) != NULL) { while ((c = getc(fi)) != EOF) { if (!*cp) cp = argv[1]; c^= *(cp++); putc(c,fo); } fclose(fo); } fclose(fi); } } } Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключ е- вым текстом для получения шифротекста . Так как повторное применение операции XOR восстанавливает ори- гинал для шифрования и дешифрирования используется одна и та же программа : P ? K = C C ? K = P Настоящей безопасности здесь никогда не было. Этот тип шифрования легко вскрывается, даже без компь ю- тера [587, 1475]. Его взлом на компьютере занимает несколько секунд . Предположим, что открытый текст использует английский язык. Более того, пусть длина ключа любое н е- большое число байт. Ниже описано, как взломать этот шифр: 1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений [577]. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещ е- ниями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обыч- ный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут др у- гими). Это называется показателем совпадений. Минимальное смещение от одного значения, кра т- ного длине ключа, к другому и есть длина ключа . 2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шиф- ротекстов. Результатом операции будет удаления ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа . Так как в английском языке на один байт приходится 1.3 бита действительной информации (см раздел 11.1), существующая значительная избы- точность позволяет определить способ шифрования . Несмотря на это, количество поставщиков программного обеспечения, навязывающих этот игрушечный а л- горитм в качестве "почти такого же безопасного как DES", впечатляет [1387]. Именно этот алгоритм (с 160-битным повторяющимся "ключом") NSA в конце концов разрешило использовать в цифровых телефонных сотовых сетях для закрытия голоса. XOR может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды. 1.5 Одноразовые блокноты Поверите или нет, но идеальный способ шифрования существует. Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном ( Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T [794]. (Фактически одноразовый блокнот представляет собой особый случай порого- вой схемы, см. раздел 3.7.) В классическом понимании одноразовый блокнот является большой неповторяю- щейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота. Первоначально это была одноразовая лента для телетайпов . Отправи- тель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста . Шифрование представляет собой сложение по модулю 26 символа открытого текста и символа ключа из одн о- разового блокнота. Каждый символ ключа используется только единожды и для единственного сообщения . Отправитель шифру- ет сообщения и уничтожает использованные страницы блокнота или использованную часть ленты . Получатель, в свою очередь, используя точно такой же блокнот, дешифрирует каждый символ шифротекста . Расшифровав сообщение, получатель уничтожает соответствующие страницы блокнота или часть ленты . Новое сообщение - новые символы ключа. Например, если сообщением является: ONETIMEPAD а ключевая последовательность в блокноте: TBFRGFARFM то шифротекст будет выглядеть как: IPKLPSFHGQ так как Q + T mod 26 = I N + B mod 26 = P E + F mod 26 = K и т.д. В предположении, что злоумышленник не сможет получить доступ к одноразовому блокноту, использова н- ному для шифрования сообщения, эта схема совершенно безопасна. Данное шифрованное сообщение на вид соответствует любому открытому сообщению того же размера. Так как все ключевые последовательности совершенно одинаковы (помните, символы ключа генерируются случайным образом), у противника отсутствует информация, позволяющая подвергнуть шифротекст криптоан а- лизу. Кусочек шифротекста может быть похож на : POYYAEAAZX что дешифрируется как: SALMONEGGS или на: BXEGBMTMXM что дешифрируется как: GREENFLUID Повторю еще раз: так как все открытые тексты равновероятны , у криптоаналитика нет возможности опред е- лить, какой из открытых текстов является правильным . Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный шифротекст, и никакие вычислительные мощн о- сти не смогут это изменить. Необходимо напомнить, что символы ключа должны генерироваться случайным образом . Любые попытки вскрыть такую схему сталкиваются со способом, которым создается последовательность символов ключа . Ис- пользование генераторов псевдослучайных чисел не считается, у них всегда неслучайные свойства . Если вы используете действительно случайный источник - это намного труднее, чем кажется на первый взгляд, см. ра з- дел 17.14 - это совершенно безопасно. Другой важный момент: ключевую последовательность никогда нельзя использовать второй раз. Даже если вы используете блокнот размером в несколько гигабайт, то если криптоаналитик получит несколько текстов с перекрывающимися ключами, он сможет восстановить открытый текст . Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. Если шифротексты смещены пр а- вильно, соотношение совпадений резко возрастет - точное значение зависит от языка открытого текста . С этой точки зрения криптоанализ не представляет труда . Это похоже на показатель совпадений, но сравниваются два различных "периода" [904]. Не используйте ключевую последовательность повторно . Идея одноразового блокнота легко расширяется на двоичные данные. Вместо одноразового блокнота, с о- стоящего из букв, используется одноразовый блокнот из битов . Вместо сложения открытого текста с ключом одноразового блокнота используйте XOR. Для дешифрирования примените XOR к шифротексту с тем же одно- разовым блокнотом. Все остальное не меняется, и безопасность остается такой же совершенной . Все это хорошо, но существует несколько проблем . Так как ключевые биты должны быть случайными и не могут использоваться снова, длина ключевой последовательности должна равняться длине сообщения . Однора- зовый блокнот удобен для нескольких небольших сообщений, но его нельзя использовать для работы по каналу связи с пропускной способностью 1.544 Мбит/с. Вы можете хранить 650 Мбайт случайных данных на CD-ROM, но и тут есть проблемы. Во первых, вам нужно только две копии случайных битов, но CD-ROM экономичны только при больших тиражах. И во вторых, вам нужно уничтожать использованные биты . Для CD-ROM нет другой возможности удалить информацию кроме как физически разрушить весь диск . Гораздо больше подходит цифровая лента. Даже если проблемы распределения и хранения ключей решены, вам придется точно синхронизировать р а- боту отправителя и получателя. Если получатель пропустит бит (или несколько бит пропадут при передаче ), сообщение потеряет всякий смысл. С другой стороны, если несколько бит изменятся при передаче (и ни один бит не будет удален или добавлен - что гораздо больше похоже на влияние случайного шума ), то лишь эти биты будут расшифрованы неправильно. Но одноразовый блокнот не обеспечивает проверку подлинности . Одноразовые блокноты используются и сегодня, главным образом для сверхсекретных каналов связи с ни з- кой пропускной способностью. По слухам "горячая линия" между Соединенными Штатами и бывшим Сове т- ским Союзом (а действует ли она сейчас?) шифруется с помощью одноразового блокнота . Многие сообщения советских шпионов зашифрованы с использованием одноразовых блокнотов . Эти сообщения нераскрыты сего- дня и навсегда останутся нераскрытыми. На этот факт не повлияет время работы суперкомпьютеров над этой проблемой. Даже когда враги из созвездия Андромеды приземлят свои тяжелые корабли с компьютерами н е- мыслимой мощности, и они не смогут прочесть сообщения советских шпионов, зашифрованные с помощью о д- норазовых (если, конечно, они не смогут вернуться в прошлое и добыть нужные одноразовые блокноты ). 1.6 Компьютерные алгоритмы Существует множество компьютерных алгоритмов. Следующие три используются чаще всего : — DES (Data Encryption Standard, стандарт шифрования данных) - самый популярный компьютерный алго- ритм шифрования, является американским и международным стандартом . Это симметричный алгоритм, один и тот же ключ используется для шифрования и дешифрирования . — RSA (назван в честь создателей - Ривеста (Rivest), Шамира (Sharnir) и Эдлмана (Adleman)) - самый по- пулярный алгоритм с открытым ключом. Используется и для шифрования, и для цифровой подписи . — DSA (Digital Signature Algorithm, алгоритм цифровой подписи, используется как часть стандарта цифр о- вой подписи, Digital Signature Standard) - другой алгоритм с открытым ключом. Используется только для цифровой подписи, не может быть использован для шифрования . Именно эти и подобные алгоритмы описываются в этой книге . 1.7 Большие числа На протяжении всей книги я использую различные большие числа для описания различных вещей в крипт о- графии. Так как легко заблудиться в этих числах и их значениях, физические аналоги некоторых чисел прив е- дены в 0-й. Эти числа оцениваются по порядку величины и были отобраны из различных источников. Многие астроф и- зические значения объясняются в работе Фримана Дайсона ( Freeman Dyson), "Время без конца: физика и био- логия в открытой Вселенной" ("Time Without End: Physics and Biology in an Open Universe") в Reviews of Modem Physics, v. 52, n. 3, July 1979, pp. 447-460. Смертность в результате автокатастроф рассчитана с помощью стат и- стики Министерства транспорта (163 смерти миллион человек в 1993 году и для средней продолжительности жизни 69.7 года. Табл. 1-1. Большие числа Физический аналог Число Вероятность быть убитым молнией (в течение дня) 1 из 9 миллиардов (2 33 ) Вероятность выиграть главный приз в государственной лотерее США 1 из 4000000 (2 22 ) Вероятность выиграть главный приз в государственной лотерее США и быть убитым молнией в течение того же дня 1 из2 61 Вероятность утонуть (в США в течение года) 1 из 59000 (2 16 ) Вероятность погибнуть в автокатастрофе (в США в году) 1 из 6100 (2 13 ) Вероятность погибнуть в автокатастрофе (в США в течение времени жизни) 1 из 88 (2 7 ) Время до следующего оледенения 14000 (2 14 ) лет Время до превращения Солнца в сверхновую звезду 10 9 (2 30 ) лет Возраст планеты 10 9 (2 30 ) лет Возраст Вселенной 10 10 (2 34 ) лет Число атомов планеты 10 51 (2 170 ) Число атомов Солнца 10 57 (2 190 ) Число атомов галактики 10 67 (2 223 ) Число атомов Вселенной 10 77 (2 265 ) Объем Вселенной 10 84 (2 280 ) см 3 Если Вселенная конечна: Полное время жизни вселенной 10 11 (2 37 ) лет 10 18 (2 61 ) секунд Если Вселенная бесконечна: Время до остывания легких звезд 10 14 (2 47 ) лет Время до отрыва планет от звезд 10 15 (2 50 ) лет Время до отрыва звезд от галактик 10 19 (2 64 ) лет Время до разрушения орбит гравитационной радиацией 10 20 (2 67 ) лет Время до разрушения черных дыр процессами Хокинга 10 64 (2 213 ) лет Время до превращения материи в жидкость при нулевой температуре 10 65 (2 216 ) лет Время до превращения материи в твердое тело 10 10 26 лет Время до превращения материи в черную дыру 10 10 76 лет Часть 1 КРИПТОГРАФИЧЕСКИЕ ПРОТОКО- ЛЫ Глава 2 Элементы протоколов 2.1 Введение в протоколы Смысл криптографии - в решении проблем . (По сути, в этом состоит и смысл использования компьютеров, о чем многие пытаются забыть.) Криптография решает проблемы секретности, проверки подлинности, целостн о- сти и человеческой нечестности. Вы можете выучить все о криптографических алгоритмах и методах, но они представляют только академический интерес, если не используются для решения какой-нибудь проблемы . Именно поэтому мы собираемся сначала взглянуть на протоколы . Протокол - это порядок действий, предпринимаемых двумя или более сторонами, предназначенный для р е- шения определенной задачи. Это важное определение. "Порядок действий" означает, протокол выполняется в определенной последовательности, с начала до конца . Каждое действие должно выполняться в свою очередь и только после окончания предыдущего. "Предпринимаемых двумя или более сторонами " означает, что для реа- лизации протокола требуется по крайней мере два человека, один человек не сможет реализовать протокол . Че- ловек в одиночку может выполнить некоторые действия, решая задачу (например, покупая торт), но это не пр о- токол. (Для того, чтобы получился настоящий протокол, кто-то должен съесть торт .) Наконец, "предназначенный для решения определенной задачи " означает, что протокол должен приводить к какому-то результату. Что-то, похожее на протокол, но не решающее никакой задачи - это не протокол, это потеря времени. У протоколов есть также и другие характеристики : — Каждый участник протокола должен знать протокол и последовательность составляющих его действий . — Каждый участник протокола должен согласиться следовать протоколу . — Протокол должен быть непротиворечивым, каждое действие должно быть определено так, чтобы не было возможности непонимания. — Протокол должен быть полным, каждой возможной ситуации должно соответствовать определенное де й- ствие. В этой книге каждый протокол организован как некоторый порядок действий . Выполнение протокола проис- ходит по действиям, линейно, пока не будет команды перейти к следующему действию . Каждое действие включает по крайней мере одно из двух: вычисления, выполняемые одной или несколькими сторонами, или сообщения, которыми обмениваются стороны. Криптографический протокол - это протокол, использующий криптографию . Стороны могут быть друзья- ми и слепо доверять друг другу или врагами и не верить друг другу даже при сообщении времени суток . Крип- тографический протокол включает некоторый криптографический алгоритм, но, вообще говоря, предназначение протокола выходит за рамки простой безопасности . Участники протокола могут захотеть поделиться секретом друг с другом, совместно генерировать случайную последовательность, подтвердить друг другу свою подли н- ность или подписать контракт в один и тот же момент времени. Смысл использования криптографии в проток о- ле - в предотвращении или обнаружении вредительства и мошенничества . Если вы никогда не сталкивались с подобными протоколами, они могут радикально изменить ваше представление о том, что недоверяющие друг другу стороны могут выполнить, используя компьютерную сеть . Общее правило можно сформулировать сл е- дующим образом: — Невозможно сделать или узнать больше, чем определено в протоколе . Это гораздо сложнее, чем кажется. В следующих нескольких главах я рассматриваю множество протоколов . В некоторых из них один из участников может обмануть другого . В других, злоумышленник может взломать протокол или узнать секретную информацию . Ряд протоколов проваливаются, так как их разработчики недост а- точно тщательно определяли требования. Другие проваливаются из-за того, что их разработчики недостаточно тщательно анализировали свои протоколы . Как и для алгоритмов, гораздо легче доказать возможную небез о- пасность протокола, чем его полную безопасность. Смысл протоколов В повседневной жизни почти для всего существуют неформальные протоколы : заказ товаров по телефону, игра в покер, голосование на выборах. Никто не задумывается об этих протоколах, они вырабатывались в теч е- ние длительного времени, все знают, как ими пользоваться и они работают достаточно хорошо . Сегодня все больше и больше людей общаются не лично, а используя компьютерную сеть . Для тех же ве- щей, которые люди делают не задумываясь, компьютерам нужны формальные протоколы . Когда вы переезжае- те из государства в государство и обнаруживаете кабинку, совершенно отличающуюся от той, к которой вы пр и- выкли, вы легко адаптируетесь. Компьютеры далеко не так гибки . Честность и безопасность многих протоколов человеческого общения основаны на личном присутствии . Раз- ве вы дадите незнакомцу кучу денег, чтобы он купил для вас что-нибудь в бакалее ? Сядете ли вы играть в покер с тем, кто жульничает, сдавая карты? Пошлете ли вы свой избирательный бюллетень правительству, не будучи уверенным в тайности такого голосования? Наивно считать, что пользователи компьютерных сетей всегда честны. Также наивно считать, что всегда ч е- стны разработчики компьютерных сетей. Для большинства из них это именно так, но даже несколько жуликов могут принести много вреда. Формализируя протоколы, можно проверить способы, используемые жуликами для взлома протоколов. Так мы можем разработать протоколы, устойчивые к взлому. Кроме формализации действий, протоколы позволяют абстрагироваться при решении задачи от способа р е- шения. Протокол связи один и тот же и на PC, и на VAX. Можно проверить протокол, не вдаваясь в детали его реализации. Когда мы убедимся в надежности протокола, его можно будет реализовать где угодно от компьют е- ров до телефонов и интеллектуальных тостеров . Игроки Для демонстрации работы протоколов я использую несколько игроков (см. 1-й). Первые двое - это Алиса и Боб. Они участвуют во всех двусторонних протоколах . Как правило, Алиса (Alice) начинает все протоколы, а Боб (Bob) отвечает. Если для протокола нужна третья или четвертая сторона, в игру вступают Кэрол (Кэрол) и Дэйв (Dave). Другие игроки играют специальные вспомогательные роли, они будут представлены по зже. Протоколы с посредником Посредник - это незаинтересованная третья сторона, которой доверено завершение протокола (см. 1-й (а)). Незаинтересованность означает, что у посредника нет заинтересованности в результате работы протокола и склонности к одной из сторон. "Доверено" означает, что все участники протокола принимают все, что скажет посредник за истину, все его действия - как правильные, и уверены в том, что посредник выполнит свою часть протокола. Посредники помогают реализовать работу протоколов взаимодействия недоверяющих друг другу сторон. В реальном мире в качестве посредников часто выступают юристы . Например, Алиса продает незнакомому ей Бобу машину. Боб хочет заплатить чеком, но у Алисы нет способа проверить, действителен ли чек . Алиса хочет, чтобы расчет по чеку был произведен прежде, чем право собственности перейдет к Бобу . Боб, который верит Алисе не больше, чем она ему, не хочет передавать чек, не получив права собственности . Табл. 2-1. Действующие лица Алиса Первый участник всех протоколов Боб Второй участник всех протоколов Кэрол Третий участник в протоколах с участием трех и четырех сторон Дэйв Четвертый участник в протоколах с участием трех и четырех сторон Ева Злоумышленник (eavesdropper) Мэллори Взломщик протоколов Трент Заслуживающий доверия посредник Уолтер Контролер, защищает Алису и Боба в ряде протоколов Пегги Свидетель Виктор Проверяет подлинность (а) протокол с посредником (б) арбитражный протокол после случившегося Боб Трент Алиса Алиса Боб Трент Доказательство Доказательство (в) самодостаточный протокол Боб Алиса Рис. 2-1. Типы протоколов Посредничество юриста устроит обоих. С его помощью Алиса и Боб могут выполнить следующий протокол, чтобы защитить себя от обмана: (1) Алиса передает право собственности юристу. (2) Боб передает чек юристу. (3) Алиса депонирует чек. (4) Дождавшись оплаты чека юрист передает право собственности Бобу. Если чек не оплачен в течение опр е- деленного времени, Алиса доказывает этот факт юристу, и тот возвращает право собственности Алисе. В этом протоколе Алиса верит, что юрист не передаст Бобу право собственности до тех пор, пока чек не б у- дет оплачен, и вернет право собственности Алисе, если чек оплачен не будет. Боб верит, что юрист будет обла- дать правом собственности до тех пор, пока чек не будет оплачен, и передаст право собственности Бобу сразу же после оплаты чека. Юрист не заботится об оплате чека. Он в любом случае выполнит свою часть протокола, ведь ему заплатят в любом случае. В этом примере юрист играет роль посредника . Юристы часто выступают в роли посредников при завещ а- ниях и иногда при переговорах о контракте . Различные биржи выступают в качестве посредников между пок у- пателями и продавцами. В качестве посредника может выступить и банк - для покупки машины : (1) Боб заполняет чек и передает его в банк. (2) Если на счету Боба достаточно денег для покрытия чека, банк заверяет чек и возвращает его Бобу. (3) Алиса передает Бобу право собственности, а Боб передает Алисе заверенный чек. (4) Алиса депонирует чек. Этот протокол работает, потому что Алиса верит банковскому свидетельству . Алиса верит, что банк сохра- нит деньги Боба для нее и не использует их для финансирования сомнительных операций с недвижимостью в банановых республиках. Другим общепринятым посредником является нотариус . Когда Боб получает от Алисы заверенный нотари у- сом документ, он убежден, что Алиса подписала документ по своему желанию и собственноручно . При необхо- димости нотариус может выступить в суде и засвидетельствовать этот факт . Понятие посредника старо как мир. Всегда существовали определенные люди - вожди, жрецы и тому подо б- ное - обладавшие влиянием, позволяющим им действовать справедливо. Посредники играют определенную роль в нашем обществе, обман доверия подорвал бы занимаемое ими положение . Юристы-посредники, нару- шающие правила игра, подвергаются наказанию - например, исключению из коллегии адвокатов . Это идеаль- ная картина, в реальном мире положение, к сожалению, может отличаться от нее . Этот идеал можно перенести на мир компьютеров, но с компьютерными посредниками существует ряд пр о- блем: — Легко найти нейтральную третью сторону, которой можно доверять, если вы знаете посредника и можете лично увидеть его. Две стороны, относящиеся друг к другу с подозрением, с тем же подозрением отнесу т- ся и к безликому посреднику, затерянному где-то в сети . — Компьютерная сеть должна обеспечить поддержку посредника. Занятость юристов общеизвестна, на кого в сети лягут дополнительные накладные расходы ? — Существует задержка, присущая всем протоколам с посредником . — Посредник должен принимать участие в каждой транзакции, являясь узким местом в крупномасштабных реализациях любого протокола. Рост числа посредников смягчит эту проблему, но вырастет и цена этой услуги. — Так как каждый в сети должен доверять посреднику, то посредник представляет собой слабое место сети при попытке ее взлома. Несмотря на это посредничество все еще активно используется. В протоколах с использованием посредника эту роль будет играть Трент. Арбитражные протоколы Используемый из-за высокой стоимости найма посредников арбитражные протокол может быть разбит на два подпротокола нижнего уровня. Первый представляет собой протокол без посредника, используемый при желании сторон выполнить протокол. Другой представляет собой протокол с посредником, приглашаемым в исключительных обстоятельствах - при наличии разногласий между сторонами . Соответствующий специальный посредник называется арбитром (см. 1-й(б)). Арбитр, как и посредник, представляет собой незаинтересованного участника протокола, которому доверяют обе стороны. В отличие от посредника он непосредственно не принимает участия в каждой отдельной реализа- ции протокола и приглашается только для проверки честности выполнения протокола сторонами . Профессиональными арбитрами являются судьи. В отличие от нотариусов к судьям обращаются только при появлении разногласий. Алиса и Боб могут заключить контракт без участия судьи . Судья никогда не узнает о контракте, если одна из сторон не подаст на другую в суд . Протокол подписания контракта можно формализ о- вать следующим образом: Подпротокол без посредника (выполняется всегда) : (1) Алиса и Боб договариваются об условиях контракта. (2) Алиса подписывает контракт. (3) Боб подписывает контракт. Подпротокол с использованием арбитра (выполняется при наличии разногласий) : (4) Алиса и Боб предстают перед судьей. (5) Алиса предоставляет свои доказательства. (6) Боб предоставляет свои доказательства. (7) Судья принимает решение на основании доказательств. Различие используемых в этой книге понятий посредника и арбитра состоит в том, что участие арбитра пр о- исходит не всегда. Стороны обращаются к судье только при разногласиях. Если разногласий нет, судья не н у- жен. Существуют арбитражные компьютерные протоколы. Они предполагают, что участвующие стороны честны, но при подозрении о возможном мошенничестве по существующему набору данных третья сторона, которой доверяют участники, сможет обнаружить факт мошенничества . Хороший арбитражный протокол позволяет а р- битру установить и личность мошенника. Арбитражные протоколы обнаруживают, а не предупреждают моше н- ничество. Неотвратимость обнаружения выступает в качестве предупредительной меры, предотвращая моше н- ничество. Самодостаточные протоколы Самодостаточный протокол является лучшим типом протокола. Он полностью обеспечивает честность сторон (см. 1-й(в)). Для выполнения протокола не нужен ни посредник, не решающий споры арбитр . Само по- строение протокола обеспечивает отсутствие споров. Если одна из сторон попытается смошенничать, мошенн и- чество будет немедленно обнаружено другой стороной, и протокол прекратит выполняться. Чего бы не пыталась добиться мошенничающая сторона, этому не суждено случиться. В лучшем мире любой протокол должен быть самодостаточным, но, к несчастью, не существует самодост а- точных протоколов для каждой ситуации. Попытки вскрытия протоколов Криптографические попытки взлома могут быть направлены против криптографических алгоритмов, и с- пользуемых в протоколах, против криптографических методов, используемых для реализации алгоритмов и протоколов или непосредственно против протоколов. Поскольку в этом разделе книги обсуждаются именно пр о- токолы, я предполагаю, что криптографические алгоритмы и методы безопасны , и рассматриваю только попыт- ки вскрытия протоколов. Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр о- токола, могут "подслушивать" какую-то часть или весь протокол . Это называется пассивным вскрытием, так как взломщик не воздействует на протокол . Все, что он может сделать - это проследить за протоколом и поп ы- таться добыть информацию. Этот тип вскрытия соответствует вскрытию с использованием только шифротекста, обсуждавшемуся в разделе 1.1. Так как пассивные вскрытия трудно обнаружить, протоколы стремятся предо т- вращать, а не обнаруживать их. В этих протоколах роль злоумышленника будет играть Ева . В другом случае взломщик может попытаться изменить протокол для собственной выгоды . Он может выдать себя за другого, ввести новые сообщения в протокол, заменить одно сообщение другим, повторно передать ст а- рые сообщения, разорвать канал связи или изменить хранящуюся в компьютере информацию . Такие действия называются активным вскрытием, так как они требуют активного вмешательства . Эти формы вскрытия зависят от вида сети. Пассивные взломщики стараются получить информацию об участниках протокола . Они собирают сообще- ния, переданные различными сторонами, и пытаются криптоанализировать их . Попытки активного вскрытия, с другой стороны, преследуют более широкий набор целей. Взломщик может быть заинтересован в получении информации, ухудшении работы системы или получении несанкционированного доступа к ресурсам . Активные вскрытия более серьезны, особенно в отношении протоколов, в которых стороны не обязательно доверяют друг другу. Взломщик не обязательно кто-то совсем посторонний, он может быть зарегистрированным пользователем системы и даже системным администратором . Может быть даже несколько активных взломщ и- ков, работающих вместе. В этой книге роль злонамеренного активного взломщика будет играть Мэ ллори. Взломщиком может быть и один из участников протокола . Он может обманывать, выполняя протокол, или вовсе не следовать правилам протокола. Такой взломщик называется мошенником. Пассивные мошенники выполняют правила протокола, но стараются получить больше информации, чем предусмотрено протоколом . Активные мошенники нарушают работу протокола, пытаясь смошенничать . Очень трудно поддерживать безопасность протокола, если большинство его участников - активные моше н- ники, но иногда активное мошенничество может быть обнаружено законными участниками . Конечно, протоко- лы должны быть защищены и от пассивного мошенничества . 2.2 Передача информации с использованием симметричной криптографии Как двум сторонам безопасно обмениваться информацией? Конечно же, шифрую свои сообщения. Посмот- рим, что должно произойти, когда Алиса посылает шифрованное сообщение Бобу (полный протокол гораздо сложнее). (1) Алиса и Боб выбирают систему шифрования. (2) Алиса и Боб выбирают ключ. (3) Алиса шифрует открытый текст своего сообщения с использованием алгоритма шифрования и ключа, п о- лучая шифрованное сообщение. (4) Алиса посылает шифрованное сообщение Бобу. (5) Боб дешифрирует шифротекст сообщения с использованием алгоритма шифрования и ключа, получая о т- крытый текст сообщения. Что может Ева, находясь между Алисой и Бобом, узнать, подслушивая этот протокол ? Если она может под- слушать только передачу на этапе (4), ей придется подвергнуть шифротекст криптоанализу . Это пассивное вскрытие представляет собой вскрытие с использованием только шифротекста, применяемые алгоритмы усто й- чивы (насколько нам известно) по отношению к любым вычислительным мощностям, который может запол у- чить Ева для решения проблемы. Ева, однако, не глупа. Она может также подслушать и этапы (1) и (2). Тогда ей станут известны алгоритм и ключ - также как и Бобу. Когда она перехватит сообщение на этапе (4), то ей останется только дешифровать его самостоятельно. В хорошей криптосистеме безопасность полностью зависит от знания ключа и абсолютно не зависит от зн а- ния алгоритма. Именно поэтому управление ключами так важно в криптографии . Используя симметричный алгоритм, Алиса и Боб могут открыто выполнить этап (1), но этап (2) они должны сохранить в тайне . Ключ должен оставаться в секрете перед, после и в течение работы протокола - до тех пор, пока должно оставаться в тайне передаваемое сообщение - в противном случае сообщение тут же будет раскрыто . (О криптографии с от- крытыми ключами, решающей эту проблему иначе, рассказывается в разделе 2.5 .) Мэллори, активный взломщик, может сделать кое-что другое. Он может попытаться нарушить линию связи не этапе (4), сделав так, что Алиса вообще не сможет передавать информацию Бобу . Мэллори также может пе- рехватить сообщение Алисы и заменить его своим собственным . Если ему удалось узнать ключ (перехватив обмен информацией на этапе (2) или взломав криптосистему), он сможет зашифровать свое сообщение и отпр а- вить его Бобу вместо перехваченного, и Боб не сможет узнать, что сообщение отправлено не Алисой. Если Мэ л- лори не знает ключа, он может только создать сообщение, превращающееся при дешифровке в бессмыслицу . Боб, считая, что сообщение отправлено Алисой, может решить, что либо у Алисы, либо в сети возникли серье з- ные проблемы. А Алиса? Что она может сделать, чтобы испортить протокол? Она может передать копию ключа Еве, и тогда Ева сможет читать все, что говорит Боб, и напечатать его слова в Нью-Йорк Таймс. Это серьезно, но проблема не в протоколе. Алиса и так может передавать Еве любые открытые тексты, передаваемые с использованием протокола. Конечно, то же самое может сделать и Боб. Протокол предполагает, что Алиса и Боб доверяют друг другу. Итак, симметричным криптосистемам присущи следующие проблемы : — Распределение ключей должно проводиться в секрете . Ключи столь же важны, как и все сообщения, за- шифрованные этими ключами, так как знание ключа позволяет раскрыть все сообщения . Для распро- страненных систем шифрования задача распределения ключей - серьезнейшая задача . Часто курьеры лично доставляют ключи по назначению . — Если ключ скомпрометирован (украден, разгадан, выпытан, получен за взятку и т.д. ), то Ева сможет расшифровать все сообщения, зашифрованные этим ключом . Она сможет также выступить в качестве одной из сторон и создавать ложные сообщения, дурача другую сторону . — В предположении, что каждая пара пользователей сети использует отдельный ключ, общее число ключей быстро возрастает с ростом числа пользователей . Сеть из n пользователей требует n{n - l)/2 ключей. На- пример, для общения 10 пользователей между собой нужно 45 различных ключей, для 100 пользователей потребуется 4950 ключей. Решение проблемы - в уменьшении числа пользователей, но это не всегда во з- можно. 2.3 Однонаправленные функции Понятие однонаправленной функции является центральным в криптографии с открытыми ключами . Не являясь протоколами непосредственно однонаправленные функции представляют собой краеугольный камень большинства протоколов, обсуждаемых в этой книге . Однонаправленные функции относительно легко вычисляются, но инвертируются с большим трудом . То есть, зная x просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь, "нелегко" означает, что для вы- числения x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компь ю- теры мира. Хорошим примером однонаправленной функции служит разбитая тарелка . Легко разбить тарелку на тысячу крошечных кусочков.. Однако, нелегко снова сложить тарелку из этих кусочков . Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования одн о- направленных функций нет, нет и реальных свидетельств возможности их построения [230, 530, 600, 661]. Не- смотря на это, многие функции выглядят в точности как однонаправленные : мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их . Например, в ограниченной окрестности легко вычислить x 2 , но намного сложнее x 1/2 . В оставшейся части раздела я собираюсь притвориться, что однонаправленные фун к- ции существуют. Мы поговорим об этом в еще разделе 11.2. Итак, что же хорошего в однонаправленных функциях ? Непосредственно их нельзя использовать для ши ф- рования. Сообщение, зашифрованное однонаправленной функцией бесполезно - его невозможно дешифровать . (Упражнение: напишите на тарелке что-нибудь, разбейте тарелку на крошечные осколки и затем отдайте их приятелю. Попросите его прочитать сообщение. Посмотрите, как он будет озадачен однонаправленной функц и- ей.) Для криптографии с открытыми ключами нам нужно что-то другое (хотя существуют и непосредственные криптографические применения однонаправленных функций - см. раздел 3.2). Однонаправленная функция с люком - это особый тип однонаправленной функции, с секретной лазейкой . Ее легко вычислить в одном направлении и трудно - в обратном . Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному x, но трудно по известному f(x) вычислить x. Однако, существует небольшая секретная информация , y, позволяющая, при знании f(x) и y, легко вычислить x. В качестве хорошего примера однонаправленной функции с люком рассмотрим часы . Легко разобрать часы на сотни малюсеньких кусочков и трудно снова собрать из этих деталей работающие часы . Но, с секретной ин- формацией - инструкцией по сборке - намного легче решить эту задачу . 2.4 Однонаправленные хэш-функции У однонаправленной хэш-функции может быть множество имен: функция сжатия, функция сокращения contraction function, краткое изложение, характерный признак, криптографическая контрольная сумма, код це- лостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась эта функция является центральной в современной криптографии . Одно- направленные хэш-функции - это другая часть фундамента многих протоколов . Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, мате- матические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преоб- разуют ее в строку фиксированной, обычно меньшей, длины (называемую значением хэш -функции). В качестве простой хэш-функции можно рассматривать функцию, которая получает прообраз и возвращает байт, предста в- ляющий собой XOR всех входных байтов. Смысл хэш-функции состоит в получении характерного признака прообраза - значения, по которому анал и- зируются различные прообразы при решении обратной задачи . Так как обычно хэш-функция представляет со- бой соотношение "многие к одному", невозможно со всей определенностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности . Однонаправленная хэш-функция - это хэш-функция, которая работает только в одном направлении : легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш -функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленн ы- ми: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такого не выйдет. Хорошей однонаправленной хэш-функцией является хэш-функция без столкновений - трудно создать два прообраза с одинаковым значением хэш -функции. Хэш-функция является открытой, тайны ее расчета не существует . Безопасность однонаправленной хэш-функцией заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа . Из- менение одного бита прообраза приводи к изменению, в среднем, половины битов значения хэш -функции. Вы- числительно невозможно найти прообраз, соответствующий заданному значению хэш -функции. Посмотрите на это как на способ получить характерные признаки файлов . Если вы хотите проверить, что у кого-то есть тот же файл, что и у вас, но вы не хотите, чтобы этот файл был передан вам, попросите послать вам значение хэш-функции. Если присланное значение хэш-функции совпадет с рассчитанным вами, то почти н а- верняка чужой файл совпадает с вашим. Это особенно полезно при финансовых транзакциях , когда вы не хоти- те где-то в сети превратить снятие со счета $100 в снятие $1000. В обычных условиях вы можете использовать однонаправленную хэш-функцию без ключа, так что кто угодно может проверить значение хэш -функции. Если нужно, чтобы проверить значение хэш-функции мог только один получатель, прочтите следующий раздел . Коды проверки подлинности сообщения Код проверки подлинности сообщения (message authentication code, MAC), известный также как код про- верки подлинности данных (data authentication code, DAG), представляет собой однонаправленную хэш-функцию с добавлением секретного ключа (см. раздел 18.14). Значение хэш- функции является функцией и прообраза, и ключа. Теория остается той же, что и для хэш-функций, но только тот, кто знает ключ, может проверить знач е- ние хэш- функции . MAC можно создать с помощью хэш-функции или блочного алгоритма шифрования, сущес т- вуют также и специализированные MAC. 2.5 Передача информации с использованием криптографии с открытыми кл ю- чами Взгляните на симметричный алгоритм как на сейф. Ключ является комбинацией. Знающий комбинацию ч е- ловек может открыть сейф, положить в него документ и снова закрыть. Кто-то другой при помощи той же ко м- бинации может открыть сейф и забрать документ . Тем, кто не знает комбинации, придется научиться взлам ы- вать сейфы. В 1976 году Уитфилд Диффи и Мартин Хеллман навсегда изменили эту парадигму криптографии [496]. (NSA заявило, что знало о такой возможности еще в 1966 году, но доказательств не представило .) Они описали криптографию с открытыми ключами, используя два различных ключа - один открытый и один закрытый . Определение закрытого ключа по открытому требует огромных вычислительных затрат. Кто угодно, используя открытый ключ может зашифровать сообщение, но не расшифровать его. Расшифровать сообщение может только владелец закрытого ключа. Это похоже на превращение криптографического сейфа в почтовый ящик . Шифрование с открытым ключом аналогично опусканию письма в почтовый ящик, любой может сделать это, опустив письмо в прорезь почтового ящика . Дешифрирование с закрытым ключом напоминает извлечение по ч- ты из почтового ящика. Обычно это гораздо сложнее - вам может понадобиться сварочный агрегат . Однако, если вы знаете секрет (у вас есть ключ от почтового ящика ), вы без труда достанете вашу почту. Математической основой процесса являются ранее обсуждавшиеся однонаправленные хэш-функции с люком. Шифрование выполняется в прямом направлении . Указания по шифрованию открыты, каждый может зашифровать сообщение. Дешифрирование выполняется в обратном направлении . Оно настолько трудоемко, что, не зная секрета, даже на компьютерах Cray за тысячи (и миллионы) лет невозможно расшифровать соо б- щение. Секретом, или люком, и служит закрытый ключ, он делает дешифрирование таким же простым, как и шифрование. Вот как, используя криптографию с открытыми ключами, Алиса может послать сообщение Бобу : (1) Алиса и Боб согласовывают криптосистему с открытыми ключами. (2) Боб посылает Алисе свой открытый ключ. (3) Алиса шифрует свое сообщение и отправляет его Бобу. (4) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа. Обратите внимание, что криптография с открытыми ключами устраняет проблему распределения ключей, присущую симметричным криптосистемам . Раньше Алиса и Боб должны были тайно договориться о ключе . Алиса могла выбрать любой ключ, но ей нужно было передать его Бобу. Она могла сделать это заранее, но это требует от нее определенной предусмотрительности . Она могла бы послать ключ с секретным курьером, но для этого нужно время. Криптография с открытыми ключами все упрощает. Алиса может отправить Бобу секретное сообщение без каких-либо предварительных действий . У Евы, подслушивающей абсолютно все, есть открытый ключ Боба и сообщение, зашифрованное этим ключом, но она не сможет получить ни закрытый ключ Боба, ни текст сообщения. Обычно целая сеть пользователей согласовывает используемую криптосистему . У каждого из них есть от- крытый и закрытый ключ, открытые ключи помещаются в общедоступной базе данных . Теперь протокол вы- глядит еще проще: (1) Алиса извлекает открытый ключ Боба из базы данных. (2) Алиса шифрует свое сообщение с помощью открытого ключа Боба и посылает его Бобу. (3) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа. В первом протоколе Боб должен был послать Алисе ее открытый ключ прежде, чем она могла отправить ему сообщение. Второй протокол больше похож на обычную почту. Боб не участвует в протоколе до тех пор, пока он не начнет читать сообщение. Смешанные криптосистемы Первые алгоритмы с открытым ключом стали известны в то же время, когда проходило DES обсуждение как предполагаемого стандарта. Это привело к известной партизанщине в криптографическом сообществе . Как это описывал Диффи [494]: Прекрасные криптосистемы с открытым ключом, обсуждаемые в популярной и научной печати, тем не менее, не нашли соответствующего отклика среди криптографических чиновников . В том же году, когда была открыта криптография с откр ы- тыми ключами, Агентство национальной безопасности ( NSA) предложило удобную криптографическую систему , разрабо- танную фирмой IBM, в качестве федерального Стандарта шифрования данных (Data Encryption Standard, DES). Марти Хеллман и я критиковали это предложение из-за недостаточной длины ключа, но производители подготовились поддержать стандарт, и наша критика была воспринята многими как попытка помешать введению стандарта ради продвижения нашей собственной работы. Криптография с открытым ключом, в свою очередь, также подвергалась критике в популярной литер а- туре [1125] и технических статьях [849, 1159], словно это был конкурирующий продукт, а не недавнее научное открытие . Это, однако, не помешало NSA объявить о своих заслугах в этой области . Его директор в одной из статей Encyclopedia Bri- tannica [1461] указал, что "двухключевая криптография была открыта в Агентстве на десять лет раньше ", хотя доказательства этого утверждения не были публично представлены. В реальном мире алгоритмы с открытыми ключами не заменяют симметричные алгоритмы и используются не для шифрования сообщений, а для шифрования ключей по следующим двум причинам : 1. Алгоритмы с открытыми ключами работают медленно. Симметричные алгоритмы по крайней мере в 1000 раз быстрее, чем алгоритмы с открытыми ключами . Да, компьютеры становятся все быстрее и быстрее и лет через 15 криптография с открытыми ключами достигнет скоростей, сравнимых с сег о- дняшней скоростью симметричной криптографии . Но требования к объему передаваемой информации также возрастают, и всегда будет требоваться шифровать данные быстрее, чем это сможет сделать криптография с открытыми ключами. 2. Криптосистемы с открытыми ключами уязвимы по отношению к вскрытию с выбранным открытым текстом. Если C = E(P), где P - открытый текст из n возможных открытых текстов, то криптоаналити- ку нужно только зашифровать все n возможных открытых текстов и сравнить результаты с C (помните, ключ шифрования общедоступен). Он не сможет раскрыть ключ дешифрирования, но он сможет определить P. Вскрытие с выбранным открытым текстом может быть особенно эффективным, если число возможных шифрованных сообщений относительно мало . Например, если P - это денежная сумма в долларах, меньшая чем $1000000, то такое вскрытие сработает, криптоаналитик переберет весь миллион значений . (Эта проблема ре- шается с помощью вероятностного шифрования, см. раздел 23.15.) Даже если P не так хорошо определено, та- кое вскрытие может быть очень эффективно . Полезным может быть простое знание, что шифротекст не соо т- ветствует конкретному открытому тексту. Симметричные криптосистемы не чувствительны к вскрытиям такого типа, так как криптоаналитик не может выполнить тестовых дешифровок с неизвестным ключом . В большинстве реализаций криптография с открытыми ключами используется для засекречивания и распр о- странения сеансовых ключей, которые используются симметричными алгоритмами для закрытия потока сооб- щений [879]. Иногда такие реализации называются смешанными (гибридными) криптосистемами (1) Боб посылает Алисе свой открытый ключ (2) Алиса создает случайный сеансовый ключ, шифрует его с помощью открытого ключа Боба и передает его Бобу. E B (K) (3) Боб расшифровывает сообщение Алисы, используя свой закрытый ключ, для получения сеансового ключа. D B (E B (K))=K (4) Оба участника шифруют свои сообщения с помощью одного сеансового ключа. Использование криптографии с открытыми ключами для распределения ключей решает очень важную пр о- блему распределения ключей. В симметричной криптографии ключ шифрования данных, если он не использу- ется, валяется без дела. Если Ева заполучит его, она сможет расшифровать все закрытые этим ключом сообщ е- ния. С помощью приведенного протокола при необходимости зашифровать сообщения создается сеансовый ключ, который уничтожается по окончании сеанса связи . Это значительно уменьшает риск компрометации с е- ансового ключа. Конечно, к компрометации чувствителен и закрытый ключ, но риска значительно меньше, так как в течение сеанса этот ключ используется только один раз для шифрования сеансового ключа . Подробно свя- занные с этим вопросы обсуждаются в разделе 3.1. Головоломки Меркла Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами . В 1974 году он за- писался на курс по компьютерной безопасности в Калифорнийском университете, Беркли , который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам" [1064]. Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой несмотря на продолжающееся непонимание его р е- зультатов. Техника Меркла основывалась на головоломках ( "puzzle"), которые отправителю и получателю решить ле г- че чем злоумышленнику. Вот как Алиса может послать шифрованное сообщение Бобу, не обмениваясь с ним ключом до того. (1) Боб создает 2 20 (другими словами, больше миллиона) сообщений типа: "Это головоломка номер x. Это секретный ключ номер y.", где x - случайное число, а y - случайный секретный ключ. И x, и y отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 би т- ным ключом и все их отправляет Алисе. (2) Алиса выбирает одно сообщение и приступает к вскрытию грубой силой, пытаясь получить открытый текст. Эта работа является объемной, но не невозможной. (3) Алиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Бобу вместе с x. (4) Боб знает, какой секретный ключ y он использовал в сообщении x, следовательно он может расшифровать сообщение Алисы. Ева может взломать эту систему, но ей придется выполнить гораздо больше работы чем Алисе и Бобу . Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 2 20 сообщений, отправ- ленных Бобом на этапе (1). Сложность этого вскрытия составит 2 40 . Значения x также не помогут Еве, ведь они на этапе (1) присвоены случайным образом . В общем случае, вычислительные затраты Евы будут равны возв е- денным в квадрат вычислительным затратам Алисы . Это выигрыш (n по отношению к n 2 ) невелик по криптографическим стандартам, но при определенных усл о- виях может быть достаточен. Если Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе по линии связи 1.544 Мбит/с. Если вычислительные возможности Евы сравнимы с приведенными, ей потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию . 2.6 Цифровые подписи Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, |