3.6. Цифровая (электронная) подпись

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

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

(а) подписать документ может только законный владелец подписи (следовательно, никто не может подделать подпись);

(б) автор подписи не может от нее отказаться;

(в) никто не может так изменить содержание документа, сохранив под ним чужую подпись, что владелец подписи не сможет доказать факт изменения документа;

(г) в случае возникновения спора, возможно участие третьих лиц, например, суда, для установления подлинности подписи.

3.6.1. Криптографические хеш-функции

Криптографические хеш-функции играют существенную роль во многих разделах криптографии, в том числе и при формировании цифровой подписи.

Определение: хеш-функцией называется функция

y = h(x₁, ..., x_n),

которая строке (сообщению) x = x₁...x_n произвольной длины n ставит в соответствие целое число фиксированной длины.

Примером хеш-функции является так называемая контрольная сумма для сообщения:

h(x₁, ..., x_n) = (x₁ + ... + x_n) mod 2^w,

где w – длина машинного слова. Длина слова, возвращаемого этой функцией, составляет w бит независимо от длины сообщения.

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

Сформулируем основные требования к криптографическим хеш-функциям:

• для любого заданного x вычисление h(x) должно выполняться относительно быстро;

• при известном y должно быть трудно (практически невозможно) найти x, для которого y = h(x);

• при известном сообщении x должно быть трудно найти другое сообщение x'  x такое, что h(x) = h(x');

• должно быть трудно найти какую-либо пару различных сообщений x и x', для которых h(x) = h(x').

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

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

Пусть дан блоковый шифр E_K, который для заданного блока X_i и ключа K формирует шифртекст Y = E_K(X_i). Рассмотрим алгоритмы, которые формируют значение хеш-функции, имеющее длину, равную длине блока в шифре.

Один из алгоритмов получения возвращаемого значения хеш-функции таков:

все сообщение представляется в виде последовательности блоков: X = X₁... X_n. Последний блок при необходимости дополняется нулями. Значение хеш-функции получают как результат следующего итерационного алгоритма:

h:=0;

FOR i = 1,2,...,n DO

h:= E_h(X_i)X_i.

В качестве начального значения h может использоваться не 0, а какое-то другое число, хотя это и не принципиально.

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

все сообщение представляется в виде последовательности: X = X₁... X_m, где длина элемента X_i равна длине ключа. Последний элемент при необходимости дополняется нулями. Значение хеш-функции получают как результат следующего итерационного алгоритма:

h:=0;

FOR i = 1,2,...,m DO

h:= E_Xi(h)h.

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

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

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