Для того, чтобы иметь возможность доказывать в криптографии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в первую очередь шифр и открытый текст. Введем сначала алгебраическую модель шифра (шифрсистемы), предложенную, по сути дела, К. Шенноном.
Пусть X, Y, K — конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; Ek: X ⇒ Y — правило зашифрования на ключе k ∈ K. Множество {Ek: k ∈ K} обозначим через E, а множество {Ek(x): x ∈ X} — через Ek(X). Пусть Dk: Ek(X) ⇒ X — правило расшифрования на ключе k ∈ K, и D — это множество {Dk: k ∈ K}. Здесь и далее мы будем предполагать, что если k ∈ K представляется в виде k = (kз, kр), где kз — ключ зашифрования, а kр — ключ расшифрования (причем kз ≠ kр), то Ek понимается как функция Ekз, а Dk — как функция Dkр.
Определение. Шифром (шифрсистемой) назовем совокупность εA = (X, K, Y, E, D) введенных множеств, для которых выполняются следующие свойства:
Неформально, шифр — это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифртекстов (то, во что шифруется), правил зашифрования и правил расшифрования.
Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент y ∈ Y может быть представлен в виде Ek(x) для подходящих элементов x ∈ X и k ∈ K. Отметим также, что в общем случае утверждение «для любых k ∈ K и y ∈ Ek(X) выполняется равенство Ek(Dk(y)) = y» является неверным. Иначе говоря, функция Dk постоянна, а Ek может меняться в процессе шифрования.
Легко проверить, что из условия 1) следует свойство инъекции функции Ek. Другими словами, если x1, x2 ∈ X, причем x1 ≠ x2, то при любом k ∈ K выполняется неравенство Ek(x1) ≠ Ek(x2).
По сути дела определение, приведенное выше, вводит математическую модель, отражающую основные свойства реальных шифров. В силу этого мы будем отождествлять реальный шифр с его моделью εA, которую будем называть алгебраической моделью шифра.
Введем теперь вероятностную модель шифра. Следуя К. Шеннону, определим априорные распределения вероятностей P(X), P(K) на множествах P и K соответственно. Тем самым для любого x ∈ X определена вероятность px(x) ∈ P(x) и для любого k ∈ K — вероятность pk(k) ∈ P(K), причем выполняются равенства:
В тех случаях, когда нам требуется знание распределений P(X), P(K), мы будем пользоваться вероятностной моделью εB, состоящей из пяти множеств, связанных условиями 1) и 2) определения, и двух вероятностных распределений:
Отметим, что вероятностные характеристики шифров используются лишь в криптоанализе, т. е. при вскрытии (или взломе) шифров.
В большинстве случаев множества X и Y представляют собой объединения декартовых степеней некоторых множеств A и B соответственно, так что для некоторых натуральных L и L1:
Множества A и B называют соответственно алфавитом открытого текста и алфавитом шифрованного текста. Другими словами, открытые и шифрованные тексты записываются привычным образом в виде последовательностей букв.
Введем шифр простой замены в алфавите A.
Определение. Пусть X = Y = ∪i=1LAi, K ⊆ S(A), где S(A) — симметричная группа подстановок множества A. Для любого ключа k ∈ K, открытого текста X = (x1,…,xl) и шифрованного текста y = (y1,…,yl) правила зашифрования и расшифрования шифра простой замены в алфавите A определяются формулами:
где k-1 — подстановка, обратная k.
В более общей ситуации для шифра простой замены X = ∪i=1LAi, Y = ∪i=1L1Bi, причем |A| = |B|, а K представляет собой множество всех биекций множества A на множество B. Правила зашифрования и расшифрования определяются для k ∈ K, x ∈ X, y ∈ Y (и обратной к k биекции k-1) формулами (1).
Определим еще один шифр, называемый шифром перестановки.
Определение. Пусть X = Y = AL и пусть K⊆SL, где SL— симметрическая группа подстановок множества {1,2,…,L}. Для любого ключа k, открытого текста x = (x1,…,xL) и шифрованного текста y = (y1,…,yL) правила зашифрования и расшифрования шифра перестановки определяются формулами:
где k-1 — подстановка, обратная k.
Шифры, введенные выше, являются представителями двух наиболее важных классов симметричных шифров, а именно шифров замены и шифров перестановок. Другими симметричными шифрами являются композиции (или последовательные применения) некоторых шифров замены и шифров перестановки.
Определим модель εA = (X, K, Y, E, D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах A и B соответственно: X ⊂ A*, Y ⊂ B*, |A| = n, |B| = m. Здесь и далее C* обозначает множество слов конечной длины в алфавите C.
Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из A* и B* соответственно.
Пусть U = {u1,…,uN} — множество возможных шифрвеличин, V = {v1,…,vM} — множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты x ∈ X, y ∈ Y можно было представить словами из U*, V* соответственно. Требование однозначности расшифрования влечет неравенства N ≥ n, M ≥ m, M ≥ N.
Для определения правила зашифрования Ek(x) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.
Поскольку M ≥ N, множество V можно представить в виде объединения V = ∪i=1NVi непересекающихся непустых подмножеств Vi. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V: V = ∪i=1NVα(i), α = 1,…,r, r ∈ N.
Заметим, что последнее обозначение, введенное в [1], представляется неудачным, поскольку речь идет уже не о представлении множества V, а о множестве таких представлений. Кроме того, согласно тексту, N не отрезок натурального ряда, а число, что препятствует записи r ∈ N. Вследствие изложенного, семейство разбиений предпочтительно записать в виде {∪i=1NVα(i)}, α = 1,…,r, r ∈ {1,2,…,N}, ∪i=1NVα(i) = V, Vα(i) ∩ Vα(j) = ∅, Vα(i) ≠ ∅.
Семейство биекций, соответствующее этому семейству разбиений множества V, обозначим через {φα}: V⇒{Vα(1),…,Vα(N)} и будем предполагать, что φα(ui) = Vα(i), i = 1,…,N.
Рассмотрим также произвольное отображение Φ: K×N ⇒ Nr*, где Nr = {1,2,…,r}, такое, что для любых k ∈ K, l ∈ N выполнено Φ(k,l) = a1(k)…al(k), aj(k) ∈ Nr, j = 1,…,r.
Назовем последовательность Φ(k,l) распределителем, отвечающим данным значениям k ∈ K, l ∈ N.
Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть x ∈ X, x = x1…xl, xi ∈ U, i = 1,…,l, k ∈ K и Φ(k,l) = a1(k)…al(k). Тогда Ek(x) = y, где y = y1…yl, yi ∈ φaj(k) (xj), j = 1,…,l.
В качестве yj можно выбрать любой элемент множества φaj(k)(xj). Всякий раз при шифровании этот выбор можно производить случайно. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, т. к. Vα(i) ∩ Vα(j) = ∅ при i ≠ j.
В модели произвольного шифра замены, приведенной выше, правило зашифрования Ek(x) является многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Ek(x) не слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров замены на однозначные и многозначные замены (называемых также омофонами).
Для однозначных шифров справедливо свойство: для любых α, i: |Vα(i)| = 1 для многозначных шифров — существуют α, i: |Vα(i)| > 1.
Наибольшее применение получили шифры однозначной замены. К ним в частности относится и рассмотренный ниже шифр гаммирования, играющий большую роль как в классической, так и в современной криптографии. Далее шифры замены будем считать однозначными. Тогда M = N и φa(ui) = va,i, i = 1,…,M.
Заметим, что правило зашифрования Ek естественным образом индуцирует отображение Ëk: U⇒V, которое в свою очередь продолжается до отображения Ëk: U*⇒V*. Для упрощения записи будем использовать одно отображение Ek для каждого из трех указанных отображений.
В силу инъективности (по k) отображения Ek и того, что |U| = |V|, введенные в общем случае отображения φα являются биекциями φα: U⇒V,V⇒U, определенными равенствами φα(ui) = vα(i), i = 1,…,N, α = 1,…,r. Число таких биекций не превосходит N!.
Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле yj ∈ φ(αj(k)) (xj), j = 1,…,l включение следует заменить равенством yj = φ(αj(k)) (xj), j = 1,…,l.
Введем еще ряд определений.
Если для некоторого числа q ∈ N выполняются включения vi ∈ Bq, i = 1,…,N, то соответствующий шифр будем называть шифром равнозначной замены. В противном случае — шифром разнозначной замены.
Иначе говоря, шифр равнозначной замены имеет шифробозначения из одинакового количества символов, шифр разнозначной замены, вообще говоря — из разного количества. Например, шифр Цезаря, сопоставляющий каждой букве ровно одну букву — равнозначный. А шифр, сопоставляющий некоторым буквам однозначное число, а другим двузначное — разнозначный.
В подавляющем большинстве случаев используются шифры замены, для которых U⊂Ap, для некоторого p ∈ N. При p = 1 говорят о поточных шифрах замены, при p > 1 — о блочных шифрах замены. Таким образом, поточные шифры замены предусматривают только однобуквенные шифрвеличины, блочные — многобуквенные.
Наконец, в случае r = 1 шифр замены называют одноалфавитным шифром замены, в противном случае — многоалфавитным шифром замены.
Для однозначных замен эти термины представляются не совсем удачными. Действительно, в этом случае алфавит шифробозначений — единственный с точностью до его нумерации, т. е. до порядка следования шифробозначений. Если, например, шифрвеличины и шифробозначения — буквы русского алфавита, то распределитель Φ указывает, в каком порядке следует расположить буквы для замены каждой шифрвеличины сообщения. Если для двух одинаковых шифрвеличин, расположенных в разных местах открытого текста, распределитель дает разные порядки букв алфавита шифробозначений, то одно и то же правило замены j переведет эти шифрвеличины в разные шифробозначения.
Воробьева Е., Лукьянова А.