Инструменты разработчика · SHA хеш-калькулятор
SHA-256 Шаг за шагом: заполнение, расписание сообщений и 64 раунды
· Как это работает
ша-256 криптография API-интерфейс браузера javascript
SHA-256 дополняет ваш ввод, разбивает его на 512-битные блоки и пропускает каждый из 64 раундов микширования. В этом посте каждый этап объясняется простым языком, не требуя знаний в области криптографии.
Что на самом деле происходит с вашими байтами — черный ящик, который большинство разработчиков никогда не открывает
SHA-256 — это детерминированный алгоритм, который преобразует любые входные данные в 256-битный (32-байт) отпечаток пальца. То, что снаружи выглядит как черный ящик, на самом деле представляет собой последовательность четко определенных шагов. Понимание этих шагов устраняет тайну и позволяет вам проверять правильность, отслеживать ошибки и понимать, почему выходные данные такие, какие они есть. Каждая часть алгоритма является общедоступной; сила исходит из замысла, а не из секретности.
Алгоритм работает с 512-битными блоками. Если ваш ввод короче, он дополняется. Если он длиннее, он разбивается на несколько блоков, каждый из которых обрабатывается последовательно, причем выходные данные каждого блока передаются в следующий. После обработки всех блоков у вас есть восемь 32-битных чисел, которые, объединенные вместе, образуют окончательный 256-битный дайджест.
Заполнение — добавление 1 bit, нулей и длины сообщения 64 для достижения кратности 512 bits.
Шаг заполнения является детерминированным и формализованным. После фактического ввода добавьте один 1 bit (на практике это байт 0x80, если ваш ввод заканчивается на границе байта). Затем добавляйте нулевые биты до тех пор, пока вам не будет не хватать 64 bits кратного 512 bits. Наконец, добавьте 64-битную кодировку с прямым порядком байтов входной длины в битах. Это дополнение гарантирует, что каждое сообщение кратно 512 bits, и кодирует исходную длину, поэтому идентичные входные данные разной длины не могут создать один и тот же дайджест.
Для ввода abc (3 bytes = 24 bits) дополненное сообщение имеет вид 512 bits (один блок): три байта 61 62 63, за которыми следует 0x80, за которыми следуют нули, а затем 64-битная кодировка. из 24 (что равно 0x00...0x18 в 64-битном поле с прямым порядком байтов). Теперь сообщение заполняет ровно один 512-битный блок. Для пустой строки к заполнению добавляется 0x80, за которым следуют нули, а затем 0x00...0x00 (что указывает на 0 bits ввода). Для более длинных входных данных, таких как файл размером 100 байт, заполнение заполнит последний блок до 512 bits и укажет 800 bits исходной длины.
Начальные значения и константы фиксируются алгоритмом; их историческое происхождение находится за пределами хранилища
Алгоритм начинается с восьми 32-битных рабочих переменных, инициализированных первыми 32 bits дробных частей квадратных корней первых восьми простых чисел. Это жестко закодированные константы, видимые в любой эталонной реализации и в исходном коде криптографических библиотек. Они существуют потому, что использование фиксированных математических констант позволяет избежать подозрений в скрытом бэкдоре. Инструмент ToolAcre использует реализацию Web Crypto браузера, которая применяет те же константы.
Алгоритм также использует круглые константы 64, полученные из первых 32 bits дробных частей кубических корней первых 64 простых чисел. Они также являются фиксированными и общедоступными. Константы служат дополнительным материалом для смешивания; их изменение нарушит алгоритм и приведет к появлению других дайджестов.
Расписание сообщений — расширение слов 16 в 64 с помощью сдвигов и ротаций.
Расписание сообщений расширяет 16 слов (512 bits) до 64 слов (2048 bits) с помощью специальной формулы. Для раундов 0-15 слова поступают непосредственно из входного блока. В раундах 16-63 каждое новое слово вычисляется путем взятия двух предыдущих слов (с определенными смещениями), применения поворота и сдвига, операции XOR в другом слове и сохранения результата. Формула является детерминированной и обратимой в контексте одного блока, но расширение распределяет влияние входных данных на все раунды 64.
В формуле расширения используются операции поворота вправо (круговой битовый сдвиг, при котором биты, выпавшие с одного конца, снова появляются на другом) и сдвиг вправо. Вращение сохраняет все биты, но меняет их позиции; сдвиг вправо отбрасывает биты. Сочетание вращений, сдвигов и операций XOR гарантирует, что каждый бит входных данных влияет на несколько слов в расписании.
Один раунд — функции Ch, Maj и Sigma, описанные как операции смешивания битов, и как обновляются восемь рабочих переменных.
Каждый из раундов 64 обрабатывает одно слово расписания сообщений и обновляет восемь рабочих переменных. Основная функция включает в себя шесть операций: условное смешивание (часто называемое Ch, что означает «выбрать»), которое выбирает биты на основе управляющей переменной, функцию большинства (Maj), которая выбирает наиболее распространенное значение среди трех переменных, две специальные функции смешивания (Sigma_0 и Sigma_1), которые вращают и сдвигают рабочие переменные, и сложение по модулю 2^32. Вся арифметика выполняется над 32-битными словами, поэтому переполнение происходит.
Функция «выбрать» принимает три входных бита 32 и для каждой позиции бита выбирает бит из первого входа, если бит управления равен 1, или бит из второго входа, если бит управления равен 0. Функция большинства просматривает три входа и для каждой позиции бита выводит значение бита, которое встречается чаще всего среди этих трех. Это нелинейные операции, которые нарушают линейность и гарантируют, что крошечные входные изменения непредсказуемо распространяются по состоянию.
Объединение блоков в цепочку и создание выходных данных — добавление результата каждого блока в рабочее состояние.
Каждый раунд обновляет все восемь рабочих переменных, вращая их и добавляя новое значение, вычисленное на основе текущей константы раунда, слова расписания сообщений и предыдущего состояния. Первые семь рабочих переменных меняются: 8-я становится 1-й, 1-я становится 2-й и так далее. Новая восьмая вычисляется из старых переменных с использованием функций смешивания. После 64 раундов у вас есть восемь новых 32-битных значений. Они добавляются (по модулю 2^32) к исходным константам, создавая окончательное хэш-состояние для этого блока.
Для многоблочного сообщения восемь значений из одного блока становятся исходным состоянием для следующего блока. Цепочка гарантирует, что изменение в любом месте входных данных повлияет на все последующие блоки. К тому времени, как вы доберетесь до последнего блока, каждый бит входных данных повлияет на конечный результат.
Проработанный пример и то, что он не охватывает — отслеживание заполнения и количества блоков для короткого сообщения; доказательства безопасности выходят за рамки
Для ввода abc сообщение помещается в один 512-битный блок после заполнения. Заполнение добавляет 424 bits, в результате чего общая сумма составляет 512 bits. Расписание сообщений расширяет это значение до 64 слов. Каждый раунд потребляет одно слово и обновляет восемь рабочих переменных с помощью функций смешивания. После раундов 64 состояние подвергается операции XOR с начальными константами, в результате чего получается окончательный дайджест ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad.
Это опубликованный тестовый вектор: одни и те же вычисления на одних и тех же входных данных всегда дают один и тот же результат. Инструмент ToolAcre выполняет именно эти вычисления с помощью реализации Web Crypto в браузере. Вы можете проверить это, хэшировав abc и сравнив результат с известным вектором. Любой браузер, который правильно реализует Web Crypto, выдаст тот же результат; алгоритм не допускает сокращений или альтернативных путей.
Вывод: Web Crypto выполняет детерминированное смешивание SHA-256 без раскрытия секрета.
Алгоритм является общедоступным, и каждый шаг детерминирован. Функции смешивания (Ch, Maj, Sigma_0, Sigma_1) были выбраны нелинейными, что означает, что изменение одного входного бита не приводит к предсказуемому изменению одного выходного бита. Расширение слов сообщения 16 до 64 гарантирует, что весь ввод влияет на все вычисления. Раунды 64 и цепочка состояний означают, что выходные данные чувствительны к каждому биту входных данных, и репозиторий использует полученные выходные данные в качестве детерминированного дайджеста. Устойчивость к коллизиям — это свойство безопасности с ограничениями, а не обещание того, что дублирование выходных данных математически невозможно.
Криптографические доказательства выходят за рамки этой статьи. Ключевой момент заключается в том, что теперь вы знаете, что на самом деле делает алгоритм. Это не волшебство и не черный ящик. Если вы хотите убедиться, что ToolAcre хэшируется правильно, проследите свои собственные входные данные с помощью этих шагов или используйте эталонную реализацию на другом языке и сравните результаты. Реализация браузера и любая правильная ссылка будут создавать идентичные дайджесты для идентичных входных данных.