Однонаправленные хэш-функции

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

Хэш-функция должна удовлетворять целому ряду условий:

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

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

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

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

Рис.7.1. Общая схема вычисления однонаправленной хэш-функции  

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

Часто функции хэширования строят, используя в качестве однона­правленной функции – симметричный блочный алгоритм шифрования (, ГОСТ 28147-89) в режиме с обратной связью, принимая последний блок шифротекста за хэш-значение всего документа. Так как длина блока в указанных алгоритмах невелика (64 бита), то часто в качестве хэш-значения используют два блока шифротекста. Одна из возможных схем хэширования на основе блочного алгоритма шифрования изображена на рис.7.2

Рис. 7.2. Схема вычисления однонаправленной функции хэширования на базе блочного алгоритма шифрования

6.3. Алгоритм электронной цифровой подписи

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система , математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электрон­ных документов вычисляет два больших простых числа P и Q, затем находит их произведение и значение функции Эйлера . Далее отправитель вычисляет число K₀ из условий: , НОД и число K_C из условий: , .

Пара чисел является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число K_C сохраняется автором как секретный ключ для подписывания. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.7.3.

Рис. 7.3. Обобщенная схема алгоритма ЭЦП

Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала сообщение M (блок информации, файл, таблица) сжимают с помощью хэш-функции h в целое число . Затем вычисляют цифровую подпись S под электронным докумен­том M, используя хэш-значение m и секретный ключ K_C: n. Пара (M, S) передается партнеру-получателю как электрон­ный документ M, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа K_C. После приема пары (M, S) получатель вычисляет хэш-значение сообщения M двумя разными способами. Прежде всего, он восстанавливает хэш-значение , применяя криптографическое преобразование подписи S с использованием открытого ключа : . Кроме того, он находит результат хэширования принятого сообще­ния M с помощью такой же хэш-функции h: . Если соблюдается равенство вычисленных значений, т.е. , то получатель признает пару (M, S) подлинной. Доказано, что только обладатель секретного ключа K_C может сформировать цифровую подпись S по документу M, а определить секретное число K_C по открытому числу K₀ не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что ре­зультат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ K_C, соответствующий открытому ключу K₀. Поэтому открытый ключ K₀ иногда называют "идентификатором" подпи­савшего.

Недостатками алгоритма цифровой подписи являются:

1. При вычислении модуля n, ключей K_C и K₀ для системы цифровой подписи RSA необходимо проверять большое количе­ство дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фаль­сификацию цифровой подписи со стороны того, кто обнаружит та­кое невыполнение при подписании важных документов нельзя допускать такую возможность даже теоретически.

Для обеспечения криптостойкости цифровой подписи по отношению к попыткам фальсификации на уровне, напри­мер, национального стандарта США на шифрование информации (алгоритм ), т.е. , необходимо использовать при вычисле­ниях , K_C и K₀ целые числа не менее (или

около 10¹⁵⁴) каж­дое, что требует больших вычислительных затрат, превышающих на 20..30% вычислительные затраты других алгоритмов циф­ровой подписи при сохранении того же уровня криптостойкости.

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

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

6.4. Алгоритм цифровой подписи Эль Гамаля ( )

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

Для генерации пары ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число и большое целое число , причем . Отправи­тель и получатель подписанного документа используют при вы­числениях одинаковые большие целые числа ( или ) и (10¹⁵⁶ или 2⁵¹²), которые не являются секретными. Отправитель выбирает случайное целое число , , и вычисляет . Число является открытым ключом, используемым для проверки подписи отправителя. Число открыто передается всем потенциальным получателям документов. Число является секретным ключом отправителя для подписывания документов и должно храниться в секрете. Для того чтобы подписать сообщение , сначала отправи­тель хэширует его с помощью хэш-функции в целое число , , и генерирует случайное целое число , , такое, что и являются взаимно простыми. Затем отправитель вычисляет целое число : и, применяя расширенный алгоритм Евклида, вычисляет с помо­щью секретного ключа целое число из уравнения .

Пара чисел образует цифровую подпись : , проставляемую под документом . Тройка чисел передается получателю, в то время как пара чисел держится в секрете.

После приема подписанного сообщения получатель должен проверить, соответствует ли подпись сообщению . Для этого получатель сначала вычисляет по принятому сооб­щению число , т.е. хэширует принятое сообщение . Затем получатель вычисляет значение и признает сообщение подлинным, если, и только если . Иначе говоря, получатель проверяет справедливость соот­ношения .

Можно строго математически доказать, что последнее ра­венство будет выполняться тогда, и только тогда, когда подпись под документом получена с помощью именно того сек­ретного ключа , из которого был получен открытый ключ . Та­ким образом, можно надежно удостовериться, что отправителем сообщения был обладатель именно данного секретного ключа , не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ .

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

Схема цифровой подписи Эль Гамаля имеет ряд преиму­ществ по сравнению со схемой цифровой подписи :

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

2. При выборе модуля P достаточно проверить, что это число является простым и что у числа (P-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяе­мых условия).

3. Процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообще­ниями без знания секретного ключа (как в ).

Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые, недостатки по сравнению со схемой подписи . В частности, длина цифровой подписи получается в 1,5 раза боль­ше, что, в свою очередь, увеличивает время ее вычисления.

Пример. Выберем числа , и секретный ключ . Вычисля­ем значение открытого ключа . Предположим, что исходное сообщение характеризуется хэш-значением . Для того чтобы вычислить цифровую подпись для сообщения , имеющего хэш-значение , сначала выберем случайное целое число . Убедимся, что числа и являются взаимно простыми. Действительно, НОД (9,10)=1. Далее вычисляем элементы и подписи: , элемент определяем из уравнения , используя расширенный алгоритм Евклида. При получаем или Решение Цифровая подпись представляет собой пару Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ , получатель вычисляет хэш-значение для сообще­ния M: m=5, а затем вычисляет:

1. ,

2. .

Так как эти два целых числа равны, принятое получателем сообщение при­знается подлинным.

Дата добавления: 2014-12-16