Модель шифра замены

Определим модель ε_A = (X, K, Y, E, D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах A и B соответственно: X ⊂ A^*, Y ⊂ B^*, |A| = n, |B| = m. Здесь и далее C^* обозначает множество слов конечной длины в алфавите C.

Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из A^* и B^* соответственно.

Пусть U = {u₁,…,u_N} — множество возможных шифрвеличин, V = {v₁,…,v_M} — множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты x ∈ X, y ∈ Y можно было представить словами из U^*, V^* соответственно. Требование однозначности расшифрования влечет неравенства N ≥ n, M ≥ m, M ≥ N.

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

Поскольку M ≥ N, множество V можно представить в виде объединения V = ∪_i=1^NVⁱ непересекающихся непустых подмножеств Vⁱ. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V: V = ∪_i=1^NV_α⁽ⁱ⁾, α = 1,…,r, r ∈ N.

Заметим, что последнее обозначение, введенное в [1], представляется неудачным, поскольку речь идет уже не о представлении множества V, а о множестве таких представлений. Кроме того, согласно тексту, N не отрезок натурального ряда, а число, что препятствует записи r ∈ N. Вследствие изложенного, семейство разбиений предпочтительно записать в виде {∪_i=1^NV_α⁽ⁱ⁾}, α = 1,…,r, r ∈ {1,2,…,N}, ∪_i=1^NV_α⁽ⁱ⁾ = V, V_α⁽ⁱ⁾ ∩ V_α^(j) = Ø, V_α⁽ⁱ⁾ ≠ Ø.

Семейство биекций, соответствующее этому семейству разбиений множества V, обозначим через {φ_α}: V⇒{V_α⁽¹⁾,…,V_α^(N)} и будем предполагать, что φ_α(u_i) = V_α⁽ⁱ⁾, i = 1,…,N.

Рассмотрим также произвольное отображение Φ: K×N ⇒ N_r^*, где N_r = {1,2,…,r}, такое, что для любых k ∈ K, l ∈ N выполнено Φ(k,l) = a₁^(k)…a_l^(k), a_j^(k) ∈ N_r, j = 1,…,r.

Назовем последовательность Φ(k,l) распределителем, отвечающим данным значениям k ∈ K, l ∈ N.

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть x ∈ X, x = x₁…x_l, x_i ∈ U, i = 1,…,l, k ∈ K и Φ(k,l) = a₁^(k)…a_l^(k). Тогда E_k(x) = y, где y = y₁…y_l, y_i ∈ φ_aj^(k) (x_j), j = 1,…,l.

В качестве y_j можно выбрать любой элемент множества φ_aj^(k)(x_j). Всякий раз при шифровании этот выбор можно производить случайно. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, т. к. V_α⁽ⁱ⁾ ∩ V_α^(j) = Ø при i ≠ j.

Классификация шифров замены

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

Для однозначных шифров справедливо свойство: для любых α, i: |V_α⁽ⁱ⁾| = 1 для многозначных шифров — существуют α, i: |V_α⁽ⁱ⁾| > 1.

Наибольшее применение получили шифры однозначной замены. К ним в частности относится и рассмотренный ниже шифр гаммирования, играющий большую роль как в классической, так и в современной криптографии. Далее шифры замены будем считать однозначными. Тогда M = N и φ_a(u_i) = v_a,i, i = 1,…,M.

Заметим, что правило зашифрования E_k естественным образом индуцирует отображение Ë_k: U⇒V, которое в свою очередь продолжается до отображения Ë_k: U^*⇒V^*. Для упрощения записи будем использовать одно отображение E_k для каждого из трех указанных отображений.

В силу инъективности (по k) отображения E_k и того, что |U| = |V|, введенные в общем случае отображения φ_α являются биекциями φ_α: U⇒V,V⇒U, определенными равенствами φ_α(u_i) = v_α⁽ⁱ⁾, i = 1,…,N, α = 1,…,r. Число таких биекций не превосходит N!.

Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле y_j ∈ φ_(αj^(k)₎ (x_j), j = 1,…,l включение следует заменить равенством y_j = φ_(αj^(k)₎ (x_j), j = 1,…,l.

Введем еще ряд определений.

Если для некоторого числа q ∈ N выполняются включения v_i ∈ B^q, i = 1,…,N, то соответствующий шифр будем называть шифром равнозначной замены. В противном случае — шифром разнозначной замены.

Иначе говоря, шифр равнозначной замены имеет шифробозначения из одинакового количества символов, шифр разнозначной замены, вообще говоря — из разного количества. Например, шифр Цезаря, сопоставляющий каждой букве ровно одну букву — равнозначный. А шифр, сопоставляющий некоторым буквам однозначное число, а другим двузначное — разнозначный.

В подавляющем большинстве случаев используются шифры замены, для которых U⊂A^p, для некоторого p ∈ N. При p = 1 говорят о поточных шифрах замены, при p > 1 — о блочных шифрах замены. Таким образом, поточные шифры замены предусматривают только однобуквенные шифрвеличины, блочные — многобуквенные.

Наконец, в случае r = 1 шифр замены называют одноалфавитным шифром замены, в противном случае — многоалфавитным шифром замены.

Для однозначных замен эти термины представляются не совсем удачными. Действительно, в этом случае алфавит шифробозначений — единственный с точностью до его нумерации, т. е. до порядка следования шифробозначений. Если, например, шифрвеличины и шифробозначения — буквы русского алфавита, то распределитель Φ указывает, в каком порядке следует расположить буквы для замены каждой шифрвеличины сообщения. Если для двух одинаковых шифрвеличин, расположенных в разных местах открытого текста, распределитель дает разные порядки букв алфавита шифробозначений, то одно и то же правило замены j переведет эти шифрвеличины в разные шифробозначения.