значение расстояния единственности имеют файлы электронных таблиц, текстовых процессоров и баз данных. (На самом деле оно может быть намного меньше, потому что форматы файлов предполагают стандартное начало файла.) Для сжатых файлов расстояние уникальности могло бы быть в два-три раза больше (но опять-таки, стандартное начало может его существенно снизить).
Отсюда мораль: «Распознать открытый текст просто, и для этого не требуется большого количества информации».
Коды аутентификации сообщений (Message authentication codes или MACs) – это следующий базисный элемент, о котором мы поговорим. Они не обеспечивают секретность, но гарантируют аутентификацию и целостность. Они дают уверенность, что сообщение пришло именно от того человека, который обозначен как автор (это аутентификация), и что сообщение по пути не изменилось (а это целостность).
Вы можете рассматривать MAC как защищающую от вскрытия оболочку сообщения. Кто угодно может прочесть сообщение – оболочка не обеспечивает секретность. Но кто-то, кто знает ключ MAC, может удостовериться, что сообщение не было изменено. Конкретнее, MAC – это номер, который прикреплен к цифровому сообщению.
Для MAC применяют секретные ключи совместного использования, типа симметричных алгоритмов шифрования. Сначала Алиса договаривается о ключе с Бобом. Затем, когда она хочет послать Бобу сообщение, она вычисляет MAC сообщения (применяя секретный ключ) и присваивает его сообщению. У каждого сообщения есть уникальный MAC для любого возможного ключа.
Когда Боб получает сообщение, он вычисляет его MAC (опять-таки используя все тот же совместный ключ) и сравнивает его с тем значением MAC, которое прислала Алиса. Если они совпадают, то он может быть уверен в двух вещах: сообщение действительно пришло от Алисы (или от кого-то, кто знает секрет общего ключа) – потому что только применяя этот ключ, можно вычислить MAC, и это сообщение цельное и не измененное – так как MAC можно вычислить только по полному и точному сообщению. Если бы Ева (помните нашу перехватчицу?) прослушивала связь, она смогла бы прочитать сообщение. Однако если бы она попыталась изменить текст сообщения или MAC, то вычисленный Бобом MAC не был бы равен тому значению, которое он получил. Еве пришлось бы изменить сообщение, а затем изменить MAC, чтобы он был правильным для нового сообщения, но она не могла бы этого сделать, так как не знает ключа. Банки используют такую простую систему аутентификации уже несколько десятилетий.
Алиса может прибегнуть к той же уловке, чтобы установить подлинность информации, содержащейся в базе данных. Добавляя информацию в базу данных, она вычисляет MAC и хранит его вместе с информацией. Когда она извлекает информацию, то снова вычисляет MAC и сравнивает его с тем значением, которое хранилось в базе данных. Если они совпадают, то она приобретает уверенность, что никто не изменил информацию.
MAC постоянно используются в Интернете. Их применяют, например, в протоколе IPsec, чтобы гарантировать, что IP-пакеты не были изменены в промежутке между отправлением и прибытием на место назначения. Их используют во всевозможных протоколах межбанковских переводов для установления подлинности сообщений. Большинство MAC сконструированы с применением симметричных алгоритмов или односторонних хэш-функций. Например, в СВС-МАС применяется симметричный алгоритм, а в НМАС и NMAC – хэш-функции.
Односторонние (однонаправленные) хэш-функции напоминают цифровые отпечатки пальцев: небольшие фрагменты данных, которые могут служить для идентификации достаточно больших цифровых объектов. Это общедоступные функции, у них нет никаких секретных ключей.
Они названы односторонними из-за своей математической природы. Любой может вычислить одностороннее хэш-значение чего угодно (например, текста этой книги). Однако если имеется хэш- значение этой книги, исходя из вычислений невозможно создать другую книгу с таким же значением хэш- функции или получить подлинный текст книги.
Хэш-функция также может обеспечивать аутентификацию и целостность. Если бы вы загрузили эту книгу из Интернета, у вас не было бы никакого способа узнать, написал все это я или кто-то другой все же частично изменил мои слова. Однако, если бы я дал вам в руки хэш-значение для этой книги (типичный 20-байтовый код), вы смогли бы сравнить расчетный результат с тем значением, которое дал я. Если они совпадают, то это моя книга, без изменений.
Хэш-функции широко применяются в криптографии и компьютерной безопасности. Они используются почти во всех протоколах Интернета, чтобы обрабатывать ключи, связывать последовательность событий или аутентифицировать события. Они также важны для алгоритмов цифровой подписи (подробнее об этом – позднее). Они, возможно, – наиболее полезный инструмент в коллекции шифровальщика.
В настоящее время используется целый набор односторонних хэш-функций. Стандарт на хэш- функцию SHA-1 принят правительством США. Для алгоритма безопасности хэширования (Secure Hash Algorithm) есть акронимы, и они приведены в соответствующем стандарте (Secure Hash Standard, SHS). RIPEMD-160 – это европейский алгоритм. MD4 выходит из употребления (хотя вы все еще можете его неожиданно встретить), a MD5 демонстрирует существенные недостатки, и его больше не используют для создания чего-либо нового.
Помните проблему распределения ключей, о которой я упоминал в разговоре о симметричном шифровании? Как два человека могут убедиться, что у них один и тот же ключ и что они могут пользоваться алгоритмом симметричного шифрования или функцией MAC?
Звучит нелепо? Это кажется невозможным. Если бы вы спросили шифровальщиков со всего света в 1975 году, все они сказали бы, что это невозможно. Так что можете себе представить всеобщее изумление, когда в 1976 году Витфилд Диффи и Мартин Хеллман объяснили, как это сделать. Или удивление британской разведки, когда Джеймс Эллис, Клиффорд Кок и М. Д. Уильямсон осуществили то же самое на несколько лет раньше.
Основная идея в том, чтобы использовать математическую функцию, которую просто вычислять в одном направлении и тяжело – в другом. Одна из таких функций – разложение целых чисел на множители. Если даны два числа, их легко перемножить и найти произведение. Но если дано только произведение, практически невозможно разложить число на множители и определить исходные числа. Как раз такого плана математику можно применять для создания шифрования с открытым ключом: в нее входят арифметические операции над абсолютными значениями чисел, возведение в степень и большие многоразрядные (до нескольких тысяч битов) исходные числа. Сегодня существует добрые полдюжины алгоритмов с названиями вроде RSA, Эль-Гамаль и алгоритм эллиптических кривых. (Алгоритмы, в основе которых лежит так называемая «задача о ранце», конкурировали с ними на ранних стадиях, но по прошествии 20 лет их так или иначе взломали.) Математика для каждого алгоритма своя, но концептуально они все одинаковы.
Вместо единственного ключа совместного пользования у Алисы и Боба есть два ключа: один для шифрования, а другой для расшифровки. Ключи различны, и невозможно, зная один ключ, вычислить другой. То есть если у вас есть ключ для шифрования, вы не сумеете найти ключ для расшифровки.
Вот в этом-то и есть самое интересное. Боб может создать пару таких ключей. Он может взять и обнародовать ключ для шифрования. Он может послать его друзьям, опубликовать на своем веб-сайте или поместить в телефонной книге. Алиса может найти этот ключ. Она может с его помощью зашифровать
