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

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

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

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

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

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

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

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

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

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

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

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

В качестве примера простой хэш‑функции можно рассматривать XOR всех входных байтов дающий один байт суммы.

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

 

Цифровые подписи

Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?

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

2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.

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

4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.

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

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

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

 

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

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

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

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

(2) Трент, зная ключ K_A, расшифровывает сообщение.

(3) Трент добавляет к расшифрованному сообщению утверждение, что он получил это сообщение от Алисы, и шифрует это новое сообщение ключом K_B.

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

(5) Боб расшифровывает сообщение ключом K_B. Он может прочитать и сообщение Алисы, и подтверждение Трента, что сообщение отправлено именно Алисой.

Откуда Трент узнает, что сообщение пришло именно от Алисы, а не от какого-то самозванца? Он делает этот вывод из шифрования сообщения.

Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:

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

2. Эта подпись неподдельна. Только Алиса (и Трент, но ему все верят) знает K_A, поэтому только Алиса могла послать Тренту сообщение, зашифрованное ключом K_A. Если кто-нибудь попытается выдать себя за Алису, Трент сразу заметит это на этапе (2) и не заверит подлинность.

3. Эту подпись нельзя использовать повторно. Если Боб попытается взять подтверждение Трента и присоединить его к другому сообщению, Алиса закричит "Караул!" Посредник (Трент или кто-то совсем другой, имеющий доступ к той же информации) попросит Боба предъявить его сообщение и шифрованное сообщение Алисы. Затем посредник зашифрует сообщение ключом K_A и увидит, что оно не соответствует шифрованному сообщению, переданному Бобом. Боб, конечно же, не сможет создать правильное шифрованное сообщение, потому что он не знает ключа K_A.

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

5. От подписи невозможно отказаться. Если впоследствии Алиса заявит, что она никогда не посылала сообщение, подтверждение Трента докажет обратное. Помните, все доверяют Тренту, все, сказанное им - истина.

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

(1) Боб берет сообщение и утверждение Трента, что сообщение получено от Алисы, шифрует их ключом K_B и посылает обратно Тренту.

(2) Трент расшифровывает полученный пакет с помощью ключа K_B.

(3) Трент проверяет свою базу данных и подтверждает, что отправителем оригинального сообщения была Алиса.

(4) Трент шифрует полученный от Боба пакет ключом K_C, который он выделил для Кэрол, и посылает Кэрол шифрованный пакет.

(5) Трент расшифровывает полученный пакет с помощью ключа K_C. Теперь она может прочитать и сообщение, и подтверждение Трента, что сообщение отправлено Алисой.

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

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

 

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

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

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

(2) Алиса посылает подписанный документ Бобу.

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

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

1. Эта подпись достоверна. Когда Боб расшифровывает сообщение с помощью открытого ключа Алисы, он знает, что она подписала это сообщение.

2. Эта подпись неподдельна. Только Алиса знает свой закрытый ключ.

3. Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ.

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

5. От подписи невозможно отказаться. Бобу не требуется помощь Алисы при проверке ее подписи.

 

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

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

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

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

 

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

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

(1) Алиса получает значение однонаправленной хэш-функции для документа.

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

(3) Алиса посылает Бобу документ и подписанное значение хэш-функции.

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

Скорость заметно возрастает и, так как вероятность получить для двух различных документов одинаковое 160‑битное значение хэш-функции составляет только один шанс из 2¹⁶⁰, можно безопасно приравнять подпись значения хэш-функции и подпись документа. Должна использоваться только однонаправленная хэш-функция, иначе создать разные документы с одним и тем же значением хэш-функции нетрудно, и подпись одного документа приведет к ошибочной подписи сразу многих документов.

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

MD4

MD4 - это однонаправленная хэш-функция, изобретенная Роном. MD обозначает Message Digest (краткое изложение сообщения), алгоритм для входного сообщения выдает 128-битовое хэш-значение, или краткое изложение сообщения.

После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоанализа против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алгоритм, Ривест усилил свою разработку. В результате появилась MD5.

MD5

MD5 - это улучшенная версия MD4. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

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

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение.

 

Описание алгоритма:

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

Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алгоритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения.

Инициализируются четыре переменных:

A = 0x01234567

B = 0x89abcdef

C = 0xfedcba98

D = 0x76543210

Они называются переменными сцепления.

 

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

Четыре переменных копируются в другие переменные: A в a, B в b, C в c и D в d.

 

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции.

Каждая операция представляет собой нелинейную функцию над тремя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе.

Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных a, b, c и d.

Наконец результат заменяет одну из переменных a, b, c и d.

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

F(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z)

G(X,Y,Z) = (X Ù Z) Ú (Y Ù (ØZ))

H(X,Y,Z) = X Å Y Å Z

I(X,Y,Z) = Y Å (X Ú (ØZ))

(Å - это XOR, Ù - AND, Ú - OR, а Ø - NOT.)

Рис 3.2. Главный цикл алгоритма MD5

 

После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.