О криптографических свойствах нового национального стандарта шифрования Украины
Исследован ряд криптографических свойств блочного шифра «Калина», принятого в качестве нового национального стандарта шифрования Украины. Проанализированы важнейшие свойства компонент этого шифра. Показано, что его раундовые преобразования порождают знакопеременную группу подстановок, а сам шифр явл...
Saved in:
| Date: | 2016 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/133678 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О криптографических свойствах нового национального стандарта шифрования Украины / А.Н. Алексейчук, Л.В. Ковальчук, А.С. Шевцов, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 16-31. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-133678 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1336782025-02-09T17:40:54Z О криптографических свойствах нового национального стандарта шифрования Украины Про криптографічні властивості нового національного стандарту шифрування України Cryptographic properties of the new national encryption standard of Ukraine Алексейчук, А.Н. Ковальчук, Л.В. Шевцов, А.С. Яковлев, С.В. Кибернетика Исследован ряд криптографических свойств блочного шифра «Калина», принятого в качестве нового национального стандарта шифрования Украины. Проанализированы важнейшие свойства компонент этого шифра. Показано, что его раундовые преобразования порождают знакопеременную группу подстановок, а сам шифр является обоснованно стойким относительно разностного и линейного криптоанализа. Досліджено низку криптографічних властивостей блокового шифру «Калина», прийнятого як новий національний стандарт шифрування України. Проаналізовано найважливіші властивості компонент цього шифру. Показано, що його раундові перетворення породжують знакозмінну групу підстановок, що свідчить про стійкість до алгебраїчних атак, побудованих на гомоморфізмах, а сам шифр є обґрунтовано стійким відносно різницевого та лінійного криптоаналізу. Block cipher “Kalyna” has been recently accepted as a new national encryption standard of Ukraine. In the paper we analyze the most important properties of components of this cipher. We show that round transformations of “Kalyna” generate a sign-alternating group of substitutions. As a result, “Kalyna” is secure against algebraic attacks based on homomorphisms. Also we demonstrate that this cipher is reasonably secure against differential and linear cryptanalysis. 2016 Article О криптографических свойствах нового национального стандарта шифрования Украины / А.Н. Алексейчук, Л.В. Ковальчук, А.С. Шевцов, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 16-31. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/133678 621.391:519.2:519.7 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2016 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/133678 |
| citation_txt |
О криптографических свойствах нового национального стандарта шифрования Украины / А.Н. Алексейчук, Л.В. Ковальчук, А.С. Шевцов, С.В. Яковлев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 16-31. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT aleksejčukan okriptografičeskihsvojstvahnovogonacionalʹnogostandartašifrovaniâukrainy AT kovalʹčuklv okriptografičeskihsvojstvahnovogonacionalʹnogostandartašifrovaniâukrainy AT ševcovas okriptografičeskihsvojstvahnovogonacionalʹnogostandartašifrovaniâukrainy AT âkovlevsv okriptografičeskihsvojstvahnovogonacionalʹnogostandartašifrovaniâukrainy AT aleksejčukan prokriptografíčnívlastivostínovogonacíonalʹnogostandartušifruvannâukraíni AT kovalʹčuklv prokriptografíčnívlastivostínovogonacíonalʹnogostandartušifruvannâukraíni AT ševcovas prokriptografíčnívlastivostínovogonacíonalʹnogostandartušifruvannâukraíni AT âkovlevsv prokriptografíčnívlastivostínovogonacíonalʹnogostandartušifruvannâukraíni AT aleksejčukan cryptographicpropertiesofthenewnationalencryptionstandardofukraine AT kovalʹčuklv cryptographicpropertiesofthenewnationalencryptionstandardofukraine AT ševcovas cryptographicpropertiesofthenewnationalencryptionstandardofukraine AT âkovlevsv cryptographicpropertiesofthenewnationalencryptionstandardofukraine |
| first_indexed |
2025-11-28T20:04:33Z |
| last_indexed |
2025-11-28T20:04:33Z |
| _version_ |
1850065843868663808 |
| fulltext |
ÓÄÊ 621.391:519.2:519.7
À.Í. ÀËÅÊÑÅÉ×ÓÊ, Ë.Â. ÊÎÂÀËÜ×ÓÊ, À.Ñ. ØÅÂÖÎÂ, Ñ.Â. ßÊÎÂËÅÂ
Î ÊÐÈÏÒÎÃÐÀÔÈ×ÅÑÊÈÕ ÑÂÎÉÑÒÂÀÕ ÍÎÂÎÃÎ
ÍÀÖÈÎÍÀËÜÍÎÃÎ ÑÒÀÍÄÀÐÒÀ ØÈÔÐÎÂÀÍÈß ÓÊÐÀÈÍÛ
Àííîòàöèÿ. Èññëåäîâàí ðÿä êðèïòîãðàôè÷åñêèõ ñâîéñòâ áëî÷íîãî øèôðà
«Êàëèíà», ïðèíÿòîãî â êà÷åñòâå íîâîãî íàöèîíàëüíîãî ñòàíäàðòà øèôðîâà-
íèÿ Óêðàèíû. Ïðîàíàëèçèðîâàíû âàæíåéøèå ñâîéñòâà êîìïîíåíò ýòîãî
øèôðà. Ïîêàçàíî, ÷òî åãî ðàóíäîâûå ïðåîáðàçîâàíèÿ ïîðîæäàþò çíàêîïåðå-
ìåííóþ ãðóïïó ïîäñòàíîâîê, à ñàì øèôð ÿâëÿåòñÿ îáîñíîâàííî ñòîéêèì îò-
íîñèòåëüíî ðàçíîñòíîãî è ëèíåéíîãî êðèïòîàíàëèçà.
Êëþ÷åâûå ñëîâà: ñèììåòðè÷íàÿ êðèïòîãðàôèÿ, áëî÷íûé øèôð, êîíå÷íàÿ
ãðóïïà ïîäñòàíîâîê, ðàçíîñòíûé êðèïòîàíàëèç, ëèíåéíûé êðèïòîàíàëèç, íà-
öèîíàëüíûé ñòàíäàðò øèôðîâàíèÿ Óêðàèíû, øèôð «Êàëèíà».
ÂÂÅÄÅÍÈÅ
 2015 ã. â Óêðàèíå ïðèíÿò íîâûé íàöèîíàëüíûé ñòàíäàðò øèôðîâàíèÿ —
áëî÷íûé øèôð «Êàëèíà» [1]. Îñíîâíûå ïðèíöèïû, êîòîðûìè ðóêîâîäñòâîâà-
ëèñü ðàçðàáîò÷èêè øèôðà, èçëîæåíû â ðàáîòå [2], à â [3] îïèñàíà îäíà èç
ïåðâûõ àòàê íà ðåäóöèðîâàííóþ âåðñèþ «Êàëèíû». Â íàñòîÿùåé ñòàòüå ïðåä-
ñòàâëåíû ðåçóëüòàòû èññëåäîâàíèÿ êðèïòîãðàôè÷åñêèõ ñâîéñòâ øèôðà «Êàëè-
íà», îòñóòñòâóþùèå â [2, 3].
Èññëåäîâàíèÿ ïðîâîäèëèñü ïî ñëåäóþùèì íàïðàâëåíèÿì:
— àíàëèç îáùåé ñòðóêòóðû áëî÷íîãî øèôðà (çà èñêëþ÷åíèåì ïðîöåäóðû
ôîðìèðîâàíèÿ ðàóíäîâûõ êëþ÷åé);
— èññëåäîâàíèÿ êðèïòîãðàôè÷åñêèõ ñâîéñòâ îòäåëüíûõ êîìïîíåíò øèôðà
(óçëîâ çàìåíû è ëèíåéíûõ ïðåîáðàçîâàíèé);
— îöåíêà è îáîñíîâàíèå ñòîéêîñòè øèôðà îòíîñèòåëüíî àëãåáðàè÷åñêèõ è
ñòàòèñòè÷åñêèõ ìåòîäîâ êðèïòîàíàëèçà (ðàçíîñòíîãî, ëèíåéíîãî è àëãåáðàè÷åñ-
êèõ àòàê, îñíîâàííûõ íà ãîìîìîðôèçìàõ).
 ðàçä. 1 îïèñàíî SPN-ïðåäñòàâëåíèå øèôðà «Êàëèíà» (ñ òî÷íîñòüþ äî ïðî-
öåäóðû ôîðìèðîâàíèÿ ðàóíäîâûõ êëþ÷åé [1, ï. 7]), êîòîðîå ñëóæèò îñíîâîé
äàëüíåéøèõ èññëåäîâàíèé è ïîçâîëÿåò ïðèìåíÿòü äëÿ àíàëèçà øèôðà èçâåñòíûå
ìåòîäû.  ðàçä. 2 ïðîàíàëèçèðîâàíû êðèïòîãðàôè÷åñêèå ñâîéñòâà èñïîëüçóåìûõ
â «Êàëèíå» óçëîâ çàìåíû è ëèíåéíûõ ïðåîáðàçîâàíèé; ïðèâåäåíû çíà÷åíèÿ ïà-
ðàìåòðîâ, õàðàêòåðèçèðóþùèõ ðàçíîñòíûå, êîððåëÿöèîííûå (ëèíåéíûå) è êîì-
áèíàòîðíûå ñâîéñòâà îòäåëüíûõ êîìïîíåíò øèôðà. Ïîëó÷åííûå ðåçóëüòàòû èñ-
ïîëüçóþòñÿ äàëåå ïðè àíàëèçå è îáîñíîâàíèè ñòîéêîñòè øèôðà îòíîñèòåëüíî
ðÿäà ìåòîäîâ êðèïòîàíàëèçà. Â ðàçä. 3 èññëåäîâàíà ãðóïïà ïîäñòàíîâîê, ïîðîæ-
äåííàÿ ðàóíäîâûìè ïðåîáðàçîâàíèÿìè «Êàëèíû». Áàçèðóÿñü íà ðåçóëüòàòàõ ðà-
áîòû [4], ïîêàçàíî, ÷òî ýòà ãðóïïà ÿâëÿåòñÿ çíàêîïåðåìåííîé äëÿ ëþáîé âåðñèè
øèôðà.  ðàçä. 4 ñôîðìóëèðîâàíà òåîðåìà, ñîäåðæàùàÿ îöåíêè òåîðåòè÷åñêîé
ñòîéêîñòè (provable security) «Êàëèíà»-ïîäîáíûõ áëî÷íûõ øèôðîâ îòíîñèòåëüíî
ðàçíîñòíîãî è ëèíåéíîãî êðèïòîàíàëèçà. Äîêàçàòåëüñòâî òåîðåìû ïðåäñòàâëåíî
â ðàçä. 5, à â çàêëþ÷åíèè ñôîðìóëèðîâàíû êðàòêèå âûâîäû.
1. SPN-ÏÐÅÄÑÒÀÂËÅÍÈÅ ØÈÔÐÀ «ÊÀËÈÍÀ»
Ðàññìîòðèì îáùèé êëàññ áëî÷íûõ øèôðîâ, ê êîòîðîìó îòíîñèòñÿ «Êàëèíà».
Ïðåäâàðèòåëüíî ââåäåì ðÿä îáîçíà÷åíèé.
Äëÿ ëþáîãî íàòóðàëüíîãî m îáîçíà÷èì Vm ìíîæåñòâî äâîè÷íûõ âåêòîðîâ
äëèíû m . Çàôèêñèðóåì íàòóðàëüíûå ÷èñëà t q c r, , , , ïðè ýòîì t q c, , � 2, r � 4,
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
© À.Í. Àëåêñåé÷óê, Ë.Â. Êîâàëü÷óê, À.Ñ. Øåâöîâ, Ñ.Â. ßêîâëåâ, 2016
q t� ��2 11 , è ïîëîæèì p cq� , n pt� . Çàäàäèì íà Vt ñòðóêòóðó ïîëÿ ïîðÿäêà 2 t ,
ñîãëàñîâàííóþ ñ îïåðàöèåé ïîêîîðäèíàòíîãî áóëåâîãî ñëîæåíèÿ äâîè÷íûõ âåê-
òîðîâ. Ïîñëåäíþþ îáîçíà÷èì ñèìâîëîì � (íåçàâèñèìî îò äëèíû âåêòîðîâ-ñëà-
ãàåìûõ x y Vm, � ). Â äàëüíåéøåì áóäåì îòîæäåñòâëÿòü ìíîæåñòâî Vt ñ ïîëåì
GF( )2 t , à ìíîæåñòâî Vmt — ñ m-ìåðíûì âåêòîðíûì ïðîñòðàíñòâîì íàä ýòèì ïî-
ëåì. Ïðîèçâîëüíûé âåêòîð x Vn
t p� � GF( )2 áóäåì çàïèñûâàòü â âèäå
x x xc� ( )1 � , ãäå x x xj j q j� ( ), ,1 � , x Vi j t
t
, ( )� � GF 2 , i q�1, , j c�1, , è íàçû-
âàòü âåêòîðû x xc1 � êîìïîíåíòàìè, à ýëåìåíòû x xq1 1 1, ,, ..., , ...
..., , ...,, ,x xc q c1 — êîîðäèíàòàìè âåêòîðà x .
Çàôèêñèðóåì ñåìåéñòâî ïîäñòàíîâîê s V Vi j t t, :
, i q�1, , j c�1, . Çàäàäèì
ïîäñòàíîâêè s j : V Vtq tq
è s V Vn n:
, ïîëàãàÿ
s x x s x s xj j q j j j q j q j( ) ( ( ), ..., ( )), , , , , ,1 1 1 �� , x Vi j t, � , i q�1, , j c�1, , (1)
s x s x s xc c( ) ( ( ), ..., ( ))� 1 1 , x Vn� . (2)
Äàëåå, çàôèêñèðóåì ïåðåñòàíîâêó g íà ìíîæåñòâå 1 1, ,q c� è ïîëîæèì äëÿ
ëþáîãî x Vn
t p� � GF( )2
� ( ) ( , ..., )( , ) ( , ) ( , ) ( , )g x x x x xg g q g c g q c� 1 1 1 1� � . (3)
Îòîáðàæåíèå �g ÿâëÿåòñÿ ëèíåéíûì ïðåîáðàçîâàíèåì âåêòîðíîãî ïðîñòðàíñòâà
GF( )2 t p , ïåðåñòàâëÿþùèì êîîðäèíàòû xi j, ïðîèçâîëüíîãî âåêòîðà x â ñîîò-
âåòñòâèè ñ ïåðåñòàíîâêîé g, è ìîæåò áûòü çàïèñàíî â âèäå
� ( )g x xG p� , x t p�GF( )2 , (4)
ãäå G p — ïîäñòàíîâî÷íàÿ p p� -ìàòðèöà íàä ïîëåì GF( )2 t . Íàçîâåì ìàòðèöó G p
ñîîòâåòñòâóþùåé ïåðåñòàíîâêå g.
Çàôèêñèðóåì ÌÄÐ-ìàòðèöó D ïîðÿäêà q íàä ïîëåì GF( )2 t , ò.å. òàêóþ
q q� -ìàòðèöó íàä ýòèì ïîëåì, âñå êâàäðàòíûå ïîäìàòðèöû êîòîðîé ÿâëÿþòñÿ íå-
âûðîæäåííûìè. Çàìåòèì, ÷òî íà îñíîâàíèè ïðèâåäåííîãî âûøå óñëîâèÿ
q t� ��2 11 óêàçàííàÿ ìàòðèöà çàâåäîìî ñóùåñòâóåò (ñì. [5] è [6, ñ. 313]).
Íàêîíåö, çàäàäèì íà ìíîæåñòâå Vn áèíàðíóþ îïåðàöèþ �
�
, ïîëàãàÿ äëÿ ëþ-
áûõ x y Vn, �
x y x y x yc c� � � �
�
( , ..., )1 1 ,
ãäå x yj j� — ñóììà ïî ìîäóëþ 2 tq äâîè÷íûõ öåëûõ ÷èñåë, ñîîòâåòñòâóþùèõ
âåêòîðàì x y Vj j tq, � , j c�1, . Îáîçíà÷èì
M G D Dp p
c
� �diag
ðàç
( , ..., )
���
, (5)
�( ) ( )x s x M p� , x t p�GF( )2 , (6)
è ðàññìîòðèì r-ðàóíäîâûé áëî÷íûé øèôð
ñ ìíîæåñòâîì îòêðûòûõ (øèôðî-
âàííûõ) ñîîáùåíèé Vn , ìíîæåñòâîì ðàóíäîâûõ êëþ÷åé K Vn� è ñåìåéñòâîì
øèôðóþùèõ ïðåîáðàçîâàíèé
F f fr k kr� � , ,�� � 1 1
, � � �( )k k Kr
r
1 � , (7)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 17
ãäå äëÿ ëþáûõ x Vn� , k K� , i r�1,
f x x ki k, ( ) ( )� ��
�
, åñëè i �1; (8.1)
f x x ki k, ( ) ( )� �� , åñëè 2 1� � �i r , (8.2)
f x x ki k, ( ) � �
�
, åñëè i r� . (9)
Íàçîâåì îòîáðàæåíèå � âèäà (6) ðàóíäîâîé ôóíêöèåé øèôðà
, à ïîäñòà-
íîâêè si j, (i q�1, , j c�1, ) — óçëàìè çàìåíû (èëè s-áëîêàìè) ýòîãî øèôðà.
Àëãîðèòì «Êàëèíà-l k/ » (ñ òî÷íîñòüþ äî ïðîöåäóðû ôîðìèðîâàíèÿ ðàóí-
äîâûõ êëþ÷åé) îòíîñèòñÿ ê êëàññó áëî÷íûõ øèôðîâ óêàçàííîãî âûøå âèäà.
 òàáë. 1 ïðèâåäåíû çíà÷åíèÿ ïàðàìåòðîâ n p c, , è r äëÿ êàæäîé ïàðû èñõîä-
íûõ çíà÷åíèé l k, , ãäå l — äëèíà áëîêà, à k — äëèíà êëþ÷à øèôðîâàíèÿ [1].
Çàìåòèì, ÷òî ïðè ýòîì t q� � 8 , c ñîâïàäàåò ñ êîëè÷åñòâîì ñòîëáöîâ ìàòðèöû ñî-
ñòîÿíèÿ, à r íà åäèíèöó áîëüøå êîëè÷åñòâà ðàóíäîâ, óêàçàííûõ â òàáë. 1 èç [1].
Êðîìå òîãî, âõîäíîå (âûõîäíîå) ñîîáùåíèå x Vn� â êàæäîì ðàóíäå îòîæäå-
ñòâëÿåòñÿ ñ ìàòðèöåé ñîñòîÿíèÿ (ñì. [1, ï. 4]), ñîñòàâëåííîé èç êîîðäèíàò
xi j, âåêòîðà x. Àíàëîãè÷íûì îáðàçîì ïðåäñòàâëÿþòñÿ ðàóíäîâûå êëþ÷è.
Âî âñåõ âåðñèÿõ øèôðà «Êàëèíà» èñïîëüçóþòñÿ ÷åòûðå ðàçëè÷íûå ïîäñòà-
íîâêè si j, , êîòîðûå îáîçíà÷åíû â [1] ñèìâîëàìè � 0 , �1, � 2 è � 3 ; ïðè ýòîì
si j i, ( )� �� 1 4mod äëÿ ëþáûõ i q�1, , j c�1, . Ïåðåñòàíîâêà g îïðåäåëÿåòñÿ ïî ôîð-
ìóëå g i j i j
i n
c( , ) ,� �
��
��
�
��
�
�
��
�
�
�� �
�
�
�
�
�
�
�
�512
1mod , i q�1, , j c�1, (ñì. [1, ï. 6.4]). Îòîáðàæå-
íèå �g , èñïîëüçóåìîå â øèôðå «Êàëèíà» ñ äëèíîé áëîêà n áèò, èìååò ñëåäóþùèé âèä:
à) ïðè n �128
x x
x x
x x
x x
x x
x x
x
1 1 2 1
1 2 2 2
1 3 2 3
1 4 2 4
1 5 2 5
1 6 2 6
1
, ,
, ,
, ,
, ,
, ,
, ,
, ,
, ,
7 2 7
1 8 2 8
x
x x
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�g
x x
x x
x x
x x
x x
x x
x
1 1 2 1
1 2 2 2
1 3 2 3
1 4 2 4
2 5 1 5
2 6 1 6
2
, ,
, ,
, ,
, ,
, ,
, ,
, ,
, ,
7 1 7
2 8 1 8
x
x x
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
;
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Ò à á ë è ö à 1
Èñõîäíûå çíà÷åíèÿ Çíà÷åíèÿ ïàðàìåòðîâ
l k n p c r
128 128 128 16 2 11
128 256 128 16 2 15
256 256 256 32 4 15
256 512 256 32 4 19
512 512 512 64 8 19
á) ïðè n � 256
x x x x
x x x x
x x x x
x
1 1 2 1 3 1 4 1
1 2 2 2 3 2 4 2
1 3 2 3 3 3 4 3
1
, , , ,
, , , ,
, , , ,
, , , ,
, , , ,
, , , ,
,
4 2 4 3 4 4 4
1 5 2 5 3 5 4 5
1 6 2 6 3 6 4 6
1 7
x x x
x x x x
x x x x
x x x x
x x x x
2 7 3 7 4 7
1 8 2 8 3 8 4 8
, , ,
, , , ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�g
x x x x
x x x x
x x x x
x
1 1 2 1 3 1 4 1
1 2 2 2 3 2 4 2
4 3 1 3 2 3 3 3
4
, , , ,
, , , ,
, , , ,
, , , ,
, , , ,
, , , ,
,
4 1 4 2 4 3 4
3 5 4 5 1 5 2 5
3 6 4 6 1 6 2 6
2 7
x x x
x x x x
x x x x
x x x x
x x x x
3 7 4 7 1 7
2 8 3 8 4 8 1 8
, , ,
, , , ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
;
â) n � 512
x x x x x x x x
x x x x x
1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1
1 2 2 2 3 2 4 2 5
, , , , , , , ,
, , , , , , , ,
, , , , , , , ,
,
2 6 2 7 2 8 2
1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3
1 4
x x x
x x x x x x x x
x x x x x x x x
x x x x x x
2 4 3 4 4 4 5 4 6 4 7 4 8 4
1 5 2 5 3 5 4 5 5 5 6
, , , , , , ,
, , , , , , , ,
, , , , , , , ,
, ,
5 7 5 8 5
1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6
1 7 2 7
x x
x x x x x x x x
x x x x x x x x
x x x x x x x
3 7 4 7 5 7 6 7 7 7 8 7
1 8 2 8 3 8 4 8 5 8 6 8 7
, , , , , ,
, , , , , , , ,8 8 8x
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�g
�
�g
x x x x x x x x
x x x x x
1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1
8 2 1 2 2 2 3 2 4
, , , , , , , ,
, , , , , , , ,
, , , , , , , ,
,
2 5 2 6 2 7 2
7 3 8 3 1 3 2 3 3 3 4 3 5 3 6 3
6 4
x x x
x x x x x x x x
x x x x x x x x
x x x x x x
7 4 8 4 1 4 2 4 3 4 4 4 5 4
5 5 6 5 7 5 8 5 1 5 2
, , , , , , ,
, , , , , , , ,
, , , , , , , ,
, ,
5 3 5 4 5
4 6 5 6 6 6 7 6 8 6 1 6 2 6 3 6
3 7 4 7
x x
x x x x x x x x
x x x x x x x x
x x x x x x x
5 7 6 7 7 7 8 7 1 7 2 7
2 8 3 8 4 8 5 8 6 8 7 8 8
, , , , , ,
, , , , , , , ,8 1 8x
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Èñïîëüçóÿ äàííóþ èíôîðìàöèþ, à òàêæå ôîðìóëû (3), (4), íåòðóäíî óáå-
äèòüñÿ â òîì, ÷òî ïåðâîé èç òðåõ ïåðåñòàíîâîê (n �128) ñîîòâåòñòâóåò ìàòðèöà
G
I
I
I
I
16
0 0 0
0 0 0
0 0 0
0 0 0
�
�
�
�
�
��
�
�
�
�
��
,
ãäå I è 0 — ñîîòâåòñòâåííî åäèíè÷íàÿ è íóëåâàÿ ìàòðèöû ÷åòâåðòîãî ïîðÿäêà
íàä ïîëåì GF( )28 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 19
Âòîðîé ïåðåñòàíîâêå (n � 256) ñîîòâåòñòâóåò ìàòðèöà
G
I
I
I
32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
�
0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
I
I
I
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0
I
I
I
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0
I
I
I
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
I
I
I
0 0 0 0 0 0 0 0 0I
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Çäåñü I è 0 — ñîîòâåòñòâåííî åäèíè÷íàÿ è íóëåâàÿ ìàòðèöû âòîðîãî ïîðÿäêà
íàä ïîëåì GF( )28 .
Òðåòüåé ïåðåñòàíîâêå (n � 512) ñîîòâåòñòâóåò öèðêóëÿíòíàÿ ìàòðèöà G64
ïîðÿäêà 64 íàä ïîëåì GF( )2 , ïåðâûé ñòîëáåö êîòîðîé ðàâåí ( , , ... , )1 0 0 T , à êàæäûé
ñëåäóþùèé ñòîëáåö îáðàçóåòñÿ ïðè öèêëè÷åñêîì ñäâèãå ïðåäûäóùåãî íà ñåìü
ïîçèöèé ââåðõ.
Âî âñåõ âåðñèÿõ «Êàëèíû» èñïîëüçóåòñÿ îäíà è òà æå ÌÄÐ-ìàòðèöà D ïî-
ðÿäêà 8 íàä ïîëåì GF( )28 , êîòîðàÿ ÿâëÿåòñÿ òðàíñïîíèðîâàííîé ê ìàòðèöå, ïðè-
âåäåííîé â [1, ï. 5.5].
Òàêèì îáðàçîì, øèôð «Êàëèíà» îòíîñèòñÿ ê êëàññó Rijndael-ïîäîáíûõ áëî÷-
íûõ øèôðîâ, îäíàêî çàìåòíî îòëè÷àåòñÿ îò øèôðà Rijndael.  ÷àñòíîñòè, â øèô-
ðå «Êàëèíà» ïðèìåíÿþòñÿ:
— îðèãèíàëüíàÿ ïðîöåäóðà ôîðìèðîâàíèÿ ðàóíäîâûõ êëþ÷åé [1, ï. 7];
— ïðîöåäóðà «îòáåëèâàíèÿ» ñ ïîìîùüþ àëãåáðàè÷åñêîé îïåðàöèè �
�
;
— óçëû çàìåíû � 0 , �1, � 2 , � 3 , âûáðàííûå â ñîîòâåòñòâèè ñ îïðåäåëåííûìè
êðèòåðèÿìè [2].
2. ÊÐÈÏÒÎÃÐÀÔÈ×ÅÑÊÈÅ ÑÂÎÉÑÒÂÀ È ÏÀÐÀÌÅÒÐÛ
ÎÒÄÅËÜÍÛÕ ÊÎÌÏÎÍÅÍÒ ØÈÔÐÀ «ÊÀËÈÍÀ»
Çíà÷åíèÿ ïàðàìåòðîâ, õàðàêòåðèçóþùèõ ðàçíîñòíûå è êîððåëÿöèîííûå
ñâîéñòâà óçëîâ çàìåíû. Äëÿ ëþáîé ïîäñòàíîâêè � íà ìíîæåñòâå Vt îáîçíà÷èì
d d Vt� �� �( ) ( )max{ ( , ): , \ { }}� � � � � � 0 , d d Vt� �� �( ) ( )max{ ( , ): , \ { }}� � � � � � 0 , (10)
l l Vt� �� �( ) ( )max { ( , ): , \ { }}� � � � � � 0 , (11)
l l Vt� �� �( ) ( )max{ ( , ): , \ { }}� � � � � � 0 , � �( ) ( )max{ ( , ): , \ { }}� � � � � �� �Vt 0 , (12)
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
ãäå
d k kt
k Vt
�
�
�
� � ��( ) ( , ) ( ( ) ( ), )� � � � � � � �2 , (13)
d k kt
k Vt
�
�
�
� � ��( ) ( , ) ( ( ) ( ), )� � � � � � � �2 , (14)
l t t x x k
x Vk V tt
�
� � � �
��
� ���( ) ( )( , ) ( ( ) )� � ��� � 2 2 1 2 , (15)
l t t x x k
x Vk V tt
�
� � � �
��
� ���( ) ( )( , ) ( ( ) )� � ��� � 2 2 1 2 , (16)
�( ) ( , )� � � � �
�
�
�
�
�
�
�
� � � �
� ��
��2 2 1
0 1
t t x x k
x V x k aa t
( ) ( )
: ( , ){ , }
� ��
��
�
�
�
�
�
�
�
�
2
k Vt
. (17)
Ñèìâîëû � è � â ôîðìóëàõ (10)–(17) îáîçíà÷àþò îïåðàöèè ïîêîîðäèíàòíîãî
áóëåâîãî ñëîæåíèÿ äâîè÷íûõ âåêòîðîâ äëèíû t è ñëîæåíèÿ ïî ìîäóëþ 2 t
äâîè÷íûõ öåëûõ ÷èñåë, ñîîòâåòñòâóþùèõ ýòèì âåêòîðàì. Ïîä îáîçíà÷åíèåì
�( , )x k â ôîðìóëå (17) ïîíèìàåì áèò ïåðåíîñà â t-é ðàçðÿä ïðè ñëîæåíèè
(â êîëüöå Z) öåëûõ ÷èñåë, ñîîòâåòñòâóþùèõ âåêòîðàì x k Vt, � .
Ïàðàìåòðû (10) õàðàêòåðèçóþò ðàçíîñòíûå ñâîéñòâà ïîäñòàíîâêè � îòíîñè-
òåëüíî îïåðàöèé � , � , à ïàðàìåòðû (11), (12) — åå êîððåëÿöèîííûå (ëèíåéíûå)
ñâîéñòâà îòíîñèòåëüíî ýòèõ îïåðàöèé. Ìàòðèöû ðàçìåðà ( ) ( )2 1 2 1t t� � � , ñîñòîÿ-
ùèå èç ýëåìåíòîâ (13) è (15), ãäå � è � ïðîáåãàþò âñå íåíóëåâûå ýëåìåíòû ìíî-
æåñòâàVt , íàçûâàþòñÿ òàáëèöåé ðàçíîñòåé è òàáëèöåé ëèíåéíûõ àïïðîêñèìàöèé
ïîäñòàíîâêè � ñîîòâåòñòâåííî. Ïðè ýòîì ðàñøèðåííûå òàáëèöà ðàçíîñòåé è òàá-
ëèöà ëèíåéíûõ àïïðîêñèìàöèé ïîäñòàíîâêè � ñîñòîÿò ñîîòâåòñòâåííî èç
ýëåìåíòîâ (13) è (15) äëÿ âñåõ � �, �Vt .
Îòìåòèì, ÷òî âåêòîð � �Vt íàçûâàåòñÿ ëèíåéíûì òðàíñëÿòîðîì ôóíêöèè
f Vt: { , }
0 1 , åñëè äëÿ ëþáîãî x Vt� âûïîëíÿåòñÿ ðàâåíñòâî f x f x( ) ( )� �� .
Ñîãëàñíî îïðåäåëåíèþ [7] ïîäñòàíîâêà � èìååò òðèâèàëüíóþ ëèíåéíóþ ñòðóê-
òóðó, åñëè äëÿ êàæäîé íåíóëåâîé ëèíåéíîé êîìáèíàöèè åå êîîðäèíàòíûõ
ôóíêöèé íå ñóùåñòâóåò íåíóëåâûõ ëèíåéíûõ òðàíñëÿòîðîâ. Èçâåñòíî [8], ÷òî
äëÿ òðèâèàëüíîñòè ëèíåéíîé ñòðóêòóðû ïîäñòàíîâêè �: V Vt t
äîñòàòî÷íî âû-
ïîëíåíèÿ óñëîâèÿ NW t( )� � �2 1, ãäå NW ( )� — ìàêñèìàëüíîå êîëè÷åñòâî íóëå-
âûõ ýëåìåíòîâ â ñòîëáöàõ òàáëèöû ëèíåéíûõ àïïðîêñèìàöèé ýòîé ïîäñòàíîâêè.
 òàáë. 2 ïðèâåäåíû çíà÷åíèÿ ïàðàìåòðîâ (10)–(12) äëÿ óçëîâ çàìåíû øèôðà
«Êàëèíà». Ïðè ýòîì NW NW NW NW
( ) ( ) ( ) ( )
, , , .
� � � �0 1 2 337 33 36 35� � � �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 21
Ò à á ë è ö à 2
Ïîäñòàíîâêà
�
Çíà÷åíèÿ ïàðàìåòðîâ
d�
( )�
d�
( )�
l�
( )�
l�
( )� �( )�
�0 2 5� 6 2 8� � 9 2 8� � 9 2 8� � 0,035415
�1 2 5� 7 2 8� � 9 2 8� � 1936 2 16� � 0,029541
�2 2 5� 7 2 8� � 9 2 8� � 1936 2 16� � 0,029573
�3 2 5� 7 2 8� � 9 2 8� � 1600 2 16� � 0,025883
Òàêèì îáðàçîì, âñå óçëû çàìåíû èìåþò òðèâèàëüíóþ ëèíåéíóþ ñòðóêòóðó è
ïðèåìëåìûå ðàçíîñòíûå è ëèíåéíûå ñâîéñòâà.  ÷àñòíîñòè, ìàêñèìàëüíûå çíà-
÷åíèÿ ýëåìåíòîâ òàáëèö ðàçíîñòåé è òàáëèö ëèíåéíûõ àïïðîêñèìàöèé óçëîâ çà-
ìåíû íå ïðåâûøàþò 2 5� è 9 2 8� � ñîîòâåòñòâåííî.
Âïîëíåíåðàçëîæèìîñòü òàáëèö ðàçíîñòåé óçëîâ çàìåíû øèôðà «Êàëèíà».
Íàïîìíèì (ñì., íàïðèìåð, [9, ñ. 353]), ÷òî íåîòðèöàòåëüíàÿ ìàòðèöà P ïîðÿäêà n íà-
çûâàåòñÿ íåðàçëîæèìîé, åñëè íå ñóùåñòâóåò ïîäñòàíîâî÷íîé ìàòðèöû � òàêîé, ÷òî
� �P
P
P P
� � �
�
�
�
�
�1 1
2 3
0
,
ãäå P1 — êâàäðàòíàÿ ìàòðèöà ïîðÿäêà, ìåíüøåãî n . Ìàòðèöà P íàçûâàåòñÿ
âïîëíå íåðàçëîæèìîé, åñëè íå ñóùåñòâóåò ïîäñòàíîâî÷íûõ ìàòðèö �1 è �2
òàêèõ, ÷òî
� �1 2
1
2 3
P
P
P P
� �
�
�
�
�
�
0
,
ãäå P1 — êâàäðàòíàÿ ìàòðèöà ïîðÿäêà, ìåíüøåãî n . Èçâåñòíî [9], ÷òî äâàæäû
ñòîõàñòè÷åñêàÿ ìàòðèöà P âïîëíå íåðàçëîæèìà òîãäà è òîëüêî òîãäà, êîãäà
íåðàçëîæèìà ìàòðèöà P P� T . Êðîìå òîãî, ïîëîæèòåëüíàÿ êâàäðàòíàÿ ìàòðèöà
ÿâëÿåòñÿ âïîëíå íåðàçëîæèìîé.
Äëÿ êàæäîé ïîäñòàíîâêè � � � � ��{ , , , }0 1 2 3 îáîçíà÷èì
D d Vt
( ) ( )
, \{ }( ( , ))� �
� �� �� � � 0 òàáëèöó ðàçíîñòåé ïîäñòàíîâêè � (ñì. ôîðìó-
ëó (13)). Ñëåäóþùåå óòâåðæäåíèå äîêàçûâàåòñÿ íåïîñðåäñòâåííîé ïðîâåðêîé.
Óòâåðæäåíèå 1. Âñå ìàòðèöû
~
( )
( ) ( ) ( )
D D Di i i� � �� � T , i�0 3, , ÿâëÿþòñÿ ïî-
ëîæèòåëüíûìè.  ÷àñòíîñòè, òàáëèöà ðàçíîñòåé êàæäîãî óçëà çàìåíû øèôðà
«Êàëèíà» ÿâëÿåòñÿ âïîëíå íåðàçëîæèìîé ìàòðèöåé.
Çàìåòèì, ÷òî ïîëîæèòåëüíîñòü ìàòðèöû
~ ( )
D i�
ðàâíîñèëüíà ñóùåñòâîâàíèþ
äëÿ ëþáûõ u u Vt1 2 1 2, , , � , ãäå u u1 2 1 2� �, , òàêèõ k k k Vt, ,� �� � , ÷òî
� � i iu k k k( ) ( )1 1� � � � � �� , � � i iu k k k( ) ( )2 2� � � � � �� , i�0 3, . Ýòîò ôàêò
ñâèäåòåëüñòâóåò î õîðîøèõ ïåðåìåøèâàþùèõ ñâîéñòâàõ óçëîâ çàìåíû (â ñìûñëå
ðàáîòû [4]) è èñïîëüçóåòñÿ íèæå ïðè èññëåäîâàíèè ãðóïïû ïîäñòàíîâîê, ïîðîæ-
äåííîé ðàóíäîâûìè ïðåîáðàçîâàíèÿìè øèôðà «Êàëèíà».
Ñâîéñòâà ëèíåéíûõ ïðåîáðàçîâàíèé, èñïîëüçóåìûõ â øèôðå «Êàëèíà».
Äëÿ ëþáîãî íàòóðàëüíîãî m è ïðîèçâîëüíîãî âåêòîðà z z z m t m� �( , , ) ( )( ) ( )1 2� GF
îáîçíà÷èì wt z( ) âåñ âåêòîðà z:
wt z i m z i( ) # { , : }( )� � �1 0 .
Èíäåêñ âåòâëåíèÿ (branch number) m m� -ìàòðèöû M íàä ïîëåì GF( )2 t îïðå-
äåëÿåòñÿ ïî ôîðìóëå [5]
B wt z wt zM zM
t m� � �min{ ( ) ( ): ( ) \ { }}GF 2 0 .
Äëÿ ëþáîãî âåêòîðà x x xc� ( )1 � , ãäå x x xj j q j� ( ), ,1 � , x Vi j t, � , i q�1, ,
j c�1, , è ïðîèçâîëüíîé ìàòðèöû L ïîðÿäêà p íàä ïîëåì GF( )2 t îáîçíà÷èì
Wt x j c x j( ) # { , : }� � �1 0 , � � � �B Wt x Wt xL xL
t pmin{ ( ) ( ): ( ) \ { }}GF 2 0 .
×èñëà Wt x( ) è �BL íàçîâåì ðàñøèðåííûì âåñîì âåêòîðà x è ðàñøèðåííûì èí-
äåêñîì âåòâëåíèÿ ìàòðèöû L ñîîòâåòñòâåííî.
Ðàññìîòðèì ëèíåéíîå ïðåîáðàçîâàíèå �g è ìàòðèöó M p íàä ïîëåì GF( )2 t ,
îïðåäåëåííûå ïî ôîðìóëàì (3) è (5) ñîîòâåòñòâåííî, è ïîëîæèì �( ) � ( )x g xM p� ,
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
x Vn� . Èç (3)–(5) âûòåêàåò, ÷òî �( )x xLp� , x Vn� , ãäå
L G D D Gp p
c
p� � �diag
ðàç
( , ..., )
���
. (18)
Îòìåòèì (ñì., íàïðèìåð, [5]), ÷òî ïîñêîëüêó D ÿâëÿåòñÿ ÌÄÐ-ìàòðèöåé ïîðÿä-
êà q íàä ïîëåì GF( )2 t , òî
B B qD D
� � �T 1 . (19)
Óòâåðæäåíèå 2. Ïóñòü q c�
, g i j i j c ci( , ) ( , ( ) )� � �mod 1 , i q�1, , j c�1, ,
ïðè÷åì â íàáîðå ( , , )c cq1 � êàæäûé ýëåìåíò 0 1 1, , ..., c� ïîâòîðÿåòñÿ ðîâíî
ðàç.
Òîãäà ðàñøèðåííûé èíäåêñ âåòâëåíèÿ êàæäîé èç ìàòðèö Lp , Lp
T ðàâåí c�1 .
Äîêàçàòåëüñòâî. Èç óñëîâèÿ óòâåðæäåíèÿ è îïðåäåëåíèÿ ôóíêöèé wt è Wt
âûòåêàåò, ÷òî äëÿ ëþáûõ x Vn� , j c�1, ñïðàâåäëèâû ñëåäóþùèå íåðàâåíñòâà:
Wt x wt g x j( ) ( � ( ) )� �
1, Wt g x wt x j( � ( )) ( )� �
1 . (20)
Ïóñòü x Vn� \ { }0 ; òîãäà ñóùåñòâóåò j c�1, òàêîå, ÷òî � ( )g x j � 0 . Îòñþäà, ïî-
ñëåäîâàòåëüíî èñïîëüçóÿ ôîðìóëû (20), (4), (5), (19), ïîëó÷àåì
Wt x Wt xL Wt x Wt g xM wt g x wt xMp p j( ) ( ) ( ) ( � ( )) ( ( � ( ) ) ((� � � � � p j) ))
� �1
� � � � �� � �( ( � ( ) ) ( � ( ) )) ( )wt g x wt g x D B qj j D
1 1 11 .
Èòàê,
� � � � ��B cq q cLp
� 1 1 1( ) . (21)
Äàëåå, ïî óñëîâèþ óòâåðæäåíèÿ ñóùåñòâóåò i q�1, òàêîå, ÷òî ci � 0 . Ðàññìîòðèì
âåêòîð x Vn� ñ åäèíñòâåííîé íåíóëåâîé êîîðäèíàòîé xi ,1 . Òîãäà � ( )g x x� è ñîãëàñ-
íî (19) wt xM wt g x D wt x D qp(( ) ) ( � ( ) ) ( )1 1 1� � � , ò.å. âñå êîîðäèíàòû âåêòîðà
( )xM p 1 ÿâëÿþòñÿ íåíóëåâûìè. Îòñþäà ñ ó÷åòîì îïðåäåëåíèÿ ïåðåñòàíîâêè g ïîëó-
÷èì Wt g xM cp( � ( )) � . Èòàê, Wt x Wt xL Wt x Wt g xM cp p( ) ( ) ( ) ( � ( ))� � � � �1 è, ñëåäîâà-
òåëüíî, íà îñíîâàíèè (21) èìååì � � �B cLp
1.
Ðàâåíñòâî � � �B c
Lp
T 1 äîêàçûâàåòñÿ àíàëîãè÷íî. Óòâåðæäåíèå äîêàçàíî.
Çàìåòèì, ÷òî êàæäàÿ èç òðåõ ïåðåñòàíîâîê g , èñïîëüçóåìûõ â «Êàëèíå»
(ñì. ðàçä. 1), óäîâëåòâîðÿåò óñëîâèþ óòâåðæäåíèÿ 2. Îòñþäà âûòåêàåò
ñëåäóþùèé ðåçóëüòàò.
Ñëåäñòâèå 1. Ïóñòü Lp — ìàòðèöà âèäà (18), èñïîëüçóåìàÿ â øèôðå «Êàëè-
íà» ñ äëèíîé áëîêà n áèò. Òîãäà
� � � �
� �
� �B B
p n
p nL Lp p
T
åñëè
åñëè
å
3 16 128
5 32 256
9
, ( );
, ( );
, ñëè p n� �
!
"
#
$# 64 512( ).
Îòìåòèì òàêæå âàæíîå êîìáèíàòîðíîå ñâîéñòâî ìàòðèö (5), èñïîëüçóåìûõ â
øèôðå «Êàëèíà».
Íàïîìíèì, ÷òî íåîòðèöàòåëüíàÿ êâàäðàòíàÿ ìàòðèöà P íàçûâàåòñÿ ïðèìè-
òèâíîé, åñëè ñóùåñòâóåò íàòóðàëüíîå ÷èñëî l òàêîå, ÷òî P l % 0 (ò.å. âñå ýëåìåíòû
ïîñëåäíåé ìàòðèöû ÿâëÿþòñÿ ïîëîæèòåëüíûìè ÷èñëàìè). Íàèìåíüøåå íàòóðàëü-
íîå ÷èñëî l ñ óêàçàííûì ñâîéñòâîì íàçûâàåòñÿ ýêñïîíåíòîé ìàòðèöû P
[10, ñ. 392]. Íîñèòåëü ïðîèçâîëüíîé ìàòðèöû M mij� ( ) íàä ïðîèçâîëüíûì ïîëåì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 23
îïðåäåëÿåòñÿ êàê íåîòðèöàòåëüíàÿ ìàòðèöà N M( ) ñ ýëåìåíòàìè
n
m
ij
ij�
�!
"
$
1 0
0
, ;åñëè
Ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ ïðîâåðÿåòñÿ íåïîñðåäñòâåííî.
Óòâåðæäåíèå 3. Äëÿ ëþáîãî p�{ , , }16 32 64 íîñèòåëü ìàòðèöû M p ÿâëÿåòñÿ
ïðèìèòèâíîé ìàòðèöåé, ýêñïîíåíòà êîòîðîé ðàâíà äâóì.
Ïîñëåäíèå äâà óòâåðæäåíèÿ èñïîëüçóþòñÿ íèæå ïðè îáîñíîâàíèè ñòîéêîñòè
øèôðà «Êàëèíà» îòíîñèòåëüíî ðÿäà àëãåáðàè÷åñêèõ è ñòàòèñòè÷åñêèõ àòàê.
3. ÃÐÓÏÏÀ, ÏÎÐÎÆÄÅÍÍÀß ÐÀÓÍÄÎÂÛÌÈ ÏÐÅÎÁÐÀÇÎÂÀÍÈßÌÈ
ØÈÔÐÀ «ÊÀËÈÍÀ»
Ðàññìîòðèì ïðîèçâîëüíûé áëî÷íûé øèôð
, çàäàííûé ñîîòíîøåíèÿ-
ìè (1)–(9), è îáîçíà÷èì G f i r k Vi k n
� � � �& ', : , ,2 1 ãðóïïó ïîäñòàíîâîê, ïî-
ðîæäåííóþ ðàóíäîâûìè ïðåîáðàçîâàíèÿìè ýòîãî øèôðà â ðàóíäàõ ñ íîìåðà-
ìè 2 3 1, , ..., r � .
 [4] ïîëó÷åíû äîñòàòî÷íûå óñëîâèÿ, ïðè êîòîðûõ G
ÿâëÿåòñÿ çíàêîïåðå-
ìåííîé ãðóïïîé ïîäñòàíîâîê íà ìíîæåñòâå Vn .
Òåîðåìà 1 [4]. Ïóñòü âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
à) íîñèòåëü ìàòðèöû M p ÿâëÿåòñÿ ïðèìèòèâíîé ìàòðèöåé;
á) äëÿ ëþáûõ i q�1, , j c�1, ãðóïïà ïîäñòàíîâîê
G s s Vi j i j t( ) : ,, ,
,� �& '� � � � ,
ãäå s x s s xi j i j i j,
,
, ,( ) ( ( ) )
� � � �� � ��1 , x Vt� , ÿâëÿåòñÿ 2-òðàíçèòèâíîé è ñðåäè ýëå-
ìåíòîâ ýòèõ ãðóïï åñòü ïîäñòàíîâêà � òàêàÿ, ÷òî # { : ( ) }k V k kt� � (�
({ , , , ..., }0 2 2 20 1 t ;
â) ñïðàâåäëèâî íåðàâåíñòâî 2 2 1 2 2 21 1pt t p t t� � � �� �( ) ( ) .
Òîãäà ãðóïïà G
ñîñòîèò èç âñåõ ÷åòíûõ ïîäñòàíîâîê íà ìíîæåñòâå Vn .
Óòâåðæäåíèå 4. Êàæäàÿ âåðñèÿ øèôðà «Êàëèíà» óäîâëåòâîðÿåò óñëîâè-
ÿì à)–â) òåîðåìû 1.
Äîêàçàòåëüñòâî. Ñïðàâåäëèâîñòü óñëîâèÿ à) âûòåêàåò èç óòâåðæäåíèÿ 3,
à âûïîëíåíèå óñëîâèÿ â) ïðîâåðÿåòñÿ íåïîñðåäñòâåííî. Äàëåå, ñîãëàñíî òåîðå-
ìå 3 â [4] 2-òðàíçèòèâíîñòü ãðóïïû G si j( ), ðàâíîñèëüíà íåðàçëîæèìîñòè ìàòðè-
öû
~
( )
( ) ( ) ( ), , ,D D D
s s si j i j i j� � T , ãäå D
si j( ), — òàáëèöà ðàçíîñòåé ïîäñòàíîâêè si j, ,
i q�1, , j c�1, .
Ñëåäîâàòåëüíî, ñïðàâåäëèâîñòü ïåðâîé ÷àñòè óñëîâèÿ á) âûòåêàåò èç óòâåð-
æäåíèÿ 1.
Íàêîíåö, â òàáëèöå ðàçíîñòåé óçëà çàìåíû � 0 øèôðà «Êàëèíà» èìåþòñÿ
ýëåìåíòû d�
( )
( , )
�
� �0 , ðàâíûå 2 68� � . Ñëåäîâàòåëüíî, äëÿ ïîäñòàíîâêè � � � ��
0
,
âûïîëíÿþòñÿ ñîîòíîøåíèÿ
6 28
0 0
0
8
� � � � ��
�
�d k k
k V
( )
( , ) ( ( ) ( ), )
�
� � � � � � �
� � � (# { : ( ) } { , , , ..., }k V k kt � 0 2 2 20 1 8 ,
èç êîòîðûõ âûòåêàåò ñïðàâåäëèâîñòü âòîðîé ÷àñòè óñëîâèÿ á) òåîðåìû 1.
Óòâåðæäåíèå äîêàçàíî.
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
â ïðîòèâíîì ñëó÷àå.
Òàêèì îáðàçîì, ãðóïïà ïîäñòàíîâîê, ïîðîæäåííàÿ ðàóíäîâûìè ïðåîáðàçî-
âàíèÿìè øèôðà «Êàëèíà» ñ äëèíîé áëîêà n�{ , , }128 256 512 , ÿâëÿåòñÿ çíàêîïåðå-
ìåííîé íà ìíîæåñòâå Vn . Óêàçàííûé ôàêò ñâèäåòåëüñòâóåò î ñòîéêîñòè øèôðà
îòíîñèòåëüíî àëãåáðàè÷åñêèõ àòàê, îñíîâàííûõ íà ãîìîìîðôèçìàõ, à òàêæå î åãî
àñèìïòîòè÷åñêîé (ñ ðîñòîì ÷èñëà ðàóíäîâ r) ñòîéêîñòè îòíîñèòåëüíî ðÿäà
ñòàòèñòè÷åñêèõ àòàê [11–14].
4. ÎÖÅÍÊÈ ÑÒÎÉÊÎÑÒÈ ØÈÐÔÀ «ÊÀËÈÍÀ» ÎÒÍÎÑÈÒÅËÜÍÎ ÐÀÇÍÎÑÒÍÎÃÎ
È ËÈÍÅÉÍÎÃÎ ÊÐÈÏÒÎÀÍÀËÈÇÀ
Äëÿ ëþáîãî êîíå÷íîãî ñåìåéñòâà ïîäñòàíîâîê )� �( : )� k k K íà ìíîæåñòâå Vn ,
ïðîèçâîëüíûõ áèíàðíûõ îïåðàöèé � , * íà Vn è äëÿ âåêòîðîâ � �, �Vn îáîçíà÷èì
d K x xn
k k
x Vk K n
� �,
( ) ( , ) | | ( ( ), ( ) )*
� �
��
� *��) � � � � � � �2 1 ,
l K n x x
x Vk K
k
n
( ) ( )
( , ) | | ( )) � � � ��� �
�
�
�
�
�
�
�
�
� � �
��
��1
2
2 1 .
Äëÿ çàäàííîãî âûøå øèôðà
ïîëîæèì
� �i i k nf k V( : ), ,
� � � �
[ , ] , ,( : ( ) )i j i k j k i j n
j if f k k V
i j
�� � �
1 , 1� � �i j r .
Èç ôîðìóëû (7) âûòåêàåò, ÷òî
ÿâëÿåòñÿ ïðîèçâåäåíèåì øèôðîâ
1, ,� r ,
ïðè÷åì ñîãëàñíî ôîðìóëå (8)
�[ , ]2 1r ÿâëÿåòñÿ ìàðêîâñêèì (îòíîñèòåëüíî îïå-
ðàöèè �) SPN-øèôðîì.
Ñëåäóþùèå óòâåðæäåíèÿ äîêàçûâàþòñÿ íåïîñðåäñòâåííîé ïðîâåðêîé.
Óòâåðæäåíèå 5. Ïóñòü ñèìâîë � îáîçíà÷àåò ïðîèçâîëüíóþ áèíàðíóþ îïåðà-
öèþ íà ìíîæåñòâåVn . Òîãäà äëÿ ëþáûõ � �, �Vn ñïðàâåäëèâî ðàâåíñòâî
d d dr r
� �,
( )
,
( )
,
( )[ , ] [ , ]( , ) ( , ) ( ,�
�
� �
� ��1 1 1 2 1� � � � � �
�
)
�
�
Vn
.
 ÷àñòíîñòè,
max { ( , )} max {
, \{ } ,
( )
, \{ }
[ , ]
� � � �
� �
� �
�
� �
V Vn
r
n
d d
0 0
1 1
� � �
�
,
( )[ , ] ( , )}2 1r � � . (22)
Óòâåðæäåíèå 6. Äëÿ ëþáûõ � �, �Vn ñïðàâåäëèâî ðàâåíñòâî
l l l r
n
n
V
V
( ) ( ) ( )
,
( , ) ( , ) ( , )[ , ]
�
�
� �� � � � � �
�
�
1 2 2
1
2
1 1 2�
�l r r( )[ , ] ( , )2
2� � .
 ÷àñòíîñòè,
max { ( , )} max {
, \{ }
( )
, \{ }
( )[ , ]
� � � �
� �
�
�
� �
V Vn n
rl l
0 0
2 2 ( , )}� � . (23)
Îòìåòèì, ÷òî ïàðàìåòðû â ëåâûõ ÷àñòÿõ íåðàâåíñòâ (22) è (23) ñîâïàäàþò
ñîîòâåòñòâåííî ñ ìàêñèìàëüíûìè çíà÷åíèÿìè âåðîÿòíîñòåé ( )r �1 -ðàóíäîâûõ
äèôôåðåíöèàëîâ è r-ðàóíäîâûõ ëèíåéíûõ àïïðîêñèìàöèé øèôðà
(îáû÷íî ïîä
îïåðàöèåé � ïîäðàçóìåâàþò îïåðàöèþ �). Óêàçàííûå ïàðàìåòðû ÿâëÿþòñÿ ñòàí-
äàðòíûìè ïîêàçàòåëÿìè òåîðåòè÷åñêîé ñòîéêîñòè (provable security) áëî÷íûõ
øèôðîâ îòíîñèòåëüíî ðàçíîñòíîãî è ñîîòâåòñòâåííî ëèíåéíîãî êðèïòîàíàëèçà.
Òàêèì îáðàçîì, ñîîòíîøåíèÿ (22), (23) ïîçâîëÿþò ïðèìåíÿòü äëÿ îöåíêè ñòîé-
êîñòè øèôðà
îòíîñèòåëüíî óêàçàííûõ ìåòîäîâ êðèïòîàíàëèçà èçâåñòíûå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 25
ðåçóëüòàòû, ïîëó÷åííûå äëÿ ìàðêîâñêèõ SPN-øèôðîâ.  ÷àñòíîñòè, ñïðàâåäëèâà
ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Ïóñòü
— r-ðàóíäîâûé áëî÷íûé øèôð, çàäàííûé ñîîòíîøåíèÿ-
ìè (1)–(9), ãäå ïåðåñòàíîâêà g óäîâëåòâîðÿåò óñëîâèþ óòâåðæäåíèÿ 2. Îáîçíà÷èì
d d i q j c
si j
� �� � �max{ : , , , }
( ), 1 1 , l l i q j c
si j
� �� � �max{ : , , , }
( ), 1 1
ñîîòâåòñòâåííî ìàêñèìàëüíûå çíà÷åíèÿ ýëåìåíòîâ òàáëèö ðàçíîñòåé è òàáëèö
ëèíåéíûõ àïïðîêñèìàöèé âñåõ óçëîâ çàìåíû øèôðà
(ñì. (10), (11)). Òîãäà
ïðè r � 6 äëÿ ëþáîé áèíàðíîé îïåðàöèè � íà ìíîæåñòâå Vn ñïðàâåäëèâî íåðà-
âåíñòâî
max { ( , )}
, \{ } ,
( )[ , ]
� �
� �
� �
�
� �
V
cq
n
rd d
0
1 1
�
. (24)
Êðîìå òîãî, ïðè r � 7 ñïðàâåäëèâî íåðàâåíñòâî
max { ( , )}
, \{ }
( )
� �
� �
�
��
V
cq
n
l l
0
. (25)
Äîêàçàòåëüñòâî òåîðåìû ïðèâåäåíî â ðàçä. 5.
Íåïîñðåäñòâåííî èç òåîðåìû 2 è äàííûõ òàáë. 2 ïîëó÷àåì ñëåäóþùèé
ðåçóëüòàò.
Ñëåäñòâèå 2. Ïóñòü
ÿâëÿåòñÿ øèôðîì «Êàëèíà» ñ äëèíîé áëîêà n áèò è r
ðàóíäàìè øèôðîâàíèÿ. Òîãäà ïðè r � 6 äëÿ ëþáîé áèíàðíîé îïåðàöèè � íà ìíî-
æåñòâå Vn âûïîëíÿåòñÿ íåðàâåíñòâî
max { ( , )}
, ;
, \{ } ,
( )[ , ]
� �
� �
� �
�
� �
�
Vn
rd
n
0
80
1 1
2 128
�
åñëè
2 256
2 512
160
320
�
�
�
�
!
"
#
$
#
, ;
, .
åñëè
åñëè
n
n
(26)
Êðîìå òîãî, ïðè r � 7 âûïîëíÿåòñÿ íåðàâåíñòâî
max { ( , )}
, ,
, \{ }
( )
� �
� �
�
� �
�
� + �
Vn
l
n
0
16 128 789 2 165 2 åñëè �
� + � �
� +
� �
�
128
9 2 135 2 256
9 2 183
32 256 155
64 512
;
, , ;
,
åñëè n
� �
!
"
#
$
# �2 512310 , .åñëè n
(27)
Èòàê, íà îñíîâàíèè íåðàâåíñòâ (26) è (27) äëÿ ïðîâåäåíèÿ êëàññè÷åñêîé ðàç-
íîñòíîé (ëèíåéíîé) àòàêè íà ëþáóþ âåðñèþ «Êàëèíû» íåîáõîäèìî çàøèôðîâàòü
íå ìåíåå ÷åì 280 (278) îòêðûòûõ ñîîáùåíèé. Òàêèì îáðàçîì, óñïåøíîå ïðèìåíå-
íèå ê ýòîìó øèôðó ðàçíîñòíîãî èëè ëèíåéíîãî êðèïòîàíàëèçà ïðàêòè÷åñêè
íåðåàëèçóåìî.
5. ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÒÅÎÐÅÌÛ 2
Ïðåäâàðèòåëüíûå çàìå÷àíèÿ. Èç îïðåäåëåíèÿ øèôðà
è íåðà-
âåíñòâ (22), (23) âûòåêàåò, ÷òî
max { ( , )} max {
, \{ } ,
( )
, \{ }
[ , ]
� � � �
� �
� � �
�
� �
V Vn
r
n
d d
0 0
1 1
� �
,
( )[ , ] ( , )}2 5 � � , åñëè r � 6 ; (28)
max { ( , )} max { (
, \{ }
( )
, \{ }
( )[ , ]
� � � �
� � �
�
�
�
V Vn n
l l
0 0
2 5 , )}� , åñëè r � 7 . (29)
Ïîêàæåì, ÷òî äëÿ ëþáûõ âåêòîðîâ � �, \ { }�Vn 0 ñïðàâåäëèâû íåðàâåíñòâà
d d
B BD Lp
� �
�
� � �
�
,
( ) ( )( )
[ , ] ( , )2 5
1 1
� � , (30)
l l
B B
D Lp( )
( )( )
[ , ] ( , )
�
� � �
�2 5
1 1
� �
T T
, (31)
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
ãäå BD (B
DT ) — èíäåêñ âåòâëåíèÿ ìàòðèöû D (D T ), �BLp
( �B
Lp
T ) — ðàñøèðåí-
íûé èíäåêñ âåòâëåíèÿ ìàòðèöû Lp (Lp
T ). Òîãäà íåðàâåíñòâà (24) è (25) âûòåêà-
þò íåïîñðåäñòâåííî èç ôîðìóë (19), (28)–(31) è óòâåðæäåíèÿ 2.
Óáåäèìñÿ â ñïðàâåäëèâîñòè íåðàâåíñòâ (30) (îòìåòèì, ÷òî â çàâåðøàþùåé ÷àñ-
òè äîêàçàòåëüñòâà íå èñïîëüçóåòñÿ íèêàêèõ äîïîëíèòåëüíûõ ïðåäïîëîæåíèé îòíî-
ñèòåëüíî ìàòðèöû D è ïåðåñòàíîâêè g). Íåðàâåíñòâî (31) äîêàçûâàåòñÿ àíàëîãè÷íî.
Âñïîìîãàòåëüíûå óòâåðæäåíèÿ. Ñôîðìóëèðóåì ñëåäóþùèé îáùèé ðå-
çóëüòàò.
Ëåììà 1. Ïóñòü P P ui i u Vl
� �( ( , )) , , � � � �P P ui i u Vl
( ( , )) , — äâàæäû ñòî-
õàñòè÷åñêèå ìàòðèöû òàêèå, ÷òî P Pi i( , ) ( , )0 0 0 0 1� � � , i m�1, ; L V V
l
m
l
m:
—
áèåêòèâíîå îòîáðàæåíèå, óäîâëåòâîðÿþùåå óñëîâèþ
L x y L x L y( ) ( ) ( )� � � , x y V
l
m, � .
Äëÿ ëþáîãî x x x Vm
l
m� �( , ..., )( ) ( )1 îáîçíà÷èì
wt x i m xl
i( ) # { , : }( )� � �1 0 , B L wt x wt L x x Vl l l l
m( ) min{ ( ) ( ( )): }� � � .
Äàëåå, äëÿ ëþáûõ � � �� ( , ..., )( ) ( )1 m , � � �� �( , ..., )( ) ( )1 m
l
mV ïîëîæèì
P Pi
i i
i
m
( , ) ( , )( ) ( )� � � ��
�
,
1
, P Pi
i i
i
m
� � �
�
,( , ) ( , )( ) ( )� � � �
1
, (32)
( )( , ) ( , ) ( ( ), )P P P x P L x
L
x Vl
m
� � � �
�
�� � � � . (33)
Òîãäà ñïðàâåäëèâî íåðàâåíñòâî
max {( )( , )} max max
, \{ , ,
, \{
� �
� �
� �
�
� � �
V
L
i m
u V
l
m
l
P P
0 1
0
}
}
, ,
, \{ }
{ ( , )}, max { ( , )}P u P ui
i m
u V
i
l
�
�
�
!
"
#
$
#
-
.
#
/
#1
0
�
�
�
�
�
�
�
�
�
�
�B Ll ( )
.
1
Äîêàçàòåëüñòâî ëåììû ïî÷òè äîñëîâíî ïîâòîðÿåò äîêàçàòåëüñòâî òåîðåìû 1
è ñëåäñòâèÿ èç íåå â ðàáîòå [15]. Çàìåòèì, ÷òî â [15] ðàññìàòðèâàåòñÿ ÷àñòíûé
ñëó÷àé, â êîòîðîì ìàòðèöà P Pi i� � ÿâëÿåòñÿ ðàñøèðåííîé òàáëèöåé ðàçíîñòåé íå-
êîòîðîé ïîäñòàíîâêè S V Vi l l:
, i m�1, .  ýòîì ñëó÷àå ïàðàìåòð (33) ñîâïàäàåò
ñ âåðîÿòíîñòüþ äèôôåðåíöèàëà 2-ðàóíäîâîãî SPN-øèôðà, ðàóíäîâàÿ ôóíêöèÿ
êîòîðîãî ÿâëÿåòñÿ êîìïîçèöèåé íàáîðà óçëîâ çàìåíû ( , ..., )S S m1 è ëèíåéíîãî
ïðåîáðàçîâàíèÿ L . Çàìåòèì òàêæå, ÷òî â ñëó÷àå, êîãäà ïîñëåäíåå çàäàåòñÿ ñ ïî-
ìîùüþ m m� -ìàòðèöû M íàä ïîëåì èç 2 l ýëåìåíòîâ, çíà÷åíèå B Ll ( ) ñîâïàäàåò
ñ èíäåêñîì âåòâëåíèÿ ìàòðèöû M (ñì. ðàçä. 2).
Èçëîæèì åùå îäíó (ýêâèâàëåíòíóþ) ôîðìóëèðîâêó ëåììû 1.
Íàçîâåì ïðîèçâîëüíóþ äâàæäû ñòîõàñòè÷åñêóþ ìàòðèöó Q ñ ýëåìåíòàìè
Q u( , ) , u Vl, � , ñïåöèàëüíîé, åñëè Q( , )0 0 1� . Îáîçíà÷èì P è P� ñîîòâåòñòâåí-
íî ìàòðèöû ñ ýëåìåíòàìè P ( , )� � è P� ( , )� � âèäà (32) è çàäàäèì ìàòðèöó �PL , ïî-
ëàãàÿ � � �P P LL ( , ) ( ( ), )� � � � , � �, �Vn . Òîãäà ïî îïðåäåëåíèþ ìàòðèöû P è P�
ÿâëÿþòñÿ òåíçîðíûìè ïðîèçâåäåíèÿìè ìàòðèö P Pm1, ..., è � �P Pm1, ..., ñîîòâåò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 27
ñòâåííî: P P Pm� 0 ��� 01 , P P Pm� � � 0 ��� 0 �1 , à ôîðìóëà (33) ñîäåðæèò âûðàæå-
íèå ( , )� � -ãî ýëåìåíòà (îáû÷íîãî) ïðîèçâåäåíèÿ PPL� , êîòîðîå ÿâëÿåòñÿ ñïåöè-
àëüíîé ìàòðèöåé (ïîñêîëüêó òàêîâûìè ÿâëÿþòñÿ Pi è �Pi , i m�1, ). Íàêîíåö, çàäà-
äèì 1-íîðìó ëþáîé ñïåöèàëüíîé ìàòðèöû Q Q u u Vl
� �( ( , )) , , ïîëàãàÿ
|| || max { ( , )}
, \{ }
Q Q u
u Vl
1
�
�
0
. Òîãäà óòâåðæäåíèå ëåììû 1 ìîæíî çàïèñàòü â âèäå
íåðàâåíñòâà
|| || max max || || , max
,
P P P P Pm
L
m
i m
i1 1
1
0 ��� 0 � � 0 ��� 0 � �1
�
1
i m
i
B L
P
l
�
1
�
�
!
"
$
-
.
/
�
�
�
�
�
�
�
�
1
1
,
( )
|| || .
Äëÿ ôîðìóëèðîâêè ñëåäóþùåãî ðåçóëüòàòà ââåäåì íåñêîëüêî äîïîëíèòåëü-
íûõ îáîçíà÷åíèé.
Äëÿ ëþáîé ïîäñòàíîâêè h V Vl l:
îáîçíà÷èì P d uh h
u Vl
( ) ( )
,( ( , ))� � åå
ðàñøèðåííóþ òàáëèöó ðàçíîñòåé,
d u h x u h xh l
x Vl
( ) ( , ) ( ( ) ( ), ) � � � ��
�
�2 , u Vl, � .
Äëÿ êàæäîãî i�1 4, îáîçíà÷èì D di i Vn
( )
,( ( , ))
�� � � � � ìàòðèöó âåðîÿòíîñòåé
i-ðàóíäîâûõ äèôôåðåíöèàëîâ øèôðà
�
[ , ]2 5 . Çàìåòèì, ÷òî ïîñêîëüêó
ÿâëÿ-
åòñÿ 4-ðàóíäîâûì ìàðêîâñêèì SPN-øèôðîì ñ ðàóíäîâîé ôóíêöèåé � âèäà (6), òî
ìàòðèöà Di
( )
ÿâëÿåòñÿ i-é ñòåïåíüþ ìàòðèöû P ( )� , i�1 4, . Îòñþäà âûòåêàþò
ñëåäóþùèå ðàâåíñòâà:
d d d
Vn
4 2 2( , ) ( , ) ( , )� � � � � �
�
�
�
� , � �, �Vn , (34)
d M d x d xMp
s s
p
x Vn
2 ( , ) ( , ) ( , )( ) ( )� � � ��
�
� , � �, �Vn , (35)
ãäå ïîäñòàíîâêà s è ìàòðèöà M p îïðåäåëÿþòñÿ ïî ôîðìóëàì (2) è (5) ñîîòâåò-
ñòâåííî.
Íàêîíåö, èñïîëüçóÿ ââåäåííûå âûøå îáîçíà÷åíèÿ (ñì. (1) è (3)), ïîëîæèì
s s sj
g
g j g q j
( )
( , ) ( , )( , ..., )� 1 , x g xj
g
j
( ) � ( )� , ãäå x Vn� , j c�1, .
Ëåììà 2. Ïðè âûïîëíåíèè ñîîòíîøåíèé (1)–(6) äëÿ ëþáûõ � � �, , �Vn ñïðà-
âåäëèâû ðàâåíñòâà
d M P gp2 ( , ) ( � ( ), )� � � �� , (36)
d P P g M p4
1( , ) ( )( � ( ), ( ) )� � � �� � ��
, (37)
ãäå P — ñïåöèàëüíàÿ ìàòðèöà ñ ýëåìåíòàìè
P x y P P x y
s s
j j
j
c
j
g
j( , ) ( )( , )
( ) ( )
( )
� �
�
, �
1
, x y Vn, � , (38)
� è � — îòîáðàæåíèÿ, îïðåäåëÿåìûå ïî ôîðìóëàì
�( )x xD� , �( ) � ( )x g xM p� , x Vn� .
Äîêàçàòåëüñòâî. Ïîëîæèì I q c� �1 1, , . Ñîãëàñíî ðàâåíñòâàì (1), (2), (35)
d M d x dp
s
i j i j
i j I
si j j
2 ( , ) ( , ) (
( )
, ,
( , )
( ).� � ��
�
�
�
�
�
�
�
�
�
, ( ) , )xM p j j
j
c
x Vn
�
��
,�
�
�
�
�
�
�
�
�
1
.
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Èñïîëüçóÿ ââåäåííûå âûøå îáîçíà÷åíèÿ è ïðèíèìàÿ âî âíèìàíèå, ÷òî g ÿâëÿ-
åòñÿ ïåðåñòàíîâêîé íà ìíîæåñòâå I , ïîëó÷àåì ñëåäóþùèå ðàâåíñòâà:
d x d x
s
i j i j
i j I
s
g i j g i
i j g i j( )
, ,
( , )
( )
( , ) (
. ( . )( , ) ( ,� �
�
, � , )
( , )
( ) ( ) ( )) ( , )
( )
j
i j I
s
j
g
j
g
j
c
d xj
g
� �
, ,� �
1
.
Äàëåå, èñïîëüçóÿ ðàâåíñòâî ( ) ( )xM x Dp j j
g� , x Vn� , êîòîðîå âûòåêàåò èç ôîð-
ìóë (4) è (5), ïîëó÷àåì
d xM
s
p j j
j
c
j( )
(( ) , )�
�
, �
1
d x D
s
j
g
j
j
c
j( ) ( )( , )�
�
,
1
.
Èòàê,
d M d x d x Dp
s
j
g
j
g s
j
g
j
j
j
g
j
2
1
( , ) ( , ) ( , )
( ) ( ) ( ) ( ) ( )
( )
� � � ��
�
c
x Vn
,�
�
�
� �
��
,� d x d x D
s
j
g
j
s
j j
j
c
x V
j
g
j
n
( ) ( ) ( )
( )
( , ) ( , )� �
1
�
�
�
�
�
�
�
�
�
�
��
� d x d x D
s
j
g
j
s
j j
x Vj
j
g
j
j t
q
( ) ( ) ( )
( )
( , ) ( , )� �
� �
, ,� �
1 1
c s s
j
g
j
j
m
P Pj
g
j( )( , )
( ) ( ) ( )
( ) �
� � ,
ãäå ïîñëåäíåå ðàâåíñòâî âûòåêàåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ ïàðàìåòðà â åãî
ïðàâîé ÷àñòè (ñì. (33)). Îòñþäà íà îñíîâàíèè ôîðìóëû (38) âûòåêàåò ðàâåíñòâî (36).
Íàêîíåö, ðàâåíñòâî (37) ÿâëÿåòñÿ ñëåäñòâèåì ôîðìóë (34), (36) è îïðåäåëå-
íèÿ îòîáðàæåíèÿ �:
d d M d M P g P g Mp p
V
p
n
4 2 2( , ) ( , ) ( , ) ( � ( ), ) ( � (� � � � � � � � �
�
� �
�
� ), ( ) )�
�
M p
Vn
�
�
� �1
� � �� �
�
P g P M P P g Mp p( � ( ), ) ( ( ), ( ) ) ( )( � ( ), ( ))� � � � � �
�
�
�1 1
Vn
� .
Ëåììà äîêàçàíà.
Çàâåðøåíèå äîêàçàòåëüñòâà íåðàâåíñòâà (30). Çàôèêñèðóåì âåêòîðû
� �, \ { }�Vn 0 . Èñïîëüçóÿ ââåäåííûå âûøå îáîçíà÷åíèÿ, ôîðìóëû (37), (38) è
ïðèìåíÿÿ ëåììó 1 ê ñïåöèàëüíûì ìàòðèöàì P P P Pj j
s sj
g
j� � � �
( ) ( )
( )
�
ïîðÿäêà q ,
j c�1, , ïîëó÷àåì
d d P P g M p� �
�� � � �
,
( )[ , ] ( , ) ( , ) ( )( � ( ), ( ))2 5
4
1� � � � � �
�
� � �
�
�
��
�
�
��1
�
1
�
|| || max || ||
,
( )
P P P
j m
j
Bq�
�
1
1
. (39)
Äàëåå, èñïîëüçóÿ ðàâåíñòâà
P P P
s s sj
g
g j g q j( ) ( ) ( )
( )
( , ) ( , )� 0���01 , P P P
s s sj j q j( ) ( ) ( ), ,� 0���01 ,
êîòîðûå âûòåêàþò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ ïîäñòàíîâîê s j
g( ) è s j ,
j c�1, , íà îñíîâàíèè ëåììû 1 è îïðåäåëåíèÿ ïàðàìåòðà d� ïîëó÷àåì ñîîòíî-
øåíèÿ
|| || || ||
( ) ( )
( )
P P Pj
s sj
g
j
1 1� � �
�
�
!
"
$
-
.
/�
1
�
1max max || || , max || ||
,
( )
,
( )
( )
i m
s
i m
s
P Pj
g
j
1 1
�
�
�
�
�
�
�
�
�Bt ( )� 1
� �
�
d
Bt ( )� 1
, j c�1, . (40)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 29
Íåðàâåíñòâî (30) âûòåêàåò èç ôîðìóë (39), (40) è ðàâåíñòâ B Bt D( )� � ,
B Bq Lp
( )� � � (ñì. ðàçä. 2).
Òàêèì îáðàçîì, òåîðåìà 2 ïîëíîñòüþ äîêàçàíà.
ÇÀÊËÞ×ÅÍÈÅ
Øèôð «Êàëèíà» îòíîñèòñÿ ê êëàññó Rijndael-ïîäîáíûõ áëî÷íûõ øèôðîâ,
îäíàêî çàìåòíî îòëè÷àåòñÿ îò øèôðà Rijndael.  ÷àñòíîñòè, â øèôðå «Êàëèíà»
ïðèìåíÿþòñÿ:
à) îðèãèíàëüíàÿ ïðîöåäóðà ôîðìèðîâàíèÿ ðàóíäîâûõ êëþ÷åé [1, ï. 7];
á) ïðîöåäóðà «îòáåëèâàíèÿ» ñ ïîìîùüþ àëãåáðàè÷åñêîé îïåðàöèè �
�
(ñì. (8), (9));
â) óçëû çàìåíû � 0 , �1 � 2 , � 3 , ñôîðìèðîâàííûå ïî îïðåäåëåííûì êðèòåðèÿì [2].
Èñïîëüçóåìûå â «Êàëèíå» óçëû çàìåíû è ëèíåéíûå ïðåîáðàçîâàíèÿ èìåþò
ïðèåìëåìûå êðèïòîãðàôè÷åñêèå ñâîéñòâà (ñì. ðàçä. 2). Íå âûÿâëåíî ñëàáîñòåé
óêàçàííûõ êîìïîíåíò, êîòîðûå ìîãóò áûòü èñïîëüçîâàíû ïðè ïîñòðîåíèè
èçâåñòíûõ àòàê íà ýòîò øèôð.
Ãðóïïà, ïîðîæäåííàÿ ðàóíäîâûìè ïðåîáðàçîâàíèÿìè øèôðà «Êàëèíà» ñ äëè-
íîé áëîêà n�{ , , }128 256 512 , ÿâëÿåòñÿ çíàêîïåðåìåííîé íà ìíîæåñòâåVn . Ýòî ñâè-
äåòåëüñòâóåò î ñòîéêîñòè øèôðà îòíîñèòåëüíî àëãåáðàè÷åñêèõ àòàê, îñíîâàííûõ
íà ãîìîìîðôèçìàõ, à òàêæå î åãî àñèìïòîòè÷åñêîé (ñ ðîñòîì ÷èñëà ðàóíäîâ r)
ñòîéêîñòè îòíîñèòåëüíî ðÿäà ñòàòèñòè÷åñêèõ àòàê [11–14].
Ïîëó÷åííûå îöåíêè ìàêñèìàëüíûõ çíà÷åíèé âåðîÿòíîñòåé äèôôåðåíöèàëîâ
è ëèíåéíûõ àïïðîêñèìàöèé øèôðà «Êàëèíà» (ñëåäñòâèå 2) ñâèäåòåëüñòâóþò î
òîì, ÷òî óñïåøíîå ïðèìåíåíèå ê ýòîìó øèôðó êëàññè÷åñêîãî ðàçíîñòíîãî èëè
ëèíåéíîãî êðèïòîàíàëèçà ïðàêòè÷åñêè íåâîçìîæíî.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. O l i y n y k o v R . V . , G o r b e n k o I . D . , K a z y m y r o v O . V . et. al. A new encryption standard
of Ukraine: The Kalyna block cipher // Cryptology ePrint Archive. http://eprint.iacr.org/ 2015/650.
2. Î ë ³ é í è ê î â Ð .  . , à î ð á å í ê î ² . Ä . , Ê à ç è ì è ð î â Î .  . òà ³í. Ïðèíöèïè ïîáóäîâè ³
îñíîâí³ âëàñòèâîñò³ íîâîãî íàö³îíàëüíîãî ñòàíäàðòó áëîêîâîãî øèôðóâàííÿ Óêðà¿íè // Çàõèñò
³íôîðìàö³¿. — 2015. — 17, ¹ 2. — Ñ. 142–157.
3. À l T a w y R . , A b d e l k h a l e k A . , Y o u s s e f A . M . A meet-in-the-middle attack on
reduced-round Kalyna-b/2b // Cryptology ePrint Archive. http://eprint.iacr.org/2015/762.
4. Ì à ñ ë î â À . Ñ . Îá óñëîâèÿõ ïîðîæäåíèÿ SA-ïîäñòàíîâêàìè çíàêîïåðåìåííîé ãðóïïû // Òðó-
äû Èí-òà ìàòåìàòèêè. — 2007. — 15, ¹ 2. — Ñ. 58–68.
5. D a e m e n J . Cipher and hash function design strategies based on linear and differential
cryptanalysis. — Ph. D. Thesis. — Katholieke Univ. Leuven, 1995. — 224 p.
6. Ì à ê - Â è ë ü ÿ ì ñ Ô . Ä æ . , Ñ ë î ý í Í . Ä æ . À . Òåîðèÿ êîäîâ, èñïðàâëÿþùèõ îøèáêè:
Ïåð. ñ àíãë. — Ì.: Ñâÿçü, 1979. — 743 ñ.
7. À ë å ê ñ å é ÷ ó ê À . Í . Êðèòåðèé ïðèìèòèâíîñòè ãðóïïû ïîäñòàíîâîê, ïîðîæäåííîé ðàóíäî-
âûìè ïðåîáðàçîâàíèÿìè Rijndael-ïîäîáíîãî áëî÷íîãî øèôðà // Ðåºñòðàö³ÿ, çáåð³ãàííÿ ³ îáðîá-
êà äàíèõ. — 2004. — 6, ¹ 2. — Ñ. 11–18.
8. À ë å ê ñ å é ÷ ó ê À . Í . , Ñ ê ð û í í è ê Å . Â . Êëàññû îòîáðàæåíèé ñ òðèâèàëüíîé ëèíåéíîé
ñòðóêòóðîé íàä êîíå÷íûì ïîëåì // Ðåºñòðàö³ÿ, çáåð³ãàííÿ ³ îáðîáêà äàíèõ. — 2008. — 10,
¹ 3. — Ñ. 80–88.
9. Ñ à ÷ ê î â Â . Í . Ââåäåíèå â êîìáèíàòîðíûå ìåòîäû äèñêðåòíîé ìàòåìàòèêè. —
Ì.: ÌÍÖÍÌÎ, 2004. — 424 ñ.
10. Ñ à ÷ ê î â Â . Í . , Ò à ð à ê à í î â Â . Å . Êîìáèíàòîðèêà íåîòðèöàòåëüíûõ ìàòðèö. — Ì.: ÒÂÏ,
2000. — 447 ñ.
11. P a t e r s o n K . G . Imprimitive permutation groups and trapdoors in iterated block ciphers // Fast
Software Encryption. — FSE’99, Proceedings. — Springer Verlag, 1999. — P. 201–214.
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
12. H o r n a u e r G . , S t e p h a n W . , W e r n s d o r f R . Markov ciphers and alternating groups //
Advances in Cryptology — EUROCRYPT’93, Proceedings. — Springer Verlag, 1994. —
P. 453–460.
13. W a g n e r D . Towards a unifying view of block cipher cryptanalysis // Fast Software Encryption. —
FSE’04, Proceedings. — Springer Verlag, 2004. — P. 116–135.
14. V a u d e n a y S . Decorrelation: A theory for block cipher security // J. of Cryptology. — 2003. —
N 4. — P. 249–286.
15. P a r k S . , S u n g J . , L e e S . , L i m J . Improving the upper bound on the maximum differential
and the maximum linear hull probability for the SPN structures and AES // Fast Software
Encryption — FSE’03, Proceedings. — Springer Verlag, 2003. — P. 247–260.
Íàä³éøëà äî ðåäàêö³¿ 05.10.2015
À.Ì. Îëåêñ³é÷óê, Ë.Â. Êîâàëü÷óê, À.Ñ. Øåâöîâ, Ñ.Â. ßêîâëºâ
ÏÐÎ ÊÐÈÏÒÎÃÐÀÔ²×Ͳ ÂËÀÑÒÈÂÎÑÒ² ÍÎÂÎÃÎ ÍÀÖ²ÎÍÀËÜÍÎÃÎ ÑÒÀÍÄÀÐÒÓ
ØÈÔÐÓÂÀÍÍß ÓÊÐÀ¯ÍÈ
Àíîòàö³ÿ. Äîñë³äæåíî íèçêó êðèïòîãðàô³÷íèõ âëàñòèâîñòåé áëîêîâîãî øèô-
ðó «Êàëèíà», ïðèéíÿòîãî ÿê íîâèé íàö³îíàëüíèé ñòàíäàðò øèôðóâàííÿ
Óêðà¿íè. Ïðîàíàë³çîâàíî íàéâàæëèâ³ø³ âëàñòèâîñò³ êîìïîíåíò öüîãî øèô-
ðó. Ïîêàçàíî, ùî éîãî ðàóíäîâ³ ïåðåòâîðåííÿ ïîðîäæóþòü çíàêîçì³ííó ãðó-
ïó ï³äñòàíîâîê, ùî ñâ³ä÷èòü ïðî ñò³éê³ñòü äî àëãåáðà¿÷íèõ àòàê, ïîáóäîâà-
íèõ íà ãîìîìîðô³çìàõ, à ñàì øèôð º îá´ðóíòîâàíî ñò³éêèì â³äíîñíî ð³çíè-
öåâîãî òà ë³í³éíîãî êðèïòîàíàë³çó.
Êëþ÷îâ³ ñëîâà: ñèìåòðè÷íà êðèïòîãðàô³ÿ, áëîêîâèé øèôð, ñê³í÷åííà ãðóïà
ï³äñòàíîâîê, ð³çíèöåâèé êðèïòîàíàë³ç, ë³í³éíèé êðèïòîàíàë³ç, íàö³îíàëüíèé
ñòàíäàðò øèôðóâàííÿ Óêðà¿íè, øèôð «Êàëèíà».
A.N. Alekseychuk, L.V. Kovalchuk, A.S. Shevtsov, S.V. Yakovliev
CRYPTOGRAPHIC PROPERTIES OF THE NEW NATIONAL ENCRYPTION
STANDARD OF UKRAINE
Abstract. Block cipher “Kalyna” has been recently accepted as a new national
encryption standard of Ukraine. In the paper we analyze the most important
properties of components of this cipher. We show that round transformations of
“Kalyna” generate a sign-alternating group of substitutions. As a result,
“Kalyna” is secure against algebraic attacks based on homomorphisms. Also we
demonstrate that this cipher is reasonably secure against differential and linear
cryptanalysis.
Keywords: symmetric cryptography, block cipher, finite permutation group,
differential cryptanalysis, linear cryptanalysis, national encryption standard
of Ukraine, cipher “Kalyna.”
Àëåêñåé÷óê Àíòîí Íèêîëàåâè÷,
äîêòîð òåõí. íàóê, äîöåíò, ïðîôåññîð Èíñòèòóòà ñïåöèàëüíîé ñâÿçè è çàùèòû èíôîðìàöèè
Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», Êèåâ, e-mail: alex-dtn@ukr.net.
Êîâàëü÷óê Ëþäìèëà Âàñèëüåâíà,
äîêòîð òåõí. íàóê, äîöåíò Ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà
Óêðàèíû «ÊÏÈ», Êèåâ, e-mail: lusi.kovalchuk@gmail.com.
Øåâöîâ Àðòóð Ñåðãååâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò Èíñòèòóòà ñïåöèàëüíîé ñâÿçè è çàùèòû èíôîðìàöèè Íàöèîíàëüíîãî
òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», Êèåâ, e-mail: as.shevtsov@gmail.com.
ßêîâëåâ Ñåðãåé Âëàäèìèðîâè÷, êàíäèäàò òåõí. íàóê, ñòàðøèé ïðåïîäàâàòåëü Ôèçèêî-òåõíè÷åñêîãî
èíñòèòóòà Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», Êèåâ, e-mail: yasv@rl.kiev.ua.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 31
|