Рассмотрим общую схему симметричной, или традиционной, криптографии.
(рис 1.1) Общая схема симметричного шифрования
Процесс шифрования состоит в использовании определенного алго-ритма, на вход которому подаются исходное незашифрованное сообщение, называемое также plaintext, и ключ. Выходом алгоритма является зашифрованное сообщение, называемое также ciphertext. Ключ является значени-ем, не зависящим от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения.
Зашифрованное сообщение передается получателю. Получатель преобразует зашифрованное сообщение в исходное незашифрованное сообщение с помощью алгоритма расшифрования и того же самого ключа, который использовался при шифровании.
Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова chiphertext.
Безопасность, обеспечиваемая традиционной криптографией, зависит от нескольких факторов.
Во-первых, криптографический алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы его анализа.
Во-вторых, безопасность передаваемого сообщения должна зависеть от секретности ключа, но не от секретности алгоритма. Алгоритм должен быть проанализирован специалистами, чтобы исключить наличие слабых мест, при которых плохо скрыта взаимосвязь между незашифрованным и зашифрованным сообщениями. К тому же при выполнении этого условия производители могут создавать дешевые аппаратные чипы и свободно рас-пространяемые программы, реализующие данный алгоритм шифрования.
В-третьих, алгоритм должен быть таким, чтобы нельзя было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, неза-шифрованное сообщение), полученных при шифровании с использованием данного ключа.
Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.
Диффузия – это рассеяние статистических особенностей и закономерностей незашифрованного текста в широком диапазоне статистических особенностей и закономерностей зашифрованного текста. Это достигается тем, что каждый бит или группа битов незашифрованного сообщения влияет на значения многих битов зашифрованного сообщения или, что то же самое, любой бит зашифрованного сообщения зависит от многих битов незашифрованного сообщения.
Конфузия – это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.
Если P – это исходное сообщение и K – криптографический ключ, то зашифрованный передаваемый текст можно записать в виде
C = EK[P], где EK – алгоритм шифрования.
Получатель, используя тот же ключ, расшифровывает сообщение
P = DK[C], где DK – алгоритм расшифрования
Противник, не имея доступа к K и P, должен попытаться узнать P, K или и то, и другое.
Алгоритмы симметричного шифрования различаются способом, кото-рым обрабатывается исходное сообщение. Возможно шифрование блоками или шифрование потоком.
Блок сообщения рассматривается как неотрицательное целое число, либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки. В большинстве блочных алгоритмов симметричного шифрования используются следующие опера-ции:
S-box. Если преобразуется i бит в j бит, то говорят, что размерностьS-box ixj.Р (Permutation), при ко-тором биты сообщения переупорядочиваются.XOR или $$\bigoplus$$.Эти операции циклически повторяются в алгоритме, образуя так назы-ваемые раунды. Входом каждого раунда является выход предыдущего ра-унда и ключ, который получен по определенному алгоритму из ключа шифрования K. Ключ раунда называется подключом. Каждый алгоритм шифрования может быть представлен следующим образом:
(рис 1.2) Структура алгоритма симметричного шифрования
Необходимо, чтобы алгоритм симметричного шифрования мог приме-няться в следующих областях:
Стандартный алгоритм шифрования должен быть реализован на раз-личных платформах, которые, имеют разные характеристики.
Специальная аппаратура. Алгоритм должен эффективно реализовы-ваться на специализированной аппаратуре, предназначенной для выполне-ния шифрования / расшифрования.
Большие процессоры. Хотя в приложениях, требующих максимальной скорости, всегда используется специальная аппаратура, программные реа-лизации применяются чаще. Алгоритм должен допускать эффективную программную реализацию на 32-битных процессорах.
Процессоры среднего размера. Алгоритм должен работать на микро-контроллерах и других процессорах среднего размера.
Малые процессоры. Должна существовать возможность реализации алгоритма на смарт-картах, с учетом жестких ограничений на используемую память.
Алгоритм шифрования должен, по возможности, удовлетворять неко-торым дополнительным требованиям.
Блочный алгоритм преобразовывает n-битный блок незашифрованного сообщения в n-битный блок зашифрованного сообщения. Число блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного сообщения. Если длина блока будет маленькой, то такая перестановка плохо скрывает статистические особенности и закономерности незашифрованного сообщения. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности и закономерности исходного сообщения. В любом случае преобразование сообщения не может быть произвольным в силу того, что ключом при этом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации.
Наиболее широкое распространение получили сети Фейштеля, так как, с одной стороны, на их основе можно разработать алгоритм, удовлетворя-ющий всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, реализация такого алгоритма достаточно проста и ком-пактна.
Сеть Фейштеля имеет следующую структуру. Входной блок делится на несколько равной длины подблоков, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каж-дая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется циклически. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке:
(рис 1.3) I-ый раунд сети Фейштеля
Функция F называется образующей. Каждый раунд состоит из вычис-ления функции F для одной ветви и побитового выполнения операции XOR результата F с другой ветвью. После этого ветви меняются местами. Считается, что оптимальное число раундов должно быть от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостой-кость алгоритма. Возможно эта особенность и повлияла на столь активное распространение сети Фейштеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алго-ритм. В последнее время количество раундов не фиксируется, а лишь указываются допустимые пределы.
Сеть Фейштеля является обратимой даже в том случае, если функция F не является таковой, так как для расшифрования не требуется вычислять F-1. Для расшифрования используется тот же алгоритм, но на вход подается зашифрованное сообщение, и ключи используются в обратном порядке.
В настоящее время все чаще используются различные разновидности сети Фейштеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными.
Основной характеристикой алгоритма, построенного на основе сети Фейштеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, назы-ваемые забеливанием (whitening),осуществляются для того, чтобы выпол-нить начальную рандомизацию входного текста.
Процесс, при котором предпринимается попытка узнать P, K или и то, и другое, называется криптоанализом. Одной из возможных атак на алго-ритм шифрования является "лобовая атака", называемая также "атакой грубой силы" - "brute force атака". Данная атака состоит в простом переборе всех возможных ключей. Если множество ключей достаточно большое, то подобрать ключ нереально. При длине ключа n бит количество возмож-ных ключей равно2n. Таким образом, чем длиннее ключ, тем более стойким считается алгоритм для лобовой атаки.
Существуют различные типы атак, основанные на том, что противнику известно определенное количество пар незашифрованное сообщение – за-шифрованное сообщение. При анализе зашифрованного сообщения про-тивник часто применяет статистические методы анализа текста. При этом он может иметь общее представление о типе сообщения, например, англий-ский или русский текст, выполняемый файл конкретной ОС, исходный текст на некотором языке программирования и т.д. Во многих случаях криптоаналитик имеет достаточно много информации об исходном тексте. Криптоаналитик может иметь возможность перехвата одного или несколь-ких незашифрованных сообщений вместе с их зашифрованным видом. Или криптоаналитик может знать основной формат или основные характери-стики сообщения. Говорят, что криптографическая схема абсолютно безопасна, если зашифрованное сообщение не содержит никакой информации об исходном сообщении. Говорят, что криптографическая схема вычислительно безопасна, если:
Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен:
Самым распространенным и наиболее известным алгоритмом симмет-ричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).
DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (Initial Permutation - IP) 64-битного исходного сообщения, так называемое забеливание, во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.
(рис 1.4) Общая схема DES
Справа на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.
Начальная перестановка и ее инверсия определяются стандартной таблицей. Если X – это произвольные 64 бита, то Y = IP(X) – переставленные 64 бита. Если применить обратную функцию перестановки
то получится первоначальная последовательность битов.
Теперь рассмотрим последовательность преобразований, используе-мую в каждом раунде.
(рис 1.5) I-ый раунд DES
64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:
где \oplus обозначает операцию XOR.
Таким образом, выход левой половиныLi равен входу правой половины Ri-1. Выход правой половины Riявляется результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.
Рассмотрим функцию F более подробно.
Ri, которое подается на вход функции F, имеет длину 32 бита. Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет пере-становку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения
…efgh ijkl mnop…
то в результате расширения получается сообщение
…defghi hijklm lmnopq…
После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.
Подстановка состоит из восьми S-box, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Значение, стоящее на пересечении строки и столбца является 4-битным выходом. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Если значение на пересечении строки 1 и столбца 13 равно 5, то выходом S-box является 0101.
Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде каждый бит обрабатывался другим S-box.
Ключ для отдельного раунда Kiсостоит из 48 битов. Ключи Ki получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таб-лицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каж-дом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являю-щееся входом функции F(Ri-1,Ki).
Процесс расшифрования аналогичен процессу шифрования. На входе алгоритма подается зашифрованное сообщение, но ключи Ki используются в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда расшифрования будет Ri||Li.
После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 былR16||L16. Выходом этой стадии является незашифрованное сообщение.
Таким образом, вход первого раунда расшифрования равен 32-битному выходу 16-ого раунда шифрования, у которого левая и правая части записаны в обратном порядке.
Теперь мы должны показать, что выход первого раунда процесса рас-шифрования равен 32-битному входу 16-ого раунда процесса шифрования. Во-первых, рассмотрим процесс шифрования.
$$L_1_6= R_1_5$$ $$R_1_6=L_1_5\oplus F(R_1_5, K_1_6)$$При расшифровании:
$$L^d_1 = R^d_0= L_1_6 = R_1_5\\ R^d_1 = L^d_0\oplus F(R^d_0, K_1_6)\\ = R_1_6 \oplusF(R^d_0,K_1_6)\\ = (L_1_5 \oplus F(R_1_5, K_1_6))\oplus F(R_1_5, K_1_6)$$XOR имеет следующие свойства:
Таким образом, мы имеем Ld1= R15 и Rd1 = L15. Следовательно, выход первого раунда процесса расшифрования есть L15||R15, который является перестановкой входа 16-го раунда шифрования. Данное соответствие вы-полняется все 16 раундов. Мы можем описать этот процесс в общих терми-нах. Для i-ого раунда шифрующего алгоритма:
Эти равенства можно записать по-другому:
$$R_i_-_1=L_i$$ $$L_i_-_1 = R_i \oplus F(R_i_-_1, K_i) = R_i \oplus F(L_i, K_i)$$Таким образом, мы описали входы i-ого раунда как функцию выходов.
Выход последней стадии процесса расшифрования есть R0||L0. Чтобы входом IP-1 стадии было L0||R0, необходимо поменять местами левую и правую части. Но
В результате получаем незашифрованное сообщение, что и означает возможность расшифрования DES.
Так как длина ключа равна 56 битам, существует 256 возможных ключей. На сегодняшний день такая длина ключа недостаточна, поскольку допускает успешное применение лобовых атак. Альтернативой DES можно считать тройной DES, а также алгоритм Rijndael, принятый в качестве но-вого стандарта на алгоритмы симметричного шифрования.
Основой алгоритма являются восемь таблиц подстановки, или S-box, которые применяются в каждой итерации. Существует опасность, что эти S-box конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-box. В течение многих лет об-суждалось как стандартное, так и неожиданное поведение S-box, но все-таки никому не удалось обнаружить их фатально слабые места.
В настоящее время основным недостатком DES считается маленькая длина ключа, поэтому уже давно начали разрабатываться различные аль-тернативы этому алгоритму шифрования. Один из подходов состоит в том, чтобы разработать новый алгоритм. Другой подход предполагает повтор-ное применение шифрования с помощью DES с использованием нескольких ключей.
Простейший способ увеличить длину ключа состоит в повторном при-менении алгоритма DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом:
Для расшифрования требуется, чтобы два ключа применялись в обратном порядке:
$$P = D_{k1} [D_k_2[C]]$$В этом случае длина ключа равна 56 * 2= 112 бит.
Опишем атаку "встреча посередине". Она основана на следующем свойстве алгоритма.
Требуется, чтобы атакующий знал хотя бы одну пару незашифрованное сообщение и соответствующее ему зашифрованное сообщение: (Р,С). В этом случае, во-первых, он шифрует Р на всех возможных 256 значений ключей.
Этот результат запоминается в таблице, и затем таблица упорядочивается по значению Х. Затем нарушитель расшифровывает С, используя все возможные 256 значения ключа. Для каждого расшифрованного значения ищется равное ему значение в первой таблице. Если соответствующее значение найдено, то это возможные ключи.
Если известна еще одна пара (Р1,С1), полученная с использованием этих же ключей, то найденные ключи проверяются на ней.
Если известна только одна пара незашифрованное сообщение, зашиф-рованное сообщение, то может быть получено достаточно большое число потенциальных ключей. Но если противник имеет возможность перехва-тить хотя бы две пары значений (незашифрованное сообщение - зашифрованное сообщение), то сложность взлома двойного DES фактически стано-вится равной сложности взлома обычного DES, т.е. 256.
Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость атаки с известным незашифрованным текстом до 2168, которая на сегодняшний день считается выше практических возможностей. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко.
В качестве альтернативы можно использовать тройное шифрование с двумя ключами. В этом случае выполняется последовательность шифрова-ние-расшифрование-шифрование (EDE).
$$C = E_{K1} [D_{K2} [E_{K1} [P]]]$$
(рис 1.6) Шифрование тройным DES с двумя ключами
(рис 1.7) Расшифрование тройным DES с двумя ключами
Не имеет большого значения, что используется на второй стадии: шифрование или расшифрование. В случае использования расшифрования существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя K1=K2:
Тройной DES является достаточно популярной альтернативой DES и используется при управлении ключами в стандартах ANSIX9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail).
Известных криптографических атак на тройной DES не существует. Цена подбора ключа в тройном DES с двумя ключами равна 2112.
Алгоритм ГОСТ 28147 является отечественным стандартом на алго-ритмы симметричного шифрования. ГОСТ 28147 разработан в 1989 году, является блочным алгоритмом шифрования, длина блока равна 64 битам, длина ключа равна 256 битам, количество раундов равно 32. Алгоритм представляет собой классическую сеть Фейштеля.
$$L_i = R_i$$ $$R_i = L_i \oplus F(R_i_-_1, K_i)$$Функция F проста. Сначала правая половина и i-ый подключ склады-ваются по модулю 232. Затем результат разбивается на восемь 4-битовых значений, каждое из которых подается на вход S-box. ГОСТ 28147 использует восемь различных S-box, каждый из которых имеет 4-битовый вход и 4-битовый выход. Выходы всех S-box объединяются в 32-битное слово, которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью XOR результат объединяется с левой половиной, в результате чего получается новая правая половина.
(рис 1.8) I- ый раунд алгоритма ГОСТ 28147
Генерация ключей проста. 256-битный ключ разбивается на восемь 32-битных подключей. Алгоритм имеет 32 раунда, поэтому каждый подключ используется в четырех раундах по следующей схеме:
| Раунд | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Подключ | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Считается, что стойкость алгоритма ГОСТ 28147 во многом определяется структурой S-box. Долгое время структура S-box в открытой печати не публиковалась. В настоящее время известны S-box, которые используются в приложениях Центрального Банка РФ и считаются достаточно сильными. Напомню, что входом и выходом S-box являются 4-битные числа, поэтому каждый S-box может быть представлен в виде строки цифр от 0 до 15, расположенных в некотором порядке. Тогда порядковый номер цифры будет являться входным значением S-box, а сама цифра – выходным значением S-box.
| 1-ый S-box | 4 | 10 | 9 | 2 | 13 | 8 | 0 | 14 |
| 6 | 11 | 1 | 12 | 7 | 15 | 5 | 3 | |
| 2-ой S-box | 14 | 11 | 4 | 12 | 6 | 13 | 15 | 10 |
| 2 | 3 | 8 | 1 | 0 | 7 | 5 | 9 | |
| 3-ий S-box | 5 | 8 | 1 | 13 | 10 | 3 | 4 | 2 |
| 14 | 15 | 12 | 7 | 6 | 0 | 9 | 11 | |
| 4-ый S-box | 7 | 13 | 10 | 1 | 0 | 8 | 9 | 15 |
| 14 | 4 | 6 | 12 | 11 | 2 | 5 | 3 | |
| 5-ый S-box | 6 | 12 | 7 | 1 | 5 | 15 | 13 | 8 |
| 4 | 10 | 9 | 14 | 0 | 3 | 11 | 2 | |
| 6-ой S-box | 4 | 11 | 10 | 0 | 7 | 2 | 1 | 13 |
| 3 | 6 | 8 | 5 | 9 | 12 | 15 | 14 | |
| 7-ой S-box | 13 | 11 | 4 | 1 | 3 | 15 | 5 | 9 |
| 0 | 10 | 14 | 7 | 6 | 8 | 2 | 12 | |
| 8-ой S-box | 1 | 15 | 13 | 0 | 5 | 7 | 10 | 4 |
| 9 | 2 | 3 | 14 | 6 | 11 | 8 | 12 |
Основные различия между алгоритмами DES и ГОСТ 28147 следующие:
Рассмотрим общую схему симметричной, или традиционной, криптографии.
(рис 1.1) Общая схема симметричного шифрования
Процесс шифрования состоит в использовании определенного алго-ритма, на вход которому подаются исходное незашифрованное сообщение, называемое также plaintext, и ключ. Выходом алгоритма является зашифрованное сообщение, называемое также ciphertext. Ключ является значени-ем, не зависящим от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения.
Зашифрованное сообщение передается получателю. Получатель преобразует зашифрованное сообщение в исходное незашифрованное сообщение с помощью алгоритма расшифрования и того же самого ключа, который использовался при шифровании.
Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова chiphertext.
Безопасность, обеспечиваемая традиционной криптографией, зависит от нескольких факторов.
Во-первых, криптографический алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы его анализа.
Во-вторых, безопасность передаваемого сообщения должна зависеть от секретности ключа, но не от секретности алгоритма. Алгоритм должен быть проанализирован специалистами, чтобы исключить наличие слабых мест, при которых плохо скрыта взаимосвязь между незашифрованным и зашифрованным сообщениями. К тому же при выполнении этого условия производители могут создавать дешевые аппаратные чипы и свободно рас-пространяемые программы, реализующие данный алгоритм шифрования.
В-третьих, алгоритм должен быть таким, чтобы нельзя было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, неза-шифрованное сообщение), полученных при шифровании с использованием данного ключа.
Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.
Диффузия – это рассеяние статистических особенностей и закономерностей незашифрованного текста в широком диапазоне статистических особенностей и закономерностей зашифрованного текста. Это достигается тем, что каждый бит или группа битов незашифрованного сообщения влияет на значения многих битов зашифрованного сообщения или, что то же самое, любой бит зашифрованного сообщения зависит от многих битов незашифрованного сообщения.
Конфузия – это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.
Если P – это исходное сообщение и K – криптографический ключ, то зашифрованный передаваемый текст можно записать в виде
C = EK[P], где EK – алгоритм шифрования.
Получатель, используя тот же ключ, расшифровывает сообщение
P = DK[C], где DK – алгоритм расшифрования
Противник, не имея доступа к K и P, должен попытаться узнать P, K или и то, и другое.
Алгоритмы симметричного шифрования различаются способом, кото-рым обрабатывается исходное сообщение. Возможно шифрование блоками или шифрование потоком.
Блок сообщения рассматривается как неотрицательное целое число, либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки. В большинстве блочных алгоритмов симметричного шифрования используются следующие опера-ции:
S-box. Если преобразуется i бит в j бит, то говорят, что размерностьS-box ixj.Р (Permutation), при ко-тором биты сообщения переупорядочиваются.XOR или $$\bigoplus$$.Эти операции циклически повторяются в алгоритме, образуя так назы-ваемые раунды. Входом каждого раунда является выход предыдущего ра-унда и ключ, который получен по определенному алгоритму из ключа шифрования K. Ключ раунда называется подключом. Каждый алгоритм шифрования может быть представлен следующим образом:
(рис 1.2) Структура алгоритма симметричного шифрования
Необходимо, чтобы алгоритм симметричного шифрования мог приме-няться в следующих областях:
Стандартный алгоритм шифрования должен быть реализован на раз-личных платформах, которые, имеют разные характеристики.
Специальная аппаратура. Алгоритм должен эффективно реализовы-ваться на специализированной аппаратуре, предназначенной для выполне-ния шифрования / расшифрования.
Большие процессоры. Хотя в приложениях, требующих максимальной скорости, всегда используется специальная аппаратура, программные реа-лизации применяются чаще. Алгоритм должен допускать эффективную программную реализацию на 32-битных процессорах.
Процессоры среднего размера. Алгоритм должен работать на микро-контроллерах и других процессорах среднего размера.
Малые процессоры. Должна существовать возможность реализации алгоритма на смарт-картах, с учетом жестких ограничений на используемую память.
Алгоритм шифрования должен, по возможности, удовлетворять неко-торым дополнительным требованиям.
Блочный алгоритм преобразовывает n-битный блок незашифрованного сообщения в n-битный блок зашифрованного сообщения. Число блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного сообщения. Если длина блока будет маленькой, то такая перестановка плохо скрывает статистические особенности и закономерности незашифрованного сообщения. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности и закономерности исходного сообщения. В любом случае преобразование сообщения не может быть произвольным в силу того, что ключом при этом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации.
Наиболее широкое распространение получили сети Фейштеля, так как, с одной стороны, на их основе можно разработать алгоритм, удовлетворя-ющий всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, реализация такого алгоритма достаточно проста и ком-пактна.
Сеть Фейштеля имеет следующую структуру. Входной блок делится на несколько равной длины подблоков, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каж-дая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется циклически. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке:
(рис 1.3) I-ый раунд сети Фейштеля
Функция F называется образующей. Каждый раунд состоит из вычис-ления функции F для одной ветви и побитового выполнения операции XOR результата F с другой ветвью. После этого ветви меняются местами. Считается, что оптимальное число раундов должно быть от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостой-кость алгоритма. Возможно эта особенность и повлияла на столь активное распространение сети Фейштеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алго-ритм. В последнее время количество раундов не фиксируется, а лишь указываются допустимые пределы.
Сеть Фейштеля является обратимой даже в том случае, если функция F не является таковой, так как для расшифрования не требуется вычислять F-1. Для расшифрования используется тот же алгоритм, но на вход подается зашифрованное сообщение, и ключи используются в обратном порядке.
В настоящее время все чаще используются различные разновидности сети Фейштеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными.
Основной характеристикой алгоритма, построенного на основе сети Фейштеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, назы-ваемые забеливанием (whitening),осуществляются для того, чтобы выпол-нить начальную рандомизацию входного текста.
Процесс, при котором предпринимается попытка узнать P, K или и то, и другое, называется криптоанализом. Одной из возможных атак на алго-ритм шифрования является "лобовая атака", называемая также "атакой грубой силы" - "brute force атака". Данная атака состоит в простом переборе всех возможных ключей. Если множество ключей достаточно большое, то подобрать ключ нереально. При длине ключа n бит количество возмож-ных ключей равно2n. Таким образом, чем длиннее ключ, тем более стойким считается алгоритм для лобовой атаки.
Существуют различные типы атак, основанные на том, что противнику известно определенное количество пар незашифрованное сообщение – за-шифрованное сообщение. При анализе зашифрованного сообщения про-тивник часто применяет статистические методы анализа текста. При этом он может иметь общее представление о типе сообщения, например, англий-ский или русский текст, выполняемый файл конкретной ОС, исходный текст на некотором языке программирования и т.д. Во многих случаях криптоаналитик имеет достаточно много информации об исходном тексте. Криптоаналитик может иметь возможность перехвата одного или несколь-ких незашифрованных сообщений вместе с их зашифрованным видом. Или криптоаналитик может знать основной формат или основные характери-стики сообщения. Говорят, что криптографическая схема абсолютно безопасна, если зашифрованное сообщение не содержит никакой информации об исходном сообщении. Говорят, что криптографическая схема вычислительно безопасна, если:
Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен:
Самым распространенным и наиболее известным алгоритмом симмет-ричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).
DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (Initial Permutation - IP) 64-битного исходного сообщения, так называемое забеливание, во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.
(рис 1.4) Общая схема DES
Справа на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.
Начальная перестановка и ее инверсия определяются стандартной таблицей. Если X – это произвольные 64 бита, то Y = IP(X) – переставленные 64 бита. Если применить обратную функцию перестановки
то получится первоначальная последовательность битов.
Теперь рассмотрим последовательность преобразований, используе-мую в каждом раунде.
(рис 1.5) I-ый раунд DES
64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:
где \oplus обозначает операцию XOR.
Таким образом, выход левой половиныLi равен входу правой половины Ri-1. Выход правой половины Riявляется результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.
Рассмотрим функцию F более подробно.
Ri, которое подается на вход функции F, имеет длину 32 бита. Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет пере-становку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения
…efgh ijkl mnop…
то в результате расширения получается сообщение
…defghi hijklm lmnopq…
После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.
Подстановка состоит из восьми S-box, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Значение, стоящее на пересечении строки и столбца является 4-битным выходом. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Если значение на пересечении строки 1 и столбца 13 равно 5, то выходом S-box является 0101.
Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде каждый бит обрабатывался другим S-box.
Ключ для отдельного раунда Kiсостоит из 48 битов. Ключи Ki получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таб-лицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каж-дом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являю-щееся входом функции F(Ri-1,Ki).
Процесс расшифрования аналогичен процессу шифрования. На входе алгоритма подается зашифрованное сообщение, но ключи Ki используются в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда расшифрования будет Ri||Li.
После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 былR16||L16. Выходом этой стадии является незашифрованное сообщение.
Таким образом, вход первого раунда расшифрования равен 32-битному выходу 16-ого раунда шифрования, у которого левая и правая части записаны в обратном порядке.
Теперь мы должны показать, что выход первого раунда процесса рас-шифрования равен 32-битному входу 16-ого раунда процесса шифрования. Во-первых, рассмотрим процесс шифрования.
$$L_1_6= R_1_5$$ $$R_1_6=L_1_5\oplus F(R_1_5, K_1_6)$$При расшифровании:
$$L^d_1 = R^d_0= L_1_6 = R_1_5\\ R^d_1 = L^d_0\oplus F(R^d_0, K_1_6)\\ = R_1_6 \oplusF(R^d_0,K_1_6)\\ = (L_1_5 \oplus F(R_1_5, K_1_6))\oplus F(R_1_5, K_1_6)$$XOR имеет следующие свойства:
Таким образом, мы имеем Ld1= R15 и Rd1 = L15. Следовательно, выход первого раунда процесса расшифрования есть L15||R15, который является перестановкой входа 16-го раунда шифрования. Данное соответствие вы-полняется все 16 раундов. Мы можем описать этот процесс в общих терми-нах. Для i-ого раунда шифрующего алгоритма:
Эти равенства можно записать по-другому:
$$R_i_-_1=L_i$$ $$L_i_-_1 = R_i \oplus F(R_i_-_1, K_i) = R_i \oplus F(L_i, K_i)$$Таким образом, мы описали входы i-ого раунда как функцию выходов.
Выход последней стадии процесса расшифрования есть R0||L0. Чтобы входом IP-1 стадии было L0||R0, необходимо поменять местами левую и правую части. Но
В результате получаем незашифрованное сообщение, что и означает возможность расшифрования DES.
Так как длина ключа равна 56 битам, существует 256 возможных ключей. На сегодняшний день такая длина ключа недостаточна, поскольку допускает успешное применение лобовых атак. Альтернативой DES можно считать тройной DES, а также алгоритм Rijndael, принятый в качестве но-вого стандарта на алгоритмы симметричного шифрования.
Основой алгоритма являются восемь таблиц подстановки, или S-box, которые применяются в каждой итерации. Существует опасность, что эти S-box конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-box. В течение многих лет об-суждалось как стандартное, так и неожиданное поведение S-box, но все-таки никому не удалось обнаружить их фатально слабые места.
В настоящее время основным недостатком DES считается маленькая длина ключа, поэтому уже давно начали разрабатываться различные аль-тернативы этому алгоритму шифрования. Один из подходов состоит в том, чтобы разработать новый алгоритм. Другой подход предполагает повтор-ное применение шифрования с помощью DES с использованием нескольких ключей.
Простейший способ увеличить длину ключа состоит в повторном при-менении алгоритма DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом:
Для расшифрования требуется, чтобы два ключа применялись в обратном порядке:
$$P = D_{k1} [D_k_2[C]]$$В этом случае длина ключа равна 56 * 2= 112 бит.
Опишем атаку "встреча посередине". Она основана на следующем свойстве алгоритма.
Требуется, чтобы атакующий знал хотя бы одну пару незашифрованное сообщение и соответствующее ему зашифрованное сообщение: (Р,С). В этом случае, во-первых, он шифрует Р на всех возможных 256 значений ключей.
Этот результат запоминается в таблице, и затем таблица упорядочивается по значению Х. Затем нарушитель расшифровывает С, используя все возможные 256 значения ключа. Для каждого расшифрованного значения ищется равное ему значение в первой таблице. Если соответствующее значение найдено, то это возможные ключи.
Если известна еще одна пара (Р1,С1), полученная с использованием этих же ключей, то найденные ключи проверяются на ней.
Если известна только одна пара незашифрованное сообщение, зашиф-рованное сообщение, то может быть получено достаточно большое число потенциальных ключей. Но если противник имеет возможность перехва-тить хотя бы две пары значений (незашифрованное сообщение - зашифрованное сообщение), то сложность взлома двойного DES фактически стано-вится равной сложности взлома обычного DES, т.е. 256.
Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость атаки с известным незашифрованным текстом до 2168, которая на сегодняшний день считается выше практических возможностей. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко.
В качестве альтернативы можно использовать тройное шифрование с двумя ключами. В этом случае выполняется последовательность шифрова-ние-расшифрование-шифрование (EDE).
$$C = E_{K1} [D_{K2} [E_{K1} [P]]]$$(рис 1.6) Шифрование тройным DES с двумя ключами
(рис 1.7) Расшифрование тройным DES с двумя ключами
Не имеет большого значения, что используется на второй стадии: шифрование или расшифрование. В случае использования расшифрования существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя K1=K2:
Тройной DES является достаточно популярной альтернативой DES и используется при управлении ключами в стандартах ANSIX9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail).
Известных криптографических атак на тройной DES не существует. Цена подбора ключа в тройном DES с двумя ключами равна 2112.
Алгоритм ГОСТ 28147 является отечественным стандартом на алго-ритмы симметричного шифрования. ГОСТ 28147 разработан в 1989 году, является блочным алгоритмом шифрования, длина блока равна 64 битам, длина ключа равна 256 битам, количество раундов равно 32. Алгоритм представляет собой классическую сеть Фейштеля.
$$L_i = R_i$$ $$R_i = L_i \oplus F(R_i_-_1, K_i)$$Функция F проста. Сначала правая половина и i-ый подключ склады-ваются по модулю 232. Затем результат разбивается на восемь 4-битовых значений, каждое из которых подается на вход S-box. ГОСТ 28147 использует восемь различных S-box, каждый из которых имеет 4-битовый вход и 4-битовый выход. Выходы всех S-box объединяются в 32-битное слово, которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью XOR результат объединяется с левой половиной, в результате чего получается новая правая половина.
(рис 1.8) I- ый раунд алгоритма ГОСТ 28147
Генерация ключей проста. 256-битный ключ разбивается на восемь 32-битных подключей. Алгоритм имеет 32 раунда, поэтому каждый подключ используется в четырех раундах по следующей схеме:
| Раунд | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Подключ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Раунд | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Подключ | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Считается, что стойкость алгоритма ГОСТ 28147 во многом определяется структурой S-box. Долгое время структура S-box в открытой печати не публиковалась. В настоящее время известны S-box, которые используются в приложениях Центрального Банка РФ и считаются достаточно сильными. Напомню, что входом и выходом S-box являются 4-битные числа, поэтому каждый S-box может быть представлен в виде строки цифр от 0 до 15, расположенных в некотором порядке. Тогда порядковый номер цифры будет являться входным значением S-box, а сама цифра – выходным значением S-box.
| 1-ый S-box | 4 | 10 | 9 | 2 | 13 | 8 | 0 | 14 |
| 6 | 11 | 1 | 12 | 7 | 15 | 5 | 3 | |
| 2-ой S-box | 14 | 11 | 4 | 12 | 6 | 13 | 15 | 10 |
| 2 | 3 | 8 | 1 | 0 | 7 | 5 | 9 | |
| 3-ий S-box | 5 | 8 | 1 | 13 | 10 | 3 | 4 | 2 |
| 14 | 15 | 12 | 7 | 6 | 0 | 9 | 11 | |
| 4-ый S-box | 7 | 13 | 10 | 1 | 0 | 8 | 9 | 15 |
| 14 | 4 | 6 | 12 | 11 | 2 | 5 | 3 | |
| 5-ый S-box | 6 | 12 | 7 | 1 | 5 | 15 | 13 | 8 |
| 4 | 10 | 9 | 14 | 0 | 3 | 11 | 2 | |
| 6-ой S-box | 4 | 11 | 10 | 0 | 7 | 2 | 1 | 13 |
| 3 | 6 | 8 | 5 | 9 | 12 | 15 | 14 | |
| 7-ой S-box | 13 | 11 | 4 | 1 | 3 | 15 | 5 | 9 |
| 0 | 10 | 14 | 7 | 6 | 8 | 2 | 12 | |
| 8-ой S-box | 1 | 15 | 13 | 0 | 5 | 7 | 10 | 4 |
| 9 | 2 | 3 | 14 | 6 | 11 | 8 | 12 |
Основные различия между алгоритмами DES и ГОСТ 28147 следующие:
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.