В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 4. Блочные шифры ред этим биты исходного блока текста подвергаются начальной перестановке по полуупорядоченному принципу. Никто не может толком объяснить, зачем разработчики шифра DES решили переставить биты открытого текста — ведь это не имеет никакого криптографического эффекта; однако алгоритм DES определен именно так. По окончании шифрования левая и правая половины вновь объединяются и подвергаются обратной перестановке, в результате чего вновь получается 64-битовый блок текста, однако на сей раз шифрованного. Алгоритм DES состоит из 16 раундов, которые обозначаются цифрами от 1 до 16. Каждый раунд i преобразует пару ( L , R ) в новую пару ( L , R ) с помощью подключа K i . Б´ольшую часть преобразования выполняет функ- ция раунда F (на рис. 4.1 она обведена штриховой рамкой). Как показано на рисунке, вначале к значению R применяется функция расширения. Она дублирует 16 битов значения R , в результате чего 32-битовое значение пре- вращается в 48-битовое. Этот результат функции расширения складывается с помощью операции XOR с 48-битовым подключом K i . Результат этой опе- рации подается на вход S-матриц. По своей сути S-матрица (буква S озна- чает substitution , т.е. подстановка ) — это всего лишь таблица соответствий. Поскольку мы не можем построить таблицу соответствий для 48-битовых данных, S-матрицы состоят из восьми небольших таблиц соответствий, каж- дая из которых получает на вход 6 бит и выдает 4-битовый результат. Таким образом, после преобразования 48-битового значения с помощью S-матриц, мы вновь получаем 32-битовое значение. Последнее подвергается еще одной перестановке битов, после чего складывается с помощью операции XOR с ле- вой половиной L . И наконец, значения правой и левой половины меняются местами. Эта процедура повторяется еще 15 раз. В основе алгоритма DES лежит так называемый шифр Файстеля [29]. Идея шифра Файстеля очень проста и красива. Каждый раунд представляет собой побитовое сложение значения L со значением F ( K i , R ) (где F — это некоторая функция) и последующий обмен местами значений L и R . Пре- лесть этого алгоритма заключается в том, что расшифровка состоит из точ- но такого же набора операций. Необходимо поменять местами значения L и R и выполнить побитовое сложение значения L со значением F ( K i , R ) . Это намного упрощает реализацию функций шифрования и дешифрования. Это также означает, что достаточно анализировать лишь одну из двух функций, поскольку они практически идентичны. В большинстве шифров Файстеля по окончании шифрования применяется еще один особый прием — отмена пере- становки значений L и R , выполненной в последнем раунде. Благодаря этому функции шифрования и дешифрования становятся полностью идентичными за исключением порядка применения подключей. Это особенно удобно для реализации в аппаратном обеспечении, поскольку для шифрования и дешиф- рования может применяться одна и та же схема. 4.5. Современные блочные шифры 73 Для шифрования текста алгоритм DES использует шестнадцать 48-бито- вых подключей. Каждый подключ образуется путем выбора 48 бит из 56- битового ключа шифрования, причем для каждого раунда этот выбор вы- полняется по-своему 3 . Каждый из компонентов шифра DES имеет свое назначение. Алгоритм Файстеля упрощает структуру шифра и гарантирует перемешивание правой и левой половин текста. Сложение текста с подключом с помощью операции XOR гарантирует перемешивание ключа и данных, в чем, собственно, и за- ключается весь смысл шифрования. S-матрицы обеспечивают нелинейность. Без них процесс шифрования можно было бы представить в виде последова- тельности операций двоичного сложения, что очень легко взломать, исполь- зуя методы линейной алгебры. И наконец, сочетание S-матриц, функции рас- ширения и перестановки битов обеспечивает диффузию. Другими словами, если изменить один бит во входном значении функции F , в ее выходном зна- чении изменится сразу несколько битов. В следующем раунде это изменение станет еще более обширным и т.п. При отсутствии диффузии незначительное изменение открытого текста приведет к незначительному изменению шифро- ванного текста, что можно легко отследить. Алгоритм DES обладает рядом свойств, которые не позволяют считать его безопасным в соответствии с нашим определением безопасности. Каж- дый из подключей представляет собой не более чем выборку битов ключа шифрования. Если ключ шифрования равен 0, все подключи также будут равны 0. Это, в частности, означает, что все подключи будут одинаковыми. Напомним, что процедуры шифрования и дешифрования различаются лишь порядком применения подключей. Но в нашем случае все подключи будут равны. Таким образом, шифрование с помощью ключа 0 — это то же самое, что и дешифрование с помощью ключа 0. Данное свойство шифра очень лег- ко обнаружить, а поскольку идеальный шифр таким свойством не обладает, это позволяет осуществить легкую и эффективную различающую атаку 4 . Алгоритм DES обладает и свойством комплементарности (или дополне- ния). Согласно этому свойству для любого ключа K и открытого текста P справедливо следующее: E ( ¯ K, ¯ P ) = E ( K, P ) , где ¯ X — это значение, каждый бит которого является дополнением соответ- ствующего бита значения X . Другими словами, если зашифровать дополне- 3 Выбор подключей осуществляется в соответствии с некоторым механизмом, описание которого содержится в спецификациях DES [69]. 4 Существует еще три ключа, которые обладают этим же свойством. Они называются слабыми ключами алгоритма DES. |