Содержание
Назначение
При передачи электронных документов или сообщений по незащищенным каналам возникает угроза их перехвата. Злоумышленник может заполучить электронный документ, модифицировать его и отправить первоначальному адресату в целях извлечения выгоды. Чтобы избежать подобных ситуаций была разработана цифровая подпись. Правильно применённая цифровая подпись даёт получателю уверенность в том, что электронный документ достоверный и выслан указанным отправителем. Цифровая подпись для электронных документов является аналогом ручной — для бумажных носителей информации. Цифровая подпись также обеспечивает свойство неотказуемости. Это означает, что подписывающий документ не сможет впоследствии отказаться от своей подписи.
Свойства
1) Подлинность, убеждающая, что именно это лицо подписало документ.
3) Целостность подписываемого документа, т. е. невозможность изменения подписанного документа.
Симметричные схемы
Первыми, кто использовал симметричную схему цифровой подписи (см. симметричная схема цифровой подписи), были Диффи и Хеллман. Они опубликовали описание алгоритма подписи одного бита с помощью блочного шифра (см. блочный шифр). Симметричные схемы менее распространены, чем асимметричные. Асимметричные схемы цифровой подписи (см. асимметричная схема цифровой подписи) опираются на вычислительно сложные задачи. Симметричные шифры основаны на блочных шифрах.
- Стойкость симметричных схем вытекает из стойкости используемых блочных шифров, надежность которых хорошо изучена.
- Если стойкость шифра окажется недостаточной, его легко можно будет заменить на более стойкий с минимальными изменениями в реализации.
Недостатки симметричных схем:
- Нужно подписывать отдельно каждый бит передаваемой информации, что приводит к значительному увеличению подписи. Подпись может превосходить сообщение по размеру на два порядка.
- Сгенерированные для подписи ключи могут быть использованы только один раз, так как после подписывания раскрывается половина секретного ключа.
Протокол цифровой подписи с достоверным посредником
Пользователь А хочет подписать цифровое сообщение и отправить его пользователю B. Существует посредник, у которого есть ключ k_1 для секретной связи с A и ключ k_2 для секретной связи с B. Эти ключи установлены до начала протокола и могут быть использованы многократно. Шифрование происходит при помощи симметричного шифра E.
1. Отправитель A зашифровывает на ключе k_1 сообщение a для адресата B и отправляет криптограмму b посреднику.
3. Посредник формирует блок информации I = [a, b, pa], где a — расшифрованное сообщение, b — копия криптограммы, pa — идентификатор абонента A. Зашифровывает блок информации I на ключе k_2 и отправляет криптограмму c пользователю B.
Достоинства протокола:
2. Подпись не тиражируется и подписанный документ неизменяем.
Асимметричные схемы
Определение схемы цифровой подписи
Схема цифровой подписи — это совокупность вероятностных полиномиальных алгоритмов (Gen; Sign; Vrfy), удовлетворяющих следующему:
2) Алгоритм Подписания Sign принимает на вход секретный ключ sk, величину и сообщение m. На выходе получается подпись наряду с величиной , и записано, как Sign.
RSA
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSА, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.
N = p * q
Далее отправитель вычисляет число Е из условий:
и число D из условий:
Пара чисел (Е, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.
Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции (см. хэш-функция) h(M) в целое число m:
Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D:
После приема пары (М,S) получатель вычисляет хэш-значение сообидения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m’, применяя криптографическое преобразование подписи S с использованием открытого ключа Е:
Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(M):
Если соблюдается равенство вычисленных значений, т.е.
то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют «идентификатором» подписавшего.
RSA-PSS
RSA — PSS (Probabilistic signature scheme) — это вероятностная схема цифровой подписи. Вероятностный вариант схемы RSA представляет собой модификацию функций RSA с помощью рандомизированного заполнения. Схема подписи основана на функциях хэширования. В схеме RSA — PSS процедура подписания — это преобразование, использующее секрет функции RSA, так как исключительно автор владеет закрытым ключом.
Алгоритм выработки параметров
Алгоритмы подписи и проверки используют две функции хэширования. Первая функция, которая называется компрессором:
Вторая функция, которая называется генератором:
(N, e, d, G, H, k_0, k_1) — параметры цифровой подписи, где
K= k_0+k_1
Алгоритм генерации подписи
SingPss(M, d, N) =
Визуально генерацию подписи можно представить следующим образом:
Алгоритм проверки подписи
Дано: M, U, e, N
2. Представим y в виде строки бит b || w || r* || γ ;
4. Если H( M || r) = w и
b = 0
Схема подписи Рабина
Подпись Рабина базируется на криптографической системе с открытым ключом. Эта система основана на сложности вычисления квадратных корней по модулю n. При этом модуль n представляет собой произведение двух больших простых чисел. Параметры криптографической схемы Рабина:
q — простое число, секретный ключ
Формирование подписи
1. Генерируется случайная последовательность R длиной из t бит
r(i) ∈ {0,1}, i = 0, 1, …, t-1.
M||R = (m(0), m(1), m(2), …, m(k-1), r(0), r(1), …, r(t-1) ).
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´, то подпись принимается, в противном случае отвергается.
Схемы, основанные на эллиптических кривых
Группа точек эллиптической кривой (см. эллиптическая кривая), являясь первоначально абстрактным алгебраическим объектом, используется для построения алгоритмов цифровой подписи.
Эллиптическая кривая над конечным простым полем GF(p) определяется как множество пар (x,y), таких что x,y ≡ GF(p), удовлетворяющих уравнению:
Пары (x,y) называют точками. Точки эллиптической кривой можно складывать. Сумма двух точек, в свою очередь, тоже лежит на эллиптической кривой.
Множество точек эллиптической кривой вместе с нулевой точкой и с введенной операцией сложения будем называть «группой». Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико. Оценка порядка (числа элементов) группы точек эллиптической кривой m такова: p + 1 — 2√p ≤ m ≤ p + 1 + 2√p, где р — порядок поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2^512, то в случае эллиптической кривой достаточно взять p > 2^255.
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
Параметры цифровой подписи
Параметрами схемы цифровой подписи являются:
— эллиптическая кривая E, задаваемая своим инвариантом J(Е) или коэффициентами a, b ;
— простое число q — порядок циклической подгруппы группы точек эллиптической кривой E, для которого выполнены следующие условия:
— точка P O эллиптической кривой Е, с координатами , удовлетворяющая равенству qP=O.
Каждый пользователь схемы цифровой подписи должен обладать личными ключами:
— ключом проверки подписи — точкой эллиптической кривой Q с координатами , удовлетворяющей равенству dP = Q. К приведенным выше параметрам схемы цифровой подписи предъявляют следующие требования:
— должно быть выполнено неравенство mp;
Двоичные векторы
Для определения процессов формирования и проверки цифровой подписи необходимо установить соответствие между целыми числами и двоичными векторами длины l бит.
(10)
Число соответствует двоичному вектору , если выполнено равенство
Для двух двоичных векторов
соответствующих целым числам и , операция конкатенации (объединения) определяется следующим образом:
Объединение представляет собой двоичный вектор длиной 2l бит, составленный из коэффициентов векторов .
Основные процессы
Для реализации данных процессов необходимо, чтобы всем пользователям были известны параметры схемы цифровой подписи, соответствующие параметрам схемы цифровой подписи.
Схема формирования цифровой подписи
Схема процесса проверки цифровой подписи
Цифровая подпись Эль-Гамаля
Генерация параметров (ключа)
1. Выбрать случайное простое число p.
3. Выбрать x_A — секретное целое число, удовлетворяющее условию x_A < p — 1
Таким образом, (g, y, p) — параметры открытого ключа. x_A — закрытый ключ.
Генерация подписи
Для цифровой подписи сообщения m пользователь А генерирует случайное число l такое, что l < p — 1 и НОД(l, p-1) = 1, и формирует пару (r,s), где
l^(-1) можно найти с помощью алгоритма Евклида
Проверка подписи
Пользователь B должен убедиться, что параметры открытого ключа действительно принадлежат действительно пользователю A. С этой целью пользователь Б приминяет к паре (m, (r, s)) следующую процедуру проверки:
Атаки и предостережения
Атака № 1
1. u = m’m^(-1) (mod p-1).
3. Вычисляется r’, удовлетворяющее условию r’ ≡ ru(mod p-1) и r’ ≡ r(mod p). Это можно сделать с помощью китайской теоремы об остатках.
Предостережение
Атака № 2
Злоумышленник генерирует параметр g следующим образом g = β^t(mod p), где β = cq и c < b. Таким образом, вычисление дискретного логарифма не создаёт трудностей, и он равен z ≡ x_A (mod b), т.е. выполняется следующее сравнение:
Вычислив z, злоумышленник может подделать подпись пользователя A:
s = t(m — cqz) (mod p-1)
Необходимо проверять на этапе проверки цифровой подписи, насколько случайным является параметр g.
Одноразовая подпись Лампорта
Это особый вид подписи. Одноразовая подпись остаётся безопасной при её одноразовом использовании для какого-то конкретного сообщения. Повторное использование является небезопасным. В основе одноразовой подписи Лампорта лежит использование однонаправленной функции.
Генерация параметров
На вход подаётся сообщение m длиной l бит.
1. Выбираются случайно x_i,0 x_i,1 из {0, 1}.
Формируются открытый(pk) и закрытый(sk) ключи:
Генерация подписи
Каждый бит сообщения 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).
Глоссарий
- Цифровая подпись
- Симметричная схема цифровой подписи
- Асимметричная схема цифровой подписи
- Эллиптическая кривая
- Хэш-функция
- Гладкое число
- Блочный шифр
Библиографический указатель
Перейти к списку литературы.
Практическое задание
Доступно для скачивания приложение, демонстрирующее пример получения электронной подписи основанной на схеме Эль-Гамаля: File:Elgamal.zip Серёгина Елена, Амбарян Арусяк 2014
Павлов П., Кочетов П., 2013.
Источник