Криптосистема "открытый ключ"

     Рассмотрим  схему взаимодействия отправителя (A) и получателя (B), которая позволяет B проверить подлинность передаваемого сообщения.

1. A создает сообщение x, которое он собирается подписать и вычисляет подпись D_KA(x).
2. A передает B пару (x,D_KA(x)).
3. B проверяет равенство E_KA(D_KA(x)) = x. В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.

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

     Напомним  определение хэш-функции.

     Функция h:X -> M называется хэш функцией, если выполнены следующие условия:

1. Постоянство размера - для входного массива данных любого размера результатом должен быть блок данных фиксированного размера.
2. Функция h(x) легко вычислима
3. Функцию h(x) трудно инвертировать, то есть почти для всех m из M трудно найти x из X такой, что h(x) = m.
4. Для данного x сложно найти x' неравный x такой, что h(x) = h(x').
5. Сложно найти пару (x, x') из X² такую, что x неравен x' и h(x) = h(x').

     Где M - множество векторов фиксированной  длины, а X - вектора произвольной длины. Пара (x, x') из X² такая, что x неравно x' и h(x) = h(x') называется коллизией хэш-функции h.

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

     x = (x₁,..,x_k) \to ( (x₁,D_KA(x₁)),.., (x_k,D_KA(x_k))).

     Где x₁,..,x_k - вектора фиксированной длины, совпадающей с длиной входа функций E_KA(x) и D_KA(x). Подобная подпись обладает следующими недостатками:

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

     Модифицированный  протокол выглядит таким образом:

1. A создает сообщение x, которое он собирается подписать и вычисляет его хэш h(x), после чего подписывает D_KA(h(x)).
2. A передает B пару (x,D_KA(h(x))).
3. B проверяет равенство E_KA(D_KA(h(x))) = h(x). В случае совпадения обоих величин B принимает решение о подлинности сообщения x, в противном случае B принимает решение считать сообщение x искаженным.

     В этом протоколе возможность подделки подписи может быть основана на нахождении коллизии хэш-функции, то есть по известному значению h(x) найти x' такой, что h(x) = h(x'). Для предотвращения этой возможности  нельзя использовать непроверенные  функции. Как правило, стойкие к  коллизиям хэш-функции описаны  в государственном стандарте. В  Российской Федерации этот стандарт носит название ГОСТ Р 34.11-94, в США - описывается документами FIPS 180-1 и FIPS 180-2, а в Евросоюзе рекомендуется использование стандарта Whirlpool. Отечественный стандарт хэширования был принят в 1994 году и с тех пор не изменялся, размер хэш-блока для него составляет 256 бит. В США изначально действовал стандарт SHS (secure hash standard), где размер хэш-блока был равен 160 бит. Однако в 2002 году стандарт был пересмотрен: прежний остался действовать и получил обозначение SHA-1, но к нему были добавлены три новых алгоритма, вырабатывающие хэш-блоки размером 256,384 и 512 бит, названные SHA-256/384/512 соответственно.

     2.2 Схемы открытого ключа.

     Аппарат электронной цифровой подписи позволяет  решать задачи проверки целостности  и их авторства (без возможности  отречения), разумеется, если используются стойкие алгоритмы формирования ОТКРЫТЫЙ КЛЮЧ, надежные криптографические протоколы и сохранен в тайне секретный ключ. Поэтому для того, чтобы документы, подписанные ОТКРЫТЫЙ КЛЮЧ, имели юридическую силу, развитые государства принимают стандарты на алгоритмы ОТКРЫТЫЙ КЛЮЧ, кроме того, существует ряд коммерческих алгоритмов, которые хоть в среднем и слабее национальных, однако достаточно надежны для коммерческого уровня при разумном выборе длины ключей. Ниже указаны 9 алгоритмов формирования цифровой подписи:

• DSA
• ГОСТ Р34.10-01,
• ECDSA,
• ESIGN,
• RSA-PSS,
• схема Шнорра,
• ElGamal.
• Электронная цифровая подпись СТБ 1176.2-99
• Схема Диффи - Лампорта
• Вероятностная схема подписи Рабина

     Где ГОСТ Р34.10-01 и ECDSA - стандарты в России и США соответственно, а алгоритмы ESIGN, RSA-PSS - претенденты в конкурсе проекта NESSIE (Евросоюз). 

     В качестве замечания, необходимо отметить, что в последние годы в качестве мультипликативной группы используются множество точек, лежащих на эллиптической  кривой. Наиболее известными стандартами, основанными на этом подходе, является DSA (Digital Signature Algorithm FIPS 186-2, точнее его  часть, относящаяся к ANSI X9.62 ECDSA -Elliptic Curve DSA), входящий в DSS (Digital Signature Standard) и  ГОСТ 34.10-2001. «Эллиптической кривой»  называется множество пар точек {X,Y}, удовлетворяющих уравнению вида Y2=aX3+bX+c. Аналогично предыдущим рассуждениям, можно сказать, что применительно  к криптографии, мы будем говорить об эллиптической кривой над конечным простым полем Галуа, как пары {x,y} (собственно, эти пары и являются «точкой» в терминах эллиптических  кривых), таких, что x,yОGF(p), удовлетворяющих  уравнению y2=(x3+ax+b) mod p. Простое число p - это модуль преобразования групп  точек эллиптической кривой. В  качестве одного из параметров кривой рассматривается также величина m - это порядок поля (данный термин описывает мощность множества точек, образующих данное поле). Удобство описанной  конструкции в том, что если в  «чистой» схеме Эль-Гамаля длина  ключа (порядка поля) требуется не хуже 2512, то для эллиптических кривых достаточно 2255 (по некоторым оценкам  даже порядка 2180) при аналогичной  трудоемкости вскрытия.

     Сложностью  использования этого алгоритма  является то, что в международном  стандарте X9.62 предлагается сразу 3 способа  получения параметров эллиптической  кривой:

     • Первый способ состоит в использовании кривых, заданных в Х9.62 (в приложении «J»). Исследование этих готовых кривых показывает, что только одна, а именно последняя кривая удовлетворяет требуемому простому числу. Эта кривая может использоваться только в качестве тестового варианта, поэтому данный способ не пригоден.

     • Второй способ состоит в случайном выборе эллиптической кривой и проверке ее параметров. Это продолжается до тех пор, пока не будет найдена требуемая кривая. Очевидно, что поскольку процесс является вероятностным, то поиск эллиптических кривых с требуемым порядком в этом случае может продолжаться очень долго.

     • Третий способ заключается в выборе требуемых параметров и построении кривой по этим параметрам. Последний способ сразу дает одну или несколько эллиптических

2.2.1 Схема Открытого ключа ГОСТ Р 34.10-01 (Российский стандарт)

     В основу безопасности российского стандарта  электронной цифровой подписи ГОСТ Р 34.10-2001 на эллиптической кривой E(F_p) над простым конечным полем из p элементов и его американского аналога ECDSS положена задача дискретного логарифмирования на эллиптической кривой. Эллиптическая кривая E(F_p) в форме Вейерштрасса задается уравнением

     y² = f(x) ( mod p ),

     где кубический многочлен f(x) не имеет кратных  корней в поле F_p.

     В основу протокола электронной цифровой подписи ГОСТ Р 34.10-2001 положен протокол Эль-Гамаля. Этот протокол обладает вычислимыми  морфизмами, позволяющими на основании  одного подписанного сообщения создавать  произвольное число формально правильных пар сообщение-подпись, поэтому подпись  вычисляется для значения хэш-функции  от сообщения. Пусть m - подписываемое  сообщение, h - хэш-функция по ГОСТ Р 34.11-94, {E(F_p), Q, P} - открытый ключ, число l, - секретный ключ, при этом P = lQ. Для формирования подписи выполняются следующие действия:

• вычисляется хэш-функция e = h(m) ( mod r ), причем e неравно 0;
• вырабатывается случайный показатель k, 0 < k < r, и вычисляется точка R = (x_R, y_R) = k_Q, причем x_R неравно 0 ( mod r );
• вычисляется часть подписи s = (lx_R + ke) ( mod r ),  
  причем s неравно 0.

     Подписанное сообщение представляет собой тройку (m, x_R ( mod r ), s). Для проверки подписи выполняются следующие действия:

• проверяются условия 0 < x_R ( mod r ) < r и 0 < s < r;
• вычисляется e = h(m) ( mod r ) и если e = 0, то считается e = 1;
• вычисляется точка R' = (se^-1 ( mod r ))Q - (x_Re ^-1 ( mod r ))Q;
• проверяется сравнение xR' = x_R ( mod r ).

     Если  сравнение выполняется, то подпись  верна.

     Для обеспечения высокой сложности  задачи дискретного логарифмирования на эллиптической кривой необходимо выполнение следующих условий, предусмотренных  ГОСТ Р 34.10-2001:

• p - простое число длины 256 бит;
• многочлен f(x) не имеет кратных корней (дискриминант многочлена f отличен от нуля);
• многочлен f(x) не должен задаваться неполным уравнением;
• число точек |E(F_p)| имеет простой делитель r длины от 254 до 256 бит;
• порядок группы E(F_p) |E(F_p)| неравен p;
• p^k неравно 1 ( mod r ) для k = 1,... , 30.

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

    2.2.3 Схема открытого ключа ECDSA (Стандарт США)

    Пусть p>2 простое число. Эллиптическая  кривая E задается уравнением y ² = x³+ax+b (mod p ) (*) над конечным простым полем. Предположим, что группа E(F_p) содержит подгруппу простого порядка q, которая порождается точкой G из группы E(F_q).

     Перейдем  к рассмотрению протокола электронной  цифровой подписи. Известными считаются  эллиптическая кривая (*), в том  числе простое число p и точка G из группы E(F_p). Секретным ключем является s (mod q), а открытым - точка W=sG из E(F_p).

     Пусть вычет m (mod q) - хэш-значение подписываемого сообщения. Чтобы получить подпись  для m, необходимо выполнить следующие  шаги.

1. Выбирать случайный вычет u(mod q) ( и хранить его в секрете), где 0<u<q. Вычислить точку  
   V = uG =(x_V,y_V),  
   где представитель класса вычетов x_V выбирается из фиксированного интервала 0 < x_V < p.
2. Вычислить c=x_V (mod q) . Если c=0(mod q) , то перейти к шагу 1. В противном случае вычислить  
   d=u^-1 (m+sc)(mod q).  
   Если d=0 (mod q) , то перейти к шагу 1. В противном случае пара чисел (c,d), где 0<c,d<q есть подпись для m.

     Чтобы проверить подпись под сообщением m (хэш - значением сообщения) необходимо выполнить следующие шаги.

1. Вычислить h=d^-1 (mod q) и вычеты  
   h₁ =hm (mod q), h₂ = hc (mod q).
2. Вычисляет точку P=h₁G+h₂W =(x_P,y_P), 0 <= x_P <p.
3. Если c=x_P (mod q) , то подпись принимается, в противном случае - отвергается.

     Несложно  заметить, что эта схема, как и  новый ГОСТ является переложением стандарта DSA на эллиптические кривые. В [7] высказано  предположение о том, что этот переход связан с большими успехами специальных служб России и США  в решении задач дискретного  логарифмирования.

     Слабость  цифровой подписи ECDSA