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

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

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

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

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

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

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

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

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

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

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

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

Код проверки подлинности сообщения (message authentication code, MAC), известный также как код про-

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

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

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

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

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

(1)Алиса и Боб согласовывают криптосистему с открытыми ключами.

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

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

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

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

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

(1)Алиса извлекает открытый ключ Боба из базы данных.

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

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

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

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

Первые алгоритмы с открытым ключом стали известны в то же время, когда проходило DES обсуждение как предполагаемого стандарта. Это привело к известной партизанщине в криптографическом сообществе . Как это описывал Диффи [494]:

Прекрасные криптосистемы с открытым ключом, обсуждаемые в популярной и научной печати, тем не менее, не нашли соответствующего отклика среди криптографических чиновников . В том же году, когда была открыта криптография с откр ы-тыми ключами, Агентство национальной безопасности (NSA) предложило удобную криптографическую систему, разработанную фирмой IBM, в качестве федерального Стандарта шифрования данных (Data Encryption Standard, DES). Марти Хеллман и я критиковали это предложение из-за недостаточной длины ключа, но производители подготовились поддержать стандарт, и наша критика была воспринята многими как попытка помешать введению стандарта ради продвижения нашей собственной работы. Криптография с открытым ключом, в свою очередь, также подвергалась критике в популярной литер а-туре [1125] и технических статьях [849, 1159], словно это был конкурирующий продукт, а не недавнее научное открытие . Это, однако, не помешало NSA объявить о своих заслугах в этой области. Его директор в одной из статей Encyclopedia Bri-tannica [1461] указал, что "двухключевая криптография была открыта в Агентстве на десять лет раньше ", хотя доказательства этого утверждения не были публично представлены.

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

1.Алгоритмы с открытыми ключами работают медленно. Симметричные алгоритмы по крайней мере в 1000 раз быстрее, чем алгоритмы с открытыми ключами. Да, компьютеры становятся все быстрее и быстрее и лет через 15 криптография с открытыми ключами достигнет скоростей, сравнимых с сег о-дняшней скоростью симметричной криптографии. Но требования к объему передаваемой информации также возрастают, и всегда будет требоваться шифровать данные быстрее, чем это сможет сделать криптография с открытыми ключами.

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

Вскрытие с выбранным открытым текстом может быть особенно эффективным, если число возможных шифрованных сообщений относительно мало . Например, если P - это денежная сумма в долларах, меньшая чем $1000000, то такое вскрытие сработает, криптоаналитик переберет весь миллион значений . (Эта проблема решается с помощью вероятностного шифрования, см. раздел 23.15.) Даже если P не так хорошо определено, такое вскрытие может быть очень эффективно . Полезным может быть простое знание, что шифротекст не соо т-ветствует конкретному открытому тексту. Симметричные криптосистемы не чувствительны к вскрытиям такого типа, так как криптоаналитик не может выполнить тестовых дешифровок с неизвестным ключом .

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

(1)Боб посылает Алисе свой открытый ключ

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

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

(4)Оба участника шифруют свои сообщения с помощью одного сеансового ключа.

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

Головоломки Меркла

Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами . В 1974 году он записался на курс по компьютерной безопасности в Калифорнийском университете, Беркли , который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам" [1064]. Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой несмотря на продолжающееся непонимание его р е-зультатов.

Техника Меркла основывалась на головоломках ("puzzle"), которые отправителю и получателю решить лег-