Преобразования ключа

Начальная перестановка

Г

Сдвиг Сдвиг

Перестановка со сжатием

1____ [

Ключ

Рис. 12-2. Один этап DES.

Если Bt - это результат г-ой итерации, Ц и R_t - левая и правая половины В„ К, - 48-битовый ключ для этапа i, a f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

U = Ri-!

Д,-= Z,,-.! © f№__b £,■)

Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная пер е-становка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее.

Табл. 12-1. Начальная перестановка

58, 50^ 42^ Н 26, 1Л 10, 2, 60^ 52^ 44^ 36^ 28^ 20, Y2, <Г

62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,

57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, И, 3,

61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES. (Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки да н-ных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка (в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключител ь-ные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответс т-вует стандарту DES и, поэтому, не может называться DES.

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый

подключ. Эти подключи, К„ определяются следующим образом.

Табл. 12-2. Перестановка ключа

57^ 49^ 4\, 33^ 25^ \П, 9, 1^ 58^ 50^ 42^ 34, 26^ 18^

10, 2, 59, 51, 43, 35, 27, 19, И, 3, 60, 52, 44, 36,

63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,

14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвиг а-ются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й.

Табл. 12-3. Число битов сдвига ключа в зависимости от этапа

Этап I 2 3 4 5 6 7 8 9 10 П 12 13 14 15 16

Число 1122222212222221

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбр а-сывается.

Табл. 12-4. Перестановка со сжатием

\4, \П, П, 2Д 1^ 5^ 3, 28^ 1Д 6, 2й Щ

23, 19, И, 4, 26, 8, 16, 7, 27, 20, 13, 2,

41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,

44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

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

Перестановка с расширением

Эта операция расширяет правую половину данных, R„ от 32 до 48 битов. Так как при этом не просто повто­ряются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расшире-нием. У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и пол у-чить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроек­тирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита о т-крытого текста и каждого бита ключа.

Перестановка с расширением показана на 9-й. Иногда она называется E-блоком (от expansion). Для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким поз и-циям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16

^х

Дата добавления: 2014-11-29