Протоколы, алгоритмы и исходные тексты на языке С

Прикладная криптография

Е издание

Протоколы, алгоритмы и исходные тексты на языке С

Брюс Шнайер

Предисловие Уитфилд Диффи

История литературы по криптографии довольно любопытна. Секретность, конечно же, всегда играла важную роль, но до Первой мировой войны о важных разработках время от времени сообщалось в печати и криптогр а-фия развивалась также, как и другие специализированные дисциплины. В 1918 году в виде научного отчета ч а-стной Лаборатории Ривербэнк вышла в свет монография Вильяма Ф. Фридмана Показатель совпадений и его применения в криптографии (Index of Coincidence and Its Applications in Cryptography) [577], одна из опреде­ляющих работ 20-го столетия. И это несмотря на военный заказ, по которому была сделана эта работа. В том же году Эдвард X. Хеберн из Окленда, Калифорния, получил первый патент [710] на роторную машину, устройст­во, на котором основывалась военная криптография в течение почти 50 лет.

После Первой мировой войны, однако, все изменилось. Организации армии и флота Соединенных Штатов, полностью засекретив свои работы, добились фундаментальных успехов в криптографии. В течение 30 -х и 40-х годов в открытой литературе по данному предмету появлялись только отдельные основные работы и моногр а-фии, но чем дальше, тем меньше они соответствовали реальному положению дел. К концу войны переход по л-ностью завершился. Открытая литература умерла за исключением одного заметного исключения, работы Клода Шэннона "The Communication Theory of Secrecy systems" (Теория связи между секретными системами), напе­чатанной в 1949 году в Bell System Technical Journal [1432]. Эта статья, как и работа Фридмана в 1918 году, явилась результатом исследований Шэннона во время войны. После окончания Второй мировой войны она была рассекречена, возможно по ошибке.

С 1949 по 1967 литература по криптографии была бессодержательной. В 1967 году она пополнилась работой другого типа, историей Дэвида Кана Дешифровщики {The Codebreakers) [794]. В этой книге не было новых идей, но она содержала достаточно полную историю предмета, включая упоминание о некоторых вещах, все еще засекреченных правительством. Значение Дешифровщиков заключалось не только в значительном охвате предмета, книга имела заметный коммерческий успех и познакомила с криптографией тысячи людей, раньше и не задумывавшихся о ее существовании. Тоненьким ручейком начали появляться новые работы по криптогр а-фии.

Почти в то же время Хорста Фейстела, ранее работавшего над прибором "свой/чужой" для ВВС, на всю дальнейшую жизнь охватила страсть к криптографии, и он перешел в Уотсоновскую Лабораторию фирмы IBM, расположенную в Йорктаун Хайте, Нью-Йорк. Там он начал разработку того, что затем стало стандартом DES (U.S. Data Encryption Standard, Стандарт шифрования данных Соединенных Штатов). В начале 70-х годов IBM опубликовала ряд технических отчетов по криптографии, выполненных Фейстелом и его коллегами [1482, 1484, 552].

Таково было положение, когда в конце 1972 года я начал работать в этой области. Литература по крипт о-графии обильной не была, но в ней можно было найти ряд сверкающих самородков.

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

Когда Мартин Хеллман и я в 1975 году предложили криптографию с открытыми ключами [496], одним из косвенных аспектов нашего предложения было появление проблемы, решение которой не кажется простым. Теперь честолюбивый проектировщик мог создать что-то - вполне разумную криптосистему, решающую более обширные задачи, чем простое превращение значимого текста в чепуху. В результате значительно возросло число людей, занимающихся криптографией, число проводимых встреч и число опубликованных книг и статей.

В речи по поводу присуждения мне совместно с Мартином Хеллманом премии Дональда Е. Финка (присуждаемой за лучшую пояснительную статью в журнале IEEE) я сказал, что, написав "Privacy and Authenti­cation" ("Секретность и удостоверение подлинности"), я получил опыт, который необычен даже для выдающи х-ся ученых, получивших премии IEEE. Я написал статью, которую я хотел бы изучить, когда я впервые серьезно заинтересовался криптографией, и которую не смог найти. Если бы я сегодня отправился в Стэнфордскую би б-лиотеку и собрал бы современные работы по криптографии, я, возможно, получил бы представление о предмете гораздо раньше. Но осенью 1972 года были доступны только несколько классических работ и ряд туманных технических отчетов.

У сегодняшнего исследователя нет такой проблемы. Сегодня основная сложность состоит в выборе, с чего

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

Именно этот промежуток и призвана заполнить Прикладная криптография Брюса Шнайера. Начав с целей засекречивания передачи данных и элементарных примеров программ для достижения этих целей, Шнайер ра з-ворачивает перед нами панораму результатов 20 лет открытых исследований. Содержание книги полностью определяется ее названием, вы найдете в ней описание различных приложений, от засекречивания телефонного разговора до электронных денег и криптографического обеспечения выборов.

Не удовлетворенный простым изложением алгоритмов и описанием кода, Шнайер включил в книгу обсу ж-дение различных мировых организаций, связанных с разработкой и применением криптографических средств, от Международной ассоциации криптологических исследований до NSA (National Security Agency, Агентство национальной безопасности).

Когда на рубеже 70-х и 80-х годов возрос общественный интерес к криптографии, NSA, официальный крип-тографичекий орган США, предприняло ряд попыток подавить этот интерес. Первой такой попыткой было письмо старого сотрудника NSA, по видимому действовавшего по своему усмотрению. Письмо было послано в IEEE и предупреждало, что публикация материалов по криптографии является нарушением Правил междун а-родной продажи оружия (International Traffic in Arms Regulations, ITAR). Эта точка зрения, как оказалось, не поддерживаемая самими правилами, в явном виде содержащими льготы для публикуемых материалов, создала неожиданную рекламу использованию криптографии и Семинару по теории информации 1977 года.

Более серьезная попытка была предпринята в 1980 году, когда NSA финансировало изучение вопроса Аме­риканским советом по образованию с целью убедить Конгресс узаконить контроль над публикациями в области криптографии. Результаты, оказавшиеся далекими от ожиданий NSA, привели к программе добровольного ре­цензирования работ по криптографии. От исследователей потребовали перед публикацией запрашивать мнение NSA, не принесет ли раскрытие результатов исследований вред национальным интересам.

К середине 80-х годов основным объектом внимания стала не теория, а практика криптографии. Сущее т-вующие законы дают NSA право с помощью Госдепартамента регулировать экспорт криптографического об о-рудования. Так как бизнес все больше и больше принимает международный характер и американская часть м и-рового рынка уменьшается, возрастает желание использовать единый продукт и для внутреннего, и для внешн е-го рынка. Такие продукты являются субъектами контроля над экспортом, и поэтому NSA получило возможность контролировать не только экспортируемые криптографические продукты, но и продаваемые в Соединенных Штатах.

В то время, когда писались эти строки, возникло новое препятствие для общественного использования кри п-тографии. Правительство дополнило широко опубликованный и используемый алгоритм DES засекреченным алгоритмом, реализованным в микросхемах памяти, независящей от времени. Эти микросхемы будут содержать кодифицированный механизм правительственного контроля. Отрицательные аспекты такой програ м-мы-троянского коня простираются от потенциально губительного раскрытия тайны лич ности до высокой стои­мости аппаратной модернизации продуктов, ранее реализованных программно. Таким образом, предлагаемое нововведение не вызвало энтузиазма и подверглось широкой критике, особенно со стороны независимых кри п-тографов. Ряд людей, однако, видят свое будущее в программировании, а не в политике и удваивают свои ус и-лия, стремясь представить миру мощные средства криптографии.

Значительное отступление от возможности того, что закон о контроле над экспортом отменит Первую п о-правку¹, казалось было сделан в 1980 году, когда в опубликованные в Federal Register исправления ITAR вошло следующее положение: "...положение было добавлено с целью показать, что регулирование экспорта технич е-ских данных не приведет к конфликту с правами личности, определяемыми Первой поправкой". Но то, что ко н-фликт между Первой поправкой и законами о контроле над экспортом не разрешен окончательно, должно быть очевидно из заявлений, сделанных на конференции, проводимой RSA Data Security. Представитель NSA из от­дела контроля над экспортом выразил мнение, что люди, публикующие криптографические программы, нах о-дятся " в серой зоне" по отношению к закону. Если это так, то именно эту "серую зону" немного осветило первое издание этой книги. Экспорт приложений для этой книги был разрешен с подтверждением того, что опублик о-ванные материалы не попадают под юрисдикцию Совета по контролю над вооружением. Однако, экспортир о-вать опубликованные программы на диске было запрещено.

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

^конституции США

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

Уитфилд Диффи

Маунтэйн Вью, Калифорния.

Введение

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

Если я беру письмо, кладу его в сейф где-нибудь в Нью-Йорке, затем велю Вам прочитать это письмо, то это не безопасность. Это непонятно что. С другой стороны, если я беру письмо и кладу его в сейф, затем передаю этот сейф Вам вместе с детальным описанием, передаю также сотню подобных сейфов с их комбинациями, чт о-бы Вы и лучшие "медвежатники" мира могли изучить систему замков, а вы все равно не сможете открыть сейф и прочитать письмо - вот это и есть безопасность.

В течение многих лет этот тип криптографии использовался исключительно в военных целях. Агентство н а-циональной безопасности Соединенных Штатов Америки (National Security Agency, NSA) и его аналоги в быв­шем Советском Союзе, Англии, Франции, Израиле и прочих странах тратили миллиарды долларов на очень серьезную игру в обеспечение безопасности собственных линий связи, одновременно пытаясь взломать все о с-тальные. Отдельные личности, обладающие значительно меньшими средствами и опытом, были беспомощны защитить свои секреты от правительств.

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

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

Эта книга выходит в свет в беспокойное время. В 1994 году администрация Клинтона приняла Стандарт у с-ловного шифрования (Escrowed Encryption Standard), включая микросхему Clipper и плату Fortezza, и превра­тило Билль о Цифровой телефонии в закон. Эти инициативы пытаются увеличить возможности правительства проводить электронный контроль.

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

Законопроекты о микросхеме Clipper и Цифровой телефонии не способствуют сохранению тайны, но беспо ч-венно заставляют людей считать, что правительство уважает их тайны. Те же самые власти, которые незаконно записывали телефоны Мартина Лютера Кинга, могут легко прослушать телефон, защищенный микросхемой Clipper. В недавнем прошлом полицейские власти на местах были привлечены к гражданской или уголовной ответственности за незаконное прослушивание во многих судах - в Мэриленде, Коннектикуте, Вермонте, Джорджии, Миссури и Неваде. Идея развернуть технологию, которая может привести к появлению полице й-ского государства - это плохая идея.

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

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

Как читать эту книгу

Я написал Прикладную криптографию как живое введение в криптографию и как всеобъемлющий спр а-вочник. Я пытался сочетать читаемость текста с жертвенной точностью, но эта книга писалась не как мате­матическая работа. Хотя я не искажал информацию умышленно, торопясь, я опускал теорию . Для интере­сующихся теоретическими выкладками приведены обширные ссылки на академическую литературу .

Глава 1 представляет собой введение в криптографию, описывает множество терминов, в ней кратко ра с-

сматривается докомпьютерная криптография.

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

Главы с 7 по 10 (Часть II) содержат обсуждение методов криптографии. Все эти четыре главы важны для самых распространенных применений криптографии. В главах 7 и 8 рассказывается о ключах: какова должна быть длина безопасного ключа, как генерировать, хранить и распределять ключи, и т.д. Управление ключами представляет собой труднейшую часть криптографии и часто является ахиллесовой пятой систем, безопасных во всем остальном. В главе 9 рассматриваются различные способы использования криптографических алгоритмов, а глава 10 описывает особенности и цели использования этих алгоритмов - как их выбирать, реализовывать и применять.

Главы с И по 23 (Часть III) описывают эти алгоритмы. Глава И представляет собой математическую базу и является обязательной только, если вы интересуетесь алгоритмами с открытыми ключами . Если вы собираетесь использовать DES (или что-то похожее), ее можно пропустить. В главе 12 обсуждается алгоритм DES, его ис­тория, безопасность и разновидности. В главах 13, 14 и 15 рассказывается о других блочных алгоритмах. Если вам нужно что-то более надежное чем DES, сразу переходите к разделам о IDEA и тройном DES. При желании узнать о группе алгоритмов, некоторые из которых могут быть безопаснее DES, прочитайте всю главу. В главах 16 и 17 обсуждаются потоковые алгоритмы. В главе 18 подробно рассматриваются однонаправленные хэш-функции, среди которых самыми являются MDS и SHA, хотя я останавливаюсь и на многих других. В гла­ве 19 рассматриваются алгоритмы шифрования с открытым ключом, а в главе 20 - алгоритмы цифровой под­писи с открытым ключом. В главе 21 обсуждаются алгоритмы идентификации с открытым ключом, а в главе 22 - алгоритмы обмена с открытым ключом. Самыми важными являются алгоритмы RSA, DSA, Фиат-Шамира (Fiat-Shamir) и Диффи-Хелмана (Diffie-Hellman). Глава 23 содержит ряд эзотерических алгоритмов и протоко­лов с открытым ключом, математика в этой главе достаточно сложна, так что пристегните ремни .

Главы 24 и 25 (Часть IV) переносят вас в реальный мир криптографии. В главе 24 обсуждаются некоторые современные применения алгоритмов и протоколов, в то время как глава 25 касается некоторых политических аспектов криптографии. Несомненно, эти главы не являются всеохватывающими .

В книгу также включены исходные коды 10 алгоритмов, рассмотренных в Части III. Я не смог включить весь код, который хотел, из-за его большого объема, кроме того, криптографические коды в любом случае нельзя экспортировать. (Любопытно, что Госдепартамент разрешил экспортировать первое издание этой книги с и с-ходным кодом, но не разрешил экспортировать компьютерный диск с теми же исходными кодами. Смотри р и-сунок.) Соответствующий набор дисков с исходным кодом содержит существенно больше исходных кодов, чем я смог включить в эту книгу, возможно, это самая большая подборка криптографических исходных кодов, по я-вившаяся за пределами военных ведомств. Сейчас я могу переслать эти диски с исходным кодом только граж­данам США и Канады, живущим в этих странах, но, возможно, когда-нибудь все изменится. Если вы собира е-тесь использовать или попробовать эти алгоритмы, добудьте диск . Подробности на последней странице книги..

К недостаткам этой книги относится то, что из-за ее энциклопедической природы пострадала читаемость книги. Я хотел написать единый справочник для тех, кто мог встретиться с каким-либо алгоритмом в академ и-ческой литературе или при использовании какого-то продукта, и заранее извиняюсь перед теми, кто разыскива­ет учебное пособие. Впервые все множество сделанного в криптографии собрано под одной обложкой . Несмот­ря на это, соображения объема заставили меня оставить многое за пределами этой книги, я включил те темы, которые мне показались важными, практическими или интересными. Если я не мог полностью охватить тему, я приводил ссылки на соответствующие работы и статьи .

Я сделал все, что мог, пытаясь выловить и исправить все ошибки в книге, но многие люди уверяли меня, что это все равно невозможно. Конечно, во втором издании ошибок меньше, чем в первом. Перечень ошибок можно получить у меня, он также периодически рассылается в телеконференции Usenet sci.crypt. Если кто-нибудь из читателей обнаружит ошибку, пожалуйста, пусть сообщит мне об этом. Каждому, кто первый обн а-ружит данную ошибку в книге, я бесплатно пошлю диск с исходным кодом .

Благодарности

Перечень людей, приложивших руку к созданию этой книги, может показаться бесконечным, но все они до с-тойны упоминания. Мне хотелось бы поблагодарить Дона Альвареса (Don Alvarez), Росса Андерсона (Ross An­derson), Дэйва Бейленсона (Dave Balenson), Карла Бармса (Karl Barms), Стива Белловина (Steve Bellovin), Дэна Бернстайна (Dan Bernstein), Эли Байем (EH Biham), Джоан Бояр (Joan Boyar), Карен Купер (Karen Cooper), Ви­та Диффи (Whit Diffie), Джоан Фейгенбаум (Joan Feigenbaum), Фила Кана (Phil Karn), Нила Коблица (Neal Koblitz), Ксуейа Лай (Xuejia Lai), Тома Леранта (Tom Leranth), Майка Марковица (Mike Markowitz), Ральфа Меркла (Ralph Merkle), Билла Паттена (Bill Patten), Питера Пирсона (Peter Pearson), Чарльза Пфлегера (Charles

Pfleeger), Кена Пиццини (Ken Pizzini), Барта Пренела (Bart Preneel), Марка Риордана (Mark Riordan), Иоахима Шурмана (Joachim Schurman) и Марка Шварца (Marc Schwartz) за чтение и редактирование всего первого из­дания или его частей; Марка Воклера (Marc Vauclair) за перевод первого издания на французский; Эйба Абра­хама (Abe Abraham), Росса Андерсона (Ross Anderson), Дэйва Бенисара (Dave Banisar), Стива Белловина (Steve Bellovin), Эли Байем (EH Biham), Мэтта Бишопа (Matt Bishop), Мэтта Блэйза (Matt Blaze), Гэри Картера (Gary Carter), Жана Комениша (Jan Comenisch), Клода Крепо (Claude Crepeau), Джоан Дэймон (Joan Daemon), Хорхе Давила (Jorge Davila), Эда Доусона (Ed Dawson), Вита Диффи (Whit Diffie), Карла Эллисона (Carl Ellison), Джоан Фейгенбаум (Joan Feigenbaum), Нильса Фергюсона (Niels Ferguson), Матта Франклина (Matt Franklin), Розарио Сеннаро (Rosario Cennaro), Дитера Колмана (Dieter Collmann), Марка Горески (Mark Goresky), Ричарда Грэйвмана (Richard Graveman), Стюарта Хабера (Stuart Haber), Джингмана Хе (Jingman He), Боба Хэйга (Bob Hague), Кеннета Айверсона (Kenneth Iversen), Маркуса Джекобсона (Markus Jakobsson), Берта Калиски (Burt Kaliski), Фила Кана (Phil Karn), Джона Келси (John Kelsey), Джона Кеннеди (John Kennedy), Ларса Кнудсена (Lars Knudsen), Пола Кочера (Paul Kocher), Джона Лэдвига (John Ladwig), Ксуейа Лай (Xuejia Lai), Аджена Ленстры (Arjen Lenstra), Пола Лейланда (Paul Leyland), Майка Марковица (Mike Markowitz), Джима Мэсси (Jim Massey), Брюса МакНейра (Brace McNair), Вильяма Хью Мюррея (William Hugh Murray), Роджера Нидхэ-ма (Roger Needham), Клифа Неймана (Clif Neuman), Кейсу Найберг (Kaisa Nyberg), Люка О'Коннора (Luke O'Connor), Питера Пирсона (Peter Pearson), Рене Перальта (Rene Peralta), Барта Пренела (Bart Preneel), Израиля Радай (Yisrael Radai), Мэтта Робшоу (Matt Robshaw), Майкла Роу (Michael Roe), Фила Рогуэя (Phil Rogaway), Эви Рубина (Avi Rubin), Пола Рубина (Paul Rubin), Селвина Рассела (Selwyn Russell), Казуе Сако (Kazue Sako), Махмуда Салмасизадеха (Mahmoud Salmasizadeh), Маркуса Стадлера (Markus Stadler), Дмитрия Титова (Dmitry Titov), Джимми Антона (Jimmy Upton), Марка Воклера (Marc Vauclair), Сержа Воденея (Serge Vaude-пау), Гидеона Ювала (Gideon Yuval), Глена Зорна (Glen Zorn) и многих безымянных правительственных слу­жащих за чтение и редактирование всего второго издания или его частей ; Лори Брауна (Lawrie Brown), Лизу Кэндл (Leisa Candle), Джоан Дэймон (Joan Daemon), Питера Гутмана (Peter Gutmann), Алана Инсли (Alan Insley), Криса Джонстона (Chris Johnston), Джона Келси (John Kelsey), Ксуейа Лай (Xuejia Lai), Билла Лейнин-гера (Bill Leininger), Майка Марковица (Mike Markowitz), Ричарда Аутбриджа (Richard Outerbridge), Питера Пирсона (Peter Pearson), Кена Пиццини (Ken Pizzini), Кэлма Пламба (Calm Plumb), RSA Data Security, Inc., Майкла Роу (Michael Roe), Майкла Вуда (Michael Wood) и Фила Циммермана (Phil Zimmermann) за предостав­ленные исходные коды; Пола МакНерланда (Paul MacNerland) за создание рисунков к первому издания; Карен Купер (Karen Cooper) за редактирование второго издания; Бота Фридмана (Both Friedman) за сверку второго издания; Кэрол Кеннеди (Кэрол Kennedy) за работу над предметным указателем для второго издания ; читателей sci.crypt и почтового списка Cypherpunks за комментирование идей, ответы на вопросы и поиск ошибок первого издания; Рэнди Сюсс (Randy Seuss) за предоставление доступа к Internet; Джеффа Дантермана (Jeff Duntemann) и Джона Эриксона (Jon Erickson) за то, что помогли мне начать; семью Insley (в произвольном порядке) за сти­муляцию, воодушевление, поддержку, беседы, дружбу и обеды; и AT&T Bell Labs, зажегшей меня и сделавшей возможным все это. Все эти люди помогли создать гораздо лучшую книгу, чем я бы смог создать в одиночку .

Брюс Шнайер

Оак Парк, Иллинойс

schneier@counterpane.com

Об авторе

Глава 1 Основные понятия

1.1 Терминология

Отправитель иполучатель

Предположим, что отправитель хочет послать сообщение получателю. Более того, этот отправитель хочет послать свое сообщение безопасно: он хочет быть уверен, что перехвативший это сообщение не сможет его пр о-честь.

Сообщения ишифрование

Само сообщение называется открытым текстом(иногда используется термин клер). Изменение вида сооб­щения так, чтобы спрятать его суть называется шифрованием.Шифрованное сообщение называется шифро-текстом.Процесс преобразования шифротекста в открытый текст называется дешифрированием.Эта после­довательность показана на Oth.

(Если вы хотите следовать стандарту ISO 7498-2, то в английских текстах используйте термины "enchipher" вместо " encrypt" ("зашифровывать") и "dechipher" вместо " decrypt" ("дешифровывать")).

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

Первоначальный

Открытый текст ___________ Шифротекст ______________ открытый текст

----------------- ^Шифрование------------------------- ^Дешифрирован^]------------------- ►

Рис. 1-1. Шифрование и дешифрирование

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

Обозначим шифротекст как С (от ciphertext). Это тоже двоичные данные, иногда того же размера, что и М, иногда больше. (Если шифрование сопровождается сжатием, С может быть меньше чем М. Однако, само шиф­рование не обеспечивает сжатие информации.) Функция шифрования Е действует на М, создавая С. Или, в ма­тематической записи:

Е(М) = С

В обратном процессе функция дешифрирования D действует на С, восстанавливая М:

D(C) = М

Поскольку смыслом шифрования и последующего дешифрирования сообщения является восстановление пе р-воначального открытого текста, должно выполняться следующее равенство :

D(E(M)) = М

Проверка подлинности, целостность инеотрицание авторства

Кроме обеспечения конфиденциальности криптография часто используется для других функций :

— Проверка подлинности.Получатель сообщения может проверить его источник, злоумышленник не сможет замаскироваться под кого-либо.

— Целостность. Получатель сообщения может проверить, не было ли сообщение изменено в процессе доставки, злоумышленник не сможет подменить правильное сообщение ложным.

— Неотрицание авторства. Отправитель не сможет ложно отрицать отправку сообщения.

Существуют жизненно важные требования к общению при помощи компьютеров, также как существуют ана-

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

Алгоритмы иключи

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

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

Что еще хуже, ограниченные алгоритмы не допускают качественного контроля или стандартизации. У ка ж-дой группы пользователей должен быть свой уникальный алгоритм. Такие группы не могут использовать от­крытые аппаратные или программные продукты - злоумышленник может купить такой же продукт и раскрыть алгоритм. Им приходится разрабатывать и реализовывать собственные алгоритмы. Если в группе нет хорошего криптографа, то как ее члены проверят, что они пользуются безопасным алгоритмом?

Несмотря на эти основные недостатки ограниченные алгоритмы необычайно популярны для приложений с низким уровнем безопасности. Пользователи либо не понимают проблем, связанных с безопасностью своих систем, либо не заботятся о них.

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

Е_К(М)=С

D_K(C)=M

При этом выполняется следующее равенство (см -1-й):

D_K(E_K(M))=M

Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи (см -2-й). То есть ключ шифрования, К,, отличается от соответствующего ключа дешифрирования, К₂. В этом случае:

ЕК/М)=С

DKi(C)=M

DKi(EK/M))=M

Криптосистемапредставляет собой алгоритм плюс все возможные открытые тексты, шифротексты и ключи . Ключ Ключ Открытый текст

Рис. 1-2. Шифрование и дешифрирование с ключом

Ключ Ключ

шифрования дешифрирования

Открытый текст

Шифротекст

^Шифрование------------------------- ^Дешифрирование]

Первоначальный открытый текст

Рис. 1-3. Шифрование и дешифрирование с двумя различными ключами

Симметричные алгоритмы

ЕК(М)=С

DK(C)=M

Алгоритмы с открытым ключом Алгоритмы с открытым ключом(называемые асимметричными алгоритмами) разработаны…

ЕК(М)=С

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

DK(C)=M

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

ЕК(М)=С

DK(C)=M

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

Криптоанализ - это наука получения открытого текста, не имея ключа . Успешно проведенный криптоанализ может раскрыть открытый текст или ключ. Он… вается компрометацией.) Попытка криптоанализа называется вскрытием.Основное предположение криптоанализа, впервые сфо р-мулированное в…

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

Я говорю "скорее всего", потому что существует вероятность новых прорывов в криптоанализе. С другой стороны, значимость большинства данных… Ларе Кнудсен (Lars Knudsen) разбил вскрытия алгоритмов по следующим… 1. Полное вскрытие.Криптоаналитик получил ключ, К, такой, что DK(C) = Р.

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

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

Перестановочные шифры

Криптоанализ этих шифров обсуждается в [587,1475]. Так как символы шифротекста те же, что и в откры­том тексте, частотный анализ шифротекста… Немецкий шифр ADFCVX, использованный в ходе Первой мировой войны, представлял… Хотя многие современные алгоритмы используют перестановку, с этим связана проблема использования большого объема…

Роторные машины

Роторная машина,включающая клавиатуру и набор роторов, реализует вариант шифра Вигенера. Каждый ротор представляет собой произвольное размещение… ОТКРЫТЫЙTeKCTiCOMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST IT'S EXPENSIVE. COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE

Рис. 1-4. Столбцовый перестановочный фильтр.

Например, в четырехроторной машине первый ротор может заменять "А" на " F", второй - "F" на "Y", третий - "Y" на "Е" и четвертый - "Е" на "С", "С" и будет конечным шифротекстом. Затем некоторые роторы смеща­ются, и в следующий раз подстановки будут другими.

Именно комбинация нескольких роторов и механизмов, движущих роторами, и обеспечивает безопасность машины. Так как роторы вращаются с различной скоростью, период для и-роторной машины равен 26^п. Неко­торые роторные машины также могут иметь различные положения для каждого ротора, что делает криптоан а-лиз еще более бессмысленным.

Самым известным роторным устройство является Энигма (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 представляет собой операцию "исключающее или": ^,Л' в языке С или g в математической нотации. Это обычная операция над битами:

0©0 = 0

0© 1 = 1

1 ©0 = 1

1 © 1 = 0

Также заметим, что:

а®а = 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!= '') {

if ((fi = fopen(argvl[2], "rb")) != NULL) {

if ((fo = fopen(argv[3], "wb")) != NULL) { while ((c = getc(fi)) != EOF) { if (!*cp) cp = argv[l]; c^A= *(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 + Т mod 26 = I

N + В mod 26 = Р

Е + F mod 26 = К

и т.д.

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

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

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), Шамира (Shamir) и Эдлмана (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³³) 1 из 4000000 (2²²) 1 из2⁶¹

1 из 59000 (2¹⁶) 1 из 6100 (2¹³) 1 из 88 (2⁷) 14000 (2¹⁴) лет 10⁹ (2³⁰) лет 10⁹ (2³⁰) лет 10¹⁰ (2³⁴) лет 10⁵¹ (2¹⁷⁰) 10⁵⁷ (2¹⁹⁰) 10⁶⁷ (2²²³) 10⁷⁷ (2²⁶⁵) 10⁸⁴ (2²⁸⁰) см ³

Если Вселенная конечна:

Полное время жизни вселенной

10¹¹ (2³⁷) лет 10¹⁸ (2⁶¹) секунд

 

Если Вселенная бесконечна:

Время до остывания легких звезд

Время до отрыва планет от звезд

Время до отрыва звезд от галактик

Время до разрушения орбит гравитационной радиацией

Время до разрушения черных дыр процессами Хокинга

Время до превращения материи в жидкость при нулевой температуре

Время до превращения материи в твердое тело

Время до превращения материи в черную дыру

10¹⁴ (2⁴⁷) лет

10¹⁵ (2⁵⁰) лет

10¹⁹ (2⁶⁴) лет

10²⁰ (2⁶⁷) лет

10⁶⁴ (2²¹³) лет

10⁶⁵ (2²¹⁶) лет

10¹⁰²⁶ лет

10¹⁰7⁶ лет

Часть 1 КРИПТОГРАФИЧЕСКИЕ ПРОТОКО-

ЛЫ

Глава 2

Элементы протоколов

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

Игроки

Для демонстрации работы протоколов я использую несколько игроков (см. 1-й). Первые двое - это Алиса и Боб. Они участвуют во всех двусторонних протоколах. Как правило, Алиса (Alice) начинает все протоколы, а Боб (Bob) отвечает. Если для протокола нужна третья или четвертая сторона, в игру вступают Кэрол (Ёубш) и Дэйв (Dave). Другие игроки играют специальные вспомогательные роли, они будут представлены по зже.

Протоколы с посредником

Посредник- это незаинтересованная третья сторона, которой доверено завершение протокола (см. 1-й (а)). Незаинтересованность означает, что у посредника нет заинтересованности в результате работы протокола и склонности к одной из сторон. "Доверено" означает, что все участники протокола принимают все, что скажет посредник за истину, все его действия - как правильные, и уверены в том, что посредник выполнит свою часть протокола. Посредники помогают реализовать работу протоколов взаимодействия недоверяющих друг другу сторон.

В реальном мире в качестве посредников часто выступают юристы . Например, Алиса продает незнакомому ей Бобу машину. Боб хочет заплатить чеком, но у Алисы нет способа проверить, действителен ли чек. Алиса хочет, чтобы расчет по чеку был произведен прежде, чем право собственности перейдет к Бобу . Боб, который верит Алисе не больше, чем она ему, не хочет передавать чек, не получив права собственности.

Табл. 2-1. Действующие лица

 

Алиса	Первый участник всех протоколов
Боб	Второй участник всех протоколов
Кэрол	Третий участник в протоколах с участием трех и четырех сторон
Дэйв	Четвертый участник в протоколах с участием трех и четырех сторон
Ева	Злоумышленник (eavesdropper)
Мэллори	Взломщик протоколов
Трент	Заслуживающий доверия посредник
Уолтер	Контролер, защищает Алису и Боба в ряде протоколов
Пегги	Свидетель
Виктор	Проверяет подлинность

Трент

 

 

Алиса

Боб

(а)протокол с посредником

Алиса

А

Боб

Трент

 

Доказател ьство Доказател ьство -'

после случившегося

(б) арбитражный протокол

Алиса

А

Боб

I (в) самодостаточный протокол

Рис. 2-1. Типы протоколов

Посредничество юриста устроит обоих. С его помощью Алиса и Боб могут выполнить следующий протокол, чтобы защитить себя от обмана:

(1) Алиса передает право собственности юристу.

(2) Боб передает чек юристу.

(3) Алиса депонирует чек.

(4) Дождавшись оплаты чека юрист передает право собственности Бобу. Если чек не оплачен в течение опр е-деленного времени, Алиса доказывает этот факт юристу, и тот возвращает право собственности Алисе.

В этом протоколе Алиса верит, что юрист не передаст Бобу право собственности до тех пор, пока чек не б у-дет оплачен, и вернет право собственности Алисе, если чек оплачен не будет. Боб верит, что юрист будет обла-дать правом собственности до тех пор, пока чек не будет оплачен, и передаст право собственности Бобу сразу же после оплаты чека. Юрист не заботится об оплате чека. Он в любом случае выполнит свою часть протокола, ведь ему заплатят в любом случае.

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

В качестве посредника может выступить и банк - для покупки машины :

(1) Боб заполняет чек и передает его в банк.

(2) Если на счету Боба достаточно денег для покрытия чека, банк заверяет чек и возвращает его Бобу.

(3) Алиса передает Бобу право собственности, а Боб передает Алисе заверенный чек.

(4) Алиса депонирует чек.

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

банановых республиках.

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

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

Этот идеал можно перенести на мир компьютеров, но с компьютерными посредниками существует ряд пр о-блем:

— Легко найти нейтральную третью сторону, которой можно доверять, если вы знаете посредника и можете лично увидеть его. Две стороны, относящиеся друг к другу с подозрением, с тем же подозрением отнесу т-ся и к безликому посреднику, затерянному где-то в сети.

— Компьютерная сеть должна обеспечить поддержку посредника. Занятость юристов общеизвестна, на кого в сети лягут дополнительные накладные расходы ?

— Существует задержка, присущая всем протоколам с посредником .

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

— Так как каждый в сети должен доверять посреднику, то посредник представляет собой слабое место сети при попытке ее взлома.

Несмотря на это посредничество все еще активно используется. В протоколах с использованием посредника эту роль будет играть Трент.

Арбитражные протоколы

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

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

Профессиональными арбитрами являются судьи. В отличие от нотариусов к судьям обращаются только при появлении разногласий. Алиса и Боб могут заключить контракт без участия судьи. Судья никогда не узнает о контракте, если одна из сторон не подаст на другую в суд . Протокол подписания контракта можно формализо-вать следующим образом:

Подпротокол без посредника (выполняется всегда):

(1) Алиса и Боб договариваются об условиях контракта.

(2) Алиса подписывает контракт.

(3) Боб подписывает контракт. Подпротокол с использованием арбитра (выполняется при наличии разногласий) :

(4) Алиса и Боб предстают перед судьей.

(5) Алиса предоставляет свои доказательства.

(6) Боб предоставляет свои доказательства.

(7) Судья принимает решение на основании доказательств.

Различие используемых в этой книге понятий посредника и арбитра состоит в том, что участие арбитра пр о-исходит не всегда. Стороны обращаются к судье только при разногласиях. Если разногласий нет, судья не н у-жен.

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

Самодостаточные протоколы

В лучшем мире любой протокол должен быть самодостаточным, но, к несчастью, не существует самодост а-точных протоколов для каждой ситуации.

Попытки вскрытия протоколов

Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр о-токола, могут "подслушивать" какую-то… В другом случае взломщик может попытаться изменить протокол для собственной… Пассивные взломщики стараются получить информацию об участниках протокола . Они собирают сообще-ния, переданные…

Коды проверки подлинности сообщения

верки подлинности данных (data authentication code, DAG), представляет собой однонаправленную хэш-функцию с добавлением секретного ключа (см. раздел… 2.5 Передача информации с использованием криптографии с открытыми клю­чами Взгляните на симметричный алгоритм как на сейф. Ключ является комбинацией. Знающий комбинацию ч е-ловек может открыть…

Смешанные криптосистемы

Прекрасные криптосистемы с открытым ключом, обсуждаемые в популярной и научной печати, тем не менее, не нашли соответствующего отклика среди… В реальном мире алгоритмы с открытыми ключами не заменяют симметричные… 1. Алгоритмы с открытыми ключами работают медленно. Симметричные алгоритмы по крайней мере в 1000 раз быстрее, чем…

Подпись документа с помощью симметричных криптосистем и посредника

Трент - это обладающий властью посредник, которому доверяют . Он может связываться и с Алисой, и с Бо­бом (и со всеми другими желающими подписывать… (1) Алиса шифрует свое сообщение Бобу ключом Кл и посылает его Тренту. … (2) Трент, зная ключ КА, расшифровывает сообщение.

Деревья цифровых подписей

Ральф Меркл предложил систему цифровых подписей, основанную на криптографии с секретным ключом, создающей бесконечное количество одноразовых подписей, используя древовидную структуру [1067,1068]. Ос­новной идеей этой схемы является поместить корень дерева в некий открытый файл , удостоверяя его таким об-

разом. Корень подписывает одно сообщение и удостоверяет подузлы дерева. Каждый из этих узлов подписывает одно сообщение и удостоверяет свои подузлы, и так далее.

Подпись документа с помощью криптографии с открытыми ключами

(1) Алиса шифрует документ своим закрытым ключом, таким образом подписывая его. (2) Алиса посылает подписанный документ Бобу. (3) Боб расшифровывает документ, используя открытый ключ Алисы, таким образом проверяя подпись.

Подпись документа и метки времени

Предположим, что Алиса послала Бобу подписанный чек на $100. Боб отнес чек в банк, который проверил подпись и перевел деньги с одного счета на… Поэтому в цифровые подписи часто включают метки времени . Дата и время…

Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций

(1) Алиса получает значение однонаправленной хэш-функции для документа. (2) Алиса шифрует это значение своим закрытым ключом, таким образом подписывая… (3) Алиса посылает Бобу документ и подписанное значение хэш-функции.

Алгоритмы и терминология

В общем случае я буду ссылаться на процессы подписи и проверки, не вдаваясь в подробности алгоритмов. Подпись сообщения с закрытым ключом К будет… SK(M) а проверка подписи с помощью соответствующего открытого ключа как :

Несколько подписей

С помощью однонаправленных реализовать несколько подписей просто : (1) Алиса подписывает значение хэш-функции документа. (2) Боб подписывает значение хэш-функции документа.

Невозможность отказаться от цифровой подписи

Метки времени могут снизить эффект такого мошенничества, но Алиса всегда может заявить, что ее ключ был скомпрометирован раньше. Если Алиса… Хотя с подобным злоупотреблением ничего нельзя сделать, можно предпринять… (1) Алиса подписывает сообщение.

Использование цифровых подписей

Метод условного удостоверения подлинности может решить первую проблему, но только цифровые подписи могут решить обе проблемы. Сторона, на территории… 2.7 Цифровые подписи и шифрование Объединив цифровые подписи и криптографию с открытыми ключами, мы разрабатываем протокол, комб и-нирующий безопасность…

Обнаружение вскрытия, основанного на возвращении сообщения

(1) Алиса подписывает сообщение. (2) Алиса шифрует подписанное сообщение открытым ключом Боба (используя… (3) Боб расшифровывает сообщение с помощью своего закрытого ключа

Вскрытия криптографии с открытыми ключами

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

Генерация случайных и псевдослучайных последовательностей

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

Псевдослучайные последовательности

1. Он выглядит случайно. Это означает, что он проходит все тесты на случайность, которые нам удалось найти. (Начните с приведенных в [863].) Множество усилий было затрачено на создание хороших псевдослучайных… Проблема именно в этих таинственных корреляциях и странных результатах . Каждый генератор псевдослу­чайных…

Криптографически безопасные псевдослучайные последовательности

2. Она непредсказуема. Должно быть очень трудно (с точки зрения применения вычислительных мо щ- ностей) предсказать, каким будет следующий случайный… Криптографически безопасные псевдослучайные последовательности не должны… Как и любой криптографический алгоритм, генераторы криптографически безопасных псевдослучайных п о-следовательностей…

Настоящие случайные последовательности

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

Глава 3

Основные протоколы

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

Обмен ключами с помощью симметричной криптографии

(1) Алиса обращается к Тренту и запрашивает сеансовый ключ для связи с Бобом. (2) Трент генерирует случайный сеансовый ключ. Он зашифровывает две копии… (3) Алиса расшифровывает свою копию сеансового ключа.

Обмен ключами, используя криптографию с открытыми ключами

(1) Алиса получает открытый ключ Боба из KDC. (2) Алиса генерирует случайный сеансовый ключ, зашифровывает его открытым… (3) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа.

Обмен ключами с помощью цифровых подписей

Мэллори сталкивается с серьезными проблемами. Он не может выдать себя за Алису или Боба, ведь он не знает их закрытых ключей. Он не может подменить… Трент выступает участником этого протокола, но риск компрометации KDC меньше,… Мэллори может предпринять такое вскрытие. Используя закрытый ключ Трента, он может создать поддел ь-ные подписанные…

Передача ключей и сообщений

(1) Алиса генерирует случайный сеансовый ключ, К, и зашифровывает М этим ключом. ЕК(М) (2) Алиса получает открытый ключ Боба из базы данных. (3) Алиса шифрует К открытым ключом Боба. ЕВ(К)

Широковещательная рассылка ключей и сообщений

(1) Алиса генерирует случайный сеансовый ключ, К, и зашифровывает М этим ключом. ЕК(М) (2) Алиса получает из базы данных открытые ключи Боба, Кэрол и Дэйва. (3) Алиса шифрует К открытыми ключами Боба, Кэрол и Дэйва.

Удостоверение подлинности с помощью однонаправленных функций

(1) Алиса посылает главному компьютеру свой пароль. (2) Главный компьютер вычисляет однонаправленную функцию пароля. (3) Главный компьютер сравнивает полученное значение с хранящимся.

SKEY

SKEY - это программа удостоверения подлинности, обеспечивающая безопасность с помощью однонапра в-ленной функции. Это легко объяснить.

Регистрируясь в системе, Алиса задает случайное число , R. Компьютер вычисляет f(R), f(f(R)), f(f(f(R))), и так далее, около сотни раз. Обозначим эти значения как х,, х₂, х₃, ..., х_т. Компьютер печатает список этих чисел, и Алиса прячет его в безопасное место. Компьютер также открытым текстом ставит в базе данных подключения к системе в соответствие Алисе число х_т.

Подключаясь впервые, Алиса вводит свое имя и х_т. Компьютер рассчитывает f(x_m) и сравнивает его с х_т, если значения совпадают, права Алисы подтверждаются . Затем компьютер заменяет в базе данных х_т на х_т. Алиса вычеркивает х_т из своего списка.

Алиса, при каждом подключении к системе, вводит последнее невычеркнутое число из своего списка: х,. Компьютер рассчитывает/^ и сравнивает его с х₁₊₁, хранившемся в базе данных. Так как каждый номер ис­пользуется только один раз, Ева не сможет добыть никакой полезной информации . Аналогично, база данных бесполезна и для взломщика. Конечно же, как только список Алисы исчерпается ей придется перерегистрир о-ваться в системе.

Удостоверение подлинности с помощью криптографии с открытыми ключами

Криптография с открытыми ключами может решить эту проблему . Главный компьютер хранит файл откры­тых ключей всех пользователей, а все пользователи… (1) Главный компьютер посылает Алисе случайную строку. (2) Алиса шифрует эту строку своим закрытым ключом и посылает ее обратно главному компьютеру вместе со своим именем. …

SKID

SKID2 и SKID3 - это симметричные криптографические протоколы идентификации, разработанные для пр о-екта RACE RIPE [1305] (см. раздел 25.7). Они используют MAC (см. раздел 2.4) для обеспечения безопасности и предполагают, что Алиса и Боб используют общий секретный ключ, К. SKID2 позволяет Бобу доказать свою подлинность Алисе. Вот этот протокол:

(1) Алиса выбирает случайное число, R_A. (Документами RIPE определяется 64-битовое число). Она посылает это число Бобу.

(2) Боб выбирает случайное число, R_B. (Документами RIPE определяется 64-битовое число). Он посылает Алисе.

R_B, H_K(R_A, R_B, В)

Н_к-это MAC. (В документах RIPE предлагается функция RIPE-MAC, см. раздел 18.4.) В - это имя Боба.

(3) Алиса рассчитывает H_K(R_A, R_B, В) и сравнивает результат со значением, полученным от Боба. Если р е-
зультаты совпадают, Алиса убеждается в том, что она соединилась именно с Бобом.

SKID3 обеспечивает совместную проверку подлинности Алисой и Бобом . Этапы (1) - (3) совпадают с прото­колом SKID2, а затем выполняются следующие действия:

(4) Алиса посылает Бобу:

H_k(Rb, A) А - это имя Алисы.

(5) Боб рассчитывает H_K(R_B, А) и сравнивает результат со значением, полученным от Алисы. Если результаты
совпадают, Боб убеждается в том, что она соединилась именно с Алисой.

Этот протокол неустойчив к вскрытию "человек-в-середине". В общем случае, вскрытие "человек-в-середине" может угрожать любому протоколу, в который не входит какой-нибудь секрет.

Удостоверение подлинности сообщений

Некоторую проверку подлинности предоставляют и симметричные алгоритмы . Когда Боб получает сообще­ние от Алисы, шифрованное их общим ключом, он… Если сообщение не шифровано, Алиса может также использовать MAC. Это также… 3.3 Удостоверение подлинности и обмен ключами

Табл. 3-1. Символы, используемые в протоколах удостоверения подлинности и обмена ключами

1 Имя Алисы

В Имя Боба

Е_А Шифрование ключом, выделенном Трентом Алисе

Е_в Шифрование ключом, выделенном Трентом Бобу

/ Порядковый номер

К Случайное сеансовое число

L Время жизни

Та, Т_в Метки времени

R_A, R_B Случайные числа, выбранные Алисой и Бобом, соответственно

Лягушка с широким ртом

ключ: (1) Алиса объединяет метку времени, имя Боба и случайный сеансовый ключ, затем… А, ЕА(ТА, В, К)

Otway-Rees

(1) Алиса создает сообщение, состоящее из порядкового номера, ее имени, имени Боба и случайного числа. Сообщение шифруется ключом, общим для Алисы и… /, А, В, EA(RA, I, А, В) (2) Боб создает сообщение, состоящее из нового случайного числа, порядкового номера, имени Алисы и им е- ни Боба.…

Другие протоколы

В литературе описано множество протоколов. Протоколы Х.509 рассматриваются в разделе 24.9, Кгур-toKnight - в разделе 24.6, а Шифрованный обмен ключами (Encrypted Key Exchange) - в разделе 22.5.

Другим новым протоколом с открытыми ключами является Kuperee [694]. Ведется работа на протоколами, использующими маяки- заслуживающие доверия узлы сети, которые непрерывно и широковещательно пер е-дают достоверные метки времени [783].

Выводы

Из приведенных протоколов, как из тех, которые вскрываются, так и из надежных, можно извлечь ряд ва ж-ных уроков:

— Многие протоколы терпят неудачу, так как их разработчики пытались быть слишком умными. Они опт и-мизировали протоколы, убирая важные элементы - имена, случайные числа и т.п. - и пытаясь сделать протоколы как можно более прозрачными [43, 44].

— Оптимизация - эта манящая ловушка - сильно зависит от сделанных предположений. Пример: наличие достоверного времени позволяет вам реализовать многие вещи, невозможные в проти вном случае.

— Выбираемый протокол зависит от архитектуры используемых средств связи. Хотите ли вы минимизир о-вать размер сообщений или их количество? Могут ли сторона взаимодействовать каждый с каждым или круг их общения будет ограничен?

Именно подобные вопросы и привели к созданию формальных методов анализа протоколов .

3.4 Формальный анализ протоколов проверки подлинности и обмена ключами

Проблема выделения безопасного сеансового ключа для пары компьютеров (или людей) в сети настолько фундаментальна, что стала причиной многих исследований . Некоторые исследования заключались в разработке протоколов, подобных рассматриваемым в разделах 3.1, 3.2 и 3.3. Это, в свою очередь, привело к появлению более важной и интересной задачи: формальному анализу протоколов проверки подлинности и обмена ключами. Иногда прорехи в протоколах, кажущихся вполне надежными, обнаруживались спустя много лет п о-сле их разработки, и разработчикам потребовались средства, позволяющие сразу же проверять безопасность протокола. Хотя большая часть этого инструментария применима и к более общим криптографическим прот о-колам, особое внимание уделялось проверке подлинности и обмену ключами . Существует четыре основных подхода к анализу криптографических протоколов [1045]:

1. Моделирование и проверка работы протокола с использованием языков описания и средств проверки, не разработанных специально для анализа криптографических протоколов.

2. Создание экспертных систем, позволяющих конструктору протокола разрабатывать и исследовать различные сценарии.

3. Выработка требований к семейству протоколов, используя некую логику для анализа понятий "знание" и "доверие".

4. Разработка формальных методов, основанных на записи свойств криптографических систем в алге б-раическом виде.

Полное описание этих четырех подходов и связанных с ними исследований выходит за рамки данной книги. Хорошее введение в эту тему дано в [1047, 1355], я же собираюсь коснуться только основных вопросов.

Первый из подходов пытается доказать правильность протокола, рассматривая его как обычную компьюте р-ную программу. Ряд исследователей представляют протокол как конечный автомат [1449, 1565], другие исполь­зуют расширения методов исчисления предиката первого порядка [822], а третьи для анализа протоколов ис­пользуют языки описания [1566]. Однако, доказательство правильности отнюдь не является доказательством безопасности, и этот подход потерпел неудачу при анализе многих "дырявых" протоколов . И хотя его примене­ние поначалу широко изучалось, с ростом популярности третьего из подходов работы в этой области были п е-реориентированы.

Во втором подходе для определения того, может ли протокол перейти в нежелательное состояние (например, потеря ключа), используются экспертные системы. Хотя этот подход дает лучшие результаты при поиске "дыр", он не гарантирует безопасности и не предоставляет методик разработки вскрытий . Он хорош для проверки того, содержит ли протокол конкретную "дыру", но вряд ли способен обнаружить неизвестные "дыры" в протоколе . Примеры такого подхода можно найти в [987,1521], а в [1092] обсуждается экспертная система, разработанная армией США и названная Следователем (Interrogator).

Третий подход гораздо популярнее. Он был впервые введен Майклом Бэрроузом ( Michael Burrows), Марти­ном Абэди (Martin Abadi) и Роджером Неедхэмом. Они разработали формальную логическую модель для ана­лиза знания и доверия, названную БАН-логикой[283, 284]. БАН-логика является наиболее широко распро­странена при анализе протоколов проверки подлинности. Она рассматривает подлинность как функцию от ц е-лостности и новизны, используя логические правила для отслеживания состояния этих атрибутов на протяжении всего протокола. Хотя были предложены различные варианты и расширения, большинство разработчиков пр о-токолов до сих пор обращаются к оригинальной работе.

БАН-логика не предоставляет доказательство безопасности, она может только рассуждать о проверке под­линности. Она является простой, прямолинейной логикой, легкой в применении и полезной при поиске "дыр" . Вот некоторые предложения БАН-логики:

Алиса считает X. (Алиса действует, как если бы X являлось истиной.)

Алиса видит X. (Кто-то послал сообщение, содержащее X, Алисе, которая может прочитать и снова передать X - возмож­но после дешифрирования.)

Алиса сказала X. (В некоторый момент времени Алиса послала сообщение, которое содержит предложение X. Не извест­но, как давно было послано сообщение, и было ли оно послано в течении текущего выполнения протокола . Известно, что Алиса считала X, когда говорила X.)

X ново. (X никогда не было послано в сообщении до текущего выполнения протокола .)

И так далее. БАН-логика также предоставляет правила для рассуждения о доверии протоколу . Для доказа­тельства чего-либо в протоколе или для ответа на какие-то вопросы к логическим предложениям о протоколе можно применить эти правила. Например, одним из правил является правило о значении сообщения :

ЕСЛИ Алиса считает, что у Алисы и Боба общий секретный ключ, К, и Алиса видит X, шифрованное К, и Алиса не шиф­ровала X с помощью К, ТО Алиса считает, что Боб сказал X.

Другим является правило подтверждения метки времени :

ЕСЛИ Алиса считает, что X могло быть сказано только недавно, и, что Боб X когда-то сказал X, ТО Алиса считает, что Боб считает X

БАН-анализ делится на четыре этапа:

(1) Преобразуйте протокол к идеальной форме, используя описанные выше предложения.

(2) Добавьте все предположения о начальном состоянии протокола.

(3) Присоедините логические формулы к предложениям, получая утверждения о состоянии системы после каждого предложения.

(4) Примените логические постулаты к утверждениям и предположениям, чтобы раскрыть состояние доверия участников протокола.

Авторы БАН-логики "рассматривают идеализированные протоколы как более ясные и полные описания, чем традиционные, найденные в литературе..." [283, 284]. Другие исследователи не так оптимистичны и подвергают это действие критике, так как при этом реальный протокол может быть искажен [1161, 1612]. Дальнейшие спо­ры отражены в [221, 1557]. Ряд критиков пытается показать, что БАН-логика может и получить очевидно н е-правильные характеристики протоколов [1161] - см. контрдоводы в [285, 1509] - и что БАН-логика занимается только доверием, а не безопасностью [1509]. Подробное обсуждение приведено в [1488, 706, 1002].

Несмотря на эту критику БАН-логика достигла определенных успехов . Ей удалось обнаружить "дыры" в не­скольких протоколах, включая Needham-Schroeder и раннюю черновую версию протокола CCITT X.509 [303]. Она обнаружила избыточность во многих протоколах, включая Yahalom, Needham-Schroeder и Kerberos. Во многих опубликованных работах БАН-логика используется для заявления претензии о безопасности описыва е-мых протоколов [40, 1162, 73].

Были опубликованы и другие логические системы, некоторые из них разрабатывались как расширения БАН-логики [645, 586, 1556, 828], а другие основывались на БАН-логике для исправления ощутимых слабостей [1488, 1002]. Из них наиболее успешной оказалась CNY [645], хотя у нее есть ряд изъянов [40]. В [292,474] к БАН-логике с переменным успехом были добавлены вероятностные доверия . Другие формальные логики опи­саны в [156, 798,288]. [1514] пытается объединить черты нескольких логик. А в [1124, 1511] представлены ло­гики, в которых доверия изменяются со временем.

Четвертый подход к анализу криптографических протоколов предлагает моделировать протокол как алге б-раическую систему, выразить состояние знания участников о протоколе и затем проанализировать достиж и-

мость определенных состояний. Этот подход пока не привлек столько внимания, как формальная логика, но состояние дел меняется. Он впервые был использован Майклом Мерриттом [1076], который показал, что для анализа криптографических протоколов можно использовать алгебраическую модель . Другие подходы рассмот­рены в [473, 1508, 1530, 1531, 1532, 1510, 1612].

Анализатор протоколов Исследовательской лаборатория ВМС (Navy Research Laboratory, NRL), возможно, является наиболее успешным применением этих методов [1512, 823, 1046, 1513]. Он был использован для поис­ка как новых, так и известных "дыр" во множестве протоколов [1044, 1045, 1047]. Анализатор протоколов оп­ределяет следующие действия:

— Принять (Боб, Алиса, М, N). (Боб принимает сообщение М как пришедшее от Алисы в течение локально­го раунда Боба N.)

— Узнать (Ева, М). (Ева узнает М.)

— Послать (Алиса, Боб, Q, М). (Алиса посылает М Бобу в ответ на запрос, Q.)

— Запросить (Боб, Алиса, Q, N). (Боб посылает Q Алисе в течение локального раунда Боба N.)
Используя эти действия, можно задать требования. Например:

— Если Боб принял сообщение М от Алисы в какой-то прошедший момент времени, то Ева не знает М в ка­кой-то прошедший момент времени.

— Если Боб принял сообщение М от Алисы в течение локального раунда Боба N, то Алиса послала М Бобу в ответ на запрос Боба в локальном раунде Боба N.

Для анализа Анализатором протоколов NRL исследуемый протокол должен быть описан с помощью прив е-денных конструкций. Затем выполняются четыре фазы анализа: определение правил перехода для честных уча­стников, описание операций, возможных и для полностью честных, и для нечестных участников , описание базо­вых блоков протокола и описание правил преобразования. Смысл всего этого в том, чтобы показать, что дан­ный протокол удовлетворяет необходимым требованиями. Использование инструментов, подобных Анализато­ру протоколов NRL, в итоге могло бы привести к созданию протокола, который был бы обоснованно признан безопасным.

Хотя формальные методы в основном применяются к уже существующим протоколам, сегодня есть тенде н-ция использовать их и при проектировании протоколов . Ряд предварительных шагов в этом направлении сделан в [711]. Это же пытается сделать и анализатор протоколов NRL [1512, 222, 1513].

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

3.5 Криптография с несколькими открытыми ключами

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

Эта концепция была обобщены Конном Бойдом (Conn Boyd) [217]. Представьте себе вариант криптографии с открытыми ключами, использующий три ключа: К_А, К_в и К_с, распределение которых показано в 1-й.

Алиса может зашифровать сообщение ключом К_А так, что Эллен может расшифровать его, используя ключи К_в и Кс. То же самое, сговорившись, могут сделать Боб и Кэрол. Боб может зашифровать сообщение так, что Фрэнк сможет прочесть его а Кэрол сможет зашифровать сообщение так, что его сможет прочесть Дэйв. Дэйв может зашифровать сообщение ключом К_А так, что Эллен сможет прочесть его, ключом К_в так, что его сможет прочесть Фрэнк, или обоими ключами, К_А и К_в, так, что сообщение сможет прочесть Кэрол. Аналогично, Эллен может зашифровать сообщение так, что Алиса, или Дэйв, или Фрэнк сможет прочесть его. Все возможные ко м-бинации показаны в , других не существует.

Табл. 3-2. Распределение ключей в трехключевой системе.

Алиса Т_А

Боб К_в

Кэрол Т_с

Дэйв К_л и К_в

Эллен К_в и Кс

Франк К_с и К_л

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

Широковещательная передача сообщения

Криптография с несколькими ключами позволяет решить эту задачу намного проще. Мы будем использовать трех агентов: Алису, Боба и Кэрол. Вы выдадите… Для трех агентов это не слишком впечатляет, но для 100 преимущество достаточно… ключей (исключены случаи сообщения всем агентам и никому из них). Для схемы, использующий криптогра­фию с несколькими…

Табл. 3-3. Шифрование сообщения в трехключевой системе.

Шифруется ключами Должно быть расшифровано ключами

Т_А К_виКс

К_в К_А и К_с

К_с К_А и К_в

К_А и К_в К_с

К_А и К_с К_в

К_в и Кс К_А

3.6 Разделение секрета

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

Предлагаемая схема называется разделением секрета.Есть способы взять сообщение и разделить его на части [551]. Каждая часть сама по себе ничего не значит, но сложите их - и вы получите сообщение . Если это

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

По простейшей схеме сообщение делится между двумя людьми. Вот протокол, используя который Трент д е-лит сообщение между Алисой и Бобом:

(1) Трент генерирует строку случайных битов, R, такой же длины, что и сообщение, М.

(2) Трент выполняет "исключающее или" (XOR) над Ми 7?, создавая S. R®M = S

(3) Трент передает Алисе R, а Бобу - S.

Чтобы получить сообщение, Алисе и Бобу нужно выполнить единственное действие:

(4) Алиса и Боб выполняют операцию над имеющимися у них частями, восстанавливая сообщение.

R®S = M

Этот метод при правильном выполнении абсолютно безопасен. Каждая часть в отдельности абсолютно бе с-смысленна. Что существенно, Трент шифрует сообщение одноразовым блокнотом и дает шифротекст одному человеку, а блокнот - другому. Одноразовые блокноты, обладающие абсолютной безопасностью, обсуждаются в разделе 1.5. Никакие вычислительные средства не смогут восстановить сообщение только по одной его части .

Эту схему легко расширить на большее число людей. Чтобы разделить сообщение между более чем двумя людьми, выполните операцию XOR с большим числом строк случайных битов. В следующем примере Трент делит сообщение на четыре части:

(1) Трент генерирует три строки случайных битов, R, ShT, такой же длины, что и сообщение, М.

(2) Трент выполняет "исключающее или" (XOR) над Ми созданными тремя строками, создавая U. M®R®S®T = U

(3) Трент передает Алисе R, Бобу - S, Кэрол - Т, а Дэйву - U.
Вместе Алиса, Боб, Кэрол и Дэйв могут восстановить сообщение :

(4) Алиса, Боб, Кэрол и Дэйв собираются вместе и вычисляют:

R®S®T®U = M

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

Однако, одна проблема у этого протокола существует. Если любая из частей будет потеряна, а Трента не б у-дет поблизости, пропадет и все сообщение. Если Кэрол, обладая частью рецепта соуса, перейдет работать к ко н-куренту, оставив свою часть секрета у себя, значит, остальным не повезло. Она не сможет восстановить рецепт, но не смогут, собравшись, и Алиса, Боб и Дэйв. Ее часть также критична для восстановления сообщения, как и любая другая. Все, что известно Алисе, Бобу и Дэйву - это длина сообщения, и ничего больше . Это истинно, так как yR, S, T, UuMодинаковая длина, следовательно, каждому из участников известна длина М. Помните, со­общение М делится не в обычном смысле этого слова, а подвергается операции XOR со случайными величина­ми.

3.7 Совместное использование секрета

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

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

Можно сделать еще сложнее. Пусть только генерал у и паре полковников разрешено запустить ракету, но е с-ли генерал занят игрой в гольф, то запустить ракету имеют право только пять полковников . Сделайте контроль­ное устройство с пятью ключами. Выдайте генералу три ключа, а полковникам по одному. Генерал вместе с двумя полковниками или пять полковников смогут запустить ракету. Однако ни генерал в одиночку, ни четыре полковника не смогут этого сделать.

Более сложная схема совместного использования, называемая пороговой схемой,может решить и эти зада­чи, и более сложные - математически. На ее простейшем уровне вы можете взять любое сообщение (секретный рецепт, коды запуска, ваш список для прачечной и т.п.) и разделить его на п частей, называемых тенямиили долями, так, что по любым т из них можно восстановить сообщение. Более точно, это называется (т,п)-пороговой схемой.

Используя (3,4)-пороговую схему, Трент может разделить свой секретный рецепт между Алисой, Бобом, К э-рол и Дэйвом так, что любые трое из них могут сложить свои тени вместе и восстановить сообщение. Если Кэ­рол в отпуске, то Алиса, Боб и Дэйв смогут восстановить сообщение. Если Боб попал под автобус, то сообщение смогут восстановить Алиса, Кэрол и Дэйв. Но если Боб попал под автобус, а Кэрол в отпуске, то Алиса и Дэйв самостоятельно не смогут восстановить сообщение.

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

Эта идея была независимо выдвинута Ади Шамиром [1414] и Джорджем Блэкли (George Blakley) [182] и интенсивно была изучена Гусом Симмонсом (Gus Simmons) [1466]. Множество различных алгоритмов обсуж­дается в разделе 23.2.

Совместное использование с мошенниками

Сценарий 2: Полковники Алиса и Боб сидят в бункере вместе с Мэллори. Мэллори ложно выдает себя за полковника. От президента приходит то же самое… Сценарий 3: Полковники Алиса, Боб и Кэрол сидят в бункере вместе с Мэллори,…

Совместное использование секрета без Трента

Банк хочет, чтобы его подвал могли открыть трое из пяти офицеров, введя свои ключи . Это выглядит как типичная (3,5)-пороговая схема, но с одной тонкостью. Никто не знает секрета целиком. Трента, которые делит секрет на пять частей, нет. Существуют протоколы, используя которые пять офицеров могут создать секрет и поделить его на части так, что никто из офицеров не узнает секрета, пока он не будет восстановлен . В этой кни­ге я не рассматриваю эти протоколы, подробности см. в [756].

Совместное использование секрета без раскрытия долей

документа. После и-ой частичной подписи документ оказывается подписан совместно используемым закрытым ключом, а ни один из участников не может…

Подтверждаемое совместное использование секрета

Трент передает Алисе, Бобу, Кэрол и Дэйву часть секрета (или, по крайней мере, заявляет, что он это делает). Единственный способ убедиться, что их части правильны - это попытаться восстановить секрет . Может быть Трент послал Бобу поддельную часть, или часть Боба случайно испортилась при передаче по линиям связи. Подтверждаемое совместное использование секрета позволяет каждому из участников лично убедиться, что их часть правильна, без необходимости восстанавливать секрет [558, 1235].

Схемы совместного использования секрета с мерами предохранения

Математика достаточно сложна, но основная идея в том, что каждый получает две части : часть "да" и часть "нет". Когда приходит… Конечно же, ничего не мешает достаточному числу людей "да" отойти в…

Совместное использование секрета с вычеркиванием из списка

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

Глава 4

Промежуточные протоколы

Во многих ситуациях людям нужно убедиться, что определенный документ уже существовал в определенный момент времени. Примером является спор об… В цифровом мире все гораздо сложнее. Нет способов обнаружить признаки подделки… Этой проблемой задались Стюарт Хабер (Stuart Haber) и В. Скотт Сторнетта (W. Scott Stornetta) из Bellcore [682, 683,…

Решение с посредником

(1) Алиса передает копию документа Тренту. (2) Трент записывает время и дату получения документа, оставляя у себя копию… Теперь, если кто-нибудь усомнится в заявленном Алисой времени создания документа, то Алисе просто нужно обратиться к…

Улучшенное решение с посредником

(1) Алиса вычисляет значение однонаправленной хэш-функции для документа. (2) Алиса передает это значение Тренту. (3) Трент добавляет время и дату получения этого значения и затем подписывает результат цифровой подп и-сью.

Протокол связи

Если А - это имя Алисы, Нп - значение хэш-функции, для которого Алиса хочет зафиксировать время, а Тп_, -предыдущая метка времени, то протокол имеет… (1) Алиса посылает Тренту Н„ и А. (2) Трент посылает Алисе обратно: Т„ =SK(n,A,H„,Tn,In_hHn_i,T„.,,Ln)

Распределенный протокол

Развивая эту идею, следующий протокол позволяет обойтись и без Трента: (1) Используя в качестве входа Н„, Алиса генерирует последовательность… V,, V2, V3>. . . Vk

Дальнейшая работа

Эти протоколы меток времени запатентованы [684, 685, 686]. Патенты принадлежат дочерней компании Bellcore, названной Surety Technologies, которая… 4.2 Подсознательный канал Алиса и Боб были арестованы и отправлены в тюрьму, он - в мужскую, а она - в женскую . Уолтер, надзира­тель, разрешает…

Применения подсознательного канала

Используя подсознательный канал, Алиса может, даже если ей угрожают, безопасно подписать документ . Подписывая документ, она может вставить…

Подписи, свободные от подсознательного канала

4.3 Неотрицаемые цифровые подписи Обычные цифровые подписи могут быть точно скопированы. Иногда это свойство… ца, подписавшего сообщение.

Групповые подписи с надежным посредником

(1) Трент создает большую кучу пар открытый ключ/закрытый ключ и выдает каждому члену группы инд и-видуальный список уникальных закрытых ключей.… (2) Трент публикует главный список всех открытых ключей для группы в… (3) Когда член группы хочет подписать документ, он случайным образом выбирает ключ из своего списка.

Подписи с обнаружением подделки

Подписи с обнаружением подделки,введенные Биржитом Пфицманом (Birgit Pfitzmann) и Майклом Уэйднером (Michael Waidner) [1240] предотвращают подобное… Основная идея, стоящая за подписями с обнаружением подделки, состоит в том,… Ева хочет взломать закрытый ключ Алисы. (Ева также сможет быть Алисой, вычислив для себя второй з а-крытый ключ.) Она…

Вручение бита с помощью однонаправленных функций

Этот протокол использует однонаправленные функции:

(1) Алиса создает две случайных строки битов, Rj и R₂.

Ri, Ri

(2) Алиса создает сообщение, состоящее из ее случайных строк и бита, который она хочет вручить (в действ и-
тельности, это может быть и несколько битов).

(Ru R₂, b)

(3) Алиса вычисляет однонаправленную функцию для сообщения и посылает результат вместе с одной из
случайных строк Бобу.

H(R,, R₂, b), R,

Это сообщение Алисы является доказательством вручения. Использование однонаправленной функции на этапе (3) мешает Бобу, инвертируя функцию, определить бит.

Когда для Алисы придет время раскрыть свой бит, протокол продолжается :

(4) Алиса отправляет Бобу первоначальное сообщение. (Ri, R₂, b)

(5) Боб вычисляет однонаправленную функцию для сообщения и сравнивает его и R, со значением однона­правленной функции и случайной строкой, полученными на этапе (3). Если они совпадают, то бит прав и-лен.

Преимущество этого протокола перед предыдущим в том, что Бобу не нужно посылать никаких сообщений . Алиса посылает Бобу одно сообщение для вручения бита, а другое - для его раскрытия .

Не нужна и случайная строка Боба, так как результат Алисиного вручения - это сообщение, обработанное однонаправленной функцией. Алиса не может смошенничать и подобрать другое сообщение (R,, R₂, V), для ко­торого H(Rj, R₂, b')= H(Rj, R₂, b). Посылая Бобу R,, она вручает значение Ъ. Если Алиса не сохранит в секрете R₂, то Боб получит возможность вычислить H(R,, R₂, b') и H(R,, R₂, b), получая возможность увидеть, что же он получил от Алисы.

Вручение бита с помощью генератора псевдослучайной последовательности

(1) Боб создает строку случайных битов и посылает ее Алисе. Rb (2) Алиса создает стартовую последовательность для генератора псевдослучайных битов. Затем для каждого бита в строке…

Blob-объекты

1. Алиса может вручить blob-объекты. Вручая blob-объект, она вручает бит. 2. Алиса может открыть любой blob-объект, который она вручила. Когда она… 3. Боб не может знать, каким образом Алиса может открыть blob-объект, который она вручила. Это ос­тается…

Бросок монеты с помощью однонаправленных функций

(2) Алиса посылает у Бобу. (3) Боб предполагает, что х четно или нечетно, и посылает свое предположение… (4) Если предположение Боба правильно, результатом броска является "орел", если неправильно - то…

Бросок монеты с помощью криптографии с открытыми ключами

DKi(EK2(EKi(M))) = EKi(M) В общем случае это свойство не выполняется для симметричных алгоритмов, но… (1) И Алиса, и Боб создают пары открытый ключ/закрытый ключ.

Бросок монеты в колодец

Генерация ключей с помощью броска монеты

4.11 Мысленный покер Протокол, аналогичный протоколу броска монеты с помощью открытых ключей,…

Мысленный покер с тремя игроками

(1) Алиса, Боб и и Кэрол создают пары открытый ключ/закрытый ключ. (2) Алиса создает 52 сообщения, по одному для каждой карты колоды. Эти… Еа(М„)

Вскрытия мысленного покера

Шафи Голдвассер (Shan Goldwasser) и Сильвия Микали (Silvia Micali) [624] разработали протокол умствен­ного покера для двух игроков, который решает… Результаты других исследований протоколов игры в покер можно найти в [573,…

Анонимное распределение ключей

Рассмотрим проблему распределения ключей. Если предположить, что люди не могут сами генерировать свои ключи(ключи должны иметь определенную форму,… (1) Алиса создает пару открытый ключ/закрытый ключ. В этом протоколе она… (2) KDC генерирует непрерывный поток ключей.

Политика условного вручения ключей

Ну, на самом деле никакого. Пользователь не получает от условного вручения ключей ничего такого, чего он и сам не смог бы обеспечить. Он и сам может создать резервную копию ключей,… Недостатки условного вручения ключей весьма ощутимы. Пользователю приходится верить в безопасность действия…

Глава 5

Развитые протоколы

А вот другая история: Алиса: "Я знаю пароль компьютера Федеральной Резервной Системы,… Боб: "Нет, ты не знаешь".

Рис. 5-1. Пещера нулевого знания

Пегги знает секрет пещеры. Она хочет доказать свое знание Виктору, но не хочет раскрывать волшебных слов. Вот как она убеждает его:

(1) Виктор находится в точке А.

(2) Пегги проходит весь путь по пещере, либо до точки C, либо до точки D.

(3) После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.

(4) Виктор кричит Пегги, спрашивая ее либо о:

 

(a) или выйти из левого прохода

(b) выйти из правого прохода.

 

(5) Пегги исполняет его просьбу, при необходимости используя волшебные слова, чтобы отпереть дверь.

(6) Пегги и Виктор повторяют этапы (1) - (5) п раз.

Предположим, что у Виктора есть видеокамера, и он записывает все, что видит . Он записывает, как Пегги исчезает в пещере, записывает, как он сам кричит, указывая, где Пегги должна появиться, записывает как Пегги появляется. Он записывает все п тестов. Если он покажет эту видеозапись Кэрол, поверит ли она, что Пегги зн а-ет волшебные слова, отпирающие дверь? Нет. А что если Пегги и Виктор заранее договорились, что Виктор будет кричать, а Пегги будет делать вид, что она прошла весь путь. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. Или они могли сделать по другому. Пегги входит в один из проходов и Виктор случайным образом выкрикивает свои просьбы . Если Виктор угадывает правильно, хо­рошо, если нет - они вырежут эту попытку из видеозаписи. В любом случае Виктор может получить видеоза­пись, показывающую в точности ту последовательность, которая получилась бы, если бы Пегги знала волше б-ные слова.

Этот опыт показывает две вещи. Во первых, Виктор не может убедить третью сторону в правильности док а-зательства. И во вторых, данный протокол является протоколом с нулевым знанием. Если Пегги не знает вол­шебных слов, то очевидно, что Виктор не узнает ничего из просмотра видеозаписи . Но так как нет способа от­личить реальную видеозапись от подделанной, то Виктор не может ничего узнать из реального доказательства -это и есть нулевое знание.

Методика, используемая в этом протоколе, называется разрезать и выбратьиз-за того, что она похож на классический протокол честного деления чего-либо :

(1) Алиса делит некую вещь пополам.

(2) Боб выбирает одну из половин себе.

(3) Алиса забирает оставшуюся половину.

В интересах Алисы честно разделить на этапе (1), потому что Боб выберет на этапе (2) ту половину, которая ему больше нравится. Майкл Рабин (Michael Rabin) первым использовал в криптографии технику "разрезать и выбрать" [1282]. Понятия интерактивного протоколаи нулевого знания были формализованы позже [626, 627].

Протокол "разрезать и выбрать" работает, потому что Пегги не может несколько раз подряд угадывать, отк у-да Виктор попросит ее выйти. Если Пегги не знает секрета, он может выйти только из того прохода, в который она зашла. В каждом раундепротокола ее вероятность (иногда называемая аккредитацией)угадать, с какой стороны Виктор попросит ее выйти, составляет 50 процентов, поэтому ее вероятность обмануть Виктора также равна 50 процентам. Вероятность обмануть его в двух раундах составит 25 процентов , а во всех п раундах -один шанс из 2^П. После 16 раундов у Пегги 1 шанс из 65536 обмануть Виктора. Виктор может уверенно предпо­ложить, что если все 16 доказательств Пегги правильны, то она действительно знает тайные слова, открыва то­щие дверь между точками С и D. (Аналогия с пещерой несовершенна. Пегги может просто входить с одной сто­роны и выходить с другой, протокол "разрезать и выбрать" не нужен . Однако, он необходим с для нулевого зна­ния с математической точки зрения.)

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

(1) Пегги использует свою информацию и случайное число для преобразования одной трудной проблемы в другую, изоморфную оригинальной проблеме. Затем она использует свою информацию и случайное число для решения новой трудной проблемы.

(2) Пегги вручает решение новой проблемы, используя схему вручения бита.

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

(4) Виктор просит Пегги либо

 

(a) доказать ему, что новая и старая проблема изоморфны (т.е., два различных решения для двух ев я-занных проблем), либо

(b) открыть решение, полученное на этапе (2) и доказать, что это решение новой проблемы.

(5) Пегги исполняет его просьбу.

(6) Пегги и Виктор повторяют этапы (1) - (5) п раз.

Помните видеокамеру в протоколе для пещеры? Здесь вы можете сделать то же самое . Виктор может запи­сать обмен между ним и Пегги. Он не сможет использовать эту запись для убеждения Кэрол, но он всегда м о-жет сговориться с Пегги с целью создать имитатор, который подделывает информацию Пегги . Этот аргумент может быть использован, чтобы доказать, что используется доказательство с нулевым знанием .

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

Изоморфизм графа

Предположим, что Пегги знает об изоморфности двух графов , G, и G2. Следующий протокол докажет Вик­тору знание Пегги: (1) Пегги случайным образом тасует G,, получая другой граф, Я, который… (2) Пегги посылает Я Виктору.

Гамилыпоновы циклы

Пегги знает гамильтонов цикл графа, G. Виктору известен G, но не его гамильтонов цикл. Пегги хочет дока­зать Виктору, что она знает гамильтонов… (1) Пегги случайным образом преобразовывает G. Она передвигает точки и… вый граф, Я. Поскольку G и Я топологически изоморфны (т.е., это один и тот же граф), если ей известен гамильтонов цикл…

Параллельные доказательства с нулевым знанием

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

Неинтерактивные доказательства с нулевым знанием

Для неинтерактивных доказательств с нулевым знанием был придуман ряд протоколов [477, 198, 478, 197], которые не требуют непосредственного… Базовый протокол похож на параллельное доказательство с нулевым знанием, но… однонаправленная хэш-функция:

Общие замечания

Также существуют доказательства с минимальным раскрытием[590]. Для доказательства с минималь­ным раскрытием выполняются следующие свойства: 1. Пегги не может обмануть Виктора. Если Пегги не знает доказательства, ее… том, что доказательство ей известно, пренебрежимо малы.

Проблема гроссмейстера

Карпов, играя белыми, делает свой ход первым. Алиса записывает ход и идет в комнату к Каспарову. Играя белыми, она делает тот же ход на доске… На самом деле Каспаров играет с Карповым, а Алиса просто посредник,… мейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет…

Обман, выполненный мафией

Вот как мафия сможет это сделать. Алиса ест в ресторанчике Боба, принадлежащем мафии. Кэрол делает покупки в дорогом ювелирном магазине Дэйва. Боб и… Когда Алиса поела и собралась платить и доказывать свою личность Бобу, Боб…

Обман, выполненный террористами

Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Ал и-се, которая и отвечает на вопросы. Кэрол…

Предлагаемые решения

Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы [148]. Ес­ли каждый этап протокола должен происходить в…

Обман с несколькими личностями

Для защиты от этого нужны механизмы, обеспечивающие, чтобы у каждого человека была только одна ли ч-ность. В [120] авторами предлагается причудливая… лать это, так как иначе ребенок может быть украден.) Этим тоже легко…

Прокат паспортов

Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока Алиса находится в Заире. "Кэрол"… Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед… Проблема в том, что Алиса доказывает не свою личность, а то, что ей известна некоторая секретная инфо р-мация. Именно…

Доказательство членства

5.3 Слепые подписи Важным свойством протоколов цифровой подписи является знание подписывающим… Мы можем пожелать, чтобы люди подписывали документы, даже не зная их содержания . Существуют спо-собы, когда…

Полностью слепые подписи

(1) Алиса берет документ и умножает его на случайное число. Это случайное число называется маскирую­щим множителем. (2) Алиса посылает замаскированный документ Бобу. (3) Боб подписывает замаскированный документ.

Табл. 5-1. Патенты Чаума на слепые подписи

Патента Дата Название

США

0 19.07.88 Blind Signature Systems [323] (Системы слепых подписей)

1 19.07.88 Blind Unanticipated Signature Systems [324] (Системы слепых неожиданных подписей)

4914698 03.03.90 One-Show Blind Signature Systems [326] (Системы слепых подписей, показываемых

один раз)

4949380 14.08.90 Returned-Value Blind Signature Systems [328] (Системы слепых подписей с возвра-

щаемым значением)

4991210 05.02.91 Unpredictable Blind Signature Systems [331] (Системы непредсказуемых слепых под-

писей)

5.4 Личностная криптография с открытыми ключами

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

Эту проблему решают личностныекриптосистемы, иногда называемые системами с Неинтерактивным раз­делением ключей (Non-Interactive Key Sharing, NIKS) [1422]. Открытый ключ Боба основывается на его имени и сетевом адресе (телефонном номере, почтовом адресе или чем-то подобном). В обычной криптографии с от­крытыми ключами Алисе нужен подписанный сертификат, связывающий личность Боба и его открытый ключ . В личностной криптографии открытый ключ Боба и есть его личность. Это действительно свежая идея является почти совершенной для почтовой системы - Если Алиса знает адрес Боба, она может безопасно посылать ему почту, что делает криптографию прозрачной, насколько это вообще возможно .

Система основана на выдаче Трентом ключей пользователям в зависимости от их личности . Если закрытый

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

При разработке математики таких схем, обеспечение безопасности которых оказалось зверски сложным, был выполнен большой объем работы - главным образом в Японии . Многие предложенные решения содержат выбор Трентом случайного числа для каждого пользователя - по моему, это угрожает самой идее таких систем. Ряд алгоритмов, рассматриваемых в главах 19 и 20, могут быть личностными . Подробности алгоритмов и крипто­систем можно найти в [191, 1422, 891, 1022, 1515, 1202, 1196, 908, 692, 674, 1131, 1023, 1516, 1536, 1544, 63, 1210, 314, 313, 1545, 1539, 1543, 933, 1517, 748, 1228]. Алгоритм, который не использует случайных чисел, описан в [1035]. Система, обсуждаемая в [1546, 1547, 1507], ненадежна против вскрытия с использованием вы­бранного открытого ключа, то же самое можно сказать и о системе, предложенной как NIKS-TAS [1542, 1540, 1541, 993, 375, 1538]. По правде говоря, среди предложенного нет ничего одновременно практичного и безопас­ного.

5.5 Рассеянная передача

Криптограф Боб безнадежно пытается разложить на множители 500-битовое число п. Он знает, что оно яв­ляется произведением пяти 100-битовых чисел, и ничего больше . (Вот проблема. Если он не восстановит ключ, ему придется работать сверхурочно, и он не попадет на еженедельную игру с Алисой в мысленный покер .) Что же делать? И вот появляется Алиса:

"Мне посчастливилось узнать один из множителей числа", - говорит она, - "и я продам его тебе за 100 долларов. По дол­лару за бит." Показывая свою серьезность, она собирается использовать схему вручения бита, вручая каждый бит о тдельно.

Боб заинтересован, но только за 50 долларов. Алиса не хочет сбрасывать цену и предлагает продать Бобу половину битов за половину стоимости. "Это заметно сократит тебе работу", -.

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

Они в патовой ситуации. Алиса не может убедить Боба в том, что она знает сомножитель и, не раскрыв его, а Боб не хо­чет покупать 50 битов, которые вполне могут оказаться бесполезными .

Эта история, утащенная у Джо Килиана [831], вводит понятие рассеянной передачи.Алиса передает Бобу группу сообщений. Боб получает некоторое подмножество этих сообщений, но Алиса не знает, какие из сообщ е-ний Боб получил. Однако, это не полностью решает проблему. Когда Боб получит случайную половину битов, Алисе придется убеждать его, используя доказательство с нулевым знанием, что она послала часть множителя п.

В следующем протоколе Алиса посылает Бобу одно из двух сообщений. Боб получает сообщение, но какое -Алиса не знает.

(1) Алиса генерирует две пары открытый ключ/закрытый ключ, всего четыре ключа . Она посылает оба от­крытых ключа Бобу.

(2) Боб выбирает ключ симметричного алгоритма (например, DES). Он выбирает один из открытых ключей Алисы и шифрует с его помощью свой ключ DES. Он посылает шифрованный ключ Алисе, не сообщая, какой из ее открытых ключей он использовал для шифрования .

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

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

(5) Боб получает сообщения Алисы, одно из которых зашифровано правильным ключом DES, а другое - бес­смысленным ключом DES. Когда Боб расшифровывает каждое из этих сообщений своим ключом DES, он может прочитать одно из них, а другое будет для него выглядеть полной бессмыслицей .

Теперь у Боба есть два сообщения Алисы, и Алиса не знает, какое из них Бобу удалось успешно расшифр о-вать. К несчастью, если протокол остановится на этом этапе, Алиса сможет смошенничать. Необходим еще один этап.

(6) Когда протокол завершится, и станут известны оба возможных результата передачи , Алиса должна пере­
дать Бобу свои закрытые ключи, чтобы он убедиться в отсутствии мошенничества . В конце концов, она
могла зашифровать на этапе (4) обоими ключами одно и то же сообщение .

В этот момент, конечно же Боб сможет узнать и второе сообщение .

Протокол надежно защищен от взлома со стороны Алисы, потому что у нее нет возможности узнать, какой из двух ключей DES является настоящим. Оба из них она использует для шифрования своих сообщений, но Боб может успешно расшифровать только одно из них - до этапа (6). Протокол защищен и от взлома со стороны Боба, потому что до этапа (6) он не сможет получить закрытый ключ Алисы, чтобы определить ключ DES, ко­торым зашифровано другое сообщение. На вид этот протокол может показаться просто усложненным способом бросать "честную" монету по модему, но он интенсивно используется во многих сложных протоколах .

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

В литературе можно найти и другие протоколы рассеянной передачи . Некоторые из них неинтерактивны, т.е. Алиса публикует свои два сообщения, а Боб может прочесть только одно из них . Он может сделать это, когда захочет, ему не нужно для этого связываться с Алисой [105].

В действительности на практике никто не использует протокол рассеянной передачи , но это понятие является важным блоком при построении других протоколов. Хотя существует много типов рассеянной передачи - у меня есть два секрета, а вы получаете один, у меня есть п секретов, а вы получаете один, у меня есть один секрет, который вы получаете с вероятностью 1/2 и так далее - все они эквивалентны [245, 391, 395].

Рассеянные подписи

1. У Алисы есть п различных сообщений. Боб может выбрать одно из них, чтобы Алиса его подписала, и у Алисы не будет способа узнать, что же она… 2. У Алисы есть единственное сообщение. Боб может выбрать один из п ключей,… Идея изящна, я уверен, что где-нибудь она найдет применение .

Подпись контракта с помощью посредника

(1) Алиса подписывает копию контракта и посылает ее Тренту. (2) Боб подписывает копию контракта и посылает ее Тренту. (3) Трент посылает сообщение и Алисе, и Бобу, сообщающее, что другой партнер подписал контракт .

Глава 6

Эзотерические протоколы

Компьютерное голосование никогда не будет использовано для обычных выборов, пока не появится прот о-кол, который одновременно предохраняет от… 1. Голосовать могут только те, кто имеет на это право . 2. Каждый может голосовать не более одного раза.

Упрощенный протокол голосования №1

(2) Каждый голосующий посылает свой бюллетень в ЦИК. (3) ЦИК расшифровывает бюллетени, подводит итоги и опубликовывает результаты… Этот протокол просто кишит проблемами. ЦИК не может узнать, откуда получены бюллетени, и даже, при-надлежат ли…

Упрощенный протокол голосования №2

(2) Каждый голосующий шифрует свой бюллетень открытым ключом ЦИК . (3) Каждый голосующий посылает свой бюллетень в ЦИК. (4) ЦИК расшифровывает бюллетени, проверяет подписи, подводит итоги и опубликовывает результаты г о-лосования.

Голосование со слепыми подписями

(1) Каждый избиратель создает 10 наборов сообщений, каждый набор содержит правильный бюллетень для каждого возможного результата (например, если… (2) Каждый избиратель лично маскирует все сообщения (см. раздел 5.3) и… (3) ЦИК по своей базе данных проверяет, что пользователь не присылал раньше для подписания свои зама с-кированные…

Голосование с двумя Центральными комиссиями

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

Голосование с одной Центральной комиссией

— ЦУР и ЦИК являются единой организацией, и — для анонимного распределения регистрационных номеров на этапе (2)… Так как протокол анонимного распределения ключей не позволяет ЦИК узнать, у какого избирателя какой регистрационный…

Улучшенное голосование с одной Центральной комиссией

7. Избиратель может изменить свое мнение (т.е., аннулировать свой бюллетень и проголосовать заново) в течение заданного периода времени. 8. Если избиратель обнаруживает, что его бюллетень посчитан неправильно, он… Вот этот протокол:

Ek(I, v'), d

На этапе (4) два избирателя могут получить один и тот же идентификационный номер . Эта возможность мо­жет быть минимизирована, если число возможных… Г,Ек(1, v) Владелец этого бюллетеня узнает о произошедшей путанице и посылает свой бюллетень снова, повторяя этап (5) с новым…

Голосование без Центральной избирательной комиссии

Алиса, Боб, Кэрол и Дэйв голосуют (да/нет или 0/1) по какому-то вопросу . Пусть у каждого избирателя есть открытый и закрытый ключи. Пусть также все… (1) Каждый голосующий решает, как голосовать, и делает следующее: (a) Добавляет случайную строку к своему бюллетеню.

Другие схемы голосования

Также существуют протоколы с разделением, в которых личные бюллетени делятся между различными счетными комиссиями так, что ни одна из них не сможет… Один из протоколов с разделением предложен в [1371]. Основная идея состоит в… Другой протокол, предложенный Дэвидом Чаумом [322], позволяет проследить избирателя, который пытает-ся мошенничать.…

Протокол №1

(1) Алиса добавляет секретное случайное число к сумме своей зарплаты, шифрует результат открытым кл ю-чом Боба и посылает его Бобу. (2) Боб расшифровывает результат своим закрытым ключом. Он добавляет сумму… (3) Кэрол расшифровывает результат своим закрытым ключом. Она добавляет сумму своей зарплаты к пол у-ченному от Боба…

Протокол №2

У приведенного протокола есть две проблемы. Во первых, вычислительные способности среднего официант не позволяю ему обработать ситуации более… Криптография с открытыми ключами предлагает существенно менее жесткое решение.… Конечно, этот протокол не защитит от активных мошенников. Ничто не сможет помешать Алисе (или Бобу, какая разница)…

Протокол №3

В Службе безопасных вычислений с несколькими участниками мы спроектировали протокол для подобных людей. Мы занумеровали впечатляющий список их… Вот как это работает: (1) С помощью однонаправленной функции Алиса хэширует свою привычку как семизначную строку .

Протокол №4

встречается, чтобы тайно проголосовать по некоторым вопросам. (Все в порядке, они управляют миром - не говорите никому, что я вам проговорился.) Все… Следующие два примера иллюстрируют процесс голосования. Пусть участвуют пять… St S2 N., N2 N3 N4 N5

Безусловные безопасные протоколы с несколькими участниками

Это только частный случай общей теоремы: любая функция с п входами может быть вычислена п игроками способом, который позволит всем узнать значение функции, но любое количество игроков, меньшее, чем и/2, не сможет получить никакой дополнительной информации, не следующей из их собственных входов и результата вычислений. Подробности можно найти в [136, 334, 1288, 621].

Безопасная оценка схемы

1. Алиса может ввести свое значение так, что Боб не сможет его узнать . 2. Боб может ввести свое значение так, что Алиса не сможет его узнать . 3. И Алиса, и Боб могут вычислить результат, причем обе стороны будут убеждены в том, что результат правилен и не…

Протокол №4

Чтобы спрятать имя Алисы в электронном чеке, можно воспользоваться методикой разделения секрета . (1) Алиса готовит п анонимных денежных чеков на заданную сумму. Каждый из чеков содержит уникальную строку, X, полученную случайным образом и достаточно длин­ную, чтобы вероятность…

Электронные наличные и идеальное приведение

(1) Алиса крадет ребенка. (2) Алиса готовит 10000 анонимных денежных чеков по $1000 (или другое… (3) Алиса маскирует все 10000 денежных чеков, используя протокол слепой подписи. Она посылает их вла­стям с угрозой…

Реальные электронные наличные

Голландская компания, DigiCash, владеет большей частью патентов в области электронных наличных и ре а-лизовала протоколы электронных наличных в работающих продуктах owns. Если вы заинтересовались этим, обратитесь в DigiCash BV, Kraislaan 419, 1098 VA Amsterdam, Nethe rlands.

Другие протоколы электронных наличных

Автономныесистемы, подобные протоколу №4, не требуют соединения между продавцом и банком до окончания транзакции между продавцом и покупателем. Эти… Другой путь состоит в создании специальной интеллектуальной карты (см. Раздел… Протоколы электронных наличных можно разделить и по другому признаку . Номинал электронных монетфиксирован, людям,…

Анонимные кредитные карточки

Клиент может брать деньги из второго банка, доказывая, что он является владельцем счета. Но, этот банк не знает личности человека и не может… Обмены между клиентом, продавцом и различными банками особо выделены в [988].…