9.3. Алгоритм sha-1

Алгоритм SHA (Secure Hash Algorithm) является частью стандарта SHS, принятого АНБ и Национальным институтом стандартов и технологий США в 1993 году. Для версии SHA-1 длина хэш-кода составляет 160 битов.

В конец сообщения , которое представлено в виде строки битов, приписывается бит, равный 1. Затем, при необходимости, дописываются нули, таким образом, чтобы длина полученного сообщения, увеличенная на 64, была кратна 512.

Далее формируется сообщение, состоящее из блоков длиной 512 битов, в последнем блоке которого зарезервировано поле длиной в 64 бита.

В этом поле размещается число, равное исходной длине сообщения (без дописок).

Расширенное сообщение обрабатывается блоками по 512 битов.

При этом отдельный блок рассматривается как массив, состоящий из 16 слов, каждое длиной в 32 бита.

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

Блок является конкатенцией пяти зарезервированных начальных значений, каждое длиной в 32 бита, которые в шестнадцатиричной системе счисления имеют следующий вид:

,,,,.

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

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

Результат работы последнего цикла дает значение хэш-кода .

Каждый цикл состоит из 80 шагов. На шаге цикла с номеромобрабатывается слово, длиной в 32 бита.

В начале каждого цикла создаются копии переменных :.

Слова, обрабатываемые на цикле , образуются из блокаследующим образом.

1. Блок рассматривается как последовательность 16 слов,, исходя из которых,по рекуррентному закону формируются остальные 64 слова. Рекуррентное соотношение имеет вид:

, .

Здесь функция означает циклический сдвиг слова нарозрядов влево, а операція является поразрядной суммой слов по модулю два.

2. Обработка восьмидесяти слов выполняется последовательно, группами, по 20 слов в группе.

Каждой из четырех групп соответствуют 20 шагов цикла (один раунд):;;;.

Кроме того, с каждым раундом ,, связана своя константадлиной в 32 бита и функцияот трех переменных, каждая из которых является словом той же длины.

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

3. Обработка очередного слова приводит к изменению слов , что выглядит следующим образом:

, ,,,.

Здесь – вспомогательная переменная, а сложение производится по модулю.

4. После 80 шагов обработки блока сообщения цикл завершается модификацией переменных :,,,,(сложение по).

Конец цикла.

Для полноты, приведем и, которые используются в циклах,.

, ;

, ;

, ;

, .

9.4. Стандарты алгоритмов формирования и проверки эцп

Один из первых стандартов ЭЦП DSS был предложен NIST в 1991 году для правительственных систем (используется совместно с функцией хэширования сообщений SHA-1 ‑Secure Hash Algorithm).

В 1994 году ФАПСИ РФ был разработан стандарт ГОСТ Р34.10 цифровой подписи совместно с функцией хэширования – ГОСТ Р34.11, которые в качестве межгосударственных были приняты в Украине (ГОСТ 34.310 и ГОСТ 34.311 соответственно).

Механизмы цифровой подписи, рекомендованые DSS и ГОСТ Р34.10 основаны на сложности задачи дискретного логарифмирования. Размер ключа – 512 или 1024 бита.

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

Пусть – простое число и– элемент большого порядка по модулю, Скажем, для простоты,– примитивный элемент поля вычетов по модулю. Поясним суть дела подробнее.

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

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

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

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

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

1. Сгенерировать случайное секретное число в интервале, взаимно простое с.

2. Вычислить .

3. Для сообщения вычислить значение хэш-функции(хэш-код).

4. Присвоить значения формальным параметрам сравненияв виде, что дает сравнение.

5. Решить полученное сравнение относительно :.

6. В качестве подписи для сообщения принимаем пару.

Проверка подписи заключается в проверке соотношения , поскольку при истинных значениях параметров.

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

Примечание. Особые случаи обычно оговариваются отдельно и учитываются при проверке ЦП. Например, при илиперейти на выбор нового рандомизатора; припринять.

Схема цифровой подписи Эль-Гамаля [11] послужила основой для построения целого семейства схем, в зависимости от значений, присвоенных вектору параметров из множества векторов-перестановок чисел.

В частности, в алгоритме DSA ,.

Поэтому и.

Проверочное соотношение для DSA задается в виде , где,.

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

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

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

В последнее время активно развивается направление, связанное с построением криптографических алгоритмов, использующих аппарат эллиптических кривых (ECC). Именно с целью решения проблемы возрастания длин ключей, в 2000-2002 г.г. в США, России и Украине (ДСТУ 4145-2002) были введены в действие стандарты ЦП, базирующиеся на применении эллиптических кривых.

В ряде изданий приводятся данные об эквивалентных длинах ключей. Некоторые условно эквивалентные длины ключей сведены в таблицу 9.2.

Таблица 9.2. Эквивалентные длины ключей

Длина ключа в битах			Число вариантов ключей
Симметричные системы	RSA системы	ЕСС системы
56-64	384-512	112	10^17-10^19
80	768	132	10^24
112	1792	160	10^34
128	2304	240	10^38