Электронная подпись 1 страница

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

- когда некоторый абонент получает сообщение, предположительно от абонента , как подтвердить, что получено сообщение именно от абонента , а не от третьего лица;

- когда абонент получает от абонента сообщение, как подтвердить, что оно не было изменено третьим лицом.

Для решения этой проблемы были разработаны алгоритмы электронной подписи. Определение электронной подписи дано федеральным законом №63-ФЗ от 6.04.2011 г.

Определение 2.1. Электронная подпись - информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию.

Во многих странах мира, в том числе в России, введены в действие стандарты на электронную подпись. В Европе и США, вместо термина «электронная подпись», чаще используется термин «цифровая подпись». Оба термина означают одно и то же.

Электронная подпись (ЭП) должна обладать следующими свойствами:

1) подписать документ может только законный владелец ЭП;

2) автор ЭП не может от нее отказаться;

3) в случае возникновения спора возможно участи третьих лиц (например, суда) для установления подлинности ЭП.

Из рассмотренных свойств можно определить злонамеренные действия, к которым относятся:

- отказ (ренегатство) – отправитель впоследствии отказывается от переданного сообщения;

- фальсификация – получатель (или третье лицо) подделывает сообщение;

- изменение - получатель (или третье лицо) вносит изменение в сообщение;

- маскировка – злоумышленник маскируется под легального пользователя.

Схема ЭП включает в себя:

- параметр безопасности ;

- пространство исходных сообщений;

- алгоритм генерации пары ключей ;

- алгоритм формирования подписи;

- алгоритм проверки подписи.

Электронная подпись называется допустимой для документа , если она принимается алгоритмом . Подделкой ЭП документа называется нахождение злоумышленником, не имеющим секретного ключа, допустимой подписи для документа .

Обобщенная схема ЭП имеет следующий вид (см. рис.2.1) [7-10]:

1. Отправитель А вычисляет и посылает получателю В .

2. Для получения подписи документа отправитель вычисляет и посылает получателю.

3. Получатель вычисляет и в зависимости от результата принимает или отвергает подпись отправителя А.

В классической схеме ЭП предполагается, что отправитель знает содержание подписываемого документа, а получатель проверяет подлинность ЭП без какого-либо разрешения и участия отправителя А.

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

1) хеш-функция обеспечивает преобразование входного массива данных любого размера в выходной массив данных (хеш) фиксированного размера;

2) практически невозможно внести изменения в входной массив данных, не изменив выходной массив данных (хеш).

Отправителю А достаточно снабдить подписью не сам документ , а его хеш-образ .

Рис. 2.1. Обобщенная схема формирования и проверки ЭП

2.1. Электронная подпись на основе криптосистемы RSA

Пусть некоторая сеть включает в себя абонентов. Абонент планирует подписывать документы. Вначале абонент должен сформировать параметры криптосистемы RSA (см. пункт 1.3). Для этого абонент выбирает два больших простых числа , и вычисляет , . Затем абонент выбирает число , взаимно простое с , а затем находит .

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

На следующем шаге абонент вычисляет хеш-функцию (или просто - хеш) подписываемого документа . Далее абонент вычисляет число

,

которое представляет собой ЭП. Число добавляется к документу и абонент получает подписанный документ .

Каждый абонент сети, который знает параметры абонента , может проверить подлинность его подписи. Для этого необходимо из подписанного документа взять и вычислить хеш-образ . Затем вычислить число

,

и проверить выполнение равенства .

Утверждение 2.1. Если ЭП подлинная, то .

□ Из свойств RSA следует, что

. ■

Первое свойство ЭП выполняется, т.к. никто кроме владельца подписи не может разложить на простые множители и . Для злоумышленника это будет односторонняя функция. По состоянию на 2010 год, при порядка 1024 бит, эта задача для злоумышленника практически неразрешима. Злоумышленник, зная и , не может определить . Действительно чтобы вычислить требуется знать , а, следовательно, и . Второе и третье свойства выполняются, т.к. выполняется первое.

Рассмотрим пример формирования ЭП с помощью алгоритма RSA. Пусть и . Тогда , . Пусть , тогда . Подписываемый документ . Будем полагать, что значение хеш-образа документа равно .

Вычисляется ЭП

.

Затем формируется подписанный документ . Зная открытый ключ подписавшего документ . В соответствии с правилом проверки подлинности ЭП вычисляется и затем

.

Значение , следовательно ЭП верна.

2.2. Электронная подпись на основе криптосистемы Эль Гамаля

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

,

которое является открытым. Теперь абонент готов подписывать документы.

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

На третьем шаге абонент выбирает случайное число , , взаимно простое с и вычисляет числа

,

,

.

где . Числа является ЭП. Таким образом, подписанное сообщение имеет вид .

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

.

Утверждение 2.2. Если ЭП верна, то условие выполняется.

□ Действительно,

. ■

Первое свойство ЭП выполняется, т.к. никто кроме законного владельца не знает . По этой же причине выполняются второе и третье свойства ЭП.

Основное отличие ЭП на базе криптосистемы Эль Гамаля от ЭП на базе криптосистемы RSA заключается в длине подписи. ЭП на базе криптосистемы RSA , практически в два раза короче, чем ЭП на базе криптосистемы Эль Гамаля , т.е. если длина ЭП RSA 1024 бит, то длина ЭП Эль Гамаля 2048бит.

Рассмотрим пример. Пусть общие параметры , . Пользователь выбирает секретный ключ и вычисляет открытый ключ

.

Подписываемый документ имеет вид . Вычисляется хеш-образ , затем генерируется число (). Вычисляется ЭП:

,

,

.

При этом . Подписанное сообщение имеет вид . Для проверки подлинности ЭП вычисляется хеш-образ документа , а затем вычисляется

,

.

Следовательно, ЭП верна.

Рассмотрим методы сокращения длины ЭП Эль Гамаля [10].

1. Схема ЭП Эль Гамаля с сокращенной длиной параметра .

Уравнение проверки подлинности ЭП может выполняться также в случае, когда в качестве берется число, относящееся к простому показателю , где . Для этого параметр должен быть вычислен из соотношения

.

Можно выбрать простой модуль таким образом, чтобы разложение содержало бы простой множитель , размер которого существенно меньше размера . Например, для модуля длиной 2048 бит длина может составлять 160 бит. Тогда будет иметь длину не более 160 бит.

2. Схема ЭП Эль Гамаля с сокращенной длиной параметров и .

Соотношение для проверки подписи может быть преобразовано к виду

.

При этом, вместо в степени при можно использовать значение его хеш-образ . В этом случае уравнение проверки подписи имеет вид

.

Чтобы ЭП была корректной, законный владелец подписи должен вычислить параметр из следующего уравнения

.

Так как при проверке ЭП не требуется выполнять никаких вычислений с использованием параметра , то проверка ЭП может быть осуществлена в соответствии с уравнением

.

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

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

2.3. Стандарты электронных подписей

В многих странах мира существуют стандарты на ЭП. Рассмотрим российские стандарты ГОСТ Р34.10-94 и ГОСТ Р34.10-2012, а также особенности американского стандарта ЭП FIPS 186 [7,9-12].

Российский стандарт ГОСТ Р34.10-94 был принят в 1994 году, а американский стандарт FIPS 186 в 1991 году. В основе обоих стандартов лежит по сути один и тот же алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией ЭП Эль Гамаля. Российский стандарт ГОСТ Р34.10-2012 введен в действие с 1 января 2013 года взаимен утратившего силу стандарта ГОСТ Р 34.10-2001. Стандарт ГОСТ Р 34.10-2012 содержит описание процессов формирования и проверки ЭП, реализуемой с использованием операций в группе точек эллиптической кривой, определенной над конечным простым полем.

Российский стандарт ГОСТ Р 34.10-94. Для некоторого сообщества пользователей выбираются общие несекретные параметры. Прежде всего необходимо найти два простых числа: длиной 256 бит и длиной 1024 бит, между которыми выполняется соотношение , где - небольшое целое число. Старшие биты и должны быть равны единице. Затем выбирается число , такое что

. (2.1)

В результате получают три общих параметра - , и .

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

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

.

Число является секретным ключом, а - открытым ключом. Приведенные обозначения параметров взяты из ГОСТ Р 34.11.-94. Открытые ключи пользователей указываются в сертифицированном справочнике, который есть у всех пользователей. На этом этап выбора параметров заканчивается.

Генерация ЭП выполняется следующим образом.

1. Вычисляется значение хеш-функции для выбранного документа , причем . В российском стандарте хеш-функция определяется ГОСТ Р 34.11-94.

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

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

.

Если , то требуется перейти к шагу 2.

4. Вычисляется

.

Если , то требуется перейти к шагу 2.

5. Формируется подписанное сообщение .

Для проверки ЭП выполняются следующие вычисления.

1. Вычисляется хеш-функцию .

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

, .

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

, ,

.

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

Если хотя бы одна из проверок (шаги 2 и 4) дает неверный результат, то ЭП считается недействительной.

Утверждение 2.3. Если подпись была сформирована законным владельцем, то .

□ Действительно,

■

Американский стандарт FIPS 186. Рассмотрим только отличия американского стандарта ЭП от российского стандарта. Они сводятся к следующему:

1. Длина числа берется равной 160 бит.

2. В качестве хеш-функции используется алгоритм SHA-1.

3. При генерации подписи на шаге 4 параметр вычисляется по формуле

.

4. При проверке подписи на шаге 3 вычисление и выполняются по формулам

, .

Российский стандарт ГОСТ Р 34.10-2012. На рис. 2.2 представлен алгоритм формирования и проверки ЭП. Каждый пользователь должен иметь ключ формирования подписи и ключ проверки подписи . В алгоритме формирования ЭП вычисляется хеш-функция , на основании которой определяется число , двоичным представлением которого является . Затем определяется число:

.

Генерация случайного числа , осуществляется при условии . Затем вычисляется точка и оп ее абсциссе определяется число . Точка удовлетворяет равенству . Далее вычисляется число

Дата добавления: 2014-12-26