Электронная подпись ГОСТ Р 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 «Информационная технология. Методы защиты. Схема цифровой подписи с восстановлением сообщения», серии ИСО/МЭК 14 888 «Информационная технология. Методы защиты. Цифровые подписи с приложением» и серии ИСО/МЭК 10 118 «Информационная технология. Методы защиты. Хэш-функции» .

ГОСТ содержит описание процессов формирования и проверки электронной цифровой подписи, реализуемой с использованием операций группы точек эллиптической кривой, определенной над конечным простым полем.

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

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

ОБОЗНАЧЕНИЯ

V256 — множество всех двоичных векторов длиной 256 бит;

V? — множество всех двоичных векторов произвольной конечной длины;

Z — множество всех целых чисел;

р — простое число, р > 3 ;

Fр — конечное простое поле, представляемое как множество из р целых чисел {0, 1,…, р — 1};

b (mod р) — минимальное не отрицательное число, сравнимое с b по модулю р ;

М — сообщение пользователя, ;

— объединение двух двоичных векторов;

а, b — коэффициенты эллиптической кривой;

q — порядок подгруппы группы точек эллиптической кривой;

Р — точка эллиптической кривой порядка q ;

d — целое число — ключ подписи, 0 < d < q;

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, без потери криптостойкости.

Также старый стандарт описывает механизмы получения чисел, и .

КОНТРОЛЬНЫЙ ПРИМЕР

1) Для формирования и проверки цифровой подписи должны быть использованы следующие параметры:

*Модуль эллиптической кривой В данном примере параметру р присвоено следующее значение:

р =5 789 604 461 865 809 771 178 549 250 434 395 392 663 499 233 282 028 201 972 879 200 395 656 481 996 800

*Коэффициенты эллиптической кривой В данном примере параметры a и b принимают следующие значения:

a = 710

b =4 330 887 654 676 728 085 365 188 894 006 752 608 201 023 241 409 443 742 718 173 805 793 456 460 660 736

*Порядок группы точек эллиптической кривой В данном примере параметр m принимает следующее значение:

m =5 789 604 461 865 809 771 178 549 250 434 395 392 663 499 233 282 028 201 972 879 200 395 656 481 996 800

*Порядок циклической подгруппы группы точек эллиптической кривой В данном примере параметр q принимает следующее значение:

q =5 789 604 461 865 809 771 178 549 250 434 395 392 663 499 233 282 028 201 972 879 200 395 656 481 996 800

*Коэффициенты точки эллиптической кривой В данном примере координаты точки Р принимают следующие значения:

Хр = 210

Yp=401 897 405 653 903 726 066 399 454 969 440 850 944 238 274 535 271 087 711 736 671 370 142 409 555 968

*Ключ подписи В данном примере считается, что пользователь обладает следующим ключом подписи d:

d =5 544 119 606 536 324 384 057 338 530 176 269 344 222 988 626 781 733 706 679 135 383 248 924 240 248 832

*Ключ проверки В данном примере считается, что пользователь обладает ключом проверки Q, координаты которого имеют следующие значения:

Xq=5 752 021 612 617 680 515 615 558 613 621 829 810 713 857 131 740 246 177 480 762 796 065 230 791 114 752

Yq=1 761 494 441 921 378 093 566 753 761 755 094 048 733 610 731 006 690 722 476 403 839 625 839 608 070 144

2) Процесс формирования ЦП Пусть после выполнения шагов 1 — 3 были получены следующие числовые значения:

е =2 079 889 367 447 645 126 429 495 562 526 736 062 940 543 640 940 224 729 820 370 411 272 863 387 484 160

k =5 385 413 767 734 846 188 193 869 749 912 412 654 294 616 265 734 404 411 225 317 123 627 455 130 632 192

При этом кратная точка С = kP имеет координаты:

Xc=2 970 098 091 581 795 282 651 999 523 441 733 230 990 309 588 459 019 983 951 211 179 950 040 833 589 248

Yc=3 284 253 527 868 466 479 793 511 493 134 637 372 025 525 838 003 818 888 531 553 437 525 157 802 409 984

Параметр r = х (mod q) принимает значение:

r =2 970 098 091 581 795 282 651 999 523 441 733 230 990 309 588 459 019 983 951 211 179 950 040 833 589 248

Параметр s = (rd + ke) (mod q) принимает значение:

s =57 497 340 027 008 466 952 362 135 873 851 036 456 715 201 019 553 051 895 295 570 462 228 363 608 064

3) Процесс проверки ЦП Пусть после выполнения шагов 1 — 3 было получено следующее числовое значение:

е =2 079 889 367 447 645 126 429 495 562 526 736 062 940 543 640 940 224 729 820 370 411 272 863 387 484 160

При этом параметр v = e (mod q) принимает значение:

v =1 768 668 360 593 446 968 101 805 290 016 982 602 635 489 023 454 146 809 732 048 855 884 549 047 975 936

Параметры и принимают значения:

=3 769 916 750 090 193 669 636 451 501 505 302 704 596 856 562 393 108 490 639 282 032 242 743 090 085 888

=141 719 984 273 434 714 051 778 555 540 947 303 390 414 499 159 814 852 073 247 338 731 889 015 914 496

Точка имеет координаты:

Xc=2 970 098 091 581 795 282 651 999 523 441 733 230 990 309 588 459 019 983 951 211 179 950 040 833 589 248

Yc=3 284 253 527 868 466 479 793 511 493 134 637 372 025 525 838 003 818 888 531 553 437 525 157 802 409 984

Тогда параметр принимает значение:

R =2 970 098 091 581 795 282 651 999 523 441 733 230 990 309 588 459 019 983 951 211 179 950 040 833 589 248

Поскольку выполнено равенство 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/136 022/

Wikipedia. Свободная энциклопедия. http://ru.wikipedia.org/wiki/Main_Page