Геш-функції та коди аутентифікації повідомлень

Вступ

Література.

Час – 2 год.

Навчальні питання

1.... Геш-функції та коди аутентифікації повідомлень. 2

2.... Безумовно безпечні коди аутентифікації 3

1. Тилборг ван Х.К. Основы криптологии. Профессиональное руководство и интерактивный учебник. — М.: Мир, 2006, с. 278 – 297.

2. Henk C.A. van Tilborg, FUNDAMENTALS OF CRYPTOLOGY. A Professional Reference and Interactive Tutorial. Eindhoven University of Technology. The Netherlands. KLUWER ACADEMIC PUBLISHERS, Boston/Dordrecht/London.

3. Johansson T. Contributions to Uncoditionally Secure Authentication, KF Sigma, Lund, 1994.

4. Gilbert E.N., F.J. MacWilliains, N.J.A. Sloane, Codes which detect deception, Bell System Technical Journal, Vol. 53, pp. 405-424, 1974.

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

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

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

1. Желательна ли безусловная безопасность или просто вычислительная безопасность?

2. Доверяют ли различные стороны друг другу или нет?

3. Имеется ли обоюдно доверенная третья сторона?

4. Типичные файлы данных очень длинны или, скорее, коротки?

5. Важна ли также конфиденциальность?

6. Предназначена ли система для многократного использования или только на один раз?

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

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

Такие схемы обычно называют кодами аутентификации, а один их частный подкласс называют А-кодами.

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

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

· посылается файл с добавлением относительно короткой последовательности (например, 100-200) битов, которая сложным образом зависит от всех битов исходного сообщения.

Этот "хвост" должен доказывать, что сообщение на самом деле пришло от предполагаемого отправителя и что его содержание не было изменено.

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

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

Хэш-функции и MAC'и являются предметом этой лекции.

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

Функция хэширования (хэш-функция или хэш-код) — это отображение из множества 𝒜* всех последовательностей символов из алфавита 𝒜 в , где — некоторое фиксированное натуральное число. Таким образом, каждая последовательность (произвольной длины) над 𝒜 отображается в последовательность длины над 𝒜. В типичных приложениях , а принимает значение между 64 и 256.

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

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

H1. Хэш-функция — односторонняя функция, т.е. почти для всех выходов вычислительно невозможно найти вход такой, что ).

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

(13.1)

Множество называется множеством сообщений, ‑ множеством ключей, ‑ множеством кодовых слов.

Код аутентификации можно описать таблицей , в которой строки индексированы ключами из , столбцы — кодовыми словами из , а в клетке с индексами стоит либо такое , что (если оно существует; тогда в силу (13.1) оно единственно), либо стоит прочерк, если такого нет. Эту таблицу мы будем называть матрицей аутентификации данного кода.

В примере 13.4 , и . Матрица аутентификации этого кода задана в табл. 13.1.

Условие (13.1) означает, что инъективно для каждого ключа .

Когда Боб получает кодовое слово от Алисы, он принимает как подписанную версию сообщения , где однозначно определено равенством . Здесь — ключ, уже согласованный Алисой и Бобом. Чтобы система была практичной, должно быть легко обратимым для каждого ключа . С этой целью структуру (и ) часто значительно упрощают.