Пошаговое объяснение хеш-функции SHA-256

Введение

Хеш-функция — это просто функция, которая принимает входные данные переменной длины и выдает выходные данные определенной длины. SHA-256 — одна из таких функций. Он преобразует ввод с максимальным размером (2⁶⁴-1) бит в 256-битное значение, называемое хэшем.

Шаг 1. Предварительная обработка

Предположим, что входным сообщением является слово media. В двоичном виде это переводится как

01101101 01100101 01100100 01101001 01110101 01101101

• Добавить 1 как один бит в конце

01101101 01100101 01100100 01101001 01110101 01101101 1

• Добавляйте к этому нули, пока количество битов не станет кратным 512.

01101101 01100101 01100100 01101001 01110101 01101101 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000

• Замените последние 64 бита длиной исходного ввода в виде целого числа с обратным порядком байтов.

01101101 01100101 01100100 01101001 01110101 01101101 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00111000

Шаг 2. Расписание сообщений

• Реструктурируйте все это как массив из 16 слов, это называется расписанием сообщений.

w = [
01101101011001010110010001101001, 01110101011011011000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000111000]

• Запустите этот цикл, чтобы создать остальную часть расписания сообщений.

For i from 16 to 63:
  s0 = (w[i-15] rightrotate 7) xor 
       (w[i-15] rightrotate 18) xor   
       (w[i-15] rightshift 3)
  
  s1 = (w[i- 2] rightrotate 17) xor 
       (w[i- 2] rightrotate 19) xor 
       (w[i- 2] rightshift 10)
  
  w[i] = w[i-16] + s0 + w[i-7] + s1

Например, давайте вычислим для i = 16

s0 = (01110101011011011000000000000000 rightrotate  7) xor 
     (01110101011011011000000000000000 rightrotate 18) xor   
     (01110101011011011000000000000000 rightshift   3)
   
   = 00000000111010101101101100000000 xor
     01100000000000000001110101011011 xor
     00001110101011011011000000000000 
   
   = 01101110010001110111011001011011
s1 = (00000000000000000000000000000000 rightrotate 17) xor 
     (00000000000000000000000000000000 rightrotate 19) xor 
     (00000000000000000000000000000000 rightshift 10)
  
   = 00000000000000000000000000000000 xor
     00000000000000000000000000000000 xor
     00000000000000000000000000000000
   
   = 00000000000000000000000000000000
w[16] = 01101101011001010110010001101001 +  
        01101110010001110111011001011011 + 
        00000000000000000000000000000000 +
        00000000000000000000000000000000
      
      = 11011011101011001101101011000100

• Проделав все это, мы получаем

w = [ 
01101101011001010110010001101001, 01110101011011011000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000110000, 11011011101011001101101011000100, 01110101100010001000000000000000,
11110110000011000001110110010101, 01010000000111010101011001010101,
10001101010001011100011011000000, 00000001111101000000010101011000,
01011011100110110000011010110011, 01011101101101000101100010001001,
01011001001000011010000001111111, 10011101000011110000011000001111,
00110100100000110110011000110001, 11110000111001110100010110100111,
11100001100001111010000101100000, 10100101111101100100011001110001,
11110010011001100110010110101011, 11101001011101010011000010010001,
10100101001100100001110000011011, 00011011001101101010000100010011,
00101001100100100001001001010101, 10010110110101000010101100001110,
00110000010100101000101110001100, 00110001000001100001011111111010,
10001000011110101011011010010010, 10001010001111101101010011010001,
01101110111010100000011010111111, 00010101011010011111101101111011,
10001110100000000100101101101110, 00011010001110101100011010101001,
10100110111100000011110100011011, 01011001101110011001101011010101,
11001011100000111000110001010011, 00011100101100000110111111010100,
00111101010001010001001110010101, 00110001111111011001101001100000,
10110010011101001000100111001110, 10110110000000001110001001000010,
01110011111110101101101101001000, 01100111100001100111001111100110,
10100101011000110011010101010110, 00101111000001101111011001110101,
11100010101011010100100110110010, 11000111001100111110001110000010,
10111100001010011001111111010111, 11000001000100010010011111011101,
01110101001000101110101011111000, 00000001011100110111000110000000,
10101001111000100100100101100000, 11110000010011000001110011010101]

Шаг 3. Инициализируйте константы

• Создайте массив с 32 битами дробной части квадратного корня из первых 8 простых чисел.

h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 
     0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

• Создайте массив с 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]

Шаг 4. Инициализируйте рабочие переменные

• Создайте 8 переменных (a,b,..,h) и присвойте им (h[0], h[1], …, h[7])

a = h[0]
b = h[1]
c = h[2]
d = h[3]
e = h[4]
f = h[5]
g = h[6]
h = h[7]

Шаг 5. Цикл сжатия

• Запустите этот цикл, чтобы изменить значения a, b, …, h

for i from 0 to 63
        S1    = (e rightrotate  6) xor 
                (e rightrotate 11) xor 
                (e rightrotate 25)
        ch    = (e and f) xor ((not e) and g)
        
        temp1 = h + S1 + ch + k[i] + w[i]
        
        S0    = (a rightrotate 2) xor 
                (a rightrotate 13) xor 
                (a rightrotate 22)
        maj   = (a and b) xor (a and c) xor (b and c)
        temp2 = S0 + maj
 
        h = g
        g = f
        f = e
        e = d + temp1
        d = c
        c = b
        b = a
        a = temp1 + temp2

Например, давайте вычислим a, b, …, h, когда i = 0

S1 = (01010001000011100101001001111111 rightrotate  6) xor 
     (01010001000011100101001001111111 rightrotate 11) xor 
     (01010001000011100101001001111111 rightrotate 25)
   = 11111101010001000011100101001001 xor  
     01001111111010100010000111001010 xor
     10000111001010010011111110101000

   = 00110101100001110010011100101011
ch = (01010001000011100101001001111111 and 
      10011011000001010110100010001100) 
     xor 
     ((not 01010001000011100101001001111111) and 
     00011111100000111101100110101011)
     
   = 00011111100001011100100110001100  
temp1 = 01011011111000001100110100011001 + 
        00110101100001110010011100101011 +
        00011111100001011100100110001100 + 
        01000010100010100010111110011000 + 
        01101101011001010110010001101001
    
      = 01100000110111010101000111010001
S0    = (01101010000010011110011001100111 rightrotate 2) xor 
        (01101010000010011110011001100111 rightrotate 13) xor 
        (01101010000010011110011001100111 rightrotate 22)
      = 11011010100000100111100110011001 xor
        00110011001110110101000001001111 xor
        00100111100110011001110110101000
   
      = 11001110001000001011010001111110
maj   = (01101010000010011110011001100111 and 
         10111011011001111010111010000101) 
        xor 
        (01101010000010011110011001100111 and  
         00111100011011101111001101110010) 
        xor 
        (10111011011001111010111010000101 and 
         00111100011011101111001101110010)
      
      = 00111010011011111110011001100111
temp2 = 11001110001000001011010001111110 + 
        00111010011011111110011001100111
      = 00001000100100001001101011100101
h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e = 10100101010011111111010100111010 + 
    01100000110111010101000111010001
  
  = 00000110001011010100011100001011
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a = 01100000110111010101000111010001 + 
    00001000100100001001101011100101
 
  = 01101001011011011110110010110110

• Вычислив это еще 63 раза для i = 1, i = 2, …, i = 63, мы получим

a = 0x56785f03
b = 0xbbff33b5
c = 0xdc6c14da
d = 0x2dfb7abb
e = 0xbfac9cd1
f = 0xca43500b
g = 0xacfd100c
h = 0x780054af

Шаг 6: Обновление хеш-значений

• Теперь мы обновляем значения h[0], h[1],…, h[7], делая это

h[0] = h[0] + a = 0xc082456a
h[1] = h[1] + b = 0x7766e23a
h[2] = h[2] + c = 0x18db084c
h[3] = h[3] + d = 0xd34b6ff5
h[4] = h[4] + e = 0x10baef50
h[5] = h[5] + f = 0x6548b897
h[6] = h[6] + g = 0xcc80e9b7
h[7] = h[7] + h = 0xd3e121c8

Шаг 7. Зацикливание фрагментов

• Теперь, поскольку наш ввод (слово среда) настолько мал, у нас был только один фрагмент из 512 бит. Но предположим, что нам нужен хэш сообщения большего размера, у нас будет более одного фрагмента из 512 бит. В этом случае нам нужно будет выполнить шаги 2,4,5 для каждого отдельного фрагмента.

Шаг 8: Окончательное значение хеш-функции

• После обработки каждой отдельной порции из 512 бит (в нашем случае только 1), мы объединяем вместе h[0], h[1], …, h[7] в указанном порядке, чтобы получить хэш.

hash = h[0] append 
       h[1] append 
       h[2] append 
       h[3] append 
       h[4] append 
       h[5] append 
       h[6] append 
       h[7]
     = c082456a7766e23a18db084cd34b6ff510baef506548b897cc80e9b7d3e121c8

• Теперь мы вычислили хэш слова media.