Применение хеш-функции в создании электронной цифровой подписи



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

Целью аутентификации электронных документов является их защита от возможных видов вредоносных действий:

– активный перехват — злоумышленник, подключившись к каналу связи, перехватывает файлы документов и меняет их на другие,

– маскарад — абонент направляет документ абоненту от имени абонента ;

– ренегатство — абонент утверждает, что не направлял документ абоненту , хотя в действительности посылал;

– подмена — абонент меняет полученный или формирует новый документ, после чего утверждает, что получил его от абонента ;

– повтор — абонент повторяет от своего имени ранее переданный документ, который абонент посылал абоненту .

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

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

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

– показывает, что подписанный документ получен от лица, поставившего свою подпись;

– не дает возможности лицу, поставившему свою подпись, отказаться от подписанного документа;

– является неотъемлемой частью данного документа и не может быть использована для подписания другого документа;

– гарантирует целостность подписанного документа.

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

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

;

2) хэш-значение отправитель шифрует своим личным секретным ключом и получает число, которое считается подписью документа;

3) зашифрованное хэш-значение вместе с документом отправитель направляет получателю ;

4) получатель сначала сам вычисляет хэш-значение полученного документа, далее дешифрует полученное хеш-значения с использованием открытого ключа отправителя

, после чего сравнивает оба значения.

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

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

Среди большого количества различных асимметричных криптосистем самой популярной является криптосистема RSA, разработанная в 1977 г. и получившая свое название в честь Рона Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Эйдельмана (Adleman). Алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (Обслуживание кредитных карточек). Надежность алгоритма основывается на трудности факторизации (разложения на множители) больших чисел и трудности вычисления дискретных алгоритмов (нахождения при известных , b и из уравнения .

Алгоритм RSA состоит из трех частей: генерации ключей, шифрования и дешифрования. Генерируют

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

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

Основные свойства хэш-функции:

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

;

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

3) хэш-функция является необратимой, то есть подбор некоторого фиктивного документа ' с тем же самым хеш-значением является задачей практически нерешаемой;

4) вероятность того, что хеш-значения двух разных документов совпадут, чрезвычайно мала.

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

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

Содержание указанных входных значений хэш-функции следующее:

1) первое входное значение представляет собой очередной блок документа ;

2) второе входное значение представляет собой хэш-значение всех предыдущих блоков документа.

При исчислении хэш-значение для первого блока документа используется некоторое начальное хэш-значение

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

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

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

Возьмем два простых числа и . Тогда модуль

Начальное хэш-значение выбираем случайным образом, пусть оно равно 12. Слово «ТРУБНИКОВА» представим в виде последовательности чисел (20, 18, 21, 2, 15, 10, 12, 16, 3, 1) по номерам букв в русском алфавите. Тогда имеем

Используя формулу , получим хеш-образ сообщения «ТРУБНИКОВА»:

n

n

n

n

n

n

n

n

n

n

В итоге получаем хеш-образ сообщения «ТРУБНИКОВА», равный 9, который будем использовать для вычисления электронной цифровой подписи по схеме RSA.

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

.

Секретный ключ выбираем из условий и взаимно просто с , т. е. и не имеют общих делителей.

Пусть . Открытый ключ выбираем из условий

и .

Получим

, .

Последнее условие означает, что число должно делиться на 352 без остатка.

Таким образом, для определения нужно подобрать такое число

, что . При получаем или .

Таким образом мы сгенерировали — открытый ключ и — секретный ключ.

Электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу

.

Для проверки ЭЦП используем открытый ключ

.

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

Таким образом мы построили демонстрационный пример создания электронной цифровой подписи с использованием хеш-функции и алгоритма шифрования RSA. Все вычисления были выполнены в электронных таблицах Excel, в частности, с использованием формулы =ОСТАТ( ; ).

Литература:

1. Айерлэнд К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен. — Пер. с англ. — М.: Мир, 1987. — 416 с.
2. Алферов А. П. Основы криптографии / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. М.: Гелиос АРВ, 2002. — 480 с.