Линейный криптоанализпредставляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsura Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные приближения для оп и-сания работы блочного шифра (в данном случае DES.)
Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, вы получите бит, который представляет собой XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с некот о-рой вероятностьюp. Еслиp Ф 1/2, то это смещение можно использовать. Используйте собранные открытые те к-сты и связанные шифротексты для предположения о значениях битов ключа. Чем больше у вас данных, тем вернее предположение. Чем больше смещение, тем б ыстрее вскрытие увенчается успехом.
Как определить хорошее линейное приближение для DES? Найдите хорошие одноэтапные линейные пр и-ближения и объедините их. (Начальная и заключительная перестановки снова игнорируются, так как они не влияют на вскрытие.) Взгляните на S-блоки. У них 6 входных битов и 4 выходных. Входные биты можно объ е-динить с помощью операции XOR 63 способами (26 - 1), а выходные биты - 15 способами. Теперь для каждого S-блока можно оценить вероятность того, что для случайно выбранного входа входная комбинация XOR равна некоторой выходной комбинации XOR. Если существует комбинация с достаточно большим смещением, то л и-нейный криптоанализ может сработать.
Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я и з-
бавлю вас от длительного изучения таблиц, наиболее смещенным S-блоком является пятый S-блок. Действ и-тельно, для 12 входов второй входной бит равен XOR всех четырех выходных битов. Это соответствует вероя т-ности 3/16 или смещению 5/16, что является самым большим смещением для всех S-блоков. (Шамир писал об этом в [1423], но не смог найти способа использовать.)
На 4-й показано, как воспользоваться этим для вскрытия функции этапа DES. Ь26 - это входной бит S-блока 5. (Я нумерую биты слева направо от 1 до 64. Мацуи игнорирует это принятое для DES соглашение и нумерует свои биты справа налево и от 0 до 63. Этого хватит, чтобы свести вас с ума.) с17, с18, с19, с20 - это 4 выходных бита S-блока 5. Мы можем проследить Ь26 в обратном направлении от входа в S-блок. Для получения Ь26 бит объединяется с помощью XOR с битом подключа Kh26. А бит Хг1 проходит через подстановку с расширением, чтобы превратиться в а26. После S-блока 4 выходных бита проходят через Р-блок, превращаясь в четыре выхо д-ных бита функции этапа: Y3, YH, Yu и Y25. Это означает, что с вероятностью 1/2 - 5/6:
Х17 © Г3 © Г8 © У14 © Y25 = Kh26
X
Хм
Е
Е(Х)
К,
Э26
-$
К/,26
ь26
S-блок
Ci7,Cig,Ci9, C20
У
Уз, Ye, Yu, Y25