Хеш-функции на основе клеточных автоматов — разновидность хеш-функций, использующая для вычисления клеточные автоматы. Использование клеточных автоматов обеспечивает высокий уровень параллелизма и, следовательно, позволяет достичь высоких скоростей, что необходимо в условиях ограниченных вычислительных мощностей и жестких требований к энергопотреблению (например, Интернет вещей). Хеш-функции на основе клеточных автоматов обладают хорошим лавинным эффектом. Использование клеточных автоматов позволяет добиться устойчивости к атакам временного анализа.
В криптографии наибольший интерес представляют аддитивные клеточные автоматы (сочетание операций XOR и XNOR в его переходной функции) благодаря таким свойствам, как адаптивность, обратимость и масштабируемостьJ. Randall and M. Szydlo. Collisions for SHAO, MDS, HAVAL, MD4, and RIPEMD, but SHA1 still secure. A technical note on the RSA website, August 2004..
Пример Алгоритма Алгоритм получает на вход сообщение произвольного размера и ключ , размером: 128, 192 или 256 бит и возвращает хешированное значение ключа.
Базовое описание алгоритма Первоначальное сообщение должно быть дополнено следующим образом:
дополнение можно производить простым заполнением недостающих разрядов нулями. Обозначим дополненное сообщение как . Аналогично дополняется ключ :
Обозначим дополненный ключ как . Сообщение разбивается на блоки по 512 бит. Каждый 512 битный блок, полученный на предыдущем шаге разбивается ещё раз на 8 подблоков по 64 бита. К каждому 512 блоку применяется правило 30. Выход пункта 5 вместе с 512 битным ключом поступают в функцию трансформации (ФТ). Этот результат подвергается операции XOR с результатом пункта 5 для следующего 512 битного блока. Ключ для последующих раундов получается с помощью поворота ключа предыдущей итерации, который выполняет циклический сдвиг битов на 1. Шаги 6, 7 и 8 повторяются, пока не кончатся блоки сообщения по 512 бит, то есть пока всё сообщение не будет хешировано.
Описание функции трансформации Для получения полностью случайного выхода по заданному входу в функции трансформации используются как клеточные автоматы, так и побитовые логические операции.
Ниже приведен пример возможной трансформации, оперирующей с отдельными 64 битными подблоками.
Это означает, что байты из напрямую отображаются в . или Если раунд нечетный, то используется иначе . . или Если раунд нечетный, то используется иначе . .
. или Если раунд нечетный, то используется иначе . Функция определена в пункте 1.
.
. или Если раунд нечетный, то используется иначе Функция определена в пункте 4. Где ROTL — циклический сдвиг битов влево, ROTR — циклический сдвиг битов вправо.
Внутри этой функции преобразования количество раундов распределяется динамически. Они рассчитываются по формуле:
= количество '1' в блоке сообщения(512 битовом) количество '0' в ключе (512 битовом) .
Анализ безопасности Наиболее распространенное правило 30, демонстрирующее желаемое поведение, необходимое в криптографических примитивах неспособно обеспечить полный лавинный эффект и случайность. Для улучшения этих параметров применяется объединение других нелинейных правил клеточного автомата с правилом 30. Гибридные правила демонстрируют желательный строгий лавинный критерий для очень большого числа итерации. Введение функции трансформации с комбинацией правил клеточного автомата достигает полного лавинного эффекта за небольшое число итераций и проходит все статистические тесты, распространяемые Национальным институтом Стандартов и технологий.
Примечания
Категория:Криптография