کد گذاری شبکه امنیت دو الیه یا 2-LSNC
نویسنده : مهدی حسن زاده , محمد روان بخش و yvind Ytrehus مترجم :شهرزاد امیررحیمی شماره دانشجویی :890110162
( min-cutبرش کمینه) از جریان شبکه از منبع به هریک از گیرنده ها بسنده میکند . در {3} , Caiو Yeungیک مشکل مهم امنیتی را ارائه کردند که میتوان با کد گذاری شبکه کاهش یابد. آنها مدلی برای امنیت کد گذاری شبکه خطی معرفی کردند که میتواند عالی ترین امنیت اطالعات را در مقابل جاسوسان ,کسانی که میتوانند تعداد محدودی از لینک های شبکه را استراق سمع کنند ,داشته باشد . روش آنها بر پایه تلفیق کردن ایده ی اشتراک محرمانه با محدودیت اندازه فیلد ها برای امنیت کد گذاری شبکه است . محدودیت ها بر پایه توپولوژی شبکه میباشد. محدوده اساسی برای این روش در اندازه فیلد الزم برای امنیت کد گذاری شبکه نهفته است . با توجه به شرایط الزم برای اندازه بزرگ فیلد , این مدل محاسباتی غیرعملی است. در ادامه مقاله , ما به نام مدل C&Yاز این مدل یاد میکنیم . در {4}, . feldman et alنشان داد که پیدا کردن یک ماتریس برای ساختار مطلوب کد گذاری امن شبکه معادل پیدا کردن یک کد خطی با برخی از خواص فاصله عمومی است .عالوه بر آن, آنها کران پایین انداره فیلد را بهبود دادند. آنها نشان دادند که اگر ما مقداری کمی از ظرفیت کلی را از دست دهیم , یک منبع تصادفی کد گذاری شبکه با اندازه فیلد کوچکتر از مدل C&Y قابل دست یابی است .در این مدل نتیجه افزایش سطح امنیت, نیاز به اندازه فیلد را باال میبرد. این خاصیت باعث میشود که این مدل در عمل ناکارآمد باشد. در {5} , Lima et alروشی دیگر برای دست یابی به امنیت کد گذاری شبکه را در نظر میگیرد. آنها نشان دادند که کد گذاری شبکه خطی هنگامی که شبکه با محدودیت های در گره های ورودی ساخته شده باشد , برای راه اندازی طرح امنیت کد گذاری شبکه کافی است . بعالوه ,آنها نشان داند که امنیت این مدل به طور کامل به توپولوژی شبکه بستگی دارد , که یکی از نقاط ضعف آن است {5} . همچنین در این مدل , باال بردن سطح کلمات کلیدی :کد گذاری شبکه, امنیت کد گذاری شبکه , اشتراک محرمانه . چکیده _ دو مشخصه مهم برای کاربران شبکه امنیت و هزینه بهربرداری از منابع میباشد. از دید هزینه , کدگذاری شبکه نویدی سودمند تر در مقایسه با مسیریابی معمولی میدهد. در این مقاله , الگویی جدید برای امنیت کد گذاری شبکه بیان میشود. این الگو کد گذاری شبکه امنیت دو الیه یا 2-LSNCنام دارد. مزیت های الگوی جدید ما در سه بخش مطرح میشود : 0) تعداد لینک های الزم برای انکه جاسوسان بتواند رمز را خارج کنند بهبود یافته . 8) برای انکه مقیاس پذیری را بررسی کنیم یک سیستم متریک به نام سطح امنیت ایجاد کردیم , و نشان دادیم که مدل ما با این استاندارد متریک مقیاس پذیر است . 3) مقایسه بین هزینه و سطح امنیت مورد بررسی قرار گرفت . در مدل ما , این هزینه کمتر از مدل مطرح شده Caiو Yeungاست. {3} هنگامی که اندازه شبکه و تعداد سینک ها به نقطه بحرانی میرسند. دست یافته ما در مقایسه با دیگر مدلها به وسیله ی شبیه سازی است .
0. معرفی
کد گذاری شبکه توسط Ahlswede et alمعرفی شد . در این الگوی ارتباطی , گره های نه تنها اجاره میدهند بسته های اصالح نشده به جلو فرستاده شوند , درحالی که در مسیریابی کالسیک ذخیره و ارسال به جلو شبکه محدود شده است , بلکه بسته های دریافت شده را برای ارسال به جلو , اصالح و ترکیب میکنند .در {8} . . Li et alثابت شده که کد گذاری شبکه خطی به ارسال چند پخشی اطالعات از یک منبع واحد به یک دریافت کننده ثابت در یک نرخ یکسان تا حداقل( برتمامی گیرنده ها )
هدف نشست چند پخشی این است که رشته ای از اطالعات نمادی تولید شده در یک منبع را به یک سری Tاز گره ها( بهتر است بگویم سری از سینک های ) برسانند. ماکزیمم تعداد انتقال مستقیم بین منبع و یک سینک در گراف مستقیم به عنوان جریان بیشینه ( )max-flowشناخته میشود ,که, تئوری معروف max-flow همانند min- cutبین منبع و سینک برقرار میشود. در یک چندپخشی جای که یک گره منبع اطالعات را به تمام سینک گره ها ارسال میکند ؛ امکان دارد با بکار بردن کد گذاری جریان شبکه به جریان بیشینه هر سینک دست بیابیم{0}. بدون کدگذاری شبکه این امکان همیشه وجود ندارد. در کد گذاری شبکه گره های میانی نه تنها نسخه برداری و ارسال به جلوی بسته های دریافتیشان را انجام میدهند بلکه میتوانند آنها را باهم ترکیب کنند. ایجاد یک کد شبکه از پیش تعیین شده شامل دو گام است : 0) یک زیرگراف برای انتقال جریان بیشینه اطالعات , و 8) اختصاص دادن روش رمزگشایی به این زیر گراف ؛ این اطالعات تهیه شده برای هر گره باید بسته های گرفته شده و لینک های خروجی را ترکیب کند . در {2} یک روش جبری برای رمزگشایی اراده شده و در {6} این الگوریتم با توسعه دوره تناوب زیرگراف ها(جریان دوره تناوب) انجام میشود . ب) اشتراک گذاری محرمانه در رمز نویسی ( , )cryptographyاشتراک گذاری محرمانه اشاره دارد به هر روشی که برای دسته بندی یک رمز (با وجود دالل) میان گروهی از nشرکت کننده (بازی کننده ), که به هر کدام سهمی از رمز اختصاص داده شده است .در یک ()n,tssآستانه روش اشتراک محرمانه , رمز تنها زمانی میتواند بازسازی شود که حداقل در نقطه پایان tssسهم های با یکدیگر ترکیب شوند .اشتراک محرمانه در سال 6760توسط }01{A.Shamirو }00{G.Blakleyمستقالنه ایجاد شد . هدف از اشتراک محرمانه این است که رمز Sدرون nسهم 1 sn....,sتقسیم گردد بدین صورت که : 0) شناسای هر tssیا siهای بیشتر کاری میکند Sآسان تر قابل تخمین زدن باشد
امنیت بستگی به افزایش اندازه فیلد و تعداد پروسه های تصادفی دارد. مشابه مدل قبلی این خاصیت باعث میشود که این مدل در عمل ناکارآمد باشد {5} .و مدل بیان شده در {5} در ایجاد امنیت در شبکه های حسگر استفاده میشود {7}. در این مقاله , مدل جدیدی برای امنیت شبکه ارائه میگردد . این مدل کد گذاری شبکه امنیت دو الیه یا 2- LSNCنام دارد. با این مدل , ما تعداد لینک های که یک جاسوس الزم دارد تا به رمز پیام دست بیابد , سطح امنیت و هزینه افزایش سطح ایمنی را بهبود داده ایم .مدل ما مقیاس پذیر است , بدین معنی که با رشد اندازه شبکه بهره وری بهبود می یابد.ما از شبیه سازیمان این خاصیت که در روش های قبلی نبود را مشاهده کردیم.بهبود امنیت در {3} و {5} تابعی از اندازه فیلد است. به معنای دیگر , پایداری در مقابل جاسوسان قدرتمند با استفاده از اندازه فیلد بزرگتر امکان پذیر است. هرچند, روش ما محدودیتی روی اندازه فیلد ندارد و تنها الزم است یک فیلد که بتواند راه حلی عملی برای کد گذاری شبکه ارائه دهد, استفاده شود . مقاله بدین صورت ترتیب بندی شده است : بخش 8 با معرفی کد گذاری و اشتراک محرمانه آغاز میشود . این بخش با جزئیاتی در مورد مدل C&Yادامه می یابد. یک مدل جدید برای اشتراک گذاری محرمانه در بخش 3 معرفی میشود . مدل امن کد گذاری شبکه ی ما در بخش 4 ام مطرح میشود . بخش 5 ام نتایج شبیه سازی را نشان میدهد. این مقاله در بخش 9 نتیجه گیری میشود .
8. مقدمه
الف ) مدل کدگذاری شبکه ما شبکه ارتباطی را با یک گراف جهت دار ) V,E( =G بازنمایی میکنیم , جای که Vبه جای گره ها ( یک منبع ,مسیریاب , و سینک ها / گیرنده ها ) و Eجای کران ها یا لینک ها است. تمام گره ها با رنجی از اعداد که از 1 (که برای گره منبع استفاده میشود) تا 1-| |Vمشخص میشوند. هر لینک ()i.j نمایشگر یک لینک نقطه به نقطه بدون از دست دادن اطالعات از نود iبه نود jاست . ) TI(iو ) TO(iبه تعداد لینک های که از نود iداخل و خارج میشود اشاره دارد.
8) شناسای هر 1- tssیا تعداد کمتر siاجازه میدهد Sبه طور کامل غیرقابل دسترس (نامعین) شود .
3. آستانه پیوسته ی اشتراک گذاری محرمانه
در این بخش ما نوع جدیدی از اشتراک گذاری محرمانه را معرفی میکنیم. این توسط سلایر های الحاقی طرح جزئی و طرح دیگر آستانه طراحی میشود. یک رمز Sاول تقسیم شده به nسهم ( )s1,s2,…,snبا استفاده از روش رمز اشتراک گذاشته شده ( , )n,nپس یک کاربر الزم است به تمام سهم ها ( )s1,s2,…,snبرای دوباره سازی رمز , Sدست یابد. در این مرحله , هر کدام از سهم های siتقسیم شده به miسهم با استفاده از یک روش اشتراک گذاری محرمانه آستانه ).(mi,t ss,iپارامتر miو tssiمیتواند برای هر سهم siمتفاوت باشد ولی برای سادگی میتوان آنها را به ترتیب عددی ثابت و برابر mو tssiدانست. به همین سبب,سهم های nt ssبرای باز سازی رمز Sالزم است و سری سهم های t ssباید از siمشابه دریافت شود.ما از این مدل با عنوان ) -(n,m,tssاشتراک گذاری پیوسته سطح آستانه یا CTSSیاد میکنیم. چهارچوب CTSSآن را برای مدل ما , در قسمت ساخت امنیت کد گذاری شبکه که در بخش 4 ارائه شده ؛ قابل استفاده کرده است. این نشان میدهد روش CTSSسطح امنیت را در مقایسه با مدل C&Yبهبود داده است. (0) در {10} یک نمونه (-)n,tssآغازگر روش پایه بر درون یابی چند جمله ای ارائه شده است . چند جمله ای میتواند جایگزین هر کدام از مجموعه تابع که برای ارزیابی آسان تر هستند,گردد. با در نظر گرفتن این مورد بدیهی روش ()n,nآستانه ؛ tss .e ,iبرابر است با .nدر این روش , 1- nعددی تصادفی (1-)r1,….,rn بعنوان سهم های 1- nایجاد شدند و برای سهم اخر ما خواهیم داشت : , rn−1 ⊕ . . . ⊕ r2 ⊕ r1 ⊕rn= Sجای که ⊕ از هر فرمول بعالوه جدا است . این واضح است که S میتواند با داشتن تمام سهم ها بدست آید,در حالی که هیچ زیرشبکه ای از 1- nیا سهم کمتر نمیتواند رمز Sرا بازیابی کند .ج) توصیف مدل Caiو Yeung در این زیر مجموعه ؛ مدل C&Yتوصیف میشود. در نظر بگیرید یک جاسوس به تعداد محدودی از لینک های توسط μ مشخص شده است ,دست رسی پیدا کرده باشد .از آنجای که جاسوس به زیرشبکه توسط μلینک , دست رسی پیدا کرده است , به طور مشخص, نمادهای h =R – μمیتوانند به طور ایمن انتقال یابند , جای که })R=min t∈ T{max-flow(t
4. پیشنهاد مدل کدگذاری امن شبکه
در این بخش , ما مدلی برای کدگذاری امن شبکه ارائه میکنیم که میتواند برای هر شبکه ای که بتواند راه حلی برای کد گذاری شبکه عملی سازد ,مطرح گردد. به معنی دیگر , هیچ شرط اضافه ای به شبکه تحمیل نشده برای آنکه وجود راه حل عملی را ضمانت کند . ما ثابت خواهیم کرد که مدل جدید در مقایسه با مدل C&Yبا نسبت به سطح امنیت مطرح شده در بخش V_B مطلوب تر است. ما روش CTSSمعرفی شده در بخش 3 را به کار گرفته ایم. از آنجای که روش جدید اشتراک گذاری محرمانه از دو گام اشتراک گذاری رمز در گره منبع و همسایگانش
تفسیر : برای سینک گره , t ∈ Tاگر کانالهای μدر شبکه
استراق سمع شوند , تعداد " مسیرهای امن " از منبع به گره T
( هرچند کاربران شبکه نمیدانند کدام مسیر
هنوز h=R- μ
امن است.) در نتیجه , یک بردار از نماد های )x=(x1,…xh میتواند با امنیت به هر مقصد فرستاده شود . از این رو , μ
مستقل ارقام تصادفی ( )r1,….r μایجاد میشوند و پیوند میخورد تا بردار ) y=(x1,…,xh,r1,… rμرا بسازد . در اخر , گره منبع با استفاده از ماتریس Mبردار c=Myرا میسازد و بردار cرا برای تمام گره های سینک به وسیله کد گذاری شبکه ارسال میکند .
در نگاهی کلی , رمز Sتقسیم شده به nΓOسهم و با ارسال چندپخشی به وسیله کد گذاری شبکه به تمام سینک ها ارسال شده است . هر سینک میتواند رمز Sرا از ntssسهم بازسازی کند . باید در نظر گرفت که نه همه ی سری ntssسهم میتواند رمز را بازسازی کنند. تنها اگر هر سینک حداقل tssسهم از هر گره در الیه دوم دریافت کند , رمز Sقابل استخراج است.این بدین معنی است که حتی اگر جاسوسان بتوانند ntssسهم را بگیرند , این سری گرفته شده تنها اگر دقیقا مربوط به nاصلی الیه اول باشد قابل استفاده است ,پس امنیت شبکه بهبود یافته است. ما نشان خواهیم داد که کد گذاری شبکه میتوان ضمانت کند د هر سری از tssسهم الیه دوم بتوانند به گره انتقال به هر سینک در الیه دوم برسند . جریان بیشینه ( )Rبین منبع و هر سینک باید بزرگتریا برابر ntssباشد . برای ایمنی , این مورد الزم است ).(ntss >= μ ب) بهینه سازی گراف در روش , 2-LSNCمجموعه های متفاوتی از جریان اطالعات باید به گره های الیه دوم ارسال شود. هر کدام از این جریان ها باید به هر یک از گره های سینک شده روی مسیری مجزا فرستاده شود. با مسیریابی , مشکل پیدا کردن محل مجزا روی درخت اشتاینر است {30},که به عنوان NP-hardشناخته میشود؛ و نتیجه نسبت به منبع شبکه نسبتا بی فایده است .حتی برای تعداد متوسطی از سینک گره ها , امکان دارد غیرممکن باشد که بتوانیم همچین درختی را به خود اختصاص دهند. واضح است تنها روش جایگزین استفاده از کد گذاری شبکه میباشد. در این زیر بخش ,ما تو توضیح میدهیم چگونه گراف ارسال چند پخشی کد گذاری شبکه را بهبود دهیم . در پایه کار , }08{lun et alما یک برنامه خطی استفاده کردیم تا هزینه را حداقل برسانیم و بتوانیم هدف خود را ایجاد کنیم. هدف این است که گراف با جریان الزم و حداقل هزینه را پیدا کنیم. یک هزینه ثابت و ظرفیت واحد برای هر لینک در نظر گرفته شده. CTSSبرای دست آورد ما ( )2-LSNCبرای تعدادی از لینک های خروجی از گره منبع استفاده شد (nخروجی ) تا اولین قدماشتراک گذاری محرمانه صورت گیرد. هر گره در الیه دوم به
تشکیل شده است , ما از این مدل جدید به عنوان کدگذاری شبکه امنیت دو الیه یا 2-LSNCیاد میکنیم. در زیر بخش 4-الف ما توضیح میدهیم چگونه از روش CTSS در مدل جدید استفاده کرده ایم. سپس در رابطه با بهینه سازی پردازش در دو الیه امن کد گذاری شبکه در زیربخش 4-ب بحث میکنیم. الف ) آستانه متنی پیوسته اشتراک گذاری محرمانه برای 2-LSNC از حاال به بعد, اولین الیه شبکه به گره منبع اشاره دارد که با 0 اندیس گذاری شده , در حالی که الیه دوم اشاره دارد به تمام گره های که از مستقیما از منبع اطالعات ورودی را دریافت میکنند. گره های الیه دوم از 0 تا ) ΓO(iاندیس گذاری شده اند . ما فرض میگیریم که لینک ها ) (0, iبرای ) i = 1. . . ΓO(iامن هستند . این فرضیه در بسیاری از شبکه ها عملی است و در مقایسه ی ما در بخش 5 تمام روش ها در نظر گرفته شده است. برای راحتی , ما در نظر گرفتیم ) ΓO(iبرای تمام نود های در الیه دوم یکسان است .) .(∀ i : ΓO(i) = ΓO یک روش CTSSبا پارامتر های ) (n, ΓO, tssدر دو الیه از شبکه استفاده میشود , جای که گره منبع نقش دالل را بازی میکند و تمام شرکت کنندگان را سینک میکند. به معنای دیگر , یک رمز Sدر الیه اول تقسیم شده به nسهم )(s1, s2, . . . , sn جای که ΓO(0) λبا افزایش μ وکاهش λرشد میکند . در نتیجه , Φاز فرمول زیر بدست میآید : بر پایه شکل 5 و 6 مشاهده میکنیم که برای تعداد کوچکی از گره ها یا سینک ها , مدل C&Yهزینه کارامدتری از مدل جدید دارد. هرچند مدل جدید مقایس بهتری دارد و در شبکه با تعداد گره ها و سینک ها باال کارامد تر است.
9. نتیجه گیری مدل جدید , دو الیه کد گذاری امن شبکه ( , )2-LSNCدر بسیاری از پارامترهای امنیتی نسبت به روش های قبلی بهبود یافته است. این پارامتر ها شامل ماکزیمم توان مقابله با جاسوسان, سطح امنیت و هزینه سطح امنیت هستند. مدل ما در مقابل جاسوسان قوی تر , پایدار تر است ,و هزینه افزایش سطح امنیت در مقایسه با مدل Caiو Yeongدر زمانی که اندازه شبکه و تعداد سینک ها به نقطه بحرانی میرسند , کمتر است. نتیجه شبیه سازی ما این بهبود ها را تایید میکند .
: منابع
}0{ R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network Information Flow”, IEEE Transactions on Information Theory, Vol. 46, April 2000, pp. 1204-1216. }8{ S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding”, IEEE Transactions on Information Theory, Vol. 49, February 2003, pp. 371-381. }3{ N. Cai, and R. W. Yeung, “Secure network coding”, Proceedings of IEEE Symposium on Information Theory, 2002 }4{ J. Feldman, T. Malkin, R. A. Servedio, and C. Stein, “On the Capacity of Secure Network Coding”, Proc. 42nd Annual Allerton Conference on Comunication, Control and Computing, September 2004. }5{ L. Lima, M. Medard, and J. Barros, “Random linear network coding: a free cipher?”, Proceedings of IEEE Symposium on Information Theory, 2007 }6{ T. Ho, M. Medard, J. Shi, M. Effros, and D.R. Karger, “On randomized network coding”, Proc. 41st Annual Allerton Conference on Comunication, Control and Computing, Oct. 2003. }7{ F. Lu, L. Geng, L. Chia, and Y. Liang, “Secure Multi-path in Sensor Networks”, Proc. the 5th international conference on Embedded networked sensor systems, 2007. }2{ S. Jaggi, P. Sanders, P.A. Chou, M. Effros, S. Egner, K. Jain and L.M.G.M. Tolhuizen,“Polynomial Time Algorithms for Multicast Network Code Construction”, IEEE Transactions on Information Theory, Vol. 51, June 2005, pp. 1973-1982. }6{ A´ . Barbero and Ø. Ytrehus, “Cycle-logical Treatment of ’Cyclopathic’ Networks”, IEEE Transactions on Information Theory, Vol. 52, June 2006, pp. 2795-2805. }01{ A. Shamir, “How to share a secret”, Communications of the ACM, Vol. 22(1), 1979, pp. 612-613. }00{ G. R. Blakley, “Safeguarding cryptographic keys”, Proc. the National Computer Conference, Vol. 48, 1979, PP. 313-317. }08{ D. S. Lun, N. Ratnakar, M. M´edard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, and F. Zhao “Minimum-Cost Multicast over Coded Packet Networks”, IEEE Transactions on Information Theory, Vol. 52, Issue 6, June 2006, pp. 2608– 2623. }03{ P. Winter, “Steiner problem in networks: A survey,”, Networks, vol. 17, Wiley-Interscience New York, 1987, pp. 129-167.