Криптографические преобразования нешенноновских источников информации

Розглянуто підходи до моделювання криптографічних систем, їх стійкість в цих моделях. Досліджується побудова криптографічних перетворень для колмогоровських джерел інформації. Введено нову обчислювальну модель криптографічних систем та досліджено нові асиметричні криптографічні системи, ідеально сті...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
1. Verfasser:	Кудин, А.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/45634
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Криптографические преобразования нешенноновских источников информации / А.М. Кудин // Кибернетика и системный анализ. — 2010. — № 5. — С. 143-149. — Бібліогр.: 25 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-45634
record_format	dspace
spelling	irk-123456789-456342013-06-17T03:19:12Z Криптографические преобразования нешенноновских источников информации Кудин, А.М. Системный анализ Розглянуто підходи до моделювання криптографічних систем, їх стійкість в цих моделях. Досліджується побудова криптографічних перетворень для колмогоровських джерел інформації. Введено нову обчислювальну модель криптографічних систем та досліджено нові асиметричні криптографічні системи, ідеально стійкі в запропонованій моделі. Existing methods of modelling cryptosystems and their cryptographic security are considered. The construction of cryptographic transformations for Kolmogorov sources of information is investigated. A new computational model of cryptosystems is proposed. New asymmetric cryptosystems are investigated that are ideally resistant in this model. 2010 Article Криптографические преобразования нешенноновских источников информации / А.М. Кудин // Кибернетика и системный анализ. — 2010. — № 5. — С. 143-149. — Бібліогр.: 25 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45634 681.3 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	2010
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/45634
citation_txt	Криптографические преобразования нешенноновских источников информации / А.М. Кудин // Кибернетика и системный анализ. — 2010. — № 5. — С. 143-149. — Бібліогр.: 25 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT kudinam kriptografičeskiepreobrazovaniânešennonovskihistočnikovinformacii
first_indexed	2025-07-04T04:30:58Z
last_indexed	2025-07-04T04:30:58Z
_version_	1836689352092024832
fulltext	ÓÄÊ 681.3 À.Ì. ÊÓÄÈÍ ÊÐÈÏÒÎÃÐÀÔÈ×ÅÑÊÈÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÍÅØÅÍÍÎÍÎÂÑÊÈÕ ÈÑÒÎ×ÍÈÊÎÂ ÈÍÔÎÐÌÀÖÈÈ Êëþ÷åâûå ñëîâà: ìîäåëè êðèïòîñèñòåì, ñòîéêîñòü êðèïòîñèñòåì, îáùàÿ òåîðèÿ îïòèìàëüíûõ àëãîðèòìîâ, àëãîðèòìè÷åñêàÿ òåîðèÿ èíôîðìàöèè Êîëìîãîðîâà, èäåàëü- íî ñòîéêèå àñèììåòðè÷íûå êðèïòîñèñòåìû, âû÷èñëèòåëüíàÿ ìîäåëü êðèïòîñèñòåì. ÂÂÅÄÅÍÈÅ Àêòóàëüíîé â êðèïòîëîãèè ÿâëÿåòñÿ ïðîáëåìà ïîëó÷åíèÿ íåòðèâèàëüíûõ íèæíèõ îöåíîê ñòîéêîñòè ïðàêòè÷åñêè èñïîëüçóåìûõ êðèïòîñèñòåì. Íåñìîòðÿ íà çíà÷è- òåëüíûé ïðîãðåññ â èññëåäîâàíèè òåîðåòè÷åñêèõ îñíîâ êðèïòîãðàôèè [1–10], äî ñèõ ïîð íå ïðåäëîæåíû ìåòîäû ïîñòðîåíèÿ êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé (êðèïòîãðàôè÷åñêèõ àëãîðèòìîâ è êðèïòîñèñòåì), ñòîéêîñòü êîòîðûõ êî âñåì âîçìîæíûì êðèïòîàíàëèòè÷åñêèì àòàêàì ôîðìàëüíî äîêàçàíà äëÿ «ðåàëüíûõ» ïðàêòè÷åñêèõ ñèòóàöèé (ìîäåëåé). Âìåñòî ýòîãî äî ñèõ ïîð ïðèìåíÿþòñÿ ìåòî- äû ýêñïåðòíûõ îöåíîê ñòîéêîñòè (ìåòîä ad-hoc). Ïðè ýòîì ñòîéêîñòü êðèïòîãðàôè- ÷åñêîãî àëãîðèòìà â áîëüøèíñòâå ïðàêòè÷åñêèõ ñèòóàöèé îöåíèâàåòñÿ ïî îòíîøå- íèþ ê èçâåñòíûì êðèïòîãðàôè÷åñêèì àòàêàì. Ðàáîòû ïîñëåäíèõ ëåò [1, 2] ðàçäåëÿ- þò äâà ãëàâíûõ íàïðàâëåíèÿ ðàçâèòèÿ êðèïòîãðàôèè: ôîðìàëüíûå ìîäåëè è ðåàëèçóåìûå êðèïòîãðàôè÷åñêèå ñèñòåìû. Â ðàìêàõ ïåðâîãî íàïðàâëåíèÿ ïîëó÷åíû äîñòàòî÷íî âåñîìûå ðåçóëüòàòû [1–4], íî ðàçðàáîòàííûå ìîäåëè êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé âñå åùå íå ðåàëèçîâàíû íà ïðàêòèêå. Â ðàáîòå [3] îïðåäåëåíû äâà íàïðàâëåíèÿ ðåøåíèÿ ýòîé çàäà÷è: ïîñòðîåíèå àäåêâàòíûõ ìîäåëåé êðèïòîñèñòåì (è ðåàëèçàöèÿ êðèïòîñèñòåì â ýòèõ ìîäåëÿõ), òàê íàçûâàåìûé êîíñòðóêòèâíûé ïóòü, è âòîðîé — ïðèáëèæåíèå òðåáîâàíèé ïðàêòè÷åñêèõ ñèòóàöèé ê èìåþùèìñÿ ôîð- ìàëüíûì ìîäåëÿì. Â ðàìêàõ âòîðîãî íàïðàâëåíèÿ, êàê ïðàâèëî, íå óäàåòñÿ ïîñòðî- èòü åäèíûå ìåòîäû àíàëèçà âñåõ ñèñòåì, ïîýòîìó ìåòîäû àäàïòèðîâàíû äëÿ êàæäî- ãî øèôðà (òåì áîëåå ñèñòåìû). Îäíà èç ïðè÷èí — íå ðàññìîòðåíû ðàçëè÷íûå (êðî- ìå ñòàòèñòè÷åñêèõ) ìîäåëè èñòî÷íèêà èíôîðìàöèè [5]. Ôàêòè÷åñêè ñëîæèëàñü ñëåäóþùàÿ ñèòóàöèÿ: ïðèìåíÿåìûå øèôðû äîñòàòî÷íî ñòîéêè ê èçâåñòíûì ìåòîäàì êðèïòîàíàëèçà íà ïðàêòèêå, íî äîêàçàòü, íàñêîëüêî îíè ñòîéêè, íåëüçÿ. Êàê ñëåäñòâèå, ïðè ïðîåêòèðîâàíèè øèôðà ïîñëå ïðîâåðêè î÷åâèäíûõ, ýìïèðè÷åñêè èçâåñòíûõ ñâîéñòâ âîçíèêàåò íîâàÿ çàäà÷à ïðîâåðêè åãî íà ñòîéêîñòü ê êðèïòîàíàëèçó, ðåøåíèå êîòîðîé â îáùåì ñëó÷àå çàâèñèò îò ïðèìåíÿåìûõ ìîäåëåé èñ- òî÷íèêà èíôîðìàöèè, îáðàáîòêè èíôîðìàöèè (ïåðåäà÷è, õðàíåíèÿ, èçìåíåíèÿ), êðèïòîã- ðàôè÷åñêîãî ïðåîáðàçîâàíèÿ, íàðóøèòåëÿ. Ðàçíîðîäíîñòü ýòèõ ìîäåëåé ïðèâîäèò ê íå- ñêîëüêèì ðàçëè÷íûì ïîäõîäàì ê ôîðìàëüíîìó îïèñàíèþ ñòîéêîñòè êðèïòîñèñòåì. ÌÎÄÅËÈ È ÑÒÎÉÊÎÑÒÜ ÊÐÈÏÒÎÑÈÑÒÅÌ Â ðàáîòå [6] ïðåäëîæåíî òðè ïîäõîäà ê îïðåäåëåíèþ ñòîéêîñòè êðèïòîñèñòåì: òåîðåòèêî-èíôîðìàöèîííûé (íåò èíôîðìàöèè äëÿ ðåøåíèÿ çàäà÷è, ðåñóðñû ïðî- òèâíèêà íåîãðàíè÷åííûå), òåîðåòèêî-ñëîæíîñòíîé (ðåñóðñû îãðàíè÷åíû) è òåîðå- òèêî-ñèñòåìíûé (ñòîéêîñòü ê îïðåäåëåííûì àòàêàì). Â òåîðåòèêî-èíôîðìàöèîííîì ïîäõîäå [7–12] ñâÿçûâàþò íåâîçìîæíîñòü âû- ïîëíåíèÿ êðèïòîàíàëèçà ñ íåäîñòàòî÷íîñòüþ èíôîðìàöèè äëÿ åãî ïðîâåäåíèÿ. Íà- èáîëåå èçâåñòíûì ïîäõîäîì ê ïîñòðîåíèþ êðèïòîñèñòåì, ñòîéêèõ â òåîðåòèêî-èí- ôîðìàöèîííîì ñìûñëå, â íàñòîÿùåå âðåìÿ ÿâëÿåòñÿ ðàíäîìèçàöèÿ èñòî÷íèêà îò- êðûòûõ ñîîáùåíèé. Ïðè ýòîì ÷àñòî êàæóùèåñÿ äàëåêèìè äðóã îò äðóãà íàïðàâëåíèÿ èññëåäîâàíèé [10, 11] ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìè ìåòîäîâ ðàíäîìè- çàöèè èñòî÷íèêà îòêðûòûõ ñîîáùåíèé èëè ðàíäîìèçàöèè êðèïòîãðàôè÷åñêèõ ïðå- îáðàçîâàíèé. Òàê èäåÿ «óùåðáíûõ òåêñòîâ» [11] ÿâëÿåòñÿ âàðèàíòîì ïðèìåíåíèÿ âåðîÿòíîñòíûõ êîäîâ [12] äëÿ ïðåäâàðèòåëüíîãî êîäèðîâàíèÿ èíôîðìàöèè, îáùèé ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 143 � À.Ì. Êóäèí, 2010 ñëó÷àé êîòîðûõ ðàññìîòðåí â ðàáîòàõ [8, 9]. Çàìåòèì, ÷òî åñòåñòâåííûì ïðîäîë- æåíèåì èññëåäîâàíèé ìåòîäîâ ðàíäîìèçàöèè ÿâëÿåòñÿ óòî÷íåíèå ïîíÿòèé «êî- ëè÷åñòâà èíôîðìàöèè» â êðèïòîãðàììå îòíîñèòåëüíî îòêðûòîãî òåêñòà è «ñëó- ÷àéíîñòè» ïîñëåäîâàòåëüíîñòåé. Â äàííîé ñòàòüå ðàññìàòðèâàåòñÿ ïîñòðîåíèå ìà- òåìàòè÷åñêèõ ìîäåëåé ñ èñïîëüçîâàíèåì êîëìîãîðîâñêîé ìåðû êîëè÷åñòâà èíôîðìàöèè è êîëìîãîðîâñêîãî îïðåäåëåíèÿ ñëó÷àéíîé ïîñëåäîâàòåëüíîñòè. Â òåîðåòèêî-ñëîæíîñòíîì ïîäõîäå [1, 13, 14] ñâÿçûâàþò íåâîçìîæíîñòü âû- ïîëíåíèÿ àëãîðèòìà êðèïòîàíàëèçà ñ íåäîñòàòî÷íîñòüþ ðåñóðñîâ äëÿ åãî âûïîëíå- íèÿ. Çàìåòèì, ÷òî ðåøåíèå çàäà÷è ïîëó÷åíèÿ íèæíèõ îöåíîê ñòîéêîñòè êðèïòîãðà- ôè÷åñêèõ ñèñòåì ïðè òåîðåòèêî-ñëîæíîñòíîì (è òåì áîëåå ïðè òåîðåòèêî-ñèñòåì- íîì) ïîäõîäàõ ñâÿçàíî ñ äîêàçàòåëüñòâîì ãèïîòåçû î ñóùåñòâîâàíèè îäíîíàïðàâëåííûõ ôóíêöèé [15], ÿâëÿþùåéñÿ áîëåå ñòðîãîé, ÷åì èçâåñòíàÿ ãèïî- òåçà P NP� . Ñëîæíîñòü îïðåäåëåíèÿ íèæíèõ îöåíîê ñòîéêîñòè â äàííîì ïîäõîäå ñîñòîèò òàêæå â ïðèìåíåíèè ñòàòèñòè÷åñêèõ êðèòåðèåâ îòêðûòîãî òåêñòà ñîâìåñòíî ñ ìåòîäàìè òåîðèè ñëîæíîñòè âû÷èñëåíèé äëÿ îöåíêè ñòîéêîñòè êðèïòîñèñòå- ìû [5]. Îñîáåííî ÿâíî ïðîÿâëÿåòñÿ äàííîå ïðîòèâîðå÷èå ïðè îïèñàíèè àñèììåò- ðè÷íûõ êðèïòîñèñòåì áëàãîäàðÿ ñóùåñòâîâàíèþ äâóõ âîçìîæíûõ ìåòîäîâ êðèïòî- àíàëèçà: ïî èçâåñòíîìó øèôðòåêñòó è ïî èçâåñòíîìó îòêðûòîìó êëþ÷ó. Åñëè äëÿ îöåíêè ñòîéêîñòè îòíîñèòåëüíî àíàëèçà ïî îòêðûòîìó òåêñòó ïðèìåíÿþòñÿ ìåòî- äû, àíàëîãè÷íûå òåì, êîòîðûå ïðèìåíÿþòñÿ ê ðàíäîìèçèðîâàííûì ñèììåòðè÷íûì êðèïòîñèñòåìàì [1, 14], òî îáùèå ìåòîäû îöåíêè ñòîéêîñòè îòíîñèòåëüíî àíàëèçà ïî îòêðûòîìó êëþ÷ó ïðàêòè÷åñêè èññëåäîâàëèñü òîëüêî äëÿ ÷àñòíûõ ñëó÷àåâ [16]. Ñôîðìóëèðóåì ñëåäóþùóþ çàäà÷ó: äëÿ çàäàííîé àñèììåòðè÷íîé êðèïòîãðà- ôè÷åñêîé ñèñòåìû ( , , , , )G E D X Y , ãäå G — ìíîæåñòâî àëãîðèòìîâ ãåíåðàöèè êëþ- ÷åé, E D, — ìíîæåñòâà àëãîðèòìîâ øèôðîâàíèÿ/ðàñøèôðîâàíèÿ ñîîòâåòñòâåííî, X — ìíîæåñòâî îòêðûòûõ òåêñòîâ, Y — ìíîæåñòâî øèôðòåêñòîâ, îïðåäåëèòü óñëîâèÿ îòñóòñòâèÿ àëãîðèòìà îïðåäåëåíèÿ d D x Xi i� �, ïðè èçâåñòíûõ e Ei � , y Yi � è ÷àñòè÷íî èçâåñòíîì g Gi � . Ïåðâûì ê ðåøåíèþ ïîñòàâëåííîé çàäà÷è ïðè óñëîâèè E D� ïîäîøåë â ñâîåé ôóíäàìåíòàëüíîé ðàáîòå ßî [13]. Îí ïîêàçàë ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåð- æäåíèÿ: ïóñòü O v n( ( )) — ëþáàÿ ôóíêöèÿ f n( ) , êîòîðàÿ ñòðåìèòñÿ ê íóëþ áûñò- ðåå, ÷åì n t� äëÿ íåêîòîðîé êîíñòàíòû t � 0 . Ñóùåñòâóåò àíñàìáëü èñòî÷íèêîâ èíôîðìàöèè S n ñ ýôôåêòèâíîé ýíòðîïèåé H Sc n( ) , ìíîãî áîëüøåé, ÷åì êëàññè- ÷åñêàÿ ýíòðîïèÿ H S n( ) . Äëÿ g n n g n n( ): (log ) ( )2 2 � � ñóùåñòâóåò àíñàìáëü èñ- òî÷íèêîâ òàêîé, ÷òî H S g nn( ) ( )� , H S n O v nc n( ) ( ( ))� . Ôàêòè÷åñêè óäàëîñü ïîêà- çàòü, ÷òî åñëè ñóùåñòâóåò òàê íàçûâàåìûé èäåàëüíûé ãåíåðàòîð ñëó÷àéíûõ ïîñëåäîâà- òåëüíîñòåé G k:{ , } { , }0 1 0 1 � [1], òî àëãîðèòìà ïîëó÷åíèÿ x Xi � ïî ìíîæåñòâàì e Ei � , y Yi � íå ñóùåñòâóåò äëÿ ðåàëüíûõ èñòî÷íèêîâ îòêðûòûõ ñîîáùåíèé X . Áîëåå òî÷íûå ìîäåëè ìíîæåñòâ X Y, ìîæíî ïîñòðîèòü ñ ïîìîùüþ ìåðû êî- ëè÷åñòâà èíôîðìàöèè, çàêëþ÷åííîé â èíäèâèäóàëüíûõ êîíå÷íûõ îáúåêòàõ, ïðåä- ëîæåííîé Êîëìîãîðîâûì [17]. Ñëåäóþùàÿ òåîðåìà [18] îïðåäåëÿåò ñóùåñòâîâàíèå ïàð êîíå÷íûõ ñëîâ ñ «íåìàòåðèàëèçóåìîé» âçàèìíîé èíôîðìàöèåé. Òåîðåìà 1. Ïóñòü f n( ) — òàêàÿ ôóíêöèÿ, ÷òî f n o n( ) ( )� è f n n( ) log� è xn — òàêàÿ ïîñëåäîâàòåëüíîñòü, ÷òî K x n O f nn( ) ( ( ))� , ãäå K xn( ) — êîëìîãîðîâ- ñêàÿ ñëîæíîñòü ïîñëåäîâàòåëüíîñòè. Òîãäà ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü yn òà- êàÿ, ÷òî K y n O f nn( ) ( ( ))� , I x y an O f nn n( : ) ( ( ))� äëÿ ëþáûõ çíà÷åíèé 0 1� �a è äëÿ ëþáîé ïîñëåäîâàòåëüíîñòè ñëîâ zn , óäîâëåòâîðÿþùèõ óñëîâèþ K z x O f nn n( \| ) ( ( ))� , K z y O f nn n( \| ) ( ( ))� , èìååò ìåñòî ñîîòíîøåíèå K zn( ) � � O f n( ( )) . Çäåñü I x yn n( : ) — âçàèìíàÿ èíôîðìàöèÿ ïî Êîëìîãîðîâó. Ýòîò ôàêò ïîçâîëÿåò ïðè ïîñòðîåíèè êðèïòîñèñòåì èñïîëüçîâàòü ïðåîáðàçîâàíèÿ, âíîñÿùèå íå ñòàòèñòè÷åñêóþ, à «âû÷èñëèòåëüíóþ (àëãîðèòìè÷åñêóþ)» íåîïðåäåëåí- íîñòü ýëåìåíòîâ ìíîæåñòâà X îòíîñèòåëüíî èçâåñòíûõ ýëåìåíòîâ ìíîæåñòâà Y . Áðàññàðä [19] âïåðâûå ðàññìîòðåë ñëó÷àé E D� ñ ïîìîùüþ ïîñòðîåíèÿ èñ- êóññòâåííûõ ìîäåëåé âû÷èñëåíèé, â êîòîðûõ ëþáîé àëãîðèòì îïðåäåëåíèÿ X ïî èçâåñòíûì E Y, ïðèíàäëåæàë áû êëàññó NP. Ïðàêòè÷åñêèì ðàçâèòèåì èäåé Áðàññàðà ñòàëà êîíöåïöèÿ âåðîÿòíîñòíîãî øèô- ðîâàíèÿ. Çà ñ÷åò ââåäåíèÿ âåðîÿòíîñòíîé ìîäåëè âû÷èñëåíèé, ðàíäîìèçàöèè ìíî- 144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 æåñòâà X , ãèïîòåç î ñóùåñòâîâàíèè èäåàëüíûõ ãåíåðàòîðîâ ñëó÷àéíûõ ïîñëåäîâà- òåëüíîñòåé G k:{ , } { , }0 1 0 1 � è õåø-ôóíêöèé H k:{ , } { , }0 1 0 1� óäàëîñü äîêàçàòü ñëåäóþùåå óòâåðæäåíèå [14]. Òåîðåìà 2. Ïóñòü A — ïîëèíîìèàëüíàÿ âåðîÿòíîñòíàÿ ìàøèíà Òüþðèíãà, õà- ðàêòåðèçóþùàÿ âû÷èñëèòåëüíûå âîçìîæíîñòè êðèïòîàíàëèòèêà ïðè íàëè÷èè èí- ôîðìàöèè îá îòêðûòîì êëþ÷å è øèôðòåêñòå; G — àëãîðèòì ãåíåðàöèè êëþ÷åé, E D, — àëãîðèòìû øèôðîâàíèÿ/ðàñøèôðîâàíèÿ ñîîòâåòñòâåííî, X — ìíîæåñòâî îòêðûòûõ òåêñòîâ, Y — ìíîæåñòâî øèôðòåêñòîâ, Q — ïðîèçâîëüíûé ïîëèíîì. Ñóùåñòâóåò êðèïòîñèñòåìà ( , , , , )G E D X Y òàêàÿ, ÷òî ëþáàÿ A îïðåäåëÿåò x Xi � ïðè èçâåñòíûõ e Ei � , y Yi � ñ âåðîÿòíîñòüþ íå áîëüøåé 1 2 1/ / ( ) Q k , ãäå k — âûáðàííûé ïàðàìåòð ñòîéêîñòè ê êðèïòîàíàëèçó. Ãëàâíàÿ èäåÿ ìåòîäà — ðàíäîìèçàöèÿ ìíîæåñòâà îòêðûòûõ ñîîáùåíèé X , çà ñ÷åò êîòîðîé íàðóøàåòñÿ èíúåêòèâíîñòü îòîáðàæåíèÿ Y X . Äàëüíåéøèå èññëåäîâàíèÿ ñâÿçàíû ñ èçó÷åíèåì ñâÿçè ñòðóêòóð ìíîæåñòâ X Y, ïðè ðàçëè÷íûõ E D, . Â ðàáîòå [20] ââîäèòñÿ ñâîéñòâî íåñîõðàíåíèÿ ãîìîìîðôèçìà (non-malleability) êðèïòîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ, îïðåäåëåííîå íà ìíîæåñòâå øèôðòåêñòîâ Y ñëåäóþùèì îáðàçîì: �y y Y1 2, îòíîñèòåëüíî ôóíêöèè f , îïðåäåëåííîé íà ìíîæåñòâå îòêðûòûõ òåêñòîâ, íå ñóùåñòâóåò âåðîÿòíîñòíîãî àëãîðèòìà îïðåäåëåíèÿ y2 ïî èçâåñòíîìó y1, òàêîãî, ÷òî y E x1 1� ( ) , y E f x2 1� ( ( )). Òàêèì îáðàçîì, êðèïòîãðàôè÷åñêîå ïðåîáðàçîâàíèå ðàçðó- øàåò íåêîòîðîå îòíîøåíèå, ââåäåííîå íà ìíîæåñòâå îòêðûòûõ òåêñòîâ. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Â ðàññìîòðåííûõ âûøå ìîäåëÿõ ñòîéêîñòè àñèììåòðè÷íûõ êðèïòîñèñòåì èñ- ñëåäîâàëîñü âëèÿíèå êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé íà ñâÿçü ìåæäó ìíîæåñòâàìè X Y, , ïðè ýòîì âñåãäà ñóùåñòâóåò àëãîðèòì îïðåäåëåíèÿ D (è ñî- îòâåòñòâåííî x Xi � ) ïî èçâåñòíûì y Yi � , e Ei � . Ðàññìîòðèì ïîñòðîåíèå àñèì- ìåòðè÷íûõ êðèïòîñèñòåì, äëÿ êîòîðûõ íàðóøåíà êàê èíúåêòèâíîñòü îòîáðàæå- íèÿ Y X , òàê è îòîáðàæåíèÿ D E . Òåîðåòè÷åñêîé îñíîâîé ïîñòðîåíèÿ è îöåíêè ñòîéêîñòè òàêèõ êðèïòîãðàôè- ÷åñêèõ ñèñòåì ïðåäëàãàåòñÿ âûáðàòü îáùóþ òåîðèþ îïòèìàëüíûõ àëãîðèòìîâ [21], êîòîðàÿ ñâÿçûâàåò ñóùåñòâîâàíèå è ñëîæíîñòü àëãîðèòìîâ ñ òî÷íîñòüþ çàäàíèÿ âõîäíûõ äàííûõ. Ïðè ýòîì â êà÷åñòâå îäíîé èç ìåð ñëó÷àéíîñòè ìíîæåñòâ X Y E D, , , öåëåñîîáðàçíî èñïîëüçîâàòü êîëìîãîðîâñêóþ ìåðó èíôîðìàöèè. Äëÿ ðåøåíèÿ çàäà÷è ïîñòðîåíèÿ òàêèõ êðèïòîñèñòåì àâòîð â ðàáîòå [22] ïðåä- ëîæèë îáúåäèíèòü ïîñòðîåíèå ðàíäîìèçèðîâàííûõ àñèììåòðè÷íûõ øèôðîâ è «øàðàä Ìåðêëÿ» [23]. Ãëàâíàÿ èäåÿ — âíåñòè íåîïðåäåëåííîñòü â ñâÿçü àëãîðèò- ìîâ øèôðîâàíèÿ è ðàñøèôðîâàíèÿ, ëåãêî óñòðàíèìóþ ïðè çíàíèè äîïîëíèòåëüíîé èíôîðìàöèè. Äëÿ ýòîãî óâåëè÷èâàëàñü íåîïðåäåëåííîñòü êëþ÷à ðàñøèôðîâàíèÿ, òîëüêî ÷àñòü êîòîðîãî áûëà áû ñâÿçàíà ñ îòêðûòûì êëþ÷îì. Íåîïðåäåëåííîñòü çà- âèñèìîñòè êëþ÷åé øèôðîâàíèÿ è ðàñøèôðîâàíèÿ îñóùåñòâëÿëàñü çà ñ÷åò ðàíäîìè- çàöèè îòêðûòîãî êëþ÷à âî âçàèìîñâÿçè ñ ðàíäîìèçàöèåé îòêðûòîãî òåêñòà ïðè çàøèôðîâàíèè. Ïðè ýòîì ïðîòèâíèê, îãðàíè÷åííûé â âû÷èñëèòåëüíûõ âîçìîæíîñòÿõ âå- ðîÿòíîñòíûìè àëãîðèòìàìè ïîëèíîìèàëüíîé ñëîæíîñòè, íå â ñîñòîÿíèè îïðåäåëèòü àëãî- ðèòì ðàñøèôðîâàíèÿ, à çàêîííûé ïîëüçîâàòåëü òàêèì àëãîðèòìîì îáëàäàåò áëàãîäàðÿ çíàíèþ èçáûòî÷íîñòè îòêðûòîãî òåêñòà. Åäèíñòâåííîé ñòðàòåãèåé ïðîòèâíèêà ïðè ýòîì îñòàåòñÿ âû÷èñëåíèå îáðàòíîé ôóíêöèè ñâÿçè îòêðûòîãî òåêñòà/øèôðòåêñòà, à íå ôóíêöèè ëàçåéêè (ñâÿçè êëþ÷åé øèôðîâàíèÿ/ðàñøèôðîâàíèÿ). Îãðàíè÷åíèåì òàêîãî ïîõîäà ÿâëÿåòñÿ ñëîæíîñòü ââåäåíèÿ íåîïðåäåëåííîñòè â ñâÿçü ëè÷íîãî è îòêðûòîãî êëþ÷à íà îñíîâàíèè êðèòåðèÿ îòêðûòîãî òåêñòà. Áîëåå ïðîñòûì ìåòîäîì ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è ïîñòðîåíèÿ àñèì- ìåòðè÷íûõ êðèïòîñèñòåì ÿâëÿåòñÿ ñëåäóþùèé: íàðóøåíèå èíúåêòèâíîñòè îòîáðà- æåíèé Y X è D E îñóùåñòâëÿåòñÿ çà ñ÷åò ðàíäîìèçàöèè ìíîæåñòâ X E, ; çà- êîííûå àáîíåíòû äëÿ ðàñøèôðîâàíèÿ ñîîáùåíèé èñïîëüçóþò êðèïòîãðàôè÷åñêè ñèëüíûé ãåíåðàòîð ñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé G k:{ , } { , }0 1 0 1 � ñ íåèç- âåñòíûì íàðóøèòåëþ íà÷àëüíûì çàïîëíåíèåì. Ïðè ýòîì âûáîð êîíêðåòíûõ àëãî- ðèòìîâ e Ei � , d Di � ó çàêîííûõ àáîíåíòîâ óïðàâëÿåòñÿ ãåíåðàòîðîì G (íàïðè- ìåð, i G t� ( ) , t — ñîñòîÿíèå ãåíåðàòîðà). Ðàññìîòðèì ýòîò ïîõîä ïîäðîáíåå. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 145 ÊÐÈÏÒÎÃÐÀÔÈ×ÅÑÊÎÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÈÍÔÎÐÌÀÖÈÈ Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÎÁÙÅÉ ÒÅÎÐÈÈ ÎÏÒÈÌÀËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂ Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ. Ïóñòü çàäàíû ìíîæåñòâà X Y, , ïóñòü 2Y — êëàññ âñåõ ïîäìíîæåñòâ ìíîæåñòâà Y . Â ðàáîòå [21] ðàññìàòðèâàåòñÿ îïåðàòîð S X: � � R Y2 , ãäå R � �[ , )0 — îïåðàòîð ðåøåíèÿ, îáëàäàþùèé äâóìÿ ñâîéñòâàìè: S x x X( , )0 � � � , � � � �1 2 1 2� � �S x S x( , ) ( , ) � � � �1 2, ,R x X . Äëÿ çàäàííîãî � � 0 ýëåìåíò y Y� , óäîâëåòâîðÿþùèé óñëîâèþ y S x� ( , )� , íà- çûâàåòñÿ �-ïðèáëèæåíè- åì. Çàäà÷à ïîèñêà �-ïðè- áëèæåíèÿ ðàññìàòðèâà- åòñÿ ïðè óñëîâèè îòñóò- ñòâèÿ ïîëíîé (è â îáùåì ñëó÷àå òî÷íîé) èíôîðìà- öèè îá ýëåìåíòå x , î êî- òîðîì èçâåñòíà íåêîòîðàÿ èíôîðìàöèÿ N x( ) , ãäå N X Y: — èíôîðìàöè- îííûé îïåðàòîð â òåðìè- íîëîãèè îáùåé òåîðèè îïòèìàëüíûõ àëãîðèòìîâ, à Y — îáðàç ìíîæåñòâà X . Çíàÿ N x( ) , íåîáõîäè- ìî íàéòè �-ïðèáëèæåíèå ê x (ðèñ. 1). Åñëè ìíîæåñòâî V N x x X N x N x( , ) {~ : (~) ( )}� � � âñåõ ýëåìåíòîâ ~x, íåîòëè÷èìûõ ñ ïîìîùüþ èíôîðìàöèîííîãî îïåðàòîðà N îò x, îäíîòî÷å÷íî, òî îïåðàòîð N óñòà- íàâëèâàåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíîæåñòâàìè X è Y è íàçûâà- åòñÿ ïîëíûì (è íåïîëíûì â ïðîòèâíîì ñëó÷àå). Îïåðàòîð ðåøåíèÿ, ïðèìåíÿåìûé ê íåïîëíîìó èíôîðìàöèîííîìó îïåðàòîðó, ïîðîæäàåò ìíîæåñòâî A N f( , , )� � � �� ~ ( , ) (~, )x V N x S x � , ïðè ýòîì äëÿ � � � �1 2 1 2� � �A N x A N x( , , ) ( , , ) . Òîãäà âåëè- ÷èíû r N x A N x( , ) inf { : ( , , ) }� � �� è r N r N xx X( ) sup ( , )� � ( inf { : ( , , )� �� A N x � � �, })x X îïðåäåëÿþò íèæíèå îöåíêè òî÷íîñòè ðåøåíèé, êîòîðûå ìîãóò áûòü äîñòèãíóòû ïðè íåïîëíîì èíôîðìàöèîííîì îïåðàòîðå. Â ðàáîòå [21] äîêàçàíî, ÷òî íà êëàññå èäåàëüíûõ àëãîðèòìîâ �( ): ( )N N x G , c ââåäåííûìè îïðåäåëåíèÿ- ìè ëîêàëüíîé e N x N x A N x( , , ) inf { : ( ( )) ( , , )}� � � �� è ãëîáàëüíîé e N( , )� � � �sup ( , , )x X N x� � ïîãðåøíîñòåé, èíôîðìàöèÿ N x( ) ïîçâîëÿåò íàéòè �-ïðèáëèæå- íèå äëÿ ïðîèçâîëüíîãî x X� òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ îäíî èç óñëîâèé: r N( ) � � , r N N x S x e N x X( ) , : ( ( )) ( , ( , ))� � � �� . Â ñëó÷àå ïðèáëèæåííîé èíôîðìàöèè N � ( � — ìåðà ïîãðåøíîñòè) ðåçóëüòàòû äëÿ íèæíèõ îöåíîê îïðåäåëÿþòñÿ àíàëîãè÷íî: r N( )� �� , r N N x S x e N x X( ) , : ( ( )) ( , ( , ))� � �� . Â îòëè÷èå îò òî÷íîãî èíôîðìàöèîííîãî îïåðàòîðà, îïåðàòîð N � îïðåäåëÿåòñÿ ÷åðåç îïåðàòîð èíôîðìàöèîííîé îøèáêè E H R H: � 2 , îáëàäàþùèé äâóìÿ ñâîéñòâàìè: E h h h H( , ) { }0 � � , � � � �1 2 1 2� � �E h E h( , ) ( , ) , � � � �� , ,2 R h H. Ïðèáëèæåííûé îïåðàòîð N X H� : óäîâëåòâîðÿåò óñëîâèþ N x E N x x X� �( ) ( ( ), )� � . 146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 )( xN 1x 2x 3x ),( 1 �xS ),( XNV ),( 2 �xS ),( 3 �xS )),,(( �XNVS 1�N S � ),,( �fNA Ðèñ. 1. Ãðàôè÷åñêîå èçîáðàæåíèå èíôîðìàöèîííîãî îïåðàòîðà è îïåðàòîðà ðåøåíèÿ A N f( , , )� Çàìåòèì, ÷òî åñëè òî÷íûé èíôîðìàöèîííûé îïåðàòîð N íåïîëîí, òî N � òîæå íåïîëîí, åñëè æå N ïîëîí, òî N � ìîæåò îêàçàòüñÿ êàê ïîëíûì, òàê è íåïîëíûì. Åñëè îïåðàòîð N � ïîëîí, òî r N( )� � 0 . Ïðè ïîñòðîåíèè ìàòåìàòè÷åñêîé ìîäåëè êðèïòîñèñòåìû ñ èñïîëüçîâàíèåì îïèñàííîãî âûøå ïîäõîäà îòìåòèì, ÷òî â çàäà÷àõ, ðàññìàòðèâàåìûõ â êðèïòîëî- ãèè, íàðóøèòåëþ íå èçâåñòåí îòêðûòûé òåêñò, íî èçâåñòíà íåêîòîðàÿ èíôîðìàöèÿ î íåì, çàêëþ÷åííàÿ â êðèïòîãðàììàõ. Ïóñòü X — èñòî÷íèê îòêðûòûõ ñîîáùåíèé, òîãäà N X Y: — îïåðàòîð, îïèñûâàþùèé êðèïòîãðàôè÷åñêîå ïðåîáðàçîâàíèå, S X R G: � 2 — îïåðàòîð êðèïòîãðàôè÷åñêîãî àíàëèçà, G — ìíîæåñòâî îöåíîê «èñòèííîñòè» îòêðûòûõ òåêñòîâ. Â çàâèñèìîñòè îò ïðàêòè÷åñêîé ñèòóàöèè â êà÷åñòâå ìíîæåñòâà G ìîãóò èñïîëüçîâàòüñÿ, íàïðèìåð, àïîñòåðèîðíûå âåðîÿòíîñòè ýëåìåí- òîâ ìíîæåñòâà X (êàê â òåîðèè èíôîðìàöèè Øåííîíà); ìíîæåñòâî ïðåäïîëàãàåìûõ îòêðûòûõ òåêñòîâ èëè ìíîæåñòâî ñîñòîÿíèé êîíå÷íîãî àâòîìàòà, îïèñûâàþùåãî èñòî÷íèê îòêðûòûõ ñîîáùåíèé X . Çàìåòèì, ÷òî äëÿ äîñòèæåíèÿ èäåàëüíîé ñòîé- êîñòè êðèïòîñèñòåìû îïåðàòîð N äîëæåí áûòü íåïîëíûì. Â êà÷åñòâå �( ( ))N X âûáèðàåì ìíîæåñòâî èäåàëüíûõ àëãîðèòìîâ � ðåàëèçà- öèè îïåðàòîðà êðèïòîàíàëèçà. Ïðè ýòîì óñëîâèå èäåàëüíîé ñòîéêîñòè îïðåäåëÿåò- ñÿ êàê r N X( ( )) � �� 0 , ãäå r N X( ( )) — ðàäèóñ èíôîðìàöèè N x( ) . Îñîáûé èíòåðåñ âûçûâàåò ñëó÷àé ïðèáëèæåííîé èíôîðìàöèè, ò.å. ñîçíàòåëüíîå âíåñåíèå îøèáîê â ïðîöåññ êðèïòîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ. Ïðè ýòîì, êàê óêàçû- âàëîñü âûøå, ïðè ïîëíîì òî÷íîì èíôîðìàöèîííîì îïåðàòîðå N îïåðàòîð N � ìîæåò îêàçàòüñÿ êàê ïîëíûì, òàê è íåïîëíûì. Ýòî ïîçâîëÿåò ïðåäïîëîæèòü ñóùåñòâîâàíèå èäåàëüíûõ êðèïòîñèñòåì, êîòîðûå Øåííîí îòíåñ ê «ïðàêòè÷åñêè ñòîéêèì». Íàçîâåì ââåäåííóþ ìîäåëü âû÷èñëèòåëüíîé ìîäåëüþ ñòîéêîñòè êðèïòîñèñòåì. Ñïðàâåäëèâû ñëåäóþùèå òåîðåìû. Òåîðåìà 3. Äëÿ êðèïòîñèñòåì, èäåàëüíî ñòîéêèõ â âû÷èñëèòåëüíîé ìîäåëè ñòîéêîñ- òè, âñå êðèïòîãðàôè÷åñêèå ïðåîáðàçîâàíèÿ èìåþò ñâîéñòâî íå ñîõðàíÿòü ãîìîìîðôèçì. Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ äëÿ êðèïòîãðàôè÷åñêîãî ïðåîáðàçîâàíèÿ, íå ñîõðàíÿþùåãî ãîìîìîðôèçì �y y Y1 2, , è íåêîòîðîé ôóíêöèè f , îïðåäåëåí- íîé íà X , íå ñóùåñòâóåò âåðîÿòíîñòíîãî àëãîðèòìà A x y E f( , , , )1 1 , îïðåäåëÿþùåãî y2 , òàêîãî, ÷òî y E x1 1� ( ) , y E f x2 1� ( ( )) . Ïîñêîëüêó äëÿ èäåàëüíî ñòîéêîé â âû- ÷èñëèòåëüíîì ñìûñëå êðèïòîñèñòåìû r N X( ( )) � �� 0 , òî äëÿ ëþáûõ ôóíêöèé f x f x x f x, , ( ), ( )1 1 2 1� ñóùåñòâóåò òàêîå � � 0 , ÷òî E x E f x E x( ) ( ( )) ( )1 1 2� � . Òîã- äà y E f x E x2 1 2� �( ( )) ( ) , îòñþäà x f x2 1� ( ) , ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ î x f x2 1� ( ) . Òåîðåìà äîêàçàíà. Òåîðåìà 4. Êðèïòîñèñòåìà, èäåàëüíî ñòîéêàÿ â âû÷èñëèòåëüíîé ìîäåëè ñòîé- êîñòè, òàêæå ÿâëÿåòñÿ ñòîéêîé â ñìûñëå ïîëèíîìèàëüíîé íåðàçëè÷èìîñòè. Ðàññìîòðèì ïðèìåðû ïîñòðîåíèÿ àñèììåòðè÷íûõ êðèïòîñèñòåì, ñòîéêèõ â èäåàëüíîì ñìûñëå â ìîäåëè âû÷èñëèòåëüíîé ñòîéêîñòè, ñ èñïîëüçîâàíèåì êðèï- òîãðàôè÷åñêè ñèëüíîãî ãåíåðàòîðà ñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé. ÏÐÈÌÅÐÛ ÏÎÑÒÐÎÅÍÈß ÈÄÅÀËÜÍÎ ÑÒÎÉÊÈÕ ÀÑÈÌÌÅÒÐÈ×ÍÛÕ ÊÐÈÏÒÎÑÈÑÒÅÌ Â ÒÅÐÌÈÍÀÕ ÎÁÙÅÉ ÒÅÎÐÈÈ ÎÏÒÈÌÀËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂ Ïóñòü ( , , )G E D — êðèïòîñèñòåìà RSA. Ãåíåðàöèÿ êëþ÷åé. Ïîëîæèì âìåñòî îòêðûòîãî êëþ÷à N ìíîæåñòâî � { , , , }N N N N k� 1 2 � . Ýòî ñîîòâåòñòâóåò ñèòóàöèè, êîãäà íåêîòîðûå áèòû N i íåèç- âåñòíû. Ïóñòü � { , , , }D d d dk� 1 2 � — ñîîòâåòñòâóþùåå ìíîæåñòâî ëè÷íûõ êëþ÷åé, X — ìíîæåñòâî îòêðûòûõ òåêñòîâ, f xr ( ) — ðàíäîìèçàòîð, G k:{ , } { , }0 1 0 1 � — êðèïòîãðàôè÷åñêè ñèëüíûé ãåíåðàòîð ñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé ñ íåèçâåñòíûì íàðóøèòåëþ íà÷àëüíûì çàïîëíåíèåì t0 . Ïîñòðîåíèå ìíîæåñòâà �N ìîæíî îñó- ùåñòâèòü ñ ïîìîùüþ êîíñòðóêòèâíîãî àëãîðèòìà: âíà÷àëå ñòðîèì ñëó÷àéíûå ïðîñòûå ÷èñëà òðåáóåìîãî ðàçìåðà, çàòåì îïðåäåëÿåì èõ ïðîèçâåäåíèÿ. ßñíî, ÷òî ýòîò àëãîðèòì èìååò ïîëèíîìèàëüíóþ ñëîæíîñòü. Çàøèôðîâàíèå. Âûáèðàåì i G t� ( )0 , ãäå t0 — íà÷àëüíîå ñîñòîÿíèå, èçâåñ- òíîå çàêîííûì àáîíåíòàì. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 147 Âû÷èñëÿåì ~ �N N G l� . Äëÿ x X� èìååì ~ ( ), ~ mod ~ x f x c x Nr e� � . Ðàñøèôðîâàíèå. Ïóñòü B — ïîëèíîìèàëüíàÿ âåðîÿòíîñòíàÿ ìàøèíà Òüþ- ðèíãà ñ âõîäàìè �N , �D , f xr ( ) , c , G t( )0 , êîòîðàÿ âû÷èñëÿåò x . Òàêàÿ ìàøèíà ñó- ùåñòâóåò, òàê êàê ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì âû÷èñëåíèÿ �D ïî èç- âåñòíîìó i G t� ( )0 è âåðîÿòíîñòíûé ïîëèíîìèàëüíûé àëãîðèòì âû÷èñëåíèÿ x ïî èçâåñòíîìó f xr ( ) . Â ïðîñòåéøåì ñëó÷àå äëÿ f x xr ( ) \| \|� random , ãäå random — ñëó- ÷àéíîå ÷èñëî, \| \| — îïåðàöèÿ êîíêàòåíàöèè, ïðèìåíÿåì ñëåäóþùèé àëãîðèòì: i G t� ( )0 , � modx c N d i i� , � \| \|x x� random. Ïîäîáíûé àëãîðèòì ñóùåñòâóåò è äëÿ äðóãèõ ñõåì ðàíäîìèçàöèè, íàïðèìåð äëÿ ñõåìû Optimal asimetric encryption [24]. Îöåíêà ñòîéêîñòè. Ïîãðåøíîñòü âû÷èñëåíèÿ d, ñîîòâåòñòâóþùåãî âûáðàííî- ìó ïðè çàøèôðîâàíèè ~ N (ïðè çíàíèè c, f xr ( ), N , e, G) íå ðàâíà 0, ò.å. r N d( ( ~ )) � 0 . Âñÿ èíôîðìàöèÿ «ïî Êîëìîãîðîâó», íåîáõîäèìàÿ äëÿ òî÷íîãî âîññòàíîâëåíèÿ, êà- êîé èìåííî ýëåìåíò ìíîæåñòâà �N áûë âûáðàí ïðè çàøèôðîâàíèè, çàêëþ÷åíà â t0 . Îöåíêà ïðàêòè÷åñêîé ñòîéêîñòè êðèïòîñèñòåìû çàâèñèò îò ìîùíîñòè ìíîæåñòâà �N . Äëÿ îïðåäåëåíèÿ ìîùíîñòè äàííîãî ìíîæåñòâà íåîáõîäèìî îöåíèòü êîëè÷å- ñòâî ÷èñåë, ÿâëÿþùèõñÿ ìîäóëåì äëÿ êðèïòîñèñòåìû RSA ðàçìåðà n. Èçâåñòíî, ÷òî ìîäóëü N p q� � , ãäå p q, — êëàññè÷åñêèå ñèëüíûå ïðîñòûå ÷èñëà ðàçìåðà ïðèìåð- íî n , ò.å. âûïîëíåíû ñëåäóþùèå óñëîâèÿ: p p p N p p p N p p p N x x x 1 1 2 1 2 3 31 1 11 2 3\| , , \| , , \| ,� � � � � , 1 2 1 1 2 1 1 2 11 2 3� � � � � �x x x, , ; q q q N q q q N q q q N x x x 1 1 2 1 2 3 31 1 14 5 6\| , , \| , , \| ,� � � � � , 1 2 1 1 2 1 1 2 14 5 6� � � � � �x x x, , . Ïîëó÷èì âåðõíþþ îöåíêó êîëè÷åñòâà ÷èñåë p q, . Äëÿ ýòîãî çàìåòèì, ÷òî âåðî- ÿòíîñòü òîãî, ÷òî ñëó÷àéíî âûáðàííîå ÷èñëî íåçàâèñèìî îò ðàçìåðà áóäåò èìåòü íàèáîëüøèé äåëèòåëü, áîëüøèé èëè ðàâíûé N x , 1 2 1� �x , ðàâíà ln x [25]. Êîëè÷åñ- òâî ïðîñòûõ ÷èñåë â èíòåðâàëå [ , ]a b íàõîäèòñÿ ïî ôîðìóëå � �( ) ( )b a� � dt t a b ln� . Òîãäà, ïðèíèìàÿ âî âíèìàíèå, ÷òî äëÿ ïîëó÷åíèÿ âåðõíèõ îöåíîê ñîáûòèÿ ñóùåñòâî- âàíèÿ äåëèòåëåé p p p1 2 3, , (q q q1 2 3, , ) âûáðàííûõ ðàçìåðîâ ìîæíî ñ÷èòàòü íåçàâè- ñèìûìè, ïîëó÷àåì � s a b a b x x x dt t ( , ) ln ln ln ln � � � � � �1 2 3 , ãäå � s a b( , ) — êîëè÷åñòâî ñèëüíûõ ïðîñòûõ ÷èñåë p â èíòåðâàëå [ , ]a b , 1 2 11 2 3� �x x x, , . Òàêèì îáðàçîì, âåðõíÿÿ îöåíêà ìîùíîñòè ìíîæåñòâà �N îïðåäå- ëÿåòñÿ êàê � s a b( , )2 . Äëÿ ïðèìåíÿåìûõ ðàçìåðîâ ìîäóëåé RSA (2048 áèò) ýòà îöåíêà ïðèáëèçèòåëüíî ðàâíà 10600 . Ïîäîáíûé ìåòîä ìîæíî ïðèìåíèòü äëÿ ïî- ñòðîåíèÿ èäåàëüíî ñòîéêîé â âû÷èñëèòåëüíîì ñìûñëå ñõåìû Äèôôè–Õåëëìàíà. ÇÀÊËÞ×ÅÍÈÅ Ïðåäëîæåííûå ìåòîäû ïîñòðîåíèÿ èäåàëüíî ñòîéêèõ â âû÷èñëèòåëüíîé ìîäåëè êðèïòîñèñòåì äîñòàòî÷íî ýôôåêòèâíû ïðè ïðàêòè÷åñêîé ðåàëèçàöèè. Ðåçóëüòàòû ñðàâíåíèÿ ïðåäëîæåííîãî ïîõîäà ñ èçâåñòíûìè ìîæíî ïðåäñòàâèòü â âèäå òàáëèöû, îòîáðàæàþùåé îñíîâíûå õàðàêòåðèñòèêè êðèïòîñèñòåì, ïîñòðîåííûõ â èõ ðàìêàõ. 148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 Èç òàáëèöû âèäíî, ÷òî ïðè ïðèìåíåíèè â êà÷åñòâå ìåðû èíôîðìàöèè êðèïòîãî- ðîâñêîé ñëîæíîñòè, à â êà÷åñòâå ïîêàçàòåëÿ ñòîéêîñòè, — ÷åáûøåâñêîãî ðàäèóñà èí- ôîðìàöèè, óäàåòñÿ âûäåëèòü íîâûé êëàññ êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé, îñíî- âàííûé íà âíåñåíèè íåîïðåäåëåííîñòè â ñâÿçü êëþ÷åé øèôðîâàíèÿ/ðàñøèôðîâàíèÿ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. G o l d w a s s e r S . , B e l l a r e M . Lecture Notes on Cryptography. — Cambridge, Massachusetts, 2001. — 283 c. 2. A b a d i M . , R o g a w a y P . Reconciling two views of cryptography (The computational soundness of formal encryption) / J. of Cryptology. — 2002. — 15, N 2. — P. 103–127. 3. G r i g o r i e v D . , H i r s c h E . A . , P e r v y s h e v K . A Complete Public-Key Cryptosystem / Groups-Complexity-Cryptology. — 2009. — 1, N 1. — P. 1–12. 4. P l i a m J . O . The disparity between work and entropy in cryptology // available from iacr.eprint/024. 5. Ê ó ä è í À . Ì . Îãðàíè÷åíèÿ ñîâðåìåííûõ ìîäåëåé îïèñàíèÿ êðèïòîñèñòåì / Â³ñí. Äåðæ. óí-òó ³íôîðìàö³éíî-êîìóí³êàö³éíèõ òåõíîëîã³é. — 2008. — 6, ¹ 2. — Ñ. 144–146. 6. R u e p p e l , R a i n e r A . Analysis and design of stream ciphers. With a foreword by James L. Massey // Com. and Contr. Engineer. Ser. — Berlin: Springer-Verlag, 1986. — 244 p. 7. Ø å í í î í K . Òåîðèÿ ñâÿçè â ñåêðåòíûõ ñèñòåìàõ // Ðàáîòû ïî òåîðèè èíôîðìàöèè è êèáåðíåòèêå. — Ì.: Èçä-âî èíîñòð. ëèò., 1963. — Ñ. 333–369. 8. W y n e r A . D . The wire-tap channel // Bell Syst. Techn. J. — 1975. — 54. — P. 1355–1388. 9. M a u r e r U . Information-theoretic cryptography // Advances in Cryptology — CRYPTO’99, Proceed- ings. — Berlin: Springer-Verlag, 1999. — P. 47–64. 10. Ð ÿ á ê î Á . ß . , Ô è î í î â À . Í . Áûñòðûé ìåòîä ïîëíîé ðàíäîìèçàöèè ñîîáùåíèé // Ïðîáëåìû ïåðåäà÷è èíôîðìàöèè. — 1997. — 33, âûï. 3. — Ñ. 3–14. 11. Ì è ù å í ê î Â . À . , Â è ë à í ñ ê è é Þ . Â . Óùåðáíûå òåêñòû è ìíîãîêàíàëüíàÿ êðèïòîãðàôèÿ. — Ìí.: Ýíöèêëîïåäèêñ, 2007. — 292 ñ. 12. À ë å ê ñ å é ÷ ó ê À . Í . Ìàòåìàòè÷åñêàÿ ìîäåëü è çàäà÷è àíàëèçà ñòîéêîñòè âåðîÿòíîñòíî-êðèïòî- ãðàôè÷åñêèõ ñèñòåì â ñèñòåìàõ çàùèòû èíôîðìàöèè // Çàõèñò ³íôîðìàö³¿. — 2001. — ¹ 3. — Ñ. 5–12. 13. Yao A.C. Theory and application of trapdoor functions / 23rd Annual Sympos. on Foundat. of Comput. Sci. — Chicago, 1982. — P. 80–91. 14. G o l d w a s s e r S . , M i c a l i S . Probabilistic Encryption // J. of Comput. and System Sci. — 1984. — N 28. — Ð. 270–299. 15. Ë å â è í Ë . Îäíîñòîðîííèå ôóíêöèè // Ïðîáëåìû ïåðåäà÷è èíôîðìàöèè. — 2003. — 39(1). 16. M a u r e r U . , W o l f S . The Diffie-Hellman protocol / from www.iacr.eprint/078.pdf 17. Ê î ë ì î ã î ð î â À . Í . Òðè ïîäõîäà ê îïðåäåëåíèþ ïîíÿòèÿ «Êîëè÷åñòâî èíôîðìàöèè» / Íîâîå â æèçíè, íàóêå, òåõíèêå. Ñåð. «Ìàòåìàòèêà è êèáåðíåòèêà». — 1991. — ¹ 1. — Ñ. 24–29. 18. Ó ñ ï å í ñ ê è é Â . , Â å ð å ù à ã è í Í . , Ø å í ü À . Êîëìîãîðîâñêàÿ ñëîæíîñòü. — 2004. — 325 ñ. 19. B r a s s a r d G . Relativized cryptography // IEEE Trans. on Inform. Theory. — 1983. — IT-29, N 6. — P. 877–890. 20. D o l e v D . , D w o r k C . , N a o r M . Non-malleable cryptography // Proc. of Twenty-third Annual ACM sympos. on Theory of Comput. — New Orleans, Lousiana,Us, 1991. — P. 542–552. 21. Ò ð à ó á Ä . , Â à ñ è ë ü ê î â ñ ê è é Ã . , Â î æ ü í ÿ ê î â ñ ê è é Õ . Èíôîðìàöèÿ, íåîïðåäåëåííîñòü, ñëîæíîñòü. — Ì.: Ìèð, 1988. — 184 ñ. 22. Ê ó ä è í À . Ì . Îá îäíîì êëàññå êðèïòîãðàôè÷åñêèõ ïðåîáðàçîâàíèé äëÿ ìîäåëè èñòî÷íèêîâ èíôîðìàöèè Êîëìîãîðîâà // Ïðàö³ ì³æíàð. ñèìïîç³óìó «Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü ÏÎÎ-XXXV». — Êè¿â: ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2009. — 1. — Ñ. 394–399. 23. M e r k l e R . Secure communications over insecure channels // CACM. — Apr. 1978. — P. 294–299. 24. B e l l a r e M . , R o g a w a y P . Optimal asymmetric encryption // Advances in cryptology. — LCNCS — 1994. — 950. — P. 92–111. 25. K n u t D . E . , T r a b b - P a r d o L . Analysis of a simple factorization algorithm // Theoret. Comput. Sci. — 1976. — 3. — P. 321–348. Ïîñòóïèëà 15.02.2010 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 149 Õàðàêòåðèñòèêè Ïîäõîä, ñâÿçàííûé ñ êëàññè÷åñêîé òåîðèåé èíôîðìàöèè Ïîäõîä, ñâÿçàííûé ñ âû÷èñëèòåëüíîé ýíòðîïèåé Ïîäõîä, ñâÿçàííûé ñ àëãîðèòìè÷åñêîé òåîðèåé èíôîðìàöèè Êîëìîãîðîâà è îáùåé òåîðèåé îïòèìàëüíûõ àëãîðèòìîâ Ìåðà èíôîðìàöèè Ýíòðîïèÿ H X( ) Ýôôåêòèâíàÿ ýíòðîïèÿ H XC ( ) Êîëìîãîðîâñêàÿ ñëîæíîñòü KS X( ) Óñëîâèÿ ñóùåñòâîâàíèÿ ñîâåðøåííûõ ÊÑ H X H K( ) ( )� , I X Y I X K( , ) ( , )� � 0 H X H KC C( ) ( )� KS X H K( ) ( )� , r N x( , ) �� Óñëîâèÿ ñóùåñòâîâàíèÿ èäåàëüíûõ ÊÑ I X Y H X( , ) ( )� H KC ( ) �0 , H XC ( ) �0 I X K( : ) � 0 , I X Y( : ) � 0 , r N x( , )� �� Ò à á ë è ö à 1

Криптографические преобразования нешенноновских источников информации

Institution

Ähnliche Einträge