Который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm) , a ISO — DEA-1, за 20 лет стал мировым стандартом. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще считается криптостойким.
DES представляет собой блочный шифр, шифрующий данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом: для шифрования и дешифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени.
Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов.
Oбщий вид цикла преобразования:
Если L i и R i — левая и правая половины, полученные в результате i -й итерации, K i — 48-битный ключ для цикла i , а f — функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как:
Учитывая подстановку F i (*) и перестановку Т (*), цикл преобразования можно представить так, как это сделано на рис.
Видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями — подстановкой F i (*) и перестановкой Т (*) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).
Подстановка:
(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)
является инволюцией, так как
F i (F i (L i −1 , R i −1)) = F i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i −1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)
А подстановка
T (L i ′, R i ′) = (R i ′, L i ′),
так же является инволюцией, так как
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Если обозначить начальную и завершающую перестановки как (IP) и (IР) − 1 , то прямое DES-преобразование (шифрование) реализует функцию:
DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,
а обратное DES-преобразование (дешифрование) реализует функцию:
DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).
Таким образом, DES является шифром Фейстеля и сконструирован так, чтобы выполнялось полезное свойство: для шифрования и дешифрования используется один и тот же алгоритм. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке.
То есть если при шифровании использовались ключи K 1 , K 2 , K 3 , …, K 16 , то ключами дешифрования будут K 16 , K 15 , K 14 , …, K 1 . Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.
DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные объединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис.) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f .
Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.
Стандарт России — ГОСТ 28147-89
ГОСТ 28147-89 — это блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. В криптоалгоритме также используется дополнительный ключ, который рассматривается ниже. Для шифрования открытый текст сначала разбивается на левую и правую половины L и R . На i -м цикле используется подключ К i:
L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).
Функция f реализована следующим образом. Сначала правая половина и i -й подключ складываются по модулю 2 32 . Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 бита — во второй S-блок и т. д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10 и т. д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец, результат объединяется с помощью операции XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 , k 2 , …, k 8 . На каждом цикле используется свой подключ. Дешифрование выполняется так же, как и шифрование, но инвертируется порядок подключей k i . Стандарт не определяет способ генерации S-блоков.
Основные различия между DES и ГОСТом
Главные различия между DES и ГОСТом заключаются в следующем:
- DES использует сложную процедуру для генерации подключей из ключей. В ГОСТе эта процедура очень проста;
- в DES 56-битный ключ, а в ГОСТе — 256-битный. Если добавить секретные перестановки S-блоков, то полный объем секретной информации ГОСТа составит примерно 610 бит;
- у S-блоков DES 6-битные входы и 4-битные выходы, а у S-блоков ГОСТа 4-битные входы и выходы. В обоих алгоритмах используется по восемь S-блоков, но размер S-блока ГОСТа равен четверти размера S-блока DES;
- в DES используются нерегулярные перестановки, названные Р-блоком, а в ГОСТе используется 11-битный циклический сдвиг влево;
- в DES 16 циклов, а в ГОСТе — 32.
Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ использует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа будет еще больше. ГОСТ, по-видимому, более устойчив к дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S-блоки ГОСТа при некотором выборе не гарантируют высокой криптостойкости по сравнению с фиксированными S-блоками DES, их секретность увеличивает устойчивость ГОСТа к дифференциальному и линейному криптоанализу. К тому же эффективность этих криптоаналитических методов зависит от количества циклов преобразования — чем больше циклов, тем труднее криптоанализ. ГОСТ использует в два раза больше циклов, чем DES, что, возможно, приводит к несостоятельности дифференциального и линейного криптоанализа.
ГОСТ не использует существующую в DES перестановку с расширением. Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта; разумно предположить, что отсутствие такой операции в ГОСТе отрицательно сказывается на его криптостойкости. С точки зрения криптостойкости операция арифметического сложения, используемая в ГОСТе, не хуже, чем операция XOR в DES.
Основным различием представляется использование в ГОСТе циклического сдвига вместо перестановки. Перестановка DES увеличивает лавинный эффект. В ГОСТе изменение одного входного бита влияет на один S-блок одного цикла преобразования, который затем влияет на два S-блока следующего цикла, затем на три блока следующего цикла и т.д. Потребуется восемь циклов, прежде чем изменение одного входного бита повлияет на каждый бит результата; в DES для этого нужно только пять циклов. Однако ГОСТ состоит из 32 циклов, a DES только из 16.
Разработчики ГОСТа пытались достигнуть равновесия между криптостойкостью и эффективностью. Взяв за основу конструкцию Фейстеля, они разработали криптоалгоритм, который лучше, чем DES, подходит для программной реализации. Для повышения криптостойкости введен сверхдлинный ключ и удвоено количество циклов. Однако вопрос, увенчались ли усилия разработчиков созданием более криптостойкого, чем DES, криптоалгоритма, остается открытым.
Воробьева Е., Лукьянова А.
Алгоритм DES
Основные достоинства алгоритма DES:
· используется только один ключ длиной 56 битов;
· зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;
· относительная простота алгоритма обеспечивает высокую скорость обработки информации;
· достаточно высокая стойкость алгоритма.
DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам).
Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).
Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.
Рис.2. Структура алгоритма шифрования DES
Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T).
Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты.
Таблица 1: Матрица начальной перестановки IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:
R(i) = L(i-1) xor f(R(i-1), K(i)) ,
где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.
Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.
На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл.2).
Таблица 2: Матрица обратной перестановки IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.
Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.
Итеративный процесс расшифрования может быть описан следующими формулами:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .
На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.
Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.
Рис.3. Вычисление функции f(R(i-1), K(i))
Для вычисления значения функции f используются следующие функции-матрицы:
Е - расширение 32-битовой последовательности до 48-битовой,
S1, S2, ... , S8 - преобразование 6-битового блока в 4-битовый,
Р - перестановка бит в 32-битовой последовательности.
Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) - это биты 32, 1 и 2, а последние - 31, 32 и 1.
Таблица 3:Функция расширения E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:
E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .
Функции S1, S2, ... , S8 определяются табл.4.
Таблица 4
К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.
Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.
Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), ..., B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).
Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.
Таблица 5:Функция перестановки P
Такимобразом,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1...16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.
Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).
Таблица 6
Матрица G первоначальной подготовки ключа
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, ..., 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, ..., 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1...16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.
Таблица 7
Таблица сдвигов для вычисления ключа
| Номер итерации | Сдвиг (бит) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
Полученное значение вновь "перемешивается" в соответствии с матрицей H (табл.8).
Таблица 8:Матрица H завершающей обработки ключа
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Ключ K(i) будет состоять из битов 14, 17, ..., 29, 32 последовательности C(i)D(i). Таким образом:
K(i) = H(C(i)D(i))
Блок-схема алгоритма вычисления ключа приведена на рис.4.
Рис.4. Блок-схема алгоритма вычисления ключа K(i)
Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ
K(15), затем - K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть!
Режимы работы алгоритма DES
Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:
· электронный шифроблокнот (Electronic Codebook) - ECB;
· цепочкацифровыхблоков (Cipher Block Chaining) - CBC;
· цифровая обратная связь (Cipher Feedback) - CFB;
· внешняя обратная связь (Output Feedback) - OFB.
В этом режиме исходный файл M разбивается на 64-битовые блоки (по 8 байтов): M = M(1)M(2)...M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.
- Tutorial
Привет, %username%!
Многим известно, что стандартом по умолчанию в области симметричного шифрования долгое время считался алгоритм DES. Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1993 году, спустя 16 лет после принятия его в качестве стандарта. Метод, который автор назвал линейным криптоанализом, при наличии 2 47 пар открытых/зашифрованных текстов, позволяет вскрыть секретный ключ шифра DES за 2 43 операций.
Под катом я попытаюсь кратко изложить основные моменты этой атаки.
Линейный криптоанализ
Линейный криптоанализ - особый род атаки на симметричные шифры, направленный на восстановление неизвестного ключа шифрования, по известным открытым сообщениям и соответствующим им шифртекстам.В общем случае атака на основе линейного криптоанализа сводится к следующим условиям. Злоумышленник обладает большим количеством пар открытый/зашифрованный текст, полученных с использованием одного и того же ключа шифрования K. Цель атакующего восстановить частично или полностью ключ K.
В первую очередь злоумышленник производит исследование шифра и находит т.н. статистический аналог, т.е. уравнение следующего вида, выполняющееся с вероятностью P ≠ 1/2 для произвольной пары открытый/закрытый текст и фиксированного ключа:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
где P n , C n , K n - n-ые биты текста, шифртекста и ключа.
После того как подобное уравнение будет найдено атакующий может восстановить 1 бит информации о ключе, используя следующий алгоритм
Алгоритм 1
Пусть T - количество текстов, для которых левая часть уравнения (1) равняется 0, тогда
Если T>N/2, где N - число известных открытых текстов.
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (когда P>1/2) или 1 (когда P<1/2).
Иначе
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (когда P>1/2) или 0 (когда P<1/2).
Очевидно, что успех алгоритма напрямую зависит от значения |P-1/2| и от количества доступных пар открытый/закрытый текст N. Чем больше вероятность P равенства (1) отличается от 1/2, тем меньше количество открытых текстов N необходимо для атаки.
Возникают две проблемы, которые необходимо решить для успешной реализации атаки:
- Как найти эффективное уравнение вида (1).
- Как с помощью такого уравнения получить больше одного бита информации о ключе.
Описание DES
Но для начала кратко опишем работу алгоритма. О DES сказано уже достаточно. Полное описание шифра можно найти на Википедии . Однако для дальнейшего объяснения атаки нам потребуется ряд определений которые лучше ввести заранее.Итак, DES это блочный шифр, основанный на сети Фейстеля . Шифр имеет размер блока 64 бита и размер ключа 56 бит. Рассмотрим схему шифрования алгоритма DES.
Как видно из рисунка, при шифровании над текстом производятся следующие операции:
- Начальная перестановка бит. На этом этапе биты входного блока перемешиваются в определенном порядке.
- После этого перемешанные биты разбиваются на две половины, которые поступают на вход функции Фейстеля. Для стандартного DES сеть Фейстеля включает 16 раундов, но существуют и другие варианты алгоритма.
- Два блока, полученных на последнем раунде преобразования объединяются и над полученным блоком производится еще одна перестановка.
На каждом раунде сети Фейстеля 32 младших бита сообщения проходят через функцию f:
Рассмотрим операции, выполняющиеся на этом этапе:
- Входной блок проходит через функцию расширения E, которая преобразует 32-битный блок в блок длиной 48 бит.
- Полученный блок складывается с раундовым ключом K i .
- Результат предыдущего шага разбивается на 8 блоков по 6 бит каждый.
- Каждый из полученных блоков B i проходит через функцию подстановки S-Box i , которая заменяет 6-битную последовательность, 4-битным блоком.
- Полученный в результате 32-битный блок проходит через перестановку P и возвращается в качестве результата функции f.
Наибольший интерес, с точки зрения криптоанализа шифра, для нас представляют S блоки, предназначенные для скрытия связи между входными и выходными данными функции f. Для успешной атаки на DES мы сперва построим статистические аналоги для каждого из S-блоков, а затем распространим их на весь шифр.
Анализ S блоков
Каждый S-блок принимает на вход 6-битную последовательность, и для каждой такой последовательности возвращается фиксированное 4-битное значение. Т.е. имеется всего 64 варианта входных и выходных данных. Наша задача показать взаимосвязь между входными и выходными данными S блоков. К примеру, для третьего S-блока шифра DES, 3-й бит входной последовательности равен 3-му биту выходной последовательности в 38 случаях из 64. Следовательно, мы нашли следующий статистический аналог для третьего S-блока:S 3 (x) = x, который выполняется с вероятность P=38/64.
Обе части уравнения представляют 1 бит информации. Поэтому в случае если бы левая и правая части были независимы друг от друга, уравнение должно было бы выполняться с вероятностью равной 1/2. Таким образом, мы только что продемонстрировали связь между входными и выходными данными 3-го S-блока алгоритма DES.
Рассмотрим как можно найти статистический аналог S-блока в общем случае.
Для S-блока S a , 1 ≤ α ≤ 63 и 1 ≤ β ≤ 15, значение NS a (α, β) описывает сколько раз из 64 возможных XOR входных бит S a наложенных на биты α равны XOR выходных бит, наложенных на биты β, т.е.:
где символ - логическое И.
Значения α и β, для которых NS a (α, β) сильнее всего отличается от 32, описывают самый эффективный статистический аналог S-блока S a .
Наиболее эффективный аналог был найден в 5-ом S-блоке шифра DES для α = 16 и β = 15 NS 5 (16, 15)=12. Это значит, что справедливо следующее уравнение: Z=Y ⊕ Y ⊕ Y ⊕ Y, где Z - входная последовательность S-блока, а Y - выходная последовательность.
Или с учетом того, что в алгоритме DES перед входом в S-блок данные складываются по модулю 2 с раундовым ключом, т.е. Z = X ⊕ K получаем
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X и Y - входные и выходные данные функции f без учета перестановок.
Полученное уравнение выполняется на всех раундах алгоритма DES с одинаковой вероятностью P=12/64.
На следующей таблице приведен список эффективных, т.е. имеющих наибольшее отклонение от P=1/2, статистических аналогов для каждого s-блока алгоритма DES.
Построение статистических аналогов для нескольких раундов DES
Покажем теперь каким образом можно объединить статистические аналоги нескольких раундов DES и в итоге получить статистический аналог для всего шифра.Для этого рассмотрим трехраундовую версию алгоритма:
Применим эффективный статистический аналог 5-го s-блока для вычисления определенных бит значения X(2).
Мы знаем что с вероятностью 12/64 в f-функции выполняется равенство X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X - второй входной бит 5-го S-блока, он по сути является 26-м битом последовательности, полученной после расширения входных бит. Анализируя функцию расширения можно установить что на месте 26 бита оказывается 17-й бит последовательности X(1).
Аналогичным образом, Y,…, Y по сути являются 17-м, 18-м, 19-м и 20-м битом последовательности полученной до перестановки P. Исследовав перестановку P, получаем что биты Y,…, Y на самом деле являются битами Y(1), Y(1), Y(1), Y(1).
Бит ключа K вовлеченный в уравнения является 26 битом подключа первого раунда K1 и тогда статистический аналог приобретает следующую форму:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1 .
Следовательно, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) (2) с вероятностью P=12/64.
Зная 3, 8, 14, 25 биты последовательности Y(1) можно найти 3, 8, 14, 25 биты последовательности X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) или с учетом уравнения (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) с вероятностью 12/64.
Найдем подобное выражение используя последний раунд. На этот раз мы имеем уравнение
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
.
Так как
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
получаем, что
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3
(4)
с вероятностью 12/64.
Приравняв правые части уравнений (3) и (4) получаем
СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1
с вероятностью (12/64) 2 +(1-12/64) 2 .
С учетом того, что X(1) = PR и X(3) = CR получаем статистический аналог
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3
(5)
,
который выполняется с вероятностью (12/64) 2 +(1-12/64) 2 =0.7.
Описанный выше статистический аналог можно представить графически следующим образом (биты на рисунке пронумерованы справа налево и начиная с нуля):
Все биты в левой части уравнения известны атакующему, следовательно он может применить алгоритм 1 и узнать значение K1 ⊕ K3. Покажем как с помощью данного статистического аналога можно вскрыть не 1, а 12 бит ключа шифрования K.
Атака на DES с известным открытым текстом
Приведем способ с помощью которого можно расширить атаку и получить сразу 6 бит подключа первого раунда.Составляя уравнение (5) мы принимали во внимание тот факт, что нам неизвестно значение F1(PR, K1). Поэтому мы использовали его статистический аналог K1 ⊕ PR.
Вернем вместо выражения K1 ⊕ PR значение F1(PR, K1) и получим следующее уравнение:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , которое будет выполняться с вероятностью 12/64. Вероятность изменилась так как мы оставили только статистический аналог из третьего раунда, все остальные значения фиксированы.
Выше мы уже определили, что на значение F1(PR, K1) оказывают влияние входные биты 5-го S-блока, а именно биты ключа K1 и биты блока PR. Покажем каким образом обладая только набором открытых/закрытых текстов можно восстановить значение K1. Для этого воспользуемся алгоритмом 2.
Алгоритм 2
Пусть N - количество известных перед атакой пар открытый/закрытый текст. Тогда для вскрытия ключа необходимо проделать следующие шаги.
For (i=0; i<64; i++) do
{
For(j=0; j
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) then
T i =T i +1
}
}
В качестве вероятной последовательности K1 принимается такое значение i, при котором выражение |T i -N/2| имеет максимальное значение.
При достаточном количестве известных открытых текстов алгоритм будет с большой вероятностью возвращать корректное значение шести бит подключа первого раунда K1. Объясняется это тем, что в случае если переменная i не равна K1, тогда значение функции F1(PR j , K) будет случайным и количество уравнений для такого значения i, при котором левая часть равна нулю будет стремиться к N/2. В случае же если подключ угадан верно, левая часть будет с вероятностью 12/64 равна фиксированному биту K3. Т.е. будет наблюдаться значительное отклонение от N/2.
Получив 6 бит подключа K1, можно аналогичным образом вскрыть 6 бит подключа K3. Все что для этого нужно, это заменить в уравнении (6) C на P и K1 на K3:
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1
.
Алгоритм 2 возвратит корректное значение K3 потому что процесс расшифровки алгоритма DES идентичен процессу шифрования, просто последовательность ключей меняется местами. Так на первом раунде расшифрования используется ключ K3, а на последнем ключ K1.
Получив по 6 бит подключей K1 и K3 злоумышленник восстанавливает 12 бит общего ключа шифра K, т.к. раундовые ключи являются обычной перестановкой ключа K. Количество открытых текстов необходимых для успешной атаки зависит от вероятности статистического аналога. Для вскрытия 12 бит ключа 3-раундового DES достаточно 100 пар открытых/закрытых текстов. Для вскрытия 12 бит ключа 16-раундового DES потребуется порядка 2 44 пар текстов. Остальные 44 бита ключа вскрываются обычным перебором.
Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technology, США) в качестве стандарта.
DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом этапе выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.
Рис.4. Алгоритм DES
На рисунке показан способ, в котором используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ K i является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи K i для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.
Начальная перестановка и ее инверсия определяются стандартной таблицей. Если М - это произвольные 64 бита, то X = IP (M) - переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов.
Описание раунда des
Рассмотрим последовательность преобразований, используемую в каждом раунде.
Рис.5. Иллюстрация раунда алгоритма DES
64-битный входной блок проходит через 16 раундов , при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:
R i = L i -1 F(R i -1 , K i)
Таким образом, выход левой половины L i равен входу правой половины R i-1 . Выход правой половины R i является результатом применения операции XOR к L i-1 и функции F, зависящей от R i-1 и K i .
Рассмотрим функцию F более подробно. R i , которое подается на вход функции F, имеет длину 32 бита. Вначале R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения
Efgh ijkl mnop . . .
то в результате расширения получается сообщение
Defghi hijklm lmnopq . . .
После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.
Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.
Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.
Ключ для отдельного раунда K i состоит из 48 битов. Ключи K i получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде C i и D i независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F(R i-1 , K i).
Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи K i используются в обратной последовательности. K 16 используется на первом раунде, K 1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет L i ||R i . Тогда соответствующий вход (16-i)-ого раунда дешифрования будет R i ||L i .
После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R 16 ||L 16 . Выходом этой стадии является незашифрованный текст.
Прошло уже белее 30 лет с даты принятия алгоритма DES в качестве стандарта шифрования США. DES - алгоритм шифрования с наиболее богатой и интересной историей.
История создания алгоритма
Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» так описал проблемы пользователей средств защиты информации в начале 70-х гг. XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»):
П не было как общепринятого стандарта шифрования данных, так и просто достаточно широко используемых алгоритмов защиты информации, поэтому о совместимости между различными программными или аппаратными средствами шифрования не могло быть и речи;
Практически любое средство шифрования представляло собой «черный ящик» с достаточно неясным содержимым: какой алгоритм шифрования используется, насколько он является криптографически стойким, грамотно ли он реализован, корректно ли создаются, хранятся, используются ключи шифрования, нет ли в средстве вставленных разработчиками недокументированных возможностей и т. д., - вся эта весьма важная информация для подавляющего большинства покупателей криптографических средств была недоступна.
Данной проблемой озаботилось Национальное Бюро Стандартов (National Bureau of Standards, NBS) США. В результате в 1973 г. был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям:
Алгоритм должен быть криптографически стойким;
Алгоритм должен быть быстрым;
П структура алгоритма должна быть четкой и ясной;
Стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным;
Алгоритм должен быть легко применим для различных целей;
Алгоритм должен легко реализовываться аппаратно на существующей элементной базе.
Предполагалось, что заинтересованные организации или специалисты будут присылать в NBS подробные спецификации алгоритмов, достаточные для их реализации, т. е. не имеющие каких-либо «белых пятен». Предполагалось также, что алгоритм будет сертифицирован NBS для всеобщего использования, с него будут сняты все патентные и экспортные ограничения, в результате чего такой стандарт должен будет решить все проблемы совместимости средств шифрования. Кроме того, NBS брало на себя функции сертификации средств шифрования - т. е. «черные ящики» должны были безвозвратно уйти в прошлое.
Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой ШМ алгоритм шифрования Lucifer {см. разд. 3.31). В течение двух лет проводилась доработка алгоритма:
Во-первых, NBS совместно с Агентством Национальной Безопасности (АНБ, NSA - National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка;
Во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц.
В результате совместной деятельности IBM, NBS и АНБ в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта - в документе ) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма . Альтернативное, но реже используемое название алгоритма - DEA (Data Encryption Algorithm).
Основные характеристики и структура алгоритма
Алгоритм DES шифрует информацию блоками по 64 бита с помощью 64- битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).
Шифрование информации выполняется следующим образом (рис. 3.56):
1. Над 64-битным блоком данных производится начальная перестановка согласно табл. 3.16.
Таблица 3.16
Таблица трактуется следующим образом: значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита - в бит 2 и т. д.
2. Результат предыдущей операции делится на 2 субблока по 32 бита (на
рис. 3.56 обозначены А 0 и В 0), над которыми производятся 16 раундов
следующих преобразований:
Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом . Процедура извлечения 56 значащих битов 64-битного ключа на рис. 3.59 обозначена как Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. 3.19 и 3.20.
Таблица 3.19
Таблица 3.20
В результате перестановки формируются два 28-битных значения С и D. Таблица 3.19 определяет выборку битов ключа для С, табл. 3.20 - для D.
Затем выполняются 16 раундов преобразований, каждый из которых дает один из ключей раундов K t . В каждом раунде процедуры расширения ключа производятся следующие действия:
1. Текущие значения С и D циклически сдвигаются влево на переменное число битов п. Для раундов 1, 2, 9 и 16 п = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.
2. С и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда К (. Сжимающая перестановка выполняется согласно табл. 3.21.
Таблица 3.21
При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 16 и п= 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов.
Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровывании, так и при расшифровывании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей других раундов, кроме текущего.
