2 - r)v{mod q)

5. Вычислить значение

и = {ау {mod p)){modq)

6. Проверить условие г = и

При совпадении значений г ми получатель принимает решение о том, что полученное сообш,ение подписано данным отправителем и в процессе передачи не нарушена целостность сооб-ш,ения, т.е. т\ = т.В противном случае подпись считается недействительной.

4.2.4. Стандарт цифровой нодписи ГОСТ Р 34.10-2001

С повышением производительности вычислительных средств и усовершенствованием алгоритмов вычисления логарифмов в конечном поле появилась потребность в повышении стойкости ЭЦП к различного рода атакам. В связи с этим был разработан стандарт ГОСТ Р 34.10-2001 "Информационная технология. Криптографическая заш,ита информации. Процессы формирования и проверки электронной цифровой подписи", вводимый с 1 июля 2002 г. вместо ранее действовавшего стандарта ГОСТ Р 34.10-94.

В данном стандарте используются операции группы точек эллиптической кривой над конечным полем. Применяется эллиптическая кривая Е в форме Вейерштрасса над простым полем, задаваемая коэффициентами анЪ или величиной J{E), называемой инвариантом эллиптической кривой:

ЛЕ) 1728

(mod р).

Коэффициенты а и b кривой Е определяются по известному инварианту следуюш,им образом:

а = 3к (mod р),

Ь = 2к (mod р), где к =

\m-j{E)

(mod/7), J{E)ФQ,Ш%

Точку Q будем называть точкой кратности к,к& Z, если для некоторой точки Р выполнено равенство Q = кР.

Параметрами схемы ЭЦП являются следуюш,ие значения:

р - модуль эллиптической кривой, простое число,/? > 2; эллиптическая кривая, задаваемая инвариантом J{E) или коэффициентами аиЬ;

целое число т - порядок группы точек эллиптической кривой

простое число q - порядок циклической подгруппы группы точек эллиптической кривой Е, для которого выполнены сле-дуюш,ие условия:

m = nq, пе Z, п>\ 2254 << 2256

базовая точка РФ О на кривой, имеюш,ая порядок q, т. е. удовлетворяюш,ая равенству qP = О. Координаты этой точки обозначим через {Хр, ур);

хэш-функция, отображаюш,ая сообш,ения произвольной длины в множество двоичных векторов длины 256. Хэш-функция определена стандартом Р 34.11-94.

Каждый пользователь схемы ЭЦП должен обладать личной ключевой парой:

секретный ключ пользователя - целое число d, О < d < q;

открытый ключ пользователя - точка Q с координатами {Хд, Уд), удовлетворяюш,ая равенству dP = Q.

Параметры ЭЦП должны удовлетворять следуюш,им условиям:

р Ф1 (mod q), для всех целых /=1,2, ...В, где В удовлетворяет неравенству S > 31; тФр;

J{E)Ф О или \72S.

Двоичному вектору h = {a255,...,ccQ) ставится в соответствие число

ЭЦП под сообш,ением М вырабатывается по следуюш,ему алгоритму:

1. Вычислить хэш-функцию сообш,ения М :h = Н{м). 100

2. Вычислить целое число а, двоичным представлением которого является вектор /г, и определить

е = а (mod «7).

Если е = О, то определить е = 1.

3. Сгенерировать (псевдо)случайное целое число к, удовлетворяющее неравенствам

0<k<q;

4. Вычислить точку эллиптической кривой С=кР и положить

г (mod q),

где Хе - х-координата точки С. Если г = О, то вернуться на шаг 3.

5. Вычислить значение

S = (rd + кё) (mod «7).

Если S = О, то вернуться на шаг 3.

6. Вычислить двоичные векторы, соответствующие числам г и S. Определить цифровую подпись = 5) как конкатенацию двух двоичных векторов.

Для проверки подписи f под полученным сообщением М необходимо выполнить следующие действия, используя ключ проверки подписи Q.

1. По полученной подписи С, вычислить целые числа г и s. Если выполнены неравенства О < г < , О < s < , то перейти к следующему шагу. В противном случае подпись неверна

2. Вычислить хэш-функцию полученного сообщения М:1г = к{м).

3. Вычислить целое число а, двоичным представлением которого является вектор /г и определить е = а (mod «7). Если е = О, то определить е = 1.

4. Вычислить значение v = (mod «7).

5. Вычислить значения

zj = SV (mod q), z2 = -rv (mod «7).

6. Вычислить точку эллиптической кривой C = ziP + z2Q и определить

R = x (mod q),

где Xc - х-координата точки С.

7. Если выполнено равенство R = г,то подпись принимается, в противном случае подпись неверна.

4.2.5. Цифровые подписи, осповаппые па симметричных криптосистемах

На первый взгляд, сама эта идея может показаться абсурдом. Действительно, общеизвестно, что так называемая «современная», она же двухключевая криптография возникла и стала быстро развиваться в последние десятилетия именно потому, что ряд новых криптографических протоколов типа протокола цифровой подписи не удалось эффективно реализовать на базе традиционных криптографических алгоритмов, широко известных и хорошо изученных к тому времени. Тем не менее, это возможно. И первыми, кто обратил на это внимание, были родоначальники криптографии с открытым ключом У. Диффи и М. Хеллман, опубликовавшие описание подхода, позволяющего выполнять процедуру цифровой подписи одного бита с помощью блочного шифра. Прежде чем изложить эту идею, сделаем несколько замечаний о сути и реализациях цифровой подписи.

Стойкость какой-либо схемы подписи (т.е. выполнение требований, описанных в п. 4.1.) доказывается обычно установлением равносильности соответствующей задачи вскрытия схемы какой-либо другой, о которой известно, что она вычислительно неразрешима. Практически все современные алгоритмы ЭЦП основаны на так называемых «сложных математических задачах» типа факторизации больших чисел или логарифмирования в дискретных полях. Однако, доказательство невозможности эффективного вычислительного решения этих задач отсутствует, и нет никаких гарантий, что они не будут решены в ближайшем будущем, а соответствующие схемы взломаны - как это произошло с «ранцевой» схемой цифровой подписи. Более того, с бурным прогрессом средств вычислительных техники «границы надежности» методов отодвигаются в область все больших размеров блока. Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно даже 128-битовых чисел.

Сейчас эта граница отодвинута до 1024-битовых чисел - практически на порядок, - и это далеко еще не предел. Это приводит к необходимости переписывать реализующие схему программы, и зачастую перепроектировать аппаратуру. Ничего подобного не наблюдается в области классических блочных шифров, если не считать изначально ущербного и непонятного решения комитета по стандартам США ограничить размер ключа алгоритма DES 56-ю битами, тогда как еще во время обсуждения алгоритма предлагалось использовать ключ большего размера Схемы подписи, основанные на классических блочных шифрах, свободны от указанных недостатков:

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

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

Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, в нашем распоряжении есть алгоритм зашифрования Е}, оперирующий блоками данных X размера п и использующий ключ размером «к: \Х\ = п, \К\ = п. Структура ключевой информации в схеме следующая: секретный ключ подписи A:s выбирается как произвольная (случайная) пара ключей ко, к\ используемого блочного шифра:

A:s = {ko,hy.

Таким образом, размер ключа подписи равен удвоенному размеру ключа использованного блочного шифра:

sH2 = 2nK.

Ключ проверки представляет собой результат шифрования двух блоков текста Хо nXi с ключами Аго и к\ соответственно:

к = (Со, Cl) = (Ek(XQ),Ek(XO)

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

lvl = 2Х = In.

Алгоритм Sig выработки цифровой подписи для бита t {t g {0,1}) заключается просто в выборе соответствующей половины из пары, составляющей секретный ключ подписи:

S = S(t) = к(.

Алгоритм Ver проверки подписи состоит в проверке уравнения EkfX() = С(, которое, очевидно, должно выполняться для

нашего t. Получателю известны все используемые при этом величины.

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

Ver(t,s,ky) =

1,Е,(Х,) = С, 0,Е,(Х,)ФС,

Покажем, что данная схема работоспособна, для чего проверим выполнение необходимых свойств схемы цифровой подписи:

1. Невозможность подписать бит t, если неизвестен ключ подписи. Действительно, для выполнения этого злоумышленнику потребовалось бы решить уравнение Eg{X() = С( относительно s, что эквивалентно определению ключа для известных блоков шифрованного и соответствующего ему открытого текста, что вычислительно невозможно в силу использования стойкого шифра