Аналіз free-running автомата над кінцевим кільцем
The analog over the finite ring of chaotic dynamical free-running system is investigated. The structure of the model under investigation is characterized in terms of automaton theory. Problems of parametric identification and identification of the initial state are solved. The structure of fixed poi...
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2010
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/106956 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866301923710205952 |
|---|---|
| author | Skobelev, V. V. |
| author_facet | Skobelev, V. V. |
| author_sort | Skobelev, V. V. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-06T12:28:40Z |
| description | The analog over the finite ring of chaotic dynamical free-running system is investigated. The structure of the model under investigation is characterized in terms of automaton theory. Problems of parametric identification and identification of the initial state are solved. The structure of fixed points in the mapping realized by the initial automaton is characterized. |
| first_indexed | 2025-07-17T10:21:53Z |
| format | Article |
| fulltext |
© В.В. Скобелев, 2010
130 ISSN 1681–6048 System Research & Information Technologies, 2010, № 3
УДК 518.6+681.3
АНАЛИЗ FREE−RUNNING АВТОМАТА НАД КОНЕЧНЫМ
КОЛЬЦОМ
В.В. СКОБЕЛЕВ
Исследован аналог над конечным кольцом хаотической динамической free-
running системы. С позиции теории автоматов охарактеризована структура ис-
следуемой модели. Решены задачи параметрической идентификации и иден-
тификации начального состояния. Охарактеризована структура множества не-
подвижных точек словарной функции, реализуемой инициальным автоматом.
ВВЕДЕНИЕ
Успешное применение хаотических динамических систем при решении за-
дач преобразования информации [1, 2] делает привлекательной разработку
на их основе высокоскоростных вычислительно стойких поточных шифров.
В простейшем случае построение такого шифра на основе динамической
системы
),( axf
dt
xd
= , (1)
(где nT
n Rxxx ∈= ),,( 1 … — состояние системы в момент +∈Rt , а
nT
n Raaa ∈= ),,( 1 … — вектор параметров) состоит в дискретизации систе-
мы (1) и аддитивном внесении информационной переменной u , т.е. система
(1) приводится к виду
⎪⎩
⎪
⎨
⎧
=
⋅⋅++=
++
++
,
,),(
)(
11
11
j
tt
tjttt
xy
uehxaxfhx α
)( +∈Zt , (2)
где T
jnj
je ) 0,,0, 1 , 0,,0 (
раз раз 1
……
−−
= и R∈α .
Вычисления в поле действительных чисел R или, при компьютерном
моделировании, в поле рациональных чисел Q наталкиваются на фактор
накопления ошибок округления, из-за чего процесс «шифрование–
расшифровка» теряет корректность. Чтобы избежать проблем, связанных с
этими ошибками, следует перейти в (2) к вычислениям в конечной алгеб-
раической системе. Тенденция перехода от чисто комбинаторных конструк-
ций к конечным полям системы четко проявляется в криптографии [3, 4].
Известно, что поле — это специальный случай кольца. Наличие в кольце
делителей нуля дает возможность охарактеризовать поиск через сложность
решения алгебраических уравнений над кольцом. Итак, при переходе в (2) к
действиям в кольце ),,( ⊕kp
Z (где p — простое число, а операции опреде-
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 131
лены равенствами ) (mod kpbaba +=⊕ и ) (mod kpbaba ⋅= для всех
), kp
Zba ∈ возникает класс нелинейных динамических систем над коль-
цом kp
Z .
Актуальность исследования таких систем обусловлена следующими
обстоятельствами. Во-первых, эти системы имеют нетривиальную область
приложения — криптографию, так как при соответствующих ограничениях
на параметры они определяют класс высокоскоростных поточных шифров,
вычислительная стойкость которых может быть теоретически охарактеризо-
вана в терминах сложности решения уравнений над кольцом. Во-вторых,
устанавливается связь между теорией динамических систем [5, 6] и совре-
менной криптологией [3, 4], так как сложность атаки для криптоаналитика
характеризуется в терминах сложности решения классических задач теории
динамических систем (управляемость, наблюдаемость, параметрическая
идентификация). В-третьих, эти системы определяют новый класс конечных
автоматов — класс нелинейных автоматов над кольцом, что дает возмож-
ность эффективно применить для их анализа теорию автоматов [7–10] и со-
временную алгебру [11], т.е. устанавливается связь между теорией динами-
ческих систем, теорией автоматов и современной алгеброй. Эта связь —
нетривиальная, так как такие чисто комбинаторные задачи абстрактной тео-
рии автоматов, как контрольный эксперимент с автоматом [12], для иссле-
дуемых систем сводятся к задаче параметрической идентификации, а исходя
из подхода, развитого в [13], исследование управляемости и наблюдаемости
для рассматриваемых систем — это задачи построения установочного и ди-
агностического экспериментов со слабоинициальным автоматом. В-четвер-
тых, для исследуемых систем решение классических задач теории
динамических систем (таких, как параметрическая идентификация, управ-
ляемость, наблюдаемость) дает возможность выделить и изучить особенно-
сти, возникающие при переходе от поля характеристики нуль к конечным
алгебраическим системам. В-пятых, применение теории конечных полей
дает возможность выделить узкие классы дискретных систем, для которых
решение ряда задач значительно проще, чем решение этих же задач для дис-
кретных систем, определенных на абстрактных множествах. Примеры —
исследование линейных последовательностных машин [14, 15], задач теории
кодов, контролирующих ошибки [16] и многочисленные приложения, рас-
смотренные в работе [17].
В работах [18, 19] систематически исследован класс нелинейных дина-
мических систем над кольцом kpZ — автоматов Мили и Мура вида, соот-
ветственно,
⎪⎩
⎪
⎨
⎧
⊕=
⊕⊕⊕=
++
++
,
,
11
11
ttt
tt
T
ttt
xFqGy
xEdqCbqqAq
)( 0Zt∈ , (3)
и
⎪⎩
⎪
⎨
⎧
=
⊕⊕⊕=
++
++
11
11
tt
tt
T
ttt
qGy
xEdqCbqqAq )( 0Zt∈ , (4)
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 132
где Tn
ttt qqq ),,( )()1( …= , Tn
ttt xxx ),,( )()1( …= и Tn
ttt yyy ),,( )()1( …= — соот-
ветственно, состояние, входной и выходной символ в момент t ,
Tnbbb ),,( )()1( …= и Tnddd ),,( )()1( …= — фиксированные векторы, а
FGECA ,,,, — фиксированные )( nn× -матрицы. К таким автоматам сво-
дится широкий класс аналогов над конечным кольцом хаотических динами-
ческих систем [2]. Однако известны примеры хаотических динамических
систем, которые не укладываются в рамки моделей (3) и (4). К ним, в част-
ности, относится free-running система [20]. Ее особенностями является то,
что, во-первых, в уравнения входит операция возведения в степень, а, во-
вторых, система имеет нетривиальную группу симметрий. Как известно,
вычисление дискретного логарифма — одна из базовых конструкций совре-
менной криптографии [3, 4], а теория симметрий [21] — мощный аппарат
анализа динамических систем.
Цель работы — исследование аналога над кольцом kp
Z free-running
системы с позиции криптологии free-running автомата.
ИССЛЕДУЕМАЯ МОДЕЛЬ
Free-running система [20] имеет вид
⎪
⎪
⎩
⎪⎪
⎨
⎧
⋅=
⋅=
⋅=
⋅−
+
⋅−
+
⋅−
+
,)(
,)(
,)(
1
1
1
n
n
n
y
nn
x
nn
z
nn
ezfz
eyfy
exfx
γ
γ
γ
)( +∈Zn , (5)
где )1()( xxaxf −⋅⋅= — логистическое отображение с параметром
)4;0(∈a . Добавим аддитивно информационную переменную u в каждое
уравнение системы (5). Получим систему
⎪
⎪
⎩
⎪⎪
⎨
⎧
⋅+⋅=
⋅+⋅=
⋅+⋅=
+
⋅−
+
+
⋅−
+
+
⋅−
+
,)(
,)(
,)(
131
121
111
n
y
nn
n
x
nn
n
z
nn
uezfz
ueyfy
uexfx
n
n
n
α
α
α
γ
γ
γ
)( +∈Zn . (6)
Перейдем в (6) к действиям в кольце kp
Z и к стандартным обозначе-
ниям теории автоматов. Получим free-running автомат Мура
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
==
⊕=
⊕=
⊕=
=
++
++
++
++
),3,2,1(
,)(
,)(
,)(
),,,,(
)(
1
)(
1
13
)3()3(
1
12
)2()2(
1
11
)1()1(
1
321 )2(
)1(
)3(
iqy
xqfq
xqfq
xqfq
aM
i
n
i
n
n
q
nn
n
q
nn
n
q
nn
FR
n
n
n
αζ
αζ
αζ
ζααα )( +∈Zn , (7)
где )1()( xxaxf Ο= (через Ο обозначена операция, обратная операции
⊕ , т.е. cba =Ο тогда и только тогда, когда cba ⊕= ). Предполагается, что
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 133
321 ,, ααα и ζ — обратимые элементы кольца kp
Z , }0{\kp
Za∈ , x —
входная переменная, а )(iy и )(iq )3,2,1( =i — соответственно, выходные
переменные и переменные состояния.
Обозначим через ),( kpFRΑ — множество всех автоматов (7) над коль-
цом kp
Z . Автомат (7) при условии 01 ≡+nx )( +∈Zn исследован в [22]. В
настоящей работе этот автомат исследуется в предположении, что
kpn Zx ∈+1 )( +∈Zn .
КОНЕЧНО-АВТОМАТНЫЕ ХАРАКТЕРИСТИКИ ИССЛЕДУЕМОЙ МОДЕЛИ
Охарактеризуем структуру автомата ).,(),,,,( 321 kpaM FRFR Α∈ζααα
Применение автомата ),(),,,,( 321 kpaM FRFR Α∈ζααα в качестве по-
точного шифра состоит в следующем: параметры a,,,, 321 ζααα — ключ
средней длительности, а начальное состояние Tqqqq ),,( )3(
0
)2(
0
)1(
00 = — сеан-
совый ключ. Критерий корректности такого процесса «шифрование–
расшифровка» — условие, состоящее в том, что ),,,,( 321 aM FR ζααα —
БПИ-автомат [23–25] (т.е. по выходной последовательности и по начально-
му состоянию автомата поданная на автомат входная последовательность
определяется однозначно). Это условие эквивалентно тому, что для любого
инициального автомата )),,,,,(( 0321 qaM FR ζααα существует обратный
автомат.
Утверждение 1. Для любого простого числа p при всех значениях
числа Nk∈ любой автомат ),(),,,,( 321 kpaM FRFR Α∈ζααα — БПИ-
автомат.
Доказательство. Так как 321 ,, ααα — обратимые элементы кольца
kp
Z , то из первых трех уравнений системы (7) находим
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Ο=
Ο=
Ο=
+
−
+
+
−
+
+
−
+
).)((
),)((
),)((
)2(
)1(
)3(
)3()3(
1
1
11
)2()2(
1
1
11
)1()1(
1
1
11
n
n
n
q
nnn
q
nnn
q
nnn
qfqx
qfqx
qfqx
ζα
ζα
ζα
(8)
Из последних трех уравнений системы (7) получим, что для всех +∈Zn
)()( i
n
i
n yq = )3,2,1( =i , (9)
где 00 qy = . Подставим (9) в (8) и заменим x на y , а y на x . Получим
)(
),)((
),)((
),)((
),,,,(
)2(
)1(
)3(
)3()3(
1
1
11
)2()2(
1
1
11
)1()1(
1
1
11
321
1
+
+
−
+
+
−
+
+
−
+
− ∈
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Ο=
Ο=
Ο=
= Zn
xfxy
xfxy
xfxy
aM
n
n
n
x
nnn
x
nnn
x
nnn
FR
ζα
ζα
ζα
ζααα . (10)
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 134
Утверждение доказано.
Замечание 1. Сравнивая (7) и (10), нетрудно заметить, что в про-
цессе «шифрование-расшифровка» автоматы ),,,,( 321 aM FR ζααα и
),,,,( 321
1 aM FR ζααα− движутся по одной и той же траектории в пространст-
ве состояний.
Замечание 2. Предположим, что элементы кольца kp
Z представле-
ны двоичными последовательностями длины ⎡ ⎤pkl log⋅= . Рассмотрим
очередную последовательность l⋅31 γγ … , сгенерированную автоматом
),,,,( 321 aM FR ζααα . Предположим, что выходы автомата
),,,,( 321
1 aM FR ζααα− подсоединены к входам мажоритарной схемы. Из (10)
вытекает, что в процессе расшифровки будут обнаружены все ошибки, воз-
никшие в процессе передачи информации по каналу связи, состоящие в ин-
вертировании значений битов и определяемые равенством ⊕⊕ +ili γγ
02 ≠⊕ +⋅ ilγ }),,1{( li …∈ . При этом будут исправлены все ошибки, для кото-
рых в каждой тройке бит ilili +⋅+ 2,, γγγ ошибка произошла не более, чем в
одном бите.
Утверждение 2. Для любого простого числа p при всех значениях
числа Nk∈
414 ))1(()1( |),(| −⋅⋅⋅−=Α −⋅ ppppkp kk
FR . (11)
Доказательство. В автомате ),(),,,,( 321 kpaM FRFR Α∈ζααα пара-
метры 321 ,, ααα и ς — обратимые элементы кольца kp
Z , а }0{\kp
Za∈ .
Число обратимых элементов кольца kp
Z равно )1(1 −⋅− pp k . Выбор пара-
метров a,,,, 321 ζααα осуществляется независимо. Сюда вытекает справед-
ливость равенства (11).
Утверждение доказано.
Утверждение 3. Для любого простого числа p при всех значениях
числа Nk∈ автомат ),(),,,,( kpaM FRFR Α∈ζααα не является сильно
связным.
Доказательство. Пусть 3
0000 ),,( kp
Zqqqq ∈= . Из (7) вытекает, что
),,( 1111 qqqq = для любого входного символа .1 kp
Zx ∈ Индукцией по дли-
не слова можно показать, что ),,( nnnn qqqq = для любого входного слова
n
pn kZxx ∈…1 .
Так как α — обратимый элемент кольца kp
Z , то из (7) вытекает,
что для любых фиксированных состояний 3
0000 ),,( kp
Zqqqq ∈= и
3
1111 ),,( kp
Zqqqq ∈= автомата ),,,,( aM FR ζααα существует единственный
входной символ kp
Zx∈ , переводящий состояние 0q в состояние 1q .
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 135
Следовательно, собственное подмножество }|),,({1 kp
ZqqqqqS ∈==
состояний автомата ),,,,( aM FR ζααα определяет компоненту сильной свя-
занности, т.е. автомат ),,,,( aM FR ζααα не является сильно связным.
Утверждение доказано.
Из доказательства утверждения 3 вытекает следствие 1.
Следствие 1. Для любого простого числа p при всех значениях числа
Nk ∈ подавтомат автомата ),(),,,,( kpaM FRFR Α∈ζααα , определяемый
множеством состояний }|),,({1 kp
ZqqqqqS ∈== , является перестановоч-
ным приведенным автоматом, диаметр графа переходов которого равен 1.
Структура любого автомата ),(),,,,( 321 kpaM FRFR Α∈ζααα сущест-
венно отличается от структуры подавтомата автомата ∈),,,,( aM FR ζααα
),( kpFRΑ∈ , определяемого множеством состояний ∈== qqqqqS |),,({1
}kp
Z∈ . В частности, из (7) вытекает утверждение 4.
Утверждение 4. Для любого простого числа p при всех значениях
числа Nk∈ множество состояний }1,0{|),,({ )()3()2()1(
2 ∈== iqqqqqS
)}3,2,1( =i любого автомата ),(),,,,( 321 kpaM FRFR A∈ζααα под действием
любого входного символа kp
Zx∈ переходит в одно и то же состояние
),,( 321 xxxq ααα=′ .
Из утверждения 4 вытекает следствие 2.
Следствие 2. Для любого простого числа p при всех значениях числа
Nk∈ любой автомат ),(),,,,( 321 kpaM FRFR Α∈ζααα не является пере-
становочным автоматом.
Обозначим через )),,,,(,( 321 aMqK FR ζααα множество всех состоя-
ний автомата ),(),,,,( 321 kpaM FRFR Α∈ζααα , эквивалентных состоянию
3
kp
Zq∈ .
Теорема 1. Для любого простого числа p при всех значениях числа
),,,,( 321 aM FR ζααα для любого автомата ∈),,,,( 321 aM FR ζααα
),( kpFRΑ∈ и любого состояния 3)3()2()1( ),,( kp
Zqqqq ∈= множество
)),,,,(,( 321 aMqK FR ζααα состоит из всех таких состояний
3)3()2()1( )~,~,~( kp
Zqqqq ∈=′ , что истинны равенства
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
−
−
−
).()~(
),()~(
),()~(
)3(~)3(
)2(~)2(
)1(~)1(
)2()2(
)1()1(
)3()3(
qfqf
qfqf
qfqf
qq
qq
qq
ζ
ζ
ζ
(12)
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 136
Доказательство. Зафиксируем автомат ∈),,,,( 321 aM FR ζααα
),( kpFRΑ∈ и состояние 3)3()2()1( ),,( kp
Zqqqq ∈= . Пусть ∈=′ )~,~,~( )3()2()1( qqqq
)).,,,,(,( 321 aMqK FR ζααα∈ Из первых трех уравнений системы (7) нахо-
дим, что для любого входного символа kp
Zx∈
⎪
⎪
⎩
⎪
⎪
⎨
⎧
⊕=
⊕=
⊕=
+
+
+
,)(
,)(
,)(
13
)3()3(
1
12
)2()2(
1
11
)1()1(
1
)2(
)1(
)3(
n
q
n
q
n
q
xqfq
xqfq
xqfq
αζ
αζ
αζ
(13)
и
⎪
⎪
⎩
⎪
⎪
⎨
⎧
⊕=
⊕=
⊕=
+
+
+
.)~(~
,)~(~
,)~(~
13
~)3()3(
1
12
~)2()2(
1
11
~)1()1(
1
)2(
)1(
)3(
n
q
n
q
n
q
xqfq
xqfq
xqfq
αζ
αζ
αζ
(14)
Так как q и q ′ — эквивалентные состояния автомата
),,,,( 321 aM FR ζααα , то из последних трех уравнений системы (7) выте-
кает, что
)(
1
)(
1
~ ii qq = )3,2,1( =i . (15)
Из (13)–(15) следует, что
⇔
⎪
⎪
⎩
⎪⎪
⎨
⎧
⊕=⊕
⊕=⊕
⊕=⊕
++
++
++
13
~)3(
13
)3(
12
~)2(
12
)2(
11
~)1(
11
)1(
)2()2(
)1()1(
)3()3(
)~()(
)~()(
)~()(
n
q
n
q
n
q
n
q
n
q
n
q
xqfxqf
xqfxqf
xqfxqf
αζαζ
αζαζ
αζαζ
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
=
=
⇔
.)~()(
,)~()(
,)~()(
)2()2(
)1()1(
)3()3(
~)3()3(
~)2()2(
~)1()1(
qq
qq
qq
qfqf
qfqf
qfqf
ζζ
ζζ
ζζ
(16)
Так как ζ — обратимый элемент кольца kp
Z , то из (16) вытекает (12).
Теорема доказана.
Состояния Qqq ∈′, автомата ),,,,( λδYXQM = — близнецы, если
),(),( xqxq ′= δδ и ),(),( xqxq ′= λλ для любого входного символа Xx∈ . Из
доказательства теоремы 1 вытекает следствие 3.
Следствие 3. Для любого простого числа p при всех значениях числа
Nk∈ эквивалентные состояния любого автомата ∈),,,,( 321 aM FR ζααα
),( kpFRΑ∈ — близнецы.
Множество )),,,,(,( 321 aMqK FR ζααα может быть вычислено сле-
дующим образом.
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 137
Пусть число ζ принадлежит показателю δ , т.е. δ — такое наимень-
шее натуральное число, что ).(mod 1 kp≡δζ Представим компоненты со-
стояния 3)3()2()1( ),,( kp
Zqqqq ∈= в виде i
hi bq iζ=)( )3,2,1( =i , где
1),( =ζib ).3,2,1( =i Из (12) вытекает, что компоненты любого состояния
)),,,,(,()~,~,~( 321
)3()2()1( aMqKqqqq FR ζααα∈=′ удовлетворяют равенствам
⎪
⎪
⎩
⎪⎪
⎨
⎧
=
=
=
.)~(
,)~(
,)~(
3
)3(
2
)2(
1
)1(
2
1
3
bqf
bqf
bqf
l
l
l
ζ
ζ
ζ
(17)
Из (12) и (17) вытекает, что
⎪
⎪
⎩
⎪⎪
⎨
⎧
Ο⊕≡
Ο⊕≡
Ο⊕≡
).(mod ~
),(mod ~
),(mod ~
3
)3(
3
)3(
2
)2(
2
)2(
1
)1(
1
)1(
δ
δ
δ
lqhq
lqhq
lqhq
(18)
Итак, для построения множества )),,,,(,( 321 aMqK FR ζααα доста-
точно найти все решения )~,~,~( )3()2()1( qqq систем сравнений (18) при
всех значениях }1,,1,0{,, 321 −∈ δ…lll . При этом ∈)~,~,~( )3()2()1( qqq
)),,,,(,( 321 aMqK FR ζααα∈ тогда и только тогда, когда истинны равен-
ства (17).
ЗАДАЧИ ИДЕНТИФИКАЦИИ ИССЛЕДУЕМОЙ МОДЕЛИ
Рассмотрим задачу параметрической идентификации автомата
),(),,,,( 321 kpaM FRFR Α∈ζααα в предположении, что экспериментатор
может управлять входом и инициализацией автомата ),,,,( 321 aM FR ζααα .
Утверждение 5. Для любого простого числа p при всех значени-
ях числа Nk∈ идентификация параметров 321 , , ααα автомата
),() , , , ,( 321 kpaM FRFR Α∈ζααα осуществляется простым экспериментом
длины 1.
Доказательство. Положим ( ) ( ) ( ) 03
0
2
0
1
0 === qqq и 1=x . Из (7) выте-
кает, что )(
1
i
i y=α )3,2,1( =i .
Утверждение доказано.
Теорема 2. Для любого простого числа 3≥p при всех значениях
числа Nk∈ , если известны параметры 321 , , ααα автомата
),() , , , ,( 321 kpaM FRFR Α∈ζααα , а также известно, что a — обратимый
элемент кольца kp
Z , то идентификация параметров a и ζ сводится к ре-
шению системы двух уравнений, полученной в результате простого экспе-
римента длины 1.
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 138
Доказательство. Пусть a — обратимый элемент кольца kp
Z . При-
своив 2)1(
0 =q , 2)2(
0 =q и 1)3(
0 =q . Из (7) вытекает, что для любого входного
символа kp
Zx ∈1
⎪⎩
⎪
⎨
⎧
Ο=−
Ο=−
.)1(2
,)1(2
12
)2(
1
2
11
)1(
1
xypa
xypa
k
k
αζ
αζ
(19)
Так как 3≥p , то 2 и 1−kp — обратимые элементы кольца kp
Z . А
так как a — обратимый элемент кольца kp
Z и система (19) — совместная,
то 1
)(
1 xy i
i αΟ )2,1( =i — обратимые элементы кольца kp
Z . Следователь-
но, из (19) вытекает, что
⎪⎩
⎪
⎨
⎧
−ΟΟ=
ΟΟ=
−−−
−
.)1(2)()(
, )()(
111
12
)2(
1
2
11
)1(
1
12
)2(
1
1
11
)1(
1
kpxyxya
xyxy
αα
ααζ
Теорема доказана.
Замечание 3. Метод доказательства, используемый в теореме 2, не
применим, если 2=p . Действительно, пусть a — обратимый элемент коль-
ца kp
Z . Если 2=p и 1=k , то 1=ζ и 1=a . Если же 2=p и 1>k , то
)1( xx Ο — необратимый элемент кольца kp
Z для любого kp
Zx∈ . По-
этому, присвоив 2)1(
0 =q , 1)2(
0 =q и 0)3(
0 =q , получим
⎪⎩
⎪
⎨
⎧
Ο=−
Ο=−
.)1(2
,)1(2
12
)2(
1
2
11
)1(
1
xypa
xypa
k
k
αζ
α
(20)
Все решения ),( ζa этой системы обладают тем свойством, что при их
подстановке в (7) получим эквивалентные друг другу автоматы. Это озна-
чает, что идентификация параметров a и ζ может быть осуществима толь-
ко с точностью до множества решений системы (20).
Идентификация параметров a и ζ существенно усложняется, если a
— необратимый элемент кольца kp
Z . В этом случае вначале необходимо
найти все решения a и ζ системы уравнений (19), а затем обычными
методами теории автоматов с помощью кратного эксперимента решить
задачу идентификации автомата в классе допустимых автоматов
),(),,,,( 321 kpaM FRFR Α∈ζααα .
Рассмотрим теперь задачу идентификации начального состояния авто-
мата ),(),,,,( 321 kpaM FRFR Α∈ζααα в предположении, что эксперимента-
тору известны параметры a,,,, 321 ζααα автомата и он может управлять
входом автомата ),,,,( 321 aM FR ζααα .
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 139
Предположим вначале, что экспериментатор имеет возможность управ-
лять также параметрами автомата ),,,,( 321 aM FR ζααα , а 4>kp . Положим
4=a и .1=ζ Из (7) вытекает, что для любого входного символа kp
Zx ∈1
⎪
⎪
⎩
⎪⎪
⎨
⎧
⊕Ο=Ο
⊕Ο=Ο
⊕Ο=Ο
.1)12(
,1)12(
,1)12(
)3(
113
2)3(
0
)2(
112
2)2(
0
)1(
111
2)1(
0
yxq
yxq
yxq
α
α
α
(21)
Множество S решений ),,( )3(
0
)2(
0
)1(
0 qqq системы уравнений (20) опре-
деляет множество всех допустимых кандидатов на начальное состояние ис-
следуемого автомата. При этом )( || kpoS = , если ∞→p или ∞→k . Неэк-
вивалентные состояния автомата ),,,,( 321 aM FR ζααα , принадлежащие
множеству S (если такие имеются), необходимо различить с помощью про-
стого диагностического эксперимента.
Предположим теперь, что экспериментатор не может управлять пара-
метрами автомата ),,,,( 321 aM FR ζααα . Из (7) вытекает, что для любого
входного символа kp
Zx ∈1
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Ο=
Ο=
Ο=
.)(
,)(
,)(
13
)3(
1
)3(
0
12
)2(
1
)2(
0
11
)1(
1
)1(
0
)2(
0
)1(
0
)3(
0
xyqf
xyqf
xyqf
q
q
q
αζ
αζ
αζ
(22)
Так как система уравнений (22) — совместная, то
⎪
⎪
⎩
⎪⎪
⎨
⎧
=Ο
=Ο
=Ο
,
,
,
2
1
3
311
)3(
1
211
)2(
1
111
)1(
1
h
h
h
bxy
bxy
bxy
ζα
ζα
ζα
(23)
где 1),( =ζib )3,2,1( =i . Из (22) и (23) следует, что
⎪
⎪
⎩
⎪⎪
⎨
⎧
=
=
=
.)(
,)(
,)(
3
)3(
0
2
)2(
0
1
)1(
0
2
1
3
bqf
bqf
bqf
l
l
l
ζ
ζ
ζ
(24)
Пусть число ζ принадлежит показателю δ . Подставим (23) и (24) в
(22). Получим
⎪
⎪
⎩
⎪⎪
⎨
⎧
Ο=
Ο=
Ο=
).(mod
),(mod
),(mod
33
)3(
0
22
)2(
0
11
)1(
0
δ
δ
δ
lhq
lhq
lhq
(25)
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 140
Таким образом, для идентификации начального состояния автомата
),(),,,,( 321 kpaM FRFR Α∈ζααα достаточно найти множество 1S всех ре-
шений ),,( )3(
0
)2(
0
)1(
0 qqq систем сравнений (25) при всех значениях
}1,,1,0{,, 321 −∈ δ…lll , вычислить подмножество 2S , состоящее из всех эле-
ментов 1
)3(
0
)2(
0
)1(
0 ),,( Sqqq ∈ , удовлетворяющих системе уравнений (24) и
различить неэквивалентные состояния автомата ),,,,( 321 aM FR ζααα , при-
надлежащие множеству 2S (если такие имеются) с помощью простого диаг-
ностического эксперимента.
НЕПОДВИЖНЫЕ ТОЧКИ ИССЛЕДУЕМОЙ МОДЕЛИ
Зафиксируем автомат ),(),,,,( 321 kpaM FRFR Α∈ζααα и начальное состоя-
ние ).,,( )3(
0
)2(
0
)1(
0 qqqq = Обозначим через )),,,,,(( 0321 qaMX FR ζααα мно-
жество всех неподвижных точек словарной функции, реализуемой иници-
альным автоматом )),,,,,(( 0321 qaM FR ζααα . Положим
kpFRFR ZqaMXqaMX ∩= )),,,,,(()),,,,,(( 03210321
)1( ζαααζααα .
Из (7) вытекает, что )),,,,,(( 0321
)1(
1 qaMXx FR ζααα∈ тогда и только
тогда, когда 1x является решением системы уравнений
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=Ο
=Ο
=Ο
.)()1(
,)()1(
,)()1(
)2(
0
)1(
0
)3(
0
)3(
013
)2(
012
)1(
011
q
q
q
qfx
qfx
qfx
ζα
ζα
ζα
(26)
Из (26) вытекают утверждение 6 и 7.
Утверждение 6. Для любого простого числа p при всех значениях
числа Nk ∈ , если каждый элемент iαΟ1 )3,2,1( =i — обратимый элемент
кольца kp
Z , то:
• ∅=)),,,,,(( 0321
)1( qaMX FR ζααα тогда и только тогда, когда
,)()1(,)()1{(|
`)1(
0
)3(
0 )2(
0
1
2
)1(
0
1
1
qq qfqf ζαζα −− ΟΟ
2 |})()1(
)2(
0)3(
0
1
3 ≥Ο − qqf ζα ;
• 1 |)),,,,,((| 0321
)1( =qaMX FR ζααα тогда и только тогда, когда
,)()1(,)()1{(|
`)1(
0
)3(
0 )2(
0
1
2
)1(
0
1
1
qq qfqf ζαζα −− ΟΟ
1 |})()1(
)2(
0)3(
0
1
3 =Ο − qqf ζα .
Анализа free-running автомата над конечным кольцом
Системні дослідження та інформаційні технології, 2010, № 3 141
Утверждение 7. Для любого простого числа p при всех значениях
числа Nk∈ , если существует такое значение }3,2,1{∈i , что iαΟ1 и
)( )(
0
iqf , соответственно, необратимый и обратимый элементы кольца kp
Z ,
то ∅=)),,,,,(( 0321
)1( qaMX FR ζααα .
ВЫВОДЫ
В работе определен и исследован класс ),( kpFRΑ автоматов
),,,,( 321 aM FR ζααα , являющихся аналогами над кольцом kp
Z хаотиче-
ской динамической free-running системы. Показано, что автоматы, при-
надлежащие классу ),( kpFRΑ , могут быть использованы в качестве кан-
дидата на поточный шифр, способный контролировать ошибки,
возникшие в процессе передачи информации по каналу связи и состоя-
щие в инвертировании значений битов. С позиции теории автоматов
охарактеризована структура автомата ).,,,,( 321 aM FR ζααα Более тон-
кий анализ компонент связанности автомата ),,,,( 321 aM FR ζααα и
множества неподвижных точек словарной функции, реализуемой инициаль-
ным автоматом )),,,,,(( 0321 qaM FR ζααα , представляет собой одно из воз-
можных направлений дальнейших исследований.
Второе направление исследований связано с детальным анализом
сложности решения задач параметрической идентификации и идентифика-
ции начального состояния автомата ),,,,( 321 aM FR ζααα с целью выделе-
ния наиболее подходящих значений параметров a , , , , 321 ζααα при исполь-
зовании автомата ),,,,( 321 aM FR ζααα в качестве поточного шифра.
Третье направление исследований связано с разработкой средств авто-
матизации решения задач построения классов эквивалентных состояний,
параметрической идентификации и идентификации начального состояния
автомата ),,,,( 321 aM FR ζααα .
Четвертое направление исследований связано с компьютерным анали-
зом вычислительной стойкости шифра, построенного на основе автомата
),,,,( 321 aM FR ζααα .
ЛИТЕРАТУРА
1. Андреев Ю.В., Дмитриев А.С., Куминов Д.А. Хаотические процессоры //
Радиотехника и электроника. — 1997. — 42, Вып. 10. — С. 50–79.
2. Кузнецов С.П. Динамический хаос. — М.: Физматлит, 2001. — 296 с.
3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные
тексты на языке СИ. — М.: ТРИУМФ, 2003. — 816 с.
4. Харин Ю.С., Берник В.И., Матвеев Б.В. Математические и компьютерные
основы криптологии. — Минск: Новое знание, 2003. — 382 с.
5. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. —
М.: Мир, 1971. — 400 с.
В.В. Скобелев
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 142
6. Льюнг Л. Идентификация систем. Теория для пользователя. — М.: Наука, 1991.
— 432 с.
7. Глушков В.М. Синтез цифровых автоматов. — М.: Физматлит, 1962. — 476 с.
8. Гилл А. Введение в теорию конечных автоматов. — М.: Наука, 1966. — 272 с.
9. Трахтенброт Б.А. Конечные автоматы (поведение и синтез). — М.: Наука,
1970. — 400 с.
10. Кудрявцев В.Б., Подколзин А.С. Введение в теорию конечных автоматов. — М.:
Наука, 1985. — 320 с.
11. Кострикин А.И. Введение в алгебру. — Т. 1–3. — М.: Наука, 1999–2000. —
818 с.
12. Hennie F.C. Finite state models for logical machines. — NY: John Wiley&Sons,
Inc., 1962. — 466 p.
13. Горяшко А.П. Проектирование легко тестируемых дискретных устройств: идеи,
методы, реализация // АиТ. — 1984. — № 7. — С. 5–35.
14. Гилл А. Линейные последовательностные машины. — М.: Наука, 1974. —
287 с.
15. Фараджев Р.Г. Линейные последовательностные машины. — М.: Сов. Радио,
1975. — 248 c.
16. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир,
1986. — 576 с.
17. Лидл Р., Нидеррайтер Г. Конечные поля. — Т. 1–2. — М.: Мир, 1988. — 820 с.
18. Скобелев В.Г. Нелинейные автоматы над конечным кольцом // Кибернетика и
системный анализ. — 2006. — № 6. — С. 29–42.
19. Скобелев В.Г. О некоторых свойствах нелинейных БПИ-автоматов над кольцом
kp
Z // Прикладная радиоэлектроника. — 2007. — 6. — № 2. — С. 288–299.
20. Aswin P., Ruclidge A.M., Sturman R. Cyclic attractors of coupled cell systems and
dynamics with symmetry // Syncronization: Theory and Application. NATO Sci-
ence Series. II. Mathematics, Physics and Chemistry. Kluver Academic Publish-
ers. — 2003. — 109. — P. 5–23.
21. Голод П.И., Климык А.У. Математические основы теории симметрий. —
Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 528 с.
22. Скобелев В.В. Симметрические динамические системы над конечным кольцом:
свойства и сложность идентификации // Труды ИПММ НАНУ. — 2005. —
10. — С. 184–189.
23. Even S. On information lossless automata of finite order // IEEE Transactions Elec-
tion Computation — 1965. — C-14, № 4. — P. 561–569.
24. Huffman D.A. Canonical forms for information-lossless finite stste logical machines
// IRE Transactions on Circuit Theory. Special Supplement,1959. — CT-6. —
P. 41–59.
25. Курмит А. Автоматы без потери информации конечного порядка. — Рига:
Зинатне, 1972. — 266 с.
Поступила 02.07.2008
|
| id | journaliasakpiua-article-106956 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:53Z |
| publishDate | 2010 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/18/ec77ca1ed40027f50eba5a1f576db318.pdf |
| spelling | journaliasakpiua-article-1069562018-04-06T12:28:40Z Analysis of free-running automaton over a finite ring Анализ free-running автомата над конечным кольцом Аналіз free-running автомата над кінцевим кільцем Skobelev, V. V. The analog over the finite ring of chaotic dynamical free-running system is investigated. The structure of the model under investigation is characterized in terms of automaton theory. Problems of parametric identification and identification of the initial state are solved. The structure of fixed points in the mapping realized by the initial automaton is characterized. Исследован аналог над конечным кольцом хаотической динамической free-running системы. С позиции теории автоматов охарактеризована структура исследуемой модели. Решены задачи параметрической идентификации и идентификации начального состояния. Охарактеризована структура множества неподвижных точек словарной функции, реализуемой инициальным автоматом. Досліджено аналог над кінцевим кільцем хаотичної динамічної free-running системи. З позиції теорії автоматів охарактеризована структура моделі, яка вивчається. Розв’язано задачі параметричної ідентифікації та ідентифікації початкового стану. Охарактеризовано структуру множини нерухомих точок словникової функції, яка реалізується ініціальним автоматом. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2010-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/106956 System research and information technologies; No. 3 (2010); 130-142 Системные исследования и информационные технологии; № 3 (2010); 130-142 Системні дослідження та інформаційні технології; № 3 (2010); 130-142 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/106956/101956 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Skobelev, V. V. Аналіз free-running автомата над кінцевим кільцем |
| title | Аналіз free-running автомата над кінцевим кільцем |
| title_alt | Analysis of free-running automaton over a finite ring Анализ free-running автомата над конечным кольцом |
| title_full | Аналіз free-running автомата над кінцевим кільцем |
| title_fullStr | Аналіз free-running автомата над кінцевим кільцем |
| title_full_unstemmed | Аналіз free-running автомата над кінцевим кільцем |
| title_short | Аналіз free-running автомата над кінцевим кільцем |
| title_sort | аналіз free-running автомата над кінцевим кільцем |
| url | https://journal.iasa.kpi.ua/article/view/106956 |
| work_keys_str_mv | AT skobelevvv analysisoffreerunningautomatonoverafinitering AT skobelevvv analizfreerunningavtomatanadkonečnymkolʹcom AT skobelevvv analízfreerunningavtomatanadkíncevimkílʹcem |