Алгебраические модели шифров

Алгебраическая модель предложенная К. Шенноном.

Пусть X, K, Y – конечные множества открытых текстов, ключей и шифртекстов соответственно, | X | > 1, | K | > 1, | Y | > 1, E_k: X ® Y и D_k: E_k (X) ® X – правила зашифрования и расшифрования, отвечающие ключу k Î K, E = { E_k: k Î K }, и D = { D_k: k Î K }. Через E_k (X) мы обозначили множество E = { E_k (x): x Î X }. Если ключ k Î K, представляется в виде пары k = (k_з, k_р), где k_з – ключ зашифрования, а k_р – ключ расшифрования (причем k_з ¹ k_р), то E_k понимается как E_kз, а D_k – как D_kр.

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

S_A = (X, K, Y, E, D)

введенных множеств, для которых выполняются условия

1) при любых x Î X и k Î K выполняется равенство D_k (E_k (x)) = x;

2) справедливо равенство .

Условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент y Î Y может быть представлен в виде E_k (x) для подходящих элементов x Î X и k Î K. В общем случае E_k могут быть многозначными отображениями, но здесь мы ограничиваемся изучением лишь однозначных шифров, получивших наибольшее распространение.

Шифр называется эндоморфным, если Y = X. Для эндоморфного шифра правило зашифрования E_k осуществляет биективное отображение множества X на себя. В этом случае удобно рассматривать правила зашифрования как подстановки множества X, и опускать индекс в записи E_k, предполагая, что правила зашифрования пронумерованы ключами. По сути, вся информация об эндоморфном шифре содержится во множествах X и K.

Определение: Подстановочной моделью эндоморфного шифра назовем упрощенную совокупность S_П = (X, E)

Примеры.

1. Шифр простой замены в алфавите А:

Пусть , где S (A) – симметрическая группа подстановок множества А и L натуральное число. " k Î K, x = (x ₁,.. x_l), y = (y ₁,.. y_l): E_k (x) = (k (x ₁),.., k (x_l)),

D_k (y) = (k ^-1(y ₁),.., k ^-1(y_l)),где k ^-1 – подстановка, обратная к k.

Подстановочной моделью данного эндоморфного шифра является совокупность (X, E), для которой e (x ₁,.. x_l) = k (x ₁),.., k (x_l). Здесь x = x ₁,.., x_l Î X, e Î E, а k – ключ, поставленный в соответствие подстановке e.