Способы представления реализаций шифров

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

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

В таком виде может быть представлена принципиальная криптосхема поточного шифратора.

Управляющий блок предназначен для выработки управляющей последовательности шифрующим блоком. Шифрующий блок предназначен для зашифрования открытого текста с помощью управляющей последовательности.

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

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

Основные понятия теории автоматов

ОПРЕДЕЛЕНИЕ. Три конечных множества X,S,Y и два семейства отображений (h_x)_xÎX, (f_x)_xÎX, h_x:S®S, f_x: S®Y, xÎX называют конечным автоматом (конечным автоматом Мили) и обозначают через А=(X,S,Y,(h_x)_xÎX,(f_x)_xÎX).

Полагают, что автомат моделирует работу многих дискретных устройств, при этом множество X называют входным алфавитом автомата, S – множеством состояний, Y – выходным алфавитом автомата функции (h_x)_xÎX, (f_x)_xÎX называют, соответственно, частичными функциями переходов и выходов автомата. Автомат А функционирует в дискретном времени tÎ{1,2,…}. При входной последовательности P=x1,x2,…, xjÎX и начальном состоянии s=s₁ÎS автомат вырабатывает последовательность состояний А_М(s,P)=s₁,s₂,… (последовательно находится в состояниях s₁,s₂,…) и выходную последовательность А(s,P)=у₁,у₂,…. Правила получения этих последовательностей таковы:

s₂=h_x1s₁ – образ s₁ при отображении h_x1, s_j+1=h_xjs_j, jÎ{1,2,…},

у₁=f_x1s₁ – образ s₁ при отображении f_x1, у_j=f_xjs_j, jÎ{1,2,…}.

В случае f_x=f<sub>x`</sub> для любых x,x`ÎX автомат А называют автоматом Мура.

Автономным конечным автоматом называют двойку конечных множеств S, Y и два отображения: h:S®S и l:S®Y и обозначают через А=(S,Y,h,l). В ряде случаев используют и другое определение: Автомат А=(X,S,Y, (h_x)_xÎX, (f_x)_xÎX) называют автономным в случае, когда |X|=1.

Для автомата определяют его граф переходов: совокупность точек на плоскости, обозначенные состояниями автомата, некоторые из которых соединены ориентированными ребрами (стрелками ®). На ребре, соединяющим состояние s с состоянием s`, ставятся две пометки: x/у, где x и у определены из соотношений h<sub>x</sub>s=s`, f_xs=у. Переход из состояния в состояние по стрелкам называется путем в графе переходов автомата. Путь определяет последовательность состояний А_М(s,P) и выходную последовательность А(s,P), отвечающую входной последовательности P автомата A и его начальному состоянию s₁=sÎS.

Отметим, что задание семейства отображений (h_x)_xÎX, ((f_x)_xÎX)) равносильно заданию отображения h: X´S®S, h(x,s)=h_x(s) (аналогично, f: X´S®Y, f(x,s)=f_x(s)). В связи с чем, чаще автомат А определяют тремя множествами X,S,Y и двумя отображениями h, f: А=(X,S,Y, h, f).

Обозначим через X* множество всех слов конечной длины в алфавите X. Автомат А с начальным состоянием s задает отображение j_А,s X*®Y*, именно, для PÎX*

j_А,s(P)=A(s,P).

Такие отображения называются конечно-автоматными или просто автоматными.

При фиксированных множествах X, S, Y автомат задается отображениями h, f. При моделировании функционирования шифратора, или его криптосхемы конечным автоматом начальные состояния автомата моделируют так называемые части ключа, иногда и весь ключ, заключенный в памяти криптосхемы, часть же ключа «логики криптосхемы», иногда и весь ключ, моделируется выбором функций переходов h, f автомата. При этом полагают, что входными последовательностями автомата являются открытые тексты, подлежащие шифрованию, а выходные последовательности автомата трактуются как шифрованные тексты, соответствующие открытым текстам и ключам. При моделировании блочных шифров открытыми текстами являются начальные состояния автомата, ключами (раундовыми ключами) являются элементы алфавита X. Шифрованным текстом, который соответствует открытому тексту и последовательности P раундовых ключей, является заключительное состояние автомата, соответствующее начальному состоянию и входной последовательности P. Более полное представление об автоматах читатель может составить ознакомившись с материалами 2 тома пособия.

Шифрующий автомат. Понятие шифрующего автомата трактуется неоднозначно.

Первое определение состоит в том, что шифрующий автомат есть множество автоматов А(r), rÎR c начальными состояниями s(r)ÎS(r). Такое определение равносильно тому, что под шифрующим автоматом понимают некоторое множество автоматных отображений множества открытых текстов в шифрованные.

Второе определение шифрующего автомата состоит в том, что автомат А=(X,S,Y,(h_x)_xÎX,(f_x)_xÎX) является шифрующим автоматом, если его автоматные отображения j_А,s X*®Y*, sÎS являются инъективными отображениями. Такое определение согласуется с определением шифра (Х,К,У,f) в том смысле, что в качестве отображений f_c берутся автоматные инъективные отображения.

Для большей общности, иногда второе определение обобщают. Именно, рассматривают автоматы, у которых X=Г´@, где Г – алфавит внешней части ключа, часть ключа: g=g1,g2,…gL, gjÎГ; @ – алфавит открытого текста. При фиксированых частях ключа gÎГ^L и sÎS требуют инъективность отображения @^L в Y^L, то есть при входных различных последовательностях вида P=(a1,g1),(a2,g2),…(aL,gL) и P`= (a`1,g1), (a`2,g2),…(a`L,gL) требуют, чтобы А(s,P)¹А(s,P`) при любом натуральном L.

Выясним условия, при которых автомат А=(X,S,Y,h,f) является шифрующим автоматом, то есть автоматные отображения j_А,s X*®Y*, sÎS являются инъективными отображениями. Для отображения f: X´S®Y обозначим через f_s отображение X в Y: f_s(x)=f(x,s). Через S_s обозначим множество состояний автомата А, содержащее s и все состояния s`ÎS, достижимые из s в графе переходов автомата А, то есть для которых есть пути из s в s`. На множестве S_s определен подавтомат А_s=(X,S_s,Y,h,f) автомата А (здесь ограничения отображений h, f обозначены теми же буквами). С использованием введенных определений несложно доказывается.

УТВЕРЖДЕНИЕ. Автоматное отображение j_А,s X*®Y*, sÎS является инъективным тогда и только тогда, если при каждом состоянии s` из S<sub>s</sub> отображение f<sub>s`</sub> инъективно.

В третьем определении под шифрующим автоматом понимают автомат, моделирующий устройство шифрования, либо некоторого его блока. В таком понимании устройство шифрования моделируют автоматом А=(X,S,Y,(h_x)_xÎX,(f_x)_xÎX), у которого отображения (h_x)_xÎX S в S являются биекциями S в S. Такие автоматы обычно называют перестановочными. Часто гаммообразующее устройство шифратора называют шифрующим автоматом.

Эквивалентность ключей шифрующего автомата.

ОПРЕДЕЛЕНИЕ. Состояния s,s` автомата А называются неотличимыми, если

А(s,P)=A(s`,P)

при любом входном слове PÎI*.

Автомат А называется приведенным, если он не имеет различных неотличимых состояний.

Ключи s,s` шифрующего автомата А называются эквивалентными, если s,s` – неотличимые состояния автомата А.

Глава 2.