ГОСТ Р34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».

01.06. 2002 года вступил в силу новый стандарт ЭЦП - ГОСТ Р 34.10-2001, разработанный специалистами ФАПСИ.

5.7.2 Известные алгоритмы ЭП

RSA

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

Недостатки алгоритма цифровой подписи RSА.

При вычислении модуля N, ключей Е и D для системы цифровой подписи RSА необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение.

Для обеспечения криптостойкости цифровой подписи RSА по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях N, D и Е целые числа не менее 2512 (или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

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

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

Название ЕGSА происходит от слов Е_ Gаmаl_ Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля).

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

Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G <Р.

Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.

Отправитель выбирает случайное целое число X,

1 < Х < (Р-1), и вычисляет Y =GX mod Р .

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

1)Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэшфункции h(M) в целое число m:

2)m = h(М), 1 < m < (Р-1) , и генерирует случайное целое число К,

3)1 < К < (Р-1), такое, что К и (Р-1) являются взаимно простыми.

4)Затем отправитель вычисляет целое число а: а = GK mod Р

5)Применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения m = (Х * а + К * b) (mod (Р-1))

6)Пара чисел (а, b) образует цифровую подпись S: S=(а,b) ,проставляемую под документом М.

64

7)Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К) держится в секрете.

8)После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись S = (а, b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число m = h(М), т.е. хэширует принятое сообщение М.

9)Затем получатель вычисляет значение А = Ya ab (mod Р) и признает сообщение М подлинным, только если А = Gm (mod Р).

10)Иначе говоря, получатель проверяет справедливость соотношения

Ya ab (mod Р) = Gm (mod Р).

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

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

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

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

Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению

со схемой подписи RSА. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления

DSA

Алгоритм DSA (Digital Signature Algorithm) был разработан в 1981 г. и с тех пор используется как стандарт США для электронной цифровой подписи — Digital Signature Standard (DSS). Согласно определению стандарта DSS, алгоритм DSA предусматривает применение в качестве хэш-функции алгоритма SHA. Заметим, что параметры алгоритма не засекречены.

В основу DSA легли алгоритмы Эль-Гамаля и RSA.

DSA базируется на применении больших простых чисел одинаковой размерности (от 512 бит)

— G и P. Среди его параметров присутствует и простое число q размерностью 160 бит — делитель числа (P — 1). Что же касается секретного ключа Ks, то он представляет собой целое число, случайно выбираемое из диапазона

[1, Kp = GKs mod P].

5.7.3 Российские стандарты ЭЦП ГОСТ Р 34.10.94,

ГОСТ Р 34.10.2001

ЭЦП — «реквизит электронного документа, предназначенный для зашиты данного электронного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа ЭЦП и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе» (Закон «Об электронной цифровой подписи» от 10.01.2002 г. N 01-ФЗ).

ГОСТ Р34.10-94 "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма".

01.06. 2002 года вступил в силу новый стандарт ЭЦП - ГОСТ Р 34.10-2001, разработанный специалистами ФАПСИ (задача дискретного логарифмирования в группе точек эллиптической кривой). Алгоритмы создания и проверки ЭЦП, базирующиеся на математическом аппарате эллиптических кривых, являются более стойкими по сравнению со схемами, базирующимися на сложности решения задач дискретного логарифмирования в простом поле.

ГОСТ Р 34.10.94

I этап

Выбираются числа p, q и a.

Число р – простое, должно находиться в диапазоне 2^509 <p <2^512. 65

Число q – простое, является делителем числа (p-1) Число a – не обязательно простое, 1 < a < (p-1),

Причем a^q mod p = 1.

Числа p, q и a выбираются не часто, используются какое-то время.

II этап

Генерируются ключи.

x- генерируется как случайное число 0 < x < q – секретный ключ, y - Вычисляется по формуле y = a^x mod p - открытый ключ

IIIэтап: вычисление ЭЦП по ГОСТ Р 34.10-2001– процедура выработки ЭЦП:

1.На основе алгоритма по ГОСТ Р34.11-94 вычислить h(m) - хэш-функцию от сообщения m. Если h(m) mod q=0, то h(m)=1

2.Выработать случайное число k, 0 <k <q.

3.Вычислить r=a^k mod p, r1 = r mod q. Если r1=0, то переход к пункту 2.

4.С использованием секретного ключа вычисляется значение подписи

s = (x*r1 + k*h(m)) mod q. Если s = 0, то перейти к пункту 2.

5.Подписью сообщения m будет являться вектор {r1, s}, каждая из составляющих размером 256 бит.

IV этап: происходит процедура проверки подписи на стороне получателя. Получатель получает сообщение m1 и подпись {r1, s}. У получателя есть ключ y - открытый ключ.

1.Проверяется, что элементы подписи удовлетворяют условиям 0 < s < q, 0 < r1 < q. Если не удовлетворяет, то подпись не действительна.

2.На основе алгоритма по ГОСТ Р34.11-94 вычисление хэш-функции h(m1) полученного сооб-

щения. Если h (m1) mod q = 0 то h(m1) = 1.

3.Вычисление значения v = h(m1) ^(q-2) mod q

4.Вычисление значений z1= (s*v) mod q, z2 = (q-r1) * v mod q.

5.Вычисление значения u = ((a^z1 *y^z2) mod p) mod q.

6.Проверить условие r1 = u. Если оно выполняется, то получатель принимает решение о том, что подпись действительна, целостность сообщения не нарушена. Иначе подпись не действительна.

ГОСТ Р 34.10-2001 Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи

История

Данный алгоритм разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Разрабатывался взамен ГОСТа Р 34.10-94 для обеспечения большей стойкости алгоритма.

Описание

ГОСТ Р 34.10-2001 основан на эллиптических кривых. Его стойкость основывается на сложности взятия дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэшфункции по ГОСТу Р 34.11. После подписывания сообщения М к нему дописывается цифровая подпись размером 512 бит и текстовое поле. В текстовом поле могут содержаться, например, дата и время отправки или различные данные об отправителе:

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

66

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

Параметры схемы цифровой подписи

Простое число p — модуль эллиптической кривой такой, что p > 2255

Эллиптическая кривая E задается своим инвариантом J(E) или коэффициентами

где Fp —конечное простое поле. J(E) связан с коэффициентами a и b следующим образом:

При этом

Целое число m — порядок группы точек эллиптической кривой (то есть число элементов группы), m не должно совпадать с p

Простое число q, порядок одной из циклических подгрупп группы точек эллиптической

кривой, то есть выполняется m = nq, для некоторого n є N. Так же q лежит в пределах 2254 < q < 2256.

Точка P (xp, yp) ≠ 0 эллиптической кривой E,

Являющаяся генератором подгруппы порядка q, или другими словами qP = 0. Здесь qP = P + P + (q раз). А 0 - нулевой элемент группы точек эллиптической кривой.

h(M) — хэш-функция (ГОСТ Р 34.11-94), которая конечные сообщения M отображает в двоичные вектора длины 256 бит.

Каждый пользователь цифровой подписи имеет личные ключи:

•Ключ шифрования d — целое число, лежащее в пределах

•0 < d < q.

•Ключ расшифрования Q (xq, yq) — точка эллиптической кривой, dP = Q.

При этом должны выполняться	где	и
Формирование цифровой подписи

1.Вычисление хэш-функции от сообщения М: h(M)

2.Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z — целое число

3.Генерация случайного числа k, такого что 0 < k < q

4.Вычисление точки эллиптической кривой C = kP, и по ней нахождение r = xc(mod q) (xc — координата x точки C). Если r = 0, возвращаемся к предыдущему шагу.

5.Нахождение s = rd + ke(mod q). Если s = 0, возвращаемся к шагу 3.

6.Формирование цифровой подписи, где r и s — векторы, соответствующие r и s.

•Проверка цифровой подписи

1.Вычисление по цифровой подписи чисел r и s, учитывая, что ξ = (r | s), где r и s — числа, соответствующие векторам r и s. Если хотя бы одно из неравенств r <q и s <q неверно, то подпись неправильная.

2.Вычисление хэш-функции от сообщения М: h(M)

3.Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z — целое число соотвествующее h

(M)

4.Вычисление v = e - 1(mod q).

5.Вычисление z1 = sv (mod q) и z2 = - rv (mod q)

6.Вычисление точки эллиптической кривой C = z1P + z2Q. И определение R = xc (mod q), где

xc — координата x кривой C. В случае равенства R = r подпись правильная, иначе — неправильная.

Государственная дума на заседании 25 марта 2011 приняла в третьем, окончательном чтении закон «Об электронной подписи», который заменит действующий сейчас федеральный закон №1 от 10 января 2002 года «Об электронной цифровой подписи».

67