Хеш-функции. Формирование цифровой подписи

Лабораторная работа МСЗИ №5

Тема: Хеш-функции. Формирование цифровой подписи.

Основные понятия хеш-функций

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

Хэш-функция Н должна применяться к блоку данных любой длины. Хэш-функция Н создает выход фиксированной длины. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h. Для любого данного х вычислительно невозможно найти y x, что H (y) = H (x). Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).

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

Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (SAB || M). Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить SAB || M = H-1 (C). Так как атакующий теперь знает и М и SAB || M, получить SAB совсем просто.

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

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

Технология цифровых подписей

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

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

· создать подпись таким образом, чтобы ее невозможно было подделать;

· иметь возможность проверки того, что подпись действительно принадлежит указанному владельцу;

· иметь возможность предотвратить отказ от подписи.

Классическая схема создания цифровой подписи

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

1.  применяет к исходному сообщению хеш-функцию;

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

3.  формирует новое сообщение, состоящее из исходного сообщения и добавленной к нему цифровой подписи.

Получатель, получив подписанное сообщение,

1.  отделяет цифровую подпись от основного сообщения;

2.  применяет к основному сообщению хеш-функцию;

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

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

Схема подписи RSA

Криптосистема с открытым ключом RSA может использоваться не только для шифрования, но и для построения схемы цифровой подписи.

Для создания подписи сообщения M отправитель

1.  вычисляет хеш-образ r = h(M) сообщения M с помощью некоторой хеш-функции;

2.  зашифровывает полученный хеш-образ r на своем секретном ключе (d,n) , т. е. вычисляет значение s = rd mod n , которое и является подписью.

Для проверки подписи получатель

1.  расшифровывает подпись s на открытом ключе (e,n) отправителя, т. е. вычисляет r’ = se mod n и таким образом восстанавливает предполагаемый хеш-образ r’ сообщения M;

2.  вычисляет хеш-образ h(M) = r сообщения M с помощью той же самой хеш-функции, которую использовал отправитель;

3.  сравнивает полученные значения r и r’ . Если они совпадают, то подпись правильная, отправитель действительно является тем, за кого себя выдает, и сообщение не было изменено при передаче.

Пример. Создать хеш–образ слова «КОЗИНА», используя хеш–функцию , где n = pq, p=13, q=19.

Хешируемое сообщение «КОЗИНА». Возьмем два простых числа p=13, q=19 Определим n=pq=13*19=247. Вектор инициализации выберем равным 8 (выбираем случайным образом). Слово «КОЗИНА» можно представить последовательностью чисел (12, 16, 9, 10, 15, 1) по номерам букв в алфавите. Таким образом,

n=247, H0=8, M1=12, M2=16, M3=9, M4=10, M5=15, M6=1.

Используя формулу

,

получим хеш-образ сообщения «КОЗИНА»:

H1=(H0+M1)2 mod n = ( 8 + 12)2 mod 247 = 400 mod 247=153

H2=(H1+M2)2 mod n = (153 + 16)2 mod 247 = 28561 mod 247= 156

H3=(H2+M3)2 mod n = (156 + 9)2 mod 247 = 27225 mod 247= 55

H4=(H3+M4)2 mod n = ( 55 + 10)2 mod 247 = 4225 mod 247= 26

H5=(H4+M5)2 mod n = ( 26 + 15)2 mod 247 = 1681 mod 247= 199

H6=(H5+M6)2 mod n = (199 + 1)2 mod 247 = 40000 mod 247= 233

В итоге получаем хеш-образ сообщения «КОЗИНА», равный 233.

Электронная цифровая подпись. Используя хеш-образ вычислить электронную цифровую подпись по схеме RSA.

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

s = mod 247 = 168.

Для проверки ЭЦП, используя открытый ключ (121, 247), найдем

H = mod 247 = 233.

Поскольку хеш-образ сообщения совпадает с найденным значением H, то подпись признается подлинной.

Индивидуальные задания:

Написать программу, реализующую формирование цифровой подписи к сообщению.

Программа должна выполнять следующие действия:

1.  Отправитель обрабатывает исходное сообщение хеш-функцией MD5 (вкладка Indy).

2.  Полученную 32-символьную последовательность (128-бит) представить в десятичных кодах ASCII и в соответствии с вариантом задания, создать хеш-образ этой последовательности.

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

4.  Сформировать файл для получателя содержащий: исходное сообщение и цифровую подпись.

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

Сделать выводы о подлинности сообщения.

Варианты:

1.

, где Mi = два символа через два

2.

, где Mi = четные символы

3.

, где Mi = нечетные символы

4.

, где Mi = каждый 5-й символ