(2.1)
Таким образом, каждый пользователь
получает пару (закрытый ключ; открытый
ключ) = (Хi, Yi). Открытые
ключи пользователей[8] могут храниться
в общей базе системы распределения ключей
и при необходимости предоставляться
всем абонентам системы.
Сообщение, предназначенное
для подписи, должно быть представлено
в виде числа, меньшего модуля Р. При большом
размере сообщение разбивается на блоки
необходимого размера. В некоторых случаях
подписывается не само сообщение, а значение
хеш-функции от него. В любом варианте
цифровая подпись вычисляется в зависимости
от некоторого числа m (m < P).
Пусть пользователь 1 хочет
подписать свое сообщение цифровой подписью
и передать его пользователю 2. В этом случае
алгоритм действий следующий:
Первый пользователь выбирает
случайное секретное число k, взаимно простое
с Р-1, и вычисляет число а
(2.2)
Затем с помощью расширенного
алгоритма Евклида необходимо найти значение b в следующем уравнении:
m = (X1 * a +k * b) mod (P-1)
(2.3)
Пара чисел (a, b) будет цифровой
подписью сообщения m.
Сообщение m вместе с подписью
(a, b) отправляется пользователю 2.
Пользователь 2 получает сообщение
m и с использованием открытого ключа первого
абонента Y1 вычисляет два числа по следующим формулам:
(2.4)
Если с1 = с2, то цифровая
подпись первого пользователя верная.
Для подписывания каждого нового сообщения
должно каждый раз выбираться новое значение
k.
Подписи, созданные с использованием
алгоритма Эль-Гамаля[8], называются рандомизированными,
так как для одного и того же сообщения
с использованием одного и того же закрытого
ключа каждый раз будут создаваться разные
подписи (a,b), поскольку каждый раз будет
использоваться новое значение k. Подписи,
созданные с применением алгоритма RSA[8],
называются детерминированными, так как
для одного и того же сообщения с использованием
одного и того же закрытого ключа каждый
раз будет создаваться одна и та же подпись.
2.1.1 Формирование и проверка
подписи EGSA
Пусть абоненты, обменивающиеся
через Интернет зашифрованными сообщениями,
имеют следующие общие параметры: Р = 11,
А = 7.
Один из пользователей этой
системы связи хочет подписать свое сообщение
m=5 цифровой подписью, сформированной
по алгоритму Эль-Гамаля. Вначале он должен
выбрать себе закрытый ключ, например,
Х1=3 и сформировать
открытый ключ Y1 = 73 mod 11 = 2. Открытый
ключ может быть передан всем заинтересованным
абонентам или помещен в базу данных открытых
ключей системы связи.
Затем пользователь выбирает
случайное секретное число k, взаимно простое
с Р-1. Пусть k=9 ( 9 не имеет общих делителей
с 10 ). Далее необходимо вычислить число
(2.5)
После этого с помощью расширенного
алгоритма Евклида находится значение
b в уравнении:
(2.6)
Решением последнего уравнения
будет значение b=9.
Таким образом, пара чисел (8,
9) будет цифровой подписью сообщения m=5.
Если любой другой пользователь
сети желает проверить цифровую подпись
в сообщении, он должен получить из базы
данных[8] открытый ключ первого пользователя
(он равен 2 ), вычислить два числа с1 и с2 и сравнить
их.
(2.7)
Так как с1 = с2, то цифровая
подпись первого пользователя в сообщения
m=5 верная.
2.2 Стандарт ЭЦП DSS
В 1991 г. NIST (National Institute of Standards
and Technology) [8] предложил для обсуждения
проект стандарта ЭЦП DSS (Digital Signature Standard),
использующий алгоритм DSA (Digital Signature Algorithm).
Стойкость данного алгоритма основана
на сложности решения задачи дискретного
логарифмирования в мультипликативной
группе простого поля[8] F(/p). Цифровая подпись
служит для установления изменений данных
и для установления подлинности подписавшейся
стороны. Получатель подписанных данных
может использовать цифровую подпись
для доказательства третьей стороне факта,
что подпись действительно сделана отправляющей
стороной.
2.2.1 Подход DSS
DSS использует алгоритм[8], который
разрабатывался для использования только
в качестве цифровой подписи. В отличие
от RSA, его нельзя использовать для шифрования
или обмена ключами. Тем не менее, это технология
открытого ключа.
Рассмотрим отличия подхода,
используемого в DSS для создания цифровых
подписей, от применения таких алгоритмов
как RSA.
Рис. 2.2.1.1. Создание и проверка подписи
с помощью алгоритма RSA
Рис. 2.2.1.2. Создание и проверка подписи
с помощью стандарта DSS
Подход DSS использует сильную
хэш-функцию. Хэш-код[8] является входом
функции подписи вместе со случайным числом
k, созданным для этой конкретной подписи.
Функция подписи также зависит от закрытого
ключа отправителя KRa и множества
параметров, известных всем участникам.
Можно считать, что это множество состоит
из глобального открытого ключа KUG. Результатом
является подпись, состоящая из двух компонент,
обозначенных как s и r.
Для проверки[8] подписи получатель
также создает хэш-код полученного сообщения.
Этот хэш-код вместе с подписью является
входом в функцию верификации. Функция
верификации[8] зависит от глобального
открытого ключа KUG и от открытого
ключа отправителя KUa. Выходом функции
верификации является значение, которое
должно равняться компоненте r подписи,
если подпись корректна. Функция подписи
такова, что только отправитель, знающий
закрытый ключ, может создать корректную
подпись.
2.2.2 Формирование и проверка
подписи DSS
1. Отправитель А сообщения Μ
предоставляет широкому кругу абонентов
(получателей его сообщений) доступ к следующим
параметрам:
p — простое число, 2(\512) < р<
2(\1024), битовая
длинам кратна 64;
q — простое число, 2(\159) <р< 2(\160), и делитель
р-1
g=h(\((p-1)/q))(mod p) (2.8)
где h — такое целое число, что
0 < h < p и h(\((p-1)/q)) (mod p) > 1;
у — открытый ключ, сформированный
по правилу у = a(\x)(mod p). Здесь x — секретный
ключ, известный только А, причем 0 < x
< q;
Η (Μ) — хэш-функция, которая
по исходному сообщению Μ формирует целое
число в диапазоне от 1 до q
2. Пользователь А генерирует
случайное число к такое, что 0 < к < q,
держит его в секрете и уничтожает сразу
после получения подписи.
3. А находит два числа r и s по
следующему правилу:
r=(g(\k)(mod p))(mod q) (2.9)
s=k(\-1)(xr+H(M))(mod q) (2.10)
Подписью к сообщению Μ является
пара (r, s).
Проверка подписи. Пользователь
В получает от А сообщение M’ и подпись
(r’,s’) к нему. B должен убедиться, что Μ
совпадает с M’. Для этого:
1) если хотя бы одно из условий
0<s’<q, 0<r’<q не выполняется, то подпись
считается недействительной;
2) В находит v=(s’)(\-1) mod q (2.11)
3) В вычисляет z(/-1)=H(M’)v(mod q), z(/2)=r’v(mod q) (2.12)
4) далее вычисляется u=(g(\z(/1))y(\z(/2))(mod p))(mod q) (2.13)
5) В проверяет условие r’=u Если
оно выполняется, то подпись считается
подлинной и сообщение не измененным,
т.е. M’= М.
2.3 Стандарт ЭЦП DSA
В 1991 г. в США был опубликован
проект федерального стандарта цифровой
подписи - DSS (Digital Signature Standard, [DSS91], описывающий
систему цифровой подписи DSA (Digital Signature
Algorithm) [8]. Одним из основных критериев
при создании проекта была его патентная
чистота.
Предлагаемый алгоритм DSA, имеет,
как и RSA, теоретико-числовой характер,
и основан на криптографической системе
Эль-Гамаля в варианте Шнорра. Его надежность
основана на практической неразрешимости
определенного частного случая задачи
вычисления дискретного логарифма. Современные
методы решения этой задачи имеют приблизительно
ту же эффективность, что и методы решения
задачи факторизации; в связи с этим предлагается
использовать ключи длиной от 512 до 1024
бит [8] с теми же характеристиками надежности,
что и в системе RSA. Длина подписи в системе
DSA меньше, чем в RSA, и составляет 320 бит
[8].
С момента опубликования проект
получил много критических отзывов, многие
из которых были учтены при его доработке.
Одним из главных аргументов против DSA
является то, что, в отличие от общей задачи
вычисления дискретного логарифма[8], ее
частный случай, использованный в данной
схеме, мало изучен и, возможно, имеет существенно
меньшую сложность вскрытия. Кроме того,
стандарт не специфицирует способ получения
псевдослучайных чисел, используемых
при формировании цифровой подписи, и
не указывает на то, что этот элемент алгоритма
является одним из самых критичных по
криптографической стойкости.
Функции DSA ограничены только
цифровой подписью, система принципиально
не предназначена для шифрования данных.
По быстродействию система DSA сравнима
с RSA [8] при формировании подписи, но существенно
(в 10-40 раз) уступает ей при проверке подписи.
Вместе с проектом DSS опубликован
проект стандарта SHS (Secure Hash Standard), описывающий
однонаправленную хэш-функцию SHA (Secure Hash
Algorithm), рекомендованную для использования
вместе с DSA. Хэш-функция SHA является модификацией
алгоритма MD4 [8], хорошо известного в криптографической
литературе.
2.3.1 Формирование и проверка подписи
DSА
При генерации ЭЦП используются параметры
трех групп:
- общие параметры
- секретный ключ
- открытый ключ
Общие параметры необходимы для функционирования
системы в целом. Секретный ключ используется
для формирования ЭЦП, а открытый - для
проверки ЭЦП. Общими параметрами системы
являются простые целые числа p,q,g, удовлетворяющие
следующим условиям:
p: 2^511<p<2^512
q: простой делитель числа (p-1), который
удовлетворяет условию
2^159<q<2^160
g: так называемый генератор, удовлетворяющий
равенству:
g=h^((p-1)/q)mod p >1. (2.14)
Параметры p,q,g публикуются для всех участников
обмена ЭД с ЭЦП. Секретный ключ x случайно
выбирается из диапазона [1,q] и держится
в секрете.
Открытый ключ вычисляется:
y=g^x mod p. (2.15)
Также при описании данной схемы будут
использоваться следующие обозначения
и дополнительные параметры: m - входное
сообщение пользователя для схемы с ЭЦП;
k - случайное число, удовлетворяющее условию
0<k<q, хранящееся в секрете и меняющееся
от одной подписи к другой; H - хэш-функция,
h - хэш-код сообщения.
Процесс генерации ЭЦП состоит из нескольких
этапов:
1.Вычисляется хэш-код сообщения m h=H(m)
2.Из диапазона [1,q] случайным образом выбирается
значение k и вычисляется r= (g^k mod p) mod q (2.16)
3. Вычисляется S= (k^-1(h+xr)) mod q,
(2.17)
где k^-1 удовлетворяет условию (k^-1*k) mod q
=1
Значения r,s являются ЭЦП сообщения m
и передаются вместе с ним по каналам связи.
Проверка ЭЦП. Пусть принято сообщение
m1 и его подпись s1,r1.
Проверка ЭЦП происходит следующим образом:
- проверяется выполнение условий 0<r1<q,
0<s1<q, и если хотя бы одно из них нарушено,
подпись отвергается.
- Вычисляются значения:
w= s1^-1 mod q (2.18)
u1 = (H(m1)w) mod q (2.19)
u2 = ((r1/w) mod q (2.20)
v = (( g^u1y^u2) mod p ) mod q (2.21)
- проверяется равенство v = r1
Если последнее равенство выполняется,
то подпись принимается. В данном стандарте
специфицируется также процедура генерации
основных параметров системы и проводится
доказательство того, что если v=r1, то m1=m,
r1=r, s1=s.
- РАЗРАБОТКА ПРОГРАММНОГО КОДА.
- Электронная цифровая подпись по Эль-Гамалю
Для выполнения курсовой работы
я использовал Adobe Flash с реализацией
интерфейса через ActionScript 3.0.
Для получения рабочей электронной цифровой
подписи по Эль-Гамалю мне было необходимо
реализовать в программе хеширование.
В алгоритме программы функция хеширования
описывается подобным образом:
var m:Number = 0;
var osn:Number = 0;
var M:String;
var arr_o:Array = new Array();
key_hesh.addEventListener(MouseEvent.CLICK, get_hesh)
function get_hesh(e:MouseEvent):void
{
M = otkritii.text;
for (var ind_1:Number = 0; ind_1 < M.length; ind_1++)
{ arr_o.push(M.charCodeAt(ind_1)); }
//РЕАЛИЗАЦИЯ ФУНКЦИИ ХЕШИРОВАНИЯ
for(var ind_2:Number = 0; ind_2 < M.length; ind_2++)
{osn = Math.pow(arr_o[ind_2], m) % 256;
m = ((osn + arr_o[ind_2]) % 30) + 2;}
hesh.text = String(m);
for (var ind_3:Number = 0; ind_3 < M.length; ind_3++)
{ arr_o.pop(); }
}
В следующей части программы
я реализовал объявление переменных в
области от 1381 до 3989.
Теперь я приступил к реализации
самой электронной цифровой подписи:
for(var gli:Number = 1; gli > 0; gli++)
{
//ГЕНЕРАЦИЯ ПАРАМЕТРОВ P
И G
ind = Math.floor(Math.random()*330);
P = prostie_chisla[ind];
gua_1 = (P - 1);
gua_2 = (P - 3);
var pre_3:Number = 0;
var pre_4:Number = 0;
for( G = 1; G < P - 1; G++)
{
for(var i_on1:Number = 0; i_on1 < (P - 1); i_on1++)
{
on_G1 = on_G1 * G;
on_G1 = on_G1 % P;
}
if( on_G1 == 1)
{
pre_3 = 1;
}
if( on_G1 != 1)
{
pre_3 = 0;
}
on_G1 = 1;
for(var l:Number = 1; l < P - 2; l++)
{
for(var i_on2:Number = 0; i_on2 < l; i_on2++)
{
on_G2 = on_G2 * G;
on_G2 = on_G2 % P;
}
if( on_G2 == 1)
{
pre_4 = 0;
break;
}
if( on_G2 != 1)
{
pre_4 = 1;
}
on_G2 = 1;
}
if( pre_3 == 1 && pre_4 == 1)
{
break;
}
}
//ГЕНЕРАЦИЯ X И К И ВЫЧИСЛЕНИЕ
Y
X = Math.floor(Math.random()*gua_2) + 2;
for(var i_Y:Number = 0; i_Y < X; i_Y++)
{
on_Y = on_Y * G;
on_Y = on_Y % P;
}
Y = on_Y % P;
for(var l_1:Number = 1; l_1 > 0; l_1++)
{
K = Math.floor(Math.random()*gua_2) + 2;
nod_a = P - 1;
nod_b = K;
for(var l_2:Number = 1; l_2 > 0; l_2++)
{
if((nod_a != 0) || (nod_b != 0))
{
if(nod_a > nod_b)
{
nod_a = nod_a % nod_b;
}
else nod_b = nod_b % nod_a;
}
if((nod_a == 0) || (nod_b == 0))
{
nod = nod_a + nod_b;
break;
}
}
if(nod == 1)
{
break;
}}
//ВЫЧИСЛЕНИЕ ПАРАМЕТРОВ
ПОДПИСИ
for(var i_a:Number = 0; i_a < K; i_a++)
{
on_a = on_a * G;
on_a = on_a % P;
}
a = on_a % P;
for(var b:Number = 1; b > 0; b++)
{
on_b1 = X*a + K*b;
on_b2 = on_b1 % (P - 1);
if(m == on_b2)
{
break;
}}
for(var i_par1:Number = 0; i_par1 < a; i_par1++)