Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом
Досліджено загальні властивості сімейств хеш-функцій, визначених сильнозв язаними автоматами без вихідної функції над скінченним кільцем. Знайдено ймовірність випадкового вибору послідовності, для якої хеш-функція приймає задане значення, а також ймовірність випадкового вибору двох різних послідовно...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/86215 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 56-65. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86215 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-862152015-09-10T03:02:22Z Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом Скобелев, В.В. Кибернетика Досліджено загальні властивості сімейств хеш-функцій, визначених сильнозв язаними автоматами без вихідної функції над скінченним кільцем. Знайдено ймовірність випадкового вибору послідовності, для якої хеш-функція приймає задане значення, а також ймовірність випадкового вибору двох різних послідовностей фіксованої довжини, для яких значення хеш-функції співпадають. Охарактеризовано обчислювальну стійкість хеш-функцій. Some general properties of families of hash functions defined by strongly connected automata without output function over a finite ring are analyzed. The probabilities of random choice of a sequence with the given value of hash function, as well as of random choice of two different sequences of the same length with the same values of the hash function are computed. The computational security of investigated hash-functions is characterized. 2013 Article Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 56-65. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/86215 512.552.37+519.115 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Скобелев, В.В. Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом Кибернетика и системный анализ |
| description |
Досліджено загальні властивості сімейств хеш-функцій, визначених сильнозв язаними автоматами без вихідної функції над скінченним кільцем. Знайдено ймовірність випадкового вибору послідовності, для якої хеш-функція приймає задане значення, а також ймовірність випадкового вибору двох різних послідовностей фіксованої довжини, для яких значення хеш-функції співпадають. Охарактеризовано обчислювальну стійкість хеш-функцій. |
| format |
Article |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| author_sort |
Скобелев, В.В. |
| title |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| title_short |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| title_full |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| title_fullStr |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| title_full_unstemmed |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| title_sort |
анализ семейств хэш-функций, определяемых автоматами над конечным кольцом |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86215 |
| citation_txt |
Анализ семейств хэш-функций, определяемых автоматами над конечным кольцом / В.В. Скобелев // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 56-65. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT skobelevvv analizsemejstvhéšfunkcijopredelâemyhavtomataminadkonečnymkolʹcom |
| first_indexed |
2025-07-06T13:40:48Z |
| last_indexed |
2025-07-06T13:40:48Z |
| _version_ |
1836905135258730496 |
| fulltext |
ÓÄÊ 512.552.37+519.115
Â.Â. ÑÊÎÁÅËÅÂ
ÀÍÀËÈÇ ÑÅÌÅÉÑÒ ÕÝØ-ÔÓÍÊÖÈÉ, ÎÏÐÅÄÅËßÅÌÛÕ
ÀÂÒÎÌÀÒÀÌÈ ÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Êëþ÷åâûå ñëîâà: êîíå÷íûå êîëüöà, àâòîìàòû áåç âûõîäà, õýø-ôóíêöèè.
ÂÂÅÄÅÍÈÅ
Èçâåñòíî, ÷òî àíàëèç àâòîìàòîâ íàä êîíå÷íûìè êîëüöàìè ÿâëÿåòñÿ çàäà÷åé àë-
ãåáðàè÷åñêîé òåîðèè àâòîìàòîâ, èìåþùåé ìíîãî÷èñëåííûå ïîòåíöèàëüíûå
ïðèëîæåíèÿ â îáëàñòè êîìïüþòåðíûõ íàóê. Îäíî èç òàêèõ ïðèêëàäíûõ íà-
ïðàâëåíèé ñîñòîèò â èññëåäîâàíèè âîçìîæíîñòè èñïîëüçîâàíèÿ îáðàòèìûõ àâ-
òîìàòîâ íàä êîíå÷íûìè êîëüöàìè â êà÷åñòâå ìàòåìàòè÷åñêèõ ìîäåëåé ïîòî÷-
íûõ øèôðîâ [1–4], ÷òî àêòóàëüíî â ñâÿçè ñ ïåðåõîäîì ê êîìáèíàòîðíî-àëãåá-
ðàè÷åñêèì ìîäåëÿì ïðè ðåøåíèè çàäà÷ ñîâðåìåííîé êðèïòîãðàôèè [5, 6].
Äðóãîå íàïðàâëåíèå ñâÿçàíî ñ èññëåäîâàíèåì âîçìîæíîñòè ïðèìåíåíèÿ àâòî-
ìàòîâ íàä êîíå÷íûìè êîëüöàìè ïðè ðåøåíèè çàäà÷ êîìïàêòíîãî ïðåäñòàâëå-
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
© Â.Â. Ñêîáåëåâ, 2013
íèÿ èíôîðìàöèè.  ýòîì ñëó÷àå îïðåäåëÿþùóþ ðîëü èãðàåò ïðîöåññ õåøèðî-
âàíèÿ, ñóòü êîòîðîãî ñîñòîèò â ïðåîáðàçîâàíèè âõîäíîãî ìàññèâà äàííûõ â
âûõîäíóþ ñòðîêó ôèêñèðîâàííîé äëèíû. Òàêèå ïðåîáðàçîâàíèÿ íàçûâàþòñÿ
õýø-ôóíêöèÿìè. Ñ ìàòåìàòè÷åñêîé òî÷êè çðåíèÿ, õýø-ôóíêöèè ïðåäñòàâëÿåò
ñîáîé îòîáðàæåíèå H X Y: � � , ãäå X è Y — òàêèå íåïóñòûå êîíå÷íûå ìíî-
æåñòâà, ÷òî | | | |X Y� .
Õýø-ôóíêöèè ïðèìåíÿþòñÿ â ïðîöåññå ðåøåíèÿ ìíîãèõ çàäà÷, ñâÿçàííûõ ñ
çàùèòîé èíôîðìàöèè [7, 8]. Ôîðìàëüíî òðåáîâàíèÿ, ïðåäúÿâëÿåìûå ê òàêîé
õýø-ôóíêöèè H X Y: � � , ìîãóò áûòü ñôîðìóëèðîâàíû ñëåäóþùèì îáðàçîì:
1) ñëîæíîñòü âû÷èñëåíèÿ çíà÷åíèé ôóíêöèè H ÿâëÿåòñÿ ïîëèíîìîì îò äëè-
íû âõîäà (H — ëåãêî âû÷èñëèìàÿ ôóíêöèÿ);
2) äëÿ ëþáîãî ôèêñèðîâàííîãî y Y� ïîèñê òàêîãî u X� � , ÷òî H u y( ) � , ÿâ-
ëÿåòñÿ òðóäíîé çàäà÷åé (îòñþäà, â ÷àñòíîñòè, âûòåêàåò, ÷òî äëÿ ëþáîãî ôèêñèðî-
âàííîãî u X� � ïîèñê òàêîãî � � �u X , ÷òî H u H u( ) ( )� � — òðóäíàÿ çàäà÷à);
3) ïîèñê äâóõ òàêèõ ñëó÷àéíûõ ýëåìåíòîâ u u X, � � � , ÷òî H u H u( ) ( )� � , èìå-
åò, ïî êðàéíåé ìåðå, ñóáýêñïîíåíöèàëüíóþ ñëîæíîñòü.
Ïåðâûå äâà òðåáîâàíèÿ îçíà÷àþò, ÷òî H ÿâëÿåòñÿ îäíîíàïðàâëåííîé ôóíê-
öèåé, à òðåòüå òðåáîâàíèå íàçûâàåòñÿ óñòîé÷èâîñòüþ ê êîëëèçèÿì.
 íàñòîÿùåå âðåìÿ íå èçâåñòíî íè îäíîé ôóíêöèè, äëÿ êîòîðîé äîêàçàíî,
÷òî îíà óäîâëåòâîðÿåò òðåáîâàíèÿì 1 è 2. Ïîýòîìó ïðè ðåøåíèè ïðèêëàäíûõ çà-
äà÷ ïîä îäíîíàïðàâëåííîé õýø-ôóíêöèåé ïîíèìàþò òàêóþ ëåãêî âû÷èñëèìóþ
ôóíêöèþ H X Y: � � , ÷òî ïðè ëþáîì ôèêñèðîâàííîì y Y� ëþáîé èçâåñòíûé
àëãîðèòì ðåøåíèÿ óðàâíåíèÿ H u y( ) � èìååò ñóáýêñïîíåíöèàëüíóþ ñëîæíîñòü.
Èñõîäÿ èç ýòîãî, ïîä êðèïòîñòîéêîé õýø-ôóíêöèåé ïîíèìàþò îäíîíàïðàâëåí-
íóþ ôóíêöèþ H X Y: � � (â óêàçàííîì âûøå ïðèêëàäíîì çíà÷åíèè ýòîãî ïîíÿ-
òèÿ), äëÿ êîòîðîé ëþáîé èçâåñòíûé àëãîðèòì íàõîæäåíèÿ êîëëèçèé èìååò
ñóáýêñïîíåíöèàëüíóþ ñëîæíîñòü.
Çàìå÷àíèå 1.  êðèïòîãðàôèè (ñì., íàïðèìåð, [8]) ëþáàÿ õýø-ôóíêöèÿ
H m k: )(E E� � ( E � { }0 1, , à k m, �N ( )k m� — ôèêñèðîâàííûå ÷èñëà) ñ÷èòàåòñÿ
êðèïòîñòîéêîé, åñëè ïðè ëþáîì ôèêñèðîâàííîì y E� k àñèìïòîòè÷åñêàÿ ñëîæíîñòü
ëþáîãî èçâåñòíîãî àëãîðèòìà ïîèñêà òàêîãî ýëåìåíòà u E�( )m n , ÷òî H ( )u y� ,
à òàêæå àñèìïòîòè÷åñêàÿ ñëîæíîñòü ëþáîãî èçâåñòíîãî àëãîðèòìà ïîèñêà äâóõ òàêèõ
ñëó÷àéíûõ ýëåìåíòîâ u u E, ( )� � m n , ÷òî H H( ) ( )u u� � , ðàâíà O n( ),20 5 ( )n � .
Öåëü íàñòîÿùåé ðàáîòû — èññëåäîâàíèå ñâîéñòâ õýø-ôóíêöèé, îïðåäåëÿå-
ìûõ àâòîìàòàìè áåç âûõîäà íàä êîíå÷íûì êîëüöîì K � �
( , , )K (| | )K � 2 (â äàëü-
íåéøåì êîëüöî K), ÿâëÿþùèõñÿ åñòåñòâåííûì îáîáùåíèåì õýø-ôóíêöèé, óêà-
çàííûõ â çàìå÷àíèè 1.
 ðàçä. 1 ñåìåéñòâà õåø-ôóíêöèé îïðåäåëåíû â òåðìèíàõ ñåìåéñòâ îòîáðà-
æåíèé, ðåàëèçóåìûõ àâòîìàòàìè áåç âûõîäà ïðè âñåâîçìîæíûõ èõ èíèöèàëèçà-
öèÿõ. Â ðàçä. 2 óñòàíîâëåíû îñíîâíûå ñâîéñòâà ýòèõ ñåìåéñòâ õåø-ôóíêöèé.
 ðàçä. 3 îõàðàêòåðèçîâàíà âû÷èñëèòåëüíàÿ ñòîéêîñòü èññëåäóåìûõ ñåìåéñòâ
õýø-ôóíêöèé. Çàêëþ÷åíèå ñîäåðæèò ðÿä âûâîäîâ. Âñå íåîïðåäåëÿåìûå â ðàáîòå
òåðìèíû òåîðèè àâòîìàòîâ è òåîðèè ãðàôîâ òàêèå æå, êàê â [2, 4, 9, 10].
1. ÈÑÑËÅÄÓÅÌÀß ÌÎÄÅËÜ
Çàôèêñèðóåì ÷èñëà k m, �N ( )k m� . Îáîçíà÷èì Fk m, ( , , )k m k m� �N ìíîæåñòâî
âñåõ îòîáðàæåíèé f : K K Kk m k� � , óäîâëåòâîðÿþùèõ ñëåäóþùèì äâóì óñëîâèÿì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 57
1) äëÿ ëþáûõ q q, � �K k èñòèííû ðàâåíñòâà
| | ( , ) | | |{ }x f q x q� � � � �K Km m k ; (1)
2) äëÿ ëþáûõ q q q, ,� �� �K k ( )q q
� èñòèííû ðàâåíñòâà
{ } { }x f q x q x f q x q� � �� � � � � �� � �K Km m| ( , ) | ( , ) . (2)
Èç (1) âûòåêàåò, ÷òî ìíîæåñòâî îòîáðàæåíèé Fk m, îïðåäåëÿåò íàä êîëüöîì
K ìíîæåñòâî Bk m, ñèëüíî ñâÿçíûõ àâòîìàòîâ áåç âûõîäà:
M t t tf q f q x: ( , )� ��1 1 ( , ),f Z� � �Fk m t , (3)
èìåþùèõ ìíîæåñòâî ñîñòîÿíèé K k è âõîäíîé àëôàâèò K m , ò.å. q t
kK� è
x t
mK� ÿâëÿþòñÿ ñîîòâåòñòâåííî ñîñòîÿíèåì è âõîäíûì ñèìâîëîì â ìîìåíò t .
Çàìå÷àíèå 2. Ëþáîé àâòîìàò M k mf �B , ( ),f �Fk m õàðàêòåðèçóåòñÿ ñëåäóþ-
ùèì îáðàçîì. Ðàññìîòðèì àâòîìàòíûé ãðàô Gf àâòîìàòà M f . Óäàëèì îòìåòêè
âñåõ äóã, è äëÿ êàæäîé ïàðû ñîñòîÿíèé q q, ~ �K k îòîæäåñòâèì (èíûìè ñëîâàìè,
ñêëåèì) âñå äóãè, èäóùèå èç âåðøèíû ñ îòìåòêîé q â âåðøèíó ñ îòìåòêîé ~q . Ïî-
ëó÷èì ïîëíûé íàïðàâëåííûé ãðàô G ñ ïåòëÿìè, èìåþùèé | |K k âåðøèí.
Ñëåäóþùèé ïðèìåð ïîêàçûâàåò, ÷òî ìíîæåñòâî îòîáðàæåíèé Fk m,
( , , )k m k m� �N îïðåäåëÿåò íåòðèâèàëüíîå ìíîæåñòâî ñèëüíî ñâÿçíûõ àâòîìà-
òîâ áåç âûõîäà íàä êîëüöîì K .
Ïðèìåð. Îáîçíà÷èì F
k m,
( )0 ( , , )k m k m� �N ìíîæåñòâî âñåõ îòîáðàæåíèé
f : K K Kk m k� � , èìåþùèõ âèä
f q x g q h x( , ) ( ) ( )� � ,
ãäå h : K Km k� — òàêàÿ ñþðúåêöèÿ, ÷òî | ( ) | | |h q� ��1 K m k äëÿ âñåõ q �K k ,
à g : K Kk k� — áèåêöèÿ. Òàê êàê äëÿ ëþáîãî îòîáðàæåíèÿ f �F
k m,
( )0 èñòèííû
ðàâåíñòâà (1) è (2), òî F F
k m k m,
( )
,
0 � . Ñëåäîâàòåëüíî, îòîáðàæåíèÿ, ïðèíàäëåæà-
ùèå ìíîæåñòâó F
k m,
( )0 , îïðåäåëÿþò ìíîæåñòâî B
k m,
( )0 ( )
,
( )
,B B
k m k m
0 � ñèëüíî ñâÿç-
íûõ àâòîìàòîâ áåç âûõîäà:
M t t tf q g q h x: ( ) ( )� �� �1 1 ( , )
,
( )f Z� � �F
k m
t0 . (4)
Åñëè k m� , òî ðàâåíñòâî (4) îïðåäåëÿåò ôóíêöèþ ïåðåõîäîâ íåêîòîðûõ íå-
òðèâèàëüíûõ ïîäìíîæåñòâ àâòîìàòîâ íàä êîëüöîì K , èññëåäîâàííûõ â [2, 4],
êîòîðûì, â ÷àñòíîñòè, ïðèíàäëåæàò íåêîòîðûå ïîäìíîæåñòâà ëèíåéíûõ àâòî-
ìàòîâ, èçó÷åííûõ â [1].
Êàê ýòî îáû÷íî ïðèíÿòî â òåîðèè àâòîìàòîâ, ðàñøèðèì îòîáðàæåíèå
f �Fk m, íà ìíîæåñòâî K Kk m� �( ) ðàâåíñòâîì
f q x x f f f f q x x x x( , ) ( ( ( ( , ), ), , ), )1 1 1 2 1� � �t t t� �� (5)
è âñþäó â äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ëþáîå îòîáðàæåíèå f �Fk m, îïðå-
äåëåíî íà ìíîæåñòâå K Kk m� �( ) .
Êàæäûé èíèöèàëüíûé àâòîìàò ( , )M f q0 ( , ),q f0 � �K k
k mF îïðåäåëÿåò îòî-
áðàæåíèå H K Km k
f q, : ( )
0
� � ñâîáîäíîé âõîäíîé ïîëóãðóïïû ( )K m � âî ìíî-
æåñòâî K k ñîñòîÿíèé àâòîìàòà M f , çíà÷åíèÿ êîòîðîãî íà âõîäíîì ñëîâå
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
x x1 � t
m tK�( ) ( )t �N âû÷èñëÿþòñÿ â ñîîòâåòñòâèè ñ ôîðìóëîé
H t tf q x x f q x x, ( ) ( , )
0 1 0 1� �� . (6)
Îòìåòèì, ÷òî èç (5) è (6) âûòåêàåò, ÷òî äëÿ ëþáûõ f �Fk m, è q0 �K k ðàâåíñòâî
H Ht t H ttf q f x xx x x x
f q, , ( )( ) ( )
,0 0 11 1 1� �� �� (7)
èñòèííî äëÿ âñåõ âõîäíûõ ñëîâ x x x1 1
1
� t t
m tK�
��( ) ( )t �N .
Òàêèì îáðàçîì, êàæäûé àâòîìàò M k mf �B , ( ),f �Fk m îïðåäåëÿåò ñåìåéñòâî
õýø-ôóíêöèé Hf f q q
�
�
{ }H
K k, 0 0
, îòîáðàæàþùèõ ìíîæåñòâî ( )K m � âî ìíîæåñò-
âî K k ñîñòîÿíèé àâòîìàòà M f .
2. ÀÍÀËÈÇ ÈÑÑËÅÄÓÅÌÎÉ ÌÎÄÅËÈ
Îñíîâíûå ñâîéñòâà ñåìåéñòâà õýø-ôóíêöèé Hf ( ),f �Fk m õàðàêòåðèçóþòñÿ
ñëåäóþùèì îáðàçîì.
Òåîðåìà 1. Äëÿ ëþáîãî îòîáðàæåíèÿ f �Fk m, , åñëè q q0 0
� ( , )q q0 0� �K k , òî
H Hf q f qu u, ,( ) ( )
0 0
'
äëÿ ëþáîãî âõîäíîãî ñëîâà u � �( )K m .
Äîêàçàòåëüñòâî. Çàôèêñèðóåì îòîáðàæåíèå f �Fk m, . Äîêàæåì òåîðåìó èí-
äóêöèåé ïî äëèíå t âõîäíîãî ñëîâà.
Ïóñòü t �1. Èç (2) âûòåêàåò, ÷òî f q x f q x( , ) ( , )0 1 0 1
� äëÿ ëþáûõ ñîñòîÿíèé
q q0 0, � �K k ( )q q0 0
� àâòîìàòà M f è ëþáîãî âõîäíîãî ñèìâîëà x1 �K m . Òàê
êàê â ñèëó ðàâåíñòâà (6) H f q x f q x, ( ) ( , )
0 1 0 1� è H f q x f q x, ( ) ( , )'0 1 0 1� � , òî
H Hf q f qx x, ,( ) ( )
0 01 1
' äëÿ ëþáûõ q q0 0, � �K k ( )q q0 0
� àâòîìàòà M f è ëþáîãî
âõîäíîãî ñèìâîëà x1 �K m , ÷òî è òðåáîâàëîñü äîêàçàòü.
Ïðåäïîëîæèì, ÷òî òåîðåìà èñòèííà äëÿ t n� , ò.å. åñëè q q0 0
�
( , )q q0 0� �K k , òî H Hn nf q f qx x x x, ,( ) ( )
0 01 1� �
' äëÿ ëþáîãî âõîäíîãî ñëîâà
x x1 � n
m nK�( ) .
Äîêàæåì òåîðåìó äëÿ t n� �1. Â ñèëó (7) äëÿ ëþáûõ ñîñòîÿíèé q q0 0, � �K k
( )q q0 0
� àâòîìàòà M f è ëþáîãî âõîäíîãî ñëîâà x x1 1
1
� n
m nK�
��( ) èñòèííû
ðàâåíñòâà
H Hn n H ntnf q f x xx x x x
f q, , ( )( ) ( )
,0 0 11 1 1� �� �� ,
H Hn n H nnf q f x xx x x x
f q, , ( )( ) ( )
,' '0 0
11 1 1� �� �� .
Ïî ïðåäïîëîæåíèþ èíäóêöèè q x x x x qf q f qn n n nH H�
� �, ,( ) ( )
0 01 1� �' .
À òàê êàê òåîðåìà èñòèííà, åñëè t �1, òî
H H H Hn n n nn nf q f q f q f qx x x x x x, , , ,( ) ( ) ( ) (
0 01 1 1 1� � � ��
�' ' 1 1� x xn n� ) ,
÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà äîêàçàíà.
 ñèëó òåîðåìû 1 ýëåìåíòû êàæäîãî ñåìåéñòâà õýø-ôóíêöèé Hf ( ),f �Fk m —
îòîáðàæåíèÿ ìíîæåñòâà ( )K m � âî ìíîæåñòâî K k ñîñòîÿíèé àâòîìàòà M f , çíà-
÷åíèÿ êîòîðûõ ïîïàðíî ðàçëè÷íû íà ëþáîì âõîäíîì ñëîâå u � �( )K m . Îòñþäà
íåïîñðåäñòâåííî âûòåêàåò, ÷òî èñòèííî ñëåäóþùåå ñëåäñòâèå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 59
Ñëåäñòâèå 1. Äëÿ ëþáîãî îòîáðàæåíèÿ f �Fk m, åñëè q q0 0
� ( , )q q0 0� �K k ,
òî H H
f q f q
q q
, ,
( ) ( )
0 0
1 1� �� � �
'
äëÿ ëþáîãî ñîñòîÿíèÿ q �K k àâòîìàòà M f .
Òåîðåìà 2. Äëÿ ëþáûõ f �Fk m, è q0 �K k ïðè âñåõ t �N èñòèííû ðàâåíñòâà
| ( ) ( ) | | |
,
H K Kt
m t tm k
f q
q
0
1� �� � ( )q t
kK� . (8)
Äîêàçàòåëüñòâî. Çàôèêñèðóåì îòîáðàæåíèå f �Fk m, . Äîêàæåì òåîðåìó èí-
äóêöèåé ïî äëèíå t âõîäíîãî ñëîâà.
Ïóñòü t �1. Èç îïðåäåëåíèÿ îòîáðàæåíèÿ H f q, 0
( , ),q f0 � �K k
k mF âûòåêà-
åò, ÷òî äëÿ ëþáîãî ñîñòîÿíèÿ q1 �K k àâòîìàòà M f èñòèííî ðàâåíñòâî
H K Km m
f q
q x f q x q
,
( ) | ( , )
0
1
1 1 0 1 1
� � � � �{ }. (9)
 ñèëó (1) äëÿ ëþáîãî ñîñòîÿíèÿ q1 �K k àâòîìàòà M f èñòèííî ðàâåíñòâî
| | ( , ) | | |{ }x f q x q1 0 1 1� � � �K Km m k . (10)
Èç (9) è (10) âûòåêàåò, ÷òî åñëè t �1, òî ðàâåíñòâî (8) èñòèííî äëÿ ëþáîãî
ñîñòîÿíèÿ q1 �K k àâòîìàòà M f , ÷òî è òðåáîâàëîñü äîêàçàòü.
Ïðåäïîëîæèì, ÷òî ðàâåíñòâî (8) èñòèííî, åñëè t n� .
Äîêàæåì òåîðåìó äëÿ t n� �1. Èç îïðåäåëåíèÿ îòîáðàæåíèÿ H f q, 0
( , ),q f0 � �K k
k mF è ðàâåíñòâ (6) è (7) âûòåêàåò, ÷òî äëÿ ëþáîãî ñîñòîÿíèÿ
qn
kK� �1 àâòîìàòà M f
H K Kn
m n
n
m n
nf q
q x x f q x x
,
( ) ( ) ( ) | ( ,
0
1
1
1
1 1
1
0 1
�
�
�
�
�
�� � �{ � � 1 1) � ��qn }
� � �
�
�
�
q
f q f qx x x x x q x
n
k
n
K
n n
m n
n n nK H H� � �{ 1 1
1
10
( ) | ( ) & (, , � �� �1 1) qn }
� � � �
�
� �
�
q
f q f q
q q
n
k
n
K
n
m n
n
mH K H K� ( ( ) ( ) ) ( ( ) )
, ,0
1 1
1 . (11)
 ñèëó ðàâåíñòâà (2) äëÿ ëþáîãî ñîñòîÿíèÿ qn
kK� �1 àâòîìàòà M f ìíîæåñò-
âà H K
n
n
m
f q
q
,
( )�
� �1
1 ( )qn
kK� ïîïàðíî íå ïåðåñåêàþòñÿ. Ïîýòîìó èç (11) âûòå-
êàåò, ÷òî
| ( ) ( ) | | ( ) ( ) | |
, , ,
H K H K Hn
m n
n
m n
nf q f q f q
q q
0 0
1
1
1 1�
�
� �� � �
�
�
�
�� 1
1( ) |.q
q
n
m
K
K
n
k
(12)
Ïî ïðåäïîëîæåíèþ èíäóêöèè äëÿ ëþáûõ ñîñòîÿíèé q q0 , n
kK� àâòîìàòà M f
ñïðàâåäëèâî ðàâåíñòâî | ( ) ( ) | | |
,
H K Kn
m n nm k
f q
q
0
1� �� � . À òàê êàê òåîðåìà èñòèí-
íà, åñëè t �1, ò.å. | ( ) | | |
,
H K K
n
n
m m k
f q
q�
�
�� �1
1 äëÿ ëþáûõ ñîñòîÿíèé
q qn n
kK, � �1 àâòîìàòà M f , òî èç (12) âûòåêàåò, ÷òî
| ( ) ( ) | | | | |
,
H q K K Kn
m n nm k m k
Kn
k
f q
q
0
1
1
1�
�
� � �
�
� �
��
� �
�
�
�
�
� � �� �
�
� � ��| | | | | | | |( ) ( ) (K K K Kn m k
K
n m k k n
n
k
1 2 1 21
q
1)m k� ,
÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà äîêàçàíà.
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
Îáîçíà÷èì p
tf q
q
, ,
( ) ( )
0
1 ( ; , ; ),f q q N� � �Fk m
kK t0 âåðîÿòíîñòü òîãî, ÷òî âõîä-
íîå ñëîâî u , ñëó÷àéíî âûáðàííîå èç ìíîæåñòâà ( )K m t , ÿâëÿåòñÿ ðåøåíèåì óðàâ-
íåíèÿ H f q u q, ( )
0
� , à p
tf q, ,
( )
0
2 ( ; ; ),f q N� � �Fk m
kK t0 — âåðîÿòíîñòü òîãî, ÷òî
äëÿ äâóõ ðàçëè÷íûõ âõîäíûõ ñëîâ: u è �u , ñëó÷àéíî âûáðàííûõ èç ìíîæåñòâà
( )K m t , èñòèííî ðàâåíñòâî H Hf q f qu u, ,( ) ( )
0 0
� � .
Ñëåäñòâèå 2. Äëÿ ëþáûõ f �Fk m, è q q0 , �K k ïðè âñåõ t �N èñòèííû ðà-
âåíñòâà
p K
t
k
f q
q
, ,
( ) ( ) | |
0
1 � � ( )t �N . (13)
Äîêàçàòåëüñòâî. Çàôèêñèðóåì îòîáðàæåíèå f �Fk m, , ñîñòîÿíèÿ q q0 , �K k
àâòîìàòà M f è ÷èñëî t �N . Ó÷èòûâàÿ ðàâåíñòâî (8), ïîëó÷èì, ÷òî äëÿ âñåõ t �N
p
H K
K
K
K
t
m t
m t
mt k
f q
f q
q
q
, ,
( ) ,
( )
| ( ) ( ) |
| ( ) |
| |
| |0
01
1
�
�
�
�
�
mt
kK� �| | .
Ñëåäñòâèå äîêàçàíî.
Èç (13) âûòåêàåò, ÷òî äëÿ âåðîÿòíîñòè p
tf q
q
, ,
( ) ( )
0
1 ( ; , ; ),f q q N� � �Fk m
kK t0
èñòèííû ñëåäóþùèå óòâåðæäåíèÿ:
1) âåðîÿòíîñòü p
tf q
q
, ,
( ) ( )
0
1 ( ; , ; ),f q q N� � �Fk m
kK t0 íå çàâèñèò îò ÷èñëà
m �N ( )m k� (ò.å. îò ìîùíîñòè âõîäíîãî àëôàâèòà àâòîìàòà M f ), íè îò äëèíû
t �N t �N âõîäíîãî ñëîâà;
2) âåðîÿòíîñòü p
tf q
q
, ,
( ) ( )
0
1 ( ; , ; ),f q q N� � �Fk m
kK t0 ìîíîòîííî óáûâàåò
ïðè ðîñòå ïàðàìåòðà k �N , ïðè÷åì lim
, ,
( )
k t
p
�
�
f q0
1 0 ( ; ; ),f q N� � �Fk m
kK t0 .
Ñëåäñòâèå 3. Äëÿ ëþáûõ f �Fk m, è q0 �K k èñòèííû ðàâåíñòâà
p K
K
K
t
k
k
mtf q
q
, ,
( ) ( ) | |
| |
| |0
2 1
1
1
� �
�
�
�
�
�
�
�
�
�
�
� ( )t �N . (14)
Äîêàçàòåëüñòâî. Çàôèêñèðóåì îòîáðàæåíèå f �Fk m, , ñîñòîÿíèå q0 �K k àâ-
òîìàòà M f è ÷èñëî t �N. Òàê êàê ìíîæåñòâà âõîäíûõ ñëîâ H K m t
f q
q
,
( ) ( )
0
1� �
( )q �K k ïîïàðíî íå ïåðåñåêàþòñÿ, òî, ó÷èòûâàÿ ðàâåíñòâà (8) è (9), ïîëó÷èì, ÷òî
äëÿ âñåõ t �N (÷åðåç
a
b
�
�
�
�
�
� îáîçíà÷åíî ÷èñëî ñî÷åòàíèé èç à ïî b):
p
H K
K
t
m t
K
m
k
f q
f q
q
q
q
, ,
( )
,
( )
| ( ) ( ) |
| (0
0
2
1
2
�
��
�
�
�
�
�
�
�
�
�
�
) |
, | | ( | | )
, | | ( |t
mt k mt k
K
mt
K K
K K
k
2
0 5 1
0 5�
�
�
�
�
�
�
�
�
�� �
�
�
q
| )mt �
�
1
�
� �
�
�
�
�
�
�
� �
�
�0 5 1 1
0 5 1
, | | ( | | )
, | | ( | |
K K
K K
mt k mt k
K
mt mt
kq
)
, | | ( | | ) | |
, | | ( | | )
�
�
�
�
� �0 5 1
0 5 1
K K K
K K
mt k mt k k
mt mt
�
�
�
�
�
�
�
�
�| |
| |
| |
| | | |
| |
K
K
K
K K
K
mt k
mt
k
mt k
mt
1
1 1
�
� � �
�
� �
�
�
�
�
� �| |
| | | |
| |
| |
| |
| |
K
K K
K
K
K
K
k
mt k
mt
k
k
mt
1 1
1
1
1
1
�
�
�
�
�
�
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 61
Ñëåäñòâèå äîêàçàíî.
Èç (14) âûòåêàåò, äëÿ ÷òî âåðîÿòíîñòè p
tf q, ,
( )
0
2 ( ; ; ),f q N� � �Fk m
kK t0 èñ-
òèííû ñëåäóþùèå óòâåðæäåíèÿ:
1) âåðîÿòíîñòü p
tf q, ,
( )
0
2 ( ; ; ),f q N� � �Fk m
kK t0 ìîíîòîííî âîçðàñòàåò ïðè
ðîñòå äëèíû t �N âõîäíîãî ñëîâà, ïðè÷åì lim | |
, ,
( )
t t
kp K
�
��
f q0
2 ( ,f �Fk m ;
q N0 � �K tk ; ) ;
2) âåðîÿòíîñòü p
tf q, ,
( )
0
2 ( ; ; ),f q N� � �Fk m
kK t0 ìîíîòîííî âîçðàñòàåò ïðè
ðîñòå ïàðàìåòðà m �N ( )m k� , ïðè÷åì lim | |
, ,
( )
m t
kp K
�
��
f q0
2 ( ,f �Fk m ;
q N0 � �K tk ; ) ;
3) ÷èñëî | |K k� ÿâëÿåòñÿ âåðõíåé ãðàíèöåé äëÿ âåðîÿòíîñòè p
tf q, ,
( )
0
2
( ,f �Fk m ; q N0 � �K tk ; ) ïðè ëþáûõ çíà÷åíèÿõ ïàðàìåòðîâ k m, �N ( )k m�
è ïðè ëþáîé äëèíå t �N âõîäíîãî ñëîâà.
3. ÂÛ×ÈÑËÈÒÅËÜÍÀß ÑÒÎÉÊÎÑÒÜ ÈÑÑËÅÄÓÅÌÎÉ ÌÎÄÅËÈ
Îõàðàêòåðèçóåì âíà÷àëå ñëîæíîñòü ïîèñêà âõîäíîãî ñëîâà u �( )K m t , äëÿ êî-
òîðîãî ïðè çàäàííîì çíà÷åíèè q �K k èñòèííî ðàâåíñòâî H f q u q, ( )
0
� , à òàê-
æå ñëîæíîñòü ïîèñêà âõîäíûõ ñëîâ u u, ~ ( )� K m t ( ~ )u u
, äëÿ êîòîðûõ èñòèí-
íî ðàâåíñòâî H Hf q f qu u, ,( ) (~ )
0 0
� â ïðåäïîëîæåíèè, ÷òî ýêñïåðèìåíòàòîðó èç-
âåñòíî ñåìåéñòâî õýø-ôóíêöèé Hf ( ),f �Fk m , ò.å. èçâåñòíî îòîáðàæåíèå
f �Fk m, äëÿ ñèñòåìû óðàâíåíèé (3). Âîçìîæíû ñëåäóþùèå äâà ñëó÷àÿ.
Ñëó÷àé 1. Ýêñïåðèìåíòàòîðó èçâåñòíî íà÷àëüíîå ñîñòîÿíèå q0 �K k àâòî-
ìàòà M k mf �B , , ò.å. èíûìè ñëîâàìè, èçâåñòíà õýø-ôóíêöèÿ H f q, 0
.
Îõàðàêòåðèçóåì ñëîæíîñòü ïîèñêà òàêîãî âõîäíîãî ñëîâà x x1 � t
m tK�( )
( )t �N , ÷òî H tf q x x q, ( )
0 1 � � , ãäå q �K k — ôèêñèðîâàííîå ñîñòîÿíèå àâòîìà-
òà M f .
Åñëè t �1, òî ýòà ñëîæíîñòü ñîâïàäàåò ñî ñëîæíîñòüþ ïîèñêà îäíîãî (íå âàæ-
íî, êàêîãî èìåííî) ðåøåíèÿ x1 �K m óðàâíåíèÿ H f q x q, ( )
0 1 � èëè, èíûìè ñëîâà-
ìè, óðàâíåíèÿ f q x q( , )0 1 � .
Åñëè æå t �1, òî â êà÷åñòâå x x1 1� t� äîñòàòî÷íî âûáðàòü ëþáîå âõîäíîå
ñëîâî, à â êà÷åñòâå âõîäíîãî ñèìâîëà x t — ëþáîå ðåøåíèå óðàâíåíèÿ
f x x x qf q( ( ), ),H t t0 1 1� � � .
Òàêèì îáðàçîì, åñëè èçâåñòíî íà÷àëüíîå ñîñòîÿíèå q0 �K k àâòîìàòà
M k mf �B , , òî ïðè ëþáîì t �N ñëîæíîñòü ïîèñêà òàêîãî âõîäíîãî ñëîâà
x x1 � t
m tK�( ) ( )t �N , ÷òî H tf q x x q, ( )
0 1 � � , ñîâïàäàåò ñî ñëîæíîñòüþ ïî-
èñêà îäíîãî (íå âàæíî, êàêîãî èìåííî) ðåøåíèÿ x �K m óðàâíåíèÿ f q x q( , ) ~�
ïðè èçâåñòíûõ çíà÷åíèÿõ q q, ~ �K k .
Îõàðàêòåðèçóåì òåïåðü ñëîæíîñòü ïîèñêà äâóõ ðàçëè÷íûõ òàêèõ âõîäíûõ ñëîâ:
x x1 � t
m tK�( ) è ~ ~ ( )x x1 � t
m tK� , ÷òî H Ht tf q f qx x x x, ,( ) (~ ~ )
0 01 1� �� .
Ïóñòü t �1. Åñëè k m� , òî â ñèëó (1) íå ñóùåñòâóåò äâóõ ðàçëè÷íûõ âõîä-
íûõ ñèìâîëîâ: x1 è ~x1, äëÿ êîòîðûõ èñòèííî ðàâåíñòâî f q x f q x( , ) ( , ~ )0 1 0 1� .
Åñëè æå k m� , òî ýòà ñëîæíîñòü ñîâïàäàåò ñî ñëîæíîñòüþ ïîèñêà îäíîãî (íå
âàæíî, êàêîãî èìåííî) ðåøåíèÿ ( , ~ )x x1 1 � �K Km m ( ~ )x x1 1
óðàâíåíèÿ
f q x f q x( , ) ( , ~ )0 1 0 1� .
Ïóñòü t �1. Åñëè k m� , òî â êà÷åñòâå x x1 1� t� äîñòàòî÷íî âûáðàòü ëþáîå
âõîäíîå ñëîâî, ïîëîæèòü ~ ~x x x x1 1 1 1� �t t� �� , à â êà÷åñòâå x t è ~x t âûáðàòü
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
ëþáûå äâà òàêèå ðàçëè÷íûå âõîäíûå ñèìâîëû, ÷òî f f q x x x( ( , ), )0 1 1� t t� �
� �f f q x x x( ( , ), ~ )0 1 1� t t .
Åñëè æå k m� , òî â êà÷åñòâå x x1 1� t� è ~ ~x x1 1� t� äîñòàòî÷íî âûáðàòü ëþ-
áûå äâà òàêèå âõîäíûå ñëîâà, ÷òî f q x x f q x x( , ) ( , ~ ~ )0 1 1 0 1 1� �t t� �
, à êà÷åñòâå
x t è ~x t — ëþáûå òàêèå âõîäíûå ñèìâîëû, ÷òî f f q x x x( ( , ), )0 1 1� t t� �
� �f f q x x x( ( , ~ ~ ), ~ )0 1 1� t t . Ïðè ýòîì äîïóñêàåòñÿ ðàâåíñòâî x xt t� ~ , òàê êàê
x x x x1 1 1 1� �t t� �
~ ~ .
Òàêèì îáðàçîì, åñëè èçâåñòíî íà÷àëüíîå ñîñòîÿíèå q0 �K k àâòîìàòà
M k mf �B , , òî ïðè ëþáîì t �N ñëîæíîñòü ïîèñêà äâóõ ðàçëè÷íûõ âõîäíûõ ñëîâ:
x x1 � t
m tK�( ) è ~ ~ ( )x x1 � t
m tK� , äëÿ êîòîðûõ èñòèííî ðàâåíñòâî
H Ht tf q f qx x x x, ,( ) (~ ~ )
0 01 1� �� , îïðåäåëÿåòñÿ ñëîæíîñòüþ ïîèñêà îäíîãî (íå
âàæíî, êàêîãî èìåííî) ðåøåíèÿ ( , ~ )x x � �K Km m (âîçìîæíî, ïðè äîïîëíèòåëü-
íîì óñëîâèè x x
~) óðàâíåíèÿ f q x f q x( , ) (~, ~ )� ïðè èçâåñòíûõ çíà÷åíèÿõ
q q, ~ �K k .
Îòìåòèì, ÷òî åñëè m k� , òî ÷èñëî ñêàëÿðíûõ óðàâíåíèé, îïðåäåëÿåìûõ êàê
âåêòîðíûì óðàâíåíèåì f q x q( , ) ~� , òàê è âåêòîðíûì óðàâíåíèåì f q x f q x( , ) (~, ~ )� ,
ìåíüøå ÷èñëà íåèçâåñòíûõ. Ýòî îáñòîÿòåëüñòâî ñóùåñòâåííî óñëîæíÿåò ïåðåáîð
â ïðîöåññå ïîèñêà ðåøåíèé óðàâíåíèé íàä êîíå÷íûì êîëüöîì ñ äåëèòåëÿìè íóëÿ
(ñì., íàïðèìåð, [4]).
Ñëó÷àé 2. Ýêñïåðèìåíòàòîðó íå èçâåñòíî íà÷àëüíîå ñîñòîÿíèå q0 �K k àâ-
òîìàòà M k mf �B , (ïðè ýòîì, êàê îáû÷íî, ïðåäïîëàãàåòñÿ, ÷òî ëþáîå ñîñòîÿíèå
q0 �K k ìîæåò áûòü âûáðàíî â êà÷åñòâå íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòà
M k mf �B , ñ îäíîé è òîé æå âåðîÿòíîñòüþ), ò.å. èíûìè ñëîâàìè, èçâåñòíî ñåìåé-
ñòâî Hf õýø-ôóíêöèé, íî íå èçâåñòíà õýø-ôóíêöèÿ H f q f, 0
�H .
Ïóñòü t �1. Òîãäà åäèíñòâåííûì ñïîñîáîì ïîèñêà âõîäíîãî ñèìâîëà
x1 �K m , äëÿ êîòîðîãî èñòèííî ðàâåíñòâî f q x q( , )0 1 � ïðè ôèêñèðîâàííûõ çíà-
÷åíèÿõ q q0 , �K k , à òàêæå (ïðè óñëîâèè, ÷òî k m� ) ïîèñêà âõîäíûõ ñèìâîëîâ
x x1 1, ~ �K m ( ~ )x x1 1
, äëÿ êîòîðûõ èñòèííî ðàâåíñòâî f q x f q x( , ) ( , ~ )0 1 0 1� ïðè
ôèêñèðîâàííîì çíà÷åíèè q0 �K k, ÿâëÿåòñÿ ñëó÷àéíûé âûáîð âõîäíûõ ñèìâîëîâ.
Èç (13) âûòåêàåò, ÷òî âåðîÿòíîñòü òîãî, ÷òî ïðè ñëó÷àéíîì âûáîðå âõîäíîãî
ñèìâîëà x1 �K m èñòèííî ðàâåíñòâî f q x q( , )0 1 � , ðàâíà p K k
f q
q
, ,
( ) ( ) | |
0 1
1 � � .
Àíàëîãè÷íûì îáðàçîì èç (14) âûòåêàåò, ÷òî âåðîÿòíîñòü òîãî, ÷òî ïðè ñëó÷àé-
íîì âûáîðå äâóõ ðàçëè÷íûõ âõîäíûõ ñèìâîëîâ x1 �K m è ~x1 �K m èñòèííî ðà-
âåíñòâî f q x f q x( , ) ( , ~ )0 1 0 1� , ðàâíà
p K
K
K
k
k
mf q
q
, ,
( ) ( ) | |
| |
| |0 1
2 1
1
1
� �
�
�
�
�
�
�
�
�
�
�
� .
Ïóñòü t �1. Âîçìîæíû ñëåäóþùèå äâå ñèòóàöèè.
Ñèòóàöèÿ 1. Ýêñïåðèìåíòàòîð èìååò âîçìîæíîñòü íàáëþäàòü ñîñòîÿíèå èñ-
ñëåäóåìîãî àâòîìàòà M k mf �B , íà ïðîìåæóòî÷íûõ âû÷èñëåíèÿõ. Òîãäà, âûáðàâ
ïðîèçâîëüíûé âõîäíîé ñèìâîë x1 �K m , ýêñïåðèìåíòàòîð îïðåäåëÿåò òåêóùåå
ñîñòîÿíèå f q x( , )0 1 èññëåäóåìîãî àâòîìàòà M k mf �B , , è ñèòóàöèÿ ñâîäèòñÿ ê
ðàññìîòðåííîìó âûøå ñëó÷àþ 1.
Ñèòóàöèÿ 2. Ýêñïåðèìåíòàòîð íå èìååò âîçìîæíîñòè íàáëþäàòü ñîñòîÿíèå
èññëåäóåìîãî àâòîìàòà M k mf �B , íà ïðîìåæóòî÷íûõ âû÷èñëåíèÿõ. Òîãäà åäèíñò-
âåííûì ñïîñîáîì ïîèñêà âõîäíîãî ñëîâà u �( )K m t , äëÿ êîòîðîãî èñòèííî ðàâå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 63
íñòâî H f q u q, ( )
0
� , à òàêæå ïîèñêà âõîäíûõ ñëîâ u u, ~ ( )� K m t ( ~ )u u
, äëÿ êîòî-
ðûõ èñòèííî ðàâåíñòâî H Hf q f qu u, ,( ) (~ )
0 0
� , ÿâëÿåòñÿ ñëó÷àéíûé âûáîð âõîäíûõ
ñëîâ. Âåðîÿòíîñòü òîãî, ÷òî ïðè ñëó÷àéíîì âûáîðå âõîäíîãî ñëîâà u �( )K m t èñ-
òèííî ðàâåíñòâî H f q u q, ( )
0
� , îïðåäåëÿåòñÿ ôîðìóëîé (13), à âåðîÿòíîñòü òîãî,
÷òî ïðè ñëó÷àéíîì âûáîðå âõîäíûõ ñëîâ u u, ~ ( )� K m t ( ~ )u u
èñòèííî ðàâåíñòâî
H Hf q f qu u, ,( ) (~ )
0 0
� , îïðåäåëÿåòñÿ ôîðìóëîé (14).
Âûñîêàÿ ñëîæíîñòü ïîèñêà âõîäíîãî ñëîâà u �( )K m t , äëÿ êîòîðîãî èñòèííî
ðàâåíñòâî H f q u q, ( )
0
� , à òàêæå ïîèñêà âõîäíûõ ñëîâ u u, ~ ( )� K m t ( ~ )u u
, äëÿ
êîòîðûõ èñòèííî ðàâåíñòâî H Hf q f qu u, ,( ) (~ ) ,
0 0
� îáîñíîâûâàþò âîçìîæíîñòü èñ-
ïîëüçîâàíèÿ ñåìåéñòâà õýø-ôóíêöèé Hf ( ),f �Fk m â àëãîðèòìàõ çàùèòû èí-
ôîðìàöèè. Ïðè ýòîì íà÷àëüíîå ñîñòîÿíèå q0 �K k àâòîìàòà M k mf �B , öåëåñîîáðàç-
íî èñïîëüçîâàòü â êà÷åñòâå ñåêðåòíîãî ñåàíñîâîãî êëþ÷à èñïîëüçóåìîé õýø-ôóíêöèè.
Ðàññìîòðèì òåïåðü çàäà÷ó ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè ñåìåéñòâà
õýø-ôóíêöèé Hf ( ),f �Fk m .
Ïóñòü (3) — ñèñòåìà óðàâíåíèé ñ ïàðàìåòðàìè íàä êîëüöîì K , ò.å.
f q x F q x( , ) ( , , , , )t t r t ta a� ��1 1 1� ( )t � �Z ,
ãäå a a Kr1, ,� � — ïàðàìåòðû. Òàêèì îáðàçîì, ñèñòåìà óðàâíåíèé (3) èìååò âèä
q F q xt r t ta a� ��1 1 1( , , , , )� ( )t � �Z , (15)
ãäå îòîáðàæåíèå F èçâåñòíî ýêñïåðèìåíòàòîðó.
Ïðåäïîëîæèì, ÷òî ýêñïåðèìåíòàòîðó íå èçâåñòíû çíà÷åíèÿ ïàðàìåòðîâ ñèñ-
òåìû óðàâíåíèé (15), íî îí èìååò âîçìîæíîñòü â êàæäûé ìîìåíò íàáëþäàòü ñî-
ñòîÿíèå èññëåäóåìîãî àâòîìàòà. Òîãäà èäåíòèôèêàöèÿ ñåìåéñòâà õýø-ôóíê-
öèé (15) ÿâëÿåòñÿ çàäà÷åé ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà, ïðèíàäëå-
æàùåãî çàäàííîìó ìíîæåñòâó àâòîìàòîâ íàä êîëüöîì K .
Ïðè âîçìîæíîñòè ýêñïåðèìåíòàòîðà ïðîâîäèòü òîëüêî ïðîñòîé ýêñïåðèìåíò
ðåøåíèå çàäà÷è ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà ñâîäèòñÿ ê ïîèñêó
âõîäíîãî ñëîâà x x1 � n
m nK�( ) çàðàíåå íåèçâåñòíîé äëèíû n r� â öåëÿõ ôîð-
ìèðîâàíèÿ è ðåøåíèÿ íàä êîëüöîì K ñèñòåìû óðàâíåíèé
q F q xi r i ia a� �( , , , , )1 1� ( , , )i n�1 � (16)
îòíîñèòåëüíî íåèçâåñòíûõ a a Kr1, ,� � .
Ïðè âîçìîæíîñòè ýêñïåðèìåíòàòîðà ïðîâîäèòü l-êðàòíûé ýêñïåðèìåíò (ãäå
l � 2 — ôèêñèðîâàííîå ÷èñëî) ðåøåíèå çàäà÷è ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè
àâòîìàòà ñâîäèòñÿ ê ïîèñêó l-ýëåìåíòíîãî ìíîæåñòâà âõîäíûõ ñëîâ
x x
1
( ) ( ) ( )i
n
i m n
i
iK� � ( , , )i l�1 � , äëèíû ni êîòîðûõ çàðàíåå íåèçâåñòíû, â öåëÿõ
ôîðìèðîâàíèÿ è ðåøåíèÿ íàä êîëüöîì K ñèñòåìû óðàâíåíèé
q F q x xj
i
r
i
j
ia a( ) ( ) ( )( , , , , )� 1 0 1
� � ( , , ; , , )i l j ni� �1 1� � (17)
îòíîñèòåëüíî íåèçâåñòíûõ a a Kr1, ,� � .
Ñèòóàöèÿ íåñêîëüêî îòëè÷àåòñÿ, åñëè ýêñïåðèìåíòàòîð ìîæåò ñêîëüêî
óãîäíî ðàç óñòàíàâëèâàòü èññëåäóåìûé àâòîìàò â ëþáîå òðåáóåìîå íà÷àëüíîå ñî-
ñòîÿíèå è ïðè êàæäîé óñòàíîâêå íà÷àëüíîãî ñîñòîÿíèÿ ïðîâîäèòü ñ èññëåäóåìûì
àâòîìàòîì êðàòíûé ýêñïåðèìåíò ëþáîé êðàòíîñòè.  ýòîì ñëó÷àå äëÿ ðåøåíèÿ
çàäà÷è ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè àâòîìàòà äîñòàòî÷íî ñôîðìèðîâàòü è
ðåøèòü íàä êîëüöîì K ñèñòåìó óðàâíåíèé
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
~ ( , , , , )q q x� F a ar1 � ( , )q x� �K Kk m (18)
îòíîñèòåëüíî íåèçâåñòíûõ a a Kr1, ,� � .
Îòìåòèì, ÷òî â êîëüöå ñ äåëèòåëÿìè íóëÿ ïðè äîñòàòî÷íî áîëüøîì çíà÷å-
íèè k ðåøåíèå ëþáîé èç ñèñòåì óðàâíåíèé (16)–(18) ÿâëÿåòñÿ ñëîæíîé çàäà÷åé
èç-çà ïåðåáîðà, îáóñëîâëåííîãî èìåííî íàëè÷èåì äåëèòåëåé íóëÿ.
Òàêèì îáðàçîì, ïðè èñïîëüçîâàíèè ñåìåéñòâà õýø-ôóíêöèé Hf ( ),f �Fk m
â àëãîðèòìàõ çàùèòû èíôîðìàöèè öåëåñîîáðàçíî èñïîëüçîâàòü ïàðàìåòðû, âõî-
äÿùèå â óðàâíåíèå (15), â êà÷åñòâå äîëãîâðåìåííîãî ñåêðåòíîãî êëþ÷à.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå èññëåäîâàíû ñåìåéñòâà õýø-ôóíêöèé, îïðåäåëÿåìûå ñèëüíî
ñâÿçàííûìè àâòîìàòàìè áåç âûõîäà íàä ïðîèçâîëüíûì êîíå÷íûì êîëüöîì
K � �
( , , )K ( | | )K � 2 . Àíàëèç âû÷èñëèòåëüíîé ñòîéêîñòè ïîêàçûâàåò, ÷òî ïðè
íåëèíåéíîì îòîáðàæåíèè f �Fk m, ýòè õåø-ôóíêöèè ìîãóò èñïîëüçîâàòüñÿ â ïðî-
öåññå ðåøåíèÿ çàäà÷ çàùèòû èíôîðìàöèè. Ïðè ýòîì ïàðàìåòðû, ïðèñóòñòâóþùèå
â îòîáðàæåíèè f �Fk m, , ìîãóò èñïîëüçîâàòüñÿ â êà÷åñòâå äîëãîâðåìåííîãî ñåêðåò-
íîãî êëþ÷à, ÷òî äàåò äîïîëíèòåëüíóþ âîçìîæíîñòü öåíòðó ðàñïðåäåëåíèÿ êëþ÷åé
íåçàâèñèìî âàðüèðîâàòü ðàñïðåäåëåíèå ñåìåéñòâ õýø-ôóíêöèé Hf ( ),f �Fk m ìåæ-
äó îòäåëüíûìè ãðóïïàìè ïîëüçîâàòåëåé. Êðîìå òîãî, â ðåçóëüòàòå èñïîëüçîâàíèÿ
íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòà M k mf �B , ( ),f �Fk m â êà÷åñòâå ñåêðåòíîãî ñåàí-
ñîâîãî êëþ÷à îòäåëüíûå ïîëüçîâàòåëè (èëè èõ ãðóïïû) íåçàâèñèìî îò öåíòðà ðàñ-
ïðåäåëåíèÿ êëþ÷åé ìîãóò âàðüèðîâàòü õåø-ôóíêöèè â ðàçëè÷íûõ ñåàíñàõ ñâÿçè.
Äåòàëüíûé àíàëèç ñåìåéñòâ õýø-ôóíêöèé Hf ( ),f �Fk m , îïðåäåëÿåìûõ ïîëè-
íîìàìè òîãî èëè èíîãî âèäà íàä àññîöèàòèâíî-êîììóòàòèâíûì êîëüöîì K ñ åäèíè-
öåé, ïðåäñòàâëÿåò äàëüíåéøåå íàïðàâëåíèå èññëåäîâàíèé. Àíàëèç ñåìåéñòâ
õýø-ôóíêöèé Hf ( ),f �Fk m , îïðåäåëÿåìûõ íàä àññîöèàòèâíûìè íåêîììóòàòèâíû-
ìè êîëüöàìè ñ åäèíèöåé (â ÷àñòíîñòè, íàä êîëüöàìè êâàäðàòíûõ ìàòðèö òîãî èëè
èíîãî âèäà íàä êîíå÷íûìè ïîëÿìè), ÿâëÿåòñÿ äðóãèì íàïðàâëåíèåì èññëåäîâàíèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ ê î á å ë å â Â . Â . Àíàëèç ñòðóêòóðû êëàññà ëèíåéíûõ àâòîìàòîâ íàä êîëüöîì Z
pk // Êèáåð-
íåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 3. — Ñ. 60–74.
2. Ñ ê î á å ë å â Â . Â . , Ñ ê î á å ë å â Â . Ã . Àíàëèç øèôðñèñòåì. — Äîíåöê: ÈÏÌÌ ÍÀÍ
Óêðàèíû, 2009. — 479 ñ.
3. Ñ ê î á å ë å â  .  . , Ñ ê î á å ë å â  . à . Î ñëîæíîñòè àíàëèçà àâòîìàòîâ íàä êîíå÷íûì êîëü-
öîì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 4. — Ñ. 17–30.
4. Ñ ê î á å ë å â Â . Â . , Ã ë à ç ó í î â Í . Ì . , Ñ ê î á å ë å â Â . Ã . . Ìíîãîîáðàçèÿ íàä êîëüöàìè.
Òåîðèÿ è ïðèëîæåíèÿ. — Äîíåöê: ÈÏÌÌ ÍÀÍ Óêðàèíû, 2011. — 323 ñ.
5. À ë ô å ð î â À . Ï . , Ç ó á î â À . Þ . , Ê ó ç ü ì è í À . Ñ . è ä ð . Îñíîâû êðèïòîãðàôèè. — Ì.:
Ãåëèîñ ÀÐÂ, 2002. — 480 ñ.
6. Õ à ð è í Þ . Ñ . , Á å ð í è ê  . È . , Ì à ò â å å â à .  . è ä ð . Ìàòåìàòè÷åñêèå è êîìïüþòåð-
íûå îñíîâû êðèïòîëîãèè. — Ìèíñê: Íîâîå çíàíèå, 2003. — 382 ñ.
7. È â à í î â Ì . À . Êðèïòîãðàôè÷åñêèå ìåòîäû çàùèòû èíôîðìàöèè â êîìïüþòåðíûõ ñèñòåìàõ
è ñåòÿõ. — Ì.: ÊÓÄÈÖ-ÎÁÐÀÇ, 2001. — 368 ñ.
8. Ø í à é å ð Á . Ïðèêëàäíàÿ êðèïòîãðàôèÿ. Ïðîòîêîëû, àëãîðèòìû, èñõîäíûå òåêñòû íà ÿçûêå
ÑÈ. — Ì.: Òðèóìô, 2003. — 816 ñ.
9. Ò ð à õ ò å í á ð î ò Á . À . , Á à ð ç ä è í ü ß . Ì . Êîíå÷íûå àâòîìàòû (ïîâåäåíèå è ñèíòåç). —
Ì.: Íàóêà, 1970. — 400 ñ.
10. B o l l o b � s B . Modern graph theory. — N.Y.: Springer-Verlag, 1998. — 394 p.
Ïîñòóïèëà 30.01.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 65
|