ными значениями. При этом параметры самой кривой, координаты точки на ней и значения произведений являются открытыми и могут передаваться по незащищенным каналам связи. Затем пользователь А умножает полученное значение на а, а пользователь В умножает полученное им значение на Ь. В силу свойств операции умножения на число аЬР = = ЪаР. Таким образом, оба пользователя получат общее секретное значение (координаты точки аЬР), которое они могут использовать для получения ключа шифрования. Отметим, что злоумышленнику для восстановления ключа потребуется решить сложную с вычислительной точки зрения задачу определенияанЪно известным Е, Р, аР и ЪР.

4. ЭЛЕКТРОННЫЕ ЦИФРОВЫЕ ПОДПИСИ

4.1. Постановка задачи

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

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

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

- изменение - получатель вносит изменения в сообщение;

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

Для верификации (подтверждения) сообщения М (пользователь А - пользователю В) необходимо следующее:

1. Отправитель (пользователь А) должен внести в М подпись, содержащую дополнительную информацию, зависящую от М и, в общем случае, от получателя сообщения и известной только отправителю закрытой информации кА.

2. Необходимо, чтобы правильную подпись М: SIG{kA, М, идентификатор В } в сообщении для пользователя В нельзя было составить без кА.

3. Для предупреждения повторного использования устаревших сообщений процедура составления подписи должнп зависеть от времени.

4. Пользователь В должен иметь возможность удостовериться, что SIG{kA, М, идентификатор В} - есть правильная подпись М пользователем А.

Рассмотри эти пункты подробнее.

1. Подпись сообщения - определенный способ шифрования М путем криптографического преобразования. Закрываемым элементом кд в преобразовании

<Идентификатор В, М> 8Ю{кд, М, идентификатор В}

является 1слюч криптопреобразования.

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

<М, идентификатор В> <г 8Ю{кд, М, идентификатор В}.

в общем должна привести к определению ключа кд злоумышленником. Если множество К достаточно велико и ключ к определен методом случайного выбора, то полная проверка ключей невозможна. Говоря, что составить правильную подпись без ключа невозможно, мы имеем в виду, что определение 8Ю{кд, М, идентификатор В} без кд с вычислительной точки зрения эквивалентно поиску ключа.

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

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

4. Хотя получатель информации не может составить правильную подпись, он должен уметь удостоверять ее подлинность. В обычных коммерческих сделках, таких, например, как продажа недвижимой собственности, эту функцию зачастую выполняет третье, независимое доверенное лицо (нотариус).

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

3. Отправитель (пользователь А) должен обеспечить получателя (пользователя В) удостоверяющей инфор-

мацией АиТН{кд, М, идентификатор В}, зависящей от секретной информации кд, известной только пользователю А.

4. Необходимо, чтобы удостоверяющую информацию АиТН{кд, идентификатор В} от пользователя А пользователю В можно было дать только при наличии ключа кд.

5. Пользователь В должен располагать процедурой проверки того, что АиТН{кд, идентификатор В} действительно подтверждает личность пользователя А.

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

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

4.2. Алгоритмы электронной цифровой подниси

4.2.1. Цифровые нодписи, основанные на асимметричных криптосистемах

Для формирования системы ЭЦП можно использовать криптографическую систему Ривеста-Шамира-Адлемана.

Пользователь А вырабатывает цифровую подпись предназначенного для пользователя В сообщения М с помощью следующего преобразования

SIG(M)=E,„(E„ (М)).

При этом он использует:

- свое секретное преобразование Е ;

- открытое преобразование ев,п-в, пользователя В.

Затем он передает пользователю В пару <М, SIG(M)>.

Пользователь В может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразования EdB,n-b, с целью получения

Erf,,„, (М) =E„ (SIG(M)) = E„ (E,„ (E

(M))).

и затем открытого Е пользователя А для получения сообщения М:

М= Е,„(Е„ (М)).

Затем пользователь В производит сравнение полученного сообщения М с тем, которое он получил в результате проверки цифровой подписи, и принимает решение о подлинности/подложности полученного сообщения.

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

SIG(M)=E„ (М),

а пользователи осуществляют верификацию с использованием открытого преобразования отправителя (пользователя А):

М = Е

(SIG(M))=E,„(E„ (М)).

Вместо криптосистемы RSA для подписи сообщений можно использовать и любую другую асимметричную криптосистему.

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

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

Выбирается большое простое число р и целое число g, являющееся примитивным элементом в Zp. Эти числа публикуются. Затем выбирается секретное число х и вычисляется открытый ключ для проверки подписи у = (mod р).

Далее для подписи сообщения М вычисляется его хэш-функция т = h(M). Выбирается случайное целое к. \ <к <{р -1), взаимно простое ср - 1, и вычисляется г = (modр). После этого с помощью расширенного алгоритма Евклида решается относительно s уравнение m=xr + ks (modр-\). Подпись образует пара чисел (г, s). После выработки подписи значение к уничтожается.

Получатель подписанного сообщения вычисляет хэш-функцию сообщения т = h(M) и проверяет выполнение равенства (mod р) = = g". Корректность этого уравнения очевидна:

yy=fi=f=g4odp).

Еще одна подобная схема была предложена Шнорром. Как обычно, р - большое простое число, q - простой делитель (р -1), g - элемент порядка q в Zp, к - случайное число, х и у = g (mod р) - секретный и открытый ключи соответственно. Уравнения выработки подписи выглядят следующим образом:

г = g*" (mod р); е = h{m, r);sk + xe (mod q).

Подписью является пара (г, s). На приемной стороне вычисляется значение хэш-функции е = h{m, г) и проверяется выполнение равенства г = gy(mod р), при этом действия с показателями степени производятся по модулю q.

Другой вариант подписи Шнорра выглядит так. Для подписи сообщения т автор выбирает случайное к е Zg, вычисляет g* modр,е h(g*, т) мг = к + хе mod q. Подписью является тройка (т, е, z). Проверка подписи заключается в проверке равенства h(g> -\ т) = е.В самом деле, g> = ig = g\