МЕТОД «ВСТРЕЧА ПОСЕРЕДИНЕ»

Рассмотрим каскадный метод построения сложного шифра из исходных простых. Даны два шифра Т₁(х, к₁) и Т₂(у, к₂). Шифртекст у получается из открытого текста х композицией отображений Т₁ и Т₂, то есть

у = Т₂(Т₁(х, к₁), к₂).

Ключ шифра – вектор к = (к₁, к₂), где к₁ÎК₁, к₂ÎК₂, К = К₁хК₂. Разумеется, в Т₁ и Т₂ согласованы области определения и значений при любых к₁ÎК₁ и к₂ÎК₂ и расшифрование происходит применением следующего преобразования:

х = Т₁(Т₂(у, к₂), к₁).

Трудоемкость полного перебора равна . Вместе с тем можно сократить перебор, увеличив используемую память. Пусть для известной пары (х, у) ключ (к₁, к₂) определяется единственным образом. Для всех к₁⁽ⁱ⁾ ÎК₁, i= 1, …, |К₁|, построим таблицу

у₁=Т₁(х, к₁⁽¹⁾)

……………. (5.1)

у_|К1|=Т₁(х, к₁^(|К1|)).

Вычисление таблицы (5.1) потребует |К₁| операций опробования. Построим следующую таблицу для всех к₂^(j) ÎК₂, j = 1, …, |К₂|.

у’₁=Т^-1₁(у, к₂⁽¹⁾)

……………. (5.2)

у’_|К2|=Т^-1₁(у, к₂^(|К2|)).

Вычисление таблицы (5.2) потребует |К₂| операций опробования. Объединим таблицы (5.1) и (5.2) и проведем их упорядочивание в соответствии с некоторым порядком на множестве значений промежуточных шифртекстов. Пара у_i = у’_j при некоторых (i,j) определяет использованный ключ (к₁⁽ⁱ⁾,к₂^(j)). Для ее нахождения достаточно просмотреть таблицу.