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

Одним из первых ввел и систематически исследовал простую и естественную математическую модель шифра К. Шеннон. Эту модель можно найти, например, в его книге «Работы по теории информации и кибернетике», 1963 [5] (раздел «Теория связи в секретных системах»). Он рассматривал так называемые «секретные системы», в которых смысл сообщения скрывается при помощи шифра или кода, но само шифрованное сообщение не скрывается, и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи передаваемых сигналов.

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

Ядром секретной системы является собственно шифр.

Пусть имеются три конечных множества:

M – множество открытых текстов (открытых сообщений),

К – множество ключей и

C – множество шифрованных сообщений (криптограмм).

Пусть на прямом произведении множеств МхК задано отображение (функция) Е:

Е _k: МхК ® С E _k (m)= c, где m Î M, k Î K, c Î C.

Определение. Алгебраической моделью шифра (криптосистемой с секретным ключом или симметричной криптосистемой) называется трехосновная универсальная алгебра

А=(М,К,С,Е),

если выполнены два условия:

1. функция E _k сюрьективна (осуществляет отображение на С).

2. " k Î K функция E _k инъективна (образы двух различных элемен­тов различны).

Требование инъективности отображений (E _k) _{k ÎK} в определении шиф­ра равносильно требованию возможности однозначного дешифрова­ния криптограммы (однозначного восстановления открытого текста по из­вестным шифртексту и ключу). Из инъективности вытекает, что |М|<|С|.

Требование же сюрьектавности отображений E _k не играет сущест­венной роли и обычно вводится для упрощения (с точки зрения математи­ки) изложения; в ряде случаев оно опускается.

Запись E _k (m)= c называется уравнением шифрования. Имеется в виду, что сообщение m зашифровывается шифром на ключе k и получается шифрованный текст с.

Уравнением дешифрования называют запись D _k (с)=E _k ^-1(с)= m, подразуме­вая, что шифрованный текст c = E _k (m) дешифруется на ключе k и по­лучается исходное открытое сообщение m.

Предполагается, что функции шифрования/дешифрования эффек­тивно строятся по ключу k и

" m Î M и " k Î K выполнено D _k (E _k (m))= m.

Все элементы криптосистемы привязаны к конкретному ключу из пространства ключей данной криптосистемы.

Для сокращения записи будут использоваться также обозначения:

k (m)=E _k (m) – шифрование ключом k,

k^-1 (с)=D _k (с) – дешифрование ключом k.

Таким образом математически криптосистема определяется как не­которое множество отображений пространства сообщений в пространст­во шифрограмм. Каждое конкретное отображение из этого множества соответствует способу шифрования при помощи конкретного ключа k.

Произведением шифров A₁=(М₁,К₁,С₁,Е₁) и A₂=(М₂,К₂,С₂,Е₂) называется шифр A₁=(М₁,К₁ х К₂,С₂,Е), для которого

Е(m, (k₁,k₂)) = Е₂(Е₁(m, k₁) ,k₂), (k₁,k₂) Î К ₁х К₂.

Введенная модель шифра отражает лишь функциональные свойства шифрования и дешифрования в классических симметричных системах шифрования. Здесь текст – элемент абстрактного множества, без учета алфавита языка, его статистических свойств и т.д. Необходима его дальнейшая детализация.

Важным классом шифров являются так называемые транзитивные шифры. Шифр A=(М,К,С,Е) называют транзитивным, если " m Î M и " с Î С найдется k Î K, при котором E(m,k)= c, то есть это уравнение разрешимо относительно ключа при любых парах (m,c).

Исходя из введенных определений, легко доказать, что для транзитивного шифра | М |≤| С |≤| К |. Транзитивный шифр, для которого | М |=| К |, называют минимальным шифром.

Другой важный класс шифров представляют эндоморфные (термин введенный Шенноном) шифры. Это шифр A=(М,К,С,Е), для которого множес­тво открытых текстов М совпадает с множеством криптограмм С. Для таких шифров каждое преобразование E _k (m), k Î K является биекцией М в М или подстановкой на М. Множество таких биекций обозначают через П(К,Е)={E _k: k Î K }, а сам эндоморфный шифр обозна­ча­­ют A=(М,П(К,Е)) и называют подстановочной моделью эндоморфного шифра. При этом под ключом шифра понимают биекцию pÎП(К,Е).

Уравнение шифрования записывают в виде p m=c,

уравнение дешифрования записывают в виде p^-1 с=m.