Петров А.А. Комп без-ть

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

71

•общие параметры;

•секретный ключ;

•открытый ключ.

Общие параметры необходимы для функционирования системы в це­ лом. Секретный ключ используется для формирования ЭЦП, а откры­ тый - для проверки ЭЦП. Общими параметрами системы являются про­ стые целые числа р, д и & удовлетворяющие следующим условиям:

•р: 2511 < р < 2512;

•простой делитель числа (р - 1 ), который удовлетворяет условию 215э< р < 2160;

•§: так называемый генератор, удовлетворяющий равенству § = Ьр'1/С1шос1 р, где к - любое целое 0 < Ь < р, при котором кр'1/чтос1 р > 1.

Параметры р, ^ и $ опубликовываются для всех пользователей системы обмена ЭД с ЭЦП.

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

Открытый ключ у вычисляется следующим образом: у = §хтос1р. Также при описании данной схемы будут использоваться следующие

обозначения и дополнительные параметры: ш - входное сообщение пользо­ вателя для схемы ЭЦП; к - случайное число, удовлетворяющее условию

О< к < р, хранящееся в секрете и меняющееся от одной подписи к другой;

Н- хэш-функция; к - хэш-код сообщения.

Процесс генерации ЭЦ П состоит из следующих этапов:

1.Вычисляется хэш-код сообщения т к = Н (т ).

2.Из диапазона [1, ц] случайным образом выбирается значение к и вы­ числяется г = (§ кт о б р )т о с ^ .

3.Вычисляется з = (к _1(к + х г ))т о б д , где к' 1 удовлетворяет условию

(к^кфпоск! - 1.

Значения г и з являются Э Ц П сообщения ш и передаются вместе с ним по открытым каналам связи.

Проверка ЭЦП

Пусть принято сообщение пц и его подпись 31 и г4 при передаче ( т , з, г). Проверка ЭЦ П происходит следующим образом:

• проверяется выполнение условий 0 < Г! и 0 < з1 < ц, и если хотя бы

одно из них нарушено, подпись отвергается;

72	Общие сведения по классической криптографии

•вычисляются значения:

^ = з[1тос1 ^

и1 = ( Н ( т 1)'^/)то(1 я и2 = ((г 1/’^ )т о (! д

у = ((§ и1уи2)т о <1 р)тос1 ц

•проверяется равенство V =

Если последнее равенство выполняется, то подпись принимается. В дан­ ном стандарте также специфицируется процедура генерации основных параметров системы и проводится доказательство того, что если V = г1( то т.! = ш, Г! = г и §1 = з.

Стойкость 08А

Криптографическая стойкость схемы Б 5А против атак методом «грубой силы» в первую очередь зависит от размера параметров р и ^ (в данном случае 512 и 160 бит). Соответственно криптостойкость против атаки ме­ тодом «грубой силы» на параметр р будет равна 2160. А успешная атака на параметр д возможна только в том случае, если злоумышленник может вычислять дискретные логарифмы в полях Галуа СЕ(2512) с количеством предварительных вычислений пропорционально

Ц р ) = е'/Ьр|п|" 1>.

Одной из теоретически возможных атак на схему Б 5А является комп­ рометация параметра к. При каждой подписи требуется новое значение к, которое должно быть выбрано случайным образом. Если злоумышленник найдет значение к, употреблявшееся при подписании сообщения (такое возможно, если будут обнаружены некоторые слабости в процедуре гене­ рации к), секретный ключ х может быть воспроизведен. Другой возможный вариант - две подписи были сгенерированы на одном значений к. В этом случае злоумышленник тоже в состоянии восстановить х. Следовательно, одним из факторов, повышающих безопасность использования схем ЭЦП, является наличие «хорошего» генератора случайных чисел.

1.4.4. Стандарт на процедуры выработки и проверки ЭЦП

Отечественным стандартом на процедуры выработки и проверки ЭЦ П является ГО СТ Р 34.10-94. Схема ЭЦП, предложенная в данном стан­ дарте, во многом напоминает подпись в Б 8 А, поэтому большая часть рассуждений о предыдущем алгоритме справедлива и для данной схе­ мы ЭЦП .

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

73

Цифровая подпись представляет собой два больших целых числа. О б­ щедоступные параметры схемы Э Ц П (р, ^ и а) должны удовлетворять сле­

дующим условиям:
• р: 2 509< р < 2 512 или 2 1020<	р < 2 1024;
• р: простой делитель (р -	1 ) и удовлетворяет неравенству 2 254 < д < 2 256;

• г : 1 < а < р - 1 и аС|(шос1 р) = 1 .

Секретный ключ пользователя х выбирается случайным образом и дол­ жен удовлетворять неравенству 0 < х < Открытый ключ пользователя вычисляется в соответствии с равенством у = ах(т о б р).

Генерация ЭЦП

Процедура генерации подписи сообщения т с о с т о и т и з следующих шагов:

1 . Вычисляется хэш-код сообщения ш: Ь в Н ( т ) (хэш-функция, исполь­ зуемая в данном стандарте в соответствии с ГО С Т Р 34.10-94), если Ь (ш )(тос1 р) = 0 , то Ь ( т ) присваивается значение 0 ...0 2551 .

2.Случайным образом выбирается значение к (аналогично О ЗА), удов­ летворяющее условию 0 < к < ^.

3.	Вычисляется значение г = ак(то с ! р) и Г1 = г (т о б р); если Г! = 0, следу­
	ет вернуться к предыдущему этапу и выработать другое значение к.
4.	Вычислить значение з = (х г 1+ к Ь .(т ))(т о (1 р); если з = 0, то необходи­
	мо выработать другое значение к. В противном случае подписью со­
	общения являются числа Г! и з.

Проверка ЭЦП

Процедура проверки Э Ц П состоит из последовательности действий:

1.	Проверяется выполнение условий 0 < з < д и 0 < Г ! ^ , и если хотя бы
	одно из них не выполняется, подпись отвергается.
2.	Вычисляется хэш-код принятого сообщения Ь = Н (т ); если Ь ( т ) х
	х (т о б р) = 0 , то битовое представление Ь(ш ) равно О...О255П
3.	Вычисляется значение V = ( Ь ( т ) ) ч'2(т о б р).
4.	Вычисляются значения: Ъ\= з у (т о б р); г2= (д - г Ц у (т о б р).
5.	Вычисляется значение и = (аг1у22 (т о б р ))(т о б ^).

6 . Проверяется равенство г* = и; если оно выполняется, подпись прини­ мается. То есть в этом случае можно считать, что сообщение подписа­ но данным отправителем и в процессе передачи не была нарушена его целостность.

74	Общие сведения по классической криптографии

/.4.5. Практическое применение ЭЦП

Наличие широкого спектра достоинств у схем ЭЦП предопределило их широкое распространение в системах обмена электронными документами, а также во многих других случаях, где требуется обеспечить целостность и достоверность передачи информации.

Практическое использование схем ЭЦП и их разновидностей описано ниже. В этом разделе рассматривается вопрос практической реализации ЭЦП в соответствии со стандартом РКСЗ # 1. Стандарт криптографии с открытым ключом (РК С З ) содержит требования для практического при­ менения процедур зашифрования/расшифрования и генерации/проверки на основе использования асимметричного алгоритма КЗА.

Схема ЭЦП, описанная в РКСЗ # 1, основана на применении хэш-функ­ ции (М Б 2 или М Б 5) к входному сообщению и зашифровании хэш-кода сообщения при помощи алгоритма КЗА.

В табл. 1.9 представлены основные обозначения и их показатели, исполь­ зуемые в данном разделе. Следует отметить, что в соответствии с РКСЗ # 1 все битовые последовательности представляются в виде строки октетов (октет имеет размерность 8 бит), то есть если х - строка октетов, то Х| -

1-й октет (отсчет начинается слева направо).

Таблица 1.9. Обозначения, используемые в разделе

к	Длина п в октетах (кУ >11)	ЕВ	Блок данных для зашифрования
п	Модуль в КЗА 28(к-1)<п<28к	ЕЭ	Зашифрованные данные
р и я	Целые числа такие, что п=ря	аЬ	Шестнадцатеричное значение октета
е и с1	Экспоненты в алгоритме КЗА	ВТ	Тип блока
М	Сообщение	РЗ	Дополнительные данные (набивка)
М Э	Хэш-код сообщения	5	Подпись
М О ]	Хэш-код, вычисляемый на этапе проверки	ЦХ|	Длина X в октетах

Форматданных в соответствии с РКСЗ # 1

Здесь данные представляют собой строку октетов Б, где ||Б||< к —11. В Т - строка октетов, шестнадцатеричное значение которой может принимать значение 00 или 01. РЗ - строка октетов, ||Р5|| = к - 3 - ||Б||- длина строки РЗ, которая зависит от значения ВТ. Если ВТ = 00, то все октеты в РЗ рав­ ны 00, если ВТ = 01, то все октеты в РЗ равны РЕ Формат ЕВ имеет следу­ ющий вид: 00||ВТ||Р5||00||Б. Первые 00 предназначены для того, чтобы значения строки ЕВ были меньше модуля п.

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

75

Генерация ЭЦП

В данной процедуре (рис. 1.20) входным является сообщение ш, а общедо­ ступными параметрами системы - модуль п и секретный компонент б.

Процесс генерации включает следующие шаги:

1.Получение хэш-кода сообщения; резуль­ татом данного шага является строка окте­ тов М Б.

2.Из М Б и значения, идентифицирующего используемую хэш-функцию в соответ­ ствии с рекомендациями АЗЫ. 1 и основ­ ными правилами кодирования (В Е К епсобт&), получают строку октетов.

3.Строка Б преобразуется в строку ЕВ на основе процедуры, описанной выше.

4.Из строки октетов ЕВ получают ее цело­ численное значение. Обозначим строку ЕВ как ЕВ! |ЕВ2||... |ЕВк, где ЕВ! - 1-й ок­ тет строки. Далее через ЕВ| обозначим це­ лочисленное значение октета ЕВ!, тогда целочисленное значение ЕВ (обозначим

1с

его как ш) будет равно т = Х 2 8(к-1)ЕВ|.

5. Зашифровывают щ в соответствии с алго­ ритмом КЗА, то есть з = тА п о б п;

6 . Преобразуют целое значение з в строку ок­ тетов ЕБ, таким образом, ЕБ и есть циф­ ровая подпись сообщения ш.

Сообщ ение

Рис. 1.20. Генерация ЭЦП

Проверка ЭЦП

В данной процедуре (рис. 1.21) входными параметрами являются сообще­ ние ш, подпись сообщения з и параметры алгоритма КЗА, а именно: мо­ дуль п и открытая компонента е.

Процесс проверки подписи включает следующие шаги:

1. Преобразование подписи з, представленной в виде строки октетов, в целочисленное значение (см. раздел «Генерация Э Ц П »), причем в этом случае происходят следующие проверки:

-если длина строки в битах з некратна восьми, подпись з отвергается;

-если з меньше п, подпись отвергается;

76	Общие сведения по классической криптографии

2. Расшифрование з в соответствии с алгоритмом КЗА, то есть т =

= зетос1 п.

3.Преобразование целочисленного значения ш в строку октетов ЕВ х

X (||ЕВ|| = к); см. раздел «Генерация ЭЦ П ».

4.Проверку формата строки ЕВ на соот­ ветствие типу, заданному в ВТ, а также проверку строки РЗ. В ходе проверки возможны следующие случаи непризна­ ния подписи з:

-если формат ЕВ не может быть одно­ значно распознан;

-если значение ВТ отличается от 00 или 0 1 ;

-если РЗ состоит из менее восьми окте­ тов или формат РЗ несовместим с ти­ пом, указанным в ВТ.

5.Из строки Б в соответствии с основны­

ми правилами кодирования и иденти­ фикатором используемой хэш-функции получают строку М Б. В случае, если идентификатор не указывает на М Б 2 или М Б 5, подпись з отвергается.

6 . Получение хэш-кода М Б! из сообщения ш с использованием хэш-функции, оп­ ределенной в соответствии с идентифи­ катором хэш-функции. Проверка равен­ ства М Б = М Б!; подпись з сообщения ш принимается только в том случае, если равенство верно.

Сообщение и подпись

Подпись принимается

Рис. 1.21. Проверка ЭЦП

1.4.6. Арбитраж ЭЦП

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

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

77

В большинстве существующих систем использование арбитража Э Ц П основано на том, что подписать сообщение может только держатель сек­ ретного ключа (в этом случае ответственность за его компрометацию л о ­ жится на пользователя). Это утверждение нельзя считать верным в ситуа­ ции, когда 11(3410 = Ь(ш ), то есть одна и та же подпись появляется под двумя разными сообщениями. Арбитр в подобном случае не сможет разрешить возникший спор, хотя очевидно, что кто-то из участников нашел к олли ­ зии для хэш-фушсции. Поэтому в большинстве случаев процедуры арбит­ ража будут неполными, за исключением варианта, когда схемы Э Ц П раз­ работаны специально с учетом проведения подобного разбирательства. И з существующих на сегодняшний день схем электронной подписи арбитраж эффективней всего может быть проведен для ЭЦП, построенных на осно­ ве симметричного шифрования при участии третьей стороны. При исполь­ зовании схем ЭЦП , построенных без участия арбитра, следует с особой тщательностью выбирать процедуру подписания ЭД, чтобы арбитр в слу­ чае возникновения спорной ситуации мог решить, какая из сторон являет­ ся правой.

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

Здесь исходными данными являются общедоступные параметры Э З А - р, ц, ЭД - т и подпись - г, з. ЭД и подпись представляются арбитру участником В, который хочет доказать, что данная подпись принадлежит участнику А; в свою очередь, участник А отказывается признать, что данпая подпись была сгенерирована им.

Прежде всего арбитр требует от участника А предъявления секретного ключа. Это требование для любого пользователя Э Ц П в конкретной опи­ сываемой системе должно выполняться безоговорочно. Арбитр проверяет открытый ключ из общедоступного справочника на соответствие пред­ ставленному секретному ключу. В случае несовпадения арбитр обраща­ ется в центр сертификации открытых ключей и требует предоставления заверенного участником А документа, содержащего открытый ключ. Если выясняется, что открытый ключ в общедоступном справочнике не совпа­ дает с указанным в документе, виновным признается центр сертификации открытых ключей. Когда открытые ключи в справочнике и в документе

78	Общие сведения по классической криптографии

совпадают, это означает, что предъявлен некорректный секретный ключ,

иучастник А признается виновным.

Вслучае, если открытый и секретный ключи соответствуют ранее со­ зданным образцам, арбитр производит следующие вычисления:

= з^шоб ц

и1 = (Ь(т)\у)тос1 ^ и2 = (пу)тос1 ц

V = ((§ и1уи2)т о б р)тос1 ц

Завершающей фазой является проверка равенства V = г. Если оно вы­ полняется, то подпись признается истинной, если нет - ложной.

1.5. Хэш-функции

1.5.1. Общие сведения

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

Как уже говорилось ранее, неотъемлемой частью электронно-цифровой подписи является использование так называемых хэш-функций. Кроме того, они находят широкое применение и для решения ряда других вопро­ сов, связанных с обеспечением защиты потоков данных, например для хэ­ ширования паролей пользователей с целью дальнейшего их шифрования и хранения в базе данных. Данный метод применяется в ОС ^ т < 1 о\У5 ЫТ (используется хэш-функция М Б 4 совместно с БЕЗ).

Одной из самых важных характеристик хэш-функций, обусловивших их широкое внедрение в практику, оказалась способность получать из откры­ того текста большой длины (например, в хэш-функции 5Е1А максималь­ ная длина открытого текста ограничена 2 64 битами) хэш-кода гораздо мень­ шей длины (в отечественном стандарте ГО СТ Р 34.11-94 длина хэш-кода равна 256 битам, западные хэш-функции в основном имеют хэш-код

Хэш-функции

79

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

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

1.5.2. Типы хэш-функций

Существует три типа построения хэш-функций:

•на основе какой-либо трудновычисляемой математической задачи;

•на основе алгоритмов блочного шифрования;

•разработанные с нуля.

Каждый из вышеперечисленных методов имеет свои достоинства и не­ достатки, однако наиболее распространенными иа сегодняшний день ока­ зались последние два. Это связано с тем, что при построении хэш-функ- ций с нуля появляется возможность учитывать такое их свойство, как эффективная программная реализация. Ш ирокое применение хэш-функ­ ций, построенных на основе алгоритмов блочного шифрования, является результатом тщательной проработки вопроса стойкости многих из суще­ ствующих алгоритмов.

В данном разделе приведены два примера практической реализации хэш-функций (ЗН А, построенная с нуля, и ГО С Т Р 34.11-94 на основе блочного алгоритма шифрования ГО С Т 28147-89). Вопросы криптографи­ ческой стойкости хэш-функций рассмотрены в разделе 1.5.3.

Стандарт ЗесигНу НазЬ А1доп1Нт

ЗесигКу НазЬ А^огШ нп (З Н А ) разработан в Ш З Т совместно с Н ЗА для использования со стандартом на цифровую подпись 033 . Этот алгоритм предназначен для работы с входными последовательностями длиной < 2 64

бит и имеет хэш-код длиной 160 бит. Принципиальную основу З Н А со­ ставляет алгоритм М Б 4, созданный Ривестом.

80	Общие сведения по классической криптографии

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

Далее инициализируются пять переменных по 32 бита:

А - 0x67452301	В - ОхНсбаШ
С = 0х98Ьа<1с1е	Б = 0x10325476
Е = 0хс362е1Ю

Основной цикл, совершаемый над одним 512-битным блоком, состоит из четырех подциклов, в каждом из которых используются по 2 0 операто­ ров. Перед тем как начать преобразования, создаются копии перечислен­ ных выше пяти переменных а, Ь, с, с1 и е.

Каждый оператор представляет собой набор нелинейных функций от трех переменных (В, С и Б ) и операций циклического сдвига и суммиро­ вания. Эти функции имеют следующий вид:

1 раунд ^ (Х , У, 2)	= (X А У ) V	(( - 1 X ) А 2 )
2 раунд (2(X, У, 2 )	= X 0 У 0 2
3 раунд 13 (Х, У, 2 )	= (X А У ) V	(X А 2) V (У а 2 )
4 раунд 14 (Х, У, 2 ) = Х 0 У 0 2
Для каждого раунда определяется одна константа:
К х- 0х5а827999 -	2^/4	К2 = 0х6еб9еЬа1 = 3‘/2/4
К 3 = 0х8ИЬЬсбс - 51/2/4		К 4 - 0хса62с136 - 10^/4

Каждый обрабатываемый блок (512 бит) разбивается на 16 подблоков по 32 бита в каждом (М 0 -г М 15), затем к нему добавляется до 80 подблоков длиной 32 бита (\У16 4- \У79) согласно следующему правилу:

\У\ = М { для 1 = 0 ^ 15 ( 1 является номером оператора)

0 ^ - з © ^ - 8 © Ж - и Ф ^ м е ) < < 1 для 1 = 16 а 79

Отметим, что первоначально при формировании подблоков \У в ЗН А не было левого циклического сдвига. Результатом его введения явилось устранение одной из уязвимостей оригинального стандарта.

Каждый основной оператор имеет вид:

РОК 1: = 0 1 о 70 { ТЕ М Р = (а < < 5) + 1(Ъ, с, 6 ) + е + ^ + К,