Функции хэширования и алгоритмы электронной цифровой подписи

ФЕДЕРАЛЬНОЕ АГЕНСТВО ВОЗДУШНОГО ТРАНСПОРТА

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ “МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ АВИАЦИИ” (МГТУГА)

 

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

 

 

Лабораторная работа № 3

 

 

КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ

ОБЕСПЕЧЕНИЯ ПОДЛИННОСТИ И ЦЕЛОСТНОСТИ ЭЛЕКТРОННЫХ ДОКУМЕНТОВ.

ЭЛЕКТРОННАЯ ЦИФРОВАЯ ПОДПИСЬ

 

Выполнил:

студент группы ЭВМ 4-1

Герасимов Д.А.

«__» _________ 2012г.

 

 

Москва 2012

Цель работы

 

Изучение современных принципов обеспечения подлинности и целостности электронных документов с использованием методов криптографического преобразования информации. Построение функ­ций хэширования на основе блочных шифраторов с секретным ключом. Исследование и апробирование функции хэширования по ГОСТ Р 34.11–94 и алгоритмов электронной цифровой подписи EGSA (Эль-Гамаля), ГОСТ Р 34.10–94 и ГОСТ Р 34.10–01.

 

 

Функции хэширования и алгоритмы электронной цифровой подписи

 

Функцией хэширования или хэш-функцией (Hash-function) назы­вается алгоритм сжатия (преобразования) текста m Î М (где М – пространство текстов) произвольной длины L до некоторого числового значения z = h (m) фиксированной длины, называемого хэш-значением или дайджестом этого текста (MessageDigest). При этом значение z хэш-функции сложным образом зависит от исходного текста m и непременно изменяется при любой его модификации. Таким образом, не существует двух разных текстов m₁ ¹ m₂, имеющих одинаковоехэш-значение z,т.е. всегда справедливо h (m₁) ¹ h (m₂). Кроме того, по отношению к злоумышленнику (противнику) хэш-функция является однонаправленной, т.е. восстановить по ее хэш-значению z исходный текст m не представляется возможным.

На практике качественные функции хэширования эффективно реализуются на основе блока хэширования, преобразующего две входные последовательности элементов (например, бит) одинаковой длины в одну выходную последовательность (хэш-значение) такой же длины. Входными последовательностями могут являться i -й блок текста m_i (предварительно весь текст m, подлежащий хэшированию, разбивается на блоки m = (m₁, …, m_i, …, m_n) фиксированной длины) и хэш-значение z_i-1, полученное для предыдущего блока m_i-1 текста m. В результате формируется хэш-значение z_i для текущего блока m_i:

 

z_i = h (m_i, z_i-1).

 

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

 

 

 

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

Для обеспечения взаимной зависимости (сцепления, обратной связи) блоков текста результат криптографического преобразования (последовательность на выходе шифратора) суммируется по модулю 2 с текущим блоком данных m_i, предыдущим хэш-значением z_i-1 или некоторой гаммированной последовательностью. Полученная на выходе сумматора последо­вательность будет являться текущим хэш-значением z_i. Качество (стойкость, безопасность) такой функции хэширования определяется криптостойкостью используемого алгоритма симметричного блочного шифрования. Обобщенная схема функции хэширования, у которой хэш-значение, входной блок данных и ключ шифрования имеют одинаковую длину, показана на рис. 2.

 

 

 

 

 

На основе рассмотренного метода реализован отечественный стандарт функции хэширования ГОСТ Р 34.11-94, который преобразует двоичную последовательность произвольной длины в 256-битовое хэш-значение. В нем использован в режиме простой замены алгоритм симметричного блочного шифрования по ГОСТ 28147-89, имеющий 256-битовый ключ и обрабатывающий блоки данных длиной 64 бита. Функция хэширования по ГОСТ Р 34.11-94 предназначена для использования при формировании электронной цифровой подписи по ГОСТ Р 34.10-94. Подробное описание указанных алгоритмов можно найти в дополнительной литературе [1, 3, 4, 6-9, 11].

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

Специальное числовое значение z (двоичное, десятичное или другое), которое неразрывно связано с документом и характеризует его в целом, является значением функции хэширования h (m) подписываемого текста m. Число z, зашифрованное секретным ключом подписанта, по сути и является электронной цифровой подписью этого документа.

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

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

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

 

Среди современных алгоритмов ЭЦП широкую известность получил алгоритм Эль-Гамаля (EGSA -ElGamalSignatureAlgorithm), являющийся более надежным по сравнению с алгоритмом RSA, поскольку он основан на задаче дискретного логарифмирования, которая считается вычислительно более сложной, чем разложение большого числа на простые множители. Рассмотрим основные этапы алгоритма Эль-Гамаля.

1. Вычисляются открытый и закрытый ключи, для чего выбираются некоторое большое простое число P и большое целое число G (причем P> G), которые известны подписанту и получателю и не являются секретом. На практике используются очень большие числа P ~10 ³⁰⁸ (2¹⁰²⁴) и G ~ 10 ¹⁵⁴ (2⁵¹²). Затем подписант выбирает случайное целое число Х такое, что 1< Х £ (Р- 1), и вычисляет число

 

Y = G^ХmodP,

 

которое является открытым ключом, используемым для проверки подлинности подписи отправителя, и открыто передается всем получателям электронных документов. Число Х является секретным ключом отправителя для формирования ЭЦП и должно храниться в секрете.

2. Исходный электронный документ m представляется подписантом в виде целого числа z, причем 1< z < (Р -1), с помощью любой известной сторонам функции хэширования.

3. Выбирается случайное целое число К, причем 1< К < (Р -1), такое, что К и Р являются взаимно простыми, т.е. НОД (К, Р -1) = 1. Затем отправитель вычисляет целое число

 

а = G^КmodP

 

и, применяя расширенный алгоритм Евклида, вычисляет, используя числа Х и К, целое число b из уравнения

 

z = Х × а + К ×b (mod (P -1)).

 

Пара чисел (a, b) образуют ЭЦП, принадлежащую электронному документу m и передаваемую вместе с ним получателю. При этом пара чисел (Х, К) держится в строгом секрете (как правило, число К уничтожается после формирования ЭЦП).

Проверка подлинности ЭЦП полученного электронного документа заключается в проверке справедливости соотношения:

 

Y^а × а^b (mod P) = G^z' (mod P),

 

где числа Y, a, b, P, G известны получателю, а число z' вычисляется им для документа m с использованием известной обеим сторонам функции хэширования. Если это соотношение выполняется, то полученный электронный документ m признается подлинным и целостным, поскольку можно математически доказать, что равенство будет истинным только в том случае, если подпись S = (a, b) сформирована для документа m с использованием секретного ключа Х, из которого был получен открытый ключ Y. Тем самым подтверждается факт того что отправителем электронного документа m может являться только обладатель секретного ключа Х.

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