- JH
-
Криптографическая хеш-функция Название JH
Разработчик У Хунцзюнь (англ Wu Hongjun)
Опубликован 16 января 2011 года
Размер хеша 224, 256, 384, 512
Число раундов 42
JH - семейство из четырех криптографических хеш-функций: JH-224, JH-256, JH-384 и JH-512.
Алгоритмы этих хеш-функций отличаются только значением одного внутреннего параметра - длины(в битах) выходного значения(которая и указана после черточки в названии). Далее в статье при описании алгоритма я буду считать этот параметр частью входных данных для удобства, говоря о JH, как об одном алгоритме или одной хеш-функции.
Хэш-функция JH входит в пятерку финалистов второго тура SHA-3. В процессе этого конкурса она была улучшена. В статье я описываю самую последнюю на данный момент версию, которую также можно назвать JH42 (так как главное изменение состояло в том, что число раундов в функции компрессии стало равно 42). Дата выхода документации по ней - 16 января 2011 года.
При хэшировании входное сообщение дополняется и разделяется на части, которые далее последовательно обрабатываются так называемой функцией компрессии. Эта функция описана в спецификации в общем виде - то есть с переменным параметром d, меняя который можно конструировать JH-подобные хэш-функции(тем более криптостойкие, чем больше d). В JH исходно d=8.
При выборе финалиста в конкурсе SHA решающую роль играют не криптографические характеристики(они у всех функций отличные), а гибкость и оптимальность в программной и аппаратной реализации. На тему аппаратной реализации существует много исследований, например,[1].
Содержание
- 1 Алгоритм[2]
- 2 Криптоанализ
- 3 См. также
- 4 Ссылки
- 5 Примечания
Алгоритм[2]
Уточнения
О названии элементов битовых векторов
Будем считать, что у всех обсуждаемых тут битовых векторов есть начало и конец, причем бит, расположенный в начале(слева) является первым, имеет позицию 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
Конкретная реализация во многом зависит от таких параметров, как
- Желательное быстродействие
- Желательный размер
- Желательная технология
- Желательное энергопотребление
- Желательная помехоустойчивость
- Желательная стоимость
Поэтому без задания этих параметров адаптация невозможна. Я дам описание преобразования с помощью обычных для аппаратной разработки побитовых операций, а также некоторые константы, которые могут пригодиться, если нет существенного ограничения по размерам схемы.
Выражение преобразования L через простые операции с битами
Пусть , тогда
где "" - операция "исключающее или".
Пусть входной и выходной векторы
lin_trans_in[0:7]
иlin_trans_out[0:7]
соответственно, тогдаverilog-кодКонстанты при разных
Для будем иметь соответственно:
verilog-кодКонстанты С раундов
Представим их в виде массива,
round_const[i][0:255]
verilog-кодПозиции полубайтов после перемешивания
Пусть на вход поступил 1024-битный вектор - массив из 256-ти 4-битных векторов: , а на выходе имеем , тогда . Это означает, что первый полубайт выходного вектора будет равен полубайту входного вектора с номером позиции(от 0 до 255), содержащемся в первом байте константы
permut_pose[0:2047]
, второй полубайт выходного вектора - полубайту входного вектора с номером позиции, содержащемся во втором байтеpermut_pose[0:2047]
, и т. д.verilog-кодИспользуемые функции - адаптация к программной реализации при d=8
Суть этой адаптации заключается в минимизации числа операций путем использования операций с как можно более длинными операндами. Сделать это позволяют такие технологии, как, например, SIMD, SSE2, AVX.
примеры реализации на языке C
Для пояснения работы функций, а также для того, чтобы показать константы раундов, будут приводиться куски кода на C[3] . Будучи соединенными в один файл и дополненными функцией
main()
, приведенной ниже, они компилируются[4]; полученная программа реализует функцию .предварительные объявления на CПример функции main()Функция
Преобразует четыре 128-битных вектора в зависимости от 128-битной константы. То есть
Алгоритм таков. Введем еще 128-битную переменную t и проинициализируем переменные начальными значениями
,
тогда последовательность присваиваний следующая:
возможная реализация на CФункция
Преобразует восемь 128-битных переменных. Пусть , тогда
возможная реализация на CФункция
Преобразует 128-битную переменную в зависимости от целой константы . Эта функция не оптимизируется для использования 128-битных переменных, однако для совместного использования с другими функциями из этого раздела она необходима.
Пусть , где. Алгоритм получения числа таков:
- :
Здесь запись означает такой участок алгоритма, после которого переменная принимает значение, которое было у переменной , а переменная принимает значение, которое было у переменной .
возможная реализация на CФункция , адаптированная к программной реализации
Преобразует 1024-битный вектор. Совпадает с функцией , описанной в обобщенном случае(в том смысле, что при совпадении значений аргументов совпадают значения функций). Пусть на вход поступил 1024-битный вектор. Представим его в виде набора 8-ми 128-битных переменных: . После следующих преобразований они будут представлять собой выходной вектор:
Использующиеся 128-битные константы задаются следующим образом:
возможная реализация на CИсходные данные
Входной параметр
- длина хэша(число бит в выходном векторе хэш-функции).
Может принимать только следующие значения:
- 224, 256, 384 и 512;
- напоминаю, что данная статья, строго говоря, описывает семейство из 4-х хэш-функций.
Входное сообщение
Представляет собой число - длину сообщения и битовый вектор (если ). Даже если никаких трудностей для вычисления не возникает.
Алгоритм вычисления
1) Дополнение входного вектора
- Присоединение к сообщению дополнительных бит в конце. Происходит в три этапа:
- 1.1)Дополнение единицей.
- Присоединение к концу сообщения единичного бита.
- 1.2)Дополнение нулями.
- Присоединение к концу сообщения, дополненного единицей, нулевых бит в количестве штук.
- 1.3)Дополнение длиной сообщения.
- Присоединение к концу сообщения, дополненного единицей и нулями, 128-ми бит, в которых записана длина исходного сообщения(например, если , то добавка будет выглядеть так: ).
- В итоге получится дополненное сообщение с длиной, кратной .
2) Свертка дополненного входного вектора функцией
- разбивается на блоки по бит. Обозначим за число таких блоков.
- Свертка происходит за итераций. На -той итерации на вход поступает -тый -ти битный блок сообщения и значение , вычисленное на предыдущей итерации. Имеется также нулевая итерация, на которой вычисляется из и . Таким образом имеем:
- .
- и выбираются так: первые бит равны входному параметру - размеру выходного хэша (для , равных или это соответственно 0200h, 0180h, 0100h или 00e0h), а остальные биты и все биты задаются равными .
3) Выборка хэша из выхода функции
- Из -битного вектора , полученного на выходе на последней итерации свертки дополненного входного сообщения, выбираются последние бит:
Криптоанализ
См. также
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"
).
Хеш-функции Общего назначения Криптографические 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
Категории:- Криптографические хеш-функции
- Хеш-функции
Wikimedia Foundation. 2010.