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

Достоинства:

· скорость (по данным Applied Cryptography -- на 3 порядка выше)

· простота реализации (за счёт более простых операций)

· меньшая требуемая длина ключа для сопоставимой стойкости

· изученность (за счёт большего возраста)

Недостатки:

· сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 -- 499500 и т. д.

· сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.

Data Encryption Standard (DES)

DES (англ. Data Encryption Standard) также известен как алгоритм шифрования данных DEA (англ. Data Encryption Algorithm). Разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FIPS-46-3). DES имеет блоки по 64 бит и 16-цикловую структуру сети Фейстеля, для шифрования использует ключ в 56 бит. ( На самом деле функция требует ввода 64-битового ключа, но в качестве ключа шифрования используется только 56 бит, остальные 8 бит могут быть битами чётности или содержать любые другие данные). Алгоритм использует комбинирование нелинейного (S-box) и линейного преобразований. Для DES рекомендовано несколько режимов шифрования, например Electronic Code Book (ECB) и Cipher Block Chaining (CBC)

Общая схема шифрования DES представлена на рисунке 2.1

Рис. 2.1 Схема шифрования DES

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

В основе алгоритма лежит цепь Фейстеля, чья цикловая (раундовая) функция f обрабатывает 32-разрядные слова (половину блока) и использует в качестве параметра 48-разрядный подключ (J). Сначала 32 входные разряда с помощью расширяющей перестановки преобразуются в 48 (некоторые разряды повторяются). Схема этого расширения показана ниже (номера соответствуют номерам бит входного 32-битового блока).

Рис. 2.2 Расширяющая перестановка

Значение на выходе ключевого сумматора получается в результате побитового сложения (исключающее ИЛИ, xor) сформированного 48-разрядного блока и текущего подключа. Результирующий 48-разрядный блок преобразуется в 32-разрядный с помощью S-блоков. Затем выполняется ещё одна битовая перестановка согласно схеме, показанной ниже (числа представляют собой порядковые номера бит).

Рис. 2.3 Битовая перестановка

Шифрование начинается с перестановки бит (IP -- Initial Permutation) в 64-разрядном блоке исходных данных. 58-ой бит становится первым, 50-ый вторым и т. д. Схема перестановки битов показана ниже.

Рис. 2.4 Схема перестановки

Полученный блок делится на две 32-разрядные части L0 и R0. Далее 16 раз повторяются следующие 4 процедуры:

1 Преобразование ключа с учетом номера итерации i (перестановки разрядов с удалением 8 бит, в результате получается 48-разрядный ключ)

2 Пусть A = Li, а J -- преобразованный ключ. С помощью функции генерируется 32-разрядное выходное значение цикловой (раундовой) функции.

3 Выполняется операция , результат обозначается Ri + 1

4 Выполняется операция присвоения Li + 1 = Ri

После выполнения 16 циклов преобразования производится ещё одна битовая перестановка, инверсная начальной. Она предполагает следующее размещение 64 бит зашифрованных данных (первым битом становится 40-ой, вторым 8-ой и т. д.)

Рис. 2.5 Битовая перестановка, инверсная начальной

S-блоки представляют собой таблицы, содержащие 4 строки и 16 столбцов. Первый S-блок S1 представлен ниже.

Рис. 2.6 Первый S-блок

Входной 48-разрядный блок делится на 8 групп по 6 разрядов. Первый и последний разряд в группе используются в качестве адреса строки, а средние 4 разряда -- в качестве адреса столбца. В результате, каждые 6 бит преобразуются в 4 бита, а весь 48-разрядный код в 32-разрядный (для этого нужно 8 S-блоков). Существуют аппаратные реализации стандарта DES, обеспечивающие высокую производительность.

Из-за малой длины ключа (56 бит), имеется всего 256 различных ключей, что при нынешнем развитии техники недопустимо по причине низкого времени взлома атакой типа Brute Force (всего несколько часов). Также вызывает сомнение его надежность, так как в основе алгоритма DES лежат 8 таблиц подстановки (S-boxes), применяемые в каждом раунде.

На сегодняшний день такая длина ключа недостаточна, поскольку допускает успешное применение атак типа Brute Force. Альтернативой DES можно считать тройной DES. Существует опасность, что эти S-boxes конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-boxes. В течение многих лет обсуждалось как стандартное, так и неожиданное поведение S-boxes, но все-таки никому не удалось обнаружить их фатально слабые места.

Всё это привело к тому, что в У. Тачмен предложил идею шифровать блок открытого текста P три раза с помощью двух ключей K1 и K2

С=ЕK1(DK2(EK2(P))) (2.2)

То есть блок открытого текста Р сначала шифруется ключом K1, затем расшифровается ключом K2 и окончательно шифруется ключом K1. [1]

Это позволило вывести стойкость алгоритма на современный уровень.

Advanced Encryption Standard (AES)(Rijndael)

Advanced Encryption Standard (AES), также известный, как Rijndael симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), финалист конкурса AES, принятый в качестве американского стандарта шифрования правительством США. Выбор был сделан с расчётом на повсеместное использование и активный анализ алгоритма, как это было с его предшественником, DES. Государственный институт стандартов и технологий (англ. National Institute of Standards and Technology, NIST) США опубликовал предварительную спецификацию AES 26 ноября 2001 года, после пятилетней подготовки. 26 мая 2002 года AES был объявлен стандартом шифрования. По состоянию на 2006 год AES является одним из самых распространённых алгоритмов симметричного шифрования.

Этот алгоритм представляет собой симметричный блочный шифр, который работает с блоками данных длиной 128 бит и использует ключи длиной 128, 192 и 256 бит (версии AES-28; AES-192 и AES-256). Сам алгоритм может работать и с другими длинами блоков данных и ключей, но эта возможность в стандарт не вошла.

Состояние можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов обозначено как Nb и равно длине блока, деленной на 32.

Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов обозначено как Nk и равно длине ключа, деленной на 32. Это показано на рисунке 1.

В некоторых случаях ключ шифрования показан как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива).

Рис. 2.7 Пример представления состояния (Nb=6) и ключа шифрования (Nk=4)

Входные данные для шифра ( "открытый текст", если используется режим шифрования ECB) обозначаются как байты состояния в порядке a0,0, a1,0, a3,0, a0,1, a1,1, a3,1 ,a4,1 ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число циклов обозначено как Nr и зависит от значений Nb и Nk. Оно приведено в Таблице 2.1.

Таблица № 2.1 Число циклов (Nr) как функция от длины ключа и длины блока

Цикловое преобразование состоит из четырех различных преобразований. На псевдо-Си это выглядит следующим образом:

Round (State, RoundKey)

{

ByteSub(State); // замена байт

ShiftRow(State); // сдвиг строк

MixColumn(State); // замешивание столбцов

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

Последний цикл шифра немного отличается. Он выглядит так:

FinalRound(State, RoundKey)

{

ByteSub(State); // замена байт

ShiftRow(State); // сдвиг строк

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

В приведенной записи, "функции" - Round, ByteSub и т.д. выполняют свои действия над массивами, переданными указателями (State, RoundKey).

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

Преобразование ByteSub представляет собой нелинейную замену байт, выполняемую независимо с каждым байтом состояния. Таблицы замены (или S-блоки) являются инвертируемыми и построены из композиции двух преобразований:

1. Первое - получение обратного элемента относительно умножения в поле GF(28), описанного в разделе 2.1. '00' переходит сам в себя.

2. Применение афинного преобразования (над GF(2)), определенного как:

Таблица 2.2 Схема аффинного преобразования

Применение описанного S-блока ко всем байтам состояния обозначено как ByteSub(State). Рисунок 2.8 иллюстрирует применение преобразования ByteSub к состоянию.

Рис 2.8 ByteSub действует на каждый байт состояния

Преобразование сдвига строк (ShiftRow).

Последние 3 строки состояния циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт.

Значения сдвигов С1, С2 и С3 зависят от длины блока Nb. Их величины приведены в таблице 2.3.

Таблица 2.3 Величина сдвига для разной длины блоков

Операция сдвига последних 3 строк состояния на определенную величину обозначена как ShiftRow(State). Рисунок 2.9 показывает влияние преобразования на состояние.

Рис 2.9: ShiftRow действует на строки состояния.

Преобразование замешивания столбцов (MixColumn).

В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю x4+1 на многочлен c(x), выглядящий следующим образом:

c(x)='03' x3 + '01' x2 + '01' x + '02' (2.3)

Это может быть представлено в виде матричного умножения. Пусть b(x)=c(x)a(x),

Таблица 2.4

Применение этой операции ко всем четырем столбцам состояния обозначено как MixColumn(State). Рисунок 2.10 демонстрирует применение MixColumn к состоянию.

Рис 2.10 MixColumn действует на столбцы состояния

Добавление циклового ключа.

В данной операции цикловой ключ добавляется к состоянию посредством простого EXOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Длина циклового ключа равна длине блока Nb.

Преобразование, содержащее добавление посредством EXOR циклового ключа к состоянию, обозначено как AddRoundKey(State, RoundKey). Оно проиллюстрировано на рисунке 2.11.

Рис 2.11 При добавлении ключа цикловой ключ складывается посредством EXOR с состоянием.

Алгоритм выработки ключей (Key Schedule).

Цикловые ключи получаются из ключа шифрования посредством алгоритма выработки ключей. Он содержит два компонента: расширение ключа (Key Expansion) и выбор циклового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом:

· Общее число бит цикловых ключей равно длине блока, умноженной на число циклов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа).

· Ключ шифрования расширяется в Расширенный Ключ (Expanded Key).

· Цикловые ключи берутся из Расширенного ключа следующим образом: первый цикловой ключ содержит первые Nb слов, второй - следующие Nb слов и т.д.

Расширение ключа (Key Expansion).

Расширенный ключ представляет собой линейный массив 4-ех байтовых слов и обозначен как W[Nb*(Nr+1)]. Первые Nk слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Nk: ниже приведена версия для Nk равного или меньшего 6 и версия для Nk большего 6.Для Nk<6 или Nk=6 мы имеем:

KeyExpansion(CipherKey,W

{

for (i = 0; i < Nk; i++) W[i] = CipherKey[i];

for (j = Nk; j < Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte( Rotl( W[j-1] ) ) ^ Rcon[j/Nk];

for (i = 1; i < Nk && i+j < Nb*(Nr+1); i++)

}

}

Как можно заметить, первые Nk слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством EXOR предыдущего слова W[i-1] и слова на Nk позиций ранее W[i-Nk]. Для слов, позиция которых кратна Nk, перед EXOR применяется преобразование к W[i-1], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначенный как Rotl, затем следует SubByte - применение замены байт. Для Nk>6 мы имеем:

KeyExpansion(CipherKey,W)

{

for (i=0; i<Nk; i++) W[i]=CipherKey[i];

for (j=Nk; j<Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte(Rotl(W[j-1])) ^ Rcon[j/Nk];

for (i=1; i<4; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

W[j+4] = W[j+4-Nk] ^ SubByte(W[j+3]);

for (i=5; i<Nk; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}

Отличие для схемы при Nk>6 состоит в применении SubByte для каждого 4-го байта из Nk. Цикловая константа независит от Nk и определяется следующим образом:

Rcon[i] = ( RC[i], '00' , '00' , '00' ) (2.4)

где: RC[0]='01'

RC[i]=xtime(Rcon[i-1])

Выбор циклового ключа.

i-ый цикловой ключ получается из слов массива циклового ключа от W[Nb*i] и доW[Nb(i+1)]. Это показано на рисунке 2.12.

Рис 2.12: Расширение ключа и выбор циклового ключа для Nb=6 и Nk=4.

Замечание: Алгоритм выработки ключей можно осуществлять и без использования массива W[Nb*(Nr+1)]. Для реализаций, в которых существенно требование к занимаемой памяти, цикловые ключи могут вычисляться на лету посредством использования буфера из Nk слов.

Шифр Rijndael состоит из:

· начального добавления циклового ключа;

· Nr-1 циклов;

· заключительного цикла.

На псевдо-Си это выглядит следующим образом:

Rijndael (State, CipherKey)

{

KeyExpansion(CipherKey, ExpandedKey); // Расширение ключа

AddRoundKey(State, ExpandedKey); // Добавление циклового ключа

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i); // циклы

FinalRound(State, ExpandedKey+Nb*Nr); // заключительный цикл

}

Если предварительно выполнена процедура расширения ключа, то Rijndael будет выглядеть следующим образом:

Rijndael (State, CipherKey)

{

AddRoundKey(State, ExpandedKey);

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i);

FinalRound(State, ExpandedKey+Nb*Nr);

}

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

Blowfish

Алгоритм был разработан в 1993 году Брюсом Шнайером (Bruce Schneier). Этот алгоритм, по заявлению автора, разрабатывался как быстрый, компактный и простой алгоритм с настраиваемой стойкостью (ключ до 448 бит).

Blowfish является сетью Фейштеля, у которой количество итераций равно 16. Длина блока равна 64 битам, ключ может иметь любую длину в пределах 448 бит. Хотя перед началом любого шифрования выполняется сложная фаза инициализации, само шифрование данных выполняется достаточно быстро.

Алгоритм состоит из двух частей: расширение ключа и шифрование данных. Расширение ключа преобразует ключ длиной, по крайней мере, 448 бит в несколько массивов подключей общей длиной 4168 байт.

В основе алгоритма лежит сеть Фейштеля с 16 итерациями. Каждая итерация состоит из перестановки, зависящей от ключа, и подстановки, зависящей от ключа и данных. Операциями являются XOR и сложение 32-битных слов.

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

1. Р - массив, состоящий из восемнадцати 32-битных подключей: Р1, Р2, ..., Р18.

2. Четыре 32-битных S-boxes c 256 входами каждый. Первый индекс означает номер S-box, второй индекс - номер входа.

3. S1,0, S1,1, … S1,255;

4. S2,0, S2,1, … S2,255;

5. S3,0, S3,1, … S3,255;

6. S4,0, S4,1, … S4,255;

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

Входом является 64-битный элемент данных X, который делится на две 32-битные половины, X1 и Xr.

Xl = Xl XOR Pi (2.5)

Xr = F (Xl) XOR Xr (2.6)

Swap Xl and Xr

Разделить Xl на четыре 8-битных элемента A, B, C, D.

F (Xl) = ((S1,А + S2,B mod 232) XOR S3,C) + S4,D mod 232

Дешифрование отличается от шифрования тем, что Pi используются в обратном порядке.

Генерация подключей: Подключи вычисляются с использованием самого алгоритма Blowfish. Для этого следует:

1 Инициализировать первый Р-массив и четыре S-boxes фиксированной строкой.

2 Выполнить операцию XOR P1 с первыми 32 битами ключа, операцию XOR P2 со вторыми 32 битами ключа и т.д. Повторять цикл до тех пор, пока весь Р-массив не будет побитно сложен со всеми битами ключа. Для коротких ключей выполняется конкатенация ключа с самим собой.

3 Зашифровать нулевую строку алгоритмом Blowfish, используя подключи, описанные в пунктах (1) и (2).

4 Заменить Р1 и Р2 выходом, полученным на шаге (3).

5 Зашифровать выход шага (3), используя алгоритм Blowfish с модифицированными подключами.

6 Заменить Р3 и Р4 выходом, полученным на шаге (5).

7 Продолжить процесс, заменяя все элементы Р-массива, а затем все четыре S-boxes, выходами соответствующим образом модифицированного алгоритма Blowfish.

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

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

RC5

Алгоритм RC5 интересен по многим причинам. Во-первых, он создан известнейшим криптологом Роном Ривестом (Ron Rivest) - одним из разработчиков асимметричной системы RSA и одним из основателей одноименной фирмы (RSA Data Security), которая, несомненно, входит в число мировых лидеров рынка средств криптографической защиты информации. Аббревиатура RC обозначает, согласно разным источникам, либо Rivest Cipher, либо Ron's Code, т. е. в совокупности "шифр Рона Ривеста".

Во-вторых, аналогично предыдущим алгоритмам шифрования Рона Ривеста RC2 и RC4, алгоритм RC5 получил весьма широкое распространение: по количеству пользователей в мире он стоит в одном ряду с такими известными алгоритмами, как IDEA и Blowfish.

И, наконец, на преобразованиях, используемых в RC5, основана последующая разработка компании RSA - алгоритм RC6, который стал финалистом конкурса AES по выбору нового стандарта шифрования США. RC6 не победил в конкурсе, но, видимо, превзойдет своего предшественника по широте использования.

Алгоритм RC5 имеет переменные длину блока, количество раундов и длину ключа. Для спецификации алгоритма с конкретными параметрами принято обозначение RC5-W/R/K, где W равно половине длины блока в битах, R -- число раундов, K -- длина ключа в байтах.

Для эффективной реализации величину W рекомендуют брать равной машинному слову. Например, для 32-битных платформ оптимальным будет выбор W=32, что соответствует размеру блока 64 бита.

Для стимуляции изучения и применения шифра RC5 RSA Security Inc. 28 января 1997 года предложила взломать серию сообщений, зашифрованных алгоритмом RC5 с разными параметрами, назначив за взлом каждого сообщения приз в $10000. Шифр с самыми слабыми параметрами RC5-32/12/5 был взломан в течение нескольких часов. Тем не менее, последний осуществлённый взлом шифра RC5-32/12/8 потребовал 5 лет. Взлом RC5-32/12/8 был осуществлён в рамках проекта распределённых вычислений RC5-64 (здесь 64=K*8, длина ключа в битах) под руководством distributed.net. По-прежнему неприступными пока остаются RC5-32/12/K для K=9..16. distributed.net стартовала проект RC5-72 для взлома RC5-32/12/9.

Как пишет автор алгоритма, "RC5 - это несколько различных алгоритмов", поскольку, помимо секретного ключа, в число параметров алгоритма входят следующие:

· размер слова w - RC5 шифрует блоками по два слова, допустимы значения w 16, 32 или 64, причем рекомендуется значение 32;

· количество раундов алгоритма R - в качестве значения допустимо любое целое число от 0 до 255 включительно;

· размер секретного ключа в байтах b - любое целое значение от 0 до 255 включительно.

По мнению автора алгоритма, переменные параметры расширяют сферу использования алгоритма, а также сильно сокращают издержки, если необходим переход на более сильный вариант алгоритма - в отличие от DES (основная проблема которого - короткий 56-битный ключ), в программной или аппаратной реализации RC5, поддерживающей переменные параметры, легко было бы заменить ключ более длинным, таким образом устранив проблему. Вот что пишет об этом Рон Ривест: "Фиксированные параметры могут быть не менее опасны [переменных], поскольку их нельзя улучшить при необходимости. Рассмотрим проблему DES: его ключ слишком короток, и нет простого способа увеличить его".