Длина блоков на которые делится сообщение в хэш функции sha 1 равна

Обновлено: 05.07.2024

Позднее были разработаны более эффективные версии SHA-2 (2001, 256-512 бит) и SHA-3 (Йоан Даймен, 2013, 256-512 бит).

В разделе 2 определены терминология и функции, использованные при построении формы SHA-1.

2. Определение битовых строк и целых

В описании используются обозначения для битовых последователей и целых чисел:

  1. Шестнацатеричные цифры - это . Шестнацатеричные числа A представляются в виде 4-битовых строк. Примеры: 7 = 0111, A = 1010.
  2. Слово соответствует 32-битной строке, которая может быть представлена последовательностью из 8 hex цифр. Чтобы преобразовать слово в 8 hex-цифр, каждая 4-битная строка преобразуется в ее hex-эквивалент, как это описано выше в (a). Пример:
    1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.
  3. Целое между 0 и 2 32 - 1 включительно может рассматриваться как слово. Младшие четыре бита этого целого представляют собой самую правую hex-цифру слова. Например: целое 291 = 2 8 +2 5 +2 1 +2 0 = 256+32+2+1 представляется hex-словом, 00000123.

Если z является целым, 0 64 , тогда z = (2 32 )x + y где 0 32 и 0 32 . Так как x и y могут быть представлены как слова X и Y, соответственно, z может быть представлен парой слов (X,Y).

3. Операция над словами

Со словами будут производиться следующие операции:

    Побитовые логические операции над словами

Затем 0 32 . Преобразуем z в слово, Z, и определяем Z = X + Y.

После шага (a) это дает

01100001 01100010 01100011 01100100 01100101 1.

5. Используемые функции и константы

В SHA-1 используется последовательность логических функций f(0), f(1). f(79). Каждая f(t), 0 32 , F - нелинейная функция,

Рис. 1. Алгоритм вычисления дайджеста SCH1 [5]

6.1. Метод 1

Прежде чем обрабатывать какой-либо блок, все H инициализируются следующим образом: в hex-представлении:

Теперь обрабатываются M(1), M(2), . , M(n). Чтобы обработать M(i), мы выполняем следующее:

  1. Разделяем M(i) на 16 слов W(0), W(1), . , W(15), где W(0) является самым левым словом.
  2. Для t = 16 до 79 пусть
  3. Пусть A = H0, B = H1, C = H2, D = H3, E = H4.
  4. Для t = 0 to 79 do
  5. Пусть H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.

6.2 Метод 2

Предыдущий метод предполагает, что последовательность W(0), . , W(79) представляет собой массив из 80 32-битных слов. Это эффективно с точки зрения минимизации времени вычисления, так как адреса W(t-3), . ,W(t-16) на этапе (b) легче вычислять. Когда имеется дефицит памяти, можно для < W(t) >организовать кольцевой буфер, который может использовать массив из 16 32-битных слов W[0], . W[15]. В этом случае в hex-формате получим: MASK = 0000000F. Затем обрабатываем M(i) следующим образом:

  1. Делим M(i) на 16 слов W[0], . , W[15], где W[0] - самое левое слово.
  2. Пусть A = H0, B = H1, C = H2, D = H3, E = H4.
  3. Для t = 0 до 79 выполнить
  4. Пусть H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.

7. C Code

Ниже представлена реализация SHA-1 на C. Раздел 7.1 содержит файл заголовков, 7.2 - код C, и 7.3 - тестовый драйвер.

7.1. .h file

7.2. .c file

7.3 Тестовый драйвер

Ниже приведен код основной программы тестового драйвера для проверки кода sha1.c.

Ссылки

[1] "Secure Hash Standard", United States of American, National Institute of Science и Technology, Federal Information Processing Standard (FIPS) 180-1, April 1993.

[2] "The MD4 Message Digest Algorithm," Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag,1991, pp. 303-311.

[3] Rivest, R., "The MD4 Message-Digest Algorithm", RFC1320, April 1992.

[4] [RFC 1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC1321, April 1992.

[5] Eastlake, D., Crocker, S. и J. Schiller, "Randomness Requirements for Security", RFC 1750, December 1994.

Правильные ответы выделены зелёным цветом.
Все ответы: Курс предполагает изучение методологических и алгоритмических основ и стандартов криптографической защиты информации.

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

(1) только совокупность административных мер, которые определяют порядок прохода в компьютерные классы

(1) даны точки P и Q на эллиптической кривой Ep (a,b) . Необходимо найти коэффициент k такой, что P = k×Q

(2) дана точка Q на эллиптической кривой Ep (a,b) и целое число k . Необходимо найти такую точку Р на данной кривой, чтобы P = k×Q

(3) дана точка Р на эллиптической кривой Ep (a,b) и целое число k . Необходимо найти такую точку Q на данной кривой, чтобы P = k×Q

(3) нахождение степени, в которую следует возвести простое число для получения заданного целого числа

(2) a Φ (n) ≡ 1 mod n для всех взаимнопростых a и n , где Φ(n) - число положительных чисел, меньших n и взаимнопростых с n

(1) каждая элементарная функция в алгоритме MD5 получает одно 32-битное слово на входе и на выходе создает три 32-битных слова

(2) каждая элементарная функция в алгоритме MD5 получает три 32-битных слова на входе и на выходе создает три 32-битных слова

(3) каждая элементарная функция в алгоритме MD5 получает три 32-битных слова на входе и на выходе создает одно 32-битное слово

В хэш-функции ГОСТ 3411 при вычислении промежуточного значения хэш-кода используется алгоритм симметричного шифрования ГОСТ 28147

В уравнениях эллиптических кривых бесконечно удаленная точка, в которой сходятся все вертикальные прямые, называется

(1) в протоколах аутентификации с использованием шифрования с открытым ключом участники должны знать открытый ключ AS или KDC

(2) в протоколах аутентификации с использованием шифрования с открытым ключом участники должны знать открытые ключи друг друга

(3) в протоколах аутентификации с использованием шифрования с открытым ключом участники должны знать как открытый ключ AS или KDC, так и открытые ключи друг друга

(1) в противном случае атакующий может перехватить передаваемые открытые ключи и заменить их своим открытым ключом

При использовании криптографии на эллиптических кривых в качестве аналога алгоритма Диффи-Хеллмана в уравнении PA = nA×G

(3) нахождение степени, в которую следует возвести простое число для получения заданного целого числа

(1) для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0.5, в группе должно быть всего 23 человека

(2) для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0.5, в группе должно быть всего 32 человека

(3) для того, чтобы вероятность совпадения дней рождения у двух человек была равна 1, в группе должно быть всего 23 человека

(2) a Φ(n) ≡ 1 mod n для всех взаимнопростых a и n , где Φ(n) - число положительных чисел, меньших n и взаимнопростых с n

(1) у сильной хэш-функции для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h

(2) у сильной хэш-функции вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x)

(3) у сильной хэш-функции для любого данного х вычислительно невозможно найти y ≠ x , что H (y) = H (x)

(3) криптография с использованием эллиптических кривых не может использоваться для создания общего секрета

При использовании криптографии на эллиптических кривых в качестве аналога алгоритма Диффи-Хеллмана в уравнении PA = nA×G точка G называется

(3) существуют различные протоколы, в одних ключ сессии создается KDC, в других - одним из участников А или В

(1) в криптографии с использованием эллиптических кривых все значения вычисляются по модулю n , где n – произведение двух простых чисел

(2) в криптографии с использованием эллиптических кривых все значения вычисляются по модулю простого числа р

(3) в криптографии с использованием эллиптических кривых все значения вычисляются по модулю произвольного числа р

Зависимость между ключами шифрования и дешифрования в алгоритмах симметричного шифрования должна быть следующей:

Протокол аутентификации с использованием симметричного шифрования и билета для защиты от replay-атак использует

(1) отношение числа раундов полного алгоритма к уменьшенному числу раундов, для которого существует атака

(1) сколько значений Y1, . Yk необходимо перебрать, чтобы для конкретного значения X вероятность того, что хотя бы для одного Yi выполнялось равенство H (X) = H (Y) , была бы равна 1

(2) сколько значений Y1, . Yk необходимо перебрать, чтобы для конкретного значения X вероятность того, что бы для всех Yi выполнялось равенство H (X) = H (Y) , была бы больше 0,5

(3) сколько значений Y1, . Yk необходимо перебрать, чтобы для конкретного значения X вероятность того, что хотя бы для одного Yi выполнялось равенство H (X) = H (Y) , была бы больше 0,5

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

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

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

Ch (x, y, z) = (x \wedge y) \oplus (\neg x \wedge z) \\ Maj (x, y, z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z) \\ \Sigma_</p> <p>^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus ROTR^ (x) \\ \Sigma_^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus ROTR^ (x) \\ \sigma_^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus SHR^ (x) \\ \sigma_^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus SHR^ (x)

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

Ch (x, y, z) = (x \wedge y) \oplus (\neg x \wedge z) \\ Maj (x, y, z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z) \\ \Sigma _</p> <p>^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus ROTR^ (x) \\ \Sigma _^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus ROTR^ (x) \\ \sigma _^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus SHR^ (x) \\ \sigma _^ (x) = ROTR^ (x) \oplus ROTR^ (x) \oplus SHR^ (x)

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

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

T_</p> <p>= h + \Sigma _^(e) + Ch(e, f, g) + K_^ + W_ \\ T_ = \Sigma _^(a) + Maj(a, b, c) \\ h = g \\ g = f \\ f = e \\ e = d + T_ \\ d = c \\ c = b \\ b = a \\ a = T_ + T_

где Ki - шестьдесят четыре 32-битных константы, каждая из которых является первыми 32-мя битами дробной части кубических корней первых 64 простых чисел.

W_</p> <p>= M_^ , 0 \le t \le 15 \\ W_ = \sigma _^(W_) + W_ + \sigma _^(W_) + W_ , \\ 16 \le t \le 63

i-ое промежуточное значение хэш-кода H (t) вычисляется следующим образом:

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

Основой алгоритма является модуль, состоящий из 80 циклических обработок каждого блока M (i) :

T_</p> <p>= h + \Sigma _^(e) + Ch(e, f, g) + K_^ + W_ \\ T_ = \Sigma _^(a) + Maj(a, b, c) \\ h = g \\ g = f \\ f = e \\ e = d + T_ \\ d = c \\ c = b \\ b = a \\ a = T_ + T_

где Ki - восемьдесят 64-битных констант, каждая из которых является первыми 64-мя битами дробной части кубических корней первых восьмидесяти простых чисел.

W_</p> <p>= M_^ , 0 \le t \le 15 \\ W_ = \sigma _^(W_) + W_ + \sigma _^(W_) + W_ , \\ 16 \le t \le 79

i-ое промежуточное значение хэш-кода H(t) вычисляется следующим образом:

Рассмотрим SHA-384 . Отличия этого алгоритма от SHA-512 :

  1. Другой начальный хэш-код H (0) .
  2. 384-битный дайджест получается из левых 384 битов окончательного хэш-кода H (N) :

Хэш-функция ГОСТ 34.11

Алгоритм ГОСТ 34.11 является отечественным стандартом для хэш-функций . Его структура довольно сильно отличается от структуры алгоритмов SHA-1 , 2 или MD5 , в основе которых лежит алгоритм MD4 .

  1. Генерация четырех ключей длиной 256 бит каждый.
  2. Шифрование 64-битных значений промежуточного хэш-кода H на ключах Ki(i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.
  3. Перемешивание результата шифрования.

Для генерации ключей используются следующие данные:

где степень обозначает количество повторений 0 или 1.

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

\varphi (i + 1 + 4(k - 1)) = 8i + k \\ i = 0 \div 3, k = 1 \div 8

Сдвиг А определяется по формуле

A (x) = (x_<1></p> <p>\oplus x_) || x_ || x_ || x_

xi - соответствующие 64 бита 256-битного значения х ,
|| обозначает конкатенацию.

Присваиваются следующие начальные значения:

i = 1, U = H, V = M. \\ W = U \oplus V, K_<1></p> <p>= Р (W)

Ключи K2 , K3 , K4 вычисляются последовательно по следующему алгоритму:

U = A(U) \oplus С_</p> <p>, \\ V = A(A(V)), \\ W = U \oplus V, \\ K_ = Р(W)

Далее выполняется шифрование 64-битных элементов текущего значения хэш-кода Н с ключами K1 , K2 , K3 и K4 . При этом хэш-код Н рассматривается как последовательность 64-битных значений:

Выполняется шифрование алгоритмом ГОСТ 28147 :

\Psi

Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений. Сдвиг обозначается и определяется следующим образом:

\eta _|| \eta _ || \dots || \eta _
- исходное значение
\eta _\oplus \eta _ \oplus \eta _ \oplus \eta _ \oplus \eta _ \oplus \eta _ || \eta _ || \dots || \eta _
- результирующее значение

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

\chi (M, H) = \psi ^<61></p> <p>(H \oplus \psi (M \oplus \psi ^(S)))

H - предыдущее значение хэш-кода ,
М - текущий обрабатываемый блок,
\Psi ^<i>
- i-ая степень преобразования \Psi.
Логика выполнения ГОСТ 34.11

Где обозначает следующую операцию: и Mi рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2 256 . Этот остаток и является результатом операции.

Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:

Источники:
1. описание стандарта NIST FIPS PUB 180-4, "Secure Hash Standard (SHS)", U.S. Department of Commerce, март 2012

Термины:
FIPS Federal Information Processing Standard (Федеральный стандарт обработки информации).
SHA Secure Hash Algorithm (алгоритм стойкого хэширования).
Слово – беззнаковая переменная длиной 32 бита (4 байта), либо 64 бита (8 байт), зависит от выбранного SHA-алгоритма.

SECURE HASH STANDARD (семейство криптографических функций SHA-1 и SHA-2)

Семейство криптографических функций SHA делят на два подмножества: непосредственно алгоритм SHA-1 (опубликован в 1995 году – FIPS PUB 180-1) и ряд алгоритмов под общим названием SHA-2 (опубликован в 2002 году – FIPS PUB 180-2, обновлен в 2008 году - FIPS PUB 180-3): SHA-224, SHA-256, SHA-384, SHA-512; в 2012 году в FIPS PUB 180-4 добавлены алгоритмы SHA-512/224 и SHA-512/256. Мы рассмотрим стандарт FIPS PUB 180-4, объединяющий все семейство хэш-функций SHA-1 и SHA-2.

Алгоритмы различаются по размеру блоков и слов хэшируемых данных и хэш-значений – см. таблицу 1.

Функции

SHA-1 использует последовательность нелинейных функций f0 , f1 ,…, f79. Каждая функция ft, где 0 ≤ t Ch(x, y, z) = (x AND y) XOR ( NOT x AND z)
20 ≤ t ≤ 39 Parity(x, y, z) = x XOR y XOR z
40 ≤ t ≤ 59 Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
60 ≤ t ≤ 79 Parity(x, y, z) = x XOR y XOR z

Булева алгебра.
Обратите внимание, что, например, функцию Ch может выразить по-другому:
z XOR (x AND (y XOR z))
Результат не изменится. В различных реализациях алгоритма такие варианты можно встретить.

SHA-224 и SHA-256 использует шесть нелинейных функций:

Ch(x, y, z) = (x AND y) XOR ( NOT x AND z)
Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)

Sigma0(x) = ROTR(x, 2) XOR ROTR(x, 13) XOR ROTR(x, 22)
Sigma1(x) = ROTR(x, 6) XOR ROTR(x, 11) XOR ROTR(x, 25)

Delta0(x) = ROTR(x, 7) XOR ROTR(x, 18) XOR SHR(x, 3)
Delta1(x) = ROTR(x, 17) XOR ROTR(x, 19) XOR SHR(x, 10)

SHA-384, SHA-512, SHA-512/224, SHA-512/384 использует шесть нелинейных функций:

Ch(x, y, z) = (x AND y) XOR ( NOT x AND z)
Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)

Sigma0(x) = ROTR(x, 28) XOR ROTR(x, 34) XOR ROTR(x, 39)
Sigma1(x) = ROTR(x, 14) XOR ROTR(x, 18) XOR ROTR(x, 41)

Delta0(x) = ROTR(x, 1) XOR ROTR(x, 8) XOR SHR(x, 7)
Delta1(x) = ROTR(x, 19) XOR ROTR(x, 61) XOR SHR(x, 6)

Константы

Константы Kt
00 ≤ t ≤ 19 0x5a827999
20 ≤ t ≤ 39 0x6ed9eba1
40 ≤ t ≤ 59 0x8f1bbcdc
60 ≤ t ≤ 79 0xca62c1d6

(Если вас заинтересовал вопрос, откуда взялись эти числа, то укажем их источник:
0x5A827999 = $\sqrt / 4$ , 0x6ED9EBA1 = $\sqrt / 4$ , 0x8F1BBCDC = $\sqrt / 4$ , 0xCA62C1D6 = $\sqrt / 4$ ; все умножено на 2 32 ).

64 константы (32-битные слова): K0 , K1 … K63. (Для любознательных: эти константы представляют собой первые 32 бита дробных частей кубических корней первых 64 простых чисел).

K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]

80 констант (64-битные слова): K0 , K1 … K79. (Для любознательных: эти константы представляют собой первые 64 бита дробных частей кубических корней первых 80 простых чисел).

K = [
0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,
0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694,
0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4,
0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70,
0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df,
0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30,
0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178,
0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817
]

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

image00.jpg

image01.jpg

3. Установка инициализирующих значений

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

Четыре 32-битных слова.
H0 = 0x67452301
H1 = 0xefcdab89
H2 = 0x98badcfe
H3 = 0x10325476
H4 = 0xc3d2e1f0

Восемь 32-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939,
0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4)

Восемь 32-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19)

(Для любознательных: эти значения представляют собой первые 32 бита дробных частей квадратного корня простых чисел – порядковые номера чисел: первые 8).

Восемь 64-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17,
0x152fecd8f70e5939, 0x67332667ffc00b31, 0x8eb44a8768581511,
0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4)

(Для любознательных: эти значения представляют собой первые 64 бита дробных частей квадратного корня простых чисел – порядковые номера чисел: с 9-го по 16-е).

Восемь 64-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b,
0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179)

(Для любознательных: эти значения представляют собой первые 64 бита дробных частей квадратного корня простых чисел – порядковые номера чисел: первые 8).

"SHA-512/t" - общее название для t-битной хэш-функции на основе SHA-512, результат которой усекается до t бит. Каждый вариант t-битной хэш-функция требует различных инициализирующих значений. Для этого введена специальная процедура определения начальных значений для SHA-512/t конкретного варианта t.

Процедура определения начальных значений для SHA-512/t.
1. Берем начальные значения H из алгоритма SHA-512.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b,
0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179)

2. Делаем следующие вычисления:
H0’ = H0 XOR 0xA5A5A5A5A5A5A5A5
H1’ = H1 XOR 0xA5A5A5A5A5A5A5A5
H2’ = H2 XOR 0xA5A5A5A5A5A5A5A5
H3’ = H3 XOR 0xA5A5A5A5A5A5A5A5
H4’ = H4 XOR 0xA5A5A5A5A5A5A5A5
H5’ = H5 XOR 0xA5A5A5A5A5A5A5A5
H6’ = H6 XOR 0xA5A5A5A5A5A5A5A5
H7’ = H7 XOR 0xA5A5A5A5A5A5A5A5

3. Считаем хэш от строки SHA-512("SHA-512/t") (где t может быть "224" или "256") c начальными значениями H’. Значение хэша и будет начальными значениями для алгоритма SHA-512/t:
H для SHA-512/224 = SHA512(H’, "SHA-512/224")
H для SHA-512/256 = SHA512(H’, "SHA-512/256")

Восемь 64-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x8C3D37C819544DA2, 0x73E1996689DCD4D6, 0x1DFAB7AE32FF9C82,
0x679DD514582F9FCF, 0x0F6D2B697BD44DA8, 0x77E36F7304C48942,
0x3F9D85A86A1D36C8, 0x1112E6AD91D692A1)

"SHA-512/t" - общее название для t-битной хэш-функции на основе SHA-512, результат которой усекается до t бит. Каждый вариант t-битной хэш-функция требует различных инициализирующих значений. Для этого введена специальная процедура определения начальных значений для SHA-512/t конкретного варианта t.

Процедура определения начальных значений для SHA-512/t.
1. Берем начальные значения H из алгоритма SHA-512.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b,
0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179)

2. Делаем следующие вычисления:
H0’ = H0 XOR 0xA5A5A5A5A5A5A5A5
H1’ = H1 XOR 0xA5A5A5A5A5A5A5A5
H2’ = H2 XOR 0xA5A5A5A5A5A5A5A5
H3’ = H3 XOR 0xA5A5A5A5A5A5A5A5
H4’ = H4 XOR 0xA5A5A5A5A5A5A5A5
H5’ = H5 XOR 0xA5A5A5A5A5A5A5A5
H6’ = H6 XOR 0xA5A5A5A5A5A5A5A5
H7’ = H7 XOR 0xA5A5A5A5A5A5A5A5

3. Считаем хэш от строки SHA-512("SHA-512/t") (где t может быть "224" или "256") c начальными значениями H’. Значение хэша и будет начальными значениями для алгоритма SHA-512/t:
H для SHA-512/224 = SHA512(H’, "SHA-512/224")
H для SHA-512/256 = SHA512(H’, "SHA-512/256")

Восемь 64-битных слова.
H0, H1, H2, H3, H4, H5, H6, H7 = (
0x22312194FC2BF72C, 0x9F555FA3C84C64C2, 0x2393B86B6F53B151,
0x963877195940EABD, 0x96283EE2A88EFFE3, 0xBE5E1E2553863992,
0x2B0199FC2C85B8AA, 0x0EB72DDC81C52CA2)

Вычисление хэша

В алгоритме сложение "+" происходит по модулю 2 32 .

2. Инициализируем переменные a,b,c,d,e.
a = H0 (i-1)
b = H1 (i-1)
c = H2 (i-1)
d = H3 (i-1)
e = H4 (i-1)

3. Главный цикл функции сжатия
For t = 0 to 79
TEMP = ROTL(a, 5) + ft(b,c,d) + e + Wt + Kt
e = d
d = c
c = ROTL(b, 30)
b = a
a = TEMP

4. Считаем промежуточное хэш-значение
H0 (i) = (H0 (i-1) + a)
H1 (i) = (H1 (i-1) + b)
H2 (i) = (H2 (i-1) + c)
H3 (i) = (H3 (i-1) + d)
H4 (i) = (H4 (i-1) + e)
>

В алгоритме сложение "+" происходит по модулю 2 32 .

3. Главный цикл функции сжатия
For t = 0 to 63
TEMP1 = h + Sigma1(e) + Ch(e,f,g) + Wt + Kt
TEMP2 = Sigma0(a) + Maj(a,b,c)
h = g
g = f
f = e
e = d + TEMP1
d = c
c = b
b = a
a = TEMP1 + TEMP2

4. Считаем промежуточное хэш-значение
H0 (i) = (H0 (i-1) + a)
H1 (i) = (H1 (i-1) + b)
H2 (i) = (H2 (i-1) + c)
H3 (i) = (H3 (i-1) + d)
H4 (i) = (H4 (i-1) + e)
H5 (i) = (H5 (i-1) + f)
H6 (i) = (H6 (i-1) + g)
H7 (i) = (H7 (i-1) + h)
>

H0 (N) || H1 (N) || H2 (N) || H3 (N) || H4 (N) || H5 (N) || H6 (N) (7 слов * 32 бита = 224 бита)
Внимание: порядок байт в каждом слове "big-endian"

Алгоритм похож на SHA-256, только все переменные и слова – 64-битные.
В алгоритме сложение "+" происходит по модулю 2 64 .

3. Главный цикл функции сжатия
For t = 0 to 79
TEMP1 = h + Sigma1(e) + Ch(e,f,g) + Wt + Kt
TEMP2 = Sigma0(a) + Maj(a,b,c)
h = g
g = f
f = e
e = d + TEMP1
d = c
c = b
b = a
a = TEMP1 + TEMP2

4. Считаем промежуточное хэш-значение
H0 (i) = (H0 (i-1) + a)
H1 (i) = (H1 (i-1) + b)
H2 (i) = (H2 (i-1) + c)
H3 (i) = (H3 (i-1) + d)
H4 (i) = (H4 (i-1) + e)
H5 (i) = (H5 (i-1) + f)
H6 (i) = (H6 (i-1) + g)
H7 (i) = (H7 (i-1) + h)
>

H0 (N) || H1 (N) || H2 (N) || H3 (N) || H4 (N) || H5 (N) (6 слов * 64 бита = 384 бит)
Внимание: порядок байт в каждом слове "big-endian"

H0 (N) || H1 (N) || H2 (N) || первые 32 бита H3 (N) (3 слова * 64 бита + 32 бита = 224 бит)
Внимание: порядок байт в каждом слове "big-endian"

H0 (N) || H1 (N) || H2 (N) || H3 (N) (4 слова * 64 бита = 256 бит)
Внимание: порядок байт в каждом слове "big-endian"

В NSA совместно с NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в SHA-1. Много спустя, на конференции SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма [ ]

Одна итерация алгоритма SHA1

Инициализируются пять 32-битовых переменных.

Определяются четыре нелинейные операции и четыре константы.

<\displaystyle F_<t>(m,l,k)=(m\wedge l)\vee (\neg \vee k)>
 <\displaystyle K_<t>>
= 0x5A827999		 0≤t≤19
<\displaystyle F_<t>(m,l,k)=m\oplus l\oplus k>
 <\displaystyle K_<t>>
= 0x6ED9EBA1		 20≤t≤39
<\displaystyle F_<t>(m,l,k)=(m\wedge l)\vee (m\wedge k)\vee (l\wedge k)>
 <\displaystyle K_<t>>
= 0x8F1BBCDC		 40≤t≤59
<\displaystyle F_<t>(m,l,k)=m\oplus l\oplus k>
 <\displaystyle K_<t>>
= 0xCA62C1D6		 60≤t≤79

Главный цикл [ ]

здесь Псевдокод SHA-1 [ ]

Вместо оригинальной формулировки FIPS PUB 180-1 приведены следующие эквивалентные выражения и могут быть использованы на компьютере f в главном цикле:

Примеры [ ]

Криптоанализ хеш-функций направлен на исследование уязвимости к различного вида атакам. Основные из них:

  • вторая задача требует 2 160 операций.
  • первая же требует в среднем 2 160/2 = 2 80 операций, если использовать парадокс дней рождения .

В феврале Сяоюнь Ван , Йицунь Лиза Йинь и SHA-1, которая требует менее 2 69 операций.

О методе авторы пишут:

Мы представляем набор методик и соответствующих технологий, которые могут быть использованы для устранения главных препятствий в нахождении коллизий в SHA-1. Сначала мы ищем близкие к коллизии дифференциальные пути, которые имеют небольшой "вес Хамминга" в "векторе помех", где каждый 1-бит представляет 6-шаговую локальную коллизию. Потом, мы соответствующим образом корректируем дифференциальный путь из первого раунда до другого приемлимого дифференциального пути, чтобы избежать неприемлимых последовательных коллизий и усеченных коллизий. В конце концов мы преобразуем два одноблоковых близких к коллизии дифференциальных пути в один двухблоковый коллизионный путь с удвоенной вычислительной сложностью. [1]

We introduce a set of strategies and corresponding techniques that can be used to remove some major obstacles in collision search for SHA-1. Firstly, we look for a near-collision differential path which has low Hamming weight in the "disturbance vector" where each 1-bit represents a 6-step local collision. Secondly, we suitably adjust the differential path in the first round to another possible differential path so as o avoid impossible consecutive local collisions and truncated local collisions. Thirdly, we transform two one-block near-collision differential paths into a twoblock collision differential path with twice the search complexity.

Также они заявляют:

In particular, our analysis is built upon the original differential attack on SHA-0, the near collision attack on SHA-0, the multi-block collision techniques, as well as the message modification techniques used in the collision search attacks on MD5.

Статья с описанием алгоритма была опубликована в августе SHA-1 (58 раундов), которая позволяет находить коллизии за 2 33 операций.

В августе SHA-1, с вычислительной сложностью в 2 63 операций. В декабре SHA-1, за что были удостоены награды за лучшую статью на конференции [2]


Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города [3]


Хотя теоретически SHA-1 считается взломанным (количество вычислительных операций сокращено в 2 80-63 = 131 000 раз), на практике подобный взлом неосуществим, так как займет пять миллиардов лет.


Ввиду того, что теоретические атаки на SHA-1 оказались успешными SHA-1 в цифровых подписях. [4]


2 ноября SHA-3 , который продлится до [5]

Сравнение SHA-1 с другими алгоритмами [ ]

Сравнение с MD5 [ ]

И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.

  1. Четыре этапа.
  2. Каждое действие прибавляется к ранее полученному результату.
  3. Размер блока обработки равный 512 бит.
  4. Оба алгоритма выполняют сложение по модулю 2 32 , они рассчитаны на 32-битную архитектуру.

Сравнение с ГОСТ Р 34.11-94 [ ]

Использование [ ]

Хеш-функции используются в системах контроля целостности программного кода и данных, системах электронной подписи, а также для построения кодов SHA-1 является наиболее распространенным из всего семейства SHA-1 используется в следующих приложениях:

Читайте также: