Меню Главная Случайная статья Настройки JH Материал из https://ru.wikipedia.org JH — семейство из четырёх криптографических хеш-функций: JH-224, JH-256, JH-384 и JH-512. Алгоритмы этих хеш-функций отличаются только значением одного внутреннего параметра — длины (в битах) ${\displaystyle l_{hash}}$ выходного значения (которая и указана после дефиса в названии). Далее в статье при описании алгоритма я буду считать этот параметр частью входных данных для удобства, говоря о JH, как об одном алгоритме или одной хеш-функции. Хеш-функция JH входит в пятёрку финалистов второго тура SHA-3. В процессе этого конкурса она была улучшена. В статье рассматривается последняя на данный момент версия, которую также можно назвать JH42 (так как главное изменение состояло в том, что число раундов в функции компрессии стало равно 42). Дата выхода документации по ней — 16 января 2011 года. При хешировании входное сообщение дополняется и разделяется на части, которые далее последовательно обрабатываются так называемой функцией компрессии. Эта функция описана в спецификации в общем виде — то есть с переменным параметром d, меняя который можно конструировать JH-подобные хеш-функции (тем более криптостойкие, чем больше d). В JH исходно d=8. При выборе финалиста в конкурсе SHA решающую роль играют не криптографические характеристики (они у всех функций отличные), а гибкость и оптимальность в программной и аппаратной реализации. На тему аппаратной реализации существует много исследований, например[1]. Содержание 1 Алгоритм[2] 1.1 Уточнения 1.1.1 О названии элементов битовых векторов 1.1.2 Обозначение конкатенации 1.2 Используемые функции — обобщённый случай 1.2.1 S-box — Si(x) 1.2.2 Линейное преобразование пар ячеек — L(A,B) 1.2.3 Перемешивание — Pd 1.2.4 Преобразование-раунд — Rd(A,C) 1.2.5 Преобразование Ed 1.2.6 Функция свёртки Fd(H,M) 1.3 Используемые функции — адаптация к аппаратной реализации при d=8 1.3.1 Выражение преобразования L через простые операции с битами 1.3.2 Константы H0 при разных lhash 1.3.3 Константы C раундов R8 1.3.4 Позиции полубайтов после перемешивания P8 1.4 Используемые функции — адаптация к программной реализации при d=8 1.4.1 примеры реализации на языке C 1.4.2 Функция SBox 1.4.3 Функция LinTrans 1.4.4 Функция Permutation 1.4.5 Функция E8, адаптированная к программной реализации 1.5 Исходные данные 1.5.1 Входной параметр 1.5.2 Входное сообщение 1.6 Алгоритм вычисления JH(M0) 2 См. также 3 Примечания 4 Ссылки Алгоритм[2] Уточнения Будем считать, что у всех обсуждаемых тут битовых векторов есть начало и конец, причём бит, расположенный в начале (слева) является первым, имеет позицию 0 и считается наиболее значимым, соответственно, бит, расположенный в конце (справа), является последним, имеет позицию с наибольшим номером, на один меньшим, чем число разрядов вектора, и считается наименее значимым. То же самое, за исключением номера позиции, будем подразумевать для векторов, состоящих из битовых векторов, например, для сообщения, состоящего из блоков, или блока, состоящего из полубайтов. С номером же позиции какой-либо составной части битового вектора, состоящей из нескольких бит, будет путаница, создаваемая для удобства. Так, номера позиций полубайтов в блоке будут начинаться с нуля, а номера позиций блоков в сообщении — с единицы… В векторе 8afd4h первый, наиболее значимый полубайт расположен слева – это 8; последний, наименее значимый полубайт расположен справа – это 4. Если эту запись рассматривать, как битовый вектор, а не как полубайтовый, то она эквивалентна такой: 1000_1010_1111_1101_0100, тут первый(с номером 0, левый, старший) бит - 1, а последний(с номером 19, правый, младший) - 0. Пусть вектор ${\displaystyle A}$ состоит из последовательно идущих векторов ${\displaystyle A_{1},A_{2},\dots ,A_{N}}$, тогда этот факт будет обозначаться так: ${\displaystyle A=A_{1}||A_{2}||\dots ||A_{N}}$ Используемые функции — обобщённый случай Здесь описаны функции, с помощью которых можно строить JH-подобные алгоритмы, меняя параметр ${\displaystyle d}$ Это функция, преобразующая s-блок (то есть размеры её входного и выходного значений одинаковы и равны 4 битам). В алгоритме используются 2 таких функции: ${\displaystyle S_{1}}$ и ${\displaystyle S_{0}}$. Их таблицы значений такие: ${\displaystyle x}$ 0 1 2 3 4 5 6 7 8 9 a b c d e f ${\displaystyle S_{0}(x)}$ 9 0 4 b d c 3 f 1 a 2 6 7 5 8 e ${\displaystyle S_{1}(x)}$ 3 c 6 d 5 7 1 9 f 2 0 4 b a e 8 Эта функция преобразует пару s-блоков (то есть размеры её входного и выходного значений одинаковы и равны 8 битам). Наиболее лаконичную запись она имеет в терминах конечных полей многочленов. Рассмотрим конечное поле многочленов над ${\displaystyle GF(2)}$ степени не выше 3-й. Оно изоморфно полю ${\displaystyle GF(2^{4})}$; установим стандартное для таких случаев соответствие межу полем многочленов и полем чисел: многочлен будет соответствовать числу, равному значению многочлена при ${\displaystyle x=2}$. Выберем для этого поля многочленов следующий примитивный многочлен: ${\displaystyle x^{4}+x+1}$. Тогда, если рассматривать ${\displaystyle L(A,B)}$, как функцию, преобразующую 2 многочлена, а числа и буквы — как многочлены, то ${\displaystyle L(A,B)=((5\bullet A+2\bullet B),(2\bullet A+B))}$, где «${\displaystyle \bullet }$» и «${\displaystyle +}$» — операции умножения и сложения в данном поле многочленов. Функция ${\displaystyle P_{d}}$ является композицией трёх более простых перемешиваний, преобразующих массив из ${\displaystyle 2^{d}}$ битовых векторов (то есть размеры их входных и выходных значений одинаковы и равны ${\displaystyle 2^{d}\times k}$ битам, где ${\displaystyle k}$ — число бит в одном элементе этого массива): ${\displaystyle P_{d}(A)=\phi _{d}(P'_{d}(\pi _{d}(A)))}$ Приведем алгоритмы этих перемешиваний, обозначив за ${\displaystyle A=A_{0}||A_{1}||\dots ||A_{2^{d}-1}}$ и ${\displaystyle B=B_{0}||B_{1}||\dots ||B_{2^{d}-1}}$ (где ${\displaystyle A_{i}}$ и ${\displaystyle B_{i}}$ — битовые векторы одинакового размера для всех ${\displaystyle i}$) — входной и выходной векторы соответственно: ${\displaystyle B=\pi _{d}(A)}$: ${\displaystyle for~i=0~~to~2^{d-2}-1~~begin}$ ${\displaystyle B_{4i+0}=A_{4i+0}}$ ${\displaystyle B_{4i+1}=A_{4i+1}}$ ${\displaystyle B_{4i+2}=A_{4i+3}}$ ${\displaystyle B_{4i+3}=A_{4i+2}}$ ${\displaystyle end}$ ${\displaystyle B=P'_{d}(A)}$: ${\displaystyle for~i=0~~to~2^{d-1}-1~~begin}$ ${\displaystyle B_{i}=A_{2i}}$ ${\displaystyle B_{i+2^{d-1}}=A_{2i+1}}$ ${\displaystyle end}$ ${\displaystyle B=\phi _{d}(A)}$: ${\displaystyle for~i=0~~to~2^{d-2}-1~~begin}$ ${\displaystyle B_{2i}=A_{2i}}$ ${\displaystyle B_{2i+1}=A_{2i+1}}$ ${\displaystyle B_{2^{d-1}+2i}=A_{2^{d-1}+2i+1}}$ ${\displaystyle B_{2^{d-1}+2i+1}=A_{2^{d-1}+2i}}$ ${\displaystyle end}$ На вход подается ${\displaystyle 2^{d+2}}$- мерный вектор ${\displaystyle A}$. Выход — ${\displaystyle 2^{d+2}}$- мерный вектор. Так же на вход подается ${\displaystyle 2^{d}}$-битная константа ${\displaystyle C}$. Вектор ${\displaystyle A}$ представляется в виде массива из ${\displaystyle 2^{d}}$ полубайт: ${\displaystyle A=A_{0}||A_{1}||\dots ||A_{2^{d}-1}}$. Потом над каждым полубайтом ${\displaystyle A_{i}}$ производится преобразование ${\displaystyle S_{0}}$ или ${\displaystyle S_{1}}$ в зависимости от значения ${\displaystyle C_{i}}$ (если ${\displaystyle C_{i}=0}$, то ${\displaystyle S_{0}}$, иначе — ${\displaystyle S_{1}}$) Далее над каждой парой вида ${\displaystyle (S_{C_{2i}}(A_{2i}),S_{C_{2i+1}}(A_{2i+1}))}$ производится линейное преобразование ${\displaystyle L(S_{C_{2i}}(A_{2i}),S_{C_{2i+1}}(A_{2i+1}))}$. И в конце концов результаты опять группируются в вектор, биты которого подвергаются перемешиванию ${\displaystyle P_{d}}$. Это выражается в виде формулы: ${\displaystyle 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 )}}$ На входе ${\displaystyle 2^{d+2}}$ — мерный вектор ${\displaystyle A}$. Сначала происходит начальная группировка: ${\displaystyle B=G_{d}(A)}$: ${\displaystyle for~i=0~~to~2^{d-1}-1~~begin}$ ${\displaystyle B_{8i+0}=A_{i+128\times 0}}$ ${\displaystyle B_{8i+1}=A_{i+128\times 2}}$ ${\displaystyle B_{8i+2}=A_{i+128\times 4}}$ ${\displaystyle B_{8i+3}=A_{i+128\times 6}}$ ${\displaystyle B_{8i+4}=A_{i+128\times 1}}$ ${\displaystyle B_{8i+5}=A_{i+128\times 3}}$ ${\displaystyle B_{8i+6}=A_{i+128\times 5}}$ ${\displaystyle B_{8i+7}=A_{i+128\times 7}}$ ${\displaystyle end}$ Далее к результату ${\displaystyle B}$ этой группировки применяется ${\displaystyle 6\times (d-1)}$ преобразований-раундов ${\displaystyle R_{d}(B,C)}$ с константами, изменяющимися от раунда к раунду. Начальное значение переменной ${\displaystyle C}$ задаётся, как целая часть числа ${\displaystyle ({\sqrt {2}}-1)\times 2^{2^{d}}}$, то есть ${\displaystyle C=\left\lfloor ({\sqrt {2}}-1)\times 2^{2^{d}}\right\rfloor }$: ${\displaystyle for~i=1~~to~6\times (d-1)~~begin}$ ${\displaystyle C=R_{d-2}(C,0)}$ ${\displaystyle B=R_{d}(B,C)}$ ${\displaystyle end}$ Далее происходит конечная разгруппировка, обратная начальной: ${\displaystyle B_{fin}=G_{d}^{-1}(B)}$, Где ${\displaystyle G_{d}^{-1}:G_{d}(G_{d}^{-1}(B))\equiv B}$