Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом
Получено решение задачи анализа сложности идентификации (параметрической и начального состояния) для простейших нелинейных одномерных обратимых автоматов с лагом 2 над произвольным конечным коммутативно-ассоциативным кольцом с единицей. Отримано вирішення задачі аналізу складності ідентифікації (пар...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84663 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом / В.В. Скобелев // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 81-89. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84663 |
|---|---|
| record_format |
dspace |
| spelling |
Скобелев, В.В. 2015-07-11T20:38:01Z 2015-07-11T20:38:01Z 2011 Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом / В.В. Скобелев // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 81-89. — Бібліогр.: 13 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84663 519.713:512.55 Получено решение задачи анализа сложности идентификации (параметрической и начального состояния) для простейших нелинейных одномерных обратимых автоматов с лагом 2 над произвольным конечным коммутативно-ассоциативным кольцом с единицей. Отримано вирішення задачі аналізу складності ідентифікації (параметричної та початкового стану) для найпростіших нелінійних одновимірних автоматів з лагом 2, що допускають обернення, над будь-яким скінченним комутативно-асоціативним кільцем з одиницею. A solution to a problem of analysis of complexity of identification (parametric one as well as of initial state) for simplest non-linear one-dimensional reversible automata with delay 2 over arbitrary finite commutative-associative ring with a unit is obtained. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Информационные технологии в экологии Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом Складність ідентифікації нелінійних одновимірних автоматів з лагом 2 над скінченним кільцем Complexity of identification of non-linear one-dimensional automata with delay 2 over arbitrary finite ring Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| spellingShingle |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом Скобелев, В.В. Информационные технологии в экологии |
| title_short |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| title_full |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| title_fullStr |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| title_full_unstemmed |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| title_sort |
сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| topic |
Информационные технологии в экологии |
| topic_facet |
Информационные технологии в экологии |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Складність ідентифікації нелінійних одновимірних автоматів з лагом 2 над скінченним кільцем Complexity of identification of non-linear one-dimensional automata with delay 2 over arbitrary finite ring |
| description |
Получено решение задачи анализа сложности идентификации (параметрической и начального состояния) для простейших нелинейных одномерных обратимых автоматов с лагом 2 над произвольным конечным коммутативно-ассоциативным кольцом с единицей.
Отримано вирішення задачі аналізу складності ідентифікації (параметричної та початкового стану) для найпростіших нелінійних одновимірних автоматів з лагом 2, що допускають обернення, над будь-яким скінченним комутативно-асоціативним кільцем з одиницею.
A solution to a problem of analysis of complexity of identification (parametric one as well as of initial state) for simplest non-linear one-dimensional reversible automata with delay 2 over arbitrary finite commutative-associative ring with a unit is obtained.
|
| issn |
ХХХХ-0003 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84663 |
| citation_txt |
Сложность идентификации нелинейных одномерных автоматов с лагом 2 над конечным кольцом / В.В. Скобелев // Компьютерная математика: сб. науч. тр. — 2011. — № 2. — С. 81-89. — Бібліогр.: 13 назв. — рос. |
| work_keys_str_mv |
AT skobelevvv složnostʹidentifikaciinelineinyhodnomernyhavtomatovslagom2nadkonečnymkolʹcom AT skobelevvv skladnístʹídentifíkacíínelíníinihodnovimírnihavtomatívzlagom2nadskínčennimkílʹcem AT skobelevvv complexityofidentificationofnonlinearonedimensionalautomatawithdelay2overarbitraryfinitering |
| first_indexed |
2025-11-26T00:17:42Z |
| last_indexed |
2025-11-26T00:17:42Z |
| _version_ |
1850599262294900736 |
| fulltext |
Компьютерная математика. 2011, № 2 81
Получено решение задачи анализа
сложности идентификации (па-
раметрической и начального со-
стояния) для простейших нели-
нейных одномерных обратимых
автоматов с лагом 2 над произ-
вольным конечным коммутатив-
но-ассоциативным кольцом с еди-
ницей.
В.В. Скобелев, 2011
УДК 519.713:512.55
В.В. СКОБЕЛЕВ
СЛОЖНОСТЬ
ИДЕНТИФИКАЦИИ
НЕЛИНЕЙНЫХ ОДНОМЕРНЫХ
АВТОМАТОВ С ЛАГОМ 2
НАД КОНЕЧНЫМ КОЛЬЦОМ
Введение. Интерес к исследованию автома-
тов над конечными кольцами обусловлен
следующими причинами. Во-первых, это ус-
тойчивая тенденция перехода криптографии
от чисто комбинаторных моделей к матема-
тическим моделям, построенным на основе
конечных алгебраических систем [1–3]. Во-
вторых, многочисленные попытки примене-
ния хаотических динамических систем [4] к
решению задач преобразования информации
столкнулись с проблемой обеспечения кор-
ректной обратимости процессов при нели-
нейных преобразованиях в поле R (или в
поле Q ). Естественный способ избежать
этой проблемы – это переход к вычислениям
в конечной алгебраической системе. В-
третьих, логическое развитие алгебраической
теории автоматов, сформировало ее новый
раздел – автоматы, представленные уравне-
ниями над конечным кольцом, для которого
математические основы криптологии – при-
кладная предметная область это [5–9].
В силу последнего обстоятельства акту-
альным является исследование обратимых
автоматов над произвольным конечным
коммутативно-ассоциативным кольцом с
единицей [10] ),,( ⋅+K (для краткости, будем
говорить «кольцо K »). Любой такой автомат
может рассматриваться как математическая
модель симметричного поточного шифра,
для которого параметры – это секретный
В.В. СКОБЕЛЕВ
ключ средней длительности,
а начальное состояние – сек-
ретный сеансовый ключ [9].
СЛОЖНОСТЬ ИДЕНТИФИКАЦИИ НЕЛИНЕЙНЫХ ОДНОМЕРНЫХ АВТОМАТОВ …
Компьютерная математика. 2011, № 2 83
Поэтому особую значимость приобретает анализ сложности решения задач
идентификации [11] такого автомата (параметрической и начального состояния).
Такая сложность является теоретической аргументацией обоснования вычисли-
тельной стойкости соответствующего шифра.
Существенное отличие задач идентификации автомата над конечным коль-
цом от задач идентификации классических динамических систем [12] состоит в
следующем. При идентификации автоматов над конечным кольцом не возникает
проблемы, связанной с точностью идентификации из-за различного рода при-
ближений (приближения, как таковые, отсутствуют вообще). Однако конечное
кольцо является настолько «жесткой» структурой, что любая ошибка приводит к
непредсказуемым последствиям.
В работах [7–9] рассмотрены, в основном, n -мерные автоматы с лагом 1 над
кольцом kp
Z ( p простое число). Однако, не исследованы простейшие обрати-
мые нелинейные одномерные автоматы с лагом 2, которые представляют инте-
рес из-за высокой скорости преобразования информации. Этот пробел частично
восполнен в [13].
Настоящая работа посвящена анализу сложности решения задач идентифи-
кации (параметрической и начального состояния) простейших обратимых нели-
нейных одномерных автоматов с лагом 2 над произвольным кольцом K .
Исследуемая модель. Система уравнений над кольцом K
⋅=
⋅+⋅+⋅+=
++
+++
21
1
2
12
tt
tttt
qey
xdqcqbaq
)( +∈ Zt , (1)
где Kedcba ∈,,,, определяет класс автоматов Мура, для которых 1+tx и 1+ty –
соответственно, входной и выходной символ в момент 1+t , а ),( 1 ttt qqq +=r
–
состояние в момент t . Если зафиксировать параметры Kedcba ∈,,,, , то система
уравнений (1) определяет конкретный автомат M , принадлежащий этому клас-
су. При фиксации начального состояния ),( 010 qqq =r
инициальный автомат
),( 0qM
v
осуществляет отображение входной полугруппы +K в себя.
Отметим, что уравнение ttt qcqbaq ⋅+⋅+= ++
2
12 – аналог над кольцом K ря-
да модельных хаотических отображений, в том числе, отображения Эно [4].
Пусть S – множество всех таких автоматов M , определенных системой
уравнений (1), что Kca ∈, , }0{\Kb ∈ , а invKed ∈, , где invK – множество всех
обратимых элементов кольца K . Тогда S – множество обратимых автоматов,
причем автомат 1−M , обратный автомату SM ∈ , имеет вид
⋅−⋅−−⋅⋅=
⋅=
++
−−
+
+
−
+
)(
2
11
11
1
1
1
2
tttt
tt
qcqbaxedy
xeq
)( +∈ Zt . (2)
В.В. СКОБЕЛЕВ
84 Компьютерная математика. 2011, № 2
С точки зрения алгебры инициальный автомат ),( 0qM
v
),( 2
0 KqSM ∈∈ v
на
каждом такте своего функционирования осуществляет сюръективное отображе-
ние множества K на себя, представляющее собой линейное преобразование
veu ⋅= линейной комбинации v = α + β квадратичной формы 2
1t tb q c q+α = ⋅ + ⋅
текущего состояния автомата M и аффинного преобразования 1ta d x +β = + ⋅
множества K .
Упорядоченная пара )),(),,(( 0
1
0 qMqM
rv − ),( 2
0 KqSM ∈∈ v
определяет сим-
метричный поточный шифр: набор параметров ( , , , , )a b c d e ∈
2( \ {0}) invK K K K∈ × × × – секретный ключ средней длительности, а 2
0 Kq ∈r
–
секретный сеансовый ключ. Отметим, что в процессе «шифрование-расшиф-
рование» оба автомата M и 1−M движутся в пространстве состояний по одной
и той же траектории в одном и том же направлении.
Для шифра )),(),,(( 0
1
0 qMqM
rv − ),( 2
0 KqSM ∈∈ v
число секретных ключей
средней длительности равно 2 2| | | | (| | 1)invK K⋅ ⋅ − , а число секретных сеансовых
ключей – 2|| K . Если число || K достаточно велико (например, kp
ZK = , где p –
простое число, для записи которого необходимо 100 бит), то вероятность угады-
вания секретного ключа чрезвычайно мала. Поэтому актуальны задачи анализа
сложности идентификации (параметрической и начального состояния) автомата
SM ∈ . С позиции криптографии эти задачи имеют различную значимость.
Действительно, из (1) вытекает, что
)( 1
2
11 +++ ⋅+⋅+⋅+⋅= tttt xdqcqbaey )( +∈ Zt . (3)
Подставив lt ,,1,0 K= )2( >l в (3), с учетом 2-го уравнения системы (1),
получаем
2
1 1 0 1
1 2
2 1 1 2
1 2
1 2 ( 3, , )i i i i
y e a b e q c e q e d x
y e a b e y c e q e d x
y e a b e y c y e d x i l
−
−
− −
= ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
= ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
= ⋅ + ⋅ ⋅ + ⋅ + ⋅ ⋅ =
K
. (4)
Из последних 2−l уравнений системы (4) вытекает, что при известном на-
боре параметров 2})0{\(),,,,( invKKKKedcba ×××∈ криптоаналитик, не распо-
лагая информацией о начальном состоянии автомата SM ∈ , может идентифи-
цировать суффикс lxx K3 входного слова, так как
1 1 2
1 2( ) ( ) ( 3, , )i i i ix e d e a b e y c y y i l− −
− −= ⋅ ⋅ ⋅ + ⋅ ⋅ + ⋅ − = K .
СЛОЖНОСТЬ ИДЕНТИФИКАЦИИ НЕЛИНЕЙНЫХ ОДНОМЕРНЫХ АВТОМАТОВ …
Компьютерная математика. 2011, № 2 85
Поэтому, с позиции криптографии задача идентификации начального со-
стояния автомата SM ∈ актуальна, если префикс длины 2 входного слова со-
держит уникальную информацию, без которой суффикс lxx K3 практически не
дает возможность восстановить исходный текст.
Такая неравнозначность задач идентификации обусловлена исключительно
тем, что функция выходов автомата SM ∈ осуществляет линейное преобразо-
вание одной из компонент состояния. Эта неравнозначность исчезает при изме-
нении модели, состоящем в переходе к автомату Мили с нелинейной функцией
выходов (достаточно положить 1121 ++++ ⋅+⋅⋅= tttt xdqqey ). Таким образом, мно-
жество автоматов S характеризует нижнюю границу сложности, с которой при-
дется столкнуться криптоаналитику при решении задач идентификации нели-
нейных одномерных автоматов с лагом 2 над конечным кольцом.
Рассмотрим эти задачи в предположении (соответствующем одной из наи-
более сильных атак криптоаналитика), что экспериментатор наблюдает вход и
выход исследуемого автомата, управляет его входом, а также может осуществ-
лять кратный эксперимент любой кратности.
Идентификация начального состояния. Охарактеризуем сложность иден-
тификации начального состояния автомата SM ∈ при условии, что эксперимен-
татору известны параметры 2})0{\(),,,,( invKKKKedcba ×××∈ .
Теорема 1. Для любого автомата SM ∈ :
1) если invKc ∈ , то идентификация начального состояния осуществляется
посредством любого простого эксперимента длины 2;
2) если invKc∉ , то идентификация начального состояния с точностью до
класса эквивалентных состояний осуществляется посредством кратного экспе-
римента кратности 2|| K и высоты 2.
Доказательство. Пусть invKc∈ . Из первых двух уравнений системы (4) по-
лучим, что для любого входного слова 2
1 2 :x x K∈
1 1 2 2
1 2 1 2
1 1 2
0 1 1 1
( )
( )
q c e y a b e y d x
q c e y a b q d x
− − −
− −
= ⋅ ⋅ − − ⋅ ⋅ − ⋅
= ⋅ ⋅ − − ⋅ − ⋅
.
Пусть invKc∉ . Рассмотрим первые два уравнения системы (4)
2
1 1 0 1
1 2
2 1 1 2
.
y e a b e q c e q e d x
y e a b e y c e q e d x−
= ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
= ⋅ + ⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
(5)
В.В. СКОБЕЛЕВ
86 Компьютерная математика. 2011, № 2
Пусть
21xxU – множество решений ),( 01 qq системы (5) для фиксированного
входного слова 2
21 Kxx ∈ . Из последних 2−l уравнений системы (4) вытекает,
что суффикс lyy K3 выходного слова полностью определяется значением его
префикса 21yy . Отсюда следует, что
212
21
xx
Kxx
UI
∈
– класс состояний, эквивалент-
ных начальному состоянию автомата SM ∈ .
Теорема доказана.
Из теоремы 1 вытекает, что задача идентификации начального состояния ав-
томата SM ∈ тривиальна, если invKc∈ . Ситуация меняется, когда invKc∉ .
В этом случае поиск решений ),( 01 qq системы (5) – нетривиальная задача (даже
если kp
ZK = , то множества
21xxU имеют сложную структуру, представляются
громоздкими формулами, а множество
212
21
xx
Kxx
UI
∈
вообще трудно подлежит
анализу [13]). Эта нетривиальность обусловлена внутренней сложностью иссле-
дуемой модели, и характеризуется необходимостью анализа принадлежности
коэффициентов системы уравнений (5) различным классам ассоциированных
элементов кольца K .
Параметрическая идентификация. Будем говорить, что для задачи пара-
метрической идентификации автомата SM ∈ алгоритм Α вычисляет:
1) точное решение, если выходом алгоритма Α является набор параметров
2})0{\(),,,,( invKKKKedcba ×××∈ исследуемого автомата M ;
2) решение с точностью до имитационной модели, если выходом алгоритма
Α является набор значений комбинаций параметров исследуемого автомата M ,
на основе которых может быть построен алгоритм, моделирующий внешнее по-
ведение автомата M (возможно, с учетом тех или иных ограничений).
Теорема 2. Никакой простой эксперимент с автоматом SM ∈ не дает воз-
можность вычислить точное решение для задачи его параметрической иденти-
фикации. Однако может существовать простой эксперимент с автоматом SM ∈ ,
который дает возможность для задачи его параметрической идентификации вы-
числить решение с точностью до имитационной модели, причем только пара-
метр Kc∈ будет вычислен точно.
Доказательство. Возможны следующие два случая.
Случай 1. Начальное состояние ),( 010 qqq =v
известно экспериментатору.
Пусть )0,0(0 =q
v
. Тогда система уравнений (4) примет вид
1 1 4 1
2
1 1 2 2 4 2
2
1 1 2 2 3 4
( 3, , )i i i i
u x u y
u y u x u y
u y u y u x u y i l− −
+ ⋅ =
+ ⋅ + ⋅ =
+ ⋅ + ⋅ + ⋅ = = K
, (6)
СЛОЖНОСТЬ ИДЕНТИФИКАЦИИ НЕЛИНЕЙНЫХ ОДНОМЕРНЫХ АВТОМАТОВ …
Компьютерная математика. 2011, № 2 87
где
1
1 2 3 4( , , , ) ( , , , )u u u u e a b e c e d−= ⋅ ⋅ ⋅ . (7)
Матрица системы уравнений (6) имеет вид
1
2
1 2
2
2 1 3
2
1 2
1 0 0
1 0
1
1 l l l
x
y x
A y y x
y y x− −
=
M M M M
.
Если существует такое входное слово l
l Kxx ∈K1 заранее неизвестной дли-
ны 4≥l , что матрица A содержит обратимую матрицу 4-го порядка, то может
быть вычислено единственное решение ),,,( 4321 uuuu системы уравнений (6).
Из равенства (7) вытекает, что тем самым будут вычислены величины ae ⋅ ,
1−⋅eb , c и de ⋅ , т. е. только параметр c будет вычислен точно. При этом из (6)
вытекает, что имитационная модель автомата SM ∈ имеет вид
1 1 1 4
2
2 1 1 2 2 4
2
1 1 2 2 3 4 ( 3)i i i i
y u x u
y u y u x u
y u y u y u x u i− −
= + ⋅
= + ⋅ + ⋅
= + ⋅ + ⋅ + ⋅ ≥
,
где значения ju )4,,1( K=j определены равенством (7).
Пусть )0,0(0 ≠q
v
. Тогда система уравнений (4) примет вид
2
1 1 2 0 4 1 6 1
2
1 1 3 1 4 2 6 2
2
1 1 3 2 5 6
( 3, ,)i i i i
v q v q v x v y
v y v q v x v y
v y v y v x v y i l− −
+ ⋅ + ⋅ + ⋅ =
+ ⋅ + ⋅ + ⋅ =
+ ⋅ + ⋅ + ⋅ = = K
, (8)
где
1
1 2 3 4 5 6( , , , , , ) ( , , , , , )v v v v v v e a b e b e c e c e d−= ⋅ ⋅ ⋅ ⋅ ⋅ . (9)
В.В. СКОБЕЛЕВ
88 Компьютерная математика. 2011, № 2
Матрица системы уравнений (8) имеет вид
2
1 0 1
2
1 1 2
2
2 1 3
2
1 2
1 0 0
1 0 0
1 0 0
1 0 0 l l l
q q x
y q x
B y y x
y y x− −
=
M M M M M M
.
Если существует такое входное слово l
l Kxx ∈K1 заранее неизвестной дли-
ны 6≥l , что матрица B содержит обратимую матрицу 6-го порядка, то может
быть вычислено единственное решение ),,,( 621 vvv K системы уравнений (8).
Из равенства (9) вытекает, что тем самым будут вычислены величины ae ⋅ ,
eb ⋅ , 1−⋅eb , ec ⋅ , c и de ⋅ , т. е. только параметр c будет вычислен точно. При
этом из (8) вытекает, что имитационная модель автомата SM ∈ имеет вид
2
1 1 1 2 0 4 1 6
2
2 1 1 3 1 4 2 6
2
1 1 3 2 5 6
( 3)i i i i
y v q v q v x v
y v y v q v x v
y v y v y v x v i− −
= + ⋅ + ⋅ + ⋅
= + ⋅ + ⋅ + ⋅
= + ⋅ + ⋅ + ⋅ ≥
,
где значения jv )6,,1( K=j определены равенством (9).
Случай 2. Начальное состояние ),( 010 qqq =v
не известно экспериментатору.
Учитывая, что ситуации различаются при )0,0(0 =q
v
и )0,0(0 ≠q
v
, отбросим в
системе (8) первые 2 уравнения. Получим систему уравнений
2
1 1 2 2 3 4 3, , )i i i iw y w y w x w y (i l− −+ ⋅ + ⋅ + ⋅ = = K , (10)
где
1
1 2 3 4( , , , ) ( , , , )w w w w e a b e c e d−= ⋅ ⋅ ⋅ . (11)
Матрица системы уравнений (10) имеет вид
2
2 1 3
2
1 2
1
1 l l l
y y x
C
y y x− −
=
M M M M .
Если существует такое входное слово l
l Kxx ∈K1 заранее неизвестной дли-
ны 6≥l , что матрица C содержит обратимую матрицу 4-го порядка, то может
быть вычислено единственное решение ),,,( 4321 wwww системы уравнений (10).
Из равенства (11) вытекает, что тем самым будут вычислены величины ae ⋅ ,
1−⋅eb , c и de ⋅ , т. е. только параметр c будет вычислен точно. При этом из (10)
вытекает, что имитационная модель, моделирующая поведение автомата
SM ∈ на суффиксах входных слов, полученных отбрасыванием префикса длины
2, имеет вид
СЛОЖНОСТЬ ИДЕНТИФИКАЦИИ НЕЛИНЕЙНЫХ ОДНОМЕРНЫХ АВТОМАТОВ …
Компьютерная математика. 2011, № 2 89
2
1 1 2 2 3 4 3, , )i i i iy w y w y w x w (i l− −= + ⋅ + ⋅ + ⋅ = K ,
где значения jw )4,,1( K=j определены равенством (11).
Теорема доказана.
Следствие. Никакой кратный эксперимент с автоматом SM ∈ не дает воз-
можность вычислить точное решение для задачи его параметрической иденти-
фикации. Однако может существовать кратный эксперимент с автоматом
SM ∈ , который дает возможность для задачи его параметрической идентифи-
кации вычислить решение с точностью до имитационной модели, причем только
параметр Kc ∈ будет вычислен точно.
Доказательство. В процессе кратного эксперимента с автоматом SM ∈ бу-
дет построено несколько систем уравнений (6), (8) или (10) (число этих систем
уравнений равно кратности эксперимента). Однако решение этих систем опре-
деляет точно такие же комбинации параметров, как и в случае простого экспе-
римента с автоматом SM ∈ .
Следствие доказано.
Полученные результаты показывают, что при решении задачи параметриче-
ской идентификации автомата SM ∈ экспериментатор вынужден осуществлять
поиск входного слова длины не меньшей, чем 4|| K . Отсюда вытекает, что
сложность решения этой задачи достаточно высокая (достаточно положить
kp
ZK = , где p – простое число, для записи которого необходимо 100 бит). Од-
нако, возможность построения в результате эксперимента с автоматом SM ∈
достаточно простых имитационных моделей (выше было отмечено, что это обу-
словлено именно тем, что функция выходов автомата M осуществляет линей-
ное преобразование одной из компонент состояния) является достаточно серьез-
ной аргументацией против выбора класса S в качестве кандидата на симмет-
ричный поточный шифр.
Заключение. В работе показано, что даже для простейших обратимых не-
линейных одномерных автоматов с лагом 2 над произвольным кольцом K ре-
шение задач идентификации (параметрической и начального состояния (в слу-
чае, когда invc K∉ )) имеет достаточно высокую сложность. Для задачи иденти-
фикации начального состояния эта сложность обусловлена необходимостью ре-
шения (в случае, когда invc K∉ ) систем нелинейных уравнений над конечным
кольцом, а для задачи параметрической идентификации – поиском в достаточно
объемном множестве входного слова, обладающего заданными условиями (вы-
ражаемыми в терминах ранга матрицы).
Показано, что в результате эксперимента с автоматом SM ∈ возможно по-
строение достаточно простых имитационных моделей. Поэтому актуальной
является задача выделения, описания и характеристики классов обратимых ав-
томатов, отличающихся от класса S только функциями выходов, для которых
любая имитационная модель, построенная в результате эксперимента с автома-
том существенно сложнее, чем система уравнений, определяющая автомат. Ре-
шение этой задачи – основное направление дальнейших исследований.
В.В. СКОБЕЛЕВ
90 Компьютерная математика. 2011, № 2
В.В. Скобелєв
СКЛАДНІСТЬ ІДЕНТИФІКАЦІЇ НЕЛІНІЙНИХ ОДНОВИМІРНИХ АВТОМАТІВ
З ЛАГОМ 2 НАД СКІНЧЕННИМ КІЛЬЦЕМ
Отримано вирішення задачі аналізу складності ідентифікації (параметричної та початкового
стану) для найпростіших нелінійних одновимірних автоматів з лагом 2, що допускають обер-
нення, над будь-яким скінченним комутативно-асоціативним кільцем з одиницею.
V.V. Skobelev
COMPLEXITY OF IDENTIFICATION OF NON-LINEAR ONE-DIMENSIONAL AUTOMATA
WITH DELAY 2 OVER arbitrary FINITE RING
A solution to a problem of analysis of complexity of identification (parametric one as well as of
initial state) for simplest non-linear one-dimensional reversible automata with delay 2 over arbitrary
finite commutative-associative ring with a unit is obtained.
1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.:
Гелиос АРВ, 2002. – 480 с.
2. Харин Ю.С., Берник В.И., Матвеев Г.В., Агиевич С.В. Математические и компьютерные
основы криптологии. − Минск: Новое знание, 2003. − 382 с.
3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке
СИ. − М.: ТРИУМФ, 2003. − 816 с.
4. Кузнецов С.П. Динамический хаос. – М.: Физматлит, 2001. – 296 с.
5. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Псевдослучайные и полилинейные последова-
тельности. – Труды по дискретной математике. Т.1. – М.: Научное изд-во «ТВП», 1997. –
С. 139–202.
6. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Свойства линейных и полилинейных рекуррент
над кольцами Галуа (I). – Труды по дискретной математике. Т. 2. – М.: Научное изд-во
«ТВП», 1998. – С. 191–222.
7. Скобелев В.Г. Нелинейные автоматы над конечным кольцом // Кибернетика и системный
анализ. – 2006. – № 6. – С. 29–42.
8. Скобелев В.В. Анализ структуры класса линейных автоматов над кольцом kp
Z // Кибер-
нетика и системный анализ. – 2008. – № 3 – С. 60–74.
9. Скобелев В.В., Скобелев В.Г. Анализ шифрсистем. – Донецк: ИПММ НАН Украины,
2009. – 479 с.
10. Курош А.Г. Лекции по общей алгебре. – М.: Наука, 1973. – 400 с.
11. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. – М.: Мир,
1971. – 400 с.
12. Льюнг Л. Идентификация систем. Теория для пользователя. − М.: Наука, 1991. − 432 с.
13. Скобелев В.В., Скобелев В.Г. Анализ нелинейных автоматов с лагом 2 над конечным
кольцом // Прикладная дискретная математика. – 2010. – № 1 (7). – С. 68–85.
Получено 19.05.2010
Об авторе:
Скобелев Владимир Владимирович,
кандидат физико-математических наук, младший научный сотрудник
отдела теории управляющих систем Института прикладной математики и механики
НАН Украины.
e-mail: skobelev_vv@iamm.ac.donetsk.ua
|