Случай известного строения классов эквивалентности

Если известны представители всех s классов эквивалентности, то можно реализовать опробование ключей по схеме без возвращения. Упорядочим мощности классов эквивалентности следующим образом:

и рассмотрим kj 6 Kj — представители классов эквивалентности.

Будем опробовать ключи kj в порядке, определяемом неравенствами (4.10). Заметим, что при случайном выборе ключа шифрования k Е К вероятность того, что к Е Kj, будет равна

Отсюда, в частности, получаем, что при равной мощности классов эквивалентности среднее число опробований составит В общем же случае для величины М справедлива оценка сверху.

Строение классов эквивалентности композиции шифров простой замены

Продемонстрируем строение классов эквивалентности множества ключей К на примере композиции двух шифров простой замены.

Пусть SA — (X, K, Y, Е, D) — шифр, являющийся композицией двух шифров простой замены. Для простоты изложения полагаем.

К = S_n х S_n — декартово произведение двух симметрических групп подстановок,.

где S, о € 5″ - две перестановки, определяющие ключ зашифрования к = (6, о),.

алгоритм расшифрования на ключе к — (6, а).

Утверждение 4.4. Множество ключей указанного выше шифра состоит из п классов эквивалентности мощности п каждый.

Доказательство. Во-первых, заметим, что ключи Ац = (<5i,к'2 = (62,0-2) являются эквивалентными в том и только том случае, когда в симметрической группе S_n выполняется равенство.

Заметим далее, что при любой подстановке л G S, существует ровно п! пар (4, а) с условием до = я. Следовательно, разложение множества ключей К на классы эквивалентности будет иметь вид

где s = п и.

Таким образом, хотя мощность ключей данного шифра равна (п!)², в среднем потребуется всего ^ опробований до нахождения истинного ключа или ему эквивалентного.

Аналогичные построения можно провести и применительно к композиции любых шифров, у которых множество отображений {Еь, к е К} образует группу по умножению.