Как читать эту книгу 3 страница

Часть I
КРИПТОГРАФИЧЕСКИЕ
ПРОТОКОЛЫ

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

2.1 Введение в протоколы

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

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

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

— Каждый участник протокола должен согласиться следовать протоколу.

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

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

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

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

— Невозможно сделать или узнать больше, чем определено в протоколе.

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

Смысл протоколов

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

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

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

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

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

Игроки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3) Боб подписывает контракт.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 Передача информации с использованием симметричной криптографии

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

(1) Алиса и Боб выбирают систему шифрования.

(2) Алиса и Боб выбирают ключ.

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

(4) Алиса посылает шифрованное сообщение Бобу.

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

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

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

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

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

А Алиса? Что она может сделать, чтобы испортить протокол? Она может передать копию ключа Еве, и тогда Ева сможет читать все, что говорит Боб, и напечатать его слова в Нью-Йорк Таймс. Это серьезно, но проблема не в протоколе. Алиса и так может передавать Еве любые открытые тексты, передаваемые с использованием протокола. Конечно, то же самое может сделать и Боб. Протокол предполагает, что Алиса и Боб доверяют друг другу. Итак, симметричным криптосистемам присущи следующие проблемы:

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

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

— В предположении, что каждая пара пользователей сети использует отдельный ключ, общее число ключей быстро возрастает с ростом числа пользователей. Сеть из nпользователей требует n{n - l)/2 ключей. Например, для общения 10 пользователей между собой нужно 45 различных ключей, для 100 пользователей потребуется 4950 ключей. Решение проблемы - в уменьшении числа пользователей, но это не всегда возможно.

2.3 Однонаправленные функции

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

Однонаправленные функции относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная x,просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь "нелегко" означает, что для вычисления xпо f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.

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

Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования однонаправленных функций нет, нет и реальных свидетельств возможности их построения [230, 530, 600, 661]. Несмотря на это многие функции выглядят в точности как однонаправленные: мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить x², но намного сложнее x^1/2. В оставшейся части раздела я собираюсь притвориться, что однонаправленные функции существуют. Мы поговорим об этом в еще разделе 11.2.

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

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

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

2.4 Однонаправленные хэш‑функции

У однонаправленной хэш‑функции может быть множество имен: функция сжатия, функция сокращения, краткое изложение, характерный признак, криптографическая контрольная сумма, код целостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась, эта функция является центральной в современной криптографии. Однонаправленные хэш‑функции - это другая часть фундамента многих протоколов.

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

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

Однонаправленная хэш‑функция - это хэш‑функция, которая работает только в одном направлении: легко вычислить значение хэш‑функции по прообразу, но трудно создать прообраз, значение хэш‑функции которого равно заданной величине. Упоминавшиеся ранее хэш‑функции, вообще говоря, не являются однонаправленными: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш‑функцией такого не выйдет. Хорошей однонаправленной хэш‑функцией является хэш‑функция без столкновений -трудно создать два прообраза с одинаковым значением хэш‑функции.

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

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

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

Код проверки подлинности сообщения (message authentication code,MAC), известный также как код проверки подлинности данных (data authentication code, DAG), представляет собой однонаправленную хэш‑функцию с добавлением секретного ключа (см. раздел 18.14). Значение хэш‑функции является функцией и прообраза, и ключа. Теория остается той же, что и для хэш‑функций, но только тот, кто знает ключ, может проверить значение хэш‑функции. MAC можно создать с помощью хэш‑функции или блочного алгоритма шифрования, существуют также и специализированные MAC.

2.5 Передача информации с использованием криптографии с открытыми ключами

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

В 1976 году Уитфилд Диффи и Мартин Хеллман навсегда изменили эту парадигму криптографии [496]. (NSA заявило, что знало о такой возможности еще в 1966 году, но доказательств не представило.) Они описали криптографию с открытыми ключами,используя два различных ключа - один открытый и один закрытый. Определение закрытого ключа по открытому требует огромных вычислительных затрат. Кто угодно, используя открытый ключ может зашифровать сообщение, но не расшифровать его. Расшифровать сообщение может только владелец закрытого ключа. Это похоже на превращение криптографического сейфа в почтовый ящик. Шифрование с открытым ключом аналогично опусканию письма в почтовый ящик, любой может сделать это, опустив письмо в прорезь почтового ящика. Дешифрирование с закрытым ключом напоминает извлечение почты из почтового ящика. Обычно это гораздо сложнее - вам может понадобиться сварочный агрегат. Однако, если вы знаете секрет (у вас есть ключ от почтового ящика), вы без труда достанете вашу почту.