JH | это... Что такое JH? (original) (raw)

Криптографическая хеш-функция
Название	JH
Разработчик	У Хунцзюнь (англ Wu Hongjun)
Опубликован	16 января 2011 года
Размер хеша	224, 256, 384, 512
Число раундов	42

JH - семейство из четырех криптографических хеш-функций: JH-224, JH-256, JH-384 и JH-512.

Алгоритмы этих хеш-функций отличаются только значением одного внутреннего параметра - длины(в битах) $l_{hash}~$ выходного значения(которая и указана после черточки в названии). Далее в статье при описании алгоритма я буду считать этот параметр частью входных данных для удобства, говоря о JH, как об одном алгоритме или одной хеш-функции.

Хэш-функция JH входит в пятерку финалистов второго тура SHA-3. В процессе этого конкурса она была улучшена. В статье я описываю самую последнюю на данный момент версию, которую также можно назвать JH42 (так как главное изменение состояло в том, что число раундов в функции компрессии стало равно 42). Дата выхода документации по ней - 16 января 2011 года.

При хэшировании входное сообщение дополняется и разделяется на части, которые далее последовательно обрабатываются так называемой функцией компрессии. Эта функция описана в спецификации в общем виде - то есть с переменным параметром d, меняя который можно конструировать JH-подобные хэш-функции(тем более криптостойкие, чем больше d). В JH исходно d=8.

При выборе финалиста в конкурсе SHA решающую роль играют не криптографические характеристики(они у всех функций отличные), а гибкость и оптимальность в программной и аппаратной реализации. На тему аппаратной реализации существует много исследований, например,[1].

Алгоритм[2]

Уточнения

О названии элементов битовых векторов

Будем считать, что у всех обсуждаемых тут битовых векторов есть начало и конец, причем бит, расположенный в начале(слева) является первым, имеет позицию 0 и считается наиболее значимым, соответственно, бит, расположенный в конце(справа), является последним, имеет позицию с наибольшим номером, на один меньшим, чем число разрядов вектора, и считается наименее значимым.

То же самое, за исключением номера позиции, будем подразумевать для векторов, состоящих из битовых векторов, например, для сообщения, состоящего из блоков, или блока, состоящего из полубайтов. С номером же позиции какой-либо составной части битового вектора, состоящей из нескольких бит, будет путаница, создаваемая для удобства. Так, номера позиций полубайтов в блоке будут начинаться с нуля, а номера позиций блоков в сообщении - с единицы...

Пример

В векторе

8afd4h

первый, наиболее значимый полубайт расположен слева – это 8; последний, наименее значимый полубайт расположен справа – это 4.

Если эту запись рассматривать, как битовый вектор, а не как полубайтовый, то она эквивалентна такой:

1000_1010_1111_1101_0100,

тут первый(с номером 0, левый, старший) бит - 1, а последний(с номером 19, правый, младший) - 0.

Обозначение конкатенации

Пусть вектор состоит из последовательно идущих векторов $A_1, A_2, \dots, A_N$ , тогда этот факт будет обозначаться так: $A=A_1||A_2|| \dots ||A_N$

Используемые функции - обобщенный случай

Здесь описаны функции, с помощью которых можно строить JH-подобные алгоритмы, меняя параметр

S-box -

Это функция, преобразующая s-блок (то есть размеры её входного и выходного значений одинаковы и равны 4 битам). В алгоритме используются 2 таких функции: S_1~ и S_0~ . Их таблицы значений такие:

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
	9	0	4	b	d	c	3	f	1	a	2	6	7	5	8	e
	3	c	6	d	5	7	1	9	f	2	0	4	b	a	e	8

Линейное преобразование пар ячеек -

Эта функция преобразует пару s-блоков (то есть размеры её входного и выходного значений одинаковы и равны 8 битам). Наиболее лаконичную запись она имеет в терминах конечных полей многочленов.

Рассмотрим конечное поле многочленов над GF(2)~ степени не выше 3-ей. Оно изоморфно полю GF(2^4)~ ; установим стандартное для таких случаев соответствие межу полем многочленов и полем чисел: многочлен будет соответствовать числу, равному значению многочлена при x=2~ . Выберем для этого поля многочленов следующий примитивный многочлен:

x^4+x+1~ .

Тогда если рассматривать L(A,B)~ , как функцию, преобразующую 2 многочлена, а числа и буквы - как многочлены, то

$L(A,B) = ((5 \bullet A + 2 \bullet B) , (2 \bullet A + B))~$ ,

где " $\bullet ~$ " и "" - операции умножения и сложения в данном поле многочленов.

Перемешивание -

Функция P_d~ является композицией трех более простых перемешиваний, преобразующих массив из 2^d~ битовых векторов(то есть размеры их входных и выходных значений одинаковы и равны $2^d\times k~$ битам, где - число бит в одном элементе этого массива):

$P_d(A)=\phi_d(P'_d(\pi_d(A)))~$

Приведем алгоритмы этих перемешиваний, обозначив за $A=A_0||A_1||\dots||A_{2^d-1}~$ и $B=B_0||B_1||\dots||B_{2^d-1}~$ (где A_i~ и B_i~ - битовые векторы одинакового размера для всех ) - входной и выходной векторы соответственно:

$B=\pi_d(A)~$ :

$for~ i=0 ~~to~ 2^{d-2}-1 ~~begin~$

$B_{4i+0}=A_{4i+0}~$

$B_{4i+1}=A_{4i+1}~$

$B_{4i+2}=A_{4i+3}~$

$B_{4i+3}=A_{4i+2}~$

end~

$for~ i=0 ~~to~ 2^{d-1}-1 ~~begin~$

$B_i=A_{2i}~$

$B_{i+2^{d-1}}=A_{2i+1}~$

end~

$B=\phi_d(A)~$ :

$for~ i=0 ~~to~ 2^{d-2}-1 ~~begin~$

$B_{2i}=A_{2i}~$

$B_{2i+1}=A_{2i+1}~$

$B_{2^{d-1}+2i}=A_{2^{d-1}+2i+1}~$

$B_{2^{d-1}+2i+1}=A_{2^{d-1}+2i}~$

end~

Преобразование-раунд -

На вход подается $2^{d+2}~$ - мерный вектор . Выход - $2^{d+2}~$ - мерный вектор. Так же на вход подается 2^d~ -битная константа .

Вектор представляется в виде массива из 2^d~ полубайт: $A=A_0||A_1||\dots||A_{2^d-1}~$ .

Потом над каждым полубайтом A_i~ производится преобразование S_0~ или S_1~ в зависимости от значения C_i~ (если C_i=0~ , то S_0~ , иначе - S_1~ )

Далее над каждой парой вида $(S_{C_{2i}}(A_{2i}),S_{C_{2i+1}}(A_{2i+1}))~$ производится линейное преобразование $L(S_{C_{2i}}(A_{2i}),S_{C_{2i+1}}(A_{2i+1}))~$ .

И в конце концов результаты опять группируются в вектор, биты которого подвергаются перемешиванию P_d~ .

Это выражается в виде формулы:

$R_d(A,C)=P_d\bigg(L\Big(S_{C_0}(A_0),S_{C_1}(A_1)\Big)||L\Big(S_{C_2}(A_2),S_{C_3}(A_3)\Big)||\dots||L\Big(S_{C_{2^d-2}}(A_{2^d-2}),S_{C_{2^d-1}}(A_{2^d-1})\Big)\bigg)~$

Преобразование

На входе $2^{d+2}~$ - мерный вектор . Сначала происходит начальная группировка:

$for~ i=0 ~~to~ 2^{d-1}-1 ~~begin~$

$B_{8i+0}=A_{i+128\times 0}~$

$B_{8i+1}=A_{i+128\times 2}~$

$B_{8i+2}=A_{i+128\times 4}~$

$B_{8i+3}=A_{i+128\times 6}~$

$B_{8i+4}=A_{i+128\times 1}~$

$B_{8i+5}=A_{i+128\times 3}~$

$B_{8i+6}=A_{i+128\times 5}~$

$B_{8i+7}=A_{i+128\times 7}~$

end~

Далее к результату этой группировки применяется $6\times(d-1)$ преобразований-раундов R_d(B,C)~ с константами, изменяющимися от раунда к раунду. Начальное значение переменной задается, как целая часть числа $(\sqrt{2}-1)\times 2^{2^d}~$ , то есть

$C=\left \lfloor (\sqrt{2}-1) \times 2^{2^d} \right \rfloor~$ :

$for~ i=1 ~~to~ 6\times(d-1) ~~begin~$

$C=R_{d-2}(C,0)~$

B=R_d(B,C)~

end~

Далее происходит конечная разгруппировка, обратная начальной:

$B_{fin}=G^{-1}_d(B)~$ ,

Где $G^{-1}_d: G_d(G^{-1}_d(B)) \equiv B~$

Таким образом

$E_d(A)=G^{-1}(R_d(R_d(R_d(\dots(R_d(G_d(A)),C_1)\dots),C_{6(d-1)-1}),C_{6(d-1)}))~$

$C_i=R_{d-2}(C_{i-1},0),~ i=1\dots 6(d-1), ~C_0=\left \lfloor (\sqrt{2}-1)\times 2^{2^d} \right \rfloor~$

Функция свертки

На входе $2^{d+2}~$ -битный вектор и $2^{d+1}~$ -битный вектор . Сначала преобразуется путем побитового сложения первой половины этого вектора с , потом над результатом выполняется преобразование E_d~ и наконец результат преобразуется путем побитового сложения его второй половины с вектором .

Запишем это в виде формул. Пусть $H_{left}~$ - первая(старшая) половина вектора , а $H_{right}~$ - вторая. Пусть также функции $E_{d-left}(A)~$ и $E_{d-right}(A)~$ возвращают левую и правую половины E_d(A)~ соответственно. Тогда

$F_d(H,M)=E_{d-left}\Big((H_{left}\oplus M)||H_{right}\Big)||\bigg(E_{d-right}\Big((H_{left}\oplus M)||H_{right}\Big)\oplus M\bigg)$

Используемые функции - адаптация к аппаратной реализации при d=8

Конкретная реализация во многом зависит от таких параметров, как

Желательное быстродействие
Желательный размер
Желательная технология
Желательное энергопотребление
Желательная помехоустойчивость
Желательная стоимость

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

Выражение преобразования L через простые операции с битами

Пусть L(A,B)=C_0||C_1||C_2||C_3||D_0||D_1||D_2||D_3,~ , тогда

$D_0 = B_0 \oplus A_1 ;$

$D_1 = B_1 \oplus A_2 ;$

$D_2 = B_2 \oplus A_3 \oplus A_0 ;$

$D_3 = B_3 \oplus A_0 ;$

$C_0 = A_0 \oplus D_1 ;$

$C_1 = A_1 \oplus D_2 ;$

$C_2 = A_2 \oplus D_3 \oplus D_0 ;$

$C_3 = A_3 \oplus D_0 .$

где " $\oplus~$ " - операция "исключающее или".

Пусть входной и выходной векторы lin_trans_in[0:7] и lin_trans_out[0:7] соответственно, тогда

verilog-код

assign lin_trans_out[4:7]=lin_trans_in[4:7] ^ {lin_trans_in [1:3],lin_trans_in [0]} ^ {2'b0,lin_trans_in [0],1'b0}, lin_trans_out[0:3]=lin_trans_in[0:3] ^ {lin_trans_out[1:3],lin_trans_out[0]} ^ {2'b0,lin_trans_out[0],1'b0};

Константы при разных $l_{hash}$

Для $l_{hash}=~512, ~384, ~256, ~224$ будем иметь соответственно:

verilog-код

assign hash_0_512[0:1023]= 1024'h6fd14b963e00aa17636a2e057a15d5438a225e8d0c97ef0be9341259f2b3c361891da0c1536f801e2aa9056bea2b6d80588eccdb2075baa6a90f3a76baf83bf70169e60541e34a6946b58a8e2e6fe65a1047a7d0c1843c243b6e71b12d5ac199cf57f6ec9db1f856a706887c5716b156e3c2fcdfe68517fb545a4678cc8cdd4b, hash_0_384[0:1023]= 1024'h481e3bc6d813398a6d3b5e894ade879b63faea68d480ad2e3324cb21480f826798aec84d9082b928d45dea304111424936f555b2924847ecc72d0a93baf43ce1569b7f8a27db454c9ef4bd496397af0e589fc27d26aa80cd80c88b8c9deb2eda8a7981e8f8d5373af43967adddd17a71a9b4d3bda475d39497643fba9842737f, hash_0_256[0:1023]= 1024'heb98a3412c20d3eb92cdbe7b9cb245c11c93519160d4c7fa260082d67e508a03a4239e267726b945e0fb1a48d41a9477cdb5ab26026b177a56f024420fff2fa871a396897f2e4d751d144908f77de262277695f776248f9487d5b6574780296c5c5e272dac8e0d6c518450c657057a0f7be4d367702412ea89e3ab13d31cd769, hash_0_224[0:1023]= 1024'h2dfedd62f99a98acae7cacd619d634e7a4831005bc301216b86038c6c966149466d9899f2580706fce9ea31b1d9b1adc11e8325f7b366e10f994857f02fa06c11b4f1b5cd8c840b397f6a17f6e738099dcdf93a5adeaa3d3a431e8dec9539a6822b4a98aec86a1e4d574ac959ce56cf015960deab5ab2bbf9611dcf0dd64ea6e;

Константы С раундов

$C_i=R_6(C_{i-1},0),~ i=1\dots 42, ~C_0=\left \lfloor (\sqrt{2}-1)\times 2^{256} \right \rfloor~$

Представим их в виде массива, $C_{i+1}=$ round_const[i][0:255]

verilog-код

assign round_const[0 ][0:255]=256'h6a09e667f3bcc908b2fb1366ea957d3e3adec17512775099da2f590b0667322a, round_const[1 ][0:255]=256'hbb896bf05955abcd5281828d66e7d99ac4203494f89bf12817deb43288712231, round_const[2 ][0:255]=256'h1836e76b12d79c55118a1139d2417df52a2021225ff6350063d88e5f1f91631c, round_const[3 ][0:255]=256'h263085a7000fa9c3317c6ca8ab65f7a7713cf4201060ce886af855a90d6a4eed, round_const[4 ][0:255]=256'h1cebafd51a156aeb62a11fb3be2e14f60b7e48de85814270fd62e97614d7b441, round_const[5 ][0:255]=256'he5564cb574f7e09c75e2e244929e9549279ab224a28e445d57185e7d7a09fdc1, round_const[6 ][0:255]=256'h5820f0f0d764cff3a5552a5e41a82b9eff6ee0aa615773bb07e8603424c3cf8a, round_const[7 ][0:255]=256'hb126fb741733c5bfcef6f43a62e8e5706a26656028aa897ec1ea4616ce8fd510, round_const[8 ][0:255]=256'hdbf0de32bca77254bb4f562581a3bc991cf94f225652c27f14eae958ae6aa616, round_const[9 ][0:255]=256'he6113be617f45f3de53cff03919a94c32c927b093ac8f23b47f7189aadb9bc67, round_const[10][0:255]=256'h80d0d26052ca45d593ab5fb3102506390083afb5ffe107dacfcba7dbe601a12b, round_const[11][0:255]=256'h43af1c76126714dfa950c368787c81ae3beecf956c85c962086ae16e40ebb0b4, round_const[12][0:255]=256'h9aee8994d2d74a5cdb7b1ef294eed5c1520724dd8ed58c92d3f0e174b0c32045, round_const[13][0:255]=256'h0b2aa58ceb3bdb9e1eef66b376e0c565d5d8fe7bacb8da866f859ac521f3d571, round_const[14][0:255]=256'h7a1523ef3d970a3a9b0b4d610e02749d37b8d57c1885fe4206a7f338e8356866, round_const[15][0:255]=256'h2c2db8f7876685f2cd9a2e0ddb64c9d5bf13905371fc39e0fa86e1477234a297, round_const[16][0:255]=256'h9df085eb2544ebf62b50686a71e6e828dfed9dbe0b106c9452ceddff3d138990, round_const[17][0:255]=256'he6e5c42cb2d460c9d6e4791a1681bb2e222e54558eb78d5244e217d1bfcf5058, round_const[18][0:255]=256'h8f1f57e44e126210f00763ff57da208a5093b8ff7947534a4c260a17642f72b2, round_const[19][0:255]=256'hae4ef4792ea148608cf116cb2bff66e8fc74811266cd641112cd17801ed38b59, round_const[20][0:255]=256'h91a744efbf68b192d0549b608bdb3191fc12a0e83543cec5f882250b244f78e4, round_const[21][0:255]=256'h4b5d27d3368f9c17d4b2a2b216c7e74e7714d2cc03e1e44588cd9936de74357c, round_const[22][0:255]=256'h0ea17cafb8286131bda9e3757b3610aa3f77a6d0575053fc926eea7e237df289, round_const[23][0:255]=256'h848af9f57eb1a616e2c342c8cea528b8a95a5d16d9d87be9bb3784d0c351c32b, round_const[24][0:255]=256'hc0435cc3654fb85dd9335ba91ac3dbde1f85d567d7ad16f9de6e009bca3f95b5, round_const[25][0:255]=256'h927547fe5e5e45e2fe99f1651ea1cbf097dc3a3d40ddd21cee260543c288ec6b, round_const[26][0:255]=256'hc117a3770d3a34469d50dfa7db020300d306a365374fa828c8b780ee1b9d7a34, round_const[27][0:255]=256'h8ff2178ae2dbe5e872fac789a34bc228debf54a882743caad14f3a550fdbe68f, round_const[28][0:255]=256'habd06c52ed58ff091205d0f627574c8cbc1fe7cf79210f5a2286f6e23a27efa0, round_const[29][0:255]=256'h631f4acb8d3ca4253e301849f157571d3211b6c1045347befb7c77df3c6ca7bd, round_const[30][0:255]=256'hae88f2342c23344590be2014fab4f179fd4bf7c90db14fa4018fcce689d2127b, round_const[31][0:255]=256'h93b89385546d71379fe41c39bc602e8b7c8b2f78ee914d1f0af0d437a189a8a4, round_const[32][0:255]=256'h1d1e036abeef3f44848cd76ef6baa889fcec56cd7967eb909a464bfc23c72435, round_const[33][0:255]=256'ha8e4ede4c5fe5e88d4fb192e0a0821e935ba145bbfc59c2508282755a5df53a5, round_const[34][0:255]=256'h8e4e37a3b970f079ae9d22a499a714c875760273f74a9398995d32c05027d810, round_const[35][0:255]=256'h61cfa42792f93b9fde36eb163e978709fafa7616ec3c7dad0135806c3d91a21b, round_const[36][0:255]=256'hf037c5d91623288b7d0302c1b941b72676a943b372659dcd7d6ef408a11b40c0, round_const[37][0:255]=256'h2a306354ca3ea90b0e97eaebcea0a6d7c6522399e885c613de824922c892c490, round_const[38][0:255]=256'h3ca6cdd788a5bdc5ef2dceeb16bca31e0a0d2c7e9921b6f71d33e25dd2f3cf53, round_const[39][0:255]=256'hf72578721db56bf8f49538b0ae6ea470c2fb1339dd26333f135f7def45376ec0, round_const[40][0:255]=256'he449a03eab359e34095f8b4b55cd7ac7c0ec6510f2c4cc79fa6b1fee6b18c59e, round_const[41][0:255]=256'h73bd6978c59f2b219449b36770fb313fbe2da28f6b04275f071a1b193dde2072;

Позиции полубайтов после перемешивания

Пусть на вход P_8 поступил 1024-битный вектор - массив из 256-ти 4-битных векторов: $A=A_1||A_2||\dots||A_{256}$ , а на выходе имеем $B=B_1||B_2||\dots||B_{256}$ , тогда $B_i=A_{permut\_pose[i*8-1-:8]}~$ . Это означает, что первый полубайт выходного вектора будет равен полубайту входного вектора с номером позиции(от 0 до 255), содержащемся в первом байте константы permut_pose[0:2047], второй полубайт выходного вектора - полубайту входного вектора с номером позиции, содержащемся во втором байте permut_pose[0:2047], и т. д.

verilog-код

assign permut_pose[0:2047]=2048'h00030407080b0c0f10131417181b1c1f20232427282b2c2f30333437383b3c3f40434447484b4c4f50535457585b5c5f60636467686b6c6f70737477787b7c7f80838487888b8c8f90939497989b9c9fa0a3a4a7a8abacafb0b3b4b7b8bbbcbfc0c3c4c7c8cbcccfd0d3d4d7d8dbdcdfe0e3e4e7e8ebeceff0f3f4f7f8fbfcff020106050a090e0d121116151a191e1d222126252a292e2d323136353a393e3d424146454a494e4d525156555a595e5d626166656a696e6d727176757a797e7d828186858a898e8d929196959a999e9da2a1a6a5aaa9aeadb2b1b6b5bab9bebdc2c1c6c5cac9cecdd2d1d6d5dad9dedde2e1e6e5eae9eeedf2f1f6f5faf9fefd;

Используемые функции - адаптация к программной реализации при d=8

Суть этой адаптации заключается в минимизации числа операций путем использования операций с как можно более длинными операндами. Сделать это позволяют такие технологии, как, например, SIMD, SSE2, AVX.

примеры реализации на языке C

Для пояснения работы функций, а также для того, чтобы показать константы раундов, будут приводиться куски кода на C[3] . Будучи соединенными в один файл и дополненными функцией main(), приведенной ниже, они компилируются[4]; полученная программа реализует функцию E_8~ .

предварительные объявления на C

#include <emmintrin.h> #include <stdlib.h> #include <stdio.h>

typedef __m128i word128; /word128 defines a 128-bit SSE2 word/

/define data alignment for different C compilers/ #if defined(GNUC) #define DATA_ALIGN16(x) x attribute ((aligned(16))) #else #define DATA_ALIGN16(x) __declspec(align(16)) x #endif

/The following defines operations on 128-bit word(s)/ #define CONSTANT(b) _mm_set1_epi8((b)) /set each byte in a 128-bit register to be "b"/

#define XOR(x,y) _mm_xor_si128((x),(y)) /XOR(x,y) = x ^ y, where x and y are two 128-bit word/ #define AND(x,y) _mm_and_si128((x),(y)) /AND(x,y) = x & y, where x and y are two 128-bit word/ #define ANDNOT(x,y) _mm_andnot_si128((x),(y)) /ANDNOT(x,y) = (!x) & y, where x and y are two 128-bit word/ #define OR(x,y) _mm_or_si128((x),(y)) /OR(x,y) = x | y, where x and y are two 128-bit word/

#define SHR1(x) _mm_srli_epi16((x), 1) /SHR1(x) = x >> 1, where x is a 128 bit word/ #define SHR2(x) _mm_srli_epi16((x), 2) /SHR2(x) = x >> 2, where x is a 128 bit word/ #define SHR4(x) _mm_srli_epi16((x), 4) /SHR4(x) = x >> 4, where x is a 128 bit word/ #define SHR8(x) _mm_slli_epi16((x), 8) /SHR8(x) = x >> 8, where x is a 128 bit word/ #define SHR16(x) _mm_slli_epi32((x), 16) /SHR16(x) = x >> 16, where x is a 128 bit word/ #define SHR32(x) _mm_slli_epi64((x), 32) /SHR32(x) = x >> 32, where x is a 128 bit word/ #define SHR64(x) _mm_slli_si128((x), 8) /SHR64(x) = x >> 64, where x is a 128 bit word/

#define SHL1(x) _mm_slli_epi16((x), 1) /SHL1(x) = x << 1, where x is a 128 bit word/ #define SHL2(x) _mm_slli_epi16((x), 2) /SHL2(x) = x << 2, where x is a 128 bit word/ #define SHL4(x) _mm_slli_epi16((x), 4) /SHL4(x) = x << 4, where x is a 128 bit word/ #define SHL8(x) _mm_srli_epi16((x), 8) /SHL8(x) = x << 8, where x is a 128 bit word/ #define SHL16(x) _mm_srli_epi32((x), 16) /SHL16(x) = x << 16, where x is a 128 bit word/ #define SHL32(x) _mm_srli_epi64((x), 32) /SHL32(x) = x << 32, where x is a 128 bit word/ #define SHL64(x) _mm_srli_si128((x), 8) /SHL64(x) = x << 64, where x is a 128 bit word/

Пример функции main()

int main() { int j; void* e8_out;

    //here can be any constant you like to use for E8 check
    char e8_in[128]={0,0xe0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};


    e8_out=(void*)calloc(9,sizeof(word128));

    //16 byte allignment - important!
    e8_out=(void*)( ((int) e8_out) + 16 - (((int) e8_out) & 15) );

    for (j = 0; j < 128; j++)
            *((char*)e8_out+j)=e8_in[j];

    printf("\ninput\n");
    for (j = 0; j < 128; j++)
            printf("%.2x",(char)(*((char*)e8_out+j)) & 0xff);

    E8((word128*)e8_out);

    //out must be equal
    //2dfedd62f99a98acae7cacd619d634e7a4831005bc301216b86038c6c966149466d9899f2580706fce9ea31b1d9b1adc11e8325f7b366e10f994857f02fa06c11b4f1b5cd8c840b397f6a17f6e738099dcdf93a5adeaa3d3a431e8dec9539a6822b4a98aec86a1e4d574ac959ce56cf015960deab5ab2bbf9611dcf0dd64ea6e
    printf("\noutput\n");
    for (j = 0; j < 128; j++)
            printf("%.2x",(char)(*((char*)e8_out+j)) & 0xff);

    return(0);

}

Функция

Преобразует четыре 128-битных вектора в зависимости от 128-битной константы. То есть

$(x_0,x_1,x_2,x_3)=SBox(x_{00},x_{10},x_{20},x_{30},c)~$

Алгоритм таков. Введем еще 128-битную переменную t и проинициализируем переменные начальными значениями

$(x_0,x_1,x_2,x_3)=(x_{00},x_{10},x_{20},x_{30})~$ ,

тогда последовательность присваиваний следующая:

$x_3=\neg x_3~$
$x_0 = x_0 \oplus (c~\&~(\neg x_2))$
$t~~ = c~ \oplus (x_0 ~\&~x_1)$
$x_0 = x_0 \oplus (x_2 ~\&~x_3)$
$x_3 = x_3 \oplus ((\neg x_1)~\&~x_2)$
$x_1 = x_1 \oplus (x_0 ~\&~x_2)$
$x_2 = x_2 \oplus (x_0 ~\&~(\neg x_3))$
$x_0 = x_0 \oplus (x_1|x_3)$
$x_3 = x_3 \oplus (x_1 ~\&~x_2)$
$x_1 = x_1 \oplus (t~\&~x_0)$
$x_2 = x_2 \oplus t$

возможная реализация на C

/Sbox implements S0 and S1, selected by a constant bit/ #define S_BOX(m0,m1,m2,m3,cnst) {
word128 t;
m3 = XOR(m3,CONSTANT(0xff));
m0 = XOR(m0,ANDNOT(m2,cnst));
t = XOR(cnst,AND(m0,m1));
m0 = XOR(m0,AND(m3,m2));
m3 = XOR(m3,ANDNOT(m1,m2));
m1 = XOR(m1,AND(m0,m2));
m2 = XOR(m2,ANDNOT(m3,m0));
m0 = XOR(m0,OR(m1,m3));
m3 = XOR(m3,AND(m1,m2));
m2 = XOR(m2,t);
m1 = XOR(m1,AND(t,m0));
}

- описание используемых макросов см. в блоке "предварительные объявления на C"

Функция

Преобразует восемь 128-битных переменных. Пусть (b_0,b_1,b_2,b_3,b_4,b_5,b_6,b_7)=LinTrans(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7)~ , тогда

$b_4 = a_4 \oplus a_1$

$b_5 = a_5 \oplus a_2$

$b_6 = a_6 \oplus a_3 \oplus a_0$

$b_7 = a_7 \oplus a_0$

$b_0 = a_0 \oplus b_5$

$b_1 = a_1 \oplus b_6$

$b_2 = a_2 \oplus b_7 \oplus b_4$

$b_3 = a_3 \oplus b_4$

возможная реализация на C

/The MDS code/ #define LIN_TRANS(word)
word[1] = XOR(word[1],word[2]);
word[3] = XOR(word[3],word[4]);
word[5] = XOR(XOR(word[5],word[6]),word[0]);
word[7] = XOR(word[7],word[0]);
word[0] = XOR(word[0],word[3]);
word[2] = XOR(word[2],word[5]);
word[4] = XOR(XOR(word[4],word[7]),word[1]);
word[6] = XOR(word[6],word[1]);

В коде для удобства дальнейшего использования a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7~ соответствует (word[0],word[2],word[4],word[6],word[1],word[3],word[5],word[7])

- описание используемых макросов см. в блоке "предварительные объявления на C"

Функция

Преобразует 128-битную переменную в зависимости от целой константы $n:~ 6\ge n \ge 0~$ . Эта функция не оптимизируется для использования 128-битных переменных, однако для совместного использования с другими функциями из этого раздела она необходима.

Пусть b=Permutation(a,n)~ , $b=b_0||b_1||\dots||b_{127},a=a_0||a_1||\dots||a_{127}~$ где. Алгоритм получения числа таков:

$for~ i=0 ~~to~ \frac{128}{2\times 2^n}-1 ~~begin~$

$Swap \Big((b_{2\times 2^n\times i+0}||b_{2\times 2^n\times i+1}||\dots||b_{2\times 2^n\times i+2^n-1}),~(b_{2\times 2^n\times i+2^n+0}||b_{2\times 2^n\times i+2^n+1}||\dots||b_{2\times 2^n\times i+2^n+2^n-1})\Big)$

end~

Здесь запись Swap(p,q)~ означает такой участок алгоритма, после которого переменная принимает значение, которое было у переменной , а переменная принимает значение, которое было у переменной .

возможная реализация на C

/The following defines operations on 128-bit word(s)/ #define SWAP0(x) OR(SHR1(AND((x),CONSTANT(0xaa))),SHL1(AND((x),CONSTANT(0x55)))) /*swapping bit 2i with bit 2i+1 of the 128-bit x */ #define SWAP1(x) OR(SHR2(AND((x),CONSTANT(0xcc))),SHL2(AND((x),CONSTANT(0x33)))) /*swapping bit 4i||4i+1 with bit 4i+2||4i+3 of the 128-bit x */ #define SWAP2(x) OR(SHR4(AND((x),CONSTANT(0xf0))),SHL4(AND((x),CONSTANT(0xf)))) /*swapping bits 8i||8i+1||8i+2||8i+3 with bits 8i+4||8i+5||8i+6||8i+7 of the 128-bit x */ #define SWAP3(x) OR(SHR8(x),SHL8(x)) /*swapping bits 16i||16i+1||...||16i+7 with bits 16i+8||16i+9||...||16i+15 of the 128-bit x */ #define SWAP4(x) OR(SHR16(x),SHL16(x)) /*swapping bits 32i||32i+1||...||32i+15 with bits 32i+16||32i+17||...||32i+31 of the 128-bit x */ #define SWAP5(x) _mm_shuffle_epi32((x),_MM_SHUFFLE(2,3,0,1)) /swapping bits 64i||64i+1||...||64i+31 with bits 64i+32||64i+33||...||64i+63 of the 128-bit x/ #define SWAP6(x) _mm_shuffle_epi32((x),_MM_SHUFFLE(1,0,3,2)) /swapping bits 128i||128i+1||...||128i+63 with bits 128i+64||128i+65||...||128i+127 of the 128-bit x/ #define STORE(x,p) _mm_store_si128((__m128i *)(p), (x)) /store the 128-bit word x into memeory address p, where p is the multile of 16 bytes/ #define LOAD(p) _mm_load_si128((__m128i *)(p)) /load 16 bytes from the memory address p, return a 128-bit word, where p is the multile of 16 bytes/

#define PERMUTATION(word,n)
word[1] = SWAP##n(word[1]); word[3] = SWAP##n(word[3]); word[5] = SWAP##n(word[5]); word[7] = SWAP##n(word[7]);

- описание используемых макросов см. в блоке "предварительные объявления на C"

Функция , адаптированная к программной реализации

Преобразует 1024-битный вектор. Совпадает с функцией E_8 , описанной в обобщенном случае(в том смысле, что при совпадении значений аргументов совпадают значения функций). Пусть на вход поступил 1024-битный вектор. Представим его в виде набора 8-ми 128-битных переменных: (x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7)~ . После следующих преобразований они будут представлять собой выходной вектор:

for~ r=0 ~~to~ 41 ~~begin~

$(x_0,x_2,x_4,x_6)=SBox(x_0,x_2,x_4,x_6,C^{even}_r)~$

$(x_1,x_3,x_5,x_7)=SBox(x_1,x_3,x_5,x_7,C^{odd}_r)~$

(x_0, x_2, x_4, x6_, x_1, x_3, x_5, x_7) = LinTrans(x_0, x_2, x_4, x_6, x_1, x_3, x_5, x_7)~

$x_1 = Permutation(x_1,r \bmod 7)~$

$x_3 = Permutation(x_3,r \bmod 7)~$

$x_5 = Permutation(x_5,r \bmod 7)~$

$x_7 = Permutation(x_7,r \bmod 7)~$

end~

Использующиеся 128-битные константы задаются следующим образом: $C^{odd}_r=C^1_r||C^3_r||\dots||C^{255}_r,~C^{even}_r=C^0_r||C^2_r||\dots||C^{254}_r,~C_r=R_6(C_{r-1},0),~ r=1\dots 42, ~C_0=\left \lfloor (\sqrt{2}-1)\times 2^{256} \right \rfloor~$

возможная реализация на C

/42 round constants, each round constant is 32-byte (256-bit)//*the round function of E8 */ #define ROUND_FUNCTION(word,n,r)
S_BOX(((word)[0]),((word)[2]),((word)[4]),((word)[6]),(LOAD(E8_bitslice_roundconstant[r])))
S_BOX(((word)[1]),((word)[3]),((word)[5]),((word)[7]),(LOAD(E8_bitslice_roundconstant[r]+16)))
LIN_TRANS(word)
PERMUTATION((word),n)

void E8(word128 *word){ int i; for (i = 0; i < 42; i = i+7) { ROUND_FUNCTION(word,0,i) ROUND_FUNCTION(word,1,i+1) ROUND_FUNCTION(word,2,i+2) ROUND_FUNCTION(word,3,i+3) ROUND_FUNCTION(word,4,i+4) ROUND_FUNCTION(word,5,i+5) ROUND_FUNCTION(word,6,i+6) } }

- описание используемых макросов см. в подразделах выше.

Исходные данные

Входной параметр

$l_{hash}~~$ - длина хэша(число бит в выходном векторе хэш-функции).

Может принимать только следующие значения:

224, 256, 384 и 512;

напоминаю, что данная статья, строго говоря, описывает семейство из 4-х хэш-функций.

Входное сообщение

Представляет собой число - длину сообщения и битовый вектор M_0~ (если $L \neq 0~$ ). Даже если L=0~ никаких трудностей для вычисления JH(M_0)~ не возникает.

Алгоритм вычисления

1) Дополнение входного вектора

Присоединение к сообщению M_0~ дополнительных бит в конце. Происходит в три этапа:

1.1)Дополнение единицей.

Присоединение к концу сообщения единичного бита.

1.2)Дополнение нулями.

Присоединение к концу сообщения, дополненного единицей, нулевых бит в количестве $383 + (-L \bmod 512)~$ штук.

1.3)Дополнение длиной сообщения.

Присоединение к концу сообщения, дополненного единицей и нулями, 128-ми бит, в которых записана длина исходного сообщения(например, если L=2~ , то добавка будет выглядеть так: $0\dots 010~$ ).

В итоге получится дополненное сообщение с длиной, кратной 512~ .

2) Свертка дополненного входного вектора функцией

разбивается на блоки по 512~ бит. Обозначим за число таких блоков.

Свертка происходит за итераций. На -той итерации на вход F_8~ поступает -тый 512~ -ти битный блок M_i~ сообщения и значение $H_{i-1}=F_8(H_{i-2},M_{i-1})~$ , вычисленное на предыдущей итерации. Имеется также нулевая итерация, на которой вычисляется H_0~ из $H_{-1}~$ и M_0~ . Таким образом имеем:

$H = H_N = F_8(H_{N-1},M_N)= F_8(F_8(H_{N-2},M_{N-1}),M_N) =\dots= F_8( \dots(H_{-1},M_0)\dots)$ .

поясняющая схема

$H_{-1}~$ и M_0~ выбираются так: первые 16~ бит $H_{-1}~$ равны входному параметру $l_{hash}~$ - размеру выходного хэша (для $l_{hash}~$ , равных 512, ~324, ~256 или 224~ это соответственно 0200h, 0180h, 0100h или 00e0h), а остальные биты $H_{-1}~$ и все биты M_0~ задаются равными .

3) Выборка хэша из выхода функции

Из 1024~ -битного вектора $H_{N}=H^0_{N}||H^1_{N}||\dots||H^{1023}_{N}~$ , полученного на выходе F_8~ на последней итерации свертки дополненного входного сообщения, выбираются последние $l_{hash}~$ бит:

$JH(M_0)=H^{1023+1-l_{hash}}_{N}||H^{1023+2-l_{hash}}_{N}||\dots||H^{1023}_{N}~$

Криптоанализ

См. также

MDS matrix

Advanced Encryption Standard

Substitution-permutation network

Ссылки

документация, актуальная в ноябре 2011 года

http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf

варианты исходных кодов на VHDL моделей электронных устройств, реализующих JH:

http://cryptography.gmu.edu/athena/sources/2011_10_01/folded_unrolled/JH_fv2.zip

http://cryptography.gmu.edu/athena/sources/2011_10_01/folded_unrolled/JH_u2.zip

http://cryptography.gmu.edu/athena/sources/2011_10_01/basic/JH_basic.zip

варианты исходных кодов на C, реализующих JH:

http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_ref.h

http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_bitslice_ref64.h

http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_sse2_opt64.h

страница автора для поддержки JH

http://www3.ntu.edu.sg/home/wuhj/research/jh/index.html

ссылки на исследования криптоаналитиков и архивы файлов, отправлявшиеся на конкурс SHA-3

http://ehash.iaik.tugraz.at/wiki/JH

ссылки на архивы с исходными кодами на VHDL(и сопутствующими файлами) моделей электронных устройств, реализующих алгоритмы хэш-функций, прошедших во второй тур SHA-3

http://cryptography.gmu.edu/athena/index.php?id=source_codes

ссылки на исследования характеристик электронных устройств(реализованных на ПЛИС), реализующих алгоритмы хэш-функций, прошедших в финал второго тура SHA-3

http://ehash.iaik.tugraz.at/wiki/SHA-3_Hardware_Implementations

http://rijndael.ece.vt.edu/sha3/publications.html

Примечания

↑ сравнение финалистов второго тура SHA по параметрам реализации на различных ПЛИС http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_07.pdf
↑ алгоритм взят здесь: http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf
↑ Эти куски взяты по адресу http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_sse2_opt64.h и изменены для ясности и простоты.
↑ При использовании компилятора gcc для того, чтобы он подразумевал возможность использования дополнительных командных наборов, поддерживаемых процессором, типа SSE2, в командную строку при компиляции можно добавить опцию -march=native (например "gcc -o prog prog.c -Wall -march=native").

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94