Современная прикладная криптография (стр. 25 )

Существенным в схеме Эль Гамаля является то, что элементы данных (M. r.s), передаваемых проверяющему, связаны линейно, то есть соотношением вида

,

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

Знаки выбраны так, чтобы в проверочных соотношениях не было отрицательных степеней, и они соответственно имели бы вид:

Отсюда видно, как изменятся процедура подписи и проверки при вычислении r и s одним из приведенных шести способов. Так, при (1 и 2 случай) или (3 и 4 случай) при подписи приходится вычислять соответственно или . В случае (5 и 6 случай) этого делать не надо. Вычисление можно также отнести к предварительной работе, когда вырабатывается ключ подписи х. Соответственно, при проверке надо вычислять (1 и 2 случай), (3 и 6 случай) и (4 и 5 случай).

Стандарты США и России соответствуют I и 5 из приведенных случаев соответственно.

Помимо необходимости вычислять , , и необходимо само существование этих обратимых элементов, что гарантируется их взаимной простотой с модулем (p-l) . Проверка взаимной простоты также требует дополнительного времени на подписывание, поэтому естественно гарантировать существование этих обратных элементов за счет выбора в качестве модуля простого числа q, являющегося делителем числа (p-l). В качестве q надо взять наибольший простой делитель числа (p-l), который должен существовать по требованию усложнения методов логарифмирования и увеличения стойкости схемы. При этом произойдет и уменьшение показателя степени, в которую надо возводить числа при проверке подписи, а также уменьшится размер самой подписи, что важно для экономии памяти.

Наконец, в качестве надо взять элемент g порядка q, степени которого {} пробегают все множество чисел {1,...,q-1}, и все проверочное соотношение привести по модулю q, так как левая его часть нам тоже нужна в виде.

Для сравнения американского и российского стандартов цифровой подписи выпишем их параллельно друг другу.

FIPS PUB 186	ГОСТ Р 50 34.10-94
,	или
, имеет порядок q	имеет порядок q

Процедура	подписи
(предварительно найти )

Процедура проверки подписи по

Для полного соответствия предыдущим рассуждениям надо в них вместо сообщения М иметь в виду значение H(M) функции хэширования H. Кроме того, в приведенной таблице опущены для сокращения изложения проверки неравенство , , а также замена Н(М) на 1 в случае в российском стандарте, что необходимо для существования обратного элемента к H(M) по модулю q.

Если проверка неравенств не производится (например, из-за ошибки программиста при реализации проверки), то это позволяет подделать подпись методом из работы [].

Приведенный материал дает возможность показать этапы становления этих стандартов из классической цифровой подписи Эль Гамаля.

3.3 Развитие американских стандартов хэш-функции.

Первый американский стандарт хэш-функции (Secure Hash Standard) принят в 1993г. Это был первый стандарт, позже были приняты и другие. Стандарт был разработан на основе алгоритма хэш-функции MD4, предложенного Райвестом [104]. Стандарт содержит описание односторонней функции хэширования без ключа (MDC), преобразующий двоичное сообщение длины меньшей в строку длины 160 бит, называемую хэш-кодом или дайджестом сообщения (message digest). Размер хэш-кода согласован с размером входа алгоритма цифровой подписи DSS (FIPS PUB 186-94).

Приведем основные используемые обозначения и понятия. Словом (word) называется 32-битовая строка, которая может представлять собой и целое число из множества 0,. Наряду с этим рассматриваются и шестнадцатеричные цифры (hex digit) - элементы множества {0,1,...,9,A,...,F}, которые представляют 4-битовые строки (7 = 0111, A = 1010). Наконец, блок (block) - это 512-битовая строка =16 слов.

Символ "+" обозначает сложение слов, как чисел по модулю 232, символы "", "", "", "-", обозначают соответственно побитовое умножение, логическое сложение, сложение по модулю два, логическое отрицание. Через (или х«n) обозначен оператор циклического сдвига слова х на n позиций влево.