Loading AI tools
Из Википедии, свободной энциклопедии
SHARK (англ. Secure Hash Algorithm Regenerative Keys — безопасный хеширующий алгоритм с воссоздающимися ключами) — симметричный алгоритм блочного шифрования, разработанный группой криптографов, среди которых Винсент Рэймен, — автор шифра AES. В теории позволяет использовать блоки и ключи различной длины, однако авторская реализация использует 128-битный ключ и 64-битные блоки. Структура схожа со структурой подстановочно-перестановочной сети.
SHARK | |
---|---|
Создатель | Винсент Рэймен, Йоан Даймен, Барт Пренель, Антун Боссэлерс и Эрик де Вин |
Создан | 1996 г. |
Опубликован | 1996 г. |
Размер ключа | 128 бит |
Размер блока | 64 бит |
Число раундов | 6[1](8[2]) |
Тип | Подстановочно-перестановочная сеть |
Шифр SHARK — первый в серии алгоритмов, разработанных в ходе исследования по созданию безопасных и эффективных алгоритмов блочного шифрования на основе метода Wide Trail design strategy[3]. Результатом исследования позже стало создание стандартного шифра AES[2].
Авторы позиционировали SHARK как алгоритм, призванный заменить широко распространенный в то время шифр DES. К новому алгоритму были предъявлены следующие требования:
Хотя до этого уже существовали шифры на основе SP-сети (MMB, SAFER, 3-Way), SHARK впервые использовал MDS-коды[4] для линейного преобразования, а именно коды Рида-Соломона[1].
Существует два варианта шифра SHARK: SHARK-A (англ. affine transform) и SHARK-E (англ. exor), получившие название благодаря различным способам введения раундовых ключей[5].
Алгоритм SHARK состоит из трех компонентов:
Каждый компонент алгоритма рассматривается отдельно и каждый должен обладать определёнными свойствами. Так, слой диффузии должен обладать равномерными и хорошими диффузионными свойствами. Нелинейный слой также должен обладать равномерными нелинейными свойствами, причем компоненты алгоритма независимы в следующем смысле: при изменении реализации, например, нелинейного слоя (одни S-блоки заменяются другими S-блоками c такими же характеристиками), защищенность алгоритма остается неизменной. Такая стратегия является вариантом Wide trail strategy[3], описанной в докторской диссертации Йоана Даймена[1].
SHARK состоит из раундов, дополнительного слоя добавления ключа и дополнительно слоя инвертированной диффузии. Каждый раунд, в свою очередь, состоит из добавления ключа, нелинейной замены и слоя диффузии. Дополнительный слой добавления ключа нужен для того, чтобы злоумышленник не смог отделить последний раунд. Дополнительный слой инвертированной диффузии необходим для упрощения операции дешифрования[1].
Слой нелинейный замены состоит из S-блоков, каждый из которых представляет собой -битную перестановку. Таким образом, алгоритм способен шифровать блоки длиной [1].
На вход слою диффузии приходят -битных чисел, которые можно рассматривать как элементы над полем . Рассматриваемый слой необходим для создания лавинного эффекта. Этот эффект проявляется в линейном и разностном контекстах:
Пусть — обратимое линейное преобразование, — элемент поля , — расстояние Хэмминга, тогда количественно лавинный эффект оценивается числом скачка (англ. branch number) [1].
Если , то . называют оптимальным числом скачка (англ. optimal branch number). В основной статье авторы показали, что с помощью MDS-кодов можно сконструировать обратимое линейное преобразование с оптимальном числом скачка. В реализации используются коды Рида-Соломона[1].
Нелинейные S-блоки обеспечивают защиту от линейного и дифференциального криптоанализов. Одним из важных численных характеристик безопасности шифра служит матрица эксклюзивных ИЛИ (англ. exor table) отображения , элементы которой определяются по формуле , где — обозначает число удовлетворяющих условию элементов, — элементы поля . Большие значения элементов матрицы могут привести к восприимчивости шифра к дифференциальной атаке[1].
Авторами были выбраны S-блоки, основанные на отображении над полем . В этом случае при четном матрица обладает следующими свойствами:
Для того чтобы удалить фиксированные точки и , используется обратимое аффинное преобразование выходных бит[1].
Расписание ключей (англ. key scheduling) позволяет расширить исходный ключ , получив раундовых ключей . Хорошее планирование позволяет получить раундовые ключи с максимальной энтропией. Авторами предлагаются два способа ввести раундовый ключ:
Вычисляется простое исключающее ИЛИ входных бит раунда и подключа. Преимущества метода — быстрота и стабильность: никакой ключ не является сильнее или слабее другого. Недостаток метода — энтропия раундового ключа не превосходит [1].
Пусть — невырожденная матрица над полем , зависящая от ключа (точнее, от его расширения). Введем ключевую операцию над входными данными следующим образом: . Это линейная операция, потому она не вводит слабых ключей. Кроме того, энтропия раундовых ключей увеличивается до . Однако, это довольно дорогая в смысле производительности операция, поэтому авторами предлагается ограничить на подпространстве диагональных матриц. В этом случае энтропия раундовых ключей становится близкой к [1].
В алгоритме SHARK, генерация раундовых ключей осуществляется следующим образом:
Механизм генерации подключей в принципе позволяет использовать ключ длины бит, но авторы рекомендуют использовать ключ, не превышающий 128 бит[1].
Для того, чтобы добиться высокой производительности, слой диффузии и блоки подстановок объединяются в одну операцию[1]. Пусть обозначают входные данные раунда; — выходные данные; — матрицы перестановок (S-блоки); — матрица, определяющая слой диффузии; и — обозначают сложение и умножение над полем . Тогда
Используя расширенные таблицы замещений размерности , определяемые по формуле , можно записать преобразование в простом виде:
Таким образом, один раунд требует поисков по таблице и бинарных операций. Однако, из-за того что при длине блока бит таблицы занимают байт, алгоритм для блоков длины 128 бит и более оказывался неэффективным для большинства процессоров того времени (1996 год), отсюда происходит существующее ограничение на длину блока в 64 бит ()[2].
Для можно построить матрицу, определяющую слой диффузии, на основе кода Рида-Соломона[2].
Для описания дешифрования рассмотрим 2-х раундовую версию SHARK[1]. Пусть — линейная операция, — нелинейная замена, — операция добавления ключа для раундового ключа . Функция шифрования, в таком случае, равна , где — комбинированная из слоя диффузии и S-блоков операция. Так как операция добавления ключа и операция диффузии — линейные операции, их порядок можно поменять местами[1]:
,
где введено обозначение
Применим полученную формулу к [1]:
Теперь покажем, что операция дешифрования имеет ту же структуру. Для этого сначала обратим операцию шифрования[1]:
Меняя местами операцию добавления ключа и операцию диффузии, получаем ту же структуру, что и в операции шифрования[1]:
На текущий момент не обнаружено уязвимостей у классической реализации алгоритма. Существуют атаки только на вариации алгоритма:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.