چکیده
برای بیش تر سیستم های رمز، با به کارگیری یک کلید سیستم اصلی، نیاز است بسیاری از کلیدهای مهم رمزگذاری و رمزگشایی سیستم به خوبی محافظت شوند. سه مشکل عمده در این آرایش تک کلید وجود دارند. یکم، اگر کلید اصلی، به صورت تصادفی، میان عموم افشا شود، آن گاه تمام سیستم امنیت نخواهد داشت. دوم، اگر کلید اصلی از میان برود، آن گاه همه ی کلیدهای تحت حفاظت غیر قابل دست رسی خواهند شد. سوم، اگر دارند هی کلید اصلی خیانت کند، آن گاه همه اطلاعات مهم به طور کامل در دسترس برای دشمن قرار خواهد گرفت.
تسهیم راز تقسیم کردن یک راز میان مجموع های از شریک ها است، به گونه ای که، تنها زیرمجموعه هایی از پیش تعیین شده از سهم ها توانایی بازسازی راز را داشته باشند. طرح های تسهیم راز، به صورت مستقل، در سال 1979، توسط بلکلی و شمیر، به عنوان راه حلی برای حفاظت از کلیدهای رمز، مطرح شد. طرح های تسهیم راز میتوانند در همه موقعیت هایی، که دسترسی به منابعی مهم باید محدود باشد، به کار گرفته شوند. برای نمونه، می توان به باز کردن یک صندوق امانت یا پرتاب یک موشک اشاره کرد.
در این پایان نامه، به بررسی روش های گوناگون تسهیم راز می پردازیم . سپس، به بررسی تسهیم یک درخت، که یک گراف هم بند بدون دور است، می پردازیم . یک درخت، برای نمونه، می تواند ساختار یک ملکول شیمیایی یا یک امضای مشترک میان چند نفر باشد.
فهرست مطالب:
چکیده............................................................................................................ ١
مقدمه ............................................................................................................ ٢
١. آشنایی ....................................................................................................... ٤
١.١ . جرم های کامپیوتری ................................................................................................... ٤
٢.١ . اهمیت حفاظت اطلاعات ............................................................................................. ٤
٣.١ . آشنایی با تسهیم راز ................................................................................................... ٥
٤.١ . بررسی دو طرح تسهیم راز اولیه ................................................................................... ٦
١.۴.١ . طرح تسهیم راز بلکلی ....................................................................................... ٦
٢.۴.١ . طرح تسهیم راز شمیر ....................................................................................... ٧
٥.١ . ساختار این پایان نامه .................................................................................................. ٨
٢. تعریف ها .................................................................................................. ١٠
١.٢ . مدل عمومی برای طرح های تسهیم راز ......................................................................... ١٠
١.١.٢ . مرحله ی ساختن سهم ها ..................................................................................... ١٠
٢.١.٢ . مرحله ی توزیع سهم ها ...................................................................................... ١١
٣.١.٢ . مرحله بازسازی راز ....................................................................................... ١٢
۴.١.٢ . بههنگام کردن سهم ها ....................................................................................... ١٣
۵.١.٢ . رازهای صریح و رازهای ضمنی ....................................................................... ١٤
٢.٢ . ساختارهای دست رسی ............................................................................................. ١٤
١.٢.٢ . ویژگی یک نوایی ساختار دست رسی .................................................................... ١٤
٢.٢.٢ . زیرمجموعه های مجاز کمین و پایه ی ساختار دست رسی ........................................... ١٥
٣.٢.٢ . ویژگی ها و تعریف هایی دیگر ............................................................................ ١٦
٣.٢ . نرخ های اطلاعاتی .................................................................................................. ١٦
١.٣.٢ . نرخ اطلاعات ................................................................................................ ١٦
۴.٢ . طرح های تسهیم راز کامل و ناکامل .............................................................................. ١٧
١.۴.٢ . مدل انترپی یک طرح کامل ............................................................................... ١٨
٢.۴.٢ . طرح های تسهیم راز با امنیت محاسباتی ................................................................ ١٩
٣.۴.٢ . طرح های تسهیم راز ایدئال ................................................................................ ١٩
۴.۴.٢ . طرح های تسهیم راز ناکامل ............................................................................... ١٩
٣. ساختارهای طرح های تسهیم راز .................................................................... ٢٢
١.٣ . طرح های تسهیم راز آستانه ای ..................................................................................... ٢٢
١.١.٣ . طرح تسهیم راز بلکلی ..................................................................................... ٢٢
٢.١.٣ . طرح تسهیم راز شمیر ..................................................................................... ٢٤
٣.١.٣ . طرح های تسهیم راز آستانه ای بر پایه ی پراکنش اطلاعات ......................................... ٢٦
٢.٣ . طرح های تسهیم راز همه یاهیچ .................................................................................... ٢٧
١.٢.٣ . طرح تسهیم راز همه یاهیچ کارنین، گرین، و هلمن ................................................... ٢٨
٢.٢.٣ . طرح تسهیم راز این پایان نامه ............................................................................ ٢٩
٣.٣ . طرح های تسهیم راز با ساختار دست رسی گرافی .............................................................. ٢٩
١.٣.٣ . ساختارهای دست رسی گرافی ایدئال .................................................................... ٣٠
۴.٣ . طرح های تسهیم راز آستانه ای وزن دار .......................................................................... ٣٠
١.٤.٣ . طرح تسهیم راز آستانه ای وزن دار شمیر ............................................................... ٣١
٢.۴.٣ . ساختارهای دست رسی تحقق ناپذیر به صورت آستانه ای وزن دار .................................. ٣١
۵.٣ . طرح های تسهیم راز چندسطحی .................................................................................. ٣٢
ز
١.۵.٣ . تحقق یک طرح تسهیم راز چندسطحی ................................................................. ٣٢
٢.۵.٣ . گونه های دیگر تسهیم راز چندسطحی ................................................................... ٣٣
۶.٣ . طرح های تسهیم راز تکه ای ....................................................................................... ٣٣
١.۶.٣ . طرح تسهیم راز تکه ای در حالت خاص ................................................................ ٣٤
٢.۶.٣ . طرح تسهیم راز تکه ای در حالت کلی .................................................................. ٣٤
٧.٣ . طرح های تسهیم راز عمومی ...................................................................................... ٣٥
١.٧.٣ . طرح های تسهیم راز تجمعی .............................................................................. ٣٥
٢.٧.٣ . طرح های تسهیم راز بر پایه ی فرمول ها ................................................................ ٣٦
٣.٧.٣ . طرح های تسهیم راز بر پایه ی اطلاعات عمومی ..................................................... ٣٨
٨. طرح های تسهیم راز شیب ......................................................................................... ٣٩ .٣
١.٨.٣ . طرح های تسهیم راز شیب آستانه یی ..................................................................... ٣٩
٢.٨.٣ . طرح های تسهیم راز شیب خطی ......................................................................... ٤٠
٣.٨.٣ . طرح های تسهیم راز شیب عمومی تر . ................................................................... ٤١
۴. طرح پیش نهادی: تسهیم یک درخت برچسب دار ................................................. ٤٤
١.۴ تعریف های گراف .................................................................................................... ٤٤
١.١.۴ . تعریف های اولیه . ............................................................................................ ٤٤
٢.١.۴ . یک ریختی .................................................................................................... ٤٦
٣.١.۴ . گراف های برچسب دار ..................................................................................... ٤٧
۴.١.۴ . مسیر، دور، و هم بندی ..................................................................................... ٤٧
۵.١.۴ . زیرگراف ها و مولفه ها ..................................................................................... ٤٨
۶.١.۴ . درجه ی یک گره ............................................................................................ ٤٩
٧.١.۴ . درخت ها ...................................................................................................... ٤٩
٨.١.۴ . فاصله، قطر، شعاع، و مرکز ............................................................................. ٥٠
٩.١.۴ . درخت های ریشه دار ........................................................................................ ٥١
٢.۴ . کدهای پروفرمانند ................................................................................................... ٥١
١.٢.۴ روش های کدگذاری درخت های برچسب دار ............................................................ ٥٢
٢.٢.۴ . ساختن درخت از روی یک کد ........................................................................... ٥٣
٣.٢.۴ . الگوریتم کدگذاری درخت نوعی ......................................................................... ٥٤
۴.٢.۴ . دسته بندی کدهای پروفرمانند .............................................................................. ٥٦
٣.٤ . تسهیم یک درخت برچسب دار ..................................................................................... ٥٨
١.٣.۴ . پنهان کردن درخت ......................................................................................... ٥٨
٢.٣.۴ . تابع آونگی .................................................................................................... ٦٠
٣.٣.۴ . وارون تابع آونگی .......................................................................................... ٦٣
۴.٣.۴ . تعداد کم تر یا بیش تر شریک ها ............................................................................ ٦٥
۴.۴ . نتیجهگیری ............................................................................................................ ٦٥
۵. پیاده سازی، مقایسه ی طرح پیش نهادی، و پیش نهاد ادامه ی کار ............................. ٦٧
١.۵ . پیاده سازی طرح پیش نهادی ........................................................................................ ٦٧
١.١.۵ . ساختن سهم ها ................................................................................................ ٦٧
٢.١.۵ . بازسازی راز ................................................................................................ ٦٧
٢.۵ . مقایسه ی طرح پیش نهادی .......................................................................................... ٦٨
١.٢.۵ . طرح آستانه ای شمیر ....................................................................................... ٦٨
....................................................................................... ٦٩
