Криптография и свобода
Шрифт:
бxi – это подстановка на множестве Z/264. Тогда все преобразование, осуществляемое схемой «Ангстрем-3», будет выглядеть как произведение подстановок:
бх1,х2,…,х16 = бx1бx2…бx16
Рассмотрим преобразование Ф(у1,у2,…у8) = (П (у1), П (у2),…, П (у8)). Заметим, что
Ф– 1(у1,у2,…у8) = (П– 1 (у1), П– 1 (у2),…, П– 1 (у8)).
Имеем
Ф– 1бх1,х2,…,х16
где фхi = Ф– 1бxiФ
Если блок открытого текста (y1,y2,…,y8) переходит в блок шифртекста (y17,y18,…,y24) с помощью преобразования бх1,х2,…,х16, т.е.
бх1,х2,…,х16(y1,y2,…,y8) = (y17,y18,…,y24),
то
Ф– 1бх1,х2,…,х16(y1,y2,…,y8) = Ф– 1 (y17,y18,…,y24) = (П– 1 (у17), П– 1 (у18),…, П– 1 (у24)).
Тогда
(П– 1(у17), П– 1(у18),…, П– 1(у24)) = Ф– 1бх1,х2,…,х16 ФФ– 1 (y1,y2,…,y8) = Ф– 1бх1,х2,…,х16Ф (П– 1 (у1), П– 1 (у2),…, П– 1 (у8))
Итак, вот она, первая зацепка для анализа «Ангстрем-3»: заменяем позначно все буквы шифрованного и известного открытого текста по подстановке П– 1 и дальше используем вместо бxi преобразования фхi. А теперь давайте посмотрим на эти преобразования повнимательнее.
фхi (yi, yi+1,…yi+7)= Ф– 1бxiФ(yi, yi+1,…yi+7) = Ф– 1бxi(П (yi), П (yi+1),… П (yi+7)) =
Ф– 1(П(yi+1), П(yi+2),….,П(П(yi)+П(yi+1)+П(yi+7)+хi) = (yi+1, yi+2,…., П (yi)+П (yi+1)+П (yi+7)+хi)
Жизнь прекрасна и удивительна! Какие уравнения получились!
уi+8 = П (yi)+П (yi+1)+П (yi+7)+хi
Возьмем-ка теперь парочку блоков открытого текста (y1,y2,…,y8) (z1,z2,…,z8)
уi+8 = П (yi)+П (yi+1)+П (yi+7)+хi
zi+8 = П (zi)+П (zi+1)+П (zi+7)+хi
Это же криптографический Клондайк! Вычитаем одно уравнение из другого и ключ пропадает!
ui+8 = vi+vi+1+vi+7 (1)
где ui = yi– zi, vi = П(yi)- П(zi).
Из (1) имеем:
vi = ui+8 –vi+1– vi+7 (2)
Линейное уравнение – мечта криптографа! Тут только надо найти все такие решения, при которых для каждой пары (ui,vi) соответствующий элемент рui,vi в матрице Р(П) был бы ненулевым. Поехали!
При Т=16 из (1) и (2) имеем:
u1,u2,…u8, v1,v2,…v8 – известны – это открытый текст
u17,u18,…u24, v17,v18,…v24 – известны – это шифртекст
Из (2) последовательно находим:
v16 = u24– v17– v23
v15 = u23– v16– v22
…………
v9 = u17– v10– v16
а затем уже из (1) – все ui. Система (1) полностью решена!
Дальше – раздолье. Ключ опробуем позначно. Для первого байта ключа x1 оставляем допустимыми только те значения, при которых пара (y9,z9) является решением системы
y9– z9 = u9
П(y9)- П(z9) = v9
Если таких значений будет несколько, то возьмем еще одну пару и истинным будут только те значения, которые содержатся в пересечении этих множеств и так поштучно определяем весь ключ.
Вот теперь пора и почитать, что там наша доблестная армия нашифровала. Военный приказ будем взламывать по-военному четко: делай раз, делай два, делай три.
1. Берем первые 24 знака известного нам открытого текста, соответствующие им знаки шифртекста и составляем две пары переходов из открытого текста в шифрованный.
Первая пара
Вторая пара
2. Все байты в этих парах заменяем по подстановке П– 1.
3. Для каждой из этих двух пар составляем и решаем систему линейных уравнений (1).
Первая пара
Открытый текст
Шифртекст
Сначала с помощью уравнений (2) вычисляем промежуточные значения v16,v15,…,v9.