Схемы цифровой подписи

From CryptoWiki
Jump to: navigation, search

Contents

Назначение

При передачи электронных документов или сообщений по незащищенным каналам возникает угроза их перехвата. Злоумышленник может заполучить электронный документ, модифицировать его и отправить первоначальному адресату в целях извлечения выгоды. Чтобы избежать подобных ситуаций была разработана цифровая подпись. Правильно применённая цифровая подпись даёт получателю уверенность в том, что электронный документ достоверный и выслан указанным отправителем. Цифровая подпись для электронных документов является аналогом ручной – для бумажных носителей информации. Цифровая подпись также обеспечивает свойство неотказуемости. Это означает, что подписывающий документ не сможет впоследствии отказаться от своей подписи.

Свойства

1) Подлинность, убеждающая, что именно это лицо подписало документ.

2) Уникальность, так как и ручная подпись - часть документа, которую нельзя переместить на другие документы. То есть у любого отдельного документа будет своя уникальная цифровая подпись.

3) Целостность подписываемого документа, т. е. невозможность изменения подписанного документа.

4) Неотказуемость от авторства или согласия с содержимым документа, от подписи в дальнейшем нельзя отказаться.

Симметричные схемы

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

Симметричные схемы имеют следующие преимущества:

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

Недостатки симметричных схем:

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

Протокол цифровой подписи с достоверным посредником

Пользователь А хочет подписать цифровое сообщение и отправить его пользователю B. Существует посредник, у которого есть ключ k_1 для секретной связи с A и ключ k_2 для секретной связи с B. Эти ключи установлены до начала протокола и могут быть использованы многократно. Шифрование происходит при помощи симметричного шифра E.

Протокол:

1. Отправитель A зашифровывает на ключе k_1 сообщение a для адресата B и отправляет криптограмму b посреднику.

2. Посредник расшифровывает криптограмму b, используя ключ k_1.

3. Посредник формирует блок информации I = [a, b, pa], где a - расшифрованное сообщение, b - копия криптограммы, pa - идентификатор абонента A. Зашифровывает блок информации I на ключе k_2 и отправляет криптограмму c пользователю B.

4. B расшифровывает блок информации I, используя ключ k_2. B получил сообщение a и сертификат посредника pa, удостоверяющий, что сообщение пришло именно от A.

Достоинства протокола:

1. Только посредник и отправитель A имеют секретный ключ k_1, поэтому только A может отправить посреднику сообщение, зашифрованное на ключе k_1.(защита ЦП от подделки)

2. Подпись не тиражируется и подписанный документ неизменяем.

3. От этой подписи нельзя отречься (неотказуемость).

Асимметричные схемы

Определение схемы цифровой подписи

Схема цифровой подписи - это совокупность вероятностных полиномиальных алгоритмов (Gen; Sign; Vrfy), удовлетворяющих следующему:

1) Алгоритм генерации ключа Gen принимает на вход секретный параметр ScreenShot 2.png и на выходе выдает (pk; sk; s0) - открытый ключ, секретный ключ и начальное состояние соответственно. Предположим, что ScreenShot 12.png и что n может быть вычислено из pk.

2) Алгоритм Подписания Sign принимает на вход секретный ключ sk, величину ScreenShot 15.png и сообщение m. На выходе получается подпись ScreenShot 18.png наряду с величиной ScreenShot 16.png, и записано, как ScreenShot 13.pngSignScreenShot 14.png.

3) Детерминированный алгоритм проверки подписи Vrfy принимает в качестве входных данных открытый ключ pk, сообщение m и подпись ScreenShot 18.png. В качестве выходных данных выступает бит b, и записывается, как ScreenShot 17.pngVrfyScreenShot 19.png.

RSA

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

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа p и q, затем находит их произведение

N = p * q

и значение функции f(N) = (p - 1)(q - 1).

Далее отправитель вычисляет число Е из условий:

E <= f(N), НОД(Е, f(N)) = 1

и число D из условий:

D < N, E*D сравнимо с единицей по модулю f(N).

Пара чисел (Е, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.

Обобщенная схема формирования и проверки цифровой подписи RSА

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

m = h(М).

Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D:

S = (m^D)(mod N). Пара (М,S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

После приема пары (М,S) получатель вычисляет хэш-значение сообидения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа Е:

m' = (S^E)(mod N).

Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(M):

m = h(М).

Если соблюдается равенство вычисленных значений, т.е.

(S^E)(mod N ) = h ( М ),

то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют "идентификатором" подписавшего.

RSA-PSS

RSA - PSS (Probabilistic signature scheme) - это вероятностная схема цифровой подписи. Вероятностный вариант схемы RSA представляет собой модификацию функций RSA с помощью рандомизированного заполнения. Схема подписи основана на функциях хэширования. В схеме RSA - PSS процедура подписания - это преобразование, использующее секрет функции RSA, так как исключительно автор владеет закрытым ключом.


Алгоритм выработки параметров

Алгоритмы подписи и проверки используют две функции хэширования. Первая функция, которая называется компрессором:

                         F 1.png

Вторая функция, которая называется генератором:

                         F 2.png

(N, e, d, G, H, k_0, k_1) - параметры цифровой подписи, где

(N, e, d) - параметры ключа RSA, причем (N, e) - открыты, а d = e^(-1)(mod φ(N)) - закрыто.

K= k_0+k_1

Алгоритм генерации подписи

SingPss(M, d, N) =

  r = u{0,1}^k0; w = H(M || r); r* = G_1(w) XOR r;
  y = 0 || w || r* || G_2(w);
  return (U = y^d(mod N)).

Визуально генерацию подписи можно представить следующим образом:


Алгоритм генерации цифровой подписи RSA PSS
Алгоритм проверки подписи

Дано: M, U, e, N

1. U^e (mod N) = y;

2. Представим y в виде строки бит b || w || r* || γ ;

3. r = r* XOR G_1(w);

4. Если H( M || r) = w и

G_2(w) = γ и

b = 0

то цифровая подпись корректна

Схема подписи Рабина

Подпись Рабина базируется на криптографической системе с открытым ключом. Эта система основана на сложности вычисления квадратных корней по модулю n. При этом модуль n представляет собой произведение двух больших простых чисел. Параметры криптографической схемы Рабина:

p – простое число, p ≡ 3 mod 4, p – секретный ключ;

q – простое число, секретный ключ

n = pq – открытый ключ криптографической системы.

Формирование подписи

1. Генерируется случайная последовательность R длиной из t бит

R = (r(0), r(1), …, r(t-1)),

r(i) ∈ {0,1}, i = 0, 1, …, t-1.

2. Сообщение M объединяется с последовательностью R

M||R = (m(0), m(1), m(2), …, m(k-1), r(0), r(1), …, r(t-1) ).

3. Последовательности битов M||R ставится в соответствии число a < n.

4. Проверяются условия a ^((p-1)/2) ≡ 1 mod p, a ^((q-1)/2) ≡ 1 mod q. 5. Если условия не выполняется, то перейти на шаг 1. 6. Вычисляются значения z ≡ a(p+1)/4 mod p, z ≡ a(q+1)/4 mod q. 7. По китайской теореме об остатках вычисляется значение Z = a ^(1/2) mod n. 8. Формируется подпись из пары чисел (R, Z) к сообщению M.

Проверка подписи

1. Вычисляется значение a´ a´ ≡ Z^2 mod n. 2. Если a=a´, то подпись принимается, в противном случае отвергается.

Схемы, основанные на эллиптических кривых

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

Можно наложить ограничения на множество значений переменных х, y, и коэффициентов a, b, c. Ограничивая область определения уравнения значимым для приложений числовым множеством (полем) мы получим эллиптическую кривую, заданную над рассматриваемым полем.

Общий вид эллиптической кривой, определенной на множестве действительных чисел

Эллиптическая кривая над конечным простым полем GF(p) определяется как множество пар (x,y), таких что x,y ≡ GF(p), удовлетворяющих уравнению:

y^2 = x^3 + ax + b mod p, a, b ≡ GF(p)


Пары (x,y) называют точками. Точки эллиптической кривой можно складывать. Сумма двух точек, в свою очередь, тоже лежит на эллиптической кривой.

Кроме точек, лежащих на эллиптической кривой, рассматривается также нулевая точка. Считается, что сумма двух точек – A с координатами (x', y') и B с координатами (x*,y*) – равна 0, если x' = x*, y' = –y* (mod p). Нулевая точка не лежит на эллиптической кривой, но, тем не менее, участвует в вычислениях. Ее можно рассматривать как бесконечно удаленную точку.

Множество точек эллиптической кривой вместе с нулевой точкой и с введенной операцией сложения будем называть «группой». Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико. Оценка порядка (числа элементов) группы точек эллиптической кривой m такова: p + 1 – 2√p ≤ m ≤ p + 1 + 2√p, где р – порядок поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2^512, то в случае эллиптической кривой достаточно взять p > 2^255.

Важную роль в алгоритмах подписи с использованием эллиптических кривых играют «кратные» точки. Точка Q называется точкой кратности k, если для некоторой точки P k раз выполнено равенство:

P = Q + Q + Q + … + Q = kQ Если для некоторой точки P существует такое число k, что kP = 0, это число называют порядком точки P. Кратные точки эллиптической кривой являются аналогом степеней чисел в простом поле. Задача вычисления кратности точки эквивалентна задаче вычисления дискретного логарифма. Собственно, на сложности вычисления «кратности» точки эллиптической кривой и основана надежность цифровой подписи. Хотя эквивалентность задачи дискретного логарифмирования и задачи вычисления кратности и доказана, вторая имеет большую сложность. Секретным ключом, как и раньше, положим некоторое случайное число x. Открытым ключом будем считать координаты точки на эллиптической кривой P, определяемую как P = xQ, где Q — специальным образом выбранная точка эллиптической кривой («базовая точка»). Координаты точки Q вместе с коэффициентами уравнения, задающего кривую, являются параметрами схемы подписи и должны быть известны всем участникам обмена сообщениями. Выбор точки Q зависит от используемых алгоритмов и весьма непрост. Так, стандарт ГОСТ 34.10-2001 определяет, что точка Q должна иметь порядок q, где q — простое число с «хорошими алгебраическими свойствами». Число q довольно велико (2254 < q < 2256). При построении конкретного алгоритма, реализующего вычисление цифровой подписи, американский стандарт предполагает использование алгоритма DSA. Новый российский стандарт использует модифицированную версию старого ГОСТ Р 34.10-94.

ГОСТ Р 34.10-2012

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

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

– простое число p - модуль эллиптической кривой;

– эллиптическая кривая E, задаваемая своим инвариантом J(Е) или коэффициентами a, b ;

– целое число m – порядок группы точек эллиптической кривой E;

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

ScreenShot 22.png;

– точка P ScreenShot 25.png O эллиптической кривой Е, с координатами ScreenShot 23.png, удовлетворяющая равенству qP=O.

– хэш–функция ScreenShot 26.png, отображающая сообщения, представленные в виде двоичных векторов произвольной конечной длины, в двоичные вектора длины l бит. Хэш-функция определена в ГОСТ Р 34.11. Если ,2^254 < q < 2^256 то l = 256. Если , 2^508 < q < 2^512 то l = 512.

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

– ключом подписи – целым числом d, удовлетворяющим неравенству 0 < d < q;

– ключом проверки подписи – точкой эллиптической кривой Q с координатами ScreenShot 24.png, удовлетворяющей равенству dP = Q. К приведенным выше параметрам схемы цифровой подписи предъявляют следующие требования:

– должно быть выполнено условие, для всех целых t = 1, 2, … B, где B = 31, если 2^254< q < 2^256, и B = 131, если 2^508 < q < 2^512;

– должно быть выполнено неравенство mScreenShot 25.pngp;

– инвариант кривой должен удовлетворять условию J(Е)ScreenShot 25.png0 и J(E)ScreenShot 25.png1728.

Двоичные векторы

Для определения процессов формирования и проверки цифровой подписи необходимо установить соответствие между целыми числами и двоичными векторами длины l бит.

Рассмотрим следующий двоичный вектор длиной l бит, в котором младшие биты расположены справа, а старшие – слева:

ScreenShot 27.png (10)

где ScreenShot 28.png, i= 0 ,..,l - 1 равно либо 1, либо 0.

Число соответствует двоичному вектору ScreenShot 29.png, если выполнено равенство

ScreenShot 30.png

Для двух двоичных векторов

ScreenShot 32.png (*)

соответствующих целым числам и , операция конкатенации (объединения) определяется следующим образом:

ScreenShot 34.png (**)

Объединение представляет собой двоичный вектор длиной 2l бит, составленный из коэффициентов векторов ScreenShot 35.png .

Формулы (*) и (**) определяют способ разбиения двоичного вектора длиной 2l бит на два двоичных вектора длиной l бит, конкатенацией которых он является.

Основные процессы

В данном разделе определены процессы формирования и проверки цифровой подписи под сообщением пользователя.

Для реализации данных процессов необходимо, чтобы всем пользователям были известны параметры схемы цифровой подписи, соответствующие параметрам схемы цифровой подписи.

Кроме того, каждый пользователь должен иметь ключ подписи d и ключ проверки подписи ScreenShot 38.png, которые также должны соответствовать параметрам схемы цифровой подписи.

Схема формирования цифровой подписи
Схема формирования цифровой подписи
Схема процесса проверки цифровой подписи
Схема процесса проверки цифровой подписи

Цифровая подпись Эль-Гамаля

Генерация параметров (ключа)

1. Выбрать случайное простое число p.

2. Вычислить случайный мультипликативный порождающий элемент F 4.png

3. Выбрать x_A - секретное целое число, удовлетворяющее условию x_A < p - 1

4. Вычислить y_A = g^x_A (mod p)

Таким образом, (g, y, p) - параметры открытого ключа. x_A - закрытый ключ.

Генерация подписи

Для цифровой подписи сообщения m пользователь А генерирует случайное число l такое, что l < p - 1 и НОД(l, p-1) = 1, и формирует пару (r,s), где

F 5.png

l^(-1) можно найти с помощью алгоритма Евклида

Проверка подписи

Пользователь B должен убедиться, что параметры открытого ключа действительно принадлежат действительно пользователю A. С этой целью пользователь Б приминяет к паре (m, (r, s)) следующую процедуру проверки:

F 6.png

Атаки и предостережения

Атака №1

Эта атака была изобретена Блайнбахером. В случае если r > p, злоумышленник может подделать новую подпись произвольно сообщения m' следующим образом:

1. u = m'm^(-1) (mod p-1).

2. s' = su(mod p-1).

3. Вычисляется r', удовлетворяющее условию r' ≡ ru(mod p-1) и r' ≡ r(mod p). Это можно сделать с помощью китайской теоремы об остатках.

Затем злоумышленник выполняет следующие операции:

F 7.png

Атака невозможна, если r < p, потому что в этом случае r', вычисляемое на третьем шаге китайской теоремы об остатках по величине сравнимо с p(p-1).

Предостережение

При проверки цифровой подписи, в первую очередь, необходимо проверить r < p.


Атака №2

Атака изобретена Блайхенбахером. Параметр g может быть выбран не пользователем А. Предположим, что g и p выбраны злоумышленником. p может быть выбрано следующим образом: p-1 = bq, где q - большое простое число, а b - гладкое число ( в таком случае дискретный логарифм в группе порядка b легко вычисляется)

Злоумышленник генерирует параметр g следующим образом g = β^t(mod p), где β = cq и c < b. Таким образом, вычисление дискретного логарифма не создаёт трудностей, и он равен z ≡ x_A (mod b), т.е. выполняется следующее сравнение:

F-8.png

Вычислив z, злоумышленник может подделать подпись пользователя A:

r = β = cq

s = t(m - cqz) (mod p-1)

Затем,

F 9.png

Предостережение

Необходимо проверять на этапе проверки цифровой подписи, насколько случайным является параметр g.

Одноразовая подпись Лампорта

Это особый вид подписи. Одноразовая подпись остаётся безопасной при её одноразовом использовании для какого-то конкретного сообщения. Повторное использование является небезопасным. В основе одноразовой подписи Лампорта лежит использование однонаправленной функции.

Генерация параметров

На вход подаётся сообщение m длиной l бит.

Для каждого бита i выполняются следующие операции:

1. Выбираются случайно x_i,0 x_i,1 из {0, 1}.

2. Вычисляется по однонаправленной функции f y_i,0 = f(x_i,0) и y_i,1 = f(x_i,1).

Формируются открытый(pk) и закрытый(sk) ключи:

F 10.png

Генерация подписи

Каждый бит сообщения m = m_1 m_2 ... m_l заменяется в соответствии с секретным ключом и получается подпись σ = (x_1,m_1 ; x_2,m_2; ... ; x_l,m_l). Таким образом, вместо i-ого бита ставится x_i,m_i значение ключа sk.

Проверка подписи

Известны открытый ключ pk, сообщение m и подпись σ = (x_1, ... , x_l).

Для каждого бита i сообщения m проверяется выполняется ли следующее условие : f(x_i) = y_i,m_i. Если условие выполняется для всех битов сообщения, то цифровая подпись считается корректной.

Глоссарий

Библиографический указатель

Перейти к списку литературы.

Практическое задание

Доступно для скачивания приложение, демонстрирующее пример получения электронной подписи основанной на схеме Эль-Гамаля:
File:Elgamal.zip Серёгина Елена, Амбарян Арусяк 2014

Доступно для скачивания приложение, демонстрирующее пример получения электронной подписи с доказуемостью подделки (C#):
File:FSS 1 .zip Исупова Ольга 2015




Павлов П., Кочетов П., 2013.