Цифровая сигнатура

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

Цифровая сигнатура - это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.

[ Пользователь А ") сообщение

сигнатура

Цифровая сигнатура

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

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

Рассмотрим типичную схему цифровой сигнатуры.

Пусть Е - функция симметричного шифрования и/- функция отображения некоторого множества сообщений на подмножество мощности р из последовательности {1,п].

Например р=3 и п=9. Если т - сообщение , то в качестве / можно взять функцию f(m) = {2, 5, 7}.

Для каждого сообщения пользователь А выбирает некоторое множество ключей =[1, и параметров V={vi, ...,¥„} для использования в качестве

пометок сообщения, которое будет послано В. Множества V и Y={E{yi,Ki) Е(\п,Кп)} посылаются пользователю В и заранее выбранному посреднику С.

Пусть т - сообщение и idm - объединение идентификационных номеров отправителя, получателя и номера сообщения. Если/({idm, m}), то цифровая сигнатура т есть множество K=[Ki, Щ}. Сообщение т, идентификационный номер idm и цифровая сигнатура К посылаются В.

Пользователь А

Пользователь В

V, V

Посредник С I

Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию/({idm, m}) и проверяет ее равенство К. Затем он проверяет, что подмножество {vi, ...,Vj} правильно зашифровано в виде подмножества {Е{у,К) E(Vj,/rj)} множества V.

В конфликтной ситуации В посылает С сообщение т, идентификационный номер idm и множество ключей К\ которое В объявляет сигнатурой т. Тогда посредник С так же, как и В, будет способен проверить сигнатуру. Вероятность раскрытия двух сообщений с одним и тем же значением функции/должна быть очень мала. Чтобы гарантировать это, число п должно быть достаточно большим, а число р должно быть больше 1, но меньше п.

Ряд недостатков этой модели очевиден:

• должно быть третье лицо - посредник, которому доверяют как получатель, так и отправитель;

• получатель, отправитель и посредник должны обменяться существенным объемом информации, прежде чем будет передано реальное сообщение;

• передача этой информации должна осуществляться в закрытом виде;

• эта информация используется крайне неэффективно, поскольку множества К, V, V используются только один раз.

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

Хэш-функции

Использование цифровой сигнатуры предполагает использование некоторых функций шифрования:

S = Щк, Т),

где S - сигнатура, к - ключ, Т - исходный текст.

Функция Н(к, Т) - является хэш-функцией, если она удовлетворяет следующим условиям:

1) исходный текст может быть произвольной длины;

2) само значение Н(к, Т) имеет фиксированную длину;

3) значение функции Н(к, Т) легко вычисляется для любого аргумента;

4) восстановить аргумент по значению с вычислительной точки зрения -практически невозможно;

5) функция Щк, Т) - однозначна".

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

Наиболее известные из хэш-функций - MD2, MD4, MD5 и SHA.

Три алгоритма серии MD разработаны Ривестом в 1989-м, 90-м и 91-м году соответственно. Все они преобразуют текст произвольной длины в 128-битную сигнатуру.

Алгоритм MD2 предполагает:

• дополнение текста до длины, кратной 128 битам;

• вычисление 16-битной контрольной суммы (старшие разряды отбрасываются);

• добавление контрольной суммы к тексту;

• повторное вычисление контрольной суммы. Алгоритм MD4 предусматривает:

• дополнение текста до длины, равной 448 бит по модулю 512;

• добавляется длина текста в 64-битном представлении;

• 512-битные блоки подвергаются процедуре Damgard-Merkle, причем каждый блок участвует в трех разных циклах.

В алгоритме MD4 довольно быстро были найдены «дыры», поэтому он был заменен алгоритмом MD5, в котором каждый блок участвует не в трех, а в четырех различных циклах.

Алгоритм SHA (Secure Hash Algorithm) разработан NIST (National Institute of Standard and Technology) и повторяет идеи серии MD. В SHA используются тексты более 2 бит, которые закрываются сигнатурой длиной 160 бит. Данный алгоритм предполагается использовать в программе Capstone.

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

Факт теории вероятностей: в группе из 23 человек с вероятностью больше 0.5 два и более человека родились в одно и то же число.

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

" Государственная программа США, предполагаюш,ая централизованное хранение всех ключей, используемых

организациями а частными лицами.