Анализ автомата Спротта над конечным кольцом

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Труды Института прикладной математики и механики
Дата:	2010
Автор:	Скобелев, В.Г.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут прикладної математики і механіки НАН України 2010
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/123967
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Анализ автомата Спротта над конечным кольцом / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 194-199. — Бібліогр.: 4 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-123967
record_format	dspace
spelling	Скобелев, В.Г. 2017-09-15T17:26:40Z 2017-09-15T17:26:40Z 2010 Анализ автомата Спротта над конечным кольцом / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 194-199. — Бібліогр.: 4 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/123967 519.7+681.3 Над конечным ассоциативно-коммутативным кольцом с единицей исследуется автомат, построенный на основе 1-й хаотической динамической системы Спротта. Для исследуемой модели охарактеризованы классы эквивалентных состояний, решена задача параметрической идентификации. Получены соотношения характеризующие вариацию поведения исследуемого автомата при вариации его начального состояния. Над скінченним асоціативно-комутативним кільцем з одиницею досліджено автомат, який отримано на основі 1-ї хаотичної динамічної системи Спротта. Для досліджуваної моделі охарактеризовано класи еквівалентних станів, розв'язано задачу параметричної ідентифікації. Отримано співвідношення, які характеризують варіацію поведінки досліджуваного автомата при варіації його початкового стану. It is analyzed the automaton over a finite associative-commutative ring with the unit designed on the base of the first chaotic dynamical Sprott’s system. For investigated model it is characterized classes of equivalent states and solved the problem of parametric identification. Formula characterizing variation of behavior of the investigated automaton under condition of variation of its initial state are established. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Анализ автомата Спротта над конечным кольцом Аналіз автомата Спротта над скінченним кільцем Analysis of Sprott’s automaton over some finite ring Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Анализ автомата Спротта над конечным кольцом
spellingShingle	Анализ автомата Спротта над конечным кольцом Скобелев, В.Г.
title_short	Анализ автомата Спротта над конечным кольцом
title_full	Анализ автомата Спротта над конечным кольцом
title_fullStr	Анализ автомата Спротта над конечным кольцом
title_full_unstemmed	Анализ автомата Спротта над конечным кольцом
title_sort	анализ автомата спротта над конечным кольцом
author	Скобелев, В.Г.
author_facet	Скобелев, В.Г.
publishDate	2010
language	Russian
container_title	Труды Института прикладной математики и механики
publisher	Інститут прикладної математики і механіки НАН України
format	Article
title_alt	Аналіз автомата Спротта над скінченним кільцем Analysis of Sprott’s automaton over some finite ring
description	Над конечным ассоциативно-коммутативным кольцом с единицей исследуется автомат, построенный на основе 1-й хаотической динамической системы Спротта. Для исследуемой модели охарактеризованы классы эквивалентных состояний, решена задача параметрической идентификации. Получены соотношения характеризующие вариацию поведения исследуемого автомата при вариации его начального состояния. Над скінченним асоціативно-комутативним кільцем з одиницею досліджено автомат, який отримано на основі 1-ї хаотичної динамічної системи Спротта. Для досліджуваної моделі охарактеризовано класи еквівалентних станів, розв'язано задачу параметричної ідентифікації. Отримано співвідношення, які характеризують варіацію поведінки досліджуваного автомата при варіації його початкового стану. It is analyzed the automaton over a finite associative-commutative ring with the unit designed on the base of the first chaotic dynamical Sprott’s system. For investigated model it is characterized classes of equivalent states and solved the problem of parametric identification. Formula characterizing variation of behavior of the investigated automaton under condition of variation of its initial state are established.
issn	1683-4720
url	https://nasplib.isofts.kiev.ua/handle/123456789/123967
citation_txt	Анализ автомата Спротта над конечным кольцом / В.Г. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 194-199. — Бібліогр.: 4 назв. — рос.
work_keys_str_mv	AT skobelevvg analizavtomatasprottanadkonečnymkolʹcom AT skobelevvg analízavtomatasprottanadskínčennimkílʹcem AT skobelevvg analysisofsprottsautomatonoversomefinitering
first_indexed	2025-11-26T21:27:15Z
last_indexed	2025-11-26T21:27:15Z
_version_	1850773197073416192
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2010. Том 21 УДК 519.7+681.3 c©2010. В.Г. Скобелев АНАЛИЗ АВТОМАТА СПРОТТА НАД КОНЕЧНЫМ КОЛЬЦОМ Над конечным ассоциативно-коммутативным кольцом с единицей исследуется автомат, построен- ный на основе 1-й хаотической динамической системы Спротта. Для исследуемой модели охарак- теризованы классы эквивалентных состояний, решена задача параметрической идентификации. Получены соотношения,характеризующие вариацию поведения исследуемого автомата при вариа- ции его начального состояния. Ключевые слова: конечные кольца, конечные автоматы, эквивалентные состояния, парамет- рическая идентификация. 1. Введение. Защита информации является одной из актуальных проблем со- временных информационных технологий. Для решения этой проблемы предназна- чено шифрование информации. При построении почти всех кандидатов на совре- менный стандарт поточного шифрования используются вычисления в кольцах вы- четов. Это обстоятельство является обоснованием актуальности систематического исследования автоматов над конечными кольцами. Автономные автоматы над конечными ассоциативно-коммутативными кольцами с единицей систематически исследованы в [1], а линейные и нелинейные автоматы общего вида – в [2]. В последнее время осуществлялись многочисленные попытки применения хао- тических динамических систем [3] при решении задач преобразования информации. Непосредственное использование таких систем обнажило целый комплекс проблем, связанных с устойчивостью поведения и точностью вычислений. Для нивелирова- ния последней проблемы достаточно перейти к вычислениям в конечной алгебраи- ческой системе. В качестве такой алгебраической системы естественно выбрать ко- нечное кольцо, так как наличие делителей нуля автоматически приводит к поиску в процессе решения уравнений. Таким образом, построение аналогов над конечным кольцом для модельных хаотических динамических систем является мощным ис- точником автоматов над конечным кольцом. Один из таких автоматов, а именно, автомат, построенный на основе 1-й хаотической динамической системы Спротта и исследуется в настоящей работе. 2. Автомат Спротта. Первая хаотическая динамическая система Спротта име- ет следующий вид [3]:    ẋ = y ẏ = −x + yz ż = 1− y2 . Внесем информационную переменную в 1-е уравнение и перейдем к действиям в конечном ассоциативно-коммутативном кольце с единицей K = (K, +, ·). После 194 автомат Спротта переобозначения переменных получим автомат MS :    q (1) t+1 = q (1) t + hq (2) t − haxt+1 q (2) t+1 = q (2) t − hq (1) t + hq (2) t q (3) t q (3) t+1 = h + q (3) t − h(q(2) t )2 yt+1 = q (1) t+1 (t ∈ Z+), (1) где a, h – обратимые элементы кольца K. Автомат MS допускает обращение. Обратный автомат имеет следующий вид: M−1 S :    q (1) t+1 = xt+1 q (2) t+1 = q (2) t − hq (1) t + hq (2) t q (3) t q (3) t+1 = h + q (3) t − h(q(2) t )2 yt+1 = (ha)−1(q(1) t + hq (2) t − xt+1) (t ∈ Z+). Пара инициальных автоматов ((MS ,q0), (M −1 S ,q0)) (q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T ) опре- деляет поточный шифр. А так как в процессе «шифрование-расшифрование» авто- маты MS и M−1 S движутся в пространстве состояний по одной и той же траектории в одном и том же направлении, то достаточно исследовать только свойства автомата MS . 3. Классы эквивалентных состояний автомата Спротта. Установим кри- терий эквивалентности состояний автомата Спротта MS . Теорема 1. Состояния q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T и q̃0 = (q̃(1) 0 , q̃ (2) 0 , q̃ (3) 0 )T автомата MS эквивалентны тогда и только тогда, когда    q̃ (1) 0 − q (1) 0 + h(q̃(2) 0 − q (2) 0 ) = 0 q̃ (2) 0 − q (2) 0 − h(q̃(1) 0 − q (1) 0 ) + h(q̃(2) 0 q̃ (3) 0 − q (2) 0 q (3) 0 ) = 0 q̃ (2) t q̃ (3) t − q (2) t q (3) t = 0 (t = 1, . . . , \|K3\| − 3) (2) для всех x1 . . . xt ∈ Kt. Доказательство. Состояния q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T и q̃0 = (q̃(1) 0 , q̃ (2) 0 , q̃ (3) 0 )T автома- та MS эквивалентны тогда и только тогда, когда yt = ỹt ⇔ q̃ (1) t − q (1) t = 0 (3) для всех x1 . . . xt ∈ Kt (t = 1, . . . , \|K\|3 − 1). Представим систему уравнений (3) в виде q̃ (1) 1 − q (1) 1 = 0, (4) q̃ (1) t − q (1) t = 0 (t = 2, . . . , \|K\|3 − 1). (5) 195 В.Г. Скобелев Из 1-го уравнения системы (1) вытекает, что (4) и (5) эквивалентны уравнениям q̃ (1) 0 − q (1) 0 + h(q̃(2) 0 − q (2) 0 ) = 0, (6) q̃ (1) t − q (1) t + h(q̃(2) t − q (2) t ) = 0 (7) для всех x1 . . . xt ∈ Kt (t = 1, . . . , \|K\|3 − 2). А так как h ∈ K – обратимый элемент кольца K, то уравнения (7) эквивалентны уравнениям q̃ (2) t − q (2) t = 0 (8) для всех x1 . . . xt ∈ Kt (t = 1, . . . , \|K\|3 − 2). Из 2-го уравнения системы (1) находим, что q̃ (2) t − q (2) t = (q̃(2) t−1 − q (2) t−1)− h(q̃(1) t−1 − q (1) t−1) + h(q̃(2) t−1q̃ (3) t−1 − q (2) t−1q (3) t−1) (9) для всех x1 . . . xt ∈ Kt (t = 1, . . . , \|K\|3 − 2). Из (8) в (9) вытекает, что (q̃(2) 0 − q (2) 0 )− h(q̃(1) 0 − q (1) 0 ) + h(q̃(2) 0 q̃ (3) 0 − q (2) 0 q (3) 0 ) = 0, (10) q̃ (2) t q̃ (3) t − q (2) t q (3) t = 0 (11) для всех x1 . . . xt ∈ Kt (t = 1, . . . , \|K\|3 − 3). Уравнения (6), (10) и (11) и составляют систему уравнений (2). ¤ Следствие 1. Состояния q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T и q̃0 = (q̃(1) 0 , q̃ (2) 0 , q̃ (3) 0 )T автомата MS являются близнецами тогда и только тогда, когда    q̃ (1) 0 = q (1) 0 − h∆ q̃ (2) 0 = q (2) 0 + ∆ q̃ (3) 0 = q (3) 0 + 2hq (2) 0 ∆ + h∆2, (12) где ∆ – решение уравнения ∆3 + 3q (2) 0 ∆2 + (2(q(2) 0 )2 + h−1q (3) 0 + 1 + h−2)∆ = 0. (13) Доказательство. Состояния q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T и q̃0 = (q̃(1) 0 , q̃ (2) 0 , q̃ (3) 0 )T автома- та MS являются близнецами тогда и только тогда, когда q̃ (i) 1 − q (i) 1 = 0 (i = 1, 2, 3). (14) При i = 1 получим уравнение (6), а при i = 2 – уравнение (10). Кроме того, из 3-го уравнения системы (1) вытекает, что q̃ (3) 1 − q (3) 1 = 0 ⇔ q̃ (3) 0 − q (3) 0 − h((q̃(2) 0 )2 − (q(2) 0 )2) = 0. 196 автомат Спротта Следовательно, уравнения (14) имеют следующий вид:    q̃ (1) 0 − q (1) 0 + h(q̃(2) 0 − q (2) 0 ) = 0 q̃ (2) 0 − q (2) 0 − h(q̃(1) 0 − q (1) 0 ) + h(q̃(2) 0 q̃ (3) 0 − q (2) 0 q (3) 0 ) = 0 q̃ (3) 0 − q (3) 0 − h((q̃(2) 0 )2 − (q(2) 0 )2) = 0 . (15) Положив    q̃ (1) 0 = q (1) 0 + ∆1 q̃ (2) 0 = q (2) 0 + ∆ q̃ (3) 0 = q (3) 0 + ∆3 (16) и подставив (16) в (15), получим    ∆1 + h∆ = 0 ∆− h∆1 + h(q(3) 0 ∆ + q (2) 0 ∆3 + ∆∆3) = 0 ∆3 − h∆(2q (2) 0 + ∆) = 0 . (17) Из 1-го и 3-го уравнений системы (17) находим { ∆1 = −h∆ ∆3 = h∆(2q(2) 0 + ∆) . (18) Подставив (18) во 2-е уравнение системы (17), получим, что ∆ – решение урав- нения h2∆3 + 3h2q (2) 0 ∆2 + (2h2(q(2) 0 )2 + hq (3) 0 + h2 + 1)∆ = 0. (19) А так как h ∈ K – обратимый элемент кольца K, то уравнение (19) эквивалентно уравнению (13). ¤ 4. Параметрическая идентификация автомата Спротта. Вначале предпо- ложим, что экспериментатор полностью управляет входным каналом автомата MS , а также может устанавливать автомат MS в любое требуемое начальное состояние сколько угодно раз. Такие предположения соответствуют одной из наиболее силь- ных атак на соответствующий поточный шифр. Положив q0 = (0, 1, 0)T и x1 = 0, получим h = y1. Положив q0 = (0, 0, 0)T и x1 = 1, получим a = −h−1y1. Таким образом, при сделанных предположениях задача параметрической иден- тификации автомата MS тривиальна. Теперь предположим, что экспериментатор не располагает возможностью уста- навливать автомат MS в требуемое состояние, но может проводить с автоматом MS , по крайней мере, двухкратный классический эксперимент. Подав на автомат MS входной символ x1 = 0, получим уравнение y1 = q (1) 0 + hq (2) 0 , (20) 197 В.Г. Скобелев а подав входной символ x1 = 1 – уравнение ỹ1 = q (1) 0 + hq (2) 0 − ha. (21) Вычитая (21) из (20), получим ha = y1 − ỹ1. (22) Если экспериментатору известны компоненты q (1) 0 и q (2) 0 начального состояния автомата MS , то из уравнения (20) находится параметр h, а из уравнения (22) – параметр a, т.е. в этом случае задача параметрической идентификации автомата MS также тривиальна. Ситуация изменяется, если экспериментатору не известны компоненты q (1) 0 и q (2) 0 начального состояния автомата MS , так как решение нелинейного уравнение (22) эквивалентно поиску всех разложений элемента y1 − ỹ1 ∈ K на два сомножителя, являющиеся обратимыми элементами кольца K с последующим различением всех возможных кандидатов на автомат MS методами классической теории эксперимен- тов с автоматами [4], а любая попытка увеличения высоты эксперимента автомати- чески приводит к нелинейной системе уравнений для поиска значения h. Таким образом, поиск секретного ключа (q(1) 0 , q (2) 0 , q (3) 0 , a, h) для поточного шифра ((MS ,q0), (M −1 S ,q0)) является сложной задачей, если экспериментатор не распола- гает возможностью устанавливать автомат MS в требуемое состояние. 5. Вариация поведения автомата Спротта. Пусть, что для автомата MS осуществляется переход от начального состояния q0 = (q(1) 0 , q (2) 0 , q (3) 0 )T к начальному состоянию q̃0 = (q̃(1) 0 , q̃ (2) 0 , q̃ (3) 0 )T . Подставив q̃0 в систему уравнений (1), получим MS :    q̃ (1) t+1 = q̃ (1) t + hq̃ (2) t − haxt+1 q̃ (2) t+1 = q̃ (2) t − hq̃ (1) t + hq̃ (2) t q̃ (3) t q̃ (3) t+1 = h + q̃ (3) t − h(q̃(2) t )2 ỹt+1 = q̃ (1) t+1 (t ∈ Z+). (23) Вычитая из (23) соответствующие уравнения системы (1), получим    ∆q (1) t+1 = ∆q (1) t + h∆q (2) t ∆q (2) t+1 = (1 + hq (3) t )∆q (2) t + h(q(2) t + ∆q (2) t )∆q (3) t − h∆q (1) t ∆q (3) t+1 = ∆q (3) t − h(2 + ∆q (2) t )∆q (2) t ∆yt+1 = ∆q (1) t+1 (t ∈ Z+), (24) где ∆q (i) t = q̃ (i) t − q (i) t (i = 1, 2, 3) и ∆yt+1 = ỹt+1 − yt+1 для всех t ∈ Z+. Таким образом, вариация поведения автомата Спротта MS при переходе от на- чального состояния q0 к начальному состоянию q̃0 характеризуется системой урав- нений (24). 198 автомат Спротта 6. Заключение. В работе исследован автомат Спротта MS над конечным ассоциативно-коммутативным кольцом с единицей, являющийся аналогом соответ- ствующей модельной хаотической динамической системы. Исследование классов эквивалентных состояний автомата MS показало, что эти классы имеют достаточно сложную структуру. Поэтому, любые попытки минимиза- ции автомата Спротта MS приведут к существенному усложнению модели. На это обстоятельство также указывает сложность соотношений, описывающих вариацию поведения автомата MS при изменении его начального состояния. Дальнейшее исследование автомата MS может быть связано с решением задачи идентификации его начального состояния. Другое направление связано с исследо- ванием сложности анализа автомата MS в зависимости от значений его параметров. Третье направление связано с исследованием автоматов, построенных для осталь- ных систем Спротта. 1. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Свойства линейных и полилинейных рекуррент над кольцами Галуа (I) // Труды по дискретной математике. Т.2. / Под общей редакцией В.Я. Козлова. – М.: ТВП, 1998. – С. 191-222. 2. Скобелев В.В., Скобелев В.Г. Анализ шифрсистем. – Донецк: ИПММ НАНУ, 2009. – 479 c. 3. Кузнецов С.П. Динамический хаос. – М: Физматлит, 2001. – 296 c. 4. Гилл А. Введение в теорию конечных автоматов. – М: Наука, 1966. – 272 c. V.G. Skobelev Analysis of Sprott’s automaton over some finite ring. It is analyzed the automaton over a finite associative-commutative ring with the unit designed on the base of the first chaotic dynamical Sprott’s system. For investigated model it is characterized classes of equivalent states and solved the problem of parametric identification. Formula characterizing variation of behavior of the investigated automaton under condition of variation of its initial state are established. Keywords: finite rings, finite automata, equivalent states, parametric identification. В.Г. Скобелєв Аналiз автомата Спротта над скiнченним кiльцем. Над скiнченним асоцiативно-комутативним кiльцем з одиницею дослiджено автомат, який отри- мано на основi 1-ї хаотичної динамiчної системи Спротта. Для дослiджуваної моделi охаракте- ризовано класи еквiвалентних станiв, розв’язано задачу параметричної iдентифiкацiї. Отримано спiввiдношення, якi характеризують варiацiю поведiнки дослiджуваного автомата при варiацiї йо- го початкового стану. Ключовi слова: скiнченнi кiльця, скiнченнi автомати, еквiвалентнi стани, параметрична iден- тифiкацiя. Ин-т прикл. математики и механики НАН Украины, Донецк skbv@iamm.ac.donetsk.ua Получено 27.10.10 199

Анализ автомата Спротта над конечным кольцом

Репозитарії

Схожі ресурси