Построение верхних оценок средних вероятностей целочисленных дифференциалов раундовых функций блочных шифров определенной структуры
Отримано верхні оцінки середніх ймовірностей цілочисельних диференціалів раундових функцій блочних шифрів у випадку нетривіального блоку підстановки та оператора зсуву певної структури. Визначено параметри, від яких залежать дані оцінки, та умови, що забезпечують якнайменше значення оцінок. Отримано...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84144 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Построение верхних оценок средних вероятностей целочисленных дифференциалов раундовых функций блочных шифров определенной структуры / Л.В. Ковальчук, Н.В. Кучинская // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 71-81. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84144 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841442015-07-04T03:01:41Z Построение верхних оценок средних вероятностей целочисленных дифференциалов раундовых функций блочных шифров определенной структуры Ковальчук, Л.В. Кучинская, Н.В. Системный анализ Отримано верхні оцінки середніх ймовірностей цілочисельних диференціалів раундових функцій блочних шифрів у випадку нетривіального блоку підстановки та оператора зсуву певної структури. Визначено параметри, від яких залежать дані оцінки, та умови, що забезпечують якнайменше значення оцінок. Отримано статистичний розподіл вказаних параметрів. The upper bounds for the average probabilities of integer round differentials are obtained for the composition of key adder, substitution block, and shift operator of special structure. The parameters on which these estimates depend and the conditions that minimize these estimates are determined. The statistical distribution of these parameters is obtained. 2012 Article Построение верхних оценок средних вероятностей целочисленных дифференциалов раундовых функций блочных шифров определенной структуры / Л.В. Ковальчук, Н.В. Кучинская // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 71-81. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84144 621.391:519.2 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 |
2012 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84144 |
| citation_txt |
Построение верхних оценок средних вероятностей целочисленных дифференциалов раундовых функций блочных шифров определенной структуры / Л.В. Ковальчук, Н.В. Кучинская // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 71-81. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kovalʹčuklv postroenieverhnihocenoksrednihveroâtnostejceločislennyhdifferencialovraundovyhfunkcijbločnyhšifrovopredelennojstruktury AT kučinskaânv postroenieverhnihocenoksrednihveroâtnostejceločislennyhdifferencialovraundovyhfunkcijbločnyhšifrovopredelennojstruktury |
| first_indexed |
2025-07-06T11:05:53Z |
| last_indexed |
2025-07-06T11:05:53Z |
| _version_ |
1836895389204086784 |
| fulltext |
ÓÄÊ 621.391:519.2
Ë.Â. ÊÎÂÀËÜ×ÓÊ, Í.Â. ÊÓ×ÈÍÑÊÀß
ÏÎÑÒÐÎÅÍÈÅ ÂÅÐÕÍÈÕ ÎÖÅÍÎÊ ÑÐÅÄÍÈÕ ÂÅÐÎßÒÍÎÑÒÅÉ
ÖÅËÎ×ÈÑËÅÍÍÛÕ ÄÈÔÔÅÐÅÍÖÈÀËΠÐÀÓÍÄÎÂÛÕ ÔÓÍÊÖÈÉ
ÁËÎ×ÍÛÕ ØÈÔÐΠÎÏÐÅÄÅËÅÍÍÎÉ ÑÒÐÓÊÒÓÐÛ
Êëþ÷åâûå ñëîâà: áëî÷íûé øèôð, ðàçíîñòíûé êðèïòîàíàëèç, öåëî÷èñëåííûå
äèôôåðåíöèàëû.
ÂÂÅÄÅÍÈÅ
Äëÿ ïîñòðîåíèÿ îöåíîê ñòîéêîñòè áëî÷íîãî àëãîðèòìà øèôðîâàíèÿ ê ðàçíîñò-
íîìó êðèïòîàíàëèçó è ðàçëè÷íûì åãî ìîäèôèêàöèÿì [1–6], êàê ïðàâèëî, íåîá-
õîäèìî îöåíèòü ñâåðõó ñðåäíþþ âåðîÿòíîñòü ðàóíäîâîãî äèôôåðåíöèàëà. Ðà-
óíäîâûå ôóíêöèè áîëüøèíñòâà èç ñîâðåìåííûõ áëî÷íûõ àëãîðèòìîâ øèôðî-
âàíèÿ (AES [7], ÃÎÑÒ 28147 [8], «Êàëèíà» [9], «Ìóõîìîð» [10]) ñîäåðæàò
êîìïîçèöèþ êëþ÷åâîãî ñóììàòîðà, áëîêà ïîäñòàíîâêè è îïåðàòîðà ïåðåñòà-
íîâêè, ëèíåéíîãî íàä ïîëåì F2 èëè åãî íåêîòîðûì ðàñøèðåíèÿì. Ïîýòîìó çà-
äà÷à îöåíèâàíèÿ ñòîéêîñòè áëî÷íûõ øèôðîâ èëè ñâîäèòñÿ ê çàäà÷å ïîñòðîå-
íèÿ âåðõíèõ îöåíîê ñðåäíèõ âåðîÿòíîñòåé òàêèõ êîìïîçèöèé, èëè ñîäåðæèò åå
êàê ïîäçàäà÷ó. Ïîñëåäíÿÿ ïîëíîñòüþ ðåøåíà â ñëåäóþùèõ ñëó÷àÿõ:
1) åñëè â êëþ÷åâîì ñóììàòîðå ðåàëèçîâàíà îïåðàöèÿ ïîáèòîâîãî ñëîæåíèÿ
è ïðè ýòîì âõîäíûå è âûõîäíûå ðàçíîñòè â ðàóíäîâîì äèôôåðåíöèàëå ðàññìàòðè-
âàþòñÿ îòíîñèòåëüíî ýòîé æå îïåðàöèè (ñì. áèáëèîãðàôèþ â [1, 3]);
2) åñëè â êëþ÷åâîì ñóììàòîðå ðåàëèçîâàíà îïåðàöèÿ ñëîæåíèÿ ïî ìîäóëþ 2ï ,
à âõîäíûå è âûõîäíûå ðàçíîñòè â ðàóíäîâîì äèôôåðåíöèàëå ðàññìàòðèâàþòñÿ
îòíîñèòåëüíî îïåðàöèè ïîáèòîâîãî ñëîæåíèÿ [1–6];
3) åñëè â êëþ÷åâîì ñóììàòîðå ðåàëèçîâàíà îïåðàöèÿ ñëîæåíèÿ ïî ìîäóëþ 2ï ,
âõîäíûå è âûõîäíûå ðàçíîñòè ðàññìàòðèâàþòñÿ îòíîñèòåëüíî ýòîé æå îïåðàöèè
(òàêîé äèôôåðåíöèàë íàçûâàþò öåëî÷èñëåííûì [11, 12]) è ïðè ýòîì ëèáî îòñóò-
ñòâóåò îïåðàòîð ïåðåñòàíîâêè [2], ëèáî îòñóòñòâóåò áëîê ïîäñòàíîâêè è îïåðàòîð
ïåðåñòàíîâêè ÿâëÿåòñÿ îïåðàòîðîì öèêëè÷åñêîãî ñäâèãà [13];
4) åñëè â êëþ÷åâîì ñóììàòîðå ðåàëèçîâàíà ëèáî îïåðàöèÿ ïîáèòîâîãî ñëî-
æåíèÿ, ëèáî îïåðàöèÿ ñëîæåíèÿ ïî ìîäóëþ 2ï , áëîê ïîäñòàíîâêè ïðîèçâîëüíûé,
à îïåðàòîð ïåðåñòàíîâêè ÿâëÿåòñÿ îïåðàòîðîì öèêëè÷åñêîãî ñäâèãà (âåëè÷èíà
ñäâèãà âçàèìíî ïðîñòà ñ äëèíîé âõîäà s-áëîêà [14].
 ñâÿçè ñ âîçðàñòàþùèìè òðåáîâàíèÿìè ê áûñòðîäåéñòâèþ áëî÷íûõ àëãî-
ðèòìîâ ìíîãèå ñîâðåìåííûå àëãîðèòìû ñòðîÿòñÿ áàéò-îðèåíòèðîâàííûìè (íà-
ïðèìåð, AES). Ïîýòîìó àêòóàëüíîé ÿâëÿåòñÿ çàäà÷à îöåíèâàíèÿ âåðîÿòíîñòè öå-
ëî÷èñëåííîãî äèôôåðåíöèàëà äëÿ êîìïîçèöèè êëþ÷åâîãî ñóììàòîðà, áëîêà ïîä-
ñòàíîâîê è îïåðàòîðà áàéòîâîé ïåðåñòàíîâêè, â òîì ÷èñëå áàéòîâîãî ñäâèãà.
 ÷àñòíîñòè, ðàóíäîâàÿ ôóíêöèÿ òàêîãî âèäà âîçìîæíà ïðè ìîäèôèêàöèè àëãî-
ðèòìà ÃÎÑÒ 28147, çàêëþ÷àþùåéñÿ â óäëèíåíèè áëîêà (äî 128, 256 èëè 512 áèò)
è ïåðåâîäà åãî íà áàéòîâóþ îñíîâó.  äàííîé ðàáîòå ðåøàåòñÿ çàäà÷à ïîñòðîåíèÿ
âåðõíèõ îöåíîê ñðåäíèõ âåðîÿòíîñòåé öåëî÷èñëåííûõ äèôôåðåíöèàëîâ îòîáðà-
æåíèé, êîòîðûå ÿâëÿþòñÿ êîìïîçèöèÿìè ñóììàòîðà, áëîêà ïîäñòàíîâêè è îïåðà-
òîðà öèêëè÷åñêîãî ñäâèãà â ñëó÷àå, êîãäà âåëè÷èíà ñäâèãà ïðîïîðöèîíàëüíà äëè-
íå âõîäà s-áëîêà. Â õîäå åå ðåøåíèÿ òàêæå ïîêàçûâàåòñÿ, ÷òî âåðõíèå îöåíêè âå-
ðîÿòíîñòè öåëî÷èñëåííîãî äèôôåðåíöèàëà óìåíüøàòñÿ, åñëè âåëè÷èíà
öèêëè÷åñêîãî ñäâèãà ïðîïîðöèîíàëüíà äëèíå âõîäà s-áëîêà, ò.å. îïèñàííàÿ ìîäè-
ôèêàöèÿ ïðèâîäèò íå òîëüêî ê óâåëè÷åíèþ ñêîðîñòè øèôðîâàíèÿ, íî è ê ñòîéêîñ-
òè àëãîðèòìà ê öåëî÷èñëåííîìó ðàçíîñòíîìó êðèïòîàíàëèçó.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 71
© Ë.Â. Êîâàëü÷óê, Í.Â. Êó÷èíñêàÿ, 2012
ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÎÁÎÇÍÀ×ÅÍÈß È ÐÅÇÓËÜÒÀÒÛ
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: � � �n N Vn
n: ,{ }0 1 — ìíîæåñòâî ï-ìåðíûõ
áèòîâûõ âåêòîðîâ. Âåêòîðû èç Vn îäíîçíà÷íî ñîîòâåòñòâóþò öåëûì ÷èñëàì îò
0 äî 2 1n � , n N� .
Ïóñòü n pu p� �, 2 , òîãäà � � � � � � �x V x x x x V i pn
p i
u: ( ), , ,( ) ( ) ( )
�
1 1 .
Îòîáðàæåíèå S V Vn n: � áèåêòèâíîå, � � �x V S x S xn
p p: ( ) ( ( ), ...( ) ( )
..., ( ))( ) ( )S x1 1 , x V i pi
u
( ) , ,� �1 , ãäå S V V i pi
u u
( ) : , ,� �1 , — áèåêòèâíûå îòî-
áðàæåíèÿ. Òàêîå îòîáðàæåíèå ÷àñòî íàçûâàþò áëîêîì ïîäñòàíîâêè, à îòîáðà-
æåíèÿ S i( ) — s-áëîêàìè.
Îáîçíà÷èì L V Vtu n n: � îòîáðàæåíèå ñäâèãà âëåâî íà tu áèò âåêòîðà èç Vn ,
1 1 �t p . Â íàñòîÿùåé ðàáîòå ðàññìàòðèâàþòñÿ òîëüêî òàêèå îïåðàòîðû ñäâè-
ãà Ltu , â êîòîðûõ âåëè÷èíà ñäâèãà êðàòíà äëèíå s-áëîêà.
Íà ìíîæåñòâå Vn îïðåäåëèì ñëåäóþùèå ïîäìíîæåñòâà [14]:
tu n n tu tuV k V L k L k( ) | : ( ) ( )� � � �� � � � � � �{ };
tu n n tu tuV k V L k L k� � � � � � � �1( ) | : ( ) ( )� � � �{ }.
Äëÿ ïðîèçâîëüíîé ôóíêöèè F V V Vn n n:
� îáîçíà÷èì F x F k xk ( ) : ( , )� ,
k x Vn, � .
Ñîãëàñíî îïðåäåëåíèþ (íàïðèìåð, [3]) ñðåäíÿÿ (ïî êëþ÷àì) âåðîÿòíîñòü öå-
ëî÷èñëåííîãî äèôôåðåíöèàëà d F
� ( , )� � , ãäå � �, \�Vn { }0 , äëÿ ïðîèçâîëüíîãî
îòîáðàæåíèÿ F xk ( ) èìååò âèä
d F x F xF n
k k
x k Vn
�
�
�
� � ��( , ) ( ( ) ( ), )
,
� � � � �2 2 . (1)
 äàííîé ðàáîòå ðàññìàòðèâàþòñÿ îòîáðàæåíèÿ, êîòîðûå ÿâëÿþòñÿ êîìïîçè-
öèåé êëþ÷åâîãî ñóììàòîðà, áëîêà ïîäñòàíîâêè è îïåðàòîðà öèêëè÷åñêîãî
ñäâèãà:
F x L S x kk tu( ) ( ( ))� � . (2)
Ñîãëàñíî ëåììå 1 èç [14] è ðåçóëüòàòàì, ïðåäñòàâëåííûì â [13], � �tu N ,
� �� Vn , � � ��q rn tu2 , ãäå 0 ��r n tu2 1, 0 �q tu2 1, âûïîëíÿåòñÿ ñëåäóþ-
ùåå ñîîòíîøåíèå ìåæäó ìíîæåñòâàìè:
tu n tu
n tu n tu�
�
� �� � � � � � �1
1 21 2 2 1( ) ( ) , , , ,� � � � � � � �{ } { , ,� �3 4 },
ãäå � � � �� � � � �( ) q r qtu tu2 2 .  ÷àñòíîñòè, | ( ) |
tu
� 1 4� è � �1 2� � �q tu
� �q r tu2 , � 2 1 2� � �q r tu , � 3 2 2� � � �q r tu n tu , � 4 1 2 2� � � � �q r tu n tu .
Îáîçíà÷èì
D S k S kS n
k V
n
i
tun
( , ) ( ( ) ( ), )
( )
� � � � �
� �
� � � ��
��
�
��
��2 2
1 1
4
�� � �
�
� � �( ( ) ( ), )S k S k
k Vn
.
Ëåììà 1.  ïðèíÿòûõ îáîçíà÷åíèÿõ äëÿ îòîáðàæåíèÿ (2) âûïîëíÿåòñÿ ñëå-
äóþùàÿ îöåíêà:
d DF S
� ( , ) ( , )� � � � , � �, \�Vn { }0 . (3)
Äîêàçàòåëüñòâî. Ñîãëàñíî (1) è (2) èìååì
d F x F xF n
k k
x k Vn
�
�
�
� � � ��( , ) ( ( ) ( ), )
,
� � � � �2 2
� � � � ��
�
�2 2n
tu tu
x k V
L S x k L S x k
n
� � �( ( ( )) ( ( )), )
,
.
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Ïîñëå âûïîëíåíèÿ çàìåíû ïåðåìåííîé x k� íà k ïîëó÷àåì
d L S k L S kF n
tu tu
k Vn
�
�
�
� � ��( , ) ( ( ( )) ( ( )), )� � � � �2 .
Ïîñëåäíåå âûðàæåíèå ïðåîáðàçóåì ñëåäóþùèì îáðàçîì:
d L S k L S k S kF n
tu tu�
��
�
�
�
� �
� �( , ) ( ( ( ) ) ( ( ), ) ( ( )� � � � � � �2 S k
Vk V nn
( ), )�
���
��
�
�
�
�
�
�
�
�
� �
� ��2 n
tu tuL S k L S k S k S k� � � � � �
�
( ( ( ) ) ( ( ), ) ( ( ) ( ), )
�� �
��
�
�
�
tunk V 1( )�
.
Ïîñêîëüêó � � �( ( ( ) ) ( ( )), )L S k L S km m� � 1, èìååì
d S k S k DF n
k V
S
tun
�
�
��
� � �
�
��( , ) ( ( ) ( ), ) ( ,
( )
� � � � � �
� �
2
1
�) ,
÷òî è òðåáîâàëîñü äîêàçàòü.
ÏÎÑÒÐÎÅÍÈÅ ÂÅÐÕÍÈÕ ÎÖÅÍÎÊ ÂÅÐÎßÒÍÎÑÒÅÉ ÖÅËÎ×ÈÑËÅÍÍÛÕ
ÐÀÓÍÄÎÂÛÕ ÄÈÔÔÅÐÅÍÖÈÀËÎÂ
Äëÿ äàëüíåéøåãî èçëîæåíèÿ ïîíàäîáÿòñÿ ñëåäóþùèå îáîçíà÷åíèÿ.
Äëÿ ïðîèçâîëüíîãî x Vn� , x x x x V i pp i
u� � � � �( ), , ,( ) ( ) ( )
�
1 1 , îáîçíà÷èì
~ ( )( ) ( )x x x Vp t
n tu� � � ��
��
1 è ~~ ( )( ) ( )x x x Vt
tu� � � ��
1 (òîãäà x x x� (~, ~~)).
Äëÿ ââåäåííîãî ðàíåå îòîáðàæåíèÿ S V Vn n: � òàêæå îáîçíà÷èì
~
:S V Vn tu n tu� �� , ãäå
~
(~) ( ( ), ..., ( ))( ) ( ) ( ) ( )S x S x S xp p t t� � �1 1 , è
~~
:S V Vu tu� , ãäå
~~
(~
~
) ( ( ), ..., ( ))( ) ( ) ( ) ( )S x S x S xt t� 1 1 .
Ââåäåì ñëåäóþùèå âåëè÷èíû:
� � � �
�
S
V
q V
u i i
i
u
u
S k S k q
( )
max ( ( ) ( ), ) (
\{ }
( ) ( )� � � �
�
�
�
0
2 { S k S k qi i
k Vu
( ) ( )( ) ( ), ) ,� � �
�
� � 1 } (4)
i p�1, ;
d S k S kS
V
u j j
k V
j
u
u
( )
max ( ( ) ( ), ),
, \
( ) ( )� � �
�
�
�
�
� �
� � �
{ }0
2 j p�1, , �k l
j k l
Sd
j
,
,
max .
( )
�
�
(5)
Îáîçíà÷èì
� � � �� � � � ��
�
�
��
(
~~ ~~) ,
~~ ~~ ,k k tu0 2 1
1
åñëè
â ïðîòèâíîì ñëó÷àå,
� � � �� � � � ��
�
�
��
(
~~ ~~) ,
~~
(
~~ ~~)
~~
(
~~
),k S k S k0
1
åñëè
â ïðîòèâíîì ñëó÷àå.
Ñëåäóþùèå òåîðåìû îïðåäåëÿþò âåðõíèå îöåíêè äëÿ âåëè÷èíû (1) îòîáðàæåíèÿ (2).
Òåîðåìà 1. Ïóñòü 1
2
4
�
�
�
�
�
� � �t
p
p p N, , . Òîãäà
d F S
t t p� � ( , ) max , ,
( )
, ( ),� � �{ }
1
1 12� � .
Äîêàçàòåëüñòâî. Ïóñòü 1
2
4
�
�
�
�
�
� � �t
p
p p N, , (âåëè÷èíà ñäâèãà âëåâî íå
ïðåâîñõîäèò ïîëîâèíû îáùåãî êîëè÷åñòâà s-áëîêîâ), 0 ��r n tu2 1, 0 q
�2 1tu . Ðàññìîòðèì äëÿ ~~� � 0 âîçìîæíûå ñëó÷àè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 73
Ñëó÷àé 1. Ïóñòü 0 � �q tu2 1. Òîãäà x x x� �(~, ~~), (~, ~~)� � � è ñîîòâåòñòâåííî
� � �1 1 1� �(~ , ~~ ) ( , )r q , � 2 1� �( , )r q , � 3
22� � �( , )r qn tu , � 4
22 1� � ��( , )r qn tu .
 ïðèíÿòûõ îáîçíà÷åíèÿõ
D S k S kS n
i
ik Vn
( , ) ( ( ) ( ), )� � � � �� � � ��
��
��2
1
4
� � �
�
�
� ��2 2tu
k V
n tuS k S k q
tu
� � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
( ) ~
(
~ ~ )
~
(
~
) ), )
~
S k S k r
k Vn tu
� � � � �
� �
� � � �
� � � �
�
�
� ��2 1 2tu
k V
n tuS k S k q
tu
� �(
~~
(
~~ ~~)
~~
(
~~
), )
~~
( ) � � � �(
~
(
~ ~ )
~
(
~
) , )
~
S k S k r
k Vn tu
� � � � �
� �
�
� � �
�
�
� ��2 2tu
k V
n tuS k S k q
tu
� � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
( ) ~
(
~ ~ )
~
(
~
) , )
~
S k S k r n tu
k Vn tu
� � � � � ��
� �
� � � � 2 2
� � � �
�
�
�2 1tu
k V
S k S k q
tu
� �(
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � � �� � �
� �
�2 2 2( )
~
(
~
(
~ ~ )
~
(
~
) , )n tu n tu
k V
S k S k r
n tu
� � � � �
� � � � � ��2 tu S k S k q S k( (
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
� � � � S k q
k Vtu
(
~~
), ))
~~
�
�
� 1
� � � � �� �
� �
�2 ( )
~
( (
~
(
~ ~ )
~
(
~
) , ) (
~
(n tu
k V
S k S k r S
n tu
� � � � �
~ ~ )
~
(
~
) , )k S k r n tu� � � � � �� � � 2 2 .
Îáîçíà÷èì
f k S k S k r1 ( , ) (
~
(
~ ~ )
~
(
~
) , )� � � � �� � � � � ,
f k S k S k r n u
2
22( , ) (
~
(
~ ~ )
~
(
~
) , )� � � � �� � � � � � � .
Òîãäà â ñèëó îäíîçíà÷íîñòè îïåðàöèè ñëîæåíèÿ, åñëè äëÿ íåêîòîðûõ
~
k âû-
ïîëíÿåòñÿ f k1 1( , )� � , òî f k2 0( , )� � , è íàîáîðîò. Òàêèì îáðàçîì,
� �
~
: ( , ) ( , )k f k f k1 2 1� � , ñëåäîâàòåëüíî,
2� �
�
� � � � �
�
�( )
~
( (
~
(
~ ~ )
~
(
~
) , ) (
~
(
~n tu
k V
S k S k r S
n tu
� � � � � k S k r n tu� � � � � �~ )
~
(
~
) , )� � � 2 12 .
Îòñþäà
D S k S k q S kS tu( , ) ( (
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~
� � � � � � � � ��2 ~~)
~~
(
~~
), ))
~~
� � �
�
� S k q
k Vtu
1 .
Ðàññìîòðèì äâà âîçìîæíûõ âàðèàíòà äëÿ ~~ ( ) :( ) ( ) ( )� � � �� � � �t
�
1 1 0 è
� ( )1 0� .
1. Åñëè � ( )1 0� , òî
D S k S k qS u
k
( , ) ( ( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )
(
� � � � � � ��2 1 1 1 1 1 1
1)�
�
Vu
� � � � � �( ( ) ( ), ))( ) ( ) ( ) ( ) ( ) ( )S k S k q1 1 1 1 1 1 1
� �
�
�
�max ( ( ) (
( )
( )
\
( ) ( ) ( ) ( )
�
� �
1
1
0
1 1 1 12
V
q V
u
u
u
S k S k
{ }
{ ( ) ( )), )1 1q
k Vu
�
�
�
� � � �� �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )S k S k q1 1 1 1 1 1 1 }.
Òàêèì îáðàçîì, D S S( , )
( )
� � �
1
.
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
2. Åñëè � ( )1 0� , òî ðàâåíñòâî
~~
(
~~ ~~)
~~
(
~~
) ~~S k S k� � �� � âîçìîæíî ëèøü â ñëó÷àå
�( )1 0� . Ïîñêîëüêó òîëüêî îäèí èç âåêòîðîâ, q èëè q �1, ìîæåò èìåòü ïåðâóþ ïðà-
âóþ íóëåâóþ êîìïîíåíòó, òî D S kS
V
q V
tu
tu
tu
( , ) max (
~~
(
~~ ~~ )
~~
~~ \
~~
� � � �
�
� �
�
�
�
{ }0
2 S k q
k Vtu
(
~~
), ~~ )
~~
�
� .
Îáîçíà÷èì äëÿ ïðîèçâîëüíîãî ~~ : min
,
( )� �� � �
�
V itu
j t
j
2
0{ }. Òîãäà äëÿ 2 i t
èìååì
D S kS
V
q V
u i i i
i
u
i
tu
( , ) max ( ( (
( )
( )
\
( ) ( ) ( )� � � �
�
�
�
�
�
{ }0
2 ) ( ), ))( ) ( ) ( )
( )
� �
�
� S k qi i i
k V
i
u
� �
�
d dS
i t
S
t t
i i( ) ( )
max
,
, ,
2
2 1� � .
Ñëó÷àé 2. Ïóñòü q tu� �2 1. Òîãäà
� � �1 1 1 2 1� � �(~ , ~~ ) ( , )r tu , � 2 1 0� �( , )r ,
� 3
22 2 1� � ��( , )r n tu tu , � 4
22 1 0� � ��( , )r n tu ,
D S k S kS tu
k Vtu
( , ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � �� � �
�
�
�2 0
� � � � � �� �2 1( ) (
~
(
~ ~)
~
(
~
), ) (
~
(
~ ~)
~
(
~n tu S k S k r S k S{� � � � k r n tu
k Vn tu
), )
~
� � ��
� �
� 2 12 }
� � � �
�
�
�2 2 1tu tu
k V
S k S k
tu
� �(
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � � �� �2 ( ) (
~
(
~ ~)
~
(
~
), ) (
~
(
~ ~)
~
(
~
)n tu S k S k r S k S k{� � � � , )
~
r n tu
k Vn tu
� �
� �
� 2 2 }.
Î÷åâèäíî, ÷òî â ñèëó áèåêòèâíîñòè îòîáðàæåíèÿ
~~
S èìååì
~~
(
~~ ~~)
~~
(
~~
)S k S k� � �� 0
òîëüêî ïðè ~~� � 0 , ÷òî ïðîòèâîðå÷èò óñëîâèþ ~~� � 0 .
1. Ïðè ~~� � 0 èìååì
D S k S kS tu tu
k Vtu
( , ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � �� � � ��
�
�2 2 1
� � � � � �� �2 1( ) (
~
(
~ ~)
~
(
~
), ) (
~
(
~ ~)
~
(
~n tu S k S k r S k S{� � � � k r n tu
k Vn tu
), )
~
� ��
� �
� 2 12 }.
Ïîñêîëüêó
2 1� � � � � � � �( ) (
~
(
~ ~)
~
(
~
), ) (
~
(
~ ~)
~
(
~n tu S k S k r S k S k{� � � � ), )
~
r n tu
k Vn tu
� � �
� �
� 2 1 12 } ,
ïîëó÷èì
D S k S kS tu tu
k Vtu
( , ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � �� � � ��
�
�2 2 1 � ��
�
�2 tu
k V
S k S k q
tu
� �(
~~
(
~~ ~~)
~~
(
~~
), )
~~
.
Îáîçíà÷èì äëÿ ïðîèçâîëüíîãî ~~ : min
,
( )� �� � �
�
V itu
j t
j
1
0{ }. Òîãäà
D S kS
V
q V
u i i i
i
u
i
u
( , ) max ( ( )
( )
( )
\
( ) ( ) ( )� � � �
�
� �
�
�
�
{ }0
2 S k q di i i
k V
S
i
tu
i
( ) ( ) ( )( ), )
( )
( )
�
� � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 75
2. Ðàññìîòðèì ñëó÷àé ~~� � 0 . Òîãäà àíàëîãè÷íî [14] ñïðàâåäëèâî íåðàâåíñòâî
� �� Vn , � � ��
�
� �
�
� �
�
� � � � �
� �
�
V d S kn
F n
k Vn tu
\ : ( , ) ( (
( )
~~
{ }0 2
1
0
) ( ), )� S k � .
Ïîñêîëüêó
tu
n tu n tu� � �� � � � � �1
1 2 3 41 2 2 1( ) , , , , , ,� � � � � � � � �{ } { }, ãäå �1 �
� � � � �� � �( ) q q rtu tu2 2 , ìíîæåñòâî { }� � �� ��
tu
1 0( ) : ~~ ñîäåðæèò íå áîëåå
äâóõ ýëåìåíòîâ: ëèáî � 1 è � 3 , ëèáî � 2 è � 4 . Ïîýòîìó ñïðàâåäëèâà îöåíêà
d S kF
i t p V
u i
u
�
� � �
� � �( , ) max max ( ( )
( ), , \
( )� � � �
� �
2 2
1 0{ }
S ki
k V
t p
u
( )
( ),( ), )�
�
�� � 2 1� .
Òåîðåìà 2. Ïóñòü
p
t p p p N
2
1 4� � � �, , . Òîãäà
d dF S
t p� ( , ) max , ,
( )
, ,� � { }2 2
1
2 1� � .
Äîêàçàòåëüñòâî. Ïóñòü
p
t p p p N
2
1 4� � � �, , (âåëè÷èíà ñäâèãà âëåâî íå
ìåíüøå ïîëîâèíû îáùåãî êîëè÷åñòâà s-áëîêîâ).
 ïðèíÿòûõ îáîçíà÷åíèÿõ � �1 2 2� � � �q q rtu tu , � 2 1 2� � �q r tu , � 3 �
� � � �q r tu n tu2 2 , � 4 1 2 2� � � � �q r tu n tu ; 0 ��r n tu2 1, 0 �q tu2 1.
Ðàññìîòðèì ïîäðîáíî âîçìîæíûå âàðèàíòû.
Ñëó÷àé 1. Åñëè q tu� �2 1, òî � � �1 1 1 2 1� � �(~ , ~~ ) ( , )r tu , � 2 1 0� �( , )r ,
� 3 2 1� � ��( , )r tu n tu2 , � 4 2 2� � �( , )r tu n tu . Òîãäà
D S k S kS n
i
ik Vn
( , ) ( ( ) ( ), )� � � � �� � � ��
��
��2
1
4
� � � � �
� �
� �
�2 ( )
~
(
~
(
~ ~ )
~
(
~
) , )
( )
n tu
k V
S k S k r
n tu
� � � �
� � � � ��2 2 1tu tuS k S k S k{� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � ��
�
� S k tu n tu
k Vtu
2 2 1
� � � � ��� �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k tu n tu2 2 }
� � � � � � �� �
�
2 1n tu
k V
S k S k k r
n
� � � � �(
~
(
~ ~ ))
~
(
~
) (
~~ ~~), )
~
( �
�
tu)
� ��
�
�2 0tu
k V
S k S k
tu
( (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � .
1. Åñëè ~~� � 0 (ïðè ýòîì ~� � 0), òî � � 0, � � 0 è 2 0�
�
� ��tu
k V
S k S k
tu
( (
~~
(
~~
)
~~
(
~~
), )
~~
�
òîëüêî ïðè � 0 . Òîãäà
D S k S k rS n tu
k V n tu
( , ) (
~
(
~ ~ )
~
(
~
), )( )
~
( )
� � � �� � � �� �
� �
�2 1
� ��
�
�2 0tu
k V
S k S k
tu
�(
~~
(
~~
)
~~
(
~~
), )
~~
� � � �� �
� �
�2 1( )
~
(
~
(
~ ~)
~
(
~
), )
( )
n tu
k V
S k S k r
n tu
� � .
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Îáîçíà÷èì äëÿ ïðîèçâîëüíîãî ~� � �Vn tu , ~ ( ) :( ) ( )� � �� � � �p t
�
1
i
j t p
j� �
� �
min
( ),
( )
1
0{ }� . Òîãäà äëÿ t i p� èìååì
D S kS
r V
u
k V
i i
i i
u
i
u
( , ) max ( (
( ) ( ) ( ), \
( ) ( )� � �
�
�
�
�
�
�
{ }0
2 � ( ) ( ) ( )) ( ), )
( )
i i i SS k r d
i
� �
�
�
�max
( )
( ),
t i p
S
t pd
i
� 1 .
2. Åñëè ~~� � 0 , òî 2 0 0�
�
� � ��tu
k V
S k S k
tu
( (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � ,
D S k S k rS n tu
k Vn tu
( , ) (
~
(
~ ~ )
~
(
~
) , )( )
~
� � � � � �� � � � �
� �
� �
2 �
� � � � ��2 2 1tu tuS k S k S k{� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � ��
�
� S k tu n tu
k Vtu
2 2 1
� � � � �� �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k tu n tu2 2 }.
Ïîñêîëüêó 2 1� �
�
� � � �
�
�( )
~
(
~
(
~ ~ )
~
(
~
) , )n tu
k V
S k S k r
n tu
� � � � , èìååì
D S k S kS tu tu
k Vt
( , ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � � � � � ��
�
2 2 1{
u
�
� � � � � � ��� � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~S k S k S ktu n tu2 2 1 �)
~~
(
~~
), )� � �S k tu n tu2 2 }.
Ðàññìîòðèì äâà âîçìîæíûõ âàðèàíòà: � ( )1 0� è � ( )1 0� .
� Åñëè � ( )1 0� , òî
� �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k tu� � � �2 1 0 , � �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k tu n tu� � � � ��2 2 1 0 .
Îáîçíà÷èì äëÿ ïðîèçâîëüíîãî ~~ : min
,
( )� �� � �
�
V in
j t
j
2
0{ }. Òîãäà äëÿ 2 i t
èìååì
D S k S kS tu tu n tu
k
( , ) (
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � � � � �� �
�
2 2 2
Vtu
�
� �
� �
�max max ( ( ) (
, \
( ) ( ) ( ) ( )
( )
i t V
u i i i i
i
u
S k S k
2 0
2
�
� �
{ }
( ) ( )
,), )i i
k V
tq
u�
� � � 2 .
� Åñëè � ( )1 0� , òî
D S k S k SS tu tu( , ) (
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~
� � � � � � � � ��2 2 1
~
~~)
~~
(
~~
), )
~~
k S k tu n tu
k Vtu
� � � � �
�
� � 2 2 1
� �
�
�2 2 2
1
0
1 1 1 1 1max ( ( ) ( ),
( )
\
( ) ( ) ( ) ( ) ( )
�
� �
V
u u
u
S k S k
{ }
�
�
� 1 2
1
)
( )
k V
S
u
d .
Ñëó÷àé 2. Åñëè 2 2 1n tu tuq� � � , òî � � �1 1 1� �(~ , ~~ ) ( , )r q , � 2 1� �( , )r q ,
� 3 2� � �( , )r q n tu , � 4 1 2� � � �( , )r q n tu . Òîãäà
D S k S k rS n tu
k Vn tu
( , ) (
~
(
~ ~ )
~
(
~
) , )( )
~
� � � � � �� � � � �
� �
� �
2 �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 77
� � � � ��2 tu S k S k q S k{� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
S k q
k Vtu
(
~~
), )
~~
� �
�
� 1
� � � � � � ��� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~
S k S k q S kn tu2
~
(
~~
), )S k q n tu� � �1 2 }.
Î÷åâèäíî, ÷òî 2 1� �
�
� � � �
�
�( )
~
(
~
(
~ ~ )
~
(
~
) , )n tu
k V
S k S k r
n tu
� � � � ,
D S k S k q S kS tu( , ) (
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~
� � � � � � � � ��2 { ~~)
~~
(
~~
), )
~~
� � � �
�
� S k q
k Vtu
1
� � � � � � ��� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~
S k S k q S kn tu2
~
(
~~
), )S k q n tu� � �1 2 }. (6)
1. Ïóñòü ~~� � 0 . Îáîçíà÷èì: �1 � q , �2 1� �q , �3 2� � �q n tu , �4 �
� � � �q n tu1 2 , � � �i i
t
i� ( , ..., )( ) ( )1 .
� Åñëè � ( )1 0� , òî àíàëîãè÷íî ïðèâåäåííûì âûøå ïðåîáðàçîâàíèÿì ïîëó÷èì
D S k S k SS n u( , ) (
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(( )� � � � � � � � �� �2 1{
~~ ~~)
~~
(
~~
), )
~
k S k
k Vn u
� � �
� �
� � �2
� � � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
(
~~
S k S k S k S� � � � �3 k ), )�4 }
� � ��
�
�2 1 1 1 1 1
1
1u
k V
S k S k
u
{� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )
� � � �� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )S k S k1 1 1 1 1
2
1
� � � � �� � � � �( ( ) ( ), ) ( (( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )S k S k S k1 1 1 1 1
3
1 1 1 ( ) ( ) ( ) ( )) ( ), )1 1 1
4
1� S k � }.
Èç îïðåäåëåíèÿ äåëüòà-ôóíêöèè o÷åâèäíî, ÷òî èç ÷åòûðåõ ñëàãàåìûõ â ôè-
ãóðíûõ ñêîáêàõ îäíîâðåìåííî íåíóëåâûìè ìîãóò áûòü ëèáî ïåðâîå è òðåòüå,
ëèáî âòîðîå è ÷åòâåðòîå.
Òàêèì îáðàçîì, ñïðàâåäëèâà ñëåäóþùàÿ îöåíêà:
D S k SS
V
u
u
( , ) max ( ( )
( ) ( )
, \
( ) ( ) ( )� � � �
� �
� �
�
�2 2
1 1
0
1 1 1
{ }
( ) ( ) ( )( ), )
( )
( )
1 1 1
1
1
2k d
k V
S
u
�
�
� .
� Åñëè � ( )1 0� , òî äëÿ � �Vn âûáåðåì � ( ) :i � 0 i
j t
j� �
�
min
,
( )
2
0{ }� .
Çàìåòèì, ÷òî ïðè � ( )1 0� èìååì � � �(
~~
(
~~ ~~)
~~
(
~~
),
~~
)S k S k� � � 0 òîãäà è òîëüêî
òîãäà, êîãäà � ( )1 0� .
Ðàññìîòðèì � j
i( ) — i-é ñïðàâà áëîê â � j j, ,�1 4. Î÷åâèäíî, â îöåíêå (6) íåíóëå-
âûìè ñëàãàåìûìè áóäóò òå, êîòîðûå ñîäåðæàò ëèáî � �1 3, , ëèáî � �2 4, .
Ïðåäïîëîæèì, ÷òî
2
1
�
�
� � ��u i i i i i i
k V
S k S k
u
{� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )
� � � �� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )S k S ki i i i i i
3
0}
(â ñëó÷àå, åñëè
2
2
�
�
� � ��u i i i i i i
k V
S k S k
u
{� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )
� � � �� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )S k S ki i i i i i
4
0} ,
îöåíêà ìîæåò áûòü ïîñòðîåíà àíàëîãè÷íî). Òîãäà
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
2
1
�
�
� � ��u i i i i i i
k V
S k S k
i
u
{� � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )
( )
� � � � � �( ( ) ( ), )( ) ( ) ( ) ( ) ( ) ( )S k S ki i i i i i
3
}
!
"" � ��
�
2
1
0
u
V
i i i i
i i
u
S k Smax ( ( )
( ) ( )
, \
( ) ( ) ( ) ( )
� �
� �
{ }
( ), )( ) ( )
( )
k i i
k V
i
u
�
1
�
� �
� � �
�
max ( ( ) ( ),
( ) ( )
, \
( ) ( ) ( ) ( ) ( )
� �
� �
i i
uV
i i i i iS k S k
3
0{ }
�
3
( ) )
( )
i
k V
i
u�
�
#
$
%%
� �
�
�2 2
0
max ( ( ) (
( ) ( )
, \
( ) ( ) ( ) ( ) (
� �
� �
i i
uV
u i i i i iS k S k
{ }
) ( )), )
( )
( )
� i
k V
S
i
u
i
d
�
� 2 ,
ñëåäîâàòåëüíî, D dS
i t
S
t
i
( , ) max
,
,
( )
� � �
�2
22 2� .
2 . Åñëè ~~� � 0 , òî ïðè ýòîì ~� � 0 . Òîãäà � � 0, � � 0 è
2 0�
�
� ��tu
k V
S k S k
tu
( (
~~
(
~~
)
~~
(
~~
), )
~~
� òîëüêî ïðè � 0 . Äëÿ � �Vn âûáåðåì � ( )i � 0:
i
j t p
j� �
� �
min
,
( )
1
0{ }� . Òîãäà
D S k S kS n tu
r V
p
n tu
( , ) max (
~
(
~ ~)
~
(
~
, \
( )
� � � �
�
� �� �
� �
2
0{ }
)), )r
k Vn tu
� �
�
� �
� � �
�max max ( ( )
, \
( ) ( ) ( ) ( )
( )
i t p V
u i i i i
i
u
S k S
1 0
2
�
� �
{ }
( ), )( ) ( )
,k qi i
k V
t p
u�
�� � � 1 .
Ñëó÷àé 3. Åñëè 0 � ��q n tu2 1, òî � � �1 1 1� �(~ , ~~ ) ( , )r q , � 2 1� �( , )r q ,
� 3 1 2 2� � � ��( , )r qtu n tu , � 4 1 2 2 1� � � � ��( , )r qtu n tu . Òîãäà
D S k S k rS n tu
k Vn tu
( , ) (
~
(
~ ~ )
~
(
~
) , )
~
� � � � � �� � � � �� �
� �
�2 { }
� � � � ��2 tu S k S k q S k{� � � �(
~~
(
~~ ~~)
~~
(
~~
), ) (
~~
(
~~ ~~)
~~
S k q
k Vtu
(
~~
), )
~~
� �
�
� 1 }
� � � � � �
� �
�
�2 1n tu
k V
S k S k r
u
{ }� � � �(
~
(
~ ~ )
~
(
~
) , )
~
� � � � �� ��2 2 2tu tu n tu
k
S k S k q{� �(
~~
(
~~ ~~)
~~
(
~~
), )
~~
� � � � � ��� �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k qtu n tu2 2 1 }. (7)
Ëåãêî çàìåòèòü, ÷òî â äàííîì ñëó÷àå îäíîâðåìåííî ëèáî
� � � �(
~
(
~ ~ )
~
(
~
) , )S k S k r� � � � � 0 , ëèáî � � � �(
~
(
~ ~ )
~
(
~
) , )S k S k r� � � � � �1 0 .
Åñëè � � � �(
~
(
~ ~ )
~
(
~
) , )S k S k r� � � � � 0 (âî âòîðîì ñëó÷àå âñå îöåíêè ìîãóò áûòü ïî-
ñòðîåíû àíàëîãè÷íî), ëèáî � �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k q� � � 0, ëèáî � �(
~~
(
~~ ~~)
~~
(
~~
), )S k S k q� � � �1 0.
Òàêèì îáðàçîì, âûðàæåíèå (7) ñîäåðæèò íå áîëåå îäíîãî ñëàãàåìîãî è � �� Vn \ { }0 ,
âûáðàâ � ( )i � 0 : i
j p
j� �
�
min
,
( )
1
0{ }� , ïîëó÷èì
D S k S kS
j p V
u j j
u
( , ) max max ( ( ) (
, , \
( ) ( )� � � �
� �
� �
� �
�
1 0
2
{ }
), ) ,�
k V
p
u�
� �1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 79
Ñëó÷àé 4. Åñëè q n tu� ��2 1, òî � � �1 1 1� �(~ , ~~ ) ( , )r q , � 2 1� �( , )r q , � 3 �
� � �( , )r tu1 2 1 , � 4 0� ( , )r . Ìîæåò áûòü ïîñòðîåíà îöåíêà, àíàëîãè÷íàÿ ñëó÷àþ 3:
D S k S kS
j p V
u j j
u
( , ) max max ( ( ) (
, , \
( ) ( )� � � �
� �
� �
� �
�
1 0
2
{ }
), ) ,�
k V
p
u�
� �1 .
Òåîðåìà äîêàçàíà.
ÐÅÇÓËÜÒÀÒÛ ÑÒÀÒÈÑÒÈ×ÅÑÊÈÕ ÈÑÑËÅÄÎÂÀÍÈÉ ÐÀÑÏÐÅÄÅËÅÍÈÉ
×ÈÑËÎÂÛÕ ÏÀÐÀÌÅÒÐÎÂ, ÕÀÐÀÊÒÅÐÈÇÓÞÙÈÕ ÇÍÀ×ÅÍÈß ÑÐÅÄÍÈÕ
ÂÅÐÎßÒÍÎÑÒÅÉ ÖÅËÎ×ÈÑËÅÍÍÛÕ ÐÀÓÍÄÎÂÛÕ ÄÈÔÔÅÐÅÍÖÈÀËÎÂ
 òàáë. 1, 2 ïðåäñòàâëåíû ðåçóëüòàòû ñòàòèñòè÷åñêèõ ðàñïðåäåëåíèé ïàðàìåò-
ðîâ (4), (5) äëÿ 8-áèòîâûõ s-áëîêîâ. Äëÿ èññëåäîâàíèé ñãåíåðèðîâàíî 10 000 íå-
çàâèñèìûõ ðàâíîâåðîÿòíûõ ïîäñòàíîâîê, äëÿ êàæäîé èç êîòîðûõ ïîñ÷èòàíû
çíà÷åíèÿ ñîîòâåòñòâóþùèõ ïàðàìåòðîâ.  òàáë. 1 ïðèâåäåíî ñòàòèñòè÷åñêîå
ðàñïðåäåëåíèå ïàðàìåòðà
� � � �
�
S
V
q V
u i i
i
u
u
S k S k q
( )
max ( ( ) ( ), ) (
\
( ) ( )� � � �
�
�
�
{ }
{
0
2 S k S k qi i
k Vu
( ) ( )( ) ( ), )� � �
�
� � 1 },
â òàáë. 2 — ñòàòèñòè÷åñêîå ðàñïðåäåëåíèå ïàðàìåòðà
d S k S kS
V
u j j
k V
j
u u
( )
max ( ( ) ( ), )
, \
( ) ( )� � �
�
�
�
�
� �
� � �
{ }0
2 .
ÇÀÊËÞ×ÅÍÈÅ
 ðåçóëüòàòå ñòàòèñòè÷åñêèõ èññëåäîâàíèé ðàñïðåäåëåíèé ïàðàìåòðîâ (4), (5),
â ÷àñòíîñòè, äëÿ 8-áèòîâûõ s-áëîêîâ íàéäåíû ïîäñòàíîâêè ñ íàèìåíüøèìè
âîçìîæíûìè çíà÷åíèÿìè ýòèõ ïàðàìåòðîâ. Íà îñíîâàíèè ïîëó÷åííûõ äàííûõ
âåðõíÿÿ îöåíêà ñðåäíåé âåðîÿòíîñòè öåëî÷èñëåííîãî ðàóíäîâîãî äèôôåðåíöè-
àëà äëÿ îòîáðàæåíèÿ (2) ïðè íàäëåæàùåì âûáîðå s-áëîêîâ ìîæåò ïðèíèìàòü
çíà÷åíèÿ, íå ïðåâîñõîäÿùèå 0,04.
Îòìåòèì, ÷òî äëÿ îòîáðàæåíèÿ (2) äîñòèãàåòñÿ ìåíüøåå çíà÷åíèå âåðõíåé
îöåíêè ñðåäíåé âåðîÿòíîñòè öåëî÷èñëåííîãî ðàóíäîâîãî äèôôåðåíöèàëà, ÷åì
â ñëó÷àå, êîãäà îïåðàòîð ïåðåñòàíîâêè ÿâëÿåòñÿ îïåðàòîðîì öèêëè÷åñêîãî ñäâè-
ãà, âåëè÷èíà êîòîðîãî âçàèìíî ïðîñòà ñ äëèíîé âõîäà s-áëîêà, è ïðè íàäëåæàùåì
âûáîðå s-áëîêîâ áóäåò âûïîëíÿòüñÿ íåðàâåíñòâî d F
� ( , ) ,� � 0 08 (ñì. [14]).
80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Ò à á ë è ö à 1
Çíà÷åíèå ïàðàìåòðà
Êîëè÷åñòâî
ïîäñòàíîâîê
0,03125 11
0,03515625 2415
0,0390625 5333
0,04296875 1847
0,046875 328
0,05078125 60
0,0546875 4
0,05859375 2
Ò à á ë è ö à 2
Çíà÷åíèå ïàðàìåòðà
Êîëè÷åñòâî
ïîäñòàíîâîê
0,0195315 13
0,0234375 4744
0,0273438 4458
0,03125 724
0,0351563 57
0,0390625 3
0,0429688 1
Äàííûå ðåçóëüòàòû ïîçâîëÿþò ñòðîèòü âåðõíèå îöåíêè ñðåäíèõ âåðîÿòíîñ-
òåé öåëî÷èñëåííûõ ðàçíîñòíûõ õàðàêòåðèñòèê áëîêîâûõ øèôðîâ, â ñòðóêòóðó
êîòîðûõ âõîäÿò óêàçàííûå ïðåîáðàçîâàíèÿ. Ïðè ýòîì ñðåäíÿÿ âåðîÿòíîñòü ðàç-
íîñòíîé õàðàêòåðèñòèêè çàâèñèò êàê îò êîëè÷åñòâà ðàóíäîâ, òàê è îò ñâîéñòâ
áëîêà ïîäñòàíîâêè è íàëè÷èÿ äîïîëíèòåëüíûõ ïðåîáðàçîâàíèé â ðàóíäå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. K o v a l c h u k L . , A l e k s e y s h u k A . Upper bounds of maximum value of average differential
and linear characteristic probabilities of feistel cipher with adder modulo 2ï // Theory Stoch. Pro-
cesses. — 2006. — 12(28), N 1, 2. — P. 20–32.
2. Ê î â à ë ü ÷ ó ê Ë . Â . Âåðõíèå îöåíêè ñðåäíèõ âåðîÿòíîñòåé äèôôåðåíöèàëüíûõ àïïðîêñèìà-
öèé áóëåâûõ îòîáðàæåíèé // Òð. ×åòâeðòîé Îáùåðîñ. íàó÷. êîíô. «Ìàòåìàòèêà è áåçîïàñ-
íîñòü èíôîðìàöèîííûõ òåõíîëîãèé» (ÌàÁÈÒ-05), 2–3 íîÿá. 2005. — Ñ. 163–167.
3. Ê î â à ë ü ÷ ó ê Ë .  . Îáîáùåííûå ìàðêîâñêèå øèôðû: îöåíêà ïðàêòè÷åñêîé ñòîéêîñòè
ê ìåòîäó äèôôåðåíöèàëüíîãî êðèïòîàíàëèçà // Òð. Ïÿòîé Îáùåðîñ. íàó÷. êîíô. «Ìàòåìàòèêà
è áåçîïàñíîñòü èíôîðìàöèîííûõ òåõíîëîãèé» (ÌàÁÈÒ-06), 25–27 îêò. 2006. — Ñ. 595–599.
4. Î ë å ê ñ ³ é ÷ ó ê À . Ì . , Ê î â à ë ü ÷ ó ê Ë .  . , Ï à ë ü ÷ å í ê î Ñ .  . Êðèïòîãðàô³÷í³ ïàðàìåò-
ðè âóçë³â çàì³íè, ùî õàðàêòåðèçóþòü ñò³éê³ñòü ÃÎÑÒ-ïîä³áíèõ áëîêîâèõ øèôð³â â³äíîñíî ìåòîä³â
ë³í³éíîãî òà ð³çíèöåâîãî êðèïòîàíàë³çó // Çàõèñò ³íôîðìàö³¿. — 2007. — ¹ 2. — Ñ. 12–23.
5. À ë å ê ñ å é ÷ ó ê À . Í . , Ê î â à ë ü ÷ ó ê Ë . Â . , Ø å â ö î â À . Ñ . , Ñ ê ð û ï í è ê Ë . Â . Îöåí-
êè ïðàêòè÷åñêîé ñòîéêîñòè áëî÷íîãî øèôðà «Êàëèíà» îòíîñèòåëüíî ðàçíîñòíîãî, ëèíåéíîãî
áèëèíåéíîãî ìåòîäîâ êðèïòîàíàëèçà // Òð. Ñåäüìîé Îáùåðîñ. íàó÷. êîíô. «Ìàòåìàòèêà
è áåçîïàñíîñòü èíôîðìàöèîííûõ òåõíîëîãèé» (ÌàÁÈÒ-08), 30 îêò.–2 íîÿá. 2008. — Ñ. 15–20.
6. À ë å ê ñ å é ÷ ó ê À . Í . , Ê î â à ë ü ÷ ó ê Ë . Â . , Ñ ê ð û í í è ê Å . Í . , Ø å â ö î â À . Ñ . Îöåí-
êè ïðàêòè÷åñêîé ñòîéêîñòè áëî÷íîãî øèôðà «Êàëèíà» îòíîñèòåëüíî ìåòîäîâ ðàçíîñòíîãî,
ëèíåéíîãî êðèïòîàíàëèçà è àëãåáðàè÷åñêèõ àòàê, îñíîâàííûõ íà ãîìîìîðôèçìàõ // Ïðèêë.
ðàäèîýëåêòðîíèêà. — 2008. — ¹ 1. — Ñ. 203–210.
7. N a t i o n a l Institute of Standards and Technology: The Advanced Encryption Standard (AES). —
http://csrc.nist.gov/aes/
8. Ã Î Ñ Ò 28147-89. Ñèñòåìû îáðàáîòêè èíôîðìàöèè. Çàùèòà êðèïòîãðàôè÷åñêàÿ. Àëãîðèòì
êðèïòîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ. — Ì.: Ãîññòàíäàðò ÑÑÑÐ, 1989. — 28 ñ.
9. Ã î ð á å í ê î ² . Ä . , Ò î ö ü ê è é Î . Ñ . , Ê à ç ü ì ³ í à Ñ . Â . Ïåðñïåêòèâíèé áëîêîâèé øèôð
«Êàëèíà» — îñíîâí³ ïîëîæåííÿ òà ñïåöèô³êàö³ÿ // Ïðèêë. ðàä³îåëåêòðîí³êà. — 2007. —
6, ¹ 2. — Ñ. 195–208.
10. Ã î ð á å í ê î ² . Ä . , Á î í ä à ð å í ê î Ì . Ô . , Ä î ë ã î â Â . ² . ò à ³ í . Ïåðñïåêòèâíèé áëî-
êîâèé øèôð «Ìóõîìîð» — îñíîâí³ ïîëîæåííÿ òà ñïåöèô³êàö³ÿ // Òàì æå. — 2007. — 6, ¹ 2.
— Ñ. 147–157.
11. W a n g X . , Y u H . How to break MD5 and other hash functions // Adv. Cryptology.
EUROCRYPT’05; Lect. Notes in Computer Sci. — 2005. — 3494. — P. 19–35.
12. C o t i n i S . , R i v e r s t R . L . , R o b s h a w M . J . B . , Y i n Y . L . Security of the RC6TM
block cipher. — http://www.rsasecurity.com/rsalabs/rc6/
13. B e r s o n T . A . Differential cryptanalysis mod 232 with applications to MD5 // Adv. Cryptology.
CRYPTO’98 (LNCS). — 1999. — 372. — P. 95–103.
14. Ê î â à ë ü ÷ ó ê Ë .  . Ïîñòðîåíèå âåðõíèõ îöåíîê ñðåäíèõ âåðîÿòíîñòåé öåëî÷èñëåííûõ
äèôôåðåíöèàëîâ êîìïîçèöèè êëþ÷åâîãî ñóììàòîðà, áëîêà ïîäñòàíîâêè è îïåðàòîðà ñäâèãà //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 6. — C. 89–96.
Ïîñòóïèëà 07.12.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 81
|