=Paper=
{{Paper
|id=Vol-1732/paper3
|storemode=property
|title=
Реализация VPN на
основе KDP-схемы
(The VPN Implementation on Base of the KDP-Scheme)
|pdfUrl=https://ceur-ws.org/Vol-1732/paper3.pdf
|volume=Vol-1732
|authors=Sergey Belim,Svetlana Belim
}}
==
Реализация VPN на
основе KDP-схемы
(The VPN Implementation on Base of the KDP-Scheme)
==
https://ceur-ws.org/Vol-1732/paper3.pdf
Ðåàëèçàöèÿ VPN íà îñíîâå KDP-ñõåìû
Ñ.Â. Áåëèì Ñ.Þ. Áåëèì
belimsv@omsu.ru sbelim@mail.ru
Îìñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò èì. Ô.Ì. Äîñòîåâñêîãî, Îìñê, Ðîññèÿ
Àííîòàöèÿ
 ñòàòüå ïðåäëîæåíà ìîäèôèêàöèÿ KDP-ñõåìû. Ðåàëèçîâàíà äèñ-
êðåöèîííàÿ ïîëèòèêà áåçîïàñíîñòè íà îñíîâå KDP-ñõåìû. Ýòà ñõå-
ìà èñïîëüçóåòñÿ äëÿ ðåàëèçàöèè VPN. Ïðåäëîæåí àëãîðèòì âû-
÷èñëåíèÿ ïàð êëþ÷åé.
Ââåäåíèå
Ïîä ïîïàðíîé êëþ÷åâîé ñõåìîé ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé ïðèíÿòî ïîíèìàòü ñõåìó, â êî-
òîðîé îäèí êëþ÷ àññîöèèðîâàí ðîâíî ñ äâóìÿ óçëàìè. Â ïðèìèòèâíîé ñõåìå êàæäûé óçåë õðàíèò (n − 1)
êëþ÷ äëÿ êàæäîãî óçëà ñåòè. Ýòà ñõåìà óñòîé÷èâà ê àòàêàì çëîóìûøëåííèêà, íî îáëàäàåò ïëîõîé ìàñ-
øòàáèðóåìîñòüþ è òðåáóåò áîëüøèõ ðåñóðñîâ ïàìÿòè äëÿ õðàíåíèÿ êëþ÷åâûõ ìàòåðèàëîâ.
Âñå ñõåìû ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé ïîäðàçóìåâàþò âîçìîæíîñòü ñâÿçè êàæäîãî àáîíåí-
òà ñåòè ñ êàæäûì. Òîãäà êàê â ðåàëüíûõ ñèñòåìàõ ñóùåñòâóþò ïîëèòèêè áåçîïàñíîñòè, îãðàíè÷èâàþùèå
âîçìîæíîñòè âçàèìîäåéñòâèÿ îòäåëüíûõ ïàð ïîëüçîâàòåëåé. Áàçîâîé ïîëèòèêîé áåçîïàñíîñòè ÿâëÿåòñÿ
äèñêðåöèîííîå ðàçäåëåíèå äîñòóïà, çàäàííîå â âèäå ìàòðèöû äîñòóïîâ, îïðåäåëÿþùèõ ðàçðåøåííûå êà-
íàëû ïåðåäà÷è èíôîðìàöèè.
Îäíîé èç ñàìûõ íàäåæíûõ ñõåì, õîðîøî ðàçðàáîòàííîé è ñòàâøåé óæå êëàññè÷åñêîé, ÿâëÿåòñÿ KDP-
ñõåìà [1, 2], îñíîâàííàÿ íà ïîñòðîåíèè ñåìåéñòâà ïåðåñåêàþùèõñÿ ìíîæåñòâ.
Ñõåìà ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé íà îñíîâå ìíîãîìåðíûõ ïðîñòðàíñòâ (DDHV-ñõåìà)
ïðåäëîæåíà â ðàáîòå [3].  äàííîé ñõåìå âìåñòî îäíîãî ãëîáàëüíîãî êëþ÷åâîãî ïðîñòðàíñòâà èñïîëüçóåòñÿ
íàáîð êëþ÷åâûõ ïðîñòðàíñòâ. Êàæäîìó óçëó ñîïîñòàâëÿåòñÿ ïîäìíîæåñòâî êëþ÷åâûõ ïðîñòðàíñòâ. Äëÿ
êàæäîãî îòäåëüíîãî êëþ÷åâîãî ïðîñòðàíñòâà èñïîëüçóåòñÿ ñõåìà Áëîìà. Âåðîÿòíîñòü òîãî, ÷òî äâà óçëà
ñìîãóò âûðàáîòàòü ñîâìåñòíûé êëþ÷ ðàâíà âåðîÿòíîñòè òîãî, ÷òî îíè èìåþò õîòÿ áû îäíî îáùåå êëþ÷å-
âîå ïðîñòðàíñòâî. DDHV-ñõåìà àáñîëþòíî óñòîé÷èâà, åñëè êîëè÷åñòâî ñêîìïðîìåòèðîâàííûõ óçëîâ íèæå
íåêîòîðîãî ïîðîãîâîãî çíà÷åíèÿ.
Ñõåìà îáìåíà êëþ÷àìè, îñíîâàííàÿ íà ìîäåëè çëîóìûøëåííèêà ïðåäñòàâëåíà â ðàáîòå [4]. Äàííàÿ
ñõåìà îñíîâûâàåòñÿ íà ïðåäïîëîæåíèè î òîì, ÷òî çëîóìûøëåííèê íå ìîæåò êîíòðîëèðîâàòü âñå ëèíèè
ñâÿçè. Ââîäèòñÿ âåðîÿòíîñòü ïðîñëóøèâàíèÿ ëèíèè ñâÿçè çëîóìûøëåííèêîì. Ïîñëå ÷åãî èññëåäóåòñÿ âîç-
ìîæíîñòü íåçàùèùåííîãî îáìåíà êëþ÷àìè ìåæäó ñîñåäíèìè óçëàìè. Çëîóìûøëåííèê ñìîæåò àòàêîâàòü
ñèñòåìó, òîëüêî åñëè áóäåò ïðîñëóøèâàòü êàíàë ñâÿçè â ìîìåíò ïåðåäà÷è êëþ÷åâîé èíôîðìàöèè.
 ñâÿçè ñ ðàçâèòèåì áåñïðîâîäíûõ ñèñòåì ñâÿçè øèðîêîå ðàñïðîñòðàíåíèå ïîëó÷èëè âåðîÿòíîñòíûå
ñõåìû ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé, îáçîð êîòîðûõ ïðåäñòàâëåí â ðàáîòå [5].
 ñòàòüå [6] ïðåäñòàâëåíû äâå ñõåìû, êîòîðûå îñíîâàíû íà íåêîòîðîé èíôîðìàöèè î ïðîöåäóðå ðàç-
âåðòûâàíèÿ ñåòè. Â ïåðâîé ñõåìå ïîïàðíûé êëþ÷ ãåíåðèðóåòñÿ òîëüêî äëÿ òåõ ïàð óçëîâ, äëÿ êîòîðûõ
âûñîêà âåðîÿòíîñòü îêàçàòüñÿ ôèçè÷åñêèìè ñîñåäÿìè ïðè ðàçâîðà÷èâàíèè ñåòè. Âòîðîé ïîäõîä îñíîâàí
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data Analysis and Modelling (DAM 2016),
Omsk, Russia, October 2016, published at http://ceur-ws.org
íà ïîðîãîâîé ñõåìå, èñïîëüçóþùåé ìíîãî÷ëåíû îò äâóõ ïåðåìåííûõ. Îáëàñòü ðàçâåðòûâàíèÿ äåëèòñÿ íà
ñåêòîðà ïîäõîäÿùåãî ðàçìåðà. Äëÿ êàæäîãî ñåêòîðà èñïîëüçóåòñÿ ñâîå êëþ÷åâîå ïðîñòðàíñòâî. Êëþ÷è
ãåíåðèðóþòñÿ òîëüêî äëÿ ñîñåäåé èç áëèçêèõ ñåêòîðîâ.
 ñòàòüå [7] ïðåäëîæåíà ñõåìà, â êîòîðîé îáëàñòü ðàçâåðòûâàíèÿ ñåòè ðàçäåëåíà íà ñåêòîðà, ñîîòâåòñòâó-
þùèå íåêîòîðîé ãðóïïå óçëîâ. Äëÿ êàæäîé ãðóïïû ñóùåñòâóåò êëþ÷åâîé ïóë, ñîçäàííûé òàêèì îáðàçîì,
÷òî ñóùåñòâóþò ïåðåêðûòèÿ ñ êëþ÷åâûìè ïóëàìè äëÿ ñîñåäíèõ ãðóïï. Ñîâìåñòíîå èñïîëüçîâàíèå íåêîòî-
ðîãî ïîäìíîæåñòâà êëþ÷åé âîçìîæíî òîëüêî äëÿ ãðóïï ñ ïðÿìûìè ñîñåäíèìè ñåêòîðàìè.
Àíàëîãè÷íûé ïîäõîä, â êîòîðîì èñõîäíàÿ ãðóïïà âñåõ óçëîâ ñåòè äåëèòñÿ íà ìåíüøèå ïîäãðóïïû, ïðåä-
ñòàâëåí â ðàáîòå [8]. Óçëû, êîòîðûå ñîâìåñòíî ðåøàþò îäíó çàäà÷ó äîëæíû èìåòü âîçìîæíîñòü ñâÿçàòüñÿ,
ïîýòîìó îíè îòíîñÿòñÿ ê îäíîé ïîäãðóïïå.
 ñòàòüå [9] ïðîâåäåíî èññëåäîâàíèå ñõåì ðàñïðåäåëåíèÿ êëþ÷åé, îñíîâàííûõ íà ïðåäïîëîæåíèè î ñëó-
÷àéíîì ïîÿâëåíèè óçëà è äåëàåòñÿ âûâîä î íèçêîé óñòîé÷èâîñòè òàêèõ ñõåì. Äëÿ ïîâûøåíèÿ óñòîé÷èâîñòè
ñõåìû ðàñïðåäåëåíèÿ êëþ÷åé ïðåäëîæåí âûáîðî÷íûé àëãîðèòì ïîëó÷åíèÿ óçëà. Íîâûé ïîäõîä òàêæå îñ-
íîâàí íà ðàçäåëåíèè âñåé ñåòè íà çîíû íà ýòàïå ðàçâåðòûâàíèÿ. Ïðîâåäåíî èññëåäîâàíèå ïðåäëîæåííîé
ñõåìû.
 ñòàòüå [10] ïðåäëîæåí ïîäõîä òàêæå èñïîëüçóþùèé ðàçäåëåíèå ñåòè íà êëàñòåðû. Ïðè ýòîì ââîäèòñÿ
äâà òèïà êëàñòåðîâ - êîíòðîëèðóåìûå è íåêîíòðîëèðóåìûå. Êîíòðîëèðóåìûå êëàñòåðû ïðåäíàçíà÷åíû äëÿ
îáåñïå÷åíèÿ áåçîïàñíîñòè êðèòè÷åñêèõ ÷àñòåé ñåòè è ñîäåðæàò áîëåå ìîùíûé óçåë ñóïåðâèçîðà. Ïîïàðíûå
êëþ÷è âû÷èñëÿþòñÿ äëÿ ñâÿçè ìåæäó ñóïåðâèçîðîì è îñòàëüíûìè óçëàìè ñåòè.  íåêîíòðîëèðóåìîé ÷àñòè
èñïîëüçóåòñÿ îäèí îáùèé êëþ÷ äëÿ âñåõ óçëîâ êëàñòåðà.
Íà ñåãîäíÿøíèé äåíü øèðîêîå ðàñïðîñòðàíåíèå ïîëó÷èëè òåõíîëîãèè ïîñòðîåíèÿ âèðòóàëüíûõ ñåòåé,
ëîãè÷åñêàÿ òîïîëîãèÿ êîòîðûõ íå ñîâïàäàåò ñ ôèçè÷åñêîé. Ðàññìîòðèì âîçìîæíîñòü ïîñòðîåíèÿ âèðòó-
àëüíîé ñåòè ñ ïîìîùüþ àëãîðèòìîâ ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé. Ïóñòü çàäàíà íåêîòîðàÿ
âû÷èñëèòåëüíàÿ ñåòü, êîòîðàÿ ìîæåò áûòü, êàê ëîêàëüíîé, òàê è ãëîáàëüíîé. Âèðòóàëüíàÿ ñåòü çàäàåòñÿ
â âèäå ëîãè÷åñêèõ ñâÿçåé ìåæäó ðåàëüíûìè óçëàìè ñåòè. Áóäåì ðàññìàòðèâàòü òîïîëîãèþ âèðòóàëüíîé
ñåòè êàê íåîðèåíòèðîâàííûé ãðàô. Ìíîæåñòâî ñâÿçåé ñåòè ÿâëÿåòñÿ ìíîæåñòâîì ðåáåð ãðàôà è çàäàåòñÿ
ìàòðèöåé èíöèäåíòíîñòè, â êîòîðîé åäèíèöà ñîîòâåòñòâóåò íàëè÷èþ ðåáðà, à íóëü - åãî îòñóòñòâèþ. Ïî
ñâîåìó ñìûñëó íàëè÷èå ëîãè÷åñêîé ñâÿçè îçíà÷àåò âîçìîæíîñòü ïðÿìîãî èíôîðìàöèîííîãî îáìåíà ìåæäó
óçëàìè. Îòñóòñòâèå ñâÿçè îçíà÷àåò çàïðåò íà ïðÿìóþ ñâÿçü äâóõ óçëîâ. Ñëåäîâàòåëüíî ìû èìååì ìíîæå-
ñòâî óçëîâ è íàáîð ïðàâèë, ðàçãðàíè÷èâàþùèõ âîçìîæíîñòè îáìåíà èíôîðìàöèåé ìåæäó íèìè. Äàííàÿ
êîíñòðóêöèÿ ìîæåò áûòü ðåàëèçîâàíà ñ ïîìîùüþ ìàòðèöû äîñòóïîâ â ðàìêàõ äèñêðåöèîííîé ïîëèòèêè
áåçîïàñíîñòè. Î÷åâèäíî, ÷òî ìàòðèöà äîñòóïîâ áóäåò ñîâïàäàòü ñ ìàòðèöåé èíöèäåíòíîñòè, ãðàôà îïðåäå-
ëÿþùåãî òîïîëîãèþ âèðòóàëüíîé ñåòè.
 îáùåì ñëó÷àå ïîñòàíîâêà çàäà÷è âûãëÿäèò ñëåäóþùèì îáðàçîì.  íåêîòîðîì âèäå çàäàíà òîïîëî-
ãèÿ ñåòè â âèäå ìíîæåñòâà âåðøèí è ìíîæåñòâà ñâÿçåé ìåæäó íèìè. Òðåáóåòñÿ ñ ïîìîùüþ ìåõàíèçìà
ðàñïðåäåëåíèÿ êëþ÷åé ðàçãðàíè÷èòü âîçìîæíîñòü âçàèìîäåéñòâèÿ óçëîâ ñåòè òàêèì îáðàçîì, ÷òîáû áûëè
âîçìîæíû òîëüêî ñâÿçè, ðàçðåøåííûå òîïîëîãèåé ñåòè.
Íåîòúåìëåìîé ñîñòàâëÿþùåé ñèñòåìû íà îñíîâå äàííîãî ïîäõîäà ÿâëÿåòñÿ ñåðâåð ðàñïðåäåëåíèÿ êëþ-
÷åé, êîòîðûé ìîæåò áûòü ðåàëèçîâàí êàê âûäåëåííûé óçåë ñåòè. Îäíàêî òàêîå ðåøåíèå ÿâëÿåòñÿ íåóäîá-
íûì, òàê êàê âåäåò ê ðîñòó ðàçìåðà ñåòè è äîïîëíèòåëüíûì ëèíèÿì ñâÿçè. Áîëåå îïðàâäàííûì áóäåò
ðàçìåùåíèå ñåðâåðà ðàñïðåäåëåíèÿ êëþ÷åé â êà÷åñòâå ñåðâèñà íà îäíîì èç ñóùåñòâóþùèõ óçëîâ ñåòè.
Òàêîå òåõíè÷åñêîå ðåøåíèå íå ïðèâåäåò ê çíà÷èòåëüíîìó óâåëè÷åíèþ íàãðóçêè íà äàííûé óçåë, òàê êàê
ñåðâåð ðàñïðåäåëåíèÿ êëþ÷åé âûïîëíÿåò äîñòàòî÷íî íåáîëüøîé îáúåì îïåðàöèé.
Ñëåäóåò îòìåòèòü, ÷òî ïîñòðîåííàÿ ñåòü îáëàäàåò ñâîéñòâàìè âèðòóàëüíîé ÷àñòíîé ñåòè (VPN), òàê êàê
âñå ñîîáùåíèÿ ïåðåäàþòñÿ â çàøèôðîâàííîì âèäå. Äëÿ òîãî, ÷òîáû ïðåäëîæåííàÿ ñåòü ñòàëà ïîëíîïðàâíîé
VPN íåîáõîäèìî äîáàâèòü â ñèñòåìó ïðîòîêîëû ñ îòêðûòûì êëþ÷îì äëÿ ïåðåäà÷è êëþ÷åâûõ ìàòåðèàëîâ
ïî îòêðûòûì êàíàëàì. Íàïðèìåð, ìîæåò áûòü èñïîëüçîâàí ïðîòîêîë Äèôôè-Õåëëìàíà äëÿ óñòàíîâëåíèÿ
ñîåäèíåíèÿ è ïåðåäà÷è êëþ÷åâûõ ìàòåðèàëîâ ìåæäó ñåðâåðîì ðàñïðåäåëåíèÿ êëþ÷åé è óçëàìè ñåòè. Äëÿ
ïîâûøåíèÿ íàäåæíîñòè ñèñòåìû êëþ÷, âûðàáàòûâàåìûé íà îñíîâå êëþ÷åâûõ ìàòåðèàëîâ, ìîæåò áûòü
èñïîëüçîâàí òîëüêî íà ýòàïå óñòàíîâëåíèÿ ñîåäèíåíèÿ äëÿ ïåðåäà÷è ñåàíñîâîãî êëþ÷à. Òàêæå êëþ÷åâûå
ìàòåðèàëû ìîãóò áûòü èñïîëüçîâàíû äëÿ àóòåíòèôèêàöèè óçëîâ ñåòè.
1 Ìîäèôèêàöèÿ KDP-ñõåìû ñ ó÷åòîì çàïðåùåííûõ êàíàëîâ
Ïóñòü â ñèñòåìå èìååòñÿ n ïîëüçîâàòåëåé u1 , ..., un , ìåæäó êîòîðûìè íåîáõîäèìî îðãàíèçîâàòü çàùèùåí-
íûé îáìåí èíôîðìàöèè íà îñíîâå ñèììåòðè÷íîé êðèïòîãðàôèè. Ðàññìîòðèì ñèñòåìó, â êîòîðîé çàäàíî
äèñêðåöèîííîå ðàçäåëåíèå äîñòóïà, çàïðåùàþùåå îáìåí ñîîáùåíèÿìè ìåæäó íåêîòîðûìè ïàðàìè ïîëüçî-
âàòåëåé. Ïðåäñòàâèì îãðàíè÷åíèÿ íà êàíàëû ñâÿçè â âèäå ìàòðèöû M , â êîòîðîé ïîëüçîâàòåëþ ui ñîîòâåò-
ñòâóåò i-àÿ ñòðîêà è i-ûé ñòîëáåö. ß÷åéêà ìàòðèöû M [i, j] = 1, åñëè ðàçðåøåí îáìåí èíôîðìàöèåé ìåæäó
i-ûì è j -ûì ïîëüçîâàòåëåì, è M [i, j] = 0, åñëè îáìåí çàïðåùåí. Çàäà÷à ñâîäèòñÿ ê òîìó, ÷òî íåîáõîäèìî
ïîñòðîèòü ñõåìó ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé òàêèì îáðàçîì, ÷òîáû îíà âûðàáàòûâàëà îáùèé
êëþ÷, åñëè îáìåí ðàçðåøåí è íå ïîçâîëÿëà ïîëó÷èòü êëþ÷, åñëè îáìåí çàïðåùåí.
Áóäåì ðåøàòü ïîñòàâëåííóþ çàäà÷ó ñ ïîìîùüþ ìîäèôèêàöèè êëàññè÷åñêîé KDP-ñõåìû [1, 2].  òðàäè-
öèîííîé KDP-ñõåìå çàäàåòñÿ ìíîæåñòâî êëþ÷åé K = {k1 , ..., km }, êîòîðûå ïåðåäàþòñÿ âñåì ó÷àñòíèêàì
çàùèùåííîé ñåòè çàðàíåå ïî çàùèùåííîìó êàíàëó è äåðæàòñÿ â ñåêðåòå. Âñå êëþ÷è ïðîíóìåðîâàíû. Ïîñëå
ýòîãî ñòðîèòñÿ ñåìåéñòâî ïîäìíîæåñòâ S = {S1 , ..., Sn } ìíîæåñòâà {1, 2, ..., n}. Êàæäîìó ïîëüçîâàòåëþ ui
ñîïîñòàâëÿåòñÿ ïîäìíîæåñòâî Si . Ñåìåéñòâî S ÿâëÿåòñÿ îòêðûòûì. Äëÿ ïîëó÷åíèÿ îáùåãî êëþ÷à øèôðî-
âàíèÿ ïîëüçîâàòåëè ui è uj äîëæíû èçâëå÷ü èç îòêðûòîé áàçû ïîäìíîæåñòâà Si è Sj è íàéòè èõ ïåðåñå÷åíèå
Sij = Si ∩ Sj . Îáùèé êëþ÷ kij îïðåäåëÿåòñÿ íà îñíîâå ïîäìíîæåñòâà êëþ÷åé kl , ãäå l ∈ Sij , ïî êàêîìó-ëèáî
ïðåîáðàçîâàíèþ, èçâåñòíîìó âñåì ó÷àñòíèêàì çàùèùåííîé ñåòè.
Òðàäèöèîííàÿ KDP-ñõåìà ñòðîèòñÿ íà îñíîâå ñåìåéñòâ Øïåðíåðà. Ñåìåéñòâîì Øïåðíåðà [][12] íàçû-
âàåòñÿ ñåìåéñòâî ïîäìíîæåñòâ D = {D1 , ..., Dn } òàêèõ, ÷òî, åñëè Di ∩ Dj ⊆ Dt , òî ëèáî t = i, ëèáî t = j .
Ñåìåéñòâî ìíîæåñòâ S ñòðîèòñÿ íà îñíîâå ñåìåéñòâà Øïåðíåðà D [11]. Ýëåìåíòû ñåìåéñòâà Øïåðíåðà Di
èñïîëüçóþòñÿ â êà÷åñòâå ïåðåñå÷åíèé ïîäìíîæåñòâ Sij .
Äëÿ ïîñòðîåíèÿ KDP-ñõåìû ñ ó÷åòîì äèñêðåöèîííîãî ðàçäåëåíèÿ äîñòóïà ïîòðåáóåì, ÷òîáû äëÿ ïàðû
ïîëüçîâàòåëåé ui è uj , êîòîðûì çàïðåùåí îáìåí èíôîðìàöèåé, ïîäìíîæåñòâî âîçìîæíûõ êëþ÷åé áûëî
íóëåâûì. Äðóãèìè ñëîâàìè, åñëè M [i, j] = 0, òî Sij = ∅, à åñëè M [i, j] = 1, òî Sij 6= ∅.
Ðàññìîòðèì âîçìîæíîñòü ðåàëèçàöèè íîâûõ òðåáîâàíèé ê KDP-ñõåìå. Êàê è ïðè ïîñòðîåíèè òðàäèöè-
îííîé KDP-ñõåìû áóäåì èñïîëüçîâàòü ñåìåéñòâî Øïåðíåðà äîïîëíåííîå íåêîòîðûì êîëè÷åñòâîì ïóñòûõ
ìíîæåñòâ. Ïóñòü â ìàòðèöå M [i, j] âûøå ãëàâíîé äèàãîíàëè ðàñïîëîæåíî m åäèíè÷íûõ ýëåìåíòîâ. Ìîæ-
íî îãðàíè÷èòüñÿ ðàññìîòðåíèåì ýëåìåíòîâ òîëüêî âûøå ãëàâíîé äèàãîíàëè, òàê êàê ïî ïîñòàíîâêå çàäà-
÷è êàíàëû îáìåíà èíôîðìàöèåé ÿâëÿþòñÿ ñèììåòðè÷íûìè, à, ñëåäîâàòåëüíî, ìàòðèöà M [i, j] ÿâëÿåòñÿ
ñèììåòðè÷íîé. Íà îñíîâå ìíîæåñòâà {1, 2, ..., n} ñòðîèì ñåìåéñòâî Øïåðíåðà, ñîäåðæàùåå m ýëåìåíòîâ
D = {D1 , ..., Dm }. Ââåäåì ìàòðèöó M D[i, j], ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ ìíîæåñòâà. Çàïîëíèì ìàòðèöó
M D[i, j] ñëåäóþùèì îáðàçîì. Åñëè M [i, j] = 1, òî M D[i, j] = Dk è M D[j, i] = Dk . Ïîäìíîæåñòâî èç ñåìåé-
ñòâà Øïåðíåðà âûáèðàåòñÿ ñëó÷àéíûì îáðàçîì. Êàæäîå ïîäìíîæåñòâî Dk èñïîëüçóåòñÿ òîëüêî îäèí ðàç
äëÿ èíèöèàëèçàöèè äâóõ ýëåìåíòîâ ìàòðèöû M D[i, j], ñèììåòðè÷íûõ îòíîñèòåëüíî ãëàâíîé äèàãîíàëè.
Åñëè M [i, j] = 0, òî M D[i, j] = ∅ è M D[j, i] = ∅. Ìíîæåñòâà Si íàéäåì êàê îáúåäèíåíèå ïîäìíîæåñòâ èç
ñåìåéñòâà Øïåðíåðà, ðàñïîëîæåííûõ â i-îé ñòðîêå.
n
[
Si = M D[i, j] (i = 1, ..., n).
j=1
Î÷åâèäíî, ÷òî â ñèëó ñèììåòðè÷íîñòè ìàòðèöû M D[i, j] îáúåäèíåíèå ìíîæåñòâ ìîæíî ïðîâîäèòü êàê ïî
ñòðîêå, òàê è ïî ñòîëáöó.
2 Àëãîðèòì ïîñòðîåíèÿ VPN íà îñíîâå KDP-ñõåìû
Ðàññìîòðèì âîçìîæíîñòü ïîñòðîåíèÿ âèðòóàëüíîé ñåòè ñ ïîìîùüþ KDP-ñõåìû. Íà âõîä ñèñòåìû ïîäàåòñÿ
ñïèñîê óçëîâ ñåòè LU è ñïèñîê ïàð óçëîâ, ìåæäó êîòîðûìè ñóùåñòâóþò âèðòóàëüíûå ñîåäèíåíèÿ. Àëãîðèòì
èìååò ñëåäóþùèé âèä:
1. Ïîëó÷àåì ìàòðèöó èíöèäåíòíîñòè ãðàôà, îïðåäåëÿþùåé òîïîëîãèþ ñåòè, êîòîðàÿ â äàëüíåéøåì èã-
ðàåò ðîëü ìàòðèöû äîñòóïîâ.
2. Ñîçäàåì êëþ÷åâîå ìíîæåñòâî K = {ki }i=1,...,n . Ìîùíîñòü ìíîæåñòâà êëþ÷åé n äîëæíà áûòü íå ìåíåå
ìàêñèìàëüíî âîçìîæíîãî êîëè÷åñòâà ñâÿçåé
(|LU |(|LU | − 1))
n> .
2
Ýëåìåíòû êëþ÷åâîãî ìíîæåñòâà ki (i = 1, ..., n) çàäàþòñÿ ñ ïîìîùüþ ãåíåðàòîðà ïñåâäîñëó÷àéíîé ïîñëå-
äîâàòåëüíîñòè.
3. Îïðåäåëÿåì êîëè÷åñòâî åäèíè÷íûõ ýëåìåíòîâ B ìàòðèöû M , ðàñïîëîæåííûõ âûøå ãëàâíîé äèàãî-
íàëè.
4. Ðàçáèâàåì ìíîæåñòâî N = {1, ..., n} íà B íå ïåðåñåêàþùèõñÿ ïîäìíîæåñòâ D1 ,..., DB , òàê ÷òîáû
B
[
Di = N.
i=1
5. Ñòðîèì ìàòðèöó MD, ðàñïðåäåëÿÿ ñëó÷àéíûì îáðàçîì ìíîæåñòâà Di ïî ÿ÷åéêàì ìàòðèöû M D, ñîîò-
âåòñòâóþùèõ åäèíè÷íûì ýëåìåíòàì ìàòðèöû M .
6. Ôîðìèðóåì ìíîæåñòâà Si , êàê îáúåäèíåíèå ìíîæåñòâ Dj ðàñïîëîæåííûõ â îäíîé ñòðîêå. Ïîëó÷åííûå
ìíîæåñòâà Si , õðàíÿùèåñÿ â îòêðûòîì âèäå, âìåñòå ñ ìíîæåñòâîì êëþ÷åé K , õðàíÿùåìñÿ â ñåêðåòå, è áóäóò
èãðàòü ðîëü êëþ÷åâûõ ìàòåðèàëîâ.
Ïðè ôîðìèðîâàíèè òàáëèöû ìàðøðóòèçàöèè, äëÿ îïðåäåëåíèÿ íàëè÷èÿ ñâÿçè ìåæäó óçëàìè i è j ,
ñèñòåìå íåîáõîäèìî îïðåäåëèòü ïåðåñå÷åíèå ìíîæåñòâ Si ∩ Sj è, åñëè îíî îêàæåòñÿ íå ïóñòûì, òî óçëû
i è j ñâÿçàíû. Ïàðíûé êëþ÷ áóäåò âû÷èñëÿòüñÿ êàê ïîáèòîâàÿ îïåðàöèÿ XOR ìåæäó âñåìè ýëåìåíòàìè
ìíîæåñòâà êëþ÷åé, èìåþùèõ íîìåðà èç ìíîæåñòâà Si ∩ Sj .
 ïóíêòå 4 àëãîðèòìà íåîáõîäèìî ñëó÷àéíûì îáðàçîì ðàçáèòü ìíîæåñòâî íà íå ïåðåñåêàþùèåñÿ ïîäìíî-
æåñòâà. Äëÿ àâòîìàòèçàöèè ïðîöåññà ðàçáèåíèå áóäåì ïðîèçâîäèòü ñ ïîìîùüþ ëèíåéíîãî êîíãðóýíòíîãî
ãåíåðàòîðà ïñåâäîñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé. Ãåíåðàòîð íóæåí äëÿ òîãî ÷òîáû îïðåäåëèòü êàêîé ýëå-
ìåíò îòíåñòè ê êàêîìó ïîäìíîæåñòâó. Åñëè íà i-îì øàãå áóäåò ïîëó÷åíî ÷èñëî xi , òî ýëåìåíò ìíîæåñòâà i
îòíåñåì ê ïîäìíîæåñòâó ñ íîìåðîì xi (Dxi ). Î÷åâèäíî, ÷òî ÷èñëà xi äîëæíû ëåæàòü â èíòåðâàëå îò 1 äî
B . Òî åñòü ëèíåéíûé êîíãðóýíòíûé ãåíåðàòîð äîëæåí áûòü ïî ìîäóëþ B . Îäíàêî íå äëÿ êàæäîãî B ìîæíî
ïîñòðîèòü ãåíåðàòîð ñ ïîëíûì ïåðèîäîì. Ïîýòîìó ìû íåìíîãî óõóäøèì õàðàêòåðèñòèêè ãåíåðàòîðà, íî
ïðè ýòîì áóäåì ãàðàíòèðîâàòü, ÷òî â ïñåâäîñëó÷àéíîé ïîñëåäîâàòåëüíîñòè áóäóò âñòðå÷àòüñÿ âñå ÷èñëà îò
1 äî B , è íå áóäåò äðóãèõ ÷èñåë.
Âûáåðåì ìèíèìàëüíîå öåëîå ÷èñëî p, ïðåâûøàþùåå B . Âû÷èñëÿåì ïñåâäîñëó÷àéíóþ ïîñëåäîâàòåëü-
íîñòü yi ñ ïîìîùüþ ëèíåéíîãî êîíãðóýíòíîãî ãåíåðàòîðà:
yi = ayi + b (mod p),
ãäå b 6= 0, y0 ïðîèçâîëüíîå öåëîå ÷èñëî, a ïðèìèòèâíûé ýëåìåíò â êîëüöå Zp . Ïîñëå ýòîãî âû÷èñëÿåì
ïñåâäîñëó÷àéíóþ ïîñëåäîâàòåëüíîñòü xi ïî ôîðìóëå:
xi = yi (mod B) + 1.
Èñõîäÿ èç òîãî, ÷òî ïî ïîñòðîåíèþ a ïðèìèòèâíûé ýëåìåíò â êîëüöå Zp , òî ïñåâäîñëó÷àéíàÿ ïîñëåäîâà-
òåëüíîñòü yi áóäåò èìåòü ìàêñèìàëüíûé ïåðèîä, òî åñòü â íåé áóäóò âñòðå÷àòüñÿ âñå ÷èñëà îò 0 äî p − 1, à,
ñëåäîâàòåëüíî, â ïîñëåäîâàòåëüíîñòè xi áóäóò âñòðå÷àòüñÿ âñå ÷èñëà îò 1 äî B . Ê ìíîæåñòâó Dj îòíåñåì òå
÷èñëà z , äëÿ êîòîðûõ xz = j . Î÷åâèäíî, ÷òî ïîëó÷åííûé íàáîð ïîäìíîæåñòâ áóäåò ñåìåéñòâîì Øïåðíåðà,
òàê êàê íîìåð ìíîæåñòâà, ê êîòîðîìó áóäåò îòíåñåí ýëåìåíò, îïðåäåëÿåòñÿ îäíîçíà÷íî.
Äëÿ ðàñïðåäåëåíèÿ ìíîæåñòâ Di ïî ÿ÷åéêàì ìàòðèöû M D óïîðÿäî÷èì ÿ÷åéêè ìàòðèöû M , ëåæàùèå
âûøå ãëàâíîé äèàãîíàëè è ñîäåðæàùèå åäèíè÷íûå ýëåìåíòû, ïî âîçðàñòàíèþ ïî ñóììå èíäåêñîâ. Åñëè äâà
ýëåìåíòà èìåþò îäèíàêîâóþ ñóììó èíäåêñîâ, òî ïåðâûì áóäåò èäòè òîò, ó êîòîðîãî ìåíüøå íîìåð ñòðîêè.
Ñîïîñòàâèì ýòèì ÿ÷åéêàì ìíîæåñòâà ñåìåéñòâà Øïåðíåðà, óïîðÿäî÷åííûå ïî âîçðàñòàíèþ èõ èíäåêñà.
Âíåñåì ñîîòâåòñòâóþùåå ìíîæåñòâî èç ñåìåéñòâà Øïåðíåðà â ÿ÷åéêè ìàòðèöû M D, ñ èíäåêñàìè, ñîâ-
ïàäàþùèìè ñ èíäåêñàìè ýëåìåíòà ìàòðèöû M è ïåðåñòàíîâêå èíäåêñîâ. Äîïîëíèòåëüíîå ïåðåìåøèâàíèå
ïîäìíîæåñòâ Di íå òðåáóåòñÿ, òàê êàê îíè ñôîðìèðîâàíû äîñòàòî÷íî ñëó÷àéíî.
Çàêëþ÷åíèå
Òàêèì îáðàçîì ïðåäëîæåííàÿ ìîäèôèöèðîâàííàÿ KDP-ñõåìà ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé
ïîçâîëÿåò ðåàëèçîâàòü âèðòóàëüíûå êîìïüþòåðíûå ñåòè. Âèðòóàëüíûå ñåòè, ðåàëèçîâàííûå ñ ïîìîùüþ
ñõåìû ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé îáëàäàþò âñåìè íåîáõîäèìûìè àòðèáóòàìè äëÿ ôóíêöè-
îíèðîâàíèÿ â êà÷åñòâå âèðòóàëüíûõ ÷àñòíûõ ñåòåé. Äëÿ ïîëíîôóíêöèîíàëüíîé ðåàëèçàöèè âèðòóàëüíîé
÷àñòíîé ñåòè íåîáõîäèìî ñõåìû ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ êëþ÷åé äîïîëíèòü êðèïòîãðàôè÷åñêèìè
ïðîòîêîëàìè íà îñíîâå êðèïòîãðàôèè ñ îòêðûòûì êëþ÷îì.
Ñïèñîê ëèòåðàòóðû
[1] C.J. Mitchell, C. Piper, Key storage in Secure Networks. Discrete and Applied Math. 21:215228, 1988.
[2] C.J. Mitchell, Combinatorial techniques for key storage reduction in secure networks. Technical memo .
Hewlett-Packard Laboratories. Bristol, 1988.
[3] W. Du, J. Deng, Y.S. Han, P.K. Varshney, A pairwise key pre-distribution for wireless sensor networks.
CCS03, Washington, DC, USA. 4251, 2003.
[4] R. Anderson, H. Chan, A. Perrig Key infection: Smart trust for smart dust. ICNP'04, Berlin, Germany.
2004.
[5] H. Chan, A. Perrig, D. Song, Key distribution techniques for sensor networks. in Wireless Sensor Networks,
Springer US. 277303, 2004.
[6] D. Liu, P. Ning, Location-based pairwise key establishments for static sensor networks. 1st ACM Workshop
Security of Ad Hoc and Sensor Networks Fairfax, Virginia. 7282, 2003.
[7] W. Du, J. Deng, Y.S. Han, P.K. Varshney, A key management scheme for wireless sensor networks using
deployment knowledge. IEEE Transactions on Parallel & Distributed Systems. 19(10):14111425, 2008.
[8] Y. Jin, L. Wang, Y. Kim, X.-Z. Yang, Energy E cient Non-uniform Clustering Division Scheme in Wireless
Sensor Networks. Wireless Personal Communications. 45(1):3143, 2008.
[9] D. Huang, M. Mehta, D. Medhi, L. Harn, Location-aware key management scheme for wireless sensor
networks. SASN04, Washington, DC, USA. 2942, 2004.
[10] Y.W. Law, R. Corin, S. Etalle, P.H. Hartel, A formally verifed decentralized key management architecture
for wireless sensor networks. in Personal Wireless Communications. 2739, Springer Berlin Heidelberg, 2003.
[11] M. Dyer, T. Fenner, A. Frieze, A. Thomason, On key storage in secure networks. J. Cryptology, 8:189200,
1995.
The VPN Implementation on Base of the KDP-Scheme
Sergey V. Belim, Svetlana Yu. Belim
In paper the modi cation of KDP-scheme is suggested. The discretionary security policy is implemented on
base of KDP-scheme. This scheme is used for release VPN. The algorithm for pair keys calculation is developed.