3.3. Гост р 34.10-2012

В стандарте ГОСТ Р 34.10-2012 по сути в точности повторяет алгоритм формирования и проверки подписи, описанные в стандарте ГОСТ Р 34.10-2001. Основным отличие является использование нового стандарта ГОСТ Р 34.11-2012, определяющим функцию хэширования. Новый стандарт позволяет формировать хэш значения длиной 256 бит или 512 бит, в то время как в старом использовалась длина 256 бит. Это и является единственным отличием ГОСТа Р 34.10-2012 от своего предшественника – возможность выбора длина хэша.

Сравнительная таблица, описывающая основные различия в отечественных ГОСТах представлена ниже.

Таблица 1

Сравнительная характеристика отечественных госТов

ГОСТ	Хэш-функция	Размер хэша	Математический аппарат
ГОСТ Р 34.10-94	ГОСТ Р 34.11-94	256 бит	Конечное поле целых чисел
ГОСТ Р34.10-2001	ГОСТ Р 34.11-94	256 бит	Эллиптическая кривая
ГОСТ Р34.10-2012	ГОСТ Р 34.11-2012	256 или 512 бит	Эллиптическая кривая

3.4. Анализ

Надежность цифровой подписи, формируемой в стандартах ГОСТ Р 34.10 определяется стойкостью к криптоатакам двух ее компонент: хэш-функции, используемой в стандартах и самого алгоритма формирования ЭЦП.

Стойкая схема цифровой подписи должна использовать хэш-функцию, обладающую следующими свойствами [9]:

1. Односторонность. Пусть дано хэш-значение H(M) некоторого неизвестного сообщения M. Тогда вычислительно невозможно определить M по имеющемуся H(M).

2. Стойкость к столкновению. Пусть дано сообщение M и его хэш-значение H(M). Тогда вычислительно невозможно определить M’ такое, что H(M) = H(M’). Это свойство эквивалентно свойству односторонности.

3. Строгая стойкость к столкновению. Вычислительно невозможно найти два произвольных сообщения M и M’, для которых H(M) = H(M’).

Для лобовой атаки на однонаправленные хэш-функции используют два метода. Первый направлен на взлом второго свойства, т.е. по известному значению хэш-функции H(M) противник хочет создать другой документ M’, такой, что H(M’) = H(M). Другой метод изящнее, он направлен на взлом третьего свойства: противник хочет найти два случайных сообщения M и M’, таких, что H(M) = H(M’) [9].

Предположим, что однонаправленная хэш-функция надежна и лучший метод ее вскрытия – лобовой. Выход этой хэш-функции – m-разрядное число. Тогда количество выходных значений хэш-функции H равно n = 2^m .

Обозначим P(n,k) – вероятность того, что для конкретного значения X и хотя бы для одного Y_i из значений Y₁, …, Y_k, выполнялось равенство H(X) = H(Y).

Каким должно быть число k, чтобы вероятность P(n,k) была больше 0,5?

Для одного Y вероятность того, что H(X) = H(Y), равна 1/n. Соответственно, вероятность того, что H(X) ≠ H(Y), равна (1-1/n). Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1-1/n)^k. Следовательно, вероятность, по крайней мере, одного совпадения равна P(n,k) = 1 – (1-1/n)^k. Приравняв P(n,k) к 0,5, получим k = n/2 = 2^m-1

Таким образом, мы выяснили, что для нахождения сообщения, которое хэшируется к заданному значению, потребовалось бы хэширование 2^m-1 случайных сообщений. Вероятность взлома хэш-функции при этом равна 1/2^m-1=2^1-m.

Теперь рассмотрим следующую задачу: обозначим P(n,r) – вероятность того, что в множестве из r элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно r, чтобы P(n,r) была больше 0,5?

Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно n!/(n-r)!. Всего возможных способов выбора элементов равно n^r. Вероятность того, что дублей нет, равна n!/((n-r)!* n^r) . Вероятность того, что есть дубли, соответственно равна P(n,r) = 1- n!/((n-r)!* n^r). Приравняв P(n,r) к 0,5, получим r=2^m/2, где m – длина хэша.

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

Таблица 2