Критерии при разработке алгоритмов

считается, что алгоритм симметричного шифрования должен:

· Манипулировать данными в больших блоках, предпочтительно размером 16 или 32 бита.

· Иметь размер блока 64 или 128 бит.

· Иметь масштабируемый ключ до 256 бит.

· Использовать простые операции, которые эффективны на микропроцессорах (XOR, +, табличные подстановки, * по модулю. Не должно использоваться сдвигов переменной длины, побитных перестановок или условных переходов.

· возможность реализации алгоритма на 8-битном процессоре с минимальными требованиями к памяти.

· Использовать заранее вычисленные подключи. Всегда должна быть возможность шифрования данных без каких-либо предварительных вычислений.

· Состоять из переменного числа итераций. Для приложений с маленькой длиной ключа нецелесообразно применять большое число итераций для противостояния дифференциальным и другим атакам.

· По возможности не иметь слабых ключей. (или минимальное кол-во. Тем не менее, все слабые ключи должны быть заранее известны, чтобы их можно было отбраковать в процессе создания ключа.

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

· Не иметь линейных структур, которые уменьшают комплексность и не обеспечивают исчерпывающий поиск.

· Использовать простую для понимания разработку. Это дает возможность анализа и уменьшает закрытость алгоритма.

Большинство блочных алгоритмов основано на использовании сети Фейштеля, все имеют плоское пространство ключей, с возможным исключением нескольких слабых ключей.

Сеть Фейштеля

Сеть Фейштеля - метод обратимых преобразований текста, при котором значение, вычисленное от одной из частей текста, накладывается на другие части. Часто структура сети выполняется таким образом, что для шифрования и дешифрования используется один и тот же алгоритм – различие состоит только в порядке использования материала ключа.

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

Классическая сеть Фейштеля имеет следующую структуру:

Рис.1.

Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их две. Величины V_i именуются параметрами сети, обычно это функции от материала ключа. Функция F называется образующей. Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Фейштеля. Оптимальное число раундов K – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптоскойстость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля – ведь при обнаружении, скажем, какого-либо слабого места в алгоритме, почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, а лишь указываются разумные пределы (обязательно нижний, и не всегда – верхний) этого параметра.

Сразу же возникает вопрос, – является ли данная схема обратимой? Очевидно, да. Сеть Фейштеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Фейштеля не нужно вычислять функцию F^-1.

Более того, как нетрудно заметить, сеть Фейштеля симметрична.

Алгоритм DES

Принципы разработки

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).

DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP^-1 результата, полученного на третьем этапе. Перестановка IP^-1 инверсна начальной перестановке.

Рис. 2.4. Общая схема DES

Справа на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ K_i является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи K_i для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

Алгоритм IDEA

IDEA (International Data Encryption Algorithm) является блочным симметричным алгоритмом шифрования, является одним из нескольких симметричных криптографических алгоритмов, которыми первоначально предполагалось заменить DES.

Сюдзя Лай (Xuejia Lai) и Джеймс Массей (James Massey) из швейцарского федерального института технологий. Первоначальная версия была опубликована в 1990 году. Пересмотренная версия алгоритма, усиленная средствами защиты от дифференциальных криптографических атак, была представлена в 1991 году и подробно описана в 1992 году.

Принципы разработкиIDEA является блочным алгоритмом, который использует 128-битовый ключ для шифрования данных блоками по 64 бита.Целью разработки IDEA было создание относительно стойкого криптографического алгоритма с достаточно простой реализацией. Следующие характеристики IDEA характеризуют его криптографическую стойкость:

1. Длина блока: длина блока должна быть достаточной, чтобы скрыть все статистические характеристики исходного сообщения. С другой стороны, сложность реализации криптографической функции возрастает экспоненциально в соответствии с размером блока. Использование блока размером в 64 бита в 90-е годы означало достаточную силу. Более того, использование режима шифрования СВС говорит о дальнейшем усилении этого аспекта алгоритма.

2. Длина ключа: длина ключа должна быть достаточно большой для того, чтобы предотвратить возможность простого перебора ключа. При длине ключа 128 бит IDEA считается достаточно безопасным.

3. Конфузия: зашифрованный текст должен зависеть от ключа сложным и запутанным способом.

4. Диффузия: каждый бит незашифрованного текста должен влиять на каждый бит зашифрованного текста. IDEA с этой точки зрения является очень эффективным алгоритмом.

В IDEA два последних пункта выполняются с помощью трех операций. Это отличает его от DES, где все постороено на использовании операции XOR и маленьких нелинейных S-boxes.

1. Побитовое XOR, обозначаемое как .

2. Сумма целых по модулю 2¹⁶ (по модулю 65536), при этом входы и выходы трактуются как беззнаковые 16-битные целые. Эту операцию обозначим как +.

3. Умножение целых по модулю 2¹⁶ + 1 (по модулю 65537), при этом входы и выходы трактуются как беззнаковые 16-битные целые, за исключением того, что блок из одних нулей трактуется как 2¹⁶. Эту операцию обозначим как •.

Шифрование

Рассмотрим общую схему шифрования IDEA. Как и в любом алгоритме шифрования, здесь существует два входа: незашифрованный блок и ключ. В данном случае незашифрованный блок имеет длину 64 бита, ключ имеет длину 128 бит.

Алгоритм IDEA состоит из восьми раундов, за которыми следует заключительное преобразование. Алгоритм разделяет блок на четыре 16-битных подблока. Каждый раунд получает на входе четыре 16-битных подблока и создает четыре 16-битных выходных подблока. Заключительное преобразование также получает на входе четыре 16-битных подблока и создает четыре 16-битных подблока. Каждый раунд использует шесть 16-битных ключей, заключительное преобразование использует четыре подключа, т.е. всего в алгоритме используется 52 подключа.

Дешифрование

Процесс дешифрования аналогичен процессу шифрования. Дешифрование состоит в использовании зашифрованного текста в качестве входа в ту же самую структуру IDEA, но с другим набором ключей. Дешифрующие ключи U₁, ..., U₅₂ получаются из шифрующих ключей следующим образом:

Алгоритм ГОСТ 28147

Алгоритм ГОСТ 28147 является отечественным стандартом для алгоритмов симметричного шифрования. ГОСТ 28147 разработан в 1989 году

- блочный алгоритм шифрования,

- длина блока равна 64 битам,

- длина ключа равна 256 битам,

- количество раундов равно 32.

- классическая сеть Фейштеля.L_i = R_i-1.R_i = L_i f (R_i-1, K_i)

- Функция F проста.

1) правая половина и i-ый подключ +ся по модулю 2³².

2) результат разбивается на восемь 4-битовых значений, каждое из которых подается на вход S-box.

ГОСТ 28147 использует восемь различных S-boxes, каждый из которых имеет 4-битовый вход и 4-битовый выход. Выходы всех S-boxes объединяются в 32-битное слово, которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью XOR результат объединяется с левой половиной, в результате чего получается новая правая половина.

Основные различия между DES и ГОСТ 28147 следующие:

DES использует гораздо более сложную процедуру создания подключей
В DES применяется 56-битный ключ, а в ГОСТ 28147 - 256-битный.
У S-boxes DES 6-битовые входы и 4-битовые выходы, а у S-boxes ГОСТ 28147 4-битовые входы и выходы. В обоих алгоритмах используется по восемь S-boxes, но размер S-box ГОСТ 28147 существенно меньше размера S-box DES.
В ГОСТ 28147 требуется 8 раундов прежде, чем изменение одного входного бита повлияет на каждый бит результата; DES для этого нужно только 5 раундов.
В DES 16 раундов, в ГОСТ 28147 - 32 раунда = более стойкий к дифференциальному и линейному криптоанализу.

Рис. I-ый раунд ГОСТ 28147

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒