SHA-256 представляет собой однонаправленную функцию для создания цифровых отпечатков фиксированной длины (256 бит, 32 байт) из входных данных размером до 2,31 эксабайт (2⁶⁴ бит) и является частным случаем алгоритма из семейства криптографических алгоритмов SHA-2 (Secure Hash Algorithm Version 2 ) опубликованным АНБ США в 2002 году.

Хеш-функции семейства SHA-2 построены на основе структуры Меркла - Дамгарда.

Исходное сообщение после дополнения разбивается на блоки, каждый блок - на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64 итерациями. На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Так как инициализация внутреннего состояния производится результатом обработки предыдущего блока, то нет возможности обрабатывать блоки параллельно. Графическое представление одной итерации обработки блока данных:

На текущий момент известны методы для конструирования коллизий до 31 итерации. Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней потенциальных уязвимостей принято решение, что SHA-3 будет базироваться на совершенно ином алгоритме. 2 октября 2012 года NIST утвердил в качестве SHA-3 алгоритм Keccak.

Алгоритм расчёта отпечатка в виде псевдокода:

Пояснения:
Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232
message - исходное двоичное сообщение
m - преобразованное сообщение Инициализация переменных
(первые 32 бита дробных частей квадратных корней первых восьми простых чисел [от 2 до 19]):
h0:= 0x6A09E667
h1:= 0xBB67AE85
h2:= 0x3C6EF372
h3:= 0xA54FF53A
h4:= 0x510E527F
h5:= 0x9B05688C
h6:= 0x1F83D9AB
h7:= 0x5BE0CD19 Таблица констант
(первые 32 бита дробных частей кубических корней первых 64 простых чисел [от 2 до 311]):
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 Предварительная обработка:
m:= message ǁ [единичный бит ]
m:= m ǁ , где k - наименьшее неотрицательное число, такое что
(L + 1 + K) mod 512 = 448, где L - число бит в сообщении (сравнима по модулю 512 c 448)
m:= m ǁ Длина (message) - длина исходного сообщения в битах в виде 64-битного числа с порядком байтов от старшего к младшему Далее сообщение обрабатывается последовательными порциями по 512 бит:
разбить сообщение на куски по 512 бит
для каждого куска разбить кусок на 16 слов длиной 32 бита (с порядком байтов от старшего к младшему внутри слова): w Сгенерировать дополнительные 48 слов:
для i от 16 до 63
s0:= (w rotr 7) xor (w rotr 18) xor (w shr 3)
s1:= (w rotr 17) xor (w rotr 19) xor (w shr 10)
w[i] := w + s0 + w + s1
Инициализация вспомогательных переменных:
a:= h0
b:= h1
c:= h2
d:= h3
e:= h4
f:= h5
g:= h6
h:= h7 Основной цикл:
для i от 0 до 63
Σ0:= (a rotr 2) xor (a rotr 13) xor (a rotr 22)
Ma:= (a and b) xor (a and c) xor (b and c)
t2:= Σ0 + Ma
Σ1:= (e rotr 6) xor (e rotr 11) xor (e rotr 25)
Ch:= (e and f) xor ((not e) and g)
t1:= h + Σ1 + Ch + k[i] + w[i] h:= g
g:= f
f:= e
e:= d + t1
d:= c
c:= b
b:= a
a:= t1 + t2 Добавить полученные значения к ранее вычисленному результату:
h0:= h0 + a
h1:= h1 + b
h2:= h2 + c
h3:= h3 + d
h4:= h4 + e
h5:= h5 + f
h6:= h6 + g
h7:= h7 + h Получить итоговое значения хеша:
digest = hash = h0 ǁ h1 ǁ h2 ǁ h3 ǁ h4 ǁ h5 ǁ h6 ǁ h7

Алгоритм используется:

• Bitcoin  - эмиссия криптовалюты через поиск отпечатков с определёнными рамками значений
• DNSSEC  - дайджесты DNSKEY
• DSA  - используется для создания электронной цифровой подписи
• IPSec  - в протоколах ESP и IKE
• OpenLDAP  - хеши паролей
• PGP  - используются для создания электронной цифровой подписи
• S/MIME  - дайджесты сообщений
• SHACAL-2  - блочный алгоритм шифрования
• X.509  - используются для создания электронной цифровой подписи сертификата

, "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.

Этот стандарт определяет следующие хэш-алгоритмы: SHA-1 , SHA-224 , SHA-256 , SHA-384 , SHA-512 , SHA-512/224 и SHA-512/256 , вычисляющие сжатое представление цифровых данных (сообщений). Если на вход хэш-алгоритма подать сообщение любой длины, но меньшее, чем 2 64 бит (для SHA-1 , SHA-224 и SHA-256 ) или меньше, чем 2 128 бита (для SHA-384 , SHA-512 , SHA-512/224 и SHA-512/256 ), то результатом будут данные, называемые дайджестом или хэш-значением сообщения . Размер хэш-значения сообщения лежит в диапазоне от 160 до 512 бит (или от 20 до 64 байт), зависит от выбранного алгоритма. SHA алгоритмы обычно используются совместно с другими криптографическими алгоритмами, например, с алгоритмами цифровой подписи или при хешировании с ключом для аутентификации сообщений (HMAC), или при создании случайных чисел (бит).

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

Каждый алгоритм состоит из двух этапов: предварительная обработка и вычисление хэша . Предварительная обработка включает в себя дополнение сообщения , разбиение дополненного сообщения на M -битные блоки , и установка инициализирующих значений , используемые при вычислении хэша. Вычисление хэша проходит итерационно, обрабатывая каждый M -битный блок дополненного сообщения, и использует функции, константы и операции над словами, чтобы получить хэш-значение. Результатом работы процедуры вычисление хэша является дайджест сообщения.

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

Алгоритм	Размер сообщения (в битах)	Размер блока (в битах)	Размер слова (в битах)	Размер дайджеста сообщения (в битах)
SHA-1	< 2 64	512	32	160
SHA-224	< 2 64	512	32	224
SHA-256	< 2 64	512	32	256
SHA-384	< 2 128	1024	64	384
SHA-512	< 2 128	1024	64	512
SHA-512/224	< 2 128	1024	64	224
SHA-512/256	< 2 128	1024	64	256

Функции

SHA-1 использует последовательность нелинейных функций f 0 , f 1 ,…, f 79 . Каждая функция f t , где 0 ≤ t < 79 , оперирует тремя 32-битными переменными: x , y , и z , в результате возвращая одно 32-битное слово. В алгоритме SHA-1 используется следующий набор нелинейных функций f t (x, y, z) :
00 ≤ t ≤ 19 Ch(x, y, z)
20 ≤ t ≤ 39 Parity(x, y, z) = x XOR y XOR z
40 ≤ t ≤ 59 Maj(x, y, 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)

n бит:
ROTR(x, n) = (x » n) | (x « (32-n))
SHR - сдвиг вправо на n бит:
SHR(x, n) = x » n

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)

Операции над словами (64-битными).
ROTR - циклический сдвиг вправо на n бит:
ROTR(x, n) = (x » n) | (x « (64-n))
SHR - сдвиг вправо на n бит:
SHR(x, n) = x » n

Константы

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

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

64 константы (32-битные слова): K 0 , K 1 … K 63 . (Для любознательных: эти константы представляют собой первые 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-битные слова): K 0 , K 1 … K 79 . (Для любознательных: эти константы представляют собой первые 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
]

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

1. Дополнение сообщения

Цель – сделать сообщение кратным 512 или 1024 бит, зависит от выбранного алгоритма SHA. Дополнение может быть выполнено перед процедурой вычисления хэша, или в ходе выполнения хэша, но до обработки блока(ов), который (ые) будут содержать дополнение.

M равна l «1» k - так, чтобы размер полученного сообщения был на 64 разряда меньше числа, кратного 512 (l+1+k = 448 mod 512 ). Далее, к полученному результату добавляется 64-битовое представление размера l исходного сообщения М «abc» «1» , затем 448 - (24 +1) = 423 бит «0» , и в конце 64-битовое представление размера 24 = 00…011000. В итоге получим 512-битовое сообщение вида:

Предположим, что длина сообщения M равна l бит. Сначала в конец сообщения добавляется «1» , а затем нули - в количестве k - так, чтобы размер полученного сообщения был на 128 разрядов меньше числа, кратного 896 (l+1+k = 896 mod 1024 ). Далее, к полученному результату добавляется 128-битовое представление размера l исходного сообщения М . Например, (ASCII текст) у нас есть сообщение «abc» , длиной 8 * 3 = 24 бита. Добавляем к сообщению «1» , затем 896 - (24 +1) = 871 бит «0» , и в конце 128-битовое представление размера 24 = 00…011000. В итоге получим 1024-битовое сообщение вида:

2. Разбиение дополненного сообщения на M -битные блоки.

N M -битных блоков.

Дополненное сообщение разбивается на N 512 -битовых блоков: M (1) , M (2) … M (N) . Т.к. 512 бит можно выразить как 16 (шестнадцать) 32-битных слов, то первые 32 бита i M 0 (i) , следующие 32 бита M 1 (i) , и так дойдем до M 15 (i) .

Дополненное сообщение разбивается на N 1024 -битовых блоков: M (1) , M (2) … M (N) . Т.к. 512 бит можно выразить как 16 (шестнадцать) 64-битных слов, то первые 64 бита i -го блока сообщения обозначим M 0 (i) , следующие 64 бита M 1 (i) , и так дойдем до M 15 (i) .

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

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

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

Восемь 32-битных слова.

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 = (

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

H0, H1, H2, H3, H4, H5, H6, H7 = (
0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b,
0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179)

Восемь 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 .

For i = 1 to N:
{
1. i
М 0 (i) по М 15 (i) )
в 80 слов размером 32 разряда (с W 0 по W 79 ):
W t = M t , для t = 0..15
W t = ROTL (W t-3 XOR W t-8 XOR W t-14 XOR W t-16 , 1) , для t = 16..79
(Интересно, что в первоначальном варианте спецификации SHA (алгоритм SHA-0) не было
циклического сдвига влево ROTL(x, 1) )

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) + f t (b,c,d) + e + W t + K t
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)
}

Результирующее хэш-значение – 160-битный дайджест сообщения:
H0 (N) || H1 (N) || H2 (N) || H3 (N) || H4 (N) (5 слов * 32 бита = 160 бит)

Операции над словами (32-битными).
ROTL - циклический сдвиг влево на n бит:
ROTL(x, n) = (x « n) | (x » (32-n))

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

For i = 1 to N:
{
1. i -й блок сообщения с помощью приведенного далее алгоритма
преобразуется из 16 слов размером в 32 разряда (с М 0 (i) по М 15 (i) )
в 64 слова размером 32 разряда (с W 0 по W 63 ):
W t = M t , для t = 0..15
W t = W t-16 + Delta0 (W t-15) + W i-7 + Delta1 (W t-2) , для t = 16..63

2.
a = H0 (i-1)
b = H1 (i-1)
c = H2 (i-1)
d = H3 (i-1)
e = H4 (i-1)
f = H5 (i-1)
g = H6 (i-1)
h = H7 (i-1)

3. Главный цикл функции сжатия
For t = 0 to 63
TEMP1 = h + Sigma1 (e) + Ch (e,f,g) + W t + K t
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)
}

Результирующее хэш-значение – 256-битный дайджест сообщения:
(8 слов * 32 бита = 256 бит)
Внимание: порядок байт в каждом слове "big-endian"

Алгоритм полностью совпадает с алгоритмом SHA-256. Отличие в инициализирующих значениях H (см. выше) и в том, как берется результирующий хэш. Т.к. мы получаем 256-битный дайджест сообщения, то мы берем только первые 224 бита, чтобы получить финальное хэш-значение:

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

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

For i = 1 to N:
{
1. i -й блок сообщения с помощью приведенного далее алгоритма
преобразуется из 16 слов размером в 64 разряда (с М 0 (i) по М 15 (i) )
в 80 слов размером 64 разряда (с W 0 по W 79 ):
W t = M t , для t = 0..15
W t = W t-16 + Delta0 (W t-15) + W i-7 + Delta1 (W t-2) , для t = 16..79

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

3. Главный цикл функции сжатия
For t = 0 to 79
TEMP1 = h + Sigma1 (e) + Ch (e,f,g) + W t + K t
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)
}

Результирующее хэш-значение – 512-битный дайджест сообщения:
H0 (N) || H1 (N) || H2 (N) || H3 (N) || H4 (N) || H5 (N) || H6 (N) || H7 (N) (8 слов * 64 бита = 512 бит)
Внимание: порядок байт в каждом слове "big-endian"

Алгоритм полностью совпадает с алгоритмом SHA-512. Отличие в инициализирующих значениях H (см. выше) и в том, как берется результирующий хэш. Т.к. мы получаем 512-битный дайджест сообщения, то мы берем только первые 384 бита, чтобы получить финальное хэш-значение:

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

Алгоритм полностью совпадает с алгоритмом SHA-512. Отличие в инициализирующих значениях H (см. выше) и в том, как берется результирующий хэш. Т.к. мы получаем 512-битный дайджест сообщения, то мы берем только первые 224 бита, чтобы получить финальное хэш-значение:

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

Алгоритм полностью совпадает с алгоритмом SHA-512. Отличие в инициализирующих значениях H (см. выше) и в том, как берется результирующий хэш. Т.к. мы получаем 512-битный дайджест сообщения, то мы берем только первые 256 бита, чтобы получить финальное хэш-значение:

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

Криптографические примитивы

Алгоритмы с открытым ключом	RSA DSA
Поточные шифры	RC4
Хэш-функции

С данной публикации мы начинаем цикл коротких статей, которые выйдут «в свет» в течение ближайших дней. Содержание этого цикла статей будет в основном посвящено различным типам алгоритмов шифрования. Мы дадим вам полное представление того, что представляют собой крипто-алгоритмы, что они означают, какие из цифровых монет первыми пришли к идее реализации данных алгоритмов и ответим на ряд других вопросов. Сегодня мы начнем с SHA-256, который, возможно, встречался большинству, если не всем вам, дорогие наши читатели.

Так что же это такое SHA-256? Как уже упоминалось ранее, это алгоритм. Если быть более точным, то это криптографическая хэш-функция, которая была разработана вашими и моими «друзьями» – Агентством национальной безопасности США. Подождите, не спешите впадать в прострацию, здесь не о чем волноваться. Потерпите немного, обещаю, что скучать вы точно не будете.

Основная работа этой хэш-функции заключается в превращении (или хэшировании) набора элементов данных в значение фиксированной длины. Это значение длины будет сравниваться с копиями исходных данных, без возможности извлечения этих исходных данных. Это официальное объяснение, выложенное в Википедии, замечательное и научно-обоснованное, но вот только я, например, не говорю на таком языке. И уверен, что большинство из вас тоже. А посему, позвольте мне объяснить значение этого «феномена», по-нашему, по-простому.

Как мы все знаем, при майнинге SHA-256 монет, мы решаем поставленную задачу при помощи процессора CPU или GPU. Процессы преобразования отображаются в интерфейсе программы, предназначенной для майнинга, например, в виде строки «Accepted 0aef41a3b». Значение 0aef41a3b — это и есть хэш. Он представляет собой кусок данных для раскодирования, которому соответствует полученный хэш-код. Если еще проще, то это короткая строка расшифрованных данных, тогда как основной кусок (или блок) данных состоит из нескольких тысяч, если не миллионов, подобных строк.

Это также объясняет то, почему вам обычно нужно решить множество задач, прежде чем удастся отыскать нужный блок вашей монеты. У вас имеется один шанс на тысячу, десять тысяч, сто тысяч или даже миллион решений того, что раскодированная строка будет иметь ТОЧНОЕ значение, необходимое для разблокировки, или это будут мои данные (или блока). Это похоже на игру в лотерею, но с машинами, которые могут выполнять вычисление выигрышной комбинации быстрее и лучше, чем любой из нас.

Вы считаете, что для решения задач, связанных с хэшированием при использовании протокола SHA-256, вам потребуется мощное аппаратное обеспечение? В этом есть определенный смысл. Чем больше используется вычислительной мощности, тем лучше, так как увеличиваются шансы на добычу монет. Но имейте в виду, что вы не единственный, кто занимается майнингом. Есть люди, которые располагают более производительным аппаратным обеспечением. Не расстраивайтесь, у вас есть все шансы на выигрыш. Это похоже на игру в лотерею, вы никогда не знаете, когда повезет!

Теперь вернемся к алгоритму SHA-256. Криптовалюта — это не единичный пример, где используется SHA-256. Есть несколько протоколов, о которых вы, скорее всего, слышали и которые работают по схожему алгоритму. Это протоколы SSL, SSH, PGP и многие другие. Каждый раз, когда вы заходите на защищенный веб-сайт с помощью сертификата SSL, используется SHA-256. Бьюсь об заклад, вы не задумывались об этом, не так ли? Все мы узнаем что-то новое со временем!

Итак, давайте поговорим о протоколе SHA-256! У вас наверняка есть биткоин, который является самой известной альтернативной валютой на сегодняшний день. Но это не повод останавливаться на достигнутом. В последнее время наблюдается всплеск новых SHA-256 монет: Zetacoin, Ocoin, Tekcoin и др. Но мы также не можем забывать про те монеты, которые были запущены ранее, например, NameCoin и т.д.

В следующей статье мы рассмотрим особенности работы алгоритма Scrypt!

Каждый, кто пробовал майнить и добывать цифровую валюту рано или поздно сталкивался с таким термином как SHA256. Что же обозначают этот акроним, какими особенностями обладает, как работает? Обо всем этом и многом другом поговорим подробнее.

SHA256.

Расшифровка SHA256 – сокращение от Secure Hashing Algorithm – это актуальный на сегодня алгоритм хеширования, созданный National Security Agency – Агентством национальной безопасности США. Задача данного алгоритма заключается в том, чтобы выполнить из случайного набора данных определённые значения с длиной, которая зафиксирована. Эта длина является идентификатором. Значение, которое получится, сравнивается с дубликатами изначальных данных, получить которые нет возможности.

Главная область, где используется алгоритм SHA256 – применение в разного рода приложениях или сервисах, что связаны с защитой информационных данных, где Secure Hashing Algorithm и распространилось. Также при помощи алгоритма выполняется майнинг цифровых валют.

SHA-256 – это криптографическая хэш-функция.

Как мы все знаем, при майне криптомонет, мы разрешаем исходную задачу, пользуясь процессорами CPU или GPU. Процессы отражены в интерфейсе программы для майна, к примеру, в виде строки «Accepted 0aef41a3b». 0aef41a3b и является хэш. Это информация для раскодировки, которой соответствует хэшированный код, который будет получен. Сказать иначе – это строчка расшифрованных данных, тогда как главный виртуальный блок данных включает в себя тысячи, а то и миллионы такого рода строчек.

Этим можно объяснить ситуацию, когда требуется разрешить огромное число задач, перед тем как получится найти необходимый блок вашей криптомонеты. Получается, присутствует единственный шанс на 1, 10, 100 тысяч или даже миллион решений того, что строка, которая расшифрована, будет иметь точное значение, требуемое для снятия блокировки, или это будут личные данные (или блока). Это словно розыгрыш, игра, но с оборудованием, которое может осуществлять вычисление комбинации выигрыша оперативнее и качественнее, чем любой майнер.

Многие думают, что для разрешения задач, что связаны с хэш при применении протокола SHA256, понадобится мощнейшее аппаратное обеспечение?

Да, это имеет место быть. Чем больше применяется вычислительной мощности, тем лучше, так как шансы на добычу криптовалюты (SHA256 miner) повышаются. Однако важно понимать, что монеты на SHA256 зарабатывает огромное количество майнеров. Есть те, у кого наиболее мощное аппаратное обеспечение. Но расстраиваться не следует, у каждого есть все шансы победить. Это словно лотерейный розыгрыш, невозможно предугадать, когда улыбнется фортуна! SHA256 майнинг – увлекательный и интересный процесс, позволяющий заработать виртуальные монеты.

Технический принцип работы алгоритма

Algorithm SHA256 сегодня реализован во всех действующих на рыночной платформе ASIC-майнерах, в то время как оборудование ASIC для других хэш-функций майнинга ещё только на стадии разработки.

Кроме Биткоин, майн путем алгоритма SHA256, используется во многих других виртуальных валют-клонах. Например, его применяют альткойны Пииркоин и Нэймкоин. Многим интересно при использовании SHA256, какие криптовалюты используются.

Наиболее актуальны следующие:

1. Ocoin.
2. Тekcoin.
3. Zetacoin и др.

Sha256 и Scrypt – это алгоритмы. Все, кто разбираются в добыче виртуальной волюты понимают, что для того, чтобы заработать какую-либо монету необходимо её майнить (то есть скачать программное обеспечение, запустить его и подождать пока компьютерное оборудование что-то заработает). Так вот вся суть майнинга заключается в том, что ПК решает сложнейшие задачи (хеш-функции) и чем больше проработает компьютерное оборудование, тем больше валюты будет добыто.

И задачи, которые разрешает ПК могут быть устроены не одинаково – одни базируются на алгоритме SHA256, а другие на Scrypt (разработаны и другие, но эти наиболее актуальные среди майнеров). К примеру, всем знакомый Биткоин зарабатывают по алгоритму Sha256, а криптовалюта DogeCoin добывается по Scrypt. Сказать иначе, разные цифровые валюты применяют различные алгоритмы. По какой причине?

А вот почему – Sha256 оказался не сложным и сегодня, появилось большое число спецустройств (они именуются ASIC), которые разрешают задачи на этом алгоритме очень оперативно, быстрее стандартных мощных процессоров, так эти ASIC приносят майнерам в разы больше криптовалюты, чем обычное компьютерное оборудование. Ниже представлено видео, на котором можно понять каким является технический принцип работы алгоритма.

Особенности протокола SHA-256

SHA256 имеет некие преимущества перед другими алгоритмами. Это наиболее востребованный алгоритм майна среди всех существующих. Он показал себя как надежный к взламыванию (случается не часто) и результативный алгоритм как для задач майна, так и для прочих целей.

Имеются и недостатки:

1. Главным минусом SHA256 валюты является контролирование майнерами.
2. Те, у кого имеются огромные вычислительные мощности, получают основную часть крипто, что исключает один из основных принципов виртуальных денег – децентрализованность.
3. Как только пошли инвестиции в вычислительные мощности для промышленного майна Биткоина, сложность добычи значительно возросла и стала требовать исключительных вычислительных мощностей. Этот минус исправлен в прочих протоколах, наиболее инновационных и «заточенных» под применение в майне цифровых валют, таких как Скрипт.

Несмотря на то, что в наши дни SHA256 занимает рыночную основу крипто, он будет ослаблять своё влияние в пользу наиболее надежных и современных протоколов. Пулы SHA256 сдадут позиции. Так алгоритмы SHA–1 перестали давать требуемый уровень защиты из–за вероятного развития коллизий.

Криптовалюты SHA256, как и SHA512 наиболее защищены от данного отрицательного момента, но вероятность развития риска все-таки есть. Miner на SHA256, как и на любом ином хешировании – это процесс разрешения какой-то сложнейшей криптографической задачи, которую генерирует программа для майна на основе информации полученной с блоков.

Майнинг при помощи хэш-функции SHA256 можно осуществлять 3 методами:

1. ASIC.

В майне хеш–сумма применяется как идентификатор уже присутствующих блоков, и создания новых на основе тех, что имеются. Процесс майна отражен в интерфейсе в виде «accepted f33ae3bc9…». Где f33ae3bc9 – это хешированная сумма, часть данных, которая требуется для дешифровывания. Главный блок включает в себя огромное число такого рода хеш-сумм. То есть, добыча с алгоритмом SHA256 – это подбор правильного значения хешированной суммы без остановки, перебор чисел для того, чтобы создать очередной блок. Чем мощнее оборудование, тем больше шансов стать владельцем того самого правильного блока: скорость перебирания разного рода сумм зависит от мощностей. Потому как Биткоин построен на алгоритме SHA256, для конкурентоспособного майна на нём требуются крайне большие вычислительные мощности.

Это связывается с тем, что для добычи криптовалюты хватает производства «асиков», а именно специальной схемы особенного назначения. Асики дают возможность добывать Биткоины и прочие криптовалюты на хэш-функции SHA–256 оперативнее, результативнее и недорого.

Какие еще криптовалюты SHA–256 можно добывать? SHA–256 это классика для цифровых валют: на нем выстроена основная виртуальная валюта – Bitcoin. Именно поэтому, и в форках биткоинаприменяется этот хеш: в Биткоин каш, Голд, Диамонд.

Кроме них, SHA–256 применяется также в:

1. Стимит.
2. Дигибайт.
3. Пиркоин.
4. Нэймкоин.
5. Тиккоин.
6. Окоин.
7. Зетакоин.
8. Эмиркоин.

Также алгоритм применяется как подпрограмма в цифровой валюте Лайткоин, а главным алгоритмом для майна там будет Scrypt.

Псевдокод хеш: функции

Отличается Scypt-Jane тем, что поддерживает более 3-х различных систем поточного шифра. И для того чтобы сформировать отчетливое понимание алгоритма, следует ознакомиться с характеристикой функционала. Основные функции:

1. ChaCha20.
2. Salsa6420/8.

Первостепенно мы имеем Salsa20/8. Это довольно несложная функция, основной задачей функционирования которой является приём 192-байтной строчки (из цифр и букв) и последующее её преобразование в 64-байтную строчку Salsa20 (х).

Salsa20 двухкомпонентная: потоковое шифрование для шифра данных и функция сжатия (алгоритм Румба20), которая нужна для сжатия 192-байтной строчки до 64-байтной. Сказать иначе: строчка может быть больше 64-байтной, пока не станет равна 192-байтной, при этом строчка будет сжиматься до 64 байтов. ChaCha20 имеет небольшие сходства с Сальса20: это также поточное шифрование, но оно предусматривает некоторые дополнительные возможности, например, повышение стойкости к криптоанализ.

Чача20 также повышает перемешивание данных на раунд. Говоря другими словами, занимаясь майном цифровых монет в составе пула, можно заметить, что один майнерский раунд может включать в себя либо короткий, либо длинный временной период. Длительность периода времени, на протяжении которого майнерский пул может отыскать один блок, отчасти определяется и более качественным перемешиванием, предлагаемым Чача20 из Скрпит-Джейн.

К слову, на понижение времени раунда оказывают влияние различные факторы. Еще одна важнейшая функция перемешивания информации в Скрипт-Джейн – это Salsa6420/8. Она усовершенствованная версия Salsa20/8, и дает возможность работать с наиболее высокобайтными блоками. Кроме этих функций, Скрипт Джейн поддерживает также ряд хешированных, среди которых присутствует и SHA256. Алгоритмом также поддерживается наиболее инновационный её вариант SHA512.

Пример хеширования

Что же такое хеширование? Идея хеш основана на распределении ключей в стандартном массиве H. Распределение происходит путем вычисления для каждого ключа элемента некой хешированно функции h. Она на основе ключа помогает получить целое число n, которое послужит индексом для массива H. Понятное дело, следует придумать такую хешированную функцию, которая бы давала разный код для разнообразных объектов. К примеру, если в качестве ключа хешированной таблицы следует применить строки, то можно подобрать хешированную функцию, которая основана на таком алгоритме (пример на С): int hash(char* str) {int h = 0; for (int i=0; i

Где m – размер хешированной таблицы, C – константна, большая любого ord(c), а ord() – функция, которая возвращает код символа (число). Для отдельного типа данных можно создать свою хешированную функцию. Но разработаны основные требования к функции: она должна расставлять ключи по ячейкам хешированной таблицы как наиболее равномерно, и должна легко находиться. Ниже предложена таблица. Можно понять, что индексами ключей в хешированной таблице является результат функции h, которая применена к ключу.

Также изображение показывает одну из главных проблем. При довольно низком значении m (размера хешированной таблицы) по отношению к n (числу ключей) или при плохой функции, может произойти так, что 2 ключа будут хешированные в общую ячейку массива H. Это коллизия.

Хорошие функции стремятся свести к нулю шанс формирования коллизий, но, принимая во внимание то, что пространство всех ключей, которые возможны, может быть больше размера хешированной таблицы H, всё-таки избежать их не получится. Но специалистами разработано ряд технологий для разрешения коллизий. Настройка pool SHA256 для добычи монет отображена на видео. Можно понять, как майнить криптовалюту.

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

Как работает алгоритм SHA-256?

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

Если быть точным, то SHA-256 не столько алгоритм, сколько криптографическая хеш-функция, разработанная АНБ США (Агентство национальной безопасности). Главной ее задачей является превращение произвольного набора данных в значения, имеющие фиксированную длину. То есть, если у вас имеется какой-либо массив данных, состоящий из десятков, сотен или тысячи элементов, он может быть приведен к какому-либо общему виду конкретного размера.

Особенность конечного значения заключается в том, что оно может сравниваться с исходным массивом, но не может быть преобразовано в свою изначальную форму.

Какое отношение алгоритм SHA-256 имеет к майнингу?

Осуществляя майнинг монет на графических картах или процессорах, в консоли мы видим сообщения следующего формата: «Accepted 0aef41a3b». 0aef41a3b и является тем хешем, который ищут все майнеры, то есть сокращенной копией какого-то большого массива данных. Эти несколько символом по существу представляют собой блок, состоящий из сотен, тысяч и миллионов подобных строк.

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

Кроме того, сложность добычи подкрепляется и естественной конкуренцией. Те, кто имеют более мощные компьютеры или майнеры, быстрее перебирают варианты, находя хеш. Поэтому надеется на то, что сегодня вы сможете «разгадать» хоть 1 хеш, используя центральный процессор, попросту глупо. Вероятность такого события составляет 1 к нескольким миллионам или даже десяткам миллионов.

Какие монеты используют алгоритм SHA-256 ?

На сегодняшний день, помимо биткоина, на SHA-256 работают и другие криптовалюты, например:

• ZetaCoin.
• NameCoin.
• PeerCoin.
• EmerCoin.

Несмотря на некоторые свои недостатки в контексте криптовалютного сегмента, монеты, основанные на алгоритме SHA-256, продолжают удерживать свои позиции. Чего стоит только биткоин, который сегодня продается по цене около 7,5 тыс. долларов за монету, а также занимает первое место в рейтинге по капитализации.