Алгоритм sha 256

План перехода ИОК с SHA-1 на SHA-2

Каждая компания с внутренним ИОК, не использующая SHA-2, должна будет создать ИОК SHA-2 или перевести существующую ИОК с SHA-1 на SHA-2. Для перехода нужно:

• Обучить вовлечённых членов команды тому, что такое SHA-2 и почему требуется его использование (эта статья будет хорошим началом).
• Провести инвентаризацию всех критических хешей или цифровых сертификатов, используемых в приложениях или устройствах.
• Определить, какие критически важные устройства или приложения могут использовать SHA-2, какой размер ключа может быть использован и какие операционные проблемы могут возникнуть (этот этап зачастую включает обращение к поставщику и тестирование).
• Определить, какие компоненты ИОК могут или должны быть перенесены в SHA-2.
• Составить план перехода для преобразования компонентов SHA-1 в SHA-2, включая потребителей и компоненты ИОК, плюс резервный план на случай сбоя.
• Провести PoC-тестирование.
• Принять управленческий риск и решение о переходе или отказе от него.
• Внедрить план перехода в производственную среду.
• Провести тестирование и получить обратную связь.

Самая сложная часть перехода — определение того, какие устройства и приложения работают с SHA-2. Если используемые устройства не понимают SHA-2, вас ждёт неудача или сообщение об ошибке, которое вряд ли будет звучать как «SHA-2 не принят». Вместо этого готовьтесь к: «Сертификат не распознан», «Соединение нестабильно», «Соединение не может быть установлено», «Повреждённый сертификат» или «Непроверенный сертификат».

Подумайте о своей миссии, чтобы определить, какие важные части вашей инфраструктуры будут или не будут работать. Начните с попытки инвентаризации каждого уникального устройства, ОС и приложения, которые должны понимать SHA-2. Затем соберите команду людей, которые протестируют, работает ли SHA-2. Можно предварительно полагаться на информацию от поставщиков, но вы не будете знать наверняка пока не проверите самостоятельно.

Обновление приложений и устройств — задача не из лёгких, и потребует больше времени, чем кажется. Даже сейчас существует множество устройств и приложений, использующих старые версии OpenSSL, которые следовало бы обновить после атаки Heartbleed, но администраторы серверов этого так и не сделали.

Если у вас есть внутренняя ИОК, вам понадобится подготовить её к переходу на SHA-2. Иногда это означает обновление ваших центров сертификации, получение новых сертификатов или установку полностью новых ИОК. Последнее рекомендуется по множеству причин, в основном потому, что новая ИОК даст вам шанс начать сначала без груза старых ошибок.

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

SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока Mi{\displaystyle M_{i}} равен hi=f(Mi,hi−1){\displaystyle h_i = f(M_i, h_{i-1})}. Хеш-значением всего сообщения является выход последнего блока.

Инициализация

Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 а потом нули, чтобы длина блока стала равной (512 — 64 = 448) бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах. Если последний блок имеет длину более 448, но менее 512 бит, дополнение выполняется следующим образом: сначала добавляется 1, затем нули вплоть до конца 512-битного блока; после этого создается ещё один 512-битный блок, который заполняется вплоть до 448 бит нулями, после чего в оставшиеся 64 бита записывается длина исходного сообщения в битах. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину.

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

A = a = 0x67452301
B = b = 0xEFCDAB89
C = c = 0x98BADCFE
D = d = 0x10325476
E = e = 0xC3D2E1F0

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

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов Mi{\displaystyle M_{i}} в 80 32-битовых слов Wj{\displaystyle W_j} по следующему правилу:

Wt=Mt{\displaystyle W_t  =  M_t }                                      при 0≤t≤15Wt{\displaystyle W_t} = (Wt{\displaystyle W_t}-3⊕{\displaystyle \oplus } Wt{\displaystyle W_t}-8⊕{\displaystyle \oplus } Wt{\displaystyle W_t}-14⊕{\displaystyle \oplus } Wt{\displaystyle W_t}-16) << 1     при 16≤t≤79

здесь << — это циклический сдвиг влево

для t{\displaystyle t} от 0 до 79 temp = (a<<5) + Ft{\displaystyle F_t}(b,c,d) + e + Wt+Kt{\displaystyle W_t + K_t }   
	e = d 
	d = c 
	c = b<<30
	b = a 
	a = temp 

После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая итерация.
Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение.

Псевдокод SHA-1

Псевдокод алгоритма SHA-1 следующий:

Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
     h0 := 0x6A09E667h0 = 0x67452301
     h1 = 0xEFCDAB89
     h2 = 0x98BADCFE
     h3 = 0x10325476
     h4 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
Присоединяем k битов '0', где k наименьшее число ≥ 0 такое, что длина получившегося сообщения (в битах) сравнима по модулю  
    512 с 448 (length mod 512 == 448)
Добавляем длину исходного сообщения (до предварительной обработки) как целое 64-битное Big-endian число, в битах.

В процессе сообщение разбивается последовательно по 512 бит:
for перебираем все такие части
    разбиваем этот кусок на 16 частей, слов по 32-бита w, 0 <= i <= 15

    16 слов по 32-бита дополняются до 80 32-битовых слов:
    for i from 16 to 79
        w = (w xor w xor w xor w) циклический сдвиг 1 

    Инициализация хеш-значений этой части:
        a = h0
        b = h1
        c = h2
        d = h3
        e = h4 

    Основной цикл:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp 

    Добавляем хеш-значение этой части к результату:
        h0 = h0 + a
        h1 = h1 + b 
        h2 = h2 + c
        h3 = h3 + d
        h4 = h4 + e 

Итоговое хеш-значение:
digest = hash = h0 append h1 append h2 append h3 append h4 

Вместо оригинальной формулировки FIPS PUB 180-1 приведены следующие эквивалентные выражения и могут быть использованы на компьютере f в главном цикле: 
(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (альтернатива 1)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (альтернатива 2)
(0  ≤ i ≤ 19): f = (b and c) + ((not b) and d)            (альтернатива 3)
 
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (альтернатива 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (альтернатива 2)
(40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c))          (альтернатива 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (альтернатива 4)

Практическое применение и сертификация технологии

Законодательством Соединенных Штатов Америки разрешается использование SHA-256 и прочих аналогичных методов хеширования в определенных государственных программах для защиты сведений. Кроме того, допускается применение алгоритма коммерческими компаниями.

Как это сказывается на специализированных устройствах для добычи криптовалюты? Каждый шаг в этом алгоритме имеет довольно простой вид — примитивная битовая операция и 32-битное сложение (любой, кто знаком с основами схемотехники, сможет без труда представить, как подобное выглядит в железе). А потому для эффективной работы асик-майнеров нужно лишь располагать десятком блоков выполнения этапов алгоритма.

В противовес Bitcoin, Лайткоин, Догикоин и прочие схожие «коины» используют протокол шифрования Scrypt, который оснащен функцией повышения сложности. Данный алгоритм в ходе деятельности сохраняет 1024 различных значения хеш-функций, а уже на выходе соединяет их и получает преобразованный результат. Благодаря этому для реализации протокола нужны несравнимо большие вычислительные мощности.

Методы