2.3.3. Помехостойкость шифров

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

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

1. Замена знаков знаками того же алфавита.

2. Потеря знаков или появление дополнительных знаков того же алфавита.

Шифры, не распространяющие искажений типа "замена знаков".

Будем рассматривать шифры, описываемые алгебраической моделью

_A = (X, K, Y, E, D),

в которой причем для любых x  X и k  K длина y = E_k(x) совпадает с длиной x.

Мерой значительности последствий искажений типа "замена знаков" является метрика на множестве сообщений X = Y. Простейшей является метрика Хэмминга , определяемая формулой

Так как для эндоморфного шифра каждое правило зашифрования E_k представляет собой биекцию E_k : X  X, то будем пользоваться подстановочной моделью шифра - _П = (X, E), в которой множество E ={e_k : k  K} рассматривается как множество подстановок e : X  X, e  E.

Шифр _П = (X, E) не распространяет искажений типа замены знаков и являются помехостойкими если для любых x, y  A^ и любого e  E выполняется неравенство

(e^-1x, e^-1y)  (x, y).

Подстановки e  E, удовлетворяющие предыдущему равенству, называются изометриями на X.

Теорема А. А. Маркова. Биекция eE является изометрией на X тогда и только тогда, когда для подходящих преобразований множества X:

где (j₁,…,j_) – перестановка чисел 1, 2, …, ; R_i  S(A) – некоторые фиксированные подстановки множества A, a_i  A,

Согласно теореме Маркова, в классе эндоморфных шифров, не изменяющих длины сообщений, не распространяют искажения типа замены знаков, например шифры перестановки, поточные шифры однозначной замены, а также их композиции типа шифр замены – шифр перестановки.

Шифры, не распространяющие искажений типа "пропуск-вставка знаков".

Приведем теорему, рассматривающую подстановочную модель шифра.

Теорема. Если _П = (X, E) – шифр не распространяющий искажений типа пропуск-вставка, то для любого e  E, либо e = _L, либо у = _L · f (при подходящем   S(A)), где _L отображение множества X в себя, определенное для любого a = (a₁,…,a_)  X формулой

( - некоторая подстановка множества A), а f – отображение множества X в себя, меняющее порядок следования букв любого слова на противоположный:

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

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