Логика выполнения SHA-1

Функция SHA-1

Хэш-

Безопасный хэш-алгоритм (Secure Hash Algorithm) был разработан национальным институтом стандартов и технологии (NIST) и опубликован в качестве федерального информационного стандарта (FIPS PUB 180) в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4.

Алгоритм получает на входе сообщение максимальной длины 2⁶⁴ бит и создает в качестве выхода дайджест сообщения длиной 160 бит.

Алгоритм состоит из следующих шагов:

Шаг 1: добавление недостающих битов

Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512 (длина = 448 mod 512). Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления.

Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y₀, Y₁,..., Y_L-1, так что общая длина расширенного сообщения есть L * 512 бит. Таким образом, результат кратен шестнадцати 32-битным словам.

Шаг 3: инициализация SHA-1 буфера

Используется 160-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как пять 32-битных регистров A, B, C, D и E. Эти регистры инициализируются следующими шестнадцатеричными числами:

A = 67452301

B = EFCDAB89

C = 98BADCFE

D = 10325476

E = C3D2E1F0

Шаг 4: обработка сообщения в 512-битных (16-словных) блоках

Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как H_SHA. Все 80 циклических обработок имеют одинаковую структуру (рис 9.7).

Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Y_q и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера.

В каждом цикле используется дополнительная константа К_t, которая принимает только четыре различных значения:

0 ≤ t ≤ 19 K_t = 5A827999 (целая часть числа [2³⁰ × 2^1/2])

20 ≤ t ≤ 39 K_t = 6ED9EBA1 (целая часть числа [2³⁰ × 3^1/2])

40 ≤ t ≤ 59 K_t = 8F1BBCDC (целая часть числа [2³⁰ × 5^1/2])

60 ≤ t ≤ 79 K_t = CA62C1D6 (целая часть числа [2³⁰ × 10^1/2])

	SHAq (160 бит)

Рис. 9.7. Обработка очередного 512 битного блока

по алгоритму SHA -1

Для получения SHA_q+1 выход 80-го цикла складывается со значением SHA_q. Сложение по модулю 2³² выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHA_q.

Шаг 5: выход

После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битного блока.

Рис. 9.8. Логика выполнения отдельного цикла SHA-1

A_q+1 = E_q + f_t(B_q, C_q, D_q) +CLS₅(A_q) + W_t +K_t

B_q+1 = A_q

C_q+1 +CLS₃₀(B_q)

D_q+1 = C_q

E_q+1 = D_q

где: A, B, C, D, E - пять слов буфера;

t - номер цикла, 0 ≤ t ≤79;

f_t - элементарная логическая функция;

CLS_s- циклический левый сдвиг 32-битного аргумента на s битов;

W_t - 32-битное слово, полученное из текущего входного 512-битного блока;

K_t - дополнительная константа;

+ - сложение по модулю 2³².

Каждая элементарная функция получает на входе три 32-битных слова и создает на выходе одно 32-битное слово. Элементарная функция выполняет набор побитных логических операций, т.е. n -ый бит выхода является функцией от n -ых битов трех входов. Функции следующие:

Номер цикла	ft (B, C, D)
(0 ≤ t ≤ 19)	(B ^ C) V (¬ B ^ D)
(20 ≤ t ≤ 39)	B Å C Å D
(40 ≤ t ≤ 59)	(B ^C) V (B ^D) V (C ^D)
(60 ≤ t ≤ 79)	B Å C Å D

32-битные слова W_t получаются из очередного 512-битного блока сообщения следующим образом.

Рис. 9.9. Схема получения входных значений

цикла из очередного блока

Хэш-функции SHA – 2

В 2001 году NIST (Национальный институт стандартов и технологии США) принял в качестве стандарта три хэш-функции с существенно большей длиной хэш-кода. Часто эти хэш-функции называют SHA-2 или SHA-256, SHA-384 и SHA-512 (соответственно, в названии указывается длина создаваемого ими хэш-кода). Эти алгоритмы отличаются не только длиной создаваемого хэш-кода, но и длиной обрабатываемого блока, длиной слова и используемыми внутренними функциями.

В данных алгоритмах размер блока сообщения равен m бит. Для SHA-256 m = 512, для SHA-384 и SHA-512 m = 1024. Каждый алгоритм оперирует с w -битными словами. Для SHA-256 w = 32, для SHA-384 и SHA-512 w = 64. В алгоритмах используются обычные булевские операции над словами, а также сложение по модулю 2^w, правый сдвиг на n бит SHRⁿ (x), где х – w-битное слово, и циклические (ротационные) правый и левый сдвиги на n бит ROTRⁿ (x) и ROTLⁿ (x), где х – w -битное слово.

Сравнительные характеристики хэш-функций

Алгоритм	Длина сообщения (бит)	Длина блока (бит)	Длина слова (бит)	Длина кода хэш-функции (бит)	Безопасность (бит)
SHA-1	<2^64
SHA-256	<2^64
SHA-384	<2^128
SHA-512	<2^128

Под безопасностью здесь понимается стойкость к атакам типа "парадокса дня рождения".

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

Ch (x, y, z) = (x & y) Å (¬x & z)

Maj (x, y, z) = (x & y) Å (x & z) Å (y & z)

Σ₀^{256} (x) = ROTR² (x) Å ROTR¹³ (x) Å ROTR²² (x)

Σ₁^{256} (x) = ROTR⁶ (x) Å ROTR¹¹ (x) Å ROTR²⁵ (x)

σ₀^{256} (x) = ROTR⁷ (x) Å ROTR¹⁸ (x) Å SHR³ (x)

σ₁^{256} (x) = ROTR¹⁷ (x) Å ROTR¹⁹ (x) Å SHR¹⁰ (x)

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

Ch (x, y, z) = (x & y) Å (¬x & z)

Maj (x, y, z) = (x & y) Å (x & z) Å (y & z)

Σ₀^{512} (x) = ROTR²⁸ (x) Å ROTR³⁴ (x) Å ROTR³⁹ (x)

Σ₁^{512} (x) = ROTR¹⁴ (x) Å ROTR¹⁸ (x) Å ROTR⁴¹ (x)

σ₀^{512} (x) = ROTR¹ (x) Å ROTR⁸ (x) Å SHR⁷ (x)

σ₁^{512} (x) = ROTR¹⁹ (x) Å ROTR⁶¹ (x) Å SHR⁶ (x)

Предварительная подготовка сообщения, т.е. добавление определенных битов до целого числа блоков и последующее разбиение на блоки выполняется аналогично тому, как это делалось в MD5 (конечно, с учетом длины блока каждой хэш-функции). После этого каждое сообщение можно представить в виде последовательности N блоков M⁽¹⁾, M⁽²⁾, …, M^(N).

Рассмотрим SHA-256. В этом случае инициализируются восемь 32-битных переменных, которые послужат промежуточным значением хэш-кода:

Дата добавления: 2014-01-07