Алгоритм SHA-3

Что такое хеш-функция?

В настоящее время информационная безопасность стала неотъемлемой частью любых цифровых операций. Ключевой роль в защите информации играет понятие криптографической функции. Криптографические хеш-функции — это выделенный класс хеш-функций, который имеет определённые свойства, делающие его пригодным для использования в криптографии.

Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой».

Иными словами, хеш-функция - это вычислительный метод, который может отображать неопределенный размер данных в фиксированный размер данных. Или, проще говоря, преобразование выводит числовое значение, которое характеризуется входными данными. Криптографическая хэш-функция использует необратимые (односторонние) математические функции, чтобы сгенерировать хеш-значение из входных данных. Одним из распространенных способов генерации криптографических хешей является использование блочных шифров.

К надежным с точки зрения криптографии хеш-функциям должны быть предъявлены следующие основные требования:

1. Хеш-функция должна представлять из себя одностороннюю функцию т.е. по образу (хешу) невозможно или почти невозможно найти исходный прообраз (сообщение).

2. Функция хеширования должна быть устойчива к коллизиям. Коллизия – это пара исходных сообщений, имеющая одинаковое выходное значение. Считается, что относительно быстрое нахождение коллизии в алгоритме хеширования делает подобный алгоритм ненадёжным с точки зрения криптоанализа.

Перейдем к подробному рассмотрению одного из самых безопасных и эффективных алгоритмов хеширования на сегодняшний день.

Что из себя представляет SHA-3?

SHA-3 является важным криптографическим алгоритмом для обеспечения информационной безопасности, а также целостности данных в цифровых операциях. Недавние безопасные хеш-алгоритмы, включая MD5, RIPEMD, SHA-0, SHA-1 и SHA-2 устарели и были признаны восприимчивыми к атакам различного рода.

SHA-3 (Keccak) – алгоритм хеширования переменной разрядности, разработанный группой во главе с Йоаном Дайменом в 2012 году. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Keccak был выбран в качестве официального алгоритма для SHA-3 в 2012 году. [1] Keccak основан на конструкции Sponge (Губка), которая является новым способом проектирования хеш-функций, помимо стратегии итерационного метода Меркла — Дамгора, реализуемой в MD(x).

Алгоритмы MD(x) основаны на методе вычислений в цикле с использованием простых логических операций типа OR, XOR, AND, NOT. поэтому становится возможным построение коллизий с одинаковым, заранее выбранным префиксом. Однако, как показало время алгоритмы MD(x) перестали быть безопасными из-за программ, способных находить коллизии за сравнительно небольшое время.

Губка — это итеративная конструкция для создания функции с произвольной длиной на входе и произвольной длиной на выходе на основе преобразований перестановки.

Алгоритм получения выходного значения хеш-функции с помощью алгоритма SHA-3 можно разделить на несколько этапов:

1 этап: Дополнение

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

Прежде чем приступить, нужно узнать, каков стандартный размер, которому стоит соответствовать, и для этого рассмотрим, как Keccak вычисляет размер состояния.

Для SHA-3 значение l принимается равным 6. Чем больше размер, тем выше безопасность, которую он обеспечивает. Теперь, основываясь на значении "", мы также решаем, сколько вычислительных раундов необходимо выполнить для каждой части дополненного сообщения.

Теперь мы знаем, что для SHA-3 размер состояния будет равен 1600 битам, а количество раундов вычислений - 24.

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

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

Первый и последний бит заполнения будут ‘1", а все биты между ними "0". После заполнения они делятся на " " частей, где эквивалентно длине дополненного сообщения. Математически это можно представить в следующем виде:

2 этап: Размер состояния

Сумма значений ‘ ' и ' ' всегда будет равна 1600, что продемонстрировано в таблице.

Теперь понятно, что длина дополненного сообщения точно кратна "" в зависимости от нужной длины хеша.( делится на блоков длины : )

Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается , а размер части, которая нетронута вводом / выводом, называется «емкостью» (англ. capacity) и обозначается .

Далее алгоритм можно условно разделить на две условные части: “впитывание” и “отжимание”.

3 этап: Функция впитывания

Каждый блок дополняется нулями до строки длины бит и суммируется по модулю 2 со строкой состояния аналогичной длины . Перед началом работы функции все элементы равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок к результату предыдущего шага.

Рассмотрим более подробно функции перестановок. Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2.