Ðåàëèçàöèÿ 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 Ecient 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 modication 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.