Схема цифровой подписи Эль Гамаля и ее модификации.

Схема Эль-Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле.

Пусть Алиса собирается подписывать документы. Алиса выбирает большое простое число р и целое число g, такое, что раз­личные степени g это различные числа по модулю р. Эти числа передаются или хранятся в открытом виде и могут быть общими для целой группы пользователей. Алиса выбирает случай­ное число х: , которое она держит в секрете. Это ее секретный ключ, только она его знает. Затем она вычисляет число

Это число y Алиса публикует в качестве своего открытого ключа. Заметим, что при больших p, зная y, невозможно найти x (это за­дача дискретного логарифмирования).

Теперь Алиса может подписывать сообщения. Допустим, она хо­чет подписать сообщение . Опишем последователь­ность действий для построения подписи.

Вначале Алиса вычисляет значение хеш-функции , ко­торое должно удовлетворять неравенству . Затем Алиса выбирает случайно число k: , взаимно простое с , и вычисляет число .

Далее Алиса вычисляет числа

Под подразумевается число, удовлетворяющее уравнению .

Такое существует, так как k и p-1 взаимно просты, и может быть найдено по обобщенному алгоритму Евклида. Наконец, Алиса формирует подписанное сообщение

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

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

Многочисленные модификации алгоритма Эль Гамаля связаны с несколь­кими шагами алгоритма. Во-первых, существует возможность при неболь­шом изменении формул выполнять все вычисления не по модулю р, а по модулю q, являющемуся наибольшим простым делителем р. Во-вторых, формула, вовлекающая секретный ключ и контрольную сумму(хеш-функцию) документа и выглядящая в базовом варианте как h = ks + xr является не единственно возможным соотношением. Другие формулы имеют вид: . Ес­тественно, в каждом из этих случаев и формула проверки меняет свой вид, но основная идея остается неизменной. Третий " пласт" модификации схемы Эль-Гамаль связан с возможностью переноса вычислений в группу, образованную эллиптическими кривыми. Стандарт США электронной цифровой подписи DSS (Digital Signature Standard), принятый в 1992 году, является од­ной из модификаций схемы Эль Гамаля и Государственный стандарт Российской Федерации на ЭП ГОСТ Р 34.10-2001(ныне заменен на ГОСТ Р 34.10-2012) также основан на схеме Эль Гамаля.

Способы ускорения процедур подписи и проверки

На основе подписи Эль-Гамаля может быть построен более эффектив­ный алгоритм, в котором время вычислений значительно сокраща­ется за счет использования «коротких» показателей степени.

Вначале для некоторого сообщества пользователей выбирают­ся общие несекретные параметры. Прежде всего необходимо найти два простых числа, qдлиной 256 бит и р длиной 1024 бита, между которыми выполняется соотношение для некоторого целого b. Старшие биты в р и qдолжны быть равны единице. Затем выбирается число , такое, что

Данное равенство означает, что при возведении a в степени по модулюp показатели приводятся по модулю q, т.е. . Такое приведение будет постоянно выполняться при генерации и проверке подписи, в результате чего длина показателей степени в рамках рассматриваемого алгоритма никогда не будет превышать 256 бит, что упрощает вычисления.

Стандарты цифровой подписи США (DSA) и России (ГОСТ Р 34.10)

DSA. DSA (Digital Signature Algorithm) — криптографический алгоритм с использованием открытого ключа для создания электронной подписи, но не для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно, но может быть публично проверена. Это означает, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Алгоритм основан на вычислительной сложности взятия логарифмов в конечных полях.

Вначале для некоторого сообщества пользователей выбирают­ся общие несекретные параметры. Прежде всего необходимо найти два простых числа, q длиной 160 бит и р длиной 1024 бита, между которыми выполняется соотношение: ,

Далее, каждый пользователь выбирает случайно число x, удо­влетворяющее неравенству , и вычисляет

Число x будет секретным ключом пользователя, а число у — от­крытым ключом. Предполагается, что открытые ключи всех поль­зователей указываются в некотором несекретном, но «сертифициро­ванном» справочнике, который должен быть у всех, кто собирается проверять подписи.

Пусть имеется сообщение m, которое необходимо подписать. Ге­нерация подписи выполняется следующим образом:

1. Вычисляем значение хеш-функции для сообщения m, значение хеш-функции должно лежать в пределах

2. Формируем случайное число k, .

3. Вычисляем . Если оказывается так, что , то возвращаемся к шагу 2.

4. Вычисляем . Если , то возвращаемся к шагу 2.

5. Получаем подписанное сообщение .

Для проверки подписи делаем следующее.

1. Вычисляем хеш-функцию для сообщения .

2. Вычисляем ; .

3. Вычисляем .

4. Проверяем выполнение равенства .

Если же все проверки удачны, то подпись считается подлинной.

ГОСТ Р34.10-2012(" Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи" ). Формирование цифровой подписи.

ГОСТ Р 34.10-2012 - российский стандарт, описывающий алгоритмы формирования и проверки электронной подписи. ГОСТ Р 34.10-2012 основан на эллиптических кривых. Стойкость алгоритма основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции.

Согласно ГОСТ Р 34.10-2012 электронная подпись позволяет:

1. Аутентифицировать лицо, подписавшее сообщение;

2. Контролировать целостность сообщения;

3. Защищать сообщение от подделок;

4. Доказать авторство лица, подписавшего сообщение.

Для получения ЭП под сообщением M необходимо выполнить следующие действия:

1. Вычислить хэш-функцию от сообщения ;

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

3. Сгенерировать случайное целое число 0< k< q

4. Вычислить точку эллиптической кривой и определить , где —координата x точки C. Если , то вернуться к шагу 3.

5. Вычислить значение . Если , то вернуться к шагу 3.

6. Вычислить двоичные векторы и , соответствующие r и s и определить электронную под­пись как конкатенацию(операция склеивания объектов («микро» и «мир» даст слово «микромир»)) двух двоичных векторов.

Исходными данными этого процесса являются ключ подписи d и подписываемое сообщение M, а выходным результатом — электронная подпись .

Проверка цифровой подписи

Для проверки ЭП под полученным сообщением M необходимо выполнить следу­ющие действия:

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

2. Вычислить хэш-функцию от сообщения ; Если e= 0, то определить e= 1.

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

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

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

6. Вычислить точку эллиптической кривой и определить , где — x-координата точки C.

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

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

⇐ Предыдущая47484950515253545556Следующая ⇒

Поделиться:

Популярное:

1. I. Цифровой тест В. мегедь—А. Овчарова
2. А-общий вид; б-принципиальная схема; 1-неоновая лампа; 2- шунтирующее сопротивление; 3-добавочное сопротивление; 4-корпус.
3. Автоматическая схема переключения шин.
4. Алгоритм линейной структуры и его блок-схема.
5. Вопрос 2. Структура и организация платежной системы. Базовая схема операции с банковской кредитной карточкой.
6. Глава 14. СТАРИННЫЕ ГЭЛЬСКИЕ ИСТОРИИ О ЛЮБВИ
7. Глава 4. Схема нейропсихологического обследования дошкольников и процедура анализа результатов
8. Даже Эльбрус можно не узнать
9. Испанская живопись XVI в. Эль Греко
10. Как воспитывать гендерно не схематизированных детей?
11. КИНЕМАТИЧЕСКАЯ СХЕМА ПРИВОДА
12. Классическая схема налогообложения