Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Алгоритм расшифровки начинает работу с ввода зашифрованного текста с в качестве "исходного блока". По формуле (7.6.1) получаем:
(ад)-гр(с).
Поскольку сообщение с, по существу, является "результирующим блоком", полученным на заключительном этапе алгоритма шифрования, в соответствии с формулой (7.6.4) имеем
(L0,i?o) = (/?i6,Li6). (7.6.6)
В первом раунде, применяя операции (7.6.2), (7.6.3) и (7.6.6), получаем
L\ «— R'Q = Lie,
RJi ^L'0@f (Rq, k[) = Rm © /(L16, k'i).
По формуле (7.6.2) в правых частях этих двух операций присваивания блок Lie должен быть заменен блоком Ris, а в соответствии с формулой (7.6.3) блок Rie следует заменить блоком Li5©/(-Ri5, &1б)- Кроме того, из расписания ключей (7.6.5) следует, что к^ = kie- Итак, две операции присваивания, описанные выше, принимают следующий вид.
L'i <— Rib,
#i «- [Lib © / (Rib, he)] © f(Ri5, кю) = Lis-
Следовательно, после первого раунда получаем
{L'1,R'1) = {R15,L15).
Таким образом, в начале второго раунда две половины блока имеют вид (R15, Lis)-Выполняя остальные 15 раундов, приходим к следующим результатам.
(L2,R2) = (Ru,Li4)(L'16,R'l6) — (R0,L0).
Последние две половины блока (L'l6, R'i6), полученные в результате 16-го раунда, меняются местами: (Д^6, L'16) = (Lq, Ro) и поступают на вход функции IP-1, выполняющей перестановку, обратную по отношению к начальной (учтите, что по формуле (7.6.4) следует выполнить дополнительную перестановку подблоков). В результате начальная перестановка (7.6.1) компенсируется, и мы получаем
ИСХОДНЫЙ блОК 771. ?
264
Часть III. Основные методы криптографии
Рис. 7.2. Шифр Файстеля (один раунд)
Мы показали, что алгоритмы шифрования и расшифровки по стандарту DES удовлетворяют условию (7.2.1) при всех т Е М и к G К.. Очевидно, что работа этих алгоритмов не зависит от внутреннего устройства функции подстановки ц и расписания ключей.
Итерации алгоритма DES, использующие операции (7.6.2) и (7.6.3) для перестановки блоков, называются шифром Файстеля (Feistel cipher) [107]. На рис. 7.2 показана структура перестановок, выполняемых в течение одного раунда шифра Файстеля. Как указывалось ранее, операция перестановки обеспечивает большую диффузию данных. Шифр Файстеля широко применяется в криптографии с от] крытым ключом. По существу, структура ОАЕР (Optimal Asymmetric Encryption Padding) является двухраундовым шифром Фейстеля. Он рассматривается в раз! деле 15.2.
7.6.2 Основа алгоритма DES — случайное и нелинейное распределение сообщений
Сущность алгоритма DES заключена в функции S-блока /. Именно она обес печивает случайное и нелинейное распределение исходных сообщений по прв странству зашифрованных сообщений.
В г-м раунде функция /(.Rj_ij fcj) выполняет две следующие вспомогательны' операции.
1. Складывает ключ раунда fcj с половиной блока Ri-\, применяя побитову операцию XOR, Это обеспечивает случайность распределения сообщений!
2. Подставляет результат первой операции в фиксированную перестановку, состоящую из восьми "блоков постановки" (S-блоков). Каждый S-блок пре
Глава 7. Шифрование — симметричные методы
265
ставляет собой нелинейную функцию подстановки. Это гарантирует нелинейность распределения сообщений. Нелинейность S-блоков очень важна для стойкости алгоритма DES. Заметим, что в общем случае подстановочный шифр (см. пример 7.1 со случайным ключом) является нелинейным, в то время как сдвиговый и аффинный шифры являются линейными. Эта линейность не только резко уменьшает размер пространства ключей, но и делает результирующий зашифрованный текст уязвимым для методов дифференциального криптоанализа (DC) [33]. Дифференциальный криптоанализ атакует шифр, используя линейную разность между двумя исходными сообщениями и между двумя зашифрованными сообщениями. Рассмотрим в качестве примера атаку на аффинный шифр (7.3.3). Допустим, что Злоумышленник (атакующий) каким-то образом узнал разность т — т', но не знает ни т, ни т'. Если соответствующие зашифрованные тексты имеют вид с = k\rn + /^(mod АГ), d = к\т' + ^(mod N), Злоумышленник может вычислить величину
h = (с - c')/(m - m')(modN).
Зная число к\, намного легче найти величину к2: ее можно вычислить, если Злоумышленнику известна хотя бы одна пара "открытый текст - зашифрованный текст". Как было выяснено в 1990 году, дифференциальный криптоанализ оказался очень мощным оружием против многих известных блочных шифров. Однако он не справился с алгоритмом DES. Со своей стороны, разработчики алгоритма DES предвидели возможность атаки с помощью методов дифференциального криптоанализа за 15 лет до этого [81] и защитили его, обеспечив нелинейность S-блоков.
Интересной особенностью алгоритма DES (а фактически — шифра Файсте-ля) является тот факт, что функция f(Ri-\,ki) не обязана быть обратимой. Как показано в примере 7.4, шифрование и расшифровка могут выполняться с помощью произвольной функции f(Ri—i, ki). Это свойство открывает перспективы для аппаратной реализации алгоритма DES.
Мы пропускаем детали внутреннего устройства S-блоков, расписания ключей и функции, обеспечивающей начальную перестановку. Эти детали выходят за рамки книги. Читатели, интересующиеся этими вопросами, найдут их в книге [93].
