Электронная подпись ГОСТ Р 31.10-2001
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
О
СТАНДАРТЕ
ОБОЗНАЧЕНИЯ
ОБЩИЕ
ПОЛОЖЕНИЯ
ФОРМИРОВАНИЕ
ЦИФРОВОЙ ПОДПИСИ
ПРОВЕРКА
ЦИФРОВОЙ ПОДПИСИ
ОТЛИЧИЯ
ОТ ГОСТ 34.10-94
КОНТРОЛЬНЫЙ
ПРИМЕР
ПРИМЕР
ИСПОЛЬЗОВАНИЯ
БИБЛИОГРАФИЧЕСКИЙ
СПИСОК
ВВЕДЕНИЕ
Электронная подпись (ЭП) - информация в
электронной форме, присоединенная к другой информации в электронной форме
(электронный документ) или иным образом связанная с такой информацией.
Используется для определения лица, подписавшего информацию (электронный
документ).
По своему существу электронная подпись
представляет собой реквизит электронного документа, позволяющий установить
отсутствие искажения информации в электронном документе с момента формирования
ЭП и проверить принадлежность подписи владельцу сертификата ключа ЭП. Значение
реквизита получается в результате криптографического преобразования информации
с использованием закрытого ключа ЭП.
В 1976 году Уитфилдом Диффи и Мартином Хеллманом
было впервые предложено понятие «электронная цифровая подпись», хотя они всего
лишь предполагали, что схемы ЭЦП могут существовать.
В 1977 году Рональд Ривест, Ади Шамир и Леонард
Адлеман разработали криптографический алгоритм RSA, который без дополнительных
модификаций можно использовать для создания примитивных цифровых подписей.
Вскоре после RSA были разработаны другие ЭЦП,
такие как алгоритмы цифровой подписи Рабина, Меркле.
В 1984 году Шафи Гольдвассер, Сильвио Микали и
Рональд Ривест первыми строго определили требования безопасности к алгоритмам
цифровой подписи. Ими были описаны модели атак на алгоритмы ЭЦП, а также
предложена схема GMR, отвечающая описанным требованиям.
В России в 1994 году Главным управлением
безопасности связи Федерального агентства правительственной связи и информации
при Президенте Российской Федерации был разработан первый российский стандарт
ЭЦП - ГОСТ Р 34.10-94.
В 2002 году для обеспечения большей
криптостойкости алгоритма взамен ГОСТ Р 34.10-94 был введен стандарт ГОСТ Р
34.10-2001, основанный на вычислениях в группе точек эллиптической кривой. В
соответствии с этим стандартом, термины «электронная цифровая подпись» и
«цифровая подпись» являются синонимами.
Использование ЭП позволяет осуществить:
Контроль целостности передаваемого документа:
при любом случайном или преднамеренном изменении документа подпись станет
недействительной, потому что вычислена она на основании исходного состояния
документа и соответствует лишь ему.
Защиту от изменений (подделки) документа:
гарантия выявления подделки при контроле целостности делает подделывание
нецелесообразным в большинстве случаев.
Невозможность отказа от авторства. Так как
создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть
известен только владельцу, то владелец не может отказаться от своей подписи под
документом.
Доказательное подтверждение авторства документа:
Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен
быть известен только владельцу, то владелец пары ключей может доказать своё
авторство подписи под документом. В зависимости от деталей определения
документа могут быть подписаны такие поля, как «автор», «внесённые изменения»,
«метка времени» и т. д.
О СТАНДАРТЕ
ГОСТ Р 34.10-2001 или Государственный Стандарт
Российской Федерации «Информационная технология. Криптографическая защита
информации. Процессы формирования и проверки электронной цифровой подписи»
(Information technology. Cryptographic data security.Formation and verification
processes of [electronic] digital signature) был разработан Главным управлением
безопасности связи Федерального агентства правительственной связи и информации
при Президенте Российской Федерации с участием Всероссийского
научно-исследовательского института стандартизации (ВНИИстандарт). Стандарт был
внесен на рассмотрение Федеральным агентством правительственной связи и
информации при Президенте Российской Федерации, принят и введен в действие
Постановлением Госстандарта России от 12 сентября 2001 г. N 380-ст взамен ГОСТ
Р 34.10-94.
Стандарт разработан с учетом терминологии и
концепций международных стандартов ИСО 2382-2-76 "Обработка данных. Словарь.
Часть 2. Арифметические и логические операции", ИСО/МЭК 9796-91
"Информационная технология. Методы защиты. Схема цифровой подписи с
восстановлением сообщения", серии ИСО/МЭК 14888 "Информационная
технология. Методы защиты. Цифровые подписи с приложением" и серии ИСО/МЭК
10118 "Информационная технология. Методы защиты. Хэш-функции".
ГОСТ содержит описание процессов формирования и
проверки электронной цифровой подписи, реализуемой с использованием операций
группы точек эллиптической кривой, определенной над конечным простым полем.
Необходимость разработки нового стандарта взамен
стандарта 1994 года вызвана потребностью в повышении стойкости ЭЦП к
несанкционированным изменениям. Стойкость ЭЦП основывается на сложности
вычисления дискретного логарифма в группе точек эллиптической кривой, а также
на стойкости используемой хэш-функции по ГОСТ Р 34.11.
Стандарт рекомендуется использовать в новых
системах обработки информации различного назначения, а также при модернизации
действующих систем.
ОБОЗНАЧЕНИЯ
- множество всех двоичных векторов длиной 256
бит;∞ - множество всех двоичных векторов произвольной конечной длины;-
множество всех целых чисел;
р - простое число, р > 3 ;р - конечное
простое поле, представляемое как множество из р целых чисел {0, 1,... , р -
1};(mod р) - минимальное не отрицательное число, сравнимое с b по модулю р ;
М - сообщение пользователя, 
;
- объединение двух двоичных
векторов;
а, b - коэффициенты эллиптической
кривой;- порядок подгруппы группы точек эллиптической кривой;
Р
- точка эллиптической кривой порядка q ;- целое число - ключ подписи, 0 < d
< q;- точка эллиптической кривой - ключ проверки;
- цифровая
подпись под сообщением М .
ОБЩИЕ
ПОЛОЖЕНИЯ
Общепризнанная
схема цифровой подписи охватывает три процесса:
генерация
ключей (подписи и проверки);
формирование
подписи;
проверка
подписи.
В
ГОСТ процесс генерации ключей (подписи и проверки) не рассмотрен.
Характеристики и способы реализации данного процесса определяются субъектами,
непосредственно участвующими в нём.
Механизм
цифровой подписи определяется посредством реализации двух основных процессов:
формирование
подписи;
проверка
подписи.
Цифровая
подпись предназначена для аутентификации лица, подписавшего электронное
сообщение. Кроме того, использование ЭЦП предоставляет возможность обеспечить
следующие свойства при передаче в системе подписанного сообщения:
осуществить
контроль целостности передаваемого подписанного сообщения,
доказательно
подтвердить авторство лица, подписавшего сообщение,
защитить
сообщение от возможной подделки.
Схематическое
представление подписанного сообщения показано на рисунке 1.
Рис.1
- Схема подписанного сообщения
Поле
"текст", дополняющее поле "цифровая подпись", может,
например, содержать различные данные об отправителе сообщения или дату и время
отправки.
Установленная
в настоящем стандарте схема цифровой подписи должна быть реализована с
использованием операций группы точек эллиптической кривой, определенной над
конечным простым полем, а также хэш-функции.
Криптографическая
стойкость данной схемы цифровой подписи основывается на сложности решения
задачи дискретного логарифмирования в группе точек эллиптической кривой, а
также на стойкости используемой хэш-функции.
Цифровая
подпись, представленная в виде двоичного вектора длиной 512 бит, должна
вычисляться с помощью определенного набора правил.
ФОРМИРОВАНИЕ
ЦИФРОВОЙ ПОДПИСИ
Для
получения ЦП под сообщением необходимо выполнить ряд действий.
Схематическое представление алгоритма формирования ЦП можно увидеть на рисунке
2.
Рис.2
- Алгоритм формирования ЦП
Вычисление
хэш-функции от сообщения М: 
Вычисление
e = 
mod q, где - целое
число, двоичным представлением которого является вектор 
, и если e =
0, взять e = 1.
Генерация
случайного (псевдослучайного) числа k такого, что 0 < k < q
Вычисление
точки эллиптической кривой C = kP
Точка
является
точкой эллиптической кривой Е, если пара (x,y) удовлетворяет тождеству 
, где a,b
принадлежат конечному простому полю 
и 
не сравнимо с нулем по модулю p.
Коэффициенты
a и b высчитываются с помощью инварианта эллиптической кривой
Нахождение
, где 
-
координата точки С. Если r = 0, то вернутся к генерации k.
Вычисление
. Если s =
0, то вернуться к генерации k.
Вычисление
двоичных векторов 
и 
, являющихся
двоичным представлением чисел r и s соответственно, и определение ЦП как
конкатенации двух двоичных векторов 
ПРОВЕРКА
ЦИФРОВОЙ ПОДПИСИ
Для
проверки ЦП под сообщением также необходимо выполнить ряд действий.
Схематическое представление алгоритма проверки ЦП можно увидеть на рисунке 3.
Рис.3
- Алгоритм проверки ЦП
Вычисление
по ЦП чисел r и
s. Если 0 < r < q или 0 < s < q не выполняется, то подпись неверна
Вычисление
хэш-функции от полученного сообщения М:
Вычисление
e = mod q, где - целое
число, двоичным представлением которого является вектор , и если e =
0, взять e = 1.
Вычисление
Вычисление
и 
Вычисление
точки эллиптической кривой 
Вычисление
, где -
координата точки С
Если
R = r, то подпись правильная, иначе - неправильная.
ОТЛИЧИЯ
ОТ ГОСТ 34.10-94
электронная подпись криптографическая защита
Новый
и старый ГОСТы цифровой подписи очень похожи друг на друга. Основное отличие -
в старом стандарте часть операций проводится над полем 
, а в новом
- над группой точек эллиптической кривой, поэтому требования налагаемые на
простое число p в старом стандарте(
или 
) более жесткие, чем в новом.
Алгоритм
формирования подписи отличается только в пункте 4. В старом стандарте в этом
пункте вычисляются 
и 
. Если r =
0, возвращаемся к пункту 3.
Алгоритм
проверки подписи отличается только в пункте 7. В старом стандарте в этом пункте
вычисляется 
, где y -
открытый ключ для проверки подписи, 
. Если R = r, подпись правильная,
иначе неправильная. Здесь 
- простое
число, 
и q
является делителем (p-1).
Использование
математического аппарата группы точек эллиптической кривой, позволяет
существенно сократить порядок модуля p, без потери криптостойкости.
Также
старый стандарт описывает механизмы получения чисел 
, и 
.
КОНТРОЛЬНЫЙ
ПРИМЕР
)
Для формирования и проверки цифровой подписи должны быть использованы следующие
параметры:
*Модуль
эллиптической кривой
В
данном примере параметру р присвоено следующее значение:
р
=5789604461865809771178549250434395392663499233282028201972879200395656482104110
*Коэффициенты
эллиптической кривой
В
данном примере параметры a и b принимают следующие значения:
a
=
710=4330887654676727690576590459565093199594211179445103958325296884203384958041410
*Порядок
группы точек эллиптической кривой
В
данном примере параметр m принимает следующее значение:
m
=5789604461865809771178549250434395392708293458372545062238097359213763106961910
*Порядок
циклической подгруппы группы точек эллиптической кривой
В
данном примере параметр q принимает следующее значение:
q
=5789604461865809771178549250434395392708293458372545062238097359213763106961910
*Коэффициенты
точки эллиптической кривой
В
данном примере координаты точки Р принимают следующие значения:
Хр
=
210=401897405653903750333544942293705977563573938990554508069097936521343156628010
*Ключ
подписи
В
данном примере считается, что пользователь обладает следующим ключом подписи d:
d
=5544119606536324612635562413032418319657670922234001657210809775000609752554410
*Ключ
проверки
В
данном примере считается, что пользователь обладает ключом проверки Q,
координаты которого имеют следующие значения:
Xq=5752021612617680844363140502333807117663010490631363218289674134220660485940310=1761494441921378154380939194965408003194266204536363926070984785943828676399410
)
Процесс формирования ЦП
Пусть
после выполнения шагов 1 - 3 были получены следующие числовые значения:
е
=2079889367447645201713406156150827013063714251537965328995261725266146887242110=5385413767734846373140384114799661924150400343430202071296083852889319623339510
При
этом кратная точка С = kP имеет координаты:
Xc=2970098091581795287437120498393825699042275210799431965163268798205921093339510=3284253527868466347709466532251708450680472103245454326813285455653927406091010
Параметр
r = х (mod q) принимает значение:
r
=2970098091581795287437120498393825699042275210799431965163268798205921093339510
Параметр
s = (rd + ke) (mod q ) принимает значение:
s
=57497340027008465417892531001914703845522704264909856393371899917551583955210
)
Процесс проверки ЦП
Пусть
после выполнения шагов 1 - 3 было получено следующее числовое значение:
е
=2079889367447645201713406156150827013063714251537965328995261725266146887242110
При
этом параметр v = e (mod q ) принимает значение:
v
=1768668360593446867730171382490026856274688308067549671528803657243114571897810
Параметры
и принимают
значения:
=3769916750090193855684105729351265610884134519049194261930453241274372099975910
=141719984273434721125159179695007657692466558389728621144999326533336710922110
Точка
имеет
координаты:
Xc=2970098091581795287437120498393825699042275210799431965163268798205921093339510=3284253527868466347709466532251708450680472103245454326813285455653927406091010
Тогда
параметр принимает
значение:=2970098091581795287437120498393825699042275210799431965163268798205921093339510
Поскольку
выполнено равенство R = r, то цифровая подпись принимается.
ПРИМЕР
ИСПОЛЬЗОВАНИЯ
На
основе ГОСТ 34.10-2001 построен механизм так называемой «слепой подписи»,
который применяется в электронном голосовании.
Механизм
одновременно и защищает приватность поданного голоса, и однозначно верифицирует
избирателя. Достигается это с помощью так называемой «слепой» электронной
подписи. Задачу, решаемую с помощью слепой подписи, можно в двух предложениях
сформулировать примерно так:
Алиса
желает анонимно отправить некую достоверную информацию Цезарю;
Для
этого используется следующее решение:
Алиса
запечатывает листок с информации в конверт;
Алиса
приносит запечатанный конверт Бобу;
Боб
видит, что Алиса это Алиса и ставит штамп на конверт с информацией, не видя ее
сути;
Алиса
идет на почту и отправляет конверт со штампом Цезарю без обратного адреса;
Цезарь
получает конверт, видит штамп Боба и доверяет источнику информации, не зная
этот источник.
Принцип
в следующем. Тот, кто будет удостоверять нашу личность (валидатор), не должен
знать, за кого мы отдали свой голос в бюллетене. А тот, кто считает наш
бюллетень (счетчик), не должен знать нашу личность. Следовательно, наши
сообщения валидатору и счетчику должны отличаться друг от друга, притом так,
чтобы валидатор и счетчик, сговорившись, не могли определить, какой бюллетень
кому принадлежит. Пусть валидатор подписывает сообщение, умножив его на 2, т.е.
мы отправляем валидатору число, он возвращает нам удвоенное число в качестве
подписи, и счетчик такую подпись признает истинной. Мы отправляем валидатору 1,
он нам возвращает 2, мы пересылаем счетчику пару (1,2), счетчик смотрит, что
да, действительно, 2 ровно в 2 раза больше 1 и признает подпись истинной. А
теперь мы делаем иначе, мы берем наше сообщение (1), отправляем валидатору
удвоенное сообщение (2), он его подписывает, возвращает подпись (4), мы
производим обратное преобразование, делим четверку на два, получаем истинную
подпись (2) для нашего сообщения. Таким образом, валидатор не знал нашего
сообщения (ведь он знает, на сколько изначально сообщение умножили), но из его
подписи нашего замаскированного сообщения мы восстановили истинную подпись для
нашего секретного сообщения.
Таким
образом, мы получаем общую схему:
Избиратель
устанавливает защищенное соединение с валидатором, т.е. во-первых, избиратель
точно знает, что валидатор это валидатор, а валидатор точно знает, что
избиратель это избиратель;
Избиратель
генерирует избирательный бюллетень, голосует за любую партию, добавляет к
бюллетеню уникальную последовательность символов и хеширует бюллетень;
Избиратель
добавляет к хешу бюллетеня маскирующий множитель и направляет на подпись
валидатору;
Валидатор
проверяет, голосовал ли уже этот избиратель. В случае отрицательной проверки,
подписывает замаскированный хеш;
Избиратель
извлекает из подписи маскирующий множитель и получает корректную подпись для
своего оригинального хеша бюллетеня;
Избиратель
устанавливает незащищенное открытое соединение с счетчиком из любого места,
которое считает анонимным, и пересылает подписанный бюллетень.
Счетчик
проверяет корректность подписи бюллетеня, уникальность идентификатора, если
проверка положительна, дописывает +1 голос указанной партии.
В
случае необходимости, избиратель по своей уникальной идентифицирующей строчке
сможет проверить, за какую из партий был засчитан его голос.
БИБЛИОГРАФИЧЕСКИЙ
СПИСОК
ГОСТ
Р 34.10-2001 Информационная технология. Криптографическая защита информации.
Процессы формирования и проверки электронной цифровой подписи. - М.: ИПК Изд-во
стандартов, 2002. - 16 с.
Баричев
С.Г., Серов Р.Е. Основы современной криптографии: учебное пособие. - М.:
Горячая линия - Телеком, 2002. - 152 с.
Блог
Habrahabr, статья «Слепая подпись на основе ГОСТ 34.10-2001».
<http://habrahabr.ru/post/136022/>. Свободная энциклопедия. <http://ru.wikipedia.org/wiki/Main_Page>
1.