Finite automata in cryptography.pdf ВведениеКонечные автоматы в криптографии распространены столь же широко, сколь и,скажем, целые числа, подстановки, булевы функции. Достаточно заметить, что всепоточные шифры, ориентированные на аппаратную реализацию, допускают конструктивноеописание как конечные автоматы канонической системой уравнений. Многочисленныепримеры таких описаний поточных шифров конца прошлого века и их примененияв криптоанализе можно найти, в частности, в [1, 2]. Вместе с тем в открытойнаучной литературе по современной криптографии конечные автоматы ещё не получилитакого же широкого отражения, какое имеют другие дискретные структуры -те же целые числа или булевы функции. Особенно это касается теории автоматныхкриптосистем. Так, в отечественной литературе постсоветского периода можно указатьлишь два источника монографического характера [3, 4], в которых хоть как-тоупоминаются шифрующие автоматы.В построении криптосистем конечные автоматы находят применение как в ролиотдельных их компонент, начиная с регистров сдвига, так и в качестве полнофункциональныхкриптоалгоритмов - шифрования, цифровой подписи и т. п. В одних криптосистемахони выступают в чистом виде, в других - как криптографические автоматы(коротко: криптоавтоматы), конечно-автоматное поведение которых определяется ещёи в зависимости от ключа, выбираемого из некоторого конечного множества. Ключомкриптоавтомата могут быть и начальное состояние автомата, и некоторые элементыего таблиц переходов и выходов или сами эти таблицы - одна или обе сразу, и др.В этой работе приводятся из открытой литературы последнего времени примерыупотребления конечных автоматов и криптоавтоматов в роли генераторов ключевогопотока и схем комбинирования (комбайнеров) в них, излагаются принципы построенияклеточно-автоматных генераторов псевдослучайных последовательностей и ключевогопотока и клеточно-автоматных хеш-функций, описываются конечно-автоматные симметричныешифры и криптосистемы с открытым ключом, демонстрируется функциональнаяэквивалентность поточных и автоматных шифрсистем и неотличимость са-мосинхронизирующихся таких систем от регистровых. Вопросы, относящиеся к криптоанализу,здесь не затрагиваются.Предполагается знакомство читателя с основами теории автоматов и криптографии.В изложении, касающемся элементов теории автоматов, придерживаемся терминологиии обозначений из [5], а в употреблении криптографических понятий следуемза [6]. Кроме того, для любой функции f , для любого подмножества U её аргументови для любого набора о значений этих аргументов через f обозначается функция (отостальных аргументов f ), которая получается из f подстановкой под её знак вместоаргументов в U их значений в наборе о.Конечный (полностью определённый) автомат M с множествами входных символовX , выходных символов Y и состояний Q и с функциями переходов ф : X х Q ^ Qи выходов ^ : X х Q ^ Y записывается как M = < X , Q, Y, ф, . В нём зависимостьмежду входными символами, состояниями и выходными символами в дискретном времениt выражается системой канонических уравненийгде q(1) -начальное состояние автомата. Если здесь a = x (1 )x (2 ). ..x (m ), в == y (1 )y (2 ). .. y(m) и 8 = q(2)q(3). .. q(m + 1), то пишем: 8 = ф (а ^ (1 )) -последовательностьсостояний, которую автомат M пробегает из состояния q(1) под действиемвходного слова а; в = ^ (a ,q (1)) -выходное слово, которое он при этом вырабатывает;q(m + 1) = ф ( а ^ ( 1)) - состояние, в которое он при этом переходит,и y(m) = 1 и хотя быодна из его функций зависит существенно от k° E К°. За таким криптоавтоматоместественно сохранить обозначение произвольного криптоавтомата, но в отличие отГy j(t) = ^ j(qi(t)q2( t ) ...qfc(t) ) j = 1 ^ . . . m\qi(t + 1) = фг(^1 (t)q2( t ) . .. qfc(t)), i = 1, 2, . . . k,Если в M функция , где G == и G' = , если выполняется следующееусловие:Vk E KVq E Q3q' E Q'Va E X*[eq(a , k) = e'q,(a , k)].Заметим, что неотличимость двух поточных шифрсистем друг от друга в этомсмысле вовсе не означает равенства семейств задаваемых ими последовательностныхшифров. Это было бы так, если бы вместо неотличимости рассматриваемых шифрсистемречь шла об их сильной неотличимости, где Es сильно неотличима от ES, есливыполнено условиеVq E Q3q' E Q'Vk E KVa E X*[eq(a, k) = e'q,(a, k)].Последнее отличается от предыдущего только порядком применения кванторов и означаеткак раз включение S(Es) С S(ES). Поскольку для любого предиката P(a,b) из3aVbP(a,b) следует Vb3aP(a,b), но не наоборот, то сильная неотличимость (=) шифр-систем влечет их неотличимость ( ) , а обратного может не быть. Таким образом,S(Es) = S(ES) ^ (Es = ES) и S(Es) = S(ES) ^ (Es « ES).Определение 4. Будем говорить, что ГКП G = неотличимот ГКП G' = -две шифрсистемыс разными ГКП G и G'. Тогда если G неотличим от G', то и Es неотличимаот e s .Доказательство. Пусть G = , G' =

Скачать электронную версию публикации