.RU
Карта сайта

Алгоритм криптографических преобразований с использованием методов биграммной шифрации - 10

^

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


Хэш-функция (англ.

hash

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

Большинство хэш-функций строится на основе однонаправленной функции f (·), которая образует выходное значение длиной n при задании двух входных значений длиной n. Этими входами являются блок исходного текста М, и хэш-значение Нi-1 предыдущего блока текста (рис.1).

Рис.1. Построение однонаправленной хэш-функции
Нi = f(Мi, Нi-1) .
Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения М. В результате однонаправленная хэш-функция всегда формирует выход фиксированной длины n (независимо от длины входного текста).
^

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


Общепринятым принципом построения хэш-функций является итеративная последовательная схема. По этой методики ядром алгоритма является преобразование k бит в n бит. Величина n - разрядность результата хэш-функции, а k - произвольное число, большее n. Базовое преобразование должно обладать всеми свойствами хэш-функции, т.е. необратимостью и невозможностью инвариантного изменения входных данных.
Хэширование производится с помощью промежуточной вспомогательной переменной разрядностью в n бит. В качестве ее начального значения выбирается произвольное известное всем сторонам значение, например, 0.
Входные данные разбиваются на блоки по (k-n) бит. На каждой итерации хэширования со значением промежуточной величины, полученной на предыдущей итерации, объединяется очередная (k-n)-битная порция входных данных, и над получившимся k-битным блоком производится базовое преобразование. В результате весь входной текст оказывается «перемешанным» с начальным значением вспомогательной величины. Из-за характера преобразования базовую функцию часто называют сжимающей.
Значение вспомогательной величины после финальной итерации поступает на выход хэш-функции (рис.2). Иногда над получившимся значением производят дополнительные преобразования. Но в том случае, если сжимающая функция спроектирована с достаточной степенью стойкости, эти преобразования излишни.

Рис.2. Итерактивная хэш-функция
При проектировании хэш-функции по итеративной схеме возникают два взаимосвязанных вопроса: как поступать с данными, не кратными числу (k-n), и как добавлять в хэш-сумму длину документа, если это требуется. Есть два варианта решения этих вопросов.
В первом варианте в начало документа перед хэшированием добавляется поле фиксированной длины (например, 32 бита), в котором в двоичном виде записывается исходная длина текста. Затем объединенный блок данных дополняется нулями до ближайшего кратного (k-n) бит размера.
Во втором варианте документ дополняется справа одним битом "1", а затем до кратного (k-n) бит размера битами "0". В этом варианте необходимость в поле длины отпадает - никакие два разных документа после выравнивания по границе порций не станут одинаковыми.
Кроме более популярных однопроходных алгоритмов хэширования существуют и многопроходные алгоритмы. В этом случае входной блок данных на этапе расширения неоднократно повторяется, а уже затем дополняется до ближайшей границы порции.
^



Однонаправленные хэш-функции на основе симметричных блочных алгоритмов


Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВС или СFВ с помощью фиксированного ключа и некоторого вектора инициализации IV.
Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения МАС (Message Authentication Code).
Более безопасный вариант хэш-функции можно получить, используя блок сообщения в качестве ключа, предыдущее хэш-значение - в качестве входа, а текущее хэш-значение – в качестве выхода. Реальные хэш-функции проектируются еще более сложными. Длина блока обычно определяется длиной ключа, а длина хэш-значения совпадает с длиной блока.
Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хэширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.
Если принять, что получаемая хэш-функция корректна, безопасность схемы хэширования базируется на безопасности лежащего в ее основе блочного алгоритма. Схема хэширования, у которой длина хэш-значения равна длине блока, показана на рис.3. Ее работа описывается выражениями:
Н0 = Iн,
Нi = ЕA(В)  С,
где  - сложение по модулю 2 (исключающее ИЛИ); Iн - некоторое случайное начальное значение;
А, В, С могут принимать значения Мi, Нi-1, (Мi  Нi-1) или быть константами.
Сообщение М разбивается на блоки Мi принятой длины, которые обрабатываются поочередно.
Рис.3. Обобщенная схема формирования хэш-функции
Три различные переменные А, В, С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 схем безопасного хэширования, у которых длина хэш-значения равна длине блока перечислены в табл.1.

Таблица 1

^ Номер схемы



Функция хэширования



1



Н

i

= Е

Hi-1

( М

i

)  М

i



2



Н

i

= Е

Hi-1

( М

i

 Н

i-1

)  М

i

 Н

i-1



3



Н

i

= E

Hi-1

( М

i

)  М

i

 Н

i-1



4



Н

i

= Е

Hi-1

( М

i

 Н

i-1

)  М

i



5



Н

i

= Е

Mi

( Н

i-1

)  Н

i-1



6



Н

i

= Е

Mi

( М

i

 Н

i-1

)  М

i

 Н

i-1



7



Н

i

= Е

Mi

( Н

i-1

)  М

i

 Н

i-1



8



Н

i

= E

Mi

( М

i

 Н

i-1

)  Н

i-1



9



Н

i

= Е

Mi

Hi-1

( М

i

)  М

i



10



Н

i

= Е

Mi

Hi-1

( Н

i-1

)  Н

i-1



11



Н

i

= Е

Mi

Hi-1

( M

i

)  Н

i-1



12



Н

i

= Е

Mi

Hi-1

( Н

i-1

)  М

i





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

Рис.4. Четыре схемы безопасного хэширования
Далее рассмотрены три самостоятельных алгоритма криптостойкого хэширования, получивших наибольшее распространение на сегодняшний день.
^

Алгоритм MD5


Алгоритм

MD5

(Message Digest №5) разработан Роналдом Риверсом. MD5 использует 4 многократно повторяющиеся преобразования над тремя 32-битными величинами U, V и W:
f(U,V,W)=(U AND V) OR ((NOT U) AND W)
g(U,V,W)=(U AND W) OR (V AND (NOT W))
h(U,V,W)=U XOR V XOR W
k(U,V,W)=V XOR (U OR (NOT W)).
Алгоритм MD5, основанный на предыдущей разработке Роналда Риверса MD4, был призван дать еще больший запас прочности к криптоатакам.
MD5 очень похож на MD4. Отличие состоит в простейших изменениях в алгоритмах наложения и в том, что в MD4 48 проходов основного преобразования, а в MD5 - 64.
Несмотря на большую популярность, MD4 был в конце концов взломан. Сначала появились публикации об атаках на упрощенный алгоритм. Затем было заявлено о возможности найти два входных блока сжимающей функции MD4, которые порождают одинаковый выход.
В 1995 году было показано, что найти «хэш-двойник» к произвольному документу, можно менее чем за минуту, а добиться «осмысленности» фальшивого документа (т.е. наличия в нем только ASCII-символов с определенными «разумными» законами расположения) - всего лишь за несколько дней.
^

Алгоритм безопасного хэширования SНА


Алгоритм безопасного хэширования SНА (Secure Hash Algorithm) разработан в 1992 г. и предназначен для использования совместно с алгоритмом цифровой подписи DSA.
При вводе сообщения М произвольной длины менее 264 бит алгоритм SНА вырабатывает 160-битовое выходное сообщение, называемое дайджестом сообщения MD (Message Digest).
Затем этот дайджест сообщения используется в качестве входа в алгоритм DSА, который вычисляет цифровую подпись сообщения М. Формирование цифровой подписи для дайджеста сообщения, а не для самого сообщения повышает эффективность процесса подписания, поскольку дайджест сообщения обычно намного короче самого сообщения.
Такой же дайджест сообщения должен вычисляться пользователем, проверяющим полученную подпись, при этом в качестве входа в алгоритм SНА используется полученное сообщение М.
Алгоритм хэширования SHA назван безопасным, потому что он спроектирован таким образом, чтобы было вычислительно невозможно восстановить сообщение, соответствующее данному дайджесту, а также найти два различных сообщения, которые дадут одинаковый дайджест. Любое изменение сообщения при передаче с очень большой вероятностью вызовет изменение дайджеста, и принятая цифровая подпись не пройдет проверку.
Рассмотрим подробнее работу алгоритма хэширования SHA. Прежде всего, исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следует столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец, добавляют 64-битовое представление длины исходного сообщения.
Инициализируется пять 32-битовых переменных в виде:
А = 0х67452301
В = 0хЕFСDАВ89
С = 0х98ВАDСFЕ
D = 0x10325476
Е = 0хС3D2Е1F0
Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:
а = А, b = В, с = С, d = D, е = Е
Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.
Блок сообщения преобразуется из шестнадцати 32-битовых слов (М0...М15) в восемьдесят 32-битовых слов (W0...W79).
С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:
цикл по t от 0 до 79
ТЕМР = (а <<< 5) + ft (b, c, d) + е + Wt + Кt
е = d
d = с
с = (b <<< 30)
b = а
а = ТЕМР
конец_цикла
После окончания главного цикла значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D, Е.
Отличия SHA от MD5 состоят в следующем:
^

Отечественный стандарт хэш-функции


Российский стандарт

ГОСТ Р 34.11-94

определяет алгоритм и процедуру вычисления хэш-функции для любых последовательностей двоичных символов, применяемых в криптографических методах обработки и защиты информации.
Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе можно было бы использовать и другой блочный алгоритм шифрования с 64-битовым блоком и 256-битовым ключом. Данная хэш-функция формирует 256-битовое хэш-значение.
Функция сжатия Hi = f(Мi, Нi-1) (оба операнда Мi и Нi-1 являются 256-битовыми величинами) определяется следующим образом:

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

Эти три переменные и дополненный последний блок М' сообщения объединяются в окончательное хэш-значение следующим образом:
Н = f (Z  М', f (L, f( М', Нn))).
Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с российским стандартом электронной цифровой подписи.
Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы.
Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа.
Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ.
Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, как и в асимметричных системах шифрования, используются разные математические схемы, основанные на применении однонаправленных функции.
Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:

^

Алгоритм цифровой подписи RSА


Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачусетском технологическом институте США.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа Р и Q, затем находит их произведение
N = Р * Q
и значение функции
 (N) = (Р-1)(Q-1).

Далее отправитель вычисляет число Е из условий:
Е  (N), НОД (Е,  (N)) = 1

и число D из условий:
D < N, Е*D  1 (mod  (N)).
Пара чисел (Е, N) называются открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.
Обобщенная схема формирования и проверки цифровой подписи RSА показана на рис.5.
Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции h(·) в целое число m:
m = h(М).
Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D:
S = mD (mod N).
Пара (М,S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.
После приема пары (М,S) получатель вычисляет хэш-значение сообщения М двумя разными способами.
Прежде всего он восстанавливает хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа Е:
m' = SE (mod N).
Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(·):
m = h(М).
Если соблюдается равенство вычисленных значений, т.е.
SE (mod N) = h (М),

то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители.
Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют «идентификатором» подписавшего.
Недостатки алгоритма цифровой подписи RSА:
Рис.5. Обобщённая схема цифровой подписи RSA
^

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


Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем.
Название ЕGSА происходит от слов Еl*Gаmа*Signature*Аlgorithm (алгоритм цифровой подписи Эль Гамаля).
Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, – задача дискретного логарифмирования.
Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSA, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа. Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля.
Для того чтобы генерировать пару ключей (открытый и секретный), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.
Отправитель выбирает случайное целое число X, 1 < Х  (Р-1), и вычисляет
Y =GX mod Р.
Число Y является открытым ключом, используемым для проверки подписи отправителя и передается всем потенциальным получателям документов.
Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.
Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h(·) в целое число m:
m = h(М), 1 < m < (Р-1) ,
и генерирует случайное целое число К, 1 < К < (Р-1), такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а:
а = GK mod Р
и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения
m = Х * а + К * b (mod (Р-1)).
Пара чисел (а,b) образует цифровую подпись S:
S=(а,b) ,
проставляемую под документом М.
Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К) держится в секрете.
После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись S = (а,b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число
m = h(М),
т.е. хэширует принятое сообщение М. Затем получатель вычисляет значение
А = Ya ab (mod Р)
и признает сообщение М подлинным, только если
А = Gm (mod Р).
Иначе говоря, получатель проверяет справедливость соотношения
А = Ya ab (mod Р) = Gm (mod Р).
Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S = (а,b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y.
Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.
Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.

Пример.

Выберем: числа Р = 11, G = 2 и секретный ключ Х = 8. Вычисляем значение открытого ключа:
Y = GX mod Р = 28 mod 11 = 3 .
Предположим, что исходное сообщение М характеризуется хэш-значением m = 5.
Для того чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m=5, сначала выберем случайное целое число К=9. Убедимся, что числа К и (Р-1) являются взаимно простыми. Действительно, НОД (9,10) = 1. Далее вычисляем элементы а и b подписи:
а = GK mod Р = 29 mod 11 = 6 ,
элемент b определяем, используя расширенный алгоритм Евклида:
m = Х * а + К * b (mod(Р-1)).
При m = 5, а = 6, Х = 8, К = 9, Р = 11 получаем
5 = 8 * 6 + 9 * b (mod 10)
или
9 * b = -43 (mod 10).
Решение: b=3. Цифровая подпись представляет собой пару: а = 6, b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y=3, получатель вычисляет хэш-значение для сообщения М : m=5, а затем вычисляет два числа:
Yaab (mod Р) = 36 * 63 (mod 11) = 10 (mod 11);
Gm (mod Р) = 25 (mod 11) = 10 (mod 11).
Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.
Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а,b).
В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.
Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА:

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

Алгоритм цифровой подписи DSА


Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г. для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К. Шнорра.
Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L бит каждое (512  L  1024); q - простое число длиной 160 бит (делитель числа (Р-1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети.
Отправитель выбирает случайное целое число X, 1 < Х < q. Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.
Затем отправитель вычисляет значение
Y = GX mod Р.
Число Y является открытым ключом для проверки подписи отправителя и передается всем получателям документов. Этот алгоритм также предусматривает использование односторонней функции хэширования h(·).
В стандарте DSS определен алгоритм хэширования SНА (Secure Hash Algorithm). Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m:
m = h(М), 1затем генерирует случайное целое число К, 1< К< q, и вычисляет число r:
r = (GK mod Р) mod q.
Затем отправитель вычисляет с помощью секретного ключа Х целое число s:
s = ((m + r * X)/K) mod q.
Пара чисел (r, s) образует цифровую подпись
S = (r, s)
под документом М.
Таким образом, подписанное сообщение представляет собой тройку чисел (М, r, s).
Получатель подписанного сообщения (М, r, s) проверяет выполнение условий
0 < r < q, 0 < s < q
и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение
w = (1/s) mod q,
хэш-значение
m = h(М)
и числа
u1 = (m * w) mod q,
u2 = (r * w) mod q.
Далее получатель с помощью открытого ключа Y вычисляет значение
v = ((Gu1 * Yu2) mod Р) mod q
и проверяет выполнение условия
v = r.
Если условие v = r выполняется, тогда подпись S = (r, s) под документом М признается получателем подлинной.
Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S = (r, s) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом Х (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М.
По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSA имеет следующие основные преимущества:

  • При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.

  • Большинство операций с числами К, r, s, Х при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.

  • При проверке подписи большинство операций с числами u1, u2, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.

Недостатком алгоритма DSA является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q:
s = ((m + rX)/K) (mod q), w = (1/s) (mod q),
что не позволяет получать максимальное быстродействие.
Следует отметить, что реальное исполнение алгоритма DSA может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r.
Можно также заранее вычислить обратные значения К-1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К-1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.
^

Отечественный стандарт цифровой подписи


Отечественный стандарт цифровой подписи обозначается как ГОСТ Р34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем используются следующие параметры:

  • р - простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;

  • q - простой сомножитель числа (р-1), имеющий длину 254...256 бит;

  • а - любое число, меньшее (р-1), причем такое, что а˖q mod p = 1;

  • х - некоторое число, меньшее q;

  • у = а˖x mod р.

Кроме того, этот алгоритм использует однонаправленную хэш-функцию Н(х) и определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.
Первые три параметра р, q, а являются открытыми и могут быть общими для всех пользователей сети. Число x является секретным ключом. Число y является открытым ключом. Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги:

  • 1. Пользователь «А» генерирует случайное число k, причем k

  • 2. Пользователь «А» вычисляет значения

r = (аk mod p) mod p , s = (х ˖ r + k (Н(m))) mod p .

  • 3. Если Н(m) mod q = 0, то значение Н(m) mod q принимают равным единице. Если r=0, то выбирают другое значение k и начинают снова.

  • 4. Цифровая подпись представляет собой два числа: r mod 2256 и s mod 2256 .

  • 5. Пользователь «А» отправляет эти числа пользователю «В».

  • 6. Пользователь «В» проверяет полученную подпись, вычисляя

v = Н(m)q-2 mod q , z1 = (s ˖ v) mod q , z2 = ((q-r) ˖ v) mod q , u = ((аz1 ˖ уz2 ) mod р) mod p .

  • Если u = r, то подпись считается верной.

Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSА
s = (k-1˖ r + (Н(m)))) mod q,
что приводит к другому уравнению верификации.
Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи. Этот стандарт вступил в действие c начала 1995 г.

2014-07-19 18:44
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © sanaalar.ru
    Образовательные документы для студентов.