JH — семейство из четырёх криптографических хеш-функций: JH-224, JH-256, JH-384 и JH-512.
Алгоритмы этих хеш-функций отличаются только значением одного внутреннего параметра — длины (в битах) выходного значения (которая и указана после дефиса в названии). Далее в статье при описании алгоритма я буду считать этот параметр частью входных данных для удобства, говоря о JH, как об одном алгоритме или одной хеш-функции.
Хеш-функция JH входит в пятёрку финалистов второго тура SHA-3. В процессе этого конкурса она была улучшена. В статье рассматривается последняя на данный момент версия, которую также можно назвать JH42 (так как главное изменение состояло в том, что число раундов в функции компрессии стало равно 42). Дата выхода документации по ней — 16 января 2011 года.
При хешировании входное сообщение дополняется и разделяется на части, которые далее последовательно обрабатываются так называемой функцией компрессии. Эта функция описана в спецификации в общем виде — то есть с переменным параметром d, меняя который можно конструировать JH-подобные хеш-функции (тем более криптостойкие, чем больше d). В JH исходно d=8.
При выборе финалиста в конкурсе SHA решающую роль играют не криптографические характеристики (они у всех функций отличные), а гибкость и оптимальность в программной и аппаратной реализации. На тему аппаратной реализации существует много исследований, напримерсравнение финалистов второго тура SHA по параметрам реализации на различных ПЛИС http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_07.pdf .
Алгоритмалгоритм взят здесь: http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf
Уточнения
О названии элементов битовых векторов Будем считать, что у всех обсуждаемых тут битовых векторов есть начало и конец, причём бит, расположенный в начале (слева) является первым, имеет позицию 0 и считается наиболее значимым, соответственно, бит, расположенный в конце (справа), является последним, имеет позицию с наибольшим номером, на один меньшим, чем число разрядов вектора, и считается наименее значимым.
То же самое, за исключением номера позиции, будем подразумевать для векторов, состоящих из битовых векторов, например, для сообщения, состоящего из блоков, или блока, состоящего из полубайтов. С номером же позиции какой-либо составной части битового вектора, состоящей из нескольких бит, будет путаница, создаваемая для удобства. Так, номера позиций полубайтов в блоке будут начинаться с нуля, а номера позиций блоков в сообщении — с единицы…
Обозначение конкатенации Пусть вектор состоит из последовательно идущих векторов , тогда этот факт будет обозначаться так:
Используемые функции — обобщённый случай Здесь описаны функции, с помощью которых можно строить JH-подобные алгоритмы, меняя параметр
S-box — Это функция, преобразующая s-блок (то есть размеры её входного и выходного значений одинаковы и равны 4 битам). В алгоритме используются 2 таких функции: и . Их таблицы значений такие: 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 битам). Наиболее лаконичную запись она имеет в терминах конечных полей многочленов.
Рассмотрим конечное поле многочленов над степени не выше 3-й. Оно изоморфно полю ; установим стандартное для таких случаев соответствие межу полем многочленов и полем чисел: многочлен будет соответствовать числу, равному значению многочлена при . Выберем для этого поля многочленов следующий примитивный многочлен:
.
Тогда, если рассматривать , как функцию, преобразующую 2 многочлена, а числа и буквы — как многочлены, то
,
где «» и «» — операции умножения и сложения в данном поле многочленов.
Перемешивание — Функция является композицией трёх более простых перемешиваний, преобразующих массив из битовых векторов (то есть размеры их входных и выходных значений одинаковы и равны битам, где — число бит в одном элементе этого массива):
Приведем алгоритмы этих перемешиваний, обозначив за и (где и — битовые векторы одинакового размера для всех ) — входной и выходной векторы соответственно:
Преобразование-раунд — На вход подается - мерный вектор . Выход — - мерный вектор. Так же на вход подается -битная константа .
Вектор представляется в виде массива из полубайт: .
Потом над каждым полубайтом производится преобразование или в зависимости от значения (если , то , иначе — )
Далее над каждой парой вида производится линейное преобразование .
И в конце концов результаты опять группируются в вектор, биты которого подвергаются перемешиванию .
Это выражается в виде формулы:
Преобразование На входе — мерный вектор . Сначала происходит начальная группировка:
Далее к результату этой группировки применяется преобразований-раундов с константами, изменяющимися от раунда к раунду. Начальное значение переменной задаётся, как целая часть числа , то есть
Далее происходит конечная разгруппировка, обратная начальной:
,
Где
Таким образом,
Функция свёртки На входе -битный вектор и -битный вектор . Сначала преобразуется путём побитового сложения первой половины этого вектора с , потом над результатом выполняется преобразование и наконец результат преобразуется путём побитового сложения его второй половины с вектором .
Запишем это в виде формул. Пусть — первая (старшая) половина вектора , а — вторая. Пусть также функции и возвращают левую и правую половины соответственно. Тогда
Используемые функции — адаптация к аппаратной реализации при d=8 Конкретная реализация во многом зависит от таких параметров, как
Желательное быстродействие Желательный размер Желательная технология Желательное энергопотребление Желательная помехоустойчивость Желательная стоимость
Поэтому без задания этих параметров адаптация невозможна. Я дам описание преобразования с помощью обычных для аппаратной разработки побитовых операций, а также некоторые константы, которые могут пригодиться, если нет существенного ограничения по размерам схемы.
Выражение преобразования через простые операции с битами Пусть , тогда
где «» — операция «исключающее или».
Пусть входной и выходной векторы lin_trans_in[0:7] и lin_trans_out[0:7] соответственно, тогда
Константы при разных Для будем иметь соответственно:
Константы раундов
Представим их в виде массива, round_const[i][0:255]
Позиции полубайтов после перемешивания Пусть на вход поступил 1024-битный вектор — массив из 256-ти 4-битных векторов: , а на выходе имеем , тогда . Это означает, что первый полубайт выходного вектора будет равен полубайту входного вектора с номером позиции (от 0 до 255), содержащемся в первом байте константы permut_pose[0:2047], второй полубайт выходного вектора — полубайту входного вектора с номером позиции, содержащемся во втором байте permut_pose[0:2047], и т. д.
Используемые функции — адаптация к программной реализации при d=8 Суть этой адаптации заключается в минимизации числа операций путём использования операций с как можно более длинными операндами. Сделать это позволяют такие технологии, как, например, SIMD, SSE2, AVX.
примеры реализации на языке C Для пояснения работы функций, а также для того, чтобы показать константы раундов, будут приводиться куски кода на CЭти куски взяты по адресу http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_sse2_opt64.h и изменены для ясности и простоты.. Будучи соединёнными в один файл и дополненными функцией main(), приведённой ниже, они компилируютсяПри использовании компилятора gcc для того, чтобы он подразумевал возможность использования дополнительных командных наборов, поддерживаемых процессором, типа SSE2, в командную строку при компиляции можно добавить опцию -march=native (например "gcc -o prog prog.c -Wall -march=native").; полученная программа реализует функцию .
Функция Преобразует четыре 128-битных вектора в зависимости от 128-битной константы. То есть
Алгоритм таков. Введём ещё 128-битную переменную t и проинициализируем переменные начальными значениями
,
тогда последовательность присваиваний следующая:
Функция Преобразует восемь 128-битных переменных. Пусть , тогда
Функция Преобразует 128-битную переменную в зависимости от целой константы . Эта функция не оптимизируется для использования 128-битных переменных, однако для совместного использования с другими функциями из этого раздела она необходима.
Пусть , где. Алгоритм получения числа таков:
Здесь запись означает такой участок алгоритма, после которого переменная принимает значение, которое было у переменной , а переменная принимает значение, которое было у переменной .
Функция , адаптированная к программной реализации Преобразует 1024-битный вектор. Совпадает с функцией , описанной в обобщённом случае (в том смысле, что при совпадении значений аргументов совпадают значения функций). Пусть на вход поступил 1024-битный вектор. Представим его в виде набора 8-ми 128-битных переменных: . После следующих преобразований они будут представлять собой выходной вектор:
Использующиеся 128-битные константы задаются следующим образом:
Исходные данные
Входной параметр — длина хэша (число бит в выходном векторе хеш-функции).
Может принимать только следующие значения: 224, 256, 384 и 512;
напомним, что данная статья, строго говоря, описывает семейство из 4-х хеш-функций.
Входное сообщение Представляет собой число — длину сообщения и битовый вектор (если ). Даже если никаких трудностей для вычисления не возникает.
Алгоритм вычисления 1) Дополнение входного вектора Присоединение к сообщению дополнительных бит в конце. Происходит в три этапа: 1.1)Дополнение единицей. Присоединение к концу сообщения единичного бита. 1.2)Дополнение нулями. Присоединение к концу сообщения, дополненного единицей, нулевых бит в количестве штук. 1.3)Дополнение длиной сообщения. Присоединение к концу сообщения, дополненного единицей и нулями, 128 бит, в которых записана длина исходного сообщения (например, если , то добавка будет выглядеть так: ). В итоге получится дополненное сообщение с длиной, кратной .
2) Свёртка дополненного входного вектора функцией разбивается на блоки по бит. Обозначим за число таких блоков.
Свёртка происходит за итераций. На -той итерации на вход поступает -й -битный блок сообщения и значение , вычисленное на предыдущей итерации. Имеется также нулевая итерация, на которой вычисляется из и . Таким образом имеем: .
и выбираются так: первые бит равны входному параметру — размеру выходного хэша (для , равных или это соответственно 0200h, 0180h, 0100h или 00e0h), а остальные биты и все биты задаются равными .
3) Выборка хэша из выхода функции Из -битного вектора , полученного на выходе на последней итерации свёртки дополненного входного сообщения, выбираются последние бит:
См. также
Advanced Encryption Standard SP-сеть
Примечания
Ссылки документация, актуальная в ноябре 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