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

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

Сначала производится расширение сообщения (message palling) так, что его длина становится кратна 512. Расширенное сообщение имеет вид:

();.

Последние 64 бита последнего блока содержат значение длины исходного сообщения (отсюда ограничение на длину ).

Размер (a-l) нулевой строки равен минимальному целому числу, при котором 512 делит b + а + 64.

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

Если обозначить через - состояние

первого регистра H в момент времени i, то оно будет меняться по следующему рекуррентному правилу

,

Начальное состояние имеет вид

Последовательное соединение (конкатенация) заполнении

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

Наконец, опишем функцию . Для получения ее значений используется 5-разрядный регистр Q и 16-разрядный регистр W, каждая ячейка памяти которого также содержит слово. Значение функции представляет собой состояние регистра Q после его изменения по следующему рекуррентному правилу за 80 тактов работы.

Здесь

a W(t) получается по линейному рекуррентному соотношению из блока сообщения следующим образом

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

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

К настоящему моменту принят целый ряд американских стандартов хэш - функции с разными размерами хэш-кода от 224 до 512.

SHA-256

Алгоритм SHA-256 работает наподобие алгоритма SHA-1. Функция сжатия алгоритма работает на 512-bit блоке сообщения и 256-bit промежуточном хэш - значении (переменная связи). На самом деле функция сжатия представляет собой алгоритм 256-битного блочного шифра, который шифрует промежуточное значение хэш-функции, используя для этого блок сообщения в качестве ключа.

Обозначения

Все эти операторы действуют на 32-битные слова.

Начальное хэш значение является следующей последовательностью 32-bit слов (которые получаются путем взятия дробных частей квадратных корней первых восьми простых чисел):

Предварительная обработка

Вычисление значения хэш - кода сообщения начинается с подготовки сообщения:

1) Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512. Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Добавление состоит из единицы, за которой следует необходимое количество нулей. К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления. Для примера (8bit - ASCII) сообщение “abc” имеет длину 8*3=24 ,тогда дополняя его единичным битом, а затем 448-(24+1)=423 нулевыми битами его длина становится дополненной до 512-битного сообщения

2) Разбиваем сообщение на N 512-битовых блоков M(1), M(2),…, M(N). Первый 32-битовый блок сообщения обозначим как M(1)0, следующий 32-bit блок через M(1)1 и так далее включительно до M(1)15 блока. Далее мы используем представление big-endian, так чтобы крайний левый бит являлся старшим.

Основной цикл.

Вычисление хэш - кода продолжается следующим образом:

For i=1 to N (где N=число блоков добавленных в сообщение)

{

  Устанавливаем регистры a, b,c, d,e, f,g, h с промежуточным значением хэш-функции (оно равно первоначальному значению хэш-кода, если i=1)

  Применяем функцию сжатия алгоритма SHA-256 для обновления регистров a,..,h

For j=0 to 63

{

Основой алгоритма является модуль, состоящий из 64 циклических обработок каждого блока M{i}.

Вычисляем Ch(e,f,g),Maj(a,b,c),∑0(a), ∑1(e),Wj (смотри описание ниже)

}

  Вычисляем i-ое промежуточное хэш значение

}

является хэш - кодом М-ого блока.

Описание

Алгоритм SHA-256 использует шесть логических функций, каждая из которых выполняется над 32-битными словами (обозначенные как x, y,z). Результатом каждой функции является 32-битное слово.

Каждая функция определяется следующим образом:

Расширенные блоки сообщения вычисляются как следует ниже через расписание сообщения алгоритма SHA-256:

Последовательность постоянных слов (констант), , используемых в SHA-256 в шестнадцатеричном виде:

Каждая из этих констант является первыми 32-мя битами дробной части кубических корней первых 64-х простых чисел.

Схема работы

Функция сжатия алгоритма SHA-256 приведена ниже

Рис : внутренний шаг функции сжатия C алгоритма SHA-256 где символ означает сложение по .