Пошаговая визуализация SHA-256

Зачем разбирать SHA-256 изнутри

Майнинг Bitcoin — это вычисление SHA-256 миллиарды раз в секунду. ASIC-майнеры стоимостью тысячи долларов заточены под один-единственный алгоритм. Но что именно происходит внутри SHA-256? Давайте разберем каждый шаг.

Цель урока: Вы сможете объяснить каждый этап SHA-256, от дополнения сообщения до финального хеша. И реализуете его на Python с нуля.

Обзор алгоритма

SHA-256 (Secure Hash Algorithm, 256-bit) определен в стандарте FIPS PUB 180-4. Алгоритм состоит из четырех основных этапов:

Шаг 1: Дополнение (Padding)

Перед хешированием сообщение нужно дополнить до длины, кратной 512 битам. Процесс:

1. Добавить бит 1 после сообщения
2. Добавить нулевые биты до тех пор, пока длина не станет конгруэнтна 448 mod 512
3. Добавить исходную длину сообщения как 64-битное число (big-endian)

Пройдите все шаги интерактивно:

Почему именно такое дополнение?

• Бит 1 отделяет исходные данные от padding — без него "abc\x00" и "abc" имели бы одинаковый padded-блок
• Длина в конце предотвращает атаки, где злоумышленник добавляет данные к сообщению
• 448 mod 512 — оставляет ровно 64 бита (8 байт) для длины

Шаг 2: Расписание сообщений (Message Schedule)

Каждый 512-битный блок разбивается на 16 слов по 32 бита (W0-W15). Затем эти 16 слов расширяются до 64 с помощью sigma-функций:

W[t] = sigma1(W[t-2]) + W[t-7] + sigma0(W[t-15]) + W[t-16]

Где:

• sigma0(x) = ROTR(x, 7) XOR ROTR(x, 18) XOR SHR(x, 3)
• sigma1(x) = ROTR(x, 17) XOR ROTR(x, 19) XOR SHR(x, 10)

Шаг 3: 64 раунда сжатия

Это сердце SHA-256. Восемь рабочих переменных a, b, c, d, e, f, g, h инициализируются начальными хеш-значениями и проходят через 64 раунда трансформации.

Формулы одного раунда

В каждом раунде i (от 0 до 63):

T1 = h + Sigma1(e) + Ch(e, f, g) + K[i] + W[i]
T2 = Sigma0(a) + Maj(a, b, c)

h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2

Где:

• Ch(e, f, g) = (e AND f) XOR (NOT e AND g) — функция “выбора” (e выбирает между f и g)
• Maj(a, b, c) = (a AND b) XOR (a AND c) XOR (b AND c) — функция “большинства”
• Sigma0(a) = ROTR(a, 2) XOR ROTR(a, 13) XOR ROTR(a, 22)
• Sigma1(e) = ROTR(e, 6) XOR ROTR(e, 11) XOR ROTR(e, 25)
• K[i] — раундовая константа (первые 32 бита дробных частей кубических корней первых 64 простых чисел)
• W[i] — слово из расписания сообщений

Интерактивная визуализация

Пройдите через все 64 раунда шаг за шагом. Обратите внимание, как переменные “прокручиваются” вниз (b=a, c=b, …), а a и e получают новые вычисленные значения:

Начальные значения (FIPS 180-4)

Начальные значения H0-H7 — это первые 32 бита дробных частей квадратных корней первых 8 простых чисел:

H0 = 6a09e667  (sqrt(2))
H1 = bb67ae85  (sqrt(3))
H2 = 3c6ef372  (sqrt(5))
H3 = a54ff53a  (sqrt(7))
H4 = 510e527f  (sqrt(11))
H5 = 9b05688c  (sqrt(13))
H6 = 1f83d9ab  (sqrt(17))
H7 = 5be0cd19  (sqrt(19))

Это не магические числа — они выбраны как “nothing up my sleeve” значения, которые может проверить любой.

Шаг 4: Финальный хеш

После обработки всех блоков финальный хеш — это конкатенация значений H0-H7:

hash = H0 || H1 || H2 || H3 || H4 || H5 || H6 || H7

Для сообщения “abc”:

SHA-256("abc") = ba7816bf 8f01cfea 414140de 5dae2223
                 b00361a3 96177a9c b410ff61 f20015ad

Почему SHA-256 безопасен?

1. Нелинейные операции: Ch и Maj перемешивают биты нелинейным образом
2. Вращения и сдвиги: Sigma и sigma функции распространяют изменения по всем битам
3. Сложение mod 2^32: Необратимая операция (информация теряется при переполнении)
4. 64 раунда: Достаточно раундов для полной диффузии — каждый бит входа влияет на каждый бит выхода

Реализация на Python

Полная реализация SHA-256 на чистом Python доступна в notebook 03-hashing.ipynb. Она следует FIPS PUB 180-4 и включает:

• Функции padding, parsing, message schedule
• Все 64 раундовые константы K[]
• Пошаговый вывод рабочих переменных на каждом раунде
• Проверку против hashlib.sha256()

# Предварительный просмотр: чистый Python SHA-256
def sha256_educational(message: bytes) -> str:
    """SHA-256 с выводом промежуточных значений для обучения."""
    # 1. Padding
    padded = pad_message(message)
    # 2. Parse blocks
    blocks = parse_blocks(padded)
    # 3. Process each block
    H = list(INITIAL_HASH_VALUES)
    for block in blocks:
        W = message_schedule(block)
        a, b, c, d, e, f, g, h = H
        for i in range(64):
            T1 = (h + Sigma1(e) + Ch(e,f,g) + K[i] + W[i]) % MOD
            T2 = (Sigma0(a) + Maj(a,b,c)) % MOD
            h,g,f,e,d,c,b,a = g,f,e,(d+T1)%MOD,c,b,a,(T1+T2)%MOD
        H = [(x+y)%MOD for x,y in zip(H,[a,b,c,d,e,f,g,h])]
    return ''.join(f'{h:08x}' for h in H)

Практика

Откройте notebook 03-hashing.ipynb (раздел “Часть 2: SHA-256 с нуля”) и:

1. Реализуйте все вспомогательные функции (rotr, shr, ch, maj, sigma0, sigma1)
2. Реализуйте padding по спецификации
3. Реализуйте полный алгоритм SHA-256
4. Убедитесь, что ваша реализация совпадает с hashlib.sha256()
5. Проверьте на тестовых векторах NIST

Итоги

• SHA-256 состоит из 4 этапов: дополнение, расписание сообщений, 64 раунда сжатия, финализация
• Каждый раунд использует Ch, Maj, Sigma функции и раундовые константы K[]
• Начальные значения и константы выведены из простых чисел (проверяемые “nothing up my sleeve”)
• Все операции работают с 32-битными словами и арифметикой mod 2^32
• Полную реализацию на Python можно и нужно написать самостоятельно для глубокого понимания