Stream and finite automaton ciphersystems.pdf Ранее в работе автора [1] были определены понятия поточной шифрсистемы и са-мосинхронизирующихся с задержкой поточной и регистровой шифрсистем и было показано,что последними исчерпываются все поточные самосинхронизирующиеся системы,у которых проекции генератора ключевого потока являются сильносвязнымиавтоматами. В настоящей работе определяются ещё и понятия автоматной и самосин-хронизирующейся с задержкой автоматной шифрсистем и устанавливается, что регистровыми шифрсистемами исчерпываются также и автоматные самосинхронизирую-щиеся системы с сильносвязными проекциями автомата расшифрования (теорема 3).Более того, установлено, что классы поточных и автоматных шифрсистем функциональноэквивалентны (теорема 1), а именно: для каждой системы любого из этихклассов существует система в другом классе, которая задаёт то же семейство последовательностныхшифров, что и первая. Наконец, как альтернатива конструктивномуопределению понятия поточной самосинхронизирующейся шифрсистемы в [1] здесьдаётся дескриптивное определение этого понятия и показывается равносильность обоихопределений (теорема 2).Условимся конечный автомат (Мили) с входным алфавитом X , выходным алфавитомY , множеством состояний Q и функциями переходов и выходов ф : Q х X ^ Qи : Q х X ^ Y соответственно обозначать набором A = < X, Q,Y, ф, ^ >. В нёмфункции ф и - конечный автомат, называемыйгенератором ключевого потока (ГКП), такой, что любая его проекция Gk естьавтомат Мура, e : X х Г ^ Y , d : Y х Г ^ X - правила шифрования и расшифрованияодного символа открытого текста (сообщения) с помощью одного символа ключевогопотока (гаммы), связанные отношением обратимости:Vy Е rVx Е XVy Е Y[e(x, y ) = у ^ d ^ ,Y ) = x].Определим в функции E : Q х X * х K ^ Y * и D : Q х Y * х K ^ X * - соответственноправила шифрования и расшифрования сообщений по ключу и начальномусостоянию - по следующим формулам:E(q0, Л, k) = Л,{ Yt = № Ы ,у* = e(xt,Yt), t = 0 ,1 , . . . ,n - 1;qt+1 = ф ^ у ^D(q0, Л, k) = Л,{ Yt = t oxt = d(yt,Yt), t = 0 ,1 , .. ., n - 1.qt+i = (qt,Уt),По определению функций E и D легко проверить, что при любых G, q . Q, e и d,где e и d связаны отношением обратимости, пятерка Sq(S) = < X , Y, K, Eq, Dq >, где Eqи Dq - функции соответственно E и D с фиксированным значением первого аргументаq . Q, будет последовательностным шифром. Множество {S q(S) | q . Q } всех такихшифров называется далее семейством последовательностных шифров, задаваемыхшифрсистемой Ss.Определение 3. Назовём автоматной шифрсистемой пятерку объектов= < X ,Y ,K ,A e,A d >, где Ae = < X х K, Q, Y ,^ ,^ > и Ad = < Y х K ,Q * ,X ,^ * ,^ * >суть конечные приведённые автоматы, называемые автоматами шифрования и расшифрованиясоответственно, если для любого состояния q . Q найдется такое состояниеq* . Q*, что пятерка Sqq* (A) = < X , Y, K, самосинхронизирую-щимся с задержкой т , если выполняется условиеVq . QVx,x; . X *Vx . X TVu . X*[, что для любого значения k Е Kего проекция Rk = < Y, Y т , Г, ak, ^ > на вход Y есть регистр сдвига длиной т .Определение 10 [1]. Назовём поточную шифрсистему S r = < X , K , Y, R, е,5 >регистровой, если её ГКП R есть регистр сдвига с ключом. Длина регистра R называетсяразмерностью шифрсистемы.Регистровая шифрсистема размерностью т является самосинхронизирующейсяс задержкой т по конструктивному определению.Определение 11. Назовём автоматную шифрсистему Sa = < X, Y, K, Ae,A d >самосинхронизирующейся с задержкой т , если таковой является проекция Ak автоматаAd для любого k Е K :Vq0 Е Q*Vy ^ ' Е Y *Vy Е Е Y *[й (ф*№ у у),и) = . k (^ (q oW ^ w )].Говорят, что некоторая шифрсистема неотличима от шифрсистемы S, если задаваемыеею последовательностные шифры задаются системой S.Теорем а 3. Любая самосинхронизирующаяся с задержкой т автоматная шифр-система S a = < X , K , Y, Ae ,A d >, у которой все проекции Ak автомата расшифрованияAd суть сильно связные автоматы, неотличима от некоторой регистровой шифр-системы S r = < X , K, Y, R, е, 5 > размерности т .

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