Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом

Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого ступеня, а функція виходу є відповідно лінійним та афінним відображенням, розв’язано задачу параметричної ідентифікації. Виділено параметри,...

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859526514400296960
author	Скобелев, В.Г.
author_facet	Скобелев, В.Г.
citation_txt	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом / В.Г. Скобелев // Проблемы управления и информатики. — 2010. — № 5. — С. 17-41. — Бібліогр.: 6 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого ступеня, а функція виходу є відповідно лінійним та афінним відображенням, розв’язано задачу параметричної ідентифікації. Виділено параметри, які легко ідентифікувати, а також параметри, ідентифікувати які не так просто. Встановлено, що властивість «бути оборотним автоматом» взагалі не впливає на складність розв’язання задачі параметричної ідентифікації досліджуваних моделей. For Mealy and Moore automata presented via quadric equations over any finite associative-commutative ring with the unit it is resolved the problem of parametric identification. There are extracted parameters identified easily and the ones that are hardly identified. It is established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving of the problem of parametric identification.
first_indexed	2026-03-13T06:17:57Z
format	Article
fulltext	© В.Г. СКОБЕЛЕВ, 2010 Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 5 37 УДК 519.712+681.3 В.Г. Скобелев АНАЛИЗ ЗАДАЧИ ПАРАМЕТРИЧЕСКОЙ ИДЕНТИФИКАЦИИ НЕЛИНЕЙНЫХ АВТОМАТОВ НАД КОНЕЧНЫМ КОЛЬЦОМ Введение. В последнее десятилетие при решении задач преобразования ин- формации, в частности задач криптографии, наметилась устойчивая тенденция перехода от комбинаторных моделей к математическим, построенным на основе конечных колец. Модульные вычисления используются практически в каждом современном стандарте шифрования [1, 2]. Кроме того, многочисленные попытки непосредственного использования хаотических динамических систем [3] при ре- шении задач построения поточных шифров наталкиваются на проблему обеспе- чения корректности процесса «шифрование–расшифрование» из-за ошибок округления. Чтобы устранить эту проблему, достаточно перейти к действиям в конечной алгебраической системе. В качестве последней естественно выбрать ко- нечное кольцо, так как наличие делителей нуля дает возможность охарактеризо- вать сложность поиска, осуществляемого криптоаналитиком, в терминах сложно- сти решения алгебраических уравнений над кольцом. Указанные выше обстоятельства стимулировали исследования автоматов, представленных уравнениями над конечными кольцами: автономные автоматы ис- следованы в [4, 5], а неавтономные автоматы над кольцом ),,(  kk pp ZZ (где p — простое число, ,Nk а )(mod kpbaba  и )(mod kpbaba  — в [6]. Исследование автоматов над конечными кольцами дает возможность устано- вить внутренние связи между теорией динамических систем, теорией автоматов, современной алгеброй и криптологией. С этой точки зрения особую роль играет задача параметрической идентификации автомата M над конечным коммутатив- но-ассоциативным кольцом ),,(  KK с единицей. С позиции криптографии решение этой задачи (для обратимого автомата) характеризует сложность атаки криптоаналитика на секретный сеансовый ключ поточного шифра, определяемого автоматом M. С позиции теории автоматов эта задача представляет собой задачу распознавания автомата, принадлежащего заданному классу автоматов. С пози- ции теории систем здесь отсутствует понятие «точность идентификации, обу- словленная выбором приближения или ошибками измерений». Однако кольцо яв- ляется настолько «жесткой» структурой, что любая ошибка приводит к непред- сказуемым последствиям (в этом и состоит основное отличие конечных колец от поля характеристики нуль). Рассмотрим решение задачи параметрической идентификации для двух клас- сов нелинейных автоматов над конечным коммутативно-ассоциативным кольцом ),,(  KK с единицей (далее кольцо )K . 1. Исследуемые модели. Пусть nM — множество всех )( nn -матриц над кольцом ,K а inv nM — множество всех обратимых матриц .nX M Обозначим 1A множество всех автоматов Мили 1M         , 11 1 T 1 ttt ttttt FG ECA xqy xdqbqqq ),( Zt (1) 38 ISSN 0572-2691 а 2A — множество всех автоматов Мура 2M         , 11 1 T 1 tt ttttt G ECA qy xdqbqqq ),( Zt (2) где ,),,( T)()1( n ttt qq q T)()1( ),,( n ttt xx x и T)()1( ),,( n ttt yy y — соответ- ственно состояние автомата, входной и выходной символ в момент t, A, C, E, G, nF M — фиксированные матрицы, а nn Kbb  T)()1( ),,( b и d nn Kdd  T)()1( ),,(  — фиксированные векторы. Отметим, что аналоги многих модельных хаотических динамических систем над кольцом K укладываются в рамки моделей (1) и (2). Рассмотрим решение задачи параметрической идентификации автомата iiM A )2,1( i в предположении, что экспериментатор полностью управляет входом автомата iM и его инициализацией, а также полностью наблюдает выход автомата .iM 2. Параметрическая идентификация автомата Мили. Положив ,0 0q  из второго уравнения системы (1) получим, что .11 yx F (3) Из (3) вытекает, что если T 1 1 ) 0,,0,1,0,,0 (  ini  x ),,,1( ni  то 1y — i-й столбец матрицы F. Таким образом, идентификация матрицы F осуществляется в результате n-кратного эксперимента высоты 1. Положив ,1 0x  из второго уравнения системы (1) получим, что .10 yq G (4) Из (4) вытекает, что если T 1 0 ) 0,,0,1,0,,0 (  ini  q ),,,1( ni  то 1y — i-й столбец матрицы G. Таким образом, идентификация матрицы G осуществляется в результате n-кратного эксперимента высоты 1. В дальнейшем считаем, что матрицы G и F известны. Из системы уравнений (1) вытекает, что .)( 2210 T 00 xyxdqbqq FECAG  (5) Положив 0q 0 и 0x 1 в (5), получим .22 xyd FG  (6) Из (6) вытекает, что если ,inv nG M то при известных матрицах G и F иден- тификация вектора d осуществляется в результате простого эксперимента дли- ны 2. Если же ,\ inv nnG MM то множество 1S решений уравнения (6) определя- ет возможные значения вектора d. Дальнейшие вычисления необходимо осуще- ствить для каждого значения .1Sd В дальнейшем считаем, что матрицы G, F и вектор d известны. Преобразуем уравнение (5) к виду .)( 2210 T 00 dxyxqbqq GFECAG  (7) Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 5 39 Положив 0q 0 в (7), получим .221 dxyx GFGE  (8) Если ,inv nG M то уравнение (8) преобразуется в эквивалентное уравнение ).( 22 1 1 dxyx GFGE   (9) Из (9) вытекает, что если T 1 1 ) 0,,0,1,0,,0 (  ini  x ),,,1( ni  то )( 22 1 dxy GFG  — i-й столбец матрицы E. Таким образом, если ,inv nG M то при известных матрицах G, F и векторе d идентификация матрицы E осуществляет- ся в результате n-кратного эксперимента высоты 2. Если же ,\ inv nnG MM то множество 2S решений уравнения (8) определяет возможные значения матрицы E. Дальнейшие вычисления необходимо осуществить для каждого значения .2SG Пусть известны матрицы G, E и F, а также вектор d. Преобразуем уравнение (9) к виду .)( 1220 T 00 dxxyqbqq GGEFCAG  (10) Обозначим )( 03 qS множество решений уравнения (10). Если ,1 )( 0 03    nK S q q то матрицы A, C и вектор b идентифицируются единственным образом в резуль- тате некоторого l-кратного ) ( n Kl  эксперимента высоты 1. В противном случае осуществляется поиск входных слов заранее неизвестной длины и соответствую- щих начальных состояний в целях формирования системы уравнений вида 122 T )(   tttttt GEGFCAG xdxyqbqq .),,1,0( lt  (11) В системе уравнений (11) каждый вектор tq ),,1( lt  с помощью первого уравнения системы (1) выражается значениями .,,,,,,,, 10 tECA xxqdb  После этого все системы уравнений объединяются в одну систему нелинейных уравне- ний, решения которой — возможные значения матриц A, C и вектора b. 3. Параметрическая идентификация автомата Мура. Из системы уравне- ний (2) вытекает, что .)()()( 110 T 00 yxdqbqq  GEGGCGA (12) Положив 0q 0 и 0x 1 в (12), получим .1yd G Таким образом, идентифи- кация вектора dG осуществляется в результате простого эксперимента длины 1. В дальнейшем считаем, что вектор dG известен. Преобразуем уравнение (12) к виду .)()()( 110 T 00 dyxqbqq GGEGCGA  (13) Положив 0q 0 в (13), получим .)( 11 dyx GGE  (14) 40 ISSN 0572-2691 Из (14) вытекает, что если T 1 1 ) 0,,0,1,0,,0 (  ini  x ),,1( ni  , то dy G1 – i-й столбец матрицы .GE Таким образом, при известном векторе dG идентифика- ция матрицы GE осуществляется в результате n-кратного эксперимента высоты 1. Пусть известен вектор dG и матрица .GE Преобразуем уравнение (13) к виду .)()()( 110 T 00 xdyqbqq GEGGCGA  (15) Обозначим )( 04 qS множество решений уравнения (15). Если ,1)( 0 04    nK S q q то матрицы ,GA GC и вектор b идентифицируются единственным образом в ре- зультате некоторого l-кратного ) ( n Kl  эксперимента высоты 1. В противном случае осуществляется поиск входных слов заранее неизвестной длины и соответ- ствующих начальных состояний в целях формирования системы уравнений вида 11 T )()()(   ttttt GEGGCGA xdyqbqq ).,,1,0( lt  (16) Дальнейшие действия с системами уравнений (16) такие же, как и с систе- мами (11). Заключение. Полученные результаты дают возможность отметить следую- щие особенности решения задачи параметрической идентификации для автома- тов (1) и (2). Для любого автомата Мили 11 AM идентификация матриц G и F осуществ- ляется достаточно легко. Сложность идентификации вектора d и матрицы E суще- ственно зависит от того, является ли матрица G обратимой. При положительном ответе идентификация вектора d и матрицы E также осуществляется достаточно легко. Однако если матрица G не является обратимой матрицей, то приходится осуществлять перебор по множествам решений уравнений (6) и (8). Трудной зада- чей является идентификация матриц A, C и вектора b, так как приходится форми- ровать и решать системы нелинейных уравнений над кольцом K (известно, что даже над полями Галуа )2( kGF решение системы уравнений второй степени от многих переменных — NP-полная задача). Для любого автомата Мура 22 AM идентификация вектора dG и матрицы GE осуществляется достаточно легко. Однако трудной задачей является иденти- фикация матриц ,GA GC (либо матриц A, G, C) и вектора b. Несложно показать следующее: 1) автомат 11 AM обратимый тогда и только тогда, когда F — обратимая матрица; 2) автомат 22 AM обратимый тогда и только тогда, когда E и G — обра- тимые матрицы. Полученные результаты показывают, что переход к обратимым автоматам ничуть не упрощает решение задачи параметрической идентификации для иссле- дуемых моделей, поэтому при использовании автомата (1) или (2) в качестве по- точного шифра (в этом случае параметры играют роль долговременного секретно- го ключа) особое внимание следует уделить обеспечению секретности параметров A, C и b. Международный научно-технический журнал «Проблемы управления и информатики», 2010, № 5 41 Дальнейшие исследования предполагают выделение и исследование под- множеств автоматов, определяемых ограничениями на структуру параметров (прежде всего, матриц A, C и вектора b), для которых решение задачи параметри- ческой идентификации существенно проще, чем в общем случае. Второе направ- ление связано с исследованием вариации автоматных отображений, реализуемых инициальными автоматами (1) и (2), при вариации параметров, в частности, в вы- делении подклассов эквивалентных друг другу инициальных автоматов. В.Г. Скобелєв АНАЛІЗ ЗАДАЧІ ПАРАМЕТРИЧНОЇ ІДЕНТИФІКАЦІЇ НЕЛІНІЙНИХ АВТОМАТІВ НАД СКІНЧЕННИМ КІЛЬЦЕМ Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кіль- цем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого ступеня, а функція виходу є відповідно лінійним та афінним відображенням, розв’язано задачу параметричної ідентифікації. Виділено па- раметри, які легко ідентифікувати, а також параметри, ідентифікувати які не так просто. Встановлено, що властивість «бути оборотним автоматом» взага- лі не впливає на складність розв’язання задачі параметричної ідентифікації досліджуваних моделей. V.G. Skobelev ANALYSIS OF THE PROBLEM OF PARAMETRIC IDENTIFICATION FOR NONLINEAR AUTOMATA OVER FINITE RING For Mealy and Moore automata presented via quadric equations over any finite asso- ciative-commutative ring with the unit it is resolved the problem of parametric identi- fication. There are extracted parameters identified easily and the ones that are hardly identified. It is established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving of the problem of parametric identi- fication. 1. Харин Ю.С., Берник В.И., Матвеев Г.В. и др. Математические и компьютерные основы криптологии. — Минск : Новое знание, 2003. — 382 с. 2. Алферов А.П., Зубов А.Ю., Кузьмин А.С. и др. Основы криптографии. — М. : Гелиос АРВ, 2002. — 480 с. 3. Кузнецов С.П. Динамический хаос. — М. : Физматлит, 2001. — 296 с. 4. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Псевдослучайные и полилинейные последова- тельности // Тр. по дискретной математике. Т .1. — М. : Науч. изд-во «ТВП», 1997. — С. 139–202. 5. Кузьмин А.С., Куракин В.Л., Нечаев А.А. Свойства линейных и полилинейных рекуррент над кольцами Галуа (I) // Тр. по дискретной математике. Т. 2. — М. : Науч. изд-во «ТВП», 1998. — С. 191–222. 6. Скобелев В.В., Скобелев В.Г. Анализ шифрсистем. — Донецк : ИПММ НАН Украины, 2009. — 479 с. Получено 17.06.2010
id	nasplib_isofts_kiev_ua-123456789-210831
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2026-03-13T06:17:57Z
publishDate	2010
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Скобелев, В.Г. 2025-12-17T19:44:32Z 2010 Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом / В.Г. Скобелев // Проблемы управления и информатики. — 2010. — № 5. — С. 17-41. — Бібліогр.: 6 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210831 519.712+681.3 10.1615/JAutomatInfScien.v42.i9.40 Для автоматів Мілі та Мура над скінченним комутативно-асоціативним кільцем з одиницею, функція переходів яких визначена за допомогою нелінійних рівнянь другого ступеня, а функція виходу є відповідно лінійним та афінним відображенням, розв’язано задачу параметричної ідентифікації. Виділено параметри, які легко ідентифікувати, а також параметри, ідентифікувати які не так просто. Встановлено, що властивість «бути оборотним автоматом» взагалі не впливає на складність розв’язання задачі параметричної ідентифікації досліджуваних моделей. For Mealy and Moore automata presented via quadric equations over any finite associative-commutative ring with the unit it is resolved the problem of parametric identification. There are extracted parameters identified easily and the ones that are hardly identified. It is established that for investigated automata the quality «to be reversible one» has no influence onto hardness of resolving of the problem of parametric identification. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы идентификации и адаптивного управления Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом Аналіз задачі параметричної ідентифікації нелінійних автоматів над скінченним кільцем Analysis of the problem of parametric identification for nonlinear automata over finite ring Article published earlier
spellingShingle	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом Скобелев, В.Г. Методы идентификации и адаптивного управления
title	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
title_alt	Аналіз задачі параметричної ідентифікації нелінійних автоматів над скінченним кільцем Analysis of the problem of parametric identification for nonlinear automata over finite ring
title_full	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
title_fullStr	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
title_full_unstemmed	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
title_short	Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
title_sort	анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом
topic	Методы идентификации и адаптивного управления
topic_facet	Методы идентификации и адаптивного управления
url	https://nasplib.isofts.kiev.ua/handle/123456789/210831
work_keys_str_mv	AT skobelevvg analizzadačiparametričeskoiidentifikaciinelineinyhavtomatovnadkonečnymkolʹcom AT skobelevvg analízzadačíparametričnoíídentifíkacíínelíníinihavtomatívnadskínčennimkílʹcem AT skobelevvg analysisoftheproblemofparametricidentificationfornonlinearautomataoverfinitering

Анализ задачи параметрической идентификации нелинейных автоматов над конечным кольцом

Репозитарії

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