А.И. Куприянов - Основы защиты информации (1022813), страница 36
Текст из файла (страница 36)
Число у определяется по закрытому ключу, как у = а"шод р. 1б8 ".Схема формирования и проверки подписи состоит в следую- . Информационный блок М на основе которого следует сфор- вать цифровую подпись, должен иметь длину меньше про:- го модуля р, т.е. число Мдолжно удовлетворять соотношению: ';.;< М< р. На практике модуль р выбирается таким, что он всегда ' вышает размер эталонной характеристики сообщения, в каче- которой выступает информационный блок М -:::- Подписью абонента А, сформированной на основе закрытого ча у и эталонной характеристики М, служит пара чисел г и з, торые удовлетворяют соотношению: ~~м уггггпос1р 5.101 (а~ -у'г'шар)=0.
(5.102) Нахождение пары чисел (г, л) без знания закрытого ключа выслительно сложно. Различных подписей, соответствующих одому и тому же документу, может быть чрезвычайно много (й может ' ринимать разные значения). Но выработать правильную подпись ожет только владелец секретного ключа. Возможные подписи от'ичаются значением г, но для данного г найти соответству1ощее 1б9 ( ) ' е. а~ и у'г' дают одинаковый остаток при целочисленном делен нар. ;-,: Значения у, а и р в совокупности являются открытым ключом онента А.
Они доступны для всех пользователей, и это позволя- . каждому из них убедиться в том, что сообщение действительно дписано абонентом А. Для проверки того факта, что документ дписан абонентом А, проверяется уравнение (5.101). Система цифровой подписи ЭльГамаля основана на том, что лько действительный владелец секретного ключа х может вырартать пару чисел (г, ~), удовлетворяющую уравнению проверки одписи (5.101). Используя значение х, абонент А вырабатывает одпись по следующему алгоритму: генерирует случайное число 1 (О < /с < р — 1), взаимно простое с : — 1), такое, чтобы наибольший общий делитель чисел /с и р был ы равен 1; вычисляет число г = а "пюдр; вычисляет з, решая уравнение М= (хг+ /се)пюд(р — 1); формирует подпись в соответствии с уравнением (5.101).
Таким образом, подпись из совокупности чисел г и ю формиется на основе информационного блока Ми закрытого ключа х, . проверяется с помощью открытого ключа (у,а,р) и текущей рактеристики М' полученного сообщения. Проверка сводится к ' становлению истинности равенства (5.101). Равенство (5.101) истинно тогда и только тогда, когда (5.103) у = у" пюс1 р. Число у служит открытым ключом для проверки подписи отправителя. Оно передается всем получателям документов. Для того чтобы подписать документ М, отправитель преобразует его, вычисляя хэш-функцию. Хэш-функция представляет собой одностороннюю криптографическую функцию от сообщения произвольной длины.
Значение хэш-функции зависит от каждого бита сообщения и реализуется, как правило, в виде некоторой итерационной процедуры. Значение этой функции Ь(М) — хэш-код— 170 значение я без знания закрьггого ключа невозможно (практически невозможно). Для вычисления закрытого ключа по открытому необходимо решить задачу дискретного логарифмирования, которая является вычислительно сложной. Особенностью схемы цифровой подписи ЭльГамаля является генерация случайного числа Е. Не допускается использовать одно и то же значение /с для подписи двух разных сообщений, поскольку на основе двух разных подписей, сформированных при одном и том же значении Й„имеется возможность вычислить закрытый ключ.
Кроме того, при известном значении й нарушитель сможет вычислить и закрытый ключ. Поэтому при формировании цифровой подписи, как и в случае криптографического закрытия информационных блоков, следует избегать повторений чисел /с и уничтожать эти числа сразу же после их применения.
В реально используемых системах большое случайное число А генерируется для каждого сообщения и гарантированно уничтожается после применения. При программной реализации обеспечиваемся такая схема шифровывания и формирования подписи, при которой число Ь появляется только в регистрах микропроцессора и оперативной памяти, а каждое новое число й записывается в ячейки памяти на место предыдущего.
Алгоритм цифровой подписи РВА (Р1811а1 Я8па1иге А18ог1Иип) является развитием алгоритмов цифровой подписи ЭльГамаля и К.Шнорра. Схема формирования электронной подписи в соответствии с алгоритмом ПЯА сводится к следующей цепочки действий. Отправитель и получатель электронного документа используют при вычислении большие целые простые числа: я и р длиной по! бит каждое (512 с 1 < 1024), а также д — большое простое число, делитель числа (р — 1).
Числа я, р, д являются открытыми и могут быть общими для всех полъзователей сети. Отправитель также выбирает случайное целое число х, 1 < х < д. Число х является секретным ключом отправителя для формирования электронной цифровой подписи. Затем отправитель вычисляет значение ' я сообщения М произвольной длины имеет фиксированный змер т (обычно 128 или 160 бит). Этот код и является эталонной ' рактеристикой сообщения М В системах электронной цифровой 'одписи сообщение М считается подписанным, если подписана хзш-функция. Поэтому к Ь(М) предъявляются следующие ос,' вные требования: '':. вычислительно неосуществимо нахождение сообщения М, хэшункция которого была бы равна заданному значению Ь; вычислительно неосуществимо создание двух разных сообщей М и М; с равными значениями хэш-функций, т.е. сообщей, удовлетворяющих условию Ь(М1) = Ь(М2).
Если эти требования не выполняются, то потенциальный злоышленник может подделать сообщение, подписанное хэш-фунией. Трудоемкость атаки, заключающейся в создании ложного :ообщения с тем же значением хэш-функции, что и у данного ' стинного, в среднем составляет около 2 ~' вычислений хэш-фуний и не зависит от качества криптографических преобразований. о обстоятельство определяет длину хзш-кода т не менее 128 бит. Сформировав хэш-функцию (5.104) т=Ь(М), 1<т<д, тправитель сообщения генерирует случайное целое число ~с, :1 < /с< д, и определяет число г по правилу: г = (~" щи р) гпод д, (5.105) Затем отправитель сообщения вычисляет с помощью секретного ключа х целое число к: т+ ~х ю = пюдр.
(5.10б) 0<г<д; 0<к<д (5.107) :.и отвергает подпись, если хотя бы одно из этих условий не вы":полнено. Затем получатель вычисляет значение 1 в = — пкк1д, Я (5.108) 171 Пара чисел г и ~ образуют цифровую подпись 5'= (г,л) под документом М. Таким образом, подписанное сообщение представляет собой ;тройку чисел 1М, г,4. Получатель подписанного сообщения 1М, г, я1 проверяет выпол"нение условий значение хэш-функции полученного документа т = Ь(М) (5.109) и числа и~ = (т и~)пик1д; и2= (г ш)тодд.
(5.110) После этого получатель с помощью открытого ключа у вычис ляет значение и = ~(8"'у"') шод р~ппх1д (5.111) и проверяет выполнение условия п = г. Если условие и= г выполняется, то подпись Я= (», я) под документом М признается получателем подлинной. Строго доказано, что равенство будет выполняться тогда и только тогда, когда подпись Я= (г, л) под документом М получена с помощью именно того секретного ключа х, из которого был получен открытый ключ у. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом х (не раскрывая при этом значения ключа х) и что отправитель подписал именно данный документ М По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм ОБА имеет ряд преимуществ, а именно: при любом допустимом уровне стойкости, т.е.
при любой паре чисел я и р (512 ... 1024 бит), числа а, х, г, з имеют длину по 160 бит, сокращая длину подписи до 320 бит. большинство операций с числами й, г, г, х при вычислении подписи производится по модулю числа а длиной 160 бит, что сокращает время вычисления подписи; при проверке подписи большинство операций с числами и„и,, и и и~ также производится по модулю числа д длиной 160 бит, что сокращает объем памяти и время вычисления. Недостатком алгоритма ОБА является то, что при подписывании и проверке подписи приходится выполнять сложные операции деления по модулю а: слить значения г. Можно также заранее вычислить обратные ачения к-' для каждого из значений й и при поступлении сооб' ения М вычислить значение л для данных значений г и й '.
Эти ' редварительные вычисления значительно ускоряют работу алгоритма 0БА. Отечественный стандарт цифровой подписи ГОСТ Р34.10 — 94 : редписывает использование следующих параметров: р — большое простое число длиной 509...512 бит либо ';;:-1020 ... 1024 бит; а — простой сомножитель числа (р — 1), имеющий длину :254... 256 бит; а — любое число, меньшее (р — 1), но такое, что а» шод р = 1; х — некоторое число, меньшее а; у = а"гпод р.
Кроме того, этот алгоритм использует одностороннюю хэш;::функцию Ь(х). Стандарт ГОСТ Р 34.11 — 94 определяет хэш-функ::цию, основанную на использовании стандартного алгоритма блоч";:,ного шифрования ГОСТ 28147 — 89. Первые три параметра р, а и а являются открытыми и могут :, быть общими для всех пользователей сети. Число х является сек':ретным ключом. Число у является открытым ключом. Чтобы под;:писать некоторое сообщение т, а затем проверить подпись, вы-' Полняются следующие действия: абонент А генерирует случайное число К< а и вычисляет: г = (а" шод р) пкк1 а; (5.113) л = ~хг+ И(т)~пюд д, если Ь(т)пкк1 а = О, то значение Ь(т)шос1 а принимают равным ', единице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
