Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров
Досліджуються властивості раундових функцій блокових шифрів, що характеризують їх практичну стійкість відносно білінійного методу криптоаналізу. Отримано верхні межі незбалансованості білінійних апроксимацій раундових функцій шифрів, які містять ключовий суматор за модулем степеня числа 2, зокрема...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45195 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров / А.Н. Алексейчук, А.С. Шевцов // Кибернетика и системный анализ. — 2010. — № 3. — С. 42-51. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-45195 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-451952025-02-23T18:59:52Z Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров Верхні оцінки незбалансованості білінійних апроксимацій раундових функцій блокових шифрів Upper estimates of imbalance of bilinear approximations for raund functions of block ciphers Алексейчук, А.Н. Шевцов, А.С. Кибернетика Досліджуються властивості раундових функцій блокових шифрів, що характеризують їх практичну стійкість відносно білінійного методу криптоаналізу. Отримано верхні межі незбалансованості білінійних апроксимацій раундових функцій шифрів, які містять ключовий суматор за модулем степеня числа 2, зокрема алгоритмів шифрування ГОСТ та «Калина». The raund functions properties of block ciphers that characterize practical security against bilinear cryptanalysis techniques are researched. Upper bounds of imbalance of bilinear approximations for raund functions of block ciphers with key adder modulo the degree of number 2, in particular, the encryption algorithms of the GOST and “Kalina” are obtained. 2010 Article Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров / А.Н. Алексейчук, А.С. Шевцов // Кибернетика и системный анализ. — 2010. — № 3. — С. 42-51. — Бібліогр.: 13 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45195 621.391:519.2 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Алексейчук, А.Н. Шевцов, А.С. Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров Кибернетика и системный анализ |
| description |
Досліджуються властивості раундових функцій блокових шифрів, що характеризують їх практичну стійкість відносно білінійного методу криптоаналізу. Отримано верхні межі незбалансованості білінійних апроксимацій раундових функцій шифрів, які містять ключовий суматор за модулем степеня числа 2, зокрема алгоритмів шифрування ГОСТ та «Калина». |
| format |
Article |
| author |
Алексейчук, А.Н. Шевцов, А.С. |
| author_facet |
Алексейчук, А.Н. Шевцов, А.С. |
| author_sort |
Алексейчук, А.Н. |
| title |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| title_short |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| title_full |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| title_fullStr |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| title_full_unstemmed |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| title_sort |
верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/45195 |
| citation_txt |
Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров / А.Н. Алексейчук, А.С. Шевцов // Кибернетика и системный анализ. — 2010. — № 3. — С. 42-51. — Бібліогр.: 13 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT aleksejčukan verhnieocenkinesbalansirovannostibilinejnyhapproksimacijraundovyhfunkcijbločnyhšifrov AT ševcovas verhnieocenkinesbalansirovannostibilinejnyhapproksimacijraundovyhfunkcijbločnyhšifrov AT aleksejčukan verhníocínkinezbalansovanostíbílíníjnihaproksimacíjraundovihfunkcíjblokovihšifrív AT ševcovas verhníocínkinezbalansovanostíbílíníjnihaproksimacíjraundovihfunkcíjblokovihšifrív AT aleksejčukan upperestimatesofimbalanceofbilinearapproximationsforraundfunctionsofblockciphers AT ševcovas upperestimatesofimbalanceofbilinearapproximationsforraundfunctionsofblockciphers |
| first_indexed |
2025-11-24T13:34:48Z |
| last_indexed |
2025-11-24T13:34:48Z |
| _version_ |
1849678929381556224 |
| fulltext |
ÓÄÊ 621.391:519.2
À.Í. ÀËÅÊÑÅÉ×ÓÊ, À.Ñ. ØÅÂÖÎÂ
ÂÅÐÕÍÈÅ ÎÖÅÍÊÈ ÍÅÑÁÀËÀÍÑÈÐÎÂÀÍÍÎÑÒÈ ÁÈËÈÍÅÉÍÛÕ
ÀÏÏÐÎÊÑÈÌÀÖÈÉ ÐÀÓÍÄÎÂÛÕ ÔÓÍÊÖÈÉ ÁËÎ×ÍÛÕ ØÈÔÐÎÂ
Êëþ÷åâûå ñëîâà: áëî÷íûé øèôð, ñòàòèñòè÷åñêàÿ àòàêà, áèëèíåéíûé êðèïòî-
àíàëèç, áèëèíåéíàÿ àïïðîêñèìàöèÿ áóëåâîé ôóíêöèè, ÃÎÑÒ 28147-89, «Êàëèíà».
ÂÂÅÄÅÍÈÅ
Ïðè èññëåäîâàíèè ñòîéêîñòè áëî÷íûõ øèôðîâ îòíîñèòåëüíî ñòàòèñòè÷åñêèõ ìå-
òîäîâ êðèïòîàíàëèçà òðåáóåòñÿ âû÷èñëÿòü èëè îöåíèâàòü çíà÷åíèÿ ïàðàìåòðîâ
âèäà
l f m m f x x k
x Vk V mm
*
( ) ( , ( ))( ) ( )� �� �
�
�
�
�
�
�
� �
��
��2 2 1
2
, (1)
ãäå � � �( , ... , )s sp0 1 — ïîäñòàíîâêà íà ìíîæåñòâå Vm
m�{ }0 1, , çàäàííàÿ ñ ïî-
ìîùüþ íàáîðà ïîäñòàíîâîê (s-áëîêîâ) s V Vi t t:
, i p� �0 1, , pt m� , * — êîììó-
òàòèâíàÿ ãðóïïîâàÿ îïåðàöèÿ íà ìíîæåñòâå Vm , à f — ôóíêöèÿ, ïðèíàäëåæàùàÿ
íåêîòîðîìó êëàññó � áóëåâûõ ôóíêöèé 2m ïåðåìåííûõ. Îáû÷íî ôóíêöèþ f íà-
çûâàþò àïïðîêñèìàöèåé (ìåæäó âõîäàìè è âûõîäàìè) áóëåâà îòîáðàæåíèÿ
x x k� �( * ), x Vm� , êîòîðîå èñïîëüçóåòñÿ â êîíñòðóêöèè ðàóíäîâîé ôóíêöèè
äàííîãî áëî÷íîãî øèôðà, à çíà÷åíèå (1) — (ñðåäíåé) íåñáàëàíñèðîâàííîñòüþ
óêàçàííîé àïïðîêñèìàöèè. Ïðè ýòîì êëàññ � àïïðîêñèìèðóþùèõ ôóíêöèé, êàê
ïðàâèëî, îïðåäåëÿåòñÿ êîíêðåòíûì ìåòîäîì êðèïòîàíàëèçà. Òàê, â ñëó÷àå ëèíåé-
íîãî êðèïòîàíàëèçà [1] f f x y� ( , ) ÿâëÿåòñÿ ëèíåéíîé áóëåâîé ôóíêöèåé, ñóùåñ-
òâåííî çàâèñÿùåé îò êàæäîãî àðãóìåíòà x y Vm, � ; äëÿ îáîáùåííîãî ëèíåéíîãî
êðèïòîàíàëèçà [2] f x y g x h y( , ) ( ) ( )� � , x y Vm, � , ãäå g è h — óðàâíîâåøåííûå
áóëåâû ôóíêöèè m ïåðåìåííûõ; áèëèíåéíûé ìåòîä êðèïòîàíàëèçà [3] ñâÿçàí
ñ êëàññîì áèëèíåéíûõ áóëåâûõ ôóíêöèé è ò.ä. Îòìåòèì ðàáîòû [4, 5], â êîòî-
ðûõ ïðåäëîæåíû îáùèå ïîäõîäû ê ïîñòðîåíèþ ïåðå÷èñëåííûõ (è äðóãèõ) ñòà-
òèñòè÷åñêèõ ìåòîäîâ êðèïòîàíàëèçà áëî÷íûõ øèôðîâ. Âåðõíèå îöåíêè íàäåæ-
íîñòè ñòàòèñòè÷åñêèõ àòàê íà áëî÷íûå øèôðû ïîëó÷åíû â [4] è óñèëåíû â [6]
äëÿ ñëó÷àÿ àòàê ïåðâîãî ïîðÿäêà.
Çàìåòèì, ÷òî íà ïðàêòèêå íàõîæäåíèå íåòðèâèàëüíûõ îöåíîê ïàðàìåòðà (1), çà
èñêëþ÷åíèåì îòäåëüíûõ ñïåöèàëüíûõ ñëó÷àåâ, ïðåäñòàâëÿåò ñîáîé íåïðîñòóþ çà-
äà÷ó, ïîñêîëüêó m ÿâëÿåòñÿ äîñòàòî÷íî áîëüøèì ÷èñëîì (íàïðèìåð, m ðàâíî 64
èëè 128).  [7] ïîëó÷åíû âåðõíèå îöåíêè ïàðàìåòðà (1), ÿâíî çàâèñÿùèå îò ÷èñëî-
âûõ õàðàêòåðèñòèê s-áëîêîâ si , i p� �0 1, , â ñëó÷àå, êîãäà * — îïåðàöèÿ ñëîæåíèÿ
ïî ìîäóëþ 2m íà ìíîæåñòâå äâîè÷íûõ öåëûõ ÷èñåë, ñîîòâåòñòâóþùèõ âåêòîðàì
èç Vm , à f — ëèíåéíàÿ áóëåâà ôóíêöèÿ. Ýòè îöåíêè èñïîëüçîâàíû â [7–9] äëÿ íà-
õîæäåíèÿ âåðõíèõ ãðàíèö âåðîÿòíîñòåé ëèíåéíûõ õàðàêòåðèñòèê øèðîêîãî êëàññà
áëî÷íûõ øèôðîâ, ïîñòðîåííûõ ñ èñïîëüçîâàíèåì êëþ÷åâîãî ñóììàòîðà ïî ìîäó-
ëþ 2m , ïîäîáíûõ àëãîðèòìàì øèôðîâàíèÿ ÃÎÑÒ [10] è «Êàëèíà» [11] (îòìåòèì,
÷òî ïîñëåäíèé èç íèõ ÿâëÿåòñÿ êàíäèäàòîì íà Íàöèîíàëüíûé ñòàíäàðò øèôðîâàíèÿ
Óêðàèíû).  ÷àñòíîñòè, ïðèìåíåíèå óêàçàííûõ ãðàíèö ê øèôðó «Êàëèíà» [9] ïî-
çâîëèëî îáîñíîâàòü åãî ïðàêòè÷åñêóþ ñòîéêîñòü îòíîñèòåëüíî ëèíåéíîãî ìåòîäà
êðèïòîàíàëèçà áåç èñïîëüçîâàíèÿ êàêèõ-ëèáî óïðîùàþùèõ ïðåäïîëîæåíèé. Âåð-
õíèå îöåíêè ïàðàìåòðà (1) äëÿ áîëåå øèðîêîãî êëàññà «îáîáùåííî-ëèíåéíûõ»
ôóíêöèé ( f x y g x g x h y h yp p p p( , ) ( ) ( ) ( ) ( )� ��� � ���� � � �0 0 1 1 0 0 1 1 , ãäå
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
© À.Í. Àëåêñåé÷óê, À.Ñ. Øåâöîâ, 2010
x x xp� �( , , )0 1� , y y yp� �( , , )0 1� , x y Vi i t, � , g h Vi i t, : ,
{ }0 1, i p� �0 1, ) è óêà-
çàííîé âûøå îïåðàöèè * ïîëó÷åíû â [12].
 íàñòîÿùåé ñòàòüå ðåøàåòñÿ çàäà÷à ïîñòðîåíèÿ âåðõíèõ ãðàíèö ïàðàìåòðà (1)
äëÿ áèëèíåéíûõ áóëåâûõ ôóíöèé f . Ïîëó÷åííûå ðåçóëüòàòû îáîáùàþò ðàíåå èç-
âåñòíûå îöåíêè [7] íåñáàëàíñèðîâàííîñòè ëèíåéíûõ àïïðîêñèìàöèé îòîáðàæåíèé
ðàññìàòðèâàåìîãî âèäà è ïîçâîëÿþò îöåíèâàòü çíà÷åíèÿ (1) ïðè äîñòàòî÷íî ñëàáûõ
îãðàíè÷åíèÿõ íà àïïðîêñèìèðóùóþ ôóíêöèþ f èëè îïåðàöèþ *.
Ðåçóëüòàòû ïðèìåíåíèÿ ïîëó÷åííûõ îöåíîê ê èññëåäîâàíèþ ñâîéñòâ ðàóíäîâûõ
ôóíêöèé øèôðîâ ÃÎÑÒ è «Êàëèíà» àâòîðû ïðåäïîëàãàþò èçëîæèòü â îòäåëüíîé
ñòàòüå. Àêòóàëüíîé çàäà÷åé äàëüíåéøèõ èññëåäîâàíèé ÿâëÿåòñÿ îáîáùåíèå ïðåäñòàâ-
ëåííûõ íèæå òåîðåì íà áîëåå øèðîêèé êëàññ êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé, ïî-
ñòðîåííûõ íà îñíîâå ðÿäà óïðàâëÿåìûõ äâóõìåñòíûõ ïîäñòàíîâî÷íûõ îïåðàöèé [13].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÔÎÐÌÓËÈÐÎÂÊÈ ÎÑÍÎÂÍÛÕ ÐÅÇÓËÜÒÀÒÎÂ
Äàëåå èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ: Vm — ìíîæåñòâî áóëåâûõ âåê-
òîðîâ äëèíû m; S
Vm — ñèììåòðè÷åñêàÿ ãðóïïà ïîäñòàíîâîê íà ìíîæåñòâå Vm ;
Fm — êîëüöî ìàòðèö ðàçìåðà m m� íàä ïîëåì F �GF( )2 . Áóäåì îòîæäåñòâëÿòü
ïðîèçâîëüíûé âåêòîð x x x Vm m� �( , , )1 � ñ öåëûì ÷èñëîì x x xm
m� � ��2 21
1
0
�
è îáîçíà÷àòü x y
m
� (èëè x y� , åñëè çíà÷åíèå m îäíîçíà÷íî îïðåäåëåíî êîíòåê-
ñòîì) ñóììó ïî ìîäóëþ 2m äâîè÷íûõ ÷èñåë, ñîîòâåòñòâóþùèõ âåêòîðàì
x y Vm, � . Ñèìâîëîì xy îáîçíà÷èì ñêàëÿðíîå ïðîèçâåäåíèå íàä ïîëåì F âåêòîðîâ
x x xm� ( , , )1 � è y y ym� ( , , )1 � : xy x y x ym m� � �1 1 � . Íàêîíåö, äëÿ ëþáîé
äâîè÷íîé m n� -ìàòðèöû U îáîçíà÷èì S U( ) è C U( ) ïîäïðîñòðàíñòâà âåêòîðíûõ
ïðîñòðàíñòâ Vn è Vm , ïîðîæäåííûå ñîîòâåòñòâåííî ñòðîêàìè è ñòîëáöàìè ìàò-
ðèöû U.
Äëÿ ëþáûõ m�N, ��S
Vm , A Fm� , � �, �Vm è ïðîèçâîëüíîé áèíàðíîé àë-
ãåáðàè÷åñêîé îïåðàöèè * íà ìíîæåñòâå Vm ïîëîæèì
l A xA x k x x km m
x Vm
*
( ) ( , , ) ( ( ( * ) ( * ))� � � � � � ��� � �
�
�
�� �
�
�2 2
�
�
�
�
�
2
k Vm
, (2)
ãäå �( ) ( )u u� �1 , u�{ }0 1, ; â ñëó÷àå, êîãäà * ,� � �{ }, îáîçíà÷èì
�
*
( )
:
( , )
( , , ) ( ( * ) (�
�
� � � � � ��A xA x k xm m
x V
x k a
m
� � �� �
�
�
�2 2 x k
ak Vm
* )) ,
,��
��
�
�
�
�
�
�
�
�
{ }0 1
2
(3)
ãäå äëÿ ëþáûõ m�N, x k Vm, �
�( , )x k
m x k
�
áèò ïåðåíîñà â é ðàçðÿä ñóììû è
â êîëüöå
-
åñëè
åñëè
Z, * ;
, * .
� �
� �
�
�
�
�
�0
(4)
Îòìåòèì, ÷òî ïàðàìåòð (1) ñîâïàäàåò ñ ïàðàìåòðîì (2), åñëè f ÿâëÿåòñÿ áèëè-
íåéíîé ôóíêöèåé: f x y xAy x y( , ) � � �� � , x y Vm, � . Êðîìå òîãî, åñëè * � �, òî
ïàðàìåòðû (2) è (3) ñîâïàäàþò.
Ïðåäïîëîæèì, ÷òî ïîäñòàíîâêà � èìååò âèä
� � � �( ) ( , ) ( ( ), ( ))x x x x x� �2 1 2 2 1 1 , x Vt1 � , x Vm t2 � � , (5)
ãäå �1 �S
Vt , �2 �
�S
Vm t , 1 1� � �t m . Òðåáóåòñÿ ïîëó÷èòü âåðõíèå îöåíêè ïàðà-
ìåòðà (2), çàâèñÿùèå íåïîñðåäñòâåííî îò ïîäñòàíîâîê �1 è �2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 43
÷èñåë
Äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è ïðåäñòàâèì ìàòðèöó A Fm� â áëî÷íîì
âèäå:
A
A U
V A
�
�
�
��
�
�
2
1
, A Ft1 � , A Fm t2 � � ; (6)
àíàëîãè÷íî çàïèøåì âåêòîðû � è �: � � �� ( , )2 1 , � � �� ( , )2 1 , ãäå � �1 1, �Vt ,
� �2 2, � �Vm t .  [7] ïîêàçàíî, ÷òî â ÷àñòíîì ñëó÷àå ïðè A � 0 âûïîëíÿåòñÿ íåðà-
âåíñòâî
l l� � ��( ) ( ) ( )
( , , ) ( , , ) ( , , )� � �
� � � � � �0 0 01 2
1 1 2 2� . (7)
Ñëåäóþùàÿ òåîðåìà îáîáùàåò ýòîò ðåçóëüòàò.
Òåîðåìà 1. Äëÿ ëþáûõ âåêòîðîâ � �, �Vm , ïîäñòàíîâêè � âèäà (5), ìàòðèöû A
âèäà (6) è îïåðàöèè * ,� � �{ } ñïðàâåäëèâû íåðàâåíñòâà
l A l A u
u C U
v S V
*
( )
*
( )
( ),
( )
*
( )
( , , ) max ( , ,� �
� � � �� �
�
�
� 1
2 2
2
2 � v), (8)
l A A v
u S U
v C V
*
( )
*
( )
( ),
( )
*
( )
( , , ) max ( ,� �
� � �� �
��
��
� �2
1 1
1 � � �, )�1 u , (9)
ãäå
�
*
( )
( ),
(| ( , , )| | ( , , )|1
2 2 2 22 0 1
1 1
2
2
� ��
�
�
t
k k
b S V
c
u b c u b c
C U
k Vt
( )
)��
�
�
�
�
�
�
�
�
�
2
1
(10)
è äëÿ ëþáûõ a�{ }0 1, , k Vt1 � , b S V2 � ( ) , c C U2 � ( )
u a b c x A x k x x kk
t
x
1 2 2 1 1 1 1 1 1 1 1 1 1 12( , , ) ( ( * ) ( * ))� � �� � � � � �
1 1 2 2�
�
S a b ck ( , , )
, (11)
S a b c x Vk t1 2 2 1( , , ) { :� � �( , )x k a1 1 � , x V b1 2� , U x k c�1 1 1 2( * ) � }; (12)
�
*
( ) ( ) max{| ( , , )|, | ( , , )|2
1 1 1 12 0 1
2 2
1
� � �
�
m t
k k
b C
v b c v b c
( ),
( )
}
V
c S U
k Vm t
1
1
2
�
�
��
�
�
�
�
�
�
�
�
�
(13)
è äëÿ ëþáûõ a�{ }0 1, , k Vm t2 � � , b C V1 � ( ) , c S U1 � ( )
v a b c x A x k ak
m t
x S k
2
2 2
1 1 2 2 2 2 22 1( , , ) ( ( * * ( , ))( )� �� �
� �
� � �
( , , )a b c1 1
�
� �� � � �2 2 2 2 2 2 1x x k a( * * ( , ))) , (14)
� � � � ��S a b c x V V x k a b x U ck m t
2
1 1 2 2 2 2 1 2 11( , , ) : ( * * ( , )) ,{ � � }. (15)
Ïðèâåäåì ðÿä ñëåäñòâèé, âûòåêàþùèõ èç ýòîé òåîðåìû. Ïðåæäå âñåãî,
îòìåòèì, ÷òî â ñëó÷àå, êîãäà * � � è A � 0 , ïàðàìåòð (10) ñîâïàäàåò ñ ïàðàìåòðîì
��
( )
( , , )
�
� �1 0 1 1 , êîòîðûé îïðåäåëÿåòñÿ â ñîîòâåòñòâèè ñ ôîðìóëîé (3).
Ñëåäîâàòåëüíî, â ýòîì ñëó÷àå íåðàâåíñòâî (8) ñâîäèòñÿ ê íåðàâåíñòâó (7), êîòîðîå
ïîëó÷åíî â [7]. Äàëåå, íà îñíîâàíèè (10)–(12) ñïðàâåäëèâî íåðàâåíñòâî �
*
( )1 1� ,
* ,� � �{ }, èç êîòîðîãî ñëåäóåò, ÷òî çíà÷åíèå ïàðàìåòðà (2) íå ïðåâîñõîäèò çíà÷åíèÿ
âòîðîãî ñîìíîæèòåëÿ â ïðàâîé ÷àñòè íåðàâåíñòâà (8). Òàêèì îáðàçîì, ñïðàâåäëèâî
ñëåäóþùåå óòâåðæäåíèå.
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Ñëåäñòâèå 1. Â óñëîâèÿõ òåîðåìû 1 èìååò ìåñòî íåðàâåíñòâî
l A l A u v
u C U
v S V
*
( )
( ),
( )
*
( )
( , , ) max ( , , )� �
� � � �� � �
�
�
2
2 2 2 . (16)
Ðàññìîòðèì íåðàâåíñòâî (9) è îöåíèì ïåðâûé ñîìíîæèòåëü â åãî ïðàâîé ÷àñ-
òè. Ïóñòü * � �; òîãäà íà îñíîâàíèè (4), (14) äëÿ ëþáûõ k Vm t2 � � , b C V1 � ( ) ,
c S U1 � ( ) âûïîëíÿåòñÿ ðàâåíñòâî v b ck2
0 1 1( , , ) = v b ck2
1 1 1( , , ), èç êîòîðîãî ñëåäóåò,
÷òî �
�
�( )2 1. Ïóñòü * � �; òîãäà â ñèëó íåðàâåíñòâà
max | ( , , )| , | ( , , )| | ( , , )|{ }v b c v b c v b ck k k2 2 2
0 1 01 1 1 1 1 1� � | ( , , )|v b ck2
1 1 1
è ôîðìóë (13)–(15) ñïðàâåäëèâà îöåíêà �� �( )2 4. Ïðè ýòîì â ñëó÷àå, êîãäà õîòÿ
áû îäíà èç ìàòðèö, U èëè V, â ôîðìóëå (6) íóëåâàÿ, èìååò ìåñòî áîëåå ñèëüíàÿ
îöåíêà
�� �( )2 1. (17)
Äåéñòâèòåëüíî, åñëè U � 0 , òî íà îñíîâàíèè ôîðìóë (14), (15) äëÿ ëþáûõ
a�{ }0 1, , k Vm t2 � � , b C V1 � ( ) , c S U1 � ( ) ñïðàâåäëèâî ñîîòíîøåíèå
| ( , , ) | | ( , , )|( ) ( )v a b c S a b ck
m t
k
V
2 21 1 1 12� � �� � �2 rank .
Åñëè V � 0 , òî, ñîãëàñíî òåì æå ôîðìóëàì,
| ( , , )| ( )v a b ck
U
2 1 1 � �2 rank , a�{ }0 1, , k Vm t2 � � , b C V1 � ( ) , c S U1 � ( ) .
Îòñþäà íà îñíîâàíèè (10) ñëåäóåò ñïðàâåäëèâîñòü (17).
Ñóììèðóÿ èçëîæåííîå âûøå, ïîëó÷àåì ñëåäóþùèé ðåçóëüòàò.
Ñëåäñòâèå 2. Â óñëîâèÿõ òåîðåìû 1 ñïðàâåäëèâû íåðàâåíñòâà
l A l A v
u S U
v C V
� ��
��
�
� � � �( )
( ),
( )
( )
( , , ) max ( , ,� �
� � � �1
1 1 1 u� ) , (18)
l A A v
u S U
v C V
�
��
��
�� � �( )
( ),
( )
( )
( , , ) max ( , ,� �
� � � �4 1
1 1 1� � �u ) . (19)
Êðîìå òîãî, åñëè â ôîðìóëå (6) U � 0 èëè V � 0, òî
l A A v
u S U
v C V
�
��
��
�� � � �( )
( ),
( )
( )
( , , ) max ( , ,� �
� � � �� 1
1 1 1 u� ). (20)
Îòìåòèì, ÷òî òåîðåìà 1 è ñëåäñòâèÿ èç íåå ñâîäÿò çàäà÷ó íàõîæäåíèÿ âåðõíèõ
îöåíîê ïàðàìåòðà (2) äëÿ ïðîèçâîëüíîé ìàòðèöû A ïîðÿäêà m è âåêòîðîâ � �, �Vm
ê ïîñòðîåíèþ àíàëîãè÷íûõ îöåíîê ïàðàìåòðîâ (2), (3), (10), (13), çàâèñÿùèõ îò ïîä-
ìàòðèö ìàòðèöû A ìåíüøåãî ðàçìåðà è ñîîòâåòñòâóþùèõ «÷àñòåé» âåêòîðîâ � è �.
 ðÿäå ñëó÷àåâ îöåíêè (16), (18)–(20) ìîæíî èñïîëüçîâàòü ìíîãîêðàòíî, ïðèìåíÿÿ èõ
ïîñëåäîâàòåëüíî ê ïîäìàòðèöàì, ðàñïîëîæåííûì íà ãëàâíîé äèàãîíàëè ìàòðèöû A.
Ïóñòü ïîäñòàíîâêà � ïðåäñòàâëÿåò ñîáîé íàáîð s-áëîêîâ:
� � �( ,... , )s sp0 1 , (21)
ãäå s Si
Vt� , i p� �0 1, , pt m� . Çàïèøåì ìàòðèöó A â âèäå A Aij i j p
�
� �
( )
, ,0 1
,
ãäå A Fij t� ; àíàëîãè÷íî ïðåäñòàâèì âåêòîðû � è �: � � �
�
� �( , , )� p 1 ,
� � �� �( , , )0 1� p , ãäå � �j j tV, � , j p� �0 1, . Äëÿ ëþáîãî i p� �0 1, îáîçíà÷èì
C Ai ( ) è S Ai ( ) ïîäïðîñòðàíñòâà âåêòîðíîãî ïðîñòðàíñòâà Vt , ïîðîæäåííûå
ñòîëáöàìè ìàòðèö Aij è ñîîòâåòñòâåííî ñòðîêàìè ìàòðèö A ji ïî âñåì j i� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 45
Ïðåäïîëîæèì âíà÷àëå, ÷òî A ÿâëÿåòñÿ áëî÷íî-äèàãîíàëüíîé ìàòðèöåé:
A A A p p� � �diag( , , )00 1 1� , A Fii t� , i p� �0 1, . (22)
Ïðèìåíÿÿ ïîñëåäîâàòåëüíî íåðàâåíñòâî (16) è p �2 ðàç íåðàâåíñòâî (20) ê ñîîò-
âåòñòâóþùèì ïîäìàòðèöàì ìàòðèöû (22), ïîëó÷àåì ñëåäóþùèé ðåçóëüòàò.
Ñëåäñòâèå 3. Ïðè âûïîëíåíèè ñîîòíîøåíèé (21), (22) ñïðàâåäëèâî íåðàâåíñòâî
l A l A A
s s
ii i i
i
i
� � �
�
�( ) ( ) ( )
( , , ) ( , , ) ( , , )� � � � � � �0
00 0 0
1
�
p�
�
1
,
êîòîðîå îáðàùàåòñÿ â ðàâåíñòâî, åñëè Aii � 0, � �i i� � 0 äëÿ âñåõ i p� �1 1, .
 îáùåì ñëó÷àå ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà, óñòàíàâëèâàþùàÿ âåðõíèå
ãðàíèöû ïàðàìåòðà (2) â òåðìèíàõ ÷èñëîâûõ ïàðàìåòðîâ ïîäñòàíîâîê s sp0 1,... , � .
Òåîðåìà 2. Ïóñòü ïîäñòàíîâêà � èìååò âèä (21). Òîãäà äëÿ ëþáûõ A Fm� ,
� �, �Vm ñïðàâåäëèâû íåðàâåíñòâà
l A l A
i p u C A
v S A
s
i
i
i
i
� � � �
�
�
�( )
, ( ),
( )
( )
( , , ) min max (� � �
0 1
i i iu v, , )� �� � , (23)
l A A
i p u C A
v S A
s
i
i
i
�
� � �
�
��( )
, ( ),
( )
( )
( , , ) min max (� � � 4
0 1
� ii i iu v, , )� �� � . (24)
Êðîìå òîãî, åñëè A — áëî÷íî-òðåóãîëüíàÿ ìàòðèöà (ò.å. Aij � 0 äëÿ ëþáûõ
0 1� � � �i j p èëè A ji � 0 äëÿ ëþáûõ 0 1� � � �i j p ), òî
l A A
i p u C A
v S A
s
i
i
i
i
�
� � �
�
��( )
, ( ),
( )
( )
( , , ) min max (� � �
0 1
� i i iu v, , )� �� � . (25)
Ðàññìîòðèì çàäà÷ó íàõîæäåíèÿ îöåíîê ïàðàìåòðà (2) â íåñêîëüêî áîëåå îá-
ùåé ïîñòàíîâêå. Ïðåäïîëîæèì, ÷òî îïåðàöèÿ * íà ìíîæåñòâå Vm îïðåäåëÿåòñÿ ïî
ôîðìóëå
( , )* ( , ) ( * , * )
( ) ( )
x x k k x k x k2 1 2 1 2
2
2 1
1
1� , x k Vt1 1, � , x k Vm t2 2, � � , (26)
ãäå *
( )1
è *
( )2
— ïðîèçâîëüíûå áèíàðíûå àëãåáðàè÷åñêèå îïåðàöèè íà ìíîæåñòâàõ
Vt è Vm t� ñîîòâåòñòâåííî, 1 1� � �t m . Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Ïðè âûïîëíåíèè ðàâåíñòâ (5), (6), (26) ïàðàìåòð (2) óäîâëåòâîðÿåò
ñîîòíîøåíèÿì
l A l A u
u C U
v S V
*
( )
( ),
( )
( )
( )
( , , ) max ( , ,
*
� �
� � � �� � �
�
�
2 2 2 2
2 v) ,
l A l A v
u S U
v Ñ V
*
( )
( ),
( )
( )
( )
( , , ) max ( , ,
*
� �
� � �� � �
��
��
1 1 1
1 �1 � �u ) .
Îòìåòèì, ÷òî ïîñëåäíèå äâå òåîðåìû ïîçâîëÿþò îöåíèâàòü ñâåðõó çíà÷åíèÿ (2)
äëÿ ëþáîé ïîäñòàíîâêè � âèäà (21), ïðîèçâîëüíîé ìàòðèöû A Fm� è îïåðàöèè * âèäà
( ,... , )* ( ,... , ) ( , , )x x k k x k x kn n
m
n
m
n
n
1 1 1 1
1
� � �� , x k Vi i mi
, � , i n�1, ,
ãäå ÷èñëà m mn1 , ,� äåëÿòñÿ íà t, m m mn1 � � �� .
ÄÎÊÀÇÀÒÅËÜÑÒÂÀ ÒÅÎÐÅÌ
Äîêàçàòåëüñòâî òåîðåìû 1. Ïîëó÷èì âñïîìîãàòåëüíîå ñîîòíîøåíèå äëÿ âíóò-
ðåííåé ñóììû â ïðàâîé ÷àñòè ðàâåíñòâà (2), èñïîëüçóÿ êîòîðîå äîêàæåì íåðà-
âåíñòâà (8), (9).
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Ïóñòü x x xt� �1 22 è k k kt� �1 22 — öåëûå ÷èñëà, ñîîòâåòñòâóþùèå áóëåâûì
âåêòîðàì ( , )x x2 1 è ( , )k k2 1 ñîîòâåòñòâåííî, x k Vt1 1, � , x k Vm t2 2, � � . Ñïðàâåäëèâû
ðàâåíñòâà
x k x k x k x k
m t
t
m t m t
� � � � � �
� �
1 1 2 2 1 12 ( ( , ))� , x k x k x k� � � �( , )2 2 1 1 ,
êîòîðûå ñ ó÷åòîì ôîðìóëû (4) ìîæíî çàïèñàòü â âèäå
x k x k x k x k* ( * * ( , ), * )� 2 2 1 1 1 1� , * ,� � �{ }.
Îòñþäà íà îñíîâàíèè ôîðìóëû (5) âûòåêàåò ðàâåíñòâî
� � � �( * ) ( ( * * ( , )), ( * ))x k x k x k x k� 2 2 2 1 1 1 1 1 , x k Vm, � . (27)
Äëÿ ëþáûõ A Fm� , � �, �Vm , k k k� ( , )2 1 , ãäå k Vt1 � , k Vm t2 � � , îáîçíà÷èì
l A xA x k x x k
k k
m
x Vm
1 2
2
,
( ) ( , , ) ( ( * ) ( * ))� � � � � � ��� � ��
�
� (28)
âíóòðåííþþ ñóììó â ïðàâîé ÷àñòè ðàâåíñòâà (2). Èñïîëüçóÿ ôîðìóëû (6), (27),
ïîëó÷àåì ñëåäóþùåå âûðàæåíèå ïàðàìåòðà (28):
l A x A x k v x k
k k
m
x Vt
1 2
1
2 2 2 2 2 2 1 1,
( ) ( , , ) ( ( * * ( , )))� � � � �� �
� ,
( ( * ))
x Vm t
x A x k
2
1 1 1 1 1
� �
� �� �
� � � �� � � � � � � �( ( * * ( , )) ) ( ( * ) )2 2 2 2 1 1 2 2 1 1 1 1 1 1x k v x k x x k x
� �� � �( ( * * ( , )) ( * ))x V x k v x k x U x k1 2 2 2 1 1 2 1 1 1 . (29)
Äîêàæåì íåðàâåíñòâî (8). Îáîçíà÷èì â ôîðìóëå (29) a x k� �( , )1 1 , b x V2 1� ,
c U x k2 1 1 1� � ( * ) è çàïèøåì åå òàêèì îáðàçîì:
l A x A
k k
t
a
b S V
c C U
1 2
2
2
2
0 1
1 1,
( )
, ,
( ),
( )
( , , ) (� � � �� �
�
�
�
�
{ }
� � � �1 1 1 1 1 1 1 1 1
1 1 2 2
( * ) ( * ))
( , , )
x k x x k
x S a b ck
� � �
�
�
� � � � �� �2 2 2 2 2 2 2 2 2 2 2 2 2
( ) ( ( * * ) ( ) ( ) ( *
m t x A x k a c x b x k� � � � � 2
2
* ))a
x Vm t
�
� �
�
� �
�
�
�
� u a b c u a b ck k
a
b S V
c C U
1 2
2
2
2 2 2 2
0 1
( , , ) ( , , )
, ,
( ),
( )
{ }
. (30)
Çäåñü äëÿ ëþáûõ a�{ }0 1, , k Vm t2 � � , b S V2 � ( ) , c C U2 � ( ) èìååì
� � �� �
� �
�u a b c x A x k ak
m t
x Vm t
2
2
2 2 2 2 2 2 22( , , ) ( ( * * )( ) � �
� � � �( ) ( ) ( * * ))� � �2 2 2 2 2 2 2 2c x b x k a , (31)
à çíà÷åíèÿ u a b ck1 2 2( , , ) è S a b ck1 2 2( , , ) îïðåäåëÿþòñÿ ïî ôîðìóëàì (11) è (12)
ñîîòâåòñòâåííî.
Ïîëîæèì u u b c u b c
k k
b S V
c C U
k
1 1
2
2
1
0 12 2 2 2� �
�
�
� (| ( , , )| | ( , , )|
( ),
( )
) , k Vt1 � . Íà îñíîâàíèè
ðàâåíñòâà (30) è âûïóêëîñòè âíèç ôóíêöèè x x�
2 , x�R, ñïðàâåäëèâû ñëåäóþùèå
íåðàâåíñòâà:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 47
( ( , , )) | ( , , )| | ( , , )|
,
( )l A u a b c u a b c
k k k k
a
1 2 1 1
2
2 2 2 2
� � � � �
�
�
�
�
�
�
�
�
�
�
��
�
�
�
{ }0 1
2
2
2
, ,
( ),
( )
b S V
c C U
� �
�
�
u u a b c u a b ck k k
a
b S V
1 1 2
2
2 2 2 2
2
0 1
| ( , , )| ( ( , , ))
, ,
( ),
{ }
c C U2�
�
( )
, k Vt1 � , k Vm t2 � � .
Îòñþäà íà îñíîâàíèè (2) è (28) âûòåêàåò
l A
*
( ) ( , , )� � � �
� �� � �
� �
2 2
1 1 2
2
2 2 2 2
2t
k k
m t
k
k V
u u a b c u a b c
m
| ( , , )| ( ( , , ))( )
tt a
b S V
c C U
k V
���
�
�
�
�
�
�
�
�
�
�
��
�
�
{ }0 1
2
2
1 , ,
( ),
( )
. (32)
Äàëåå, ñîãëàñíî (31) äëÿ ëþáûõ a�{ }0 1, , b S V2 � ( ) , c C U2 � ( ) âûïîëíÿþòñÿ
ñîîòíîøåíèÿ
2 2 2
2
2
2 2
2� �
�
� � � �� �
�
�( ) ( ) ( )( ( , , )) ( (m t
k
k V
m t m tu a b c x
m t
� 2 2 2 2 2
22
A x k
x Vk V m tm t
� ( * )�
�� ��
��
� � � � �
�
�
( ) ( ) ( * ))) max
( ),
( )
*
(
� � �2 2 2 2 2 2 2 2
2c x b x k l
u C U
v S V
�
� �2
2 2 2
)
( , , )A u v� � .
Ñëåäîâàòåëüíî, íà îñíîâàíèè (32) ïîëó÷àåì
l A u a b ct
k
a
b S V
c C U
*
( )
, ,
( ),
(
( , , ) | ( , , )|� � � � �
�
�
�
2
1
2
2
0 1{ }
)
( ),
( )
*
( )
max (��
�
�
�
�
�
�
��
�
�
� �
�
2
2
1
2
k V
u C U
v S Vt
l A
�
, , )� �2 2� �u v .
Èç ïîñëåäíåãî íåðàâåíñòâà è ôîðìóëû (10) ñëåäóåò íåðàâåíñòâî (8), ÷òî è òðå-
áîâàëîñü äîêàçàòü.
Óáåäèìñÿ â ñïðàâåäëèâîñòè íåðàâåíñòâà (9). Îáîçíà÷èì â ôîðìóëå (29)
a x k� �( , )1 1 , b V x k x k1 2 2 2 1 1� � �( * * ( , )) , c x U1 2� è çàïèøåì åå ñëåäóþùèì
îáðàçîì:
l A x A
k k
t
a
b Ñ V
c S U
1 2
1
1
2
0 1
1 1,
( )
, ,
( ),
( )
( , , ) (� � � �� �
�
�
�
�
{ }
�1 1 1
1
1 1
( * )
:
( , )
x k
x V
v x k a
t
�
�
�
�
� � � � �( ) ( ) ( * ))� � �
1 1 1 1 1 1 1 1b x c x k
� � �� �
�
2 2 2 2 2 2 2 2 2 2 2 2
2
( )
~
( ( * * ) ( * * )m t
x S
x A x k a x x k a
k
� � � � �
2 1 1( , , )
).
a b c
� (33)
Çäåñü äëÿ ëþáûõ a�{ }0 1, , k Vm t2 � � , b C V1 � ( ) , c S U1 � ( ) ìíîæåñòâî
~
( , , )S a b ck2 1 1
ñîñòîèò èç âñåõ âåêòîðîâ x Vm t2 � � , êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì
V x k a b�2 2 2 1( * * ) � , x U c2 1� .
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Çàìåòèì, ÷òî íà îñíîâàíèè (4), (33) âûïîëíÿåòñÿ ðàâåíñòâî
l A v b c v b c
k k k k
b C V
1 2 1 2
1
0 01 1 1 1,
( )
(
( , , ) ( ( , , ) ( , , )� � � � � �
� ),
( )
( , , ) ( , , )),
c S U
k kv b c v b c
1
1 2
1 11 1 1 1
�
� � ,(34)
ãäå äëÿ ëþáûõ a�{ }0 1, , k Vt1 � , b C V1 � ( ) , c S U1 � ( )
v a b c x A x kk
t
x V
v x k a
t
� � ��
�
�
�1
1
1 1
1 1 1 1 1 1 12( , , ) ( ( * )
:
( , )
� �
� � � �( ) ( ) ( * ))� � �1 1 1 1 1 1 1 1b x c x k , (35)
à v a b ck2 1 1( , , ) îïðåäåëÿåòñÿ ïî ôîðìóëå (14). Äåéñòâèòåëüíî, åñëè * � �, òî
�( , )a a1 � äëÿ ëþáîãî a�{ }0 1, , ìíîæåñòâî
~
( , , )S a b ck2 1 1 ñîâïàäàåò ñ ìíîæåñòâîì
(15) è ôîðìóëà (34) âûòåêàåò èç ðàâåíñòâà (33). Åñëè * � �, òî �( , )a 1 �
� ��( , )x k1 1 0 äëÿ ëþáûõ a�{ , }0 1, x k Vt1 1, � . Ñëåäîâàòåëüíî, â ýòîì ñëó÷àå
l A
k k1 2,
( ) ( , , )� � � �
� � � � ��
�
�
� 2
1
1
1 1 1 1 1 1 1 1 1
t
b C V
ñ S U
x A x k b x
( ),
( )
( ( * ) ( ) (� � � � c x k
x Vt
1 1 1 1
1
) ( * ))�
�
� �
� � �� �
�
2 2 2 2 2 2 2 2 2 2 2 2
02 2
( )
~
( ,
( ( * ) ( * )m t
x S
x A x k x x k
k
� � � � �
b c1 1, )
)� ,
÷òî âñëåäñòâèe (14), (15) è (35) ñîâïàäàåò ñ âûðàæåíèåì â ïðàâîé ÷àñòè ðàâåí-
ñòâà (34).
Äëÿ ëþáûõ k Vt1 � , k Vm t2 � � , b C V1 � ( ) , c S U1 � ( ) ïîëîæèì
� � � � �v b c v b c v b ck k k1 1 1
1 1 1 1 1 10 1( , ) ( , , ) ( , , ) , (36)
v b c v b c v b ck k k2 2 21 1 1 1 1 10 1( , ) max ( , , ) , ( , , )� �
�
�
�
�
�
.
(37)
Íà îñíîâàíèè (34) è âûïóêëîñòè âíèç êâàäðàòè÷íîé ôóíêöèè ñïðàâåäëèâû íåðàâåíñòâà
( ( , , )) ( , ) ( , )
,
( )
( ),
l A v b c v b c
k k k k
b C V
ñ
1 2 1 2
1
2
1 1 1 1
� � � � �
�
1
2
�
�
�
�
�
�
�
�
�
�
�
S U( )
� �
�
�
�
�
�
�
�
�
�
�
� ( ( , )) ( , )
( ),
( )
v b c v b ck k
b C V
ñ S U
1 2
1
1
1 1
2
1 1
�
�
�
�
�
�
�
�
�
�
� v b ck
b C V
c S U
2
1
1
1 1(
~
, ~ )
~
( ),
~ ( )
.
Îòñþäà ñîãëàñíî ôîðìóëàì (2), (13), (28) è (35)–(37) èìååì ñëåäóþùèå ñîîòíîøåíèÿ:
l A l Am
k V
k k
t
k Vm t
*
( )
,
,
( )( , , ) ( ( , , ))� �� � � �� ��
�
� �
�2
1
2
1 2
2
� �
�
�
�
�
�
�
�
�
�
�
�� �
b C V
c S U
t
k
k V
v b c
t1
1
1
1
2 21 1
2
( ),
( )
( ( , )) ( )
~
( ),
~ ( )
(
~
, ~ ) ( ,m t
b C V
c S U
k V
k k
m t
v b c v b�
�
�
�
��
� 1
1
2
2 21 1 1 c1 )
�
�
�
�
�
�
�
�
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 49
� � �
�
�
�2
2
1
1
2
1
1 1 1 1
( )
~
( ),
~ ( )
(
~
, ~ ) ( , )m t
k
b C V
c S U
k
b
v b c v b c
�
�
� ��
��
��
�
�
�
�
�
�
�
�
� C V
c S U
k V
u S U
v Cm t ( ),
( )
( ),
(
max
1
2 V
t
k
k V
v v u
t)
( ( , ))2
1
1
2�
�
� � �
�
�
�
��
�
�
�
��
��
�
�
�
�
�
�
�
�
�
� �
�
�
�
�2
2
1
1
2
1 1
2
( )
( ),
( )
( , )m t
k
b C V
c S U
k
v b c
V
u S U
v C Vm t
A v u
�
�
��
��
� � � � �max ( , , )
( ),
( )
*
( )� �
� �1
1 1 1
� � � � �
��
��
� �
*
( )
( ),
( )
*
( )
max ( , , )2
1 1 1
1
u S U
v C V
A v u
�
� � .
Èòàê, ñïðàâåäëèâî íåðàâåíñòâî (9), ÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà äîêàçàíà.
Äîêàçàòåëüñòâî òåîðåìû 2. Îáîçíà÷èì Tm ìíîæåñòâî áëî÷íî-òðåóãîëüíûõ
ìàòðèö ïîðÿäêà m íàä ïîëåì F; äëÿ ëþáûõ A Fm� , * ,� � �{ } ïîëîæèì
� A
mA T
,*
, * ,
�
� � �
�
�
4
1
åñëè è
â ïðîòèâíîì
Çàôèêñèðóåì ÷èñëî i p� �{ }0 1 1, , ,� è ïîêàæåì, ÷òî â óñëîâèÿõ òåîðåìû äëÿ
ëþáûõ A Fm� , � �, �Vm ñïðàâåäëèâî íåðàâåíñòâî
l A A uA
u C A
v S A
s
ii i
i
i
i
*
( )
,*
( ),
( )
*
( , , ) max ( , ,� � � � � �� �
�
�
� i v� ). (38)
Ïóñòü i � 0 ; òîãäà, ïîëàãàÿ â ôîðìóëå (6) A A2 00� , íà îñíîâàíèè ñëåäñòâèÿ 1 è
ðàâåíñòâ (2), (3) ïîëó÷àåì íåðàâåíñòâà
l A l A u
u C A
v S A
s
*
( )
( ),
( )
*
( )
( , , ) max ( , ,� � � � �� � �
�
�
0
0
0
00 0 0 v) �
� � �
�
�
max ( , , )
( ),
( )
*
( )
u C A
v S A
s
A u v
0
0
0
00 0 0� � � ,
èç êîòîðûõ ñëåäóåò îöåíêà (38). Åñëè i p� �1, òî ôîðìóëà (38) âûòåêàåò íåïî-
ñðåäñòâåííî èç íåðàâåíñòâ (18)–(20) è ôîðìóëû (6), â êîòîðîé íóæíî ïîëîæèòü
A A p p1 1 1� � � .
Ðàññìîòðèì òåïåðü ñëó÷àé, êîãäà 1 2� � �i p . Ïîëàãàÿ â ôîðìóëå (6)
A Akl k l i2 0
�
�
( )
, ,
è ïðèìåíÿÿ ê ìàòðèöå A ñëåäñòâèå 1, ïîëó÷àåì íåðàâåíñòâî
l A l A
C U
S V
*
( )
~ ( ),
~
( )
*
( )
( , , ) max ( , ~,�
�
�
�
� � � � �� � �
�
�
2
2 2 2
~
)� , (39)
ãäå �2 0� ( ,... , )s si , � � �2 0� ( ,... , )i , � � �2 0� ( ,... , )i , à áëî÷íûå ìàòðèöû U è
V èìåþò ñëåäóþùèé âèä:
U Akl k i l i p
�
� � � �
( )
, , ,0 1 1
, V Akl k i p l i
�
� � � �
( )
, , ,1 1 0
. (40)
Äëÿ îöåíêè âûðàæåíèÿ â ïðàâîé ÷àñòè íåðàâåíñòâà (39) âîñïîëüçóåìñÿ ñëåä-
ñòâèåì 2, ïîëàãàÿ â ôîðìóëå (6) A A�
2
, A Aii1 � . Â ðåçóëüòàòå äëÿ ëþáûõ âåêòîðîâ
~ (~ ,... , ~ ) ( )� � �� �0 i C U ,
~
(
~
,... ,
~
) ( )� � �� �0 i S V , ãäå ~ ,
~
� �j j tV� , j i� 0, , ïîëó÷èì íå-
ðàâåíñòâî
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
ñëó÷àå.
l A AA
u v
s
ii i
i i
i
*
( )
,*
( , ) *
( )
( , ~,
~
) max ( ,
�
� � � � � �2
2 2 2� � � � � � � �~ ,
~
),� � �i i i i iv u (41)
ãäå ìàêñèìóì áåðåòñÿ ïî âñåì óïîðÿäî÷åííûì ïàðàì ( , )u v V Vi i t t� � òàêèì, ÷òî
âåêòîð ui ÿâëÿåòñÿ ëèíåéíîé êîìáèíàöèåé ñòðîê ìàòðèö A ji , j i� �0 1, , à âåêòîð
vi — ëèíåéíîé êîìáèíàöèåé ñòîëáöîâ ìàòðèö Aij , j i� �0 1, . Çàìåòèì òåïåðü,
÷òî ñîãëàñíî ðàâåíñòâàì (40) äëÿ ëþáûõ óêàçàííûõ âûøå âåêòîðîâ u vi i, , ~,
~
� �
ñïðàâåäëèâû ñîîòíîøåíèÿ ~ ( )� i i iv C A� � ,
~
( )� i i iu S A� � , èç êîòîðûõ íà
îñíîâàíèè ôîðìóë (39), (41) âûòåêàåò íåðàâåíñòâî (38).
Òàêèì îáðàçîì, ôîðìóëà (38) è òåîðåìà äîêàçàíû.
Äîêàçàòåëüñòâî òåîðåìû 3 ïî÷òè äîñëîâíî ïîâòîðÿåò äîêàçàòåëüñòâî òåîðå-
ìû 1 äëÿ ñëó÷àÿ * � � è ïîýòîìó íå ïðèâîäèòñÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. M a t s u i M . Linear cryptanalysis methods for DES cipher // Advances in Cryptology –
EUROCRYPT’93: Proc. — Berlin; Heidelberg: Springer-Verlag, 1994. — P. 386–397.
2. H a r p e s C . , K r a m e r G . G . , M a s s e y J . L . A generalization of linear cryptanalysis and the appli-
cability of Matsui’s piling-up lemma // Advances in Cryptology – EUROCRYPT’95: Proc. — Berlin; Hei-
delberg: Springer-Verlag, 1995. — P. 24–38.
3. C o u r t o i s N . T . Feistel schemes and bi-linear cryptanalysis // Advances in Cryptology – CRYPTO’04:
Proc. — Berlin; Heidelberg: Springer-Verlag, 2004. — P. 23–40.
4. Va u d e n a y S . Decorrelation: a theory for block cipher security // J. Cryptology. — 2003. — 16, N 4.
— P. 249–286.
5. W a g n e r D . Towards a unifying view of block cipher cryptanalysis // Fast Software Encryption. –
FSE’04: Proc. — Berlin; Heidelberg: Springer-Verlag, 2004. — P. 116–135.
6. À ë å ê ñ å é ÷ ó ê À . Í . , Ø å â ö î â À . Ñ . Ïîêàçàòåëè è îöåíêè ñòîéêîñòè áëî÷íûõ øèôðîâ îòíî-
ñèòåëüíî ñòàòèñòè÷åñêèõ àòàê ïåðâîãî ïîðÿäêà // Ðåºñòðàö³ÿ, çáåð³ãàííÿ ³ îáðîáêà äàíèõ. — 2006. —
8, âèï. 4. — Ñ. 53–63.
7. A l e k s e y c h u k À . N . , K o v a l c h u k L . V . Upper bounds of maximum values of average differen-
tial and linear characteristic probabilities of Feistel cipher with adder modulo 2m // Theory Stoh. Processes.
— 2006. — 12(28), N 1, 2. — P. 20–32.
8. Î ë å ê ñ ³ é ÷ ó ê À . Ì . , Ê î â à ë ü ÷ ó ê Ë .  . , Ï à ë ü ÷ å í ê î Ñ .  . Êðèïòîãðàô³÷í³ ïàðàìåòðè
âóçë³â çàì³íè, ùî õàðàêòåðèçóþòü ñò³éê³ñòü ÃÎÑÒ-ïîä³áíèõ áëîêîâèõ øèôð³â â³äíîñíî ìåòîä³â
ë³í³éíîãî òà ð³çíèöåâîãî êðèïòîàíàë³çó // Çàõèñò ³íôîðìàö³¿. — 2007. — ¹ 2. — Ñ. 12–23.
9. À ë å ê ñ å é ÷ ó ê À . Í . , Ê î â à ë ü ÷ ó ê Ë . Â . , Ñ ê ð û í í è ê Å . Â . , Ø å â ö î â À . Ñ . Îöåíêè
ïðàêòè÷åñêîé ñòîéêîñòè áëî÷íîãî øèôðà «Êàëèíà» îòíîñèòåëüíî ìåòîäîâ ðàçíîñòíîãî, ëèíåéíîãî
êðèïòîàíàëèçà è àëãåáðàè÷åñêèõ àòàê, îñíîâàííûõ íà ãîìîìîðôèçìàõ // Ïðèêë. ðàäèîýëåêòðîíèêà. —
2008. — 7, ¹ 3. — Ñ. 203–209.
10. Ã Î Ñ Ò 28147-89. Ñèñòåìû îáðàáîòêè èíôîðìàöèè. Çàùèòà êðèïòîãðàôè÷åñêàÿ. Àëãîðèòì êðèï-
òîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ. — Ì.: Ãîññòàíäàðò ÑÑÑÐ, 1989.
11. Ï å ð ñ ï å ê ò è â í è é áëîêîâèé ñèìåòðè÷íèé øèôð «Êàëèíà» — îñíîâí³ ïîëîæåííÿ òà ñïåöèô³êàö³¿
/ ².Ä. Ãîðáåíêî, Â.². Äîëãîâ, Ð.Â. Îë³éíèêîâ òà ³í. // Ïðèêë. ðàäèîýëåêòðîíèêà. — 2007. — 6,
¹ 2. — Ñ. 195–208.
12. Ø å â ö î â À . Ñ . Îö³íêè éìîâ³ðíîñòåé óçàãàëüíåíèõ ë³í³éíèõ àïðîêñèìàö³é ðàóíäîâî¿ ôóíêö³¿
ÃÎÑÒ-ïîä³áíîãî áëîêîâîãî øèôðó // Ïðàâîâå, íîðìàòèâíå òà ìåòðîëîã³÷íå çàáåçïå÷åííÿ ñèñòåìè
çàõèñòó ³íôîðìàö³¿ â Óêðà¿í³. — Êè¿â, 2007. — Âèï. 2(15). — Ñ. 76–81.
13. È ç î ò î â Â . Â . , Ì î ë ä î â ÿ í À . À . , Ì î ë ä î â ÿ í Í . À . Àëãîðèòìû ïðåîáðàçîâàíèÿ èíôîð-
ìàöèè íà áàçå óïðàâëÿåìûõ äâóõìåñòíûõ îïåðàöèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2003. —
¹ 2. — Ñ. 164–177.
Ïîñòóïèëà 23.10.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 51
|