О вычислительной стойкости квантовых алгоритмов преобразования информации
Досліджено обчислювальну стійкість квантового протоколу переказу ключа, припускаючи, що криптоаналітик керує ймовірностями вибору базисних векторів, а також одночасною зміною базисів у відправника та адресата. Побудовано квантовий шифр, що базується на квантовому алгоритмі щільного кодування. Встано...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45642 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О вычислительной стойкости квантовых алгоритмов преобразования информации / В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 6. — С. 3–17. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859827592949923840 |
|---|---|
| author | Скобелев, В.Г. |
| author_facet | Скобелев, В.Г. |
| citation_txt | О вычислительной стойкости квантовых алгоритмов преобразования информации / В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 6. — С. 3–17. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Досліджено обчислювальну стійкість квантового протоколу переказу ключа, припускаючи, що криптоаналітик керує ймовірностями вибору базисних векторів, а також одночасною зміною базисів у відправника та адресата. Побудовано квантовий шифр, що базується на квантовому алгоритмі щільного кодування. Встановлено, що цей шифр обчислювально стійкий, якщо секретний сеансовий ключ є послідовністю, близькою до випадкової послідовності.
The computational complexity of a quantum key distribution protocol is investigated under the assumption that the cryptanalyst can control the probabilities of selection of the basic vectors for qubit measurement, as well as of simultaneous change of bases of the sender and the receiver. A cipher based on the dense coding algorithm is introduced. It is established that this cipher is computationally secure if the secret key is a near-random sequence.
|
| first_indexed | 2025-12-07T15:30:33Z |
| format | Article |
| fulltext |
Â.Ã. ÑÊÎÁÅËÅÂ
ÓÄÊ 518.6+681.3 Î ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÑÒÎÉÊÎÑÒÈ
ÊÂÀÍÒÎÂÛÕ ÀËÃÎÐÈÒÌÎÂ
ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÈÍÔÎÐÌÀÖÈÈ
Êëþ÷åâûå ñëîâà: êâàíòîâàÿ êðèïòîãðàôèÿ, êðèïòîàíàëèç, àêòèâíàÿ àòàêà,
êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à, ïëîòíîå êîäèðîâàíèå, êâàíòîâûé øèôð.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ âî âñåì ìèðå âåäóòñÿ èíòåíñèâíûå èññëåäîâàíèÿ â îáëàñòè
êâàíòîâûõ âû÷èñëåíèé [1–3] — íîâîãî ïåðñïåêòèâíîãî íàïðàâëåíèÿ ñîâðåìåííûõ
èíôîðìàöèîííûõ òåõíîëîãèé. Â êâàíòîâîé ñèñòåìå äëÿ ýêñïîíåíöèàëüíîãî óìåíü-
øåíèÿ âðåìåíè âû÷èñëåíèé òðåáóåòñÿ òîëüêî ëèíåéíîå óâåëè÷åíèå îáúåìà íåîáõî-
äèìîãî ôèçè÷åñêîãî ïðîñòðàíñòâà. Äàííûå èññëåäîâàíèÿ ïðîâîäÿò â äâóõ íàïðàâëå-
íèÿõ: ñèíòåç êâàíòîâîãî êîìïüþòåðà; ðàçðàáîòêà êâàíòîâîé òåîðèè àëãîðèòìîâ.
Ïðèìåíåíèå êâàíòîâûõ âû÷èñëåíèé ê ðåøåíèþ çàäà÷ êðèïòîëîãèè [3–5]
îáîñíîâûâàåò àêòóàëüíîñòü ðàññìîòðåíèÿ âû÷èñëèòåëüíîé ñòîéêîñòè êâàíòîâûõ
àëãîðèòìîâ, ïðåäíàçíà÷åííûõ äëÿ ïðåîáðàçîâàíèÿ èíôîðìàöèè. Âîçíèêàåò âîïðîñ:
÷òî è êàê ïîäâåðãàåòñÿ àòàêå? Ñëîæíîñòü îòâåòà ñîñòîèò â òîì, ÷òî ïîêà íåäîñòà-
òî÷íî ïðîðàáîòàíà ôîðìàëüíàÿ ìîäåëü êâàíòîâîãî êîìïüþòåðà, à èñêàæåíèå ïåðå-
äàâàåìîé èíôîðìàöèè çà ñ÷åò åå èçìåðåíèÿ ïðèâîäèò ê íîâûì òèïàì àòàê, ïðåä-
ñòàâëÿþùèì ñîáîé ñèìáèîç ïàññèâíûõ è àêòèâíûõ àòàê [6]. Â ñâÿçè ñ ýòèì àêòóàëü-
íûì ÿâëÿåòñÿ èññëåäîâàíèå âû÷èñëèòåëüíîé ñòîéêîñòè êâàíòîâûõ àëãîðèòìîâ,
ïðåäíàçíà÷åííûõ äëÿ ðåøåíèÿ ìîäåëüíûõ çàäà÷ êðèïòîëîãèè.
 íàñòîÿùåé ðàáîòå â êà÷åñòâå òàêèõ çàäà÷ âûáðàí àíàëèç àòàê íà êëàññè÷åñêèé
êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à è àíàëèç ïîñòðîåííîãî â ðàáîòå êâàíòîâîãî øèô-
ðà, îñíîâàííîãî íà àëãîðèòìå ïëîòíîãî êîäèðîâàíèÿ. Â ðàçä. 1 ðàññìîòðåí êâàíòîâûé
ïðîòîêîë ïåðåäà÷è êëþ÷à, äàíû ïîñòàíîâêè çàäà÷ àòàêè íà ýòîò ïðîòîêîë.  ðàçä. 2
ðàññìàòðèâàåòñÿ àòàêà â ïðåäïîëîæåíèè, ÷òî êðèïòîàíàëèòèê óïðàâëÿåò òîëüêî âåðî-
ÿòíîñòÿìè âûáîðà áàçèñíûõ âåêòîðîâ äëÿ èçìåðåíèÿ êóáèòà, à â ðàçä. 3 — óñèëåíèå
ýòîé àòàêè, ñîñòîÿùåå â òîì, ÷òî êðèïòîàíàëèòèê òàêæå ìîæåò óïðàâëÿòü îäíîâðåìåí-
íûì èçìåíåíèåì áàçèñîâ îòïðàâèòåëÿ è àäðåñàòà. Â ðàçä. 4 èçëîæåí àëãîðèòì ïëîòíî-
ãî êîäèðîâàíèÿ è ïðåäëîæåí øèôð, ïîñòðîåííûé íà åãî îñíîâå. Â ðàçä. 5 èññëåäóåòñÿ
âû÷èñëèòåëüíàÿ ñòîéêîñòü ýòîãî øèôðà. Çàêëþ÷åíèå ñîäåðæèò ðÿä âûâîäîâ.
1. ÊÂÀÍÒÎÂÛÉ ÏÐÎÒÎÊÎË ÏÅÐÅÄÀ×È ÊËÞ×À
Ïðåäïîëàãàåòñÿ, ÷òî îòïðàâèòåëü è àäðåñàò ðàñïîëàãàþò êâàíòîâûì è êëàññè÷åñ-
êèì êàíàëàìè: ïåðâûé ïðèìåíÿåòñÿ äëÿ ïåðåäà÷è êëþ÷à ïîñëåäîâàòåëüíîñòüþ
êóáèòîâ, âòîðîé — äëÿ êîíòðîëÿ âû÷èñëåíèé (ðèñ.1).
Îáîçíà÷èì Bj
j j� { }e e
0 1
( ) ( ), ( , )j � 0 1 òàêèå îðòîíîðìèðîâàííûå áàçèñû ïðî-
ñòðàíñòâà H2 , ÷òî e e e
i
i( ) , ( ) ( )( ( ) )1 0 5
0
0 1
1
02 1� � �� � ( , )i � 0 1 . Äëÿ ïåðåäà÷è çíà÷åíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 3
© Â.Ã. Ñêîáåëåâ, 2010
î÷åðåäíîãî áèòà îòïðàâèòåëü ñëó÷àéíûì
îáðàçîì âûáèðàåò áàçèñ Bj ( , )j � 0 1 , èçìå-
ðÿåò êóáèò (ïðåäñòàâëÿþùèé ñîáîé ñëó-
÷àéíûì îáðàçîì ïîëÿðèçîâàííûé ôîòîí)
â ýòîì áàçèñå è ïåðåäàåò èçìåðåííûé êó-
áèò àäðåñàòó ïî êâàíòîâîìó êàíàëó. Äëÿ
òîãî ÷òîáû ïðèíÿòü çíà÷åíèå î÷åðåäíîãî
áèòà, àäðåñàò ñëó÷àéíûì îáðàçîì âûáèðàåò
áàçèñ Bj ( , )j � 0 1 , à çàòåì èçìåðÿåò ïðèíÿ-
òûé êóáèò â íåì. Ïî çàâåðøåíèè ïðîöåññà ïåðåäà÷è ïîñëåäîâàòåëüíîñòè áèòîâ îò-
ïðàâèòåëü è àäðåñàò ïî êëàññè÷åñêîìó êàíàëó ñîîáùàþò äðóã äðóãó, êàêèå áàçèñû
áûëè âûáðàíû äëÿ êîäèðîâàíèÿ è èçìåðåíèÿ êàæäîãî áèòà. Áèòû, ïðè îáðàáîòêå
êîòîðûõ îòïðàâèòåëü è àäðåñàò èñïîëüçîâàëè îäèí è òîò æå áàçèñ, ïðèíèìàþòñÿ
â êà÷åñòâå êëþ÷à, à îñòàëüíûå îòáðàñûâàþòñÿ. Äîêàçàíî, ÷òî â ñðåäíåì äëèíà êëþ-
÷à ñîñòàâëÿåò 50% äëèíû ïåðåäàííîé ïîñëåäîâàòåëüíîñòè.
Êëàññè÷åñêàÿ àòàêà íà ýòîò ïðî-
òîêîë ñîñòîèò â ñëåäóþùåì. Êðèïòî-
àíàëèòèê ïåðåõâàòûâàåò ïåðåäàâàå-
ìûå êóáèòû, èçìåðÿåò èõ, à çàòåì ïå-
ðåñûëàåò àäðåñàòó. Êðîìå òîãî,
êðèïòîàíàëèòèê èìååò âîçìîæíîñòü
ïðîñëóøèâàòü êëàññè÷åñêèé êàíàë
(ðèñ. 2). Äîêàçàíî, ÷òî â ýòîì ñëó÷àå
àäðåñàò â ñðåäíåì âåðíî èçìåðèò
òîëüêî 50% îò äëèíû êëþ÷à. Ïîýòî-
ìó, ñðàâíèâ ïî îòêðûòîìó êàíàëó íå-
êîòîðîå ÷èñëî áèòîâ êëþ÷à, îòïðàâè-
òåëü è àäðåñàò ñ ñîîòâåòñòâóþùåé âåðîÿòíîñòüþ îáíàðóæàò íàëè÷èå àòàêè.
Õîòÿ îá ýòîì íèãäå ÿâíî íå ñêàçàíî, ðàññìîòðåííûé àíàëèç àòàêè íà êâàíòî-
âûé ïðîòîêîë ïåðåäà÷è êëþ÷à îñíîâàí íà ïðåäïîëîæåíèè î òîì, ÷òî êðèïòîàíàëè-
òèê è àäðåñàò ïðè èçìåðåíèè êóáèòà â áàçèñå B
j
( , )j � 0 1 âû÷èñëÿþò åãî ïðîåêöèþ
íà îäèí è òîò æå ôèêñèðîâàííûé áàçèñíûé âåêòîð. Îñëàáèì ýòî ïðåäïîëîæåíèå,
à èìåííî: áóäåì ñ÷èòàòü, ÷òî òîëüêî îòïðàâèòåëü â ïðîöåññå ïåðåäà÷è çíà÷åíèÿ i
( , )i � 0 1 áèòà, âûáðàâ áàçèñ Bj ( , )j � 0 1 , âñåãäà êîíñòðóèðóåò ïðîåêöèþ ïåðåäàâàå-
ìîãî êóáèòà íà áàçèñíûé âåêòîð e
i
j( ) .
Ðàññìîòðåííàÿ àòàêà íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à ïðåäïîëàãàåò,
÷òî â ðàñïîðÿæåíèè êðèïòîàíàëèòèêà èìååòñÿ ìèíèìóì ñðåäñòâ. Óñèëèì åå çà ñ÷åò
ñëåäóþùèõ ïðåäïîëîæåíèé:
Ïðåäïîëîæåíèå 1. Äëÿ èçìåðåíèÿ ïåðåõâà÷åííîãî êóáèòà â áàçèñå Bj ( , )j � 0 1
êðèïòîàíàëèòèê âûáèðàåò áàçèñíûé âåêòîð e
i
j( ) ( , )i � 0 1 ñ âåðîÿòíîñòüþ p ij
1
( ) ( ) .
Ïðåäïîëîæåíèå 2. Êðèïòîàíàëèòèê îïðåäåëÿåò âåðîÿòíîñòü p ij
2
( ) ( ) ( , , )i j �{ }0 1
âûáîðà àäðåñàòîì áàçèñíîãî âåêòîðà e
i
j( ) ïðè èçìåðåíèè êóáèòà â áàçèñå B
j
, ïðè-
÷åì àäðåñàò íå ðàñïîëàãàåò èíôîðìàöèåé î òîì, ÷òî ó íåãî ïðîèçîøëî èçìåíåíèå
áàçèñíîãî âåêòîðà.
Ïðåäïîëîæåíèå 3. Êðèïòîàíàëèòèê ìîæåò îäíîâðåìåííî èçìåíÿòü ó îòïðàâè-
òåëÿ è àäðåñàòà áàçèñ Bj ( , )j � 0 1 íà áàçèñ B
1� j
ñ âåðîÿòíîñòüþ p j0 ( ) , ïðè÷åì íè
îòïðàâèòåëü, íè àäðåñàò íå ðàñïîëàãàþò èíôîðìàöèåé î òîì, ÷òî ó íèõ ïðîèçîøëî
èçìåíåíèå áàçèñà.
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Ðèñ. 2
Îòïðàâèòåëü Àäðåñàò
Êëàññè÷åñêèé êàíàë
Êâàíòîâûé
êàíàë
Êâàíòîâûé
êàíàë
Êðèïòîàíàëèòèê
Ðèñ. 1
Îòïðàâèòåëü Àäðåñàò
Êëàññè÷åñêèé
êàíàë
Êâàíòîâûé
êàíàë
Òàêèì îáðàçîì, ïîëó÷àåì àòàêó íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à, êîòî-
ðàÿ ñõåìàòè÷åñêè ïðåäñòàâëåíà íà ðèñ. 3. Îòìåòèì, ÷òî èç ïðåäïîëîæåíèé 1 è 2 âû-
òåêàåò, ÷òî ðàâåíñòâî
p i p i
k
j
k
j( ) ( )( ) ( )1 1� � � (1)
èñòèííî äëÿ âñåõ i j, ,�{ }0 1 è k �{ }1 2, .
2. ÀÒÀÊÀ ÏÐÈ ÓÏÐÀÂËÅÍÈÈ ÂÅÐÎßÒÍÎÑÒßÌÈ ÂÛÁÎÐÀ
ÁÀÇÈÑÍÛÕ ÂÅÊÒÎÐÎÂ ÄËß ÈÇÌÅÐÅÍÈß ÊÓÁÈÒÀ
Èññëåäóåì àòàêó íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à, îïðåäåëÿåìóþ ïðåäïî-
ëîæåíèÿìè 1 è 2. Îáîçíà÷èì P
jhj
i( ) ( , , , )i h j �{ }0 1 âåðîÿòíîñòü ïðàâèëüíîãî ñ÷èòû-
âàíèÿ àäðåñàòîì çíà÷åíèÿ i áèòà ïðè óñëîâèè, ÷òî äëÿ äàííîãî êóáèòà îòïðàâè-
òåëü è àäðåñàò èñïîëüçóþò áàçèñ Bj , à êðèïòîàíàëèòèê — áàçèñ Bh .
Ëåììà 1. Ðàâåíñòâà
P p i p i p i
jjj
i j j j( ) ( ) ( ) ( )( ) ( ) ( )� � �1
2 1 2
, (2)
P p i
j j j
i j
, ,
( ) ( ), , ( )
1 2
0 75 0 5
�
� � (3)
èñòèííû äëÿ âñåõ i j, ,�{ }0 1 .
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî ïðè îáðàáîòêå î÷åðåäíîãî êóáèòà îòïðà-
âèòåëü, êðèïòîàíàëèòèê è àäðåñàò èñïîëüçóþò îäèí è òîò æå áàçèñ Bj ( , )j � 0 1 .
Ñ ïðèìåíåíèåì ðàâåíñòâà (1) âû÷èñëèì âåðîÿòíîñòè âîçìîæíûõ ýëåìåíòàðíûõ ñî-
áûòèé, îïðåäåëÿåìûõ âûáîðîì êðèïòîàíàëèòèêîì è àäðåñàòîì áàçèñíîãî âåêòîðà
â áàçèñå Bj ( , )j � 0 1 . Ñõåìà ýòèõ âû÷èñëåíèé ïðåäñòàâëåíà íà ðèñ. 4 (çíàê «*»
îçíà÷àåò, ÷òî ïðè èçìåðåíèè êóáèòà êðèïòîàíàëèòèêîì ôîòîí îòðàæàåòñÿ). Ñëåäî-
âàòåëüíî, åñëè i j, ,�{ }0 1, òî
P p i p i p i
jjj
i j j j( ) ( ) ( ) ( )( ) ( ) ( )� � �
1 2 1
� � � � �p i p i p i p ij j j j
1 2 1 2
1 1( ) ( ) ( ) ( )( ) ( ) ( ( ))( ( )) 1
2 1 2
� �p i p i p ij j j( ) ( ) ( )( ) ( ) ( ) ,
÷òî è òðåáîâàëîñü äîêàçàòü.
Ïðåäïîëîæèì, ÷òî ïðè îáðàáîòêå î÷åðåäíîãî êóáèòà îòïðàâèòåëü è àäðåñàò
èñïîëüçóþò áàçèñ Bj ( , )j � 0 1 , à êðèïòîàíàëèòèê — áàçèñ B1� j . Ñ ïðèìåíåíèåì ðà-
âåíñòâà (1) âû÷èñëèì âåðîÿòíîñòè âîçìîæíûõ ýëåìåíòàðíûõ ñîáûòèé, îïðåäåëÿå-
ìûõ âûáîðîì àäðåñàòîì áàçèñíîãî âåêòîðà â áàçèñå Bj ( , )j � 0 1 , à êðèïòîàíàëèòè-
êîì — áàçèñíîãî âåêòîðà â áàçèñå B1� j . Ñõåìà ýòèõ âû÷èñëåíèé ïðåäñòàâëåíà íà
ðèñ. 5 (îòìåòêà «à» äóãè îçíà÷àåò ôðàçó «ôîòîí ïðîõîäèò ñ âåðîÿòíîñòüþ 0,5»,
à îòìåòêà «b» — ôðàçó «ôîòîí îòðàæàåòñÿ ñ âåðîÿòíîñòüþ 0,5»). Ñëåäîâàòåëüíî,
åñëè i j, ,�{ }0 1, òî
P p i p i p i
j j j
i j j j
, ,
( ) ( ) ( ) ( ), ( ) ( ) , ( )(
1 1
1
2 1
10 25 0 75
�
� �� � 1
2
� �p ij( ) ( ))
� � � � �� �0 25 1 0 75 1 1
1
1
2 1
1, ( ( )) ( ) , ( ( ))(( ) ( ) ( )p i p i p i pj j j
2 2
0 75 0 5( ) ( )( )) , , ( )j ji p i� � .
Ëåììà äîêàçàíà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 5
Ðèñ. 3
Îòïðàâèòåëü Àäðåñàò
Êëàññè÷åñêèé êàíàë
Êâàíòîâûé
êàíàë
Êâàíòîâûé
êàíàë
Êðèïòîàíàëèòèê
Óïðàâëåíèå âåðîÿòíîñòüþ âûáîðà
áàçèñíîãî âåêòîðà èçìåðåíèÿ
Óïðàâëåíèå âåðîÿòíîñòüþ
îäíîâðåìåííîãî èçìåíåíèÿ áàçèñîâ
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Ïåðåäà-
âàåìûé
áèò
Ïåðåäà-
âàåìûé
êóáèò
Èçìåðåíèå
êóáèòà
êðèïòî-
àíàëèòèêîì
Èçìåðåíèå
êóáèòà
àäðåñàòîì
Ïðèíÿòûé
àäðåñàòîì
áèò
Âåðîÿòíîñòü
ýëåìåíòàðíîãî
ñîáûòèÿ
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
�
�e
p i
j
i
j
2
( )
( )
( )
e
p i
j
i
j
2
( )
( )
( )
e
1 � i
1 � i
i
� 0 25
1
1
2
, ( ) ( )
( ) ( )
p i p i
j j�
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
�
�e
p i
j
i
j
2
1
1
( )
( )
( )�
�e
p i
j
i
j
2
1
1
( )
( )
( )�
�e
i
i
1 � i
� 0 75 1
1
1
2
, ( )( ( ))
( ) ( )
p i p i
j j� �
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
�
�e
p i
j
i
j
2
( )
( )
( )
e
p i
j
i
j
2
( )
( )
( )
e
1 � i
1 � i
i � 0 25 1
1
1
2
, ( ( )) ( )
( ) ( )� �
p i p i
j j
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
�
�e
p i
j
i
j
2
1
1
( )
( )
( )�
�e
p i
j
i
j
2
1
1
( )
( )
( )�
�e
i
i
1 � i
� 0 75 1 1
1
1
2
, ( ( ))( ( ))
( ) ( )� ��
p i p i
j j
Ðèñ. 5
� ��
� ��
a
b
� ��
� ��
a
b
� ��
� ��
a
b
� ��
a
b
� ��
� ��
� ��
� ��
� ��
� ��
� ��a
b
� ��
� ��a
b
� ��
� ��a
b
� ��
� ��a
b
�
�
�
�
�
�
Ïåðåäà-
âàåìûé
áèò
Ïåðåäà-
âàåìûé
êóáèò
Èçìåðåíèå
êóáèòà
êðèïòî-
àíàëèòèêîì
Èçìåðåíèå
êóáèòà
àäðåñàòîì
Ïðèíÿòûé
àäðåñàòîì
áèò
Âåðîÿòíîñòü
ýëåìåíòàðíîãî
ñîáûòèÿ
i � e
i
j( ) �
p i
j
i
j
1
( )
( )
( )
e
�
p i
j
i
j
2
( )
( )
( )
e
� i � p i p i
j j
1 2
( ) ( )
( ) ( )
i � e
i
j( ) �
p i
j
i
j
1
( )
( )
( )
e
�
p i
j
i
j
2
1
1
( )
( )
( )
*
�
�e � i � p i p i p i
j j j
1 1 2
( ) ( ) ( )
( ) ( ) ( )�
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
*
�
�e �
p i
j
i
j
2
( )
( )
( )
e
� 1 � i
i � e
i
j( ) �
p i
j
i
j
1
1
1
( )
( )
( )
*
�
�e �
p i
j
i
j
2
1
1
( )
( )
( )�
�e
� i � ( ( ))( ( ))
( ) ( )
1 1
1 2
� �p i p i
j j
Ðèñ. 4
Îáîçíà÷èì Pjhj ( )� ( , , ; [ ; ] )j h � �{ }0 1 0 1� âåðîÿòíîñòü ïðàâèëüíîãî ñ÷èòûâàíèÿ
àäðåñàòîì çíà÷åíèÿ áèòà ïðè óñëîâèè, ÷òî äëÿ äàííîãî êóáèòà îòïðàâèòåëü è àäðå-
ñàò èñïîëüçóþò áàçèñ Bj , êðèïòîàíàëèòèê — áàçèñ B1� j , à âåðîÿòíîñòü ïåðåñûëêè
ñèìâîëà 0 îòïðàâèòåëåì ðàâíà �.
Òåîðåìà 1. Ïðè ëþáîì çíà÷åíèè âåðîÿòíîñòè � �[ ; ]0 1 ðàâåíñòâà
P p p p p pjjj
j j j j( ) ( ) ( ) ( ) ( ( )( ) ( ) ( ) ( ) (� �� � � � �1 0 0 0 0
1 1 2 1 2
j ) ( ))0 , (4)
P pj j j
j
, ,
( )( ) , , ( , ) ( )1 2
0 25 0 5 0 5 0� � � � �� � � (5)
èñòèííû äëÿ âñåõ j �{ }0 1, .
Äîêàçàòåëüñòâî. Òàê êàê P P Pjjj jjj jjj
( ) ( )( ) ( )� � �� � �0 11 ( , , [ ; ])j � �{ }0 1 0 1� , âîñ-
ïîëüçîâàâøèñü ðàâåíñòâàìè (1) è (2), ïîëó÷èì
P p p pjjj
j j j( ) ( ( ) ( ) ( ))( ) ( ) ( )� �� � � �1 0 0 0
2 1 2
� � � � � �( )( ( ) ( ( ))( ( )))( ) ( ) ( )1 0 1 0 1 0
2 1 2
� p p pj j j
� � � � �1 0 0 0 0 0
1 1 2 1 2
p p p p pj j j j j( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ( ) ( ))� ( , )j � 0 1 ,
÷òî è òðåáîâàëîñü äîêàçàòü.
Ïîñêîëüêó P P P jj j j j j j j j j, , , ,
( )
, ,
( )( ) ( ) ( , ,1 1
0
1
11 0 1� � �
� � � �� � � { } � �[ ; ])0 1 , âîñïîëü-
çîâàâøèñü ðàâåíñòâàìè (1) è (3), ïîëó÷èì
P pj j j
j
, ,
( )( ) ( , , ( ))1 2
0 75 0 5 0� � � �� �
� � � � � � �( )( , , ( ( ))) ( , , ( )) (( ) ( )1 0 75 0 5 1 0 0 75 0 5 0
2 2
� �p pj j 1 0 25 0 5 0
2
� � ��) ( , , ( ))( )p j
� � � �0 25 0 5 0 5 0
2
, , ( , ) ( )( )� � p j ( , )j � 0 1 .
Òåîðåìà äîêàçàíà.
Îòìåòèì ðÿä ñëåäñòâèé èç ðàâåíñòâà (4).
1. Ïóñòü p j
2
0 0 5( ) ( ) ,� ( , )j � 0 1 . Òîãäà
P pjjj
j( ) ( , ) ( ) ,( )� � �� � � �1 0 5 0 0 5
1
( , , [ ; ])j � �{ }0 1 0 1� . (6)
Èç (6) âûòåêàåò, ÷òî
P
p
p
jjj
j
j
( )
, , ( ) ,
, ( ), (
( )
( )
�
�
�
�
� �
�
1 0 5 0 0
0 5 1 0
1
1
åñëè
åñëè ) �
�
�
�� 1
( , , [ ; ])j � �{ }0 1 0 1� .
2. Ïóñòü p p pj j j
1 2
0 0 0( ) ( ) ( )( ) ( ) ( )� � ( , )j � 0 1 . Òîãäà
P p pjjj
j j( ) ( ) ( ( ))( ) ( )� � � �1 0 0 2 ( , , [ ; ])j � �{ }0 1 0 1� , (7)
ò.å. âåðîÿòíîñòü Pjjj ( )� íå çàâèñèò îò âåðîÿòíîñòè �. Èç (7) âûòåêàåò, ÷òî
Pjjj ( ) [ , ; ]� � 0 75 1 ( , , [ ; ])j � �{ }0 1 0 1� äëÿ âñåõ p j( ) ( ) [ ; ]0 0 1� , ïðè÷åì
P
p
p
jjj
j
j
( )
, , ( ) , ,
, ( ) ;
( )
( )
� �
�
�
�
0 75 0 0 5
1 0 0 1
åñëè
åñëè { }
�
��
( , , [ ; ])j � �{ }0 1 0 1� .
3. Ïóñòü p pj j
1 2
0 0( ) ( )( ) ( )� ( , )j � 0 1 . Òîãäà:
1) äëÿ îáëàñòè çíà÷åíèé âåðîÿòíîñòè P
j jj
( )� ( [ ; ])� � 0 1 , êàê ôóíêöèè îò âåðî-
ÿòíîñòè �, èñòèííî ðàâåíñòâî Val P l Ljjj ( ) [ ; ]� � 1 1 , ãäå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 7
l p p p p pj j j j j
1 1 1 2 2 1
1 0 0 0 1 0� � � � �min ( ) ( ) ( ) ; ( )( ) ( ) ( ) ( ) ({ ) ( )( ) ( )0 0
2
p j }, (8)
L p p p p pj j j j j
1 1 1 2 2 1
1 0 0 0 1 0� � � � �max ( ) ( ) ( ) ; ( )( ) ( ) ( ) ( ) ({ ) ( )( ) ( )0 0
2
p j }; (9)
2) èç (8) è (9) âûòåêàåò, ÷òî äëÿ âñåõ çíà÷åíèé � �[ ; ]0 1 , åñëè ëèáî p
k
j( ) ( )0 0�
( , )k � 1 2 , ëèáî p
k
j( ) ( )0 1� ( , )k � 1 2 , òî l1 1� è L1 1� , ò.å. Pjjj ( )� � 1( [ ; ])� � 0 1 ;
3) âåðîÿòíîñòü Pjjj ( )� — ìîíîòîííàÿ ôóíêöèÿ îò âåðîÿòíîñòè �, ïðè÷åì
Pjjj ( )� ìîíîòîííî âîçðàñòàåò, åñëè p j
1
0( ) ( ) � p j
2
0( ) ( ) , è ìîíîòîííî óáûâàåò, åñëè
p pj j
1 2
0 0( ) ( )( ) ( )� ;
4) åñëè p j
1
0 1( ) ( ) � è p j
2
0 0( ) ( ) � , òî Pjjj ( )� �� ( [ ; ])� � 0 1 ;
5) åñëè p j
1
0 0( ) ( ) � è p j
2
0 1( ) ( ) � , òî Pjjj ( )� �� �1 ( [ ; ])� � 0 1 .
Îòìåòèì ðÿä ñëåäñòâèé èç ðàâåíñòâà (5).
1. Âåðîÿòíîñòü Pj j j, , ( )1� � ( , , [ ; ])j � �{ }0 1 0 1� íå çàâèñèò îò âåðîÿòíîñòè âûáî-
ðà êðèïòîàíàëèòèêîì áàçèñíîãî âåêòîðà â áàçèñå B1� j äëÿ èçìåðåíèÿ ïåðåõâà÷åí-
íîãî êóáèòà.
2. Äëÿ âñåõ � �[ ; ]0 1
P
p
j j j
j
, ,
( )
( )
, , , ( ) ,
, , ,
1
2
0 25 0 5 0 0
0 75 0 5
� �
� �
�
�
�
�
åñëè
åñëè p j
2
0 1( ) ( ) �
�
�
��
( , )j � 0 1 .
3. Ïóñòü p j
2
0 0 5( ) ( ) ,� ( , )j � 0 1 . Òîãäà Pj j j, , ( ) ,1 0 5� �� ( [ ; ])� � 0 1 , ò.å. âåðîÿò-
íîñòü Pj j j, , ( )1� � íå çàâèñèò îò âåðîÿòíîñòè �.
4. Ïóñòü p j
2
0 0 5( ) ( ) ,� ( , )j � 0 1 . Òîãäà:
1) äëÿ îáëàñòè çíà÷åíèé âåðîÿòíîñòè P
j j j, ,
( )
1�
� , êàê ôóíêöèè îò âåðîÿòíîñòè �,
èñòèííî ðàâåíñòâî Val P l Lj j j, , ( ) [ ; ]1 2 2� �� , ãäå
l p pj j
2 2 2
0 25 0 5 0 0 75 0 5 0� � �min , , ( ) ; , , ( )( ) ( ){ }, (10)
L p pj j
2 2 2
0 25 0 5 0 0 75 0 5 0� � �max , , ( ) ; , , ( )( ) ( ){ }; (11)
2) âåðîÿòíîñòü Pj j j, , ( )1� � — ìîíîòîííàÿ ôóíêöèÿ îò âåðîÿòíîñòè �, ïðè÷åì
Pj j j, , ( )1� � ìîíîòîííî âîçðàñòàåò, åñëè p j
2
0 0 5( ) ( ) ,� , è ìîíîòîííî óáûâàåò, åñëè
p j
2
0 0 5( ) ( ) ,� ;
3) èç (10) è (11) âûòåêàåò, ÷òî åñëè p j
2
0 0 5( ) ( ) ,� , òî l2 0 5� , è L2 0 5� , , ò.å.
Pj j j, , ( ) ,1 0 5� �� ( [ ; ])� � 0 1 .
Îáîçíà÷èì P1 ( )� ( [ ; ] )� � 0 1 âåðîÿòíîñòü ïðàâèëüíîãî ñ÷èòûâàíèÿ àäðåñàòîì
çíà÷åíèÿ áèòà ïðè óñëîâèè, ÷òî äëÿ îáðàáîòêè äàííîãî êóáèòà îòïðàâèòåëü è àäðå-
ñàò èñïîëüçóþò îäèí è òîò æå áàçèñ, à âåðîÿòíîñòü ïåðåñûëêè îòïðàâèòåëåì ñèìâî-
ëà 0 ðàâíà �.
Òåîðåìà 2. Äëÿ âñåõ � �[ ; ]0 1 èñòèííî ðàâåíñòâî
P p p1 1
0
1
10 25 2 5 1 0 0( ) , ( , ( )( ( ) ( ))( ) ( )� � �� � � � � �
� � � � �( , ) ( ( ) ( )) ( ) ( )( ) ( ) ( ) ( ) (0 5 2 0 0 0 0
2
0
2
1
1
0
2
0
1
1� p p p p p ) ( )( ) ( ))0 0
2
1p . (12)
Äîêàçàòåëüñòâî. Ïîñêîëüêó
P P P P P1 000 111 010 1010 25( ) , ( ( ) ( ) ( ) ( ))� � � � �� � � � ( [ ; ])� � 0 1 ,
âîñïîëüçîâàâøèñü ðàâåíñòâàìè (4) è (5), ïîëó÷èì
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
P p p p p1 1
0
1
0
2
0
1
00 25 1 0 0 0 0( ) , ( ( ) ( ) ( ) ( ( )( ) ( ) ( ) ( )� �� � � � � p
2
0 0( ) ( ))�
� � � � � �1 0 0 0 0 0
1
1
1
1
2
1
1
1
2
1p p p p p( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ( ) ( ))�
� � � � � � � �0 25 0 5 0 5 0 0 25 0 5 0 5
2
0
2
1, , ( , ) ( ) , , ( , ) (( ) ( )� � � �p p 0) �
� � � � � �0 25 2 5 1 0 0
1
0
1
1, ( , ( )( ( ) ( ))( ) ( )� � p p
� � � � �( , )( ( ) ( )) ( ) ( )( ) ( ) ( ) ( ) (0 5 2 0 0 0 0
2
0
2
1
1
0
2
0
1
1� p p p p p ) ( )( ) ( ))0 0
2
1p .
Òåîðåìà äîêàçàíà.
Îòìåòèì ðÿä ñëåäñòâèé èç ðàâåíñòâà (12).
1. Âåðîÿòíîñòü P1 ( )� , êàê ôóíêöèÿ îò âåðîÿòíîñòè �:
1) ÿâëÿåòñÿ ìîíîòîííî âîçðàñòàþùåé ôóíêöèåé, åñëè
p p p p
2
0
2
1
1
0
1
10 0 0 5 1 0 0( ) ( ) ( ) ( )( ) ( ) , ( ( ) ( ))� � � � ,
ïðè÷åì Val P l L1 3 3( ) [ ; ]� � , ãäå
l p p3 1
0
1
10 25 2 5 0 0� � � �, ( , ( ( ) ( ))( ) ( )
� � � �0 5 0 0 0 0 0
2
0
2
1
1
0
2
0
1
1, ( ( ) ( )) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )p p p p p p
2
1 0( ) ( )),
L p p p p3 2
0
2
1
1
0
2
00 25 3 5 15 0 0 0 0� � � �, ( , , ( ( ) ( )) ( ) (( ) ( ) ( ) ( ) ) ( ) ( ))( ) ( )� p p
1
1
2
10 0 ;
2) ÿâëÿåòñÿ ìîíîòîííî óáûâàþùåé ôóíêöèåé, åñëè
p p p p
2
0
2
1
1
0
1
10 0 0 5 1 0 0( ) ( ) ( ) ( )( ) ( ) , ( ( ) ( ))� � � � ,
ïðè÷åì Val P l L1 4 4( ) [ ; ]� � , ãäå
l p p p p4 2
0
2
1
1
0
2
00 25 3 5 15 0 0 0 0� � � �, ( , , ( ( ) ( )) ( ) (( ) ( ) ( ) ( ) ) ( ) ( ))( ) ( )� p p
1
1
2
10 0 ,
L p p4 1
0
1
10 25 2 5 0 0� � � �, ( , ( ( ) ( ))( ) ( )
� � � �0 5 0 0 0 0 0
2
0
2
1
1
0
2
0
1
1, ( ( ) ( )) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )p p p p p p
2
1 0( ) ( )) ;
3) íå çàâèñèò îò çíà÷åíèÿ �, åñëè
p p p p
2
0
2
1
1
0
1
10 0 0 5 1 0 0( ) ( ) ( ) ( )( ) ( ) , ( ( ) ( ))� � � � , (13)
ïðè÷åì
P p p p p1 1
0
1
1
1
0
2
0 25 2 75 0 75 0 0 0( ) , ( , , ( ( ) ( )) ( )( ) ( ) ( )� � � � � ( ) ( ) ( )( ) ( ) ( ))0
1
1
2
10 0 0� p p
( [ ; ])� � 0 1 . (14)
2. Åñëè p
k
j( ) ( )0 0� ( , ; , )j k� �0 1 1 2 , òî P1 0 625 0 250( ) , ,� �� � ( [ ; ])� � 0 1 , ïðè-
÷åì:
1) åñëè � � 0 , òî P1 0 625( ) ,� � ;
2) åñëè � � 0 5, , òî P1 0 750( ) ,� � ;
3) åñëè � � 1, òî P1 0 875( ) ,� � .
3. Åñëè p j
1
0 1( ) ( ) � , p j
2
0 0( ) ( ) � ( , )j � 0 1 , òî P1 0125 0 750( ) , ,� �� � ( [ ; ])� � 0 1 ,
ïðè÷åì:
1) åñëè � � 0 , òî P1 0125( ) ,� � ;
2) åñëè � � 0 5, , òî P1 0 500( ) ,� � ;
3) åñëè � � 1, òî P1 0 875( ) ,� � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 9
4. Åñëè p j
1
0 0( ) ( ) � , p j
2
1 1( ) ( ) � ( , )j � 0 1 , òî P1 0 875 0 750( ) , ,� �� � ( [ ; ])� � 0 1 ,
ïðè÷åì:
1) åñëè � � 0 , òî P1 0 875( ) ,� � ;
2) åñëè � � 0 5, , òî P1 0 500( ) ,� � ;
3) åñëè � � 1, òî P1 0125( ) ,� � .
5. Åñëè p
k
j( ) ( )0 1� ( , ; , )j k� �0 1 1 2 , òî P1 0 875 0 250( ) , ,� �� � ( [ ; ])� � 0 1 , ïðè÷åì:
1) åñëè � � 0 , òî P1 0 875( ) ,� � ;
2) åñëè � � 0 5, , òî P1 0 750( ) ,� � ;
3) åñëè � � 1, òî P1 0 625( ) ,� � .
6. Åñëè p
k
j( ) ( ) ,0 0 5� ( , ; , )j k� �0 1 1 2 , òî P1 0 625( ) ,� � ( [ ; ])� � 0 1 .
Ïðîâåäåííûé àíàëèç ïîêàçûâàåò, ÷òî èç òåîðåìû 2 âûòåêàåò ñëåäñòâèå.
Ñëåäñòâèå 1. Ïðè àòàêå, îïðåäåëÿåìîé ïðåäïîëîæåíèÿìè 1 è 2, åñëè êðèïòî-
àíàëèòèê ðàñïîëàãàåò èíôîðìàöèåé î òîì, êàêîå èç óòâåðæäåíèé, «� � ( ; , )0 0 5 » èëè
«� � ( , ; )0 5 1 », èñòèííî, òî îí âñåãäà ìîæåò âûáðàòü ñâîþ ñòðàòåãèþ òàê, ÷òî:
— â ñðåäíåì ïðèáëèçèòåëüíî 75% êëþ÷à áóäåò ïåðåäàíî àäðåñàòó âåðíî, åñëè
ãåíåðàòîð ïîñëåäîâàòåëüíîñòåé, èñïîëüçóåìûé îòïðàâèòåëåì, áëèçîê ê ïñåâäîñëó-
÷àéíîìó ãåíåðàòîðó;
— â ñðåäíåì ïðèáëèçèòåëüíî 87,5% êëþ÷à ìîæåò áûòü ïåðåäàíî àäðåñàòó âåð-
íî, åñëè ãåíåðàòîð ïîñëåäîâàòåëüíîñòåé, èñïîëüçóåìûé îòïðàâèòåëåì, äàëåê îò
ïñåâäîñëó÷àéíîãî ãåíåðàòîðà.
Òåîðåìà 3. Ïðè àòàêå, îïðåäåëÿåìîé ïðåäïîëîæåíèÿìè 1 è 2, ñóùåñòâóåò ïî êðàé-
íåé ìåðå äâà ñâÿçíûõ êîíòèíóàëüíûõ ìíîæåñòâà òàêèõ ñòðàòåãèé êðèïòîàíàëèòèêà, ÷òî
ïðè ëþáîì çíà÷åíèè � �[ ; ]0 1 â ñðåäíåì 68,75% êëþ÷à áóäåò ïåðåäàíî àäðåñàòó âåðíî.
Äîêàçàòåëüñòâî. Ïîëîæèâ p p
1
0
1
10 0 1( ) ( )( ) ( )� � â (13), ïîëó÷èì p
2
0 0( ) ( )�
� �p
2
1 0 15( ) ( ) , . Ñëåäîâàòåëüíî, ëþáàÿ òàêàÿ ñòðàòåãèÿ êðèïòîàíàëèòèêà, ÷òî
p p
p p
1
0
1
1
2
0
2
1
0 0 1
0 0 15
( ) ( )
( ) ( )
( ) ( ) ,
( ) ( ) , ,
� �
� �
�
�
��
(15)
óäîâëåòâîðÿåò ðàâåíñòâó (13). Ïîäñòàâèâ (15) â (14), ïîëó÷èì
P1 0 25 2 75 0 75 2 15 0 6875( ) , ( , , , ) ,� � � � � � ( [ , ] )� � 0 1 .
Àíàëîãè÷íûì îáðàçîì, ïîäñòàâèâ p p
1
0
1
10 0 0( ) ( )( ) ( )� � â (13), ïîëó÷èì p
2
0 0( ) ( )�
� �p
2
1 0 0 5( ) ( ) , . Ïîýòîìó ëþáàÿ òàêàÿ ñòðàòåãèÿ êðèïòîàíàëèòèêà, ÷òî
p p
p p
1
0
1
1
2
0
2
1
0 0 0
0 0 0 5
( ) ( )
( ) ( )
( ) ( ) ,
( ) ( ) , ,
� �
� �
�
�
��
(16)
òàêæå óäîâëåòâîðÿåò ðàâåíñòâó (13), ïðè÷åì èç (16) è (14) âûòåêàåò
P1 0 25 2 75 0 6875( ) , , ,� � � � ( [ ; ] )� � 0 1 .
Ìíîæåñòâà (15) è (16) ïðåäñòàâëÿþò ñîáîé äâà òàêèõ ñâÿçíûõ êîíòèíóàëüíûõ
ìíîæåñòâà ñòðàòåãèé êðèïòîàíàëèòèêà, ÷òî ïðè ëþáîì çíà÷åíèè � �[ ; ]0 1 â ñðåäíåì
68,75% êëþ÷à áóäåò ïåðåäàíî àäðåñàòó âåðíî.
Òåîðåìà äîêàçàíà.
3. ÀÒÀÊÀ ÏÐÈ ÓÏÐÀÂËÅÍÈÈ ÈÇÌÅÍÅÍÈÅÌ ÁÀÇÈÑÎÂ ÎÒÏÐÀÂÈÒÅËß È ÀÄÐÅÑÀÒÀ
Èññëåäóåì àòàêó íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à, îïðåäåëÿåìóþ ïðåäïî-
ëîæåíèÿìè 1–3.
Îáîçíà÷èì P2 ( )� ( [ ; ] )� � 0 1 âåðîÿòíîñòü ïðàâèëüíîãî ñ÷èòûâàíèÿ àäðåñàòîì çíà-
÷åíèÿ áèòà ïðè óñëîâèè, ÷òî ïðè îáðàáîòêå äàííîãî êóáèòà îòïðàâèòåëü è àäðåñàò èñ-
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ïîëüçóþò îäèí è òîò æå áàçèñ B j ( , )j � 0 1 , âåðîÿòíîñòü ïåðåñûëêè ñèìâîëà 0 îòïðà-
âèòåëåì ðàâíà �, à âåðîÿòíîñòü îäíîâðåìåííîãî èçìåíåíèÿ êðèïòîàíàëèòèêîì êàê
ó îòïðàâèòåëÿ, òàê è ó àäðåñàòà áàçèñà B j ( , )j � 0 1 íà áàçèñ B1� j ðàâíà p j0 ( ) .
Òåîðåìà 4. Äëÿ âñåõ � �[ ; ]0 1 èñòèííî ðàâåíñòâî
P P P P P2 000 111 010 1010 25( ) , ( ( ) ( ) ( ) ( )� � � � �� � � � �
� � � � �( ( ) ( )) ( ( ) ( ) ( ) ( )))p p P P P P0 0 000 010 101 1111 0 � � � � . (17)
Äîêàçàòåëüñòâî. Ïóñòü ïðè îáðàáîòêå î÷åðåäíîãî êóáèòà îòïðàâèòåëü è àäðå-
ñàò ñ÷èòàþò, ÷òî îíè èñïîëüçóþò îäèí è òîò æå áàçèñ B j ( , )j � 0 1 , à êðèïòîàíàëèòèê
èñïîëüçóåò áàçèñ Bh ( , )h � 0 1 . Òîãäà ïðè àòàêå, îïðåäåëÿåìîé ïðåäïîëîæåíèÿìè 1–3,
äëÿ âñåõ � �[ ; ]0 1 âåðîÿòíîñòü ïðàâèëüíîãî ñ÷èòûâàíèÿ àäðåñàòîì çíà÷åíèÿ áèòà ðàâ-
íà ( ( )) ( ) ( ) ( ), ,1 0 0 1 1� � � �p j P p j Pjhj j h j� � . Ñëåäîâàòåëüíî, äëÿ âñåõ � �[ ; ]0 1 èìååì
P p j P p j Pjhj
hj
j h2 0
0
1
0
1
0 1 10 25 1( ) , ( ( )) ( ) ( ) , ,� �� � �
��
��� �
�
�
�
�
�
�
�
�
�j ( )�
� � � �0 25 1 0 00 000 0 101, (( ( )) ( ) ( ) ( )p P p P� �
� � � �( ( )) ( ) ( ) ( )1 0 00 010 0 111p P p P� � ( ( )) ( ) ( ) ( )1 1 10 101 0 000� � �p P p P� �
� � � �( ( )) ( ) ( ) ( ))1 1 10 111 0 010p P p P� �
� � � � �0 25 000 111 010 101, ( ( ) ( ) ( ) ( )P P P P� � � �
� � � � �( ( ) ( ))( ( ) ( ) ( ) ( )))p p P P P P0 0 000 010 101 1111 0 � � � � .
Òåîðåìà äîêàçàíà.
Èç (17) âûòåêàþò äâà ñëåäñòâèÿ.
Ñëåäñòâèå 2. Íåðàâåíñòâî P P2 1( ) ( )� �� ( [ ; ] )� � 0 1 èñòèííî òîãäà è òîëüêî
òîãäà, êîãäà ëèáî
P P P P
p p
000 010 101 111
0 0
0
1 0 0
( ) ( ) ( ) ( ) ,
( ) ( ) ,
� � � �� � � �
� �
�
�
ëèáî
P P P P
p p
000 010 101 111
0 0
0
1 0 0
( ) ( ) ( ) ( ) ,
( ) ( ) .
� � � �� � � �
� �
�
�
.
Ñëåäñòâèå 3. Ðàâåíñòâî P P2 1( ) ( )� �� ( [ ; ] )� � 0 1 èñòèííî òîãäà è òîëüêî òîãäà,
êîãäà p p0 01 0( ) ( )� èëè êîãäà P P P P000 010 111 101 0( ) ( ) ( ) ( )� � � �� � � � .
Èòàê, ïîêàçàíî, ÷òî äîïîëíèòåëüíàÿ âîçìîæíîñòü êðèïòîàíàëèòèêà óïðàâëÿòü
îäíîâðåìåííûì èçìåíåíèåì áàçèñîâ îòïðàâèòåëÿ è àäðåñàòà ìîæåò óñèëèòü åãî
àòàêó íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à.
Ïîäñòàâèâ (4) è (5) â (17), ïîëó÷èì, ÷òî äëÿ âñåõ � �[ ; ]0 1
P p p2 1
0
1
10 25 2 5 1 0 0( ) , ( , ( )( ( ) ( ))( ) ( )� � �� � � � � �
� � � � �( , )( ( ) ( )) ( ) ( )( ) ( ) ( ) ( ) (0 5 2 0 0 0 0
2
0
2
1
1
0
2
0
1
1� p p p p p ) ( )( ) ( )0 0
2
1p �
� � � �( ( ) ( ))( ( ) ( ) ( ) ( )( ) ( ) ( ) ( )p p p p p p0 0 1
0
2
0
1
1
2
11 0 0 0 0 0
� � � � � �( )( ( ) ( )) ( , )( ( ) (( ) ( ) ( ) ( )� �1 0 0 0 5 2 0
1
0
1
1
2
0
2
1p p p p 0)))) . (18)
Èç (18) âûòåêàåò, ÷òî âåðîÿòíîñòü P2 ( )� ( [ ; ])� � 0 1 , êàê ôóíêöèÿ îò âåðîÿòíîñòè �:
1) ìîíîòîííî âîçðàñòàåò, åñëè
1 1 1 0 0 2 00 0 1
0
2
0� � � � �( ( ) ( ))( ( ) ( ))( ) ( )p p p p
� � � � �( ( ) ( ))( ( ) ( ))( ) ( )1 1 0 0 2 0 00 0 1
1
2
1p p p p ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 11
2) ìîíîòîííî óáûâàåò, åñëè
1 1 1 0 0 2 00 0 1
0
2
0� � � � �( ( ) ( ))( ( ) ( ))( ) ( )p p p p
� � � � �( ( ) ( ))( ( ) ( ))( ) ( )1 1 0 0 2 0 00 0 1
1
2
1p p p p .
Òàêèì îáðàçîì, åñëè â ïðîöåññå ïåðåäà÷è êëþ÷à îòïðàâèòåëü óïðàâëÿåò âåðî-
ÿòíîñòüþ � ïåðåñûëêè ñèìâîëà 0, à êðèïòîàíàëèòèêó èçâåñòåí ýòîò çàêîí óïðàâëå-
íèÿ, òî êðèïòîàíàëèòèê ðàñïîëàãàåò âîçìîæíîñòüþ ïîäîáðàòü àäàïòèâíóþ ñòðàòå-
ãèþ àòàêè íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à, îïðåäåëÿåìîé ïðåäïîëîæåíèÿ-
ìè 1–3, íàïðàâëåííóþ ëèáî íà ìàêñèìèçàöèþ, ëèáî íà ìèíèìèçàöèþ êîëè÷åñòâà
ïðàâèëüíî ïðî÷èòàííûõ àäðåñàòîì ñèìâîëîâ.
Ïîäâîäÿ èòîã, çàêëþ÷àåì, ÷òî àòàêà íà êâàíòîâûé ïðîòîêîë ïåðåäà÷è êëþ÷à,
îïðåäåëÿåìàÿ ïðåäïîëîæåíèÿìè 1–3, ìîæåò ñóùåñòâåííî óñëîæíèòü ðàáîòó ëå-
ãàëüíûõ ïîëüçîâàòåëåé.
4. ØÈÔÐ ÍÀ ÎÑÍÎÂÅ ÀËÃÎÐÈÒÌÀ ÏËÎÒÍÎÃÎ ÊÎÄÈÐÎÂÀÍÈß
Çàäà÷à ïëîòíîãî êîäèðîâàíèÿ ñîñòîèò â òîì, ÷òî îòïðàâèòåëü äîëæåí ïåðåñëàòü
àäðåñàòó 2-áèòîâóþ ïîñëåäîâàòåëüíîñòü � �1 2 , èñïîëüçóÿ ñèñòåìó èç äâóõ êóáè-
òîâ | ( | | ),�� � � � ��2 00 110 5 . Ïðè ýòîì ïåðâûé êóáèò íàõîäèòñÿ ó îòïðàâèòåëÿ,
à âòîðîé — ó àäðåñàòà.
Àëãîðèòì ïëîòíîãî êîäèðîâàíèÿ ñîñòîèò â ñëåäóþùåì. Â çàâèñèìîñòè îò çíà-
÷åíèÿ ïåðåäàâàåìîé ïîñëåäîâàòåëüíîñòè � �1 2 ( , , )� �1 2 0 1�{ } îòïðàâèòåëü âûïîë-
íÿåò íàä ñâîèì êóáèòîì òàêîå óíèòàðíîå ïðåîáðàçîâàíèå U� �1 2
( , , )� �1 2 0 1�{ }
(à ñëåäîâàòåëüíî, íàä ñèñòåìîé | �� âûïîëíÿåòñÿ óíèòàðíîå ïðåîáðàçîâàíèå
U I� �1 2
� ( , , )� �1 2 0 1�{ } , ãäå � — òåíçîðíîå ïðîèçâåäåíèå, I — òîæäåñòâåííîå
ïðåîáðàçîâàíèå), ÷òî
U I00 � , U X01
0 1
1 0
� �
�
�
��
�
�
�� , U Y10
0 1
1 0
� �
�
�
�
��
�
�
�� , U Z11
1 0
0 1
� �
�
�
�
��
�
�
�� .
Ïîñëå ýòîãî îòïðàâèòåëü ïåðåñûëàåò ïî êâàíòîâîìó êàíàëó ñâîé êóáèò àäðåñàòó.
Àäðåñàò ïðèìåíÿåò ê ñèñòåìå êóáèòîâ óíèòàðíîå ïðåîáðàçîâàíèå
Cnot �
�
�
�
�
�
��
�
�
�
�
�
��
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
,
èçìåðÿåò âòîðîé êóáèò, ïðèìåíÿåò ê ïåðâîìó êóáèòó ïðåîáðàçîâàíèå Àäàìàðà
H �
�
�
�
�
�
�
�
�
�
� �
� �
2 2
2 2
0 5 0 5
0 5 0 5
, ,
, ,
,
à çàòåì èçìåðÿåò ïåðâûé êóáèò. Äåêîäèðîâàíèå àäðåñàòîì ïåðåäàííîé 2-áèòî-
âîé ïîñëåäîâàòåëüíîñòè îñóùåñòâëÿåòñÿ â ñîîòâåòñòâèè ñî ñëåäóþùåé ñõåìîé:
|
|
|
|
00 00
01 01
10 11
11 10
� �
� �
� �
� �
�
�
�
�
�
�
. (19)
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Òåîðåìà 5. Àëãîðèòì ïëîòíîãî êîäèðîâàíèÿ îñòàåòñÿ êîððåêòíûì, åñëè èñ-
õîäíàÿ ñèñòåìà èç äâóõ êóáèòîâ èìååò âèä | ( | | ),�� � � � ��2 01 100 5 . Ïðè ýòîì ñõåìà
äåêîäèðîâàíèÿ àäðåñàòîì ïåðåäàííîé 2-áèòîâîé ïîñëåäîâàòåëüíîñòè èìååò âèä
|
|
|
|
00 01
01 00
10 10
11 11
� �
� �
� �
� �
�
�
�
�
�
�
. (20)
Äîêàçàòåëüñòâî. Â ñîîòâåòñòâèè ñ àëãîðèòìîì ïëîòíîãî êîäèðîâàíèÿ ïîñëå
ïðèìåíåíèÿ îòïðàâèòåëåì óíèòàðíîãî ïðåîáðàçîâàíèÿ ê ïåðâîìó êóáèòó ïîëó÷èì
( )(| ) ( )(| ) ( | | ),U I I I00
0 52 01 10� � � � � � � � ��� � ,
( )(| ) ( )(| )U I X I01 � � � � � �� �
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�2
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
0
1
1
0
0 5, �
�
��
�
�
�
�
�
�
��
�
�
�
�
�
��
� � � �� �2
1
0
0
1
2 00 110 5 0 5, , ( | | ) ,
( )(| ) ( )(| )U I Y I10 � � � � � �� �
�
�
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�2
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
0
1
1
0
0 5,
�
�
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
�
��
� � � �� �2
1
0
0
1
2 00 110 5 0 5, , ( | | ) ,
( )(| ) ( )(| )U I Z I11 � � � � � �� �
�
�
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�2
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0
1
1
0
0 5,
�
�
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
�
��
� � � �� �2
0
1
1
0
2 01 100 5 0 5, , ( | | ) .
Ïîñëå òîãî êàê îòïðàâèòåëü ïåðåøëåò ïî êâàíòîâîìó êàíàëó ñâîé êóáèò àäðå-
ñàòó, à àäðåñàò ïðèìåíèò ê ñèñòåìå êóáèòîâ óíèòàðíîå ïðåîáðàçîâàíèå Cnot ,
ïîëó÷èì
Cnot ( ( | | )),2 01 100 5� � � � �
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�2
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
0
1
1
0
0 5, �
�
��
�
�
�
�
�
�
��
�
�
�
�
�
��
�2
0
1
0
1
0 5, � � � ��2 01 110 5, ( | | ) ,
Cnot ( ( | | )),2 00 110 5� � � � �
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�2
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
1
0
0
1
0 5, �
�
��
�
�
�
�
�
�
��
�
�
�
�
�
��
�2
1
0
1
0
0 5, � � � ��2 00 100 5, ( | | ) ,
Cnot ( ( | | )),2 00 110 5� � � � �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 13
�
�
�
�
�
�
��
�
�
�
�
�
�� �
�
�
�
�
�
��
�
�
�2
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
1
0
0
1
0 5,
�
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
�
��
�2
1
0
1
0
0 5, � � � ��2 00 100 5, ( | | ) ,
Cnot ( ( | | )),2 00 110 5� � � � �
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
�
��
�
�
�2
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
0
1
1
0
0 5,
�
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
�
��
�2
0
1
0
1
0 5, � � � ��2 01 110 5, ( | | ) .
Ïîñëå èçìåðåíèÿ âòîðîãî êóáèòà àäðåñàò ïðèõîäèò ê âûâîäó:
1) åñëè ðåçóëüòàò èçìåðåíèÿ ðàâåí |1�, òî ïåðåäàíà ïîñëåäîâàòåëüíîñòü 00 èëè 11;
2) åñëè ðåçóëüòàò èçìåðåíèÿ ðàâåí | 0�, òî ïåðåäàíà ïîñëåäîâàòåëüíîñòü 01èëè 10.
Ýòîò âûâîä ìîæåò áûòü ïðåäñòàâëåí ðàçáèåíèåì �1 00 11 01 10� { }, ; , .
Ïîñëå ïðèìåíåíèÿ ê ïåðâîìó êóáèòó ïðåîáðàçîâàíèÿ Àäàìàðà èìååì
H ( ( | | )),2 0 1 2
1 1
1 1
1
1
2
2
0
0 5 1 1� � �� � � �
�
�
�
��
�
�
��
�
�
��
�
�
�� �
�
�
��
�
�
�� �
�
�
��
�
�
�� � �
1
0
0| ,
H ( ( | | )),2 0 1 2
1 1
1 1
1
1
2
00 5 1 1� � �� � � �
�
�
�
��
�
�
�� �
�
�
��
�
�
�� �
2
0
1
1
�
�
��
�
�
�� �
�
�
��
�
�
�� � �| .
Èçìåðèâ ïåðâûé êóáèò, àäðåñàò ïðèõîäèò ê âûâîäó:
1) åñëè ðåçóëüòàò èçìåðåíèÿ ðàâåí | 0�, òî ïåðåäàíà ïîñëåäîâàòåëüíîñòü 00 èëè 01;
2) åñëè ðåçóëüòàò èçìåðåíèÿ ðàâåí |1�, òî ïåðåäàíà ïîñëåäîâàòåëüíîñòü 10 èëè 11.
Ýòîò âûâîä ìîæíî ïðåäñòàâèòü ðàçáèåíèåì � 2 00 01 10 11� { }, ; , .
Òàêèì îáðàçîì, èñõîäíàÿ äâîè÷íàÿ ïîñëåäîâàòåëüíîñòü èäåíòèôèöèðóåòñÿ
åäèíñòâåííûì îáðàçîì (òàê êàê � �1 2 00 01 10 11� � { }; ; ; ). Ïðè ýòîì (20) ïðåäñòàâ-
ëÿåò ñõåìó äåêîäèðîâàíèÿ ðåçóëüòàòîâ èçìåðåíèÿ êóáèòîâ àäðåñàòîì.
Òåîðåìà äîêàçàíà.
Èç òåîðåìû 5 âûòåêàåò êîððåêòíîñòü êâàíòîâîãî àëãîðèòìà Cêâ øèôðîâàíèÿ 2n-áè-
òîâîé ïîñëåäîâàòåëüíîñòè � � � � � �1 2 3 4 2 1 2� n n� ïîñðåäñòâîì ñèñòåìû èç 2n êóáèòîâ.
Ïóñòü n-áèòîâàÿ ïîñëåäîâàòåëüíîñòü � �1 � n — ñåêðåòíûé ñåàíñîâûé êëþ÷,
èìåþùèéñÿ è ó îòïðàâèòåëÿ, è ó àäðåñàòà. Îòïðàâèòåëü ïîäãîòàâëèâàåò èñõîäíóþ
ñèñòåìó èç 2n êóáèòîâ, èìåþùóþ âèä � � �2 1n n� � �� , ãäå
�
� �
� �
i
i
i
�
�
�
�
�
, ,
,
åñëè
åñëè
0
1
( , , )i n� 1 � .
Ïî êâàíòîâîìó êàíàëó îòïðàâèòåëü ïåðåñûëàåò àäðåñàòó êóáèòû ñ ÷åòíûìè íîìå-
ðàìè. Ïîñëå ýòîãî îòïðàâèòåëü ïðåîáðàçóåò êàæäûé êóáèò ñ íå÷åòíûì íîìåðîì â ñîîò-
âåòñòâèè ñ àëãîðèòìîì ïëîòíîãî êîäèðîâàíèÿ, çàòåì ïåðåñûëàåò ïðåîáðàçîâàííûå êó-
áèòû àäðåñàòó. Àäðåñàò, ïîëó÷èâ èõ, êîìïîíóåò ïàðû ñîîòâåòñòâóþùèõ êóáèòîâ, à çà-
òåì îáðàáàòûâàåò êàæäóþ ïàðó â ñîîòâåòñòâèè ñ àëãîðèòìîì ïëîòíîãî êîäèðîâàíèÿ.
5. ÀÍÀËÈÇ ØÈÔÐÀ Cêâ
Èññëåäóåì âû÷èñëèòåëüíóþ ñòîéêîñòü øèôðà Cêâ ïðè àòàêå íà êâàíòîâûé êàíàë,
ñîñòîÿùåé â òîì, ÷òî êðèïòîàíàëèòèê, ïðåäñòàâèâøèñü àäðåñàòîì, ïåðåõâàòûâàåò
êóáèòû, ïåðåñûëàåìûå îòïðàâèòåëåì.
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Èç (19) è (20) âûòåêàåò, ÷òî åñëè êðèïòîàíàëèòèê âûáðàë íå òó ñõåìó äåêîäè-
ðîâàíèÿ, òî îí ïðàâèëüíî ðàñøèôðîâûâàåò áèò ñ íå÷åòíûì íîìåðîì è íåïðàâèëü-
íî — áèò ñ ÷åòíûì íîìåðîì.
Ïóñòü pi �[ , ]0 1 ( , , )i n� 1 � — âåðîÿòíîñòü òîãî, ÷òî â ïðîöåññå ïåðåäà÷è
2n-áèòîâîé ïîñëåäîâàòåëüíîñòè � � � � � �1 2 3 4 2 1 2� n n� , çàøèôðîâàííîé ñ ïî-
ìîùüþ øèôðà Cêâ, êðèïòîàíàëèòèê ïðàâèëüíî îïðåäåëÿåò i-é áèò ñåêðåòíîãî ñåàí-
ñîâîãî êëþ÷à � �1 � n .
Òåîðåìà 6. Âåðîÿòíîñòü P p pn k n2 1, ( , , )� ( , , , )k n� 0 1 � òîãî, ÷òî â ïðîöåññå
ðàñøèôðîâêè 2n-áèòîâîé ïîñëåäîâàòåëüíîñòè, çàøèôðîâàííîé ïîñðåäñòâîì øèôðà
Cêâ, êðèïòîàíàëèòèê ïîëó÷èò ïîñëåäîâàòåëüíîñòü, îòñòîÿùóþ îò èñõîäíîé ïîñëå-
äîâàòåëüíîñòè íà ðàññòîÿíèè k ( )0 � �k n ïî Õåììèíãó, ðàâíà
P p p r rn k n n
i i nk
2 1 1
1 1
, ( , , )� �
�
�
� � � �
� ( , , , )k n� 0 1 � , (21)
ãäå
r
p i i i
p i i i
i
i k
i k
�
� �
�
�
�
1 1
1
, , ,
, , ,
åñëè { },
åñëè { }.
�
�
(22)
Äîêàçàòåëüñòâî. Ðåçóëüòàò ðàñøèôðîâêè êðèïòîàíàëèòèêîì 2n-áèòîâîé ïîñëåäîâà-
òåëüíîñòè, çàøèôðîâàííîé ïîñðåäñòâîì øèôðà Cêâ, îòñòîèò îò èñõîäíîé ïîñëåäîâàòåëü-
íîñòè íà ðàññòîÿíèè k ( )0 � �k n ïî Õåììèíãó òîãäà è òîëüêî òîãäà, êîãäà êðèïòîàíàëè-
òèê íåïðàâèëüíî îïðåäåëÿåò â òî÷íîñòè k áèò ñåêðåòíîãî ñåàíñîâîãî êëþ÷à � �1 � n .
Âåðîÿòíîñòü òîãî, ÷òî êðèïòîàíàëèòèê íåïðàâèëüíî îïðåäåëÿåò áèòû ñåêðåò-
íîãî êëþ÷à, èìåþùèå íîìåðà i ik1 , ,� ( )1 1� � � �i i nk� , è ïðàâèëüíî îïðåäåëÿåò
áèòû ñåêðåòíîãî êëþ÷à, èìåþùèå íîìåðà, ïðèíàäëåæàùèå ìíîæåñòâó
Nn ki i\ , ,{ }1 � , ðàâíà r rn1 � , ãäå ri ( , , )i n� 1 � îïðåäåëÿåòñÿ â ñîîòâåòñòâèè ñ (22).
Ñëåäîâàòåëüíî,
P p p r rn k n n
i i nk
2 1 1
1 1
, ( , , )� �
�
�
� � � �
� ( , , , )k n� 0 1 � .
Òåîðåìà äîêàçàíà.
Äëÿ âñåõ p �[ , ]0 1 ïîëîæèì
P p P p pn k n k
n
2 2, ,( ) ( , , )� �
��� ��
ðàç
( )0 � �k n . (23)
Ñëåäñòâèå 4. Äëÿ âñåõ p �[ , ]0 1 , n �N è k � �Z ( )0 � �k n èñòèííû ðàâåíñòâà
P p
n
k
p pn k
k n k
2 1, ( ) ( )�
�
�
��
�
�
�� � � ( )0 � �k n .
(24)
Äîêàçàòåëüñòâî. Ïîäñòàâèâ p p pn1 � � �� â (22), ïîëó÷èì
r
p i i i
p i i i
i
k
k
�
� �
�
�
�
1 1
1
, , ,
, , ,
åñëè { },
åñëè { }.
�
�
(25)
Ïîäñòàâèâ (25) â (21), èìååì
P p p p pn k n
i i n
k n k
k
2 1
1 1
1, ( , , ) ( )�
�
� � �
� � � �
��
� � �
�
�
��
�
�
�� ��
� � � �
��( ) ( )1 1 1
1 1
p p
n
k
p pk n k
i i n
k n k
k�
.
(26)
Èç (23) è (26) âûòåêàåò (24).
Ñëåäñòâèå äîêàçàíî.
Ïóñòü k p
n k2 ,
( )cp — ñðåäíåå ÷èñëî îøèáîê, äîïóñêàåìûõ êðèïòîàíàëèòèêîì
â ïðîöåññå ðàñøèôðîâêè 2n-áèòîâîé ïîñëåäîâàòåëüíîñòè, çàøèôðîâàííîé ïîñðåä-
ñòâîì øèôðà Cêâ, ïðè óñëîâèè, ÷òî p p pn1 � � �� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 15
Ñëåäñòâèå 5. Äëÿ âñåõ p �[ , ]0 1 , n �N è k � �Z ( )0 � �k n èñòèííî ðàâåíñòâî
k p n p
n k2
1
,
( ) ( ).cp � � (27)
Äîêàçàòåëüñòâî. Ïðè ôèêñèðîâàííûõ çíà÷åíèÿõ ÷èñåë p �[ , ]0 1 , n �N è
k � �Z ( )0 � �k n ïðàâàÿ ÷àñòü ôîðìóëû (24) ïðåäñòàâëÿåò ñîáîé ñõåìó Áåðíóëëè
ñ âåðîÿòíîñòüþ ñîáûòèÿ â êàæäîì èñïûòàíèè, ðàâíîé 1� p. Ïîäñòàâèâ â ôîðìóëó
äëÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ áèíîìèàëüíîãî ðàñïðåäåëåíèÿ âìåñòî âåðîÿòíîñòè
çíà÷åíèå 1� p, ïîëó÷èì (27).
Ñëåäñòâèå äîêàçàíî.
Ñëó÷àé p � 0 5, ñîîòâåòñòâóåò ñèòóàöèè, êîãäà ñåêðåòíûé ñåàíñîâûé êëþ÷
� �1 � n — ñëó÷àéíàÿ ïîñëåäîâàòåëüíîñòü, à êðèïòîàíàëèòèê îïðåäåëÿåò çíà÷åíèå
êàæäîãî áèòà êëþ÷à ñëó÷àéíûì îáðàçîì. Èç (24) è (27) ñëåäóåò
P
n
k
n k
n
2 0 5 0 5, ( , ) ( , )�
�
�
��
�
�
�� ( )0 � �k n ,
k n
n k2
0 5 0 5
,
( , ) ,cp � . (28)
Èç (28) âûòåêàþò äâà ñëåäñòâèÿ.
Ñëåäñòâèå 6. Åñëè ñåêðåòíûé ñåàíñîâûé êëþ÷ � �1 � n — ñëó÷àéíàÿ ïîñëåäî-
âàòåëüíîñòü, à êðèïòîàíàëèòèê îïðåäåëÿåò çíà÷åíèå êàæäîãî áèòà êëþ÷à ñëó÷àé-
íûì îáðàçîì, òî â ïðîöåññå ðàñøèôðîâêè 2n-áèòîâîé ïîñëåäîâàòåëüíîñòè, çàøèô-
ðîâàííîé ïîñðåäñòâîì øèôðà Cêâ, â ñðåäíåì 25% ïåðåäàííîé ïîñëåäîâàòåëüíîñòè
ðàñøèôðîâûâàåòñÿ êðèïòîàíàëèòèêîì íåïðàâèëüíî.
Ñëåäñòâèå 7. Åñëè ñåêðåòíûé ñåàíñîâûé êëþ÷ � �1 � n — ñëó÷àéíàÿ ïîñëåäî-
âàòåëüíîñòü, à êðèïòîàíàëèòèê îïðåäåëÿåò çíà÷åíèå êàæäîãî áèòà êëþ÷à ñëó÷àé-
íûì îáðàçîì, òî â ïðîöåññå ðàñøèôðîâêè 2n-áèòîâîé ïîñëåäîâàòåëüíîñòè, çàøèô-
ðîâàííîé ïîñðåäñòâîì øèôðà Cêâ, äëÿ êîððåêöèè ðàñøèôðîâàííîãî øèôðòåêñòà
êðèïòîàíàëèòèê âûíóæäåí, â ñðåäíåì, îñóùåñòâëÿòü ïîëíûé ïåðåáîð âàðèàíòîâ ïî
÷åòâåðòè äëèíû øèôðòåêñòà.
Ïîëó÷åííûå ðåçóëüòàòû ïîêàçûâàþò, ÷òî ïîñòðîåííûé êâàíòîâûé øèôð Cêâ îá-
ëàäàåò äîñòàòî÷íî âûñîêîé âû÷èñëèòåëüíîé ñòîéêîñòüþ, åñëè ñåêðåòíûé ñåàíñîâûé
êëþ÷ � �1 � n — ïîñëåäîâàòåëüíîñòü, áëèçêàÿ ê ñëó÷àéíîé ïîñëåäîâàòåëüíîñòè.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå èññëåäîâàíà âû÷èñëèòåëüíàÿ ñòîéêîñòü äâóõ ìîäåëüíûõ çàäà÷ êâàíòî-
âûõ âû÷èñëåíèé, èìåþùèõ íåïîñðåäñòâåííîå îòíîøåíèå ê ðàçðàáîòêå ìîäåëåé è
ìåòîäîâ êâàíòîâîé êðèïòîãðàôèè, à èìåííî: êëàññè÷åñêîãî êâàíòîâîãî ïðîòîêî-
ëà ïåðåäà÷è êëþ÷à è øèôðà, ïîñòðîåííîãî íà îñíîâå êëàññè÷åñêîãî àëãîðèòìà
ïëîòíîãî êîäèðîâàíèÿ. Ïîêàçàíî, ÷òî äëÿ êâàíòîâîãî ïðîòîêîëà ïåðåäà÷è êëþ÷à
ðàñøèðåíèå âîçìîæíîñòåé êðèïòîàíàëèòèêà çà ñ÷åò óïðàâëåíèÿ âåðîÿòíîñòÿìè
âûáîðà áàçèñíûõ âåêòîðîâ äëÿ èçìåðåíèÿ êóáèòà, à òàêæå îäíîâðåìåííîãî èçìå-
íåíèÿ áàçèñîâ îòïðàâèòåëÿ è àäðåñàòà ìîæåò çíà÷èòåëüíî óñèëèòü åãî àòàêó íà
ýòîò ïðîòîêîë. Ýôôåêòèâíîñòü òàêîé àòàêè ñóùåñòâåííî çàâèñèò îò ãåíåðàòîðà
ïîñëåäîâàòåëüíîñòåé, èìåþùåãîñÿ ó îòïðàâèòåëÿ. Áîëåå òîíêèé àíàëèç ýòîé çà-
âèñèìîñòè — îäíî èç âîçìîæíûõ íàïðàâëåíèé äàëüíåéøèõ èññëåäîâàíèé. Âòî-
ðîå íàïðàâëåíèå ñâÿçàíî ñ àíàëèçîì çàâèñèìîñòè âåðîÿòíîñòè P2 ( )� îò çíà÷åíèé
âåðîÿòíîñòåé p ij
1
( ) ( ) , p ij
2
( ) ( ) , p j0 ( ) ( , , )i j �{ }0 1 è �.
Ïðåäëîæåííûé øèôð, ïîñòðîåííûé íà àëãîðèòìå ïëîòíîãî êîäèðîâàíèÿ, èìå-
åò äîñòàòî÷íî âûñîêóþ âû÷èñëèòåëüíóþ ñòîéêîñòü. Äëÿ ýòîãî øèôðà åñòåñòâåííî
îáîáùåíèå ïîëó÷åííûõ ðåçóëüòàòîâ íà ñëó÷àé, êîãäà ñîñòîÿíèå êàæäîé êâàíòîâîé
÷àñòèöû ïðåäñòàâëåíî âåêòîðîì h-ìåðíîãî êîìïëåêñíîãî ïðîñòðàíñòâà, ÷òî ìîæåò
áûòü òðåòüèì íàïðàâëåíèåì èññëåäîâàíèé. ×åòâåðòîå íàïðàâëåíèå ñâÿçàíî ñ ðàçðàáîò-
êîé êâàíòîâûõ ïðîòîêîëîâ, ïðåäíàçíà÷åííûõ äëÿ ýôôåêòèâíîãî îáíàðóæåíèÿ àòàêè íà
êàê ìîæíî áîëåå ðàííåì ýòàïå ïðîöåññà ïåðåäà÷è èíôîðìàöèè.
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Î æ è ã î â Þ . È . Êâàíòîâûå âû÷èñëåíèÿ. — Ì.: ÌÃÓ, 2003. — 104 ñ.
2. Í è ë ü ñ å í Ì . , × à í ã È . Êâàíòîâûå âû÷èñëåíèÿ è êâàíòîâàÿ èíôîðìàöèÿ. — Ì.: Ìèð, 2006. —
824 ñ.
3. R i e f f e l E . , P o l l a k W . An introduction to quantum computing for non-physicists // ACM Computing
Surveys. — 2000. — 32, N 3. — P. 300–335.
4. B e n n e t t C . H . , B r a s s a r d G . Quantum public key distribution system // IBM Techn. Disclosure
Bull. — 1985. — 28. — P. 3153–3164.
5. B e n n e t t C . H . , B r a s s a r d G . Quantum public key distribution reinvented // SIGACT News. —
1987. — 18, N 4. — P. 51–53.
6. Î ñ í î â û êðèïòîãðàôèè / À.Ï. Àëôåðîâ, À.Þ. Çóáîâ, À.Ñ. Êóçüìèí è äð. — Ì.: Ãåëèîñ ÀÐÂ, 2002.
— 480 ñ.
Ïîñòóïèëà 21.01.2009
|
| id | nasplib_isofts_kiev_ua-123456789-45642 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:30:33Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скобелев, В.Г. 2013-06-17T06:08:44Z 2013-06-17T06:08:44Z 2010 О вычислительной стойкости квантовых алгоритмов преобразования информации / В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 6. — С. 3–17. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45642 518.6+681.3 Досліджено обчислювальну стійкість квантового протоколу переказу ключа, припускаючи, що криптоаналітик керує ймовірностями вибору базисних векторів, а також одночасною зміною базисів у відправника та адресата. Побудовано квантовий шифр, що базується на квантовому алгоритмі щільного кодування. Встановлено, що цей шифр обчислювально стійкий, якщо секретний сеансовий ключ є послідовністю, близькою до випадкової послідовності. The computational complexity of a quantum key distribution protocol is investigated under the assumption that the cryptanalyst can control the probabilities of selection of the basic vectors for qubit measurement, as well as of simultaneous change of bases of the sender and the receiver. A cipher based on the dense coding algorithm is introduced. It is established that this cipher is computationally secure if the secret key is a near-random sequence. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика О вычислительной стойкости квантовых алгоритмов преобразования информации Про обчислювальну стійкість квантових алгоритмів перетворення інформації On computational complexity of quantum algorithms for transformation of information Article published earlier |
| spellingShingle | О вычислительной стойкости квантовых алгоритмов преобразования информации Скобелев, В.Г. Кибернетика |
| title | О вычислительной стойкости квантовых алгоритмов преобразования информации |
| title_alt | Про обчислювальну стійкість квантових алгоритмів перетворення інформації On computational complexity of quantum algorithms for transformation of information |
| title_full | О вычислительной стойкости квантовых алгоритмов преобразования информации |
| title_fullStr | О вычислительной стойкости квантовых алгоритмов преобразования информации |
| title_full_unstemmed | О вычислительной стойкости квантовых алгоритмов преобразования информации |
| title_short | О вычислительной стойкости квантовых алгоритмов преобразования информации |
| title_sort | о вычислительной стойкости квантовых алгоритмов преобразования информации |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45642 |
| work_keys_str_mv | AT skobelevvg ovyčislitelʹnoistoikostikvantovyhalgoritmovpreobrazovaniâinformacii AT skobelevvg proobčislûvalʹnustíikístʹkvantovihalgoritmívperetvorennâínformacíí AT skobelevvg oncomputationalcomplexityofquantumalgorithmsfortransformationofinformation |