Автор: Stalker

Данный метод применяется для атаки на блочные шифры. Обладает значительно меньшей трудоемкостью по сравнению с методом полного перебора.

Начальные условия. Даны открытый и шифрованный тексты. Криптосистема состоит из h циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ K системы представляет собой сочетание из h-цикловых ключей k₁,k₂ ... k_h(см. рис.)

Задача. При известных открытом и шифрованном текстах найти ключ K.

Обозначим преобразование алгоритма как E_k(a)=b, где a-открытый текст, а b-шифротекст. Его можно представить как композицию E_k1E_k2..E_kh(a)=b, где E_ki - цикловое преобразование на ключе k_i. Каждый ключ k_i представляет собой двоичный вектор длины n, а общий ключ системы - вектор длины n*h. 

1. Заполнение памяти.

Будем перебирать все значения k'=(k₁,k₂..k_r), т.е первые r цикловых ключей. На каждом таком ключе k' зашифровываем открытый текст a   - E_k' (a)=E_k1E_k2..E_kr(a)=S (т.е. проходим r циклов шифрования вместо h). Будем считать S неким адресом памяти и по этому адресу запишем значение k'.  Необходимо перебрать все значения k'.

2. Определение ключа.

Перебираем все возможные k"=(k_r+1,k_r+2...k_h). На получаемых ключах расшифровываем шифротекст b - E^-1_k"(b)=E^-1_kh..E^-1_kr+1(b)=S' . Если по адресу S' не пусто, то достаем оттуда ключ k' и получаем кандидат в ключи (k',k")=k.

Однако нужно заметить, что первый же полученный кандидат k не обязательно является истинным ключом. Да, для данного о.т a и ш.т.b выполняется E_k(a)=b, но на других значениях открытого текста a' шифротекста b', полученного из a' на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой "псевдоэквивалентный" ключ. В противном же случае после завершения процедур будет получено некое множество ключей {k',k"...}, среди которых находится истинный ключ.

Если рассматривать конкретное применение, то шифротекст и открытый текст могут быть большого объема (например, графические файлы) и представлять собой достаточно большое число блоков для блочного шифра. В данном случае для ускорения процесса можно зашифровывать и расшифровывать не весь текст, а только его первый блок (что намного быстрее) и затем, получив множество кандидатов, искать в нем  истинный ключ, проверяя его на остальных блоках.