سیستم رمزنگاری کوله پشتی مرکل-هلمن کیست؟ توضیح بده.
سیستم رمزنگاریِ کوله پشتی ِ مرکل-هلمن یکی از اولین رمزنگاری‌های کلید عمومی است که توسط رالف مرکل و مارتین هلمن در سال 1987 ارائه شد . با وجود اینکه ایده‌های این الگوریتم ساده‌تر و بسیار هوشمندانه تر از الگوریتم آر اس ای است، این سیستم رمزنگاری شکسته شده‌است.تعریف.روش مرکل-هلمن، یک روش رمزنگاری نامتقارن است. به این معنی که برای ارتباط، به دو کلید نیاز داریم: یک کلید عمومی و یک کلید خصوصی. همچنین بر خلاف الگوریتم RSA، یک طرفه است. یعنی از کلید عمومی فقط برای رمزنگاری و از کلید خصوصی فقط برای رمز گشایی استفاده می‌شود.بنابراین توسط امضای دیجیتال تصدیق نمی‌شود.سیستم مرکل-هلمن بر پایه ی مسئله جمع زیرمجموعه ها ( نوع خاصی از مسئله کوله‌پشتی ) بناشده است. مسئله جمع زیر مجموعه ها از این قرار است: مجموعه‌ای از اعداد به نام formula_1 و عددی به نام formula_2 داده شده‌اند. زیر مجموعه‌ای از formula_1 را بیابید که جمع اعضایش برابر با formula_2 شود. در حالت کلی، این مسئله NP کامل است. اما اگر مجموعه ی اعداد (یا همان کوله پشتی) سوپر افزایشی باشد، مسئله در زمان چندجمله ای با استفاده از الگوریتم حریصانه قابل حل می‌شود. منظور از سوپر افزایشی این است که: هر عضو در مجموعه، از جمع اعضای قبل از آن اکیداً بزرگتر باشد.تولید کلید.در سیستم مرکل-هلمن، کلیدها همان کوله پشتی‌ها هستند. کلید عمومی یک کوله پشتی 'سخت' و کلید خصوصی یک کوله پشتی 'آسان'، یا سوپرافزایشی، است. اما برای کلید خصوصی، از تغییر هوشمندانه‌ای استفاده می کنیم: با استفاده از یک ضریب formula_5 و یک پیمانه formula_6. به این ترتیب که هر عدد دلخواه formula_7 را به عدد: formula_8 تبدیل می کنیم. این تبدیل یک کوله پشتی ساده از نوع سوپرافزایشی را به یک کوله پشتی سخت تبدیل می‌کند. بار دیگر از اعداد formula_5 و formula_6 برای تبدیل جمع زیرمجموعه ی مسئله ی سخت به جمع زیر مجموعه ی مسئله ی ساده، که در زمان چندجمله‌ای حل می‌شود، استفاده می‌شود.رمز نگاری.برای رمز کردن یک پیغام، زیر مجموعه‌ای از کوله پشتی سخت انتخاب می‌شود. به این ترتیب که متن را که در قالب تعدادی 0 و 1 نمایش داده می‌شود با مسئله ی کوله پشتی ای با طول مشابه مقایسه می کنیم. اگر در جایگاه formula_11 ام متن، 1 دیدیم، شی شماره formula_11 را انتخاب می کنیم و در غیر این صورت انتخاب نمی‌شود. اعضای زیرمجموعه ی انتخاب شده با هم جمع کرده، و جمع نهایی همان پیام رمز شده‌است.رمز گشایی.رمز گشایی پیغام به این صورت انجام می‌گیرد: ضریب و پیمانه‌ای که برای تبدیلِ کوله پشتی ساده به سخت، استفاده شدند، می‌توانند برای تبدیل پیام رمز شده به جمع اعضای مورد نظرِ کوله پشتی سوپرافزایشی نیز مورد استفاده قرار گیرند. سپس با استفاده از یک الگوریتم حریصانه ی ساده، مسئله ی کوله پشتی آسان با مرتبه ی زمانی O(n) حل می‌شود و پیغام رمزگشایی می‌شود.روش ریاضی.تولید کلید.برای رمز نگاری پیام‌های n- بیتی، یک رشته ی سوپرافزایشی مانند formula_13را انتخاب کنید که از formula_14 عدد طبیعیِ ناصفر تشکیل شده‌است. سپس دو عدد صحیح تصادفیِ formula_6 و formula_5 را طوری انتخاب کنید که :formula_17 و بزرگترین مقسوم علیه مشترک formula_18 و formula_6 برابر با 1 باشد. (یعنی دو عدد نسبت به هم اول باشند.)formula_6 به گونه‌ای انتخاب شده که پیام رمز شده به‌طور یکتا تعیین شود. اگر formula_6 کوچکتر از این مقدار باشد، ممکن است بیش از یک پیام به یک رمز تبدیل شوند. formula_5 هم باید نسبت به q اول باشد، در غیر این صورت به پیمانه ی formula_6 وارون نخواهد داشت. وجود وارون formula_18 برای رمزگشایی ضروری است.حال رشته ی β را محاسبه کنید :formula_25کهformula_26 . کلید عمومیformula_27و کلید خصوصیformula_28است.رمز نگاری.برای رمزکردن یک پیام n-بیتیِ:formula_29که formula_30بیتِ formula_11امِ پیام است و formula_32 ، مقدارِ:formula_33را محاسبه کنید. پیام رمز شده همان formula_34 است.رمز گشایی.برای رمزگشاییِ پیامِ رمز شده ی formula_34، دریافت‌کننده ی پیام باید بیت‌های formula_36 را پیدا کند، طوری که:formula_37این مسئله در صورتی که formula_38‌ها مقادیری تصادفی باشند، بسیار دشوار است. زیرا دریافت‌کننده ی پیام باید مسئله‌ای از نوع جمع زیرمجموعه‌ها را حل کند، که در حالت کلی NP-سخت است. اما formula_38‌ها طوری انتخاب شده اند که اگر کلیدِ خصوصی formula_40 معلوم باشد، پیام به سادگی رمز گشایی شود.برای رمزگشایی، باید عدد صحیح formula_41 را طوری بیابیم که وارون پیمانه‌ای ِ formula_5 به پیمانه ی formula_6 باشد. یعنی formula_41 در نامساوی:formula_45صدق می‌کند یا به عبارتی، عدد صحیح formula_46 وجود دارد طوری که:formula_47از آنجایی که formula_5 طوری انتخاب شده بود که formula_49، با استفاده از الگوریتم اقلیدسی توسعه یافته می‌توان formula_41 و formula_46 را محاسبه نمود. سپس دریافت‌کننده ی پیام، محاسبات زیر را انجام می دهد:formula_52بنابراین:formula_53از آنجایی که formula_54 و formula_26 داریم:formula_56بنابراین:formula_57مجموع تمام مقادیر formula_58 کوچکتر از formula_6 است. بنابراین formula_60 هم در بازه ی formula_61 قرار دارد. بنابراین دریافت‌کننده ی پیام، باید مسئله ی جمع زیر مجموعه‌ها ی زیر را حل کند:formula_62مسئله ساده است زیرا formula_63 یک دنباله ی سوپرافزایشی است. بزرگترین عضو formula_63 را در نظر بگیرید؛ فرض کنیم formula_65 باشد. اگر formula_66 باشد، formula_67 و در غیر اینصورت formula_68 است. سپس formula_69 را از formula_70 کم کنید و این مراحل را تکرار کنید تا formula_71 به‌طور کامل بدست آید.مثال.در ابتدا، یک دنباله ی سوپر افزایشی می سازیم و آن را formula_63 نام‌گذاری می کنیم:formula_73این پایه ی کلید خصوصی است. از این دنباله، جمع اعضا را محاسبه کنید:formula_74سپس عدد formula_6 را طوری انتخاب کنید که بزرگتر از مجموع باشد:formula_76همچنین عدد formula_5 را طوری انتخاب کنید که در محدوده ی formula_78 بوده و نسبت به q اول باشد:formula_79کلید خصوصی از formula_6 ، formula_63 و formula_5 تشکیل شده‌است.برای محاسبه ی کلید عمومی، دنباله ی formula_27 را با ضرب کردن هر عضوِ formula_63 در formula_5 و باقی‌مانده گرفتن نسبت به formula_6 بدست می آوریم:formula_87زیرا:formula_88formula_89formula_90formula_91formula_92formula_93formula_94formula_95دنباله ی formula_27، کلید عمومی را می سازد.برای مثال فرض کنید آلیس می‌خواهد رشته ی formula_7 را رمز کند. ابتدا باید formula_7 را به صورت دودویی نمایش داده، به رشته‌ای از 0 و 1 تبدیل کند. (با استفاده از ASCII یا UTF-8 )formula_99او بیت formula_11 ام را در عضو شماره formula_11 از دنباله ی formula_27 ضرب کرده، آن‌ها را با هم جمع می‌کند:formula_103formula_104formula_105formula_106formula_107formula_108formula_109formula_110formula_111formula_112و در نهایت عدد بدست آمده، یعنی 1129 را به دریافت‌کننده ی پیام می فرستد.باب برای رمزگشایی پیام، عدد 1129 را در formula_113 ضرب می‌کند. (برای اطلاعات بیشار وارون پیمانه ای را ببینید.)formula_114حال باب بزرگترین عضو formula_63 را که کمتر یا مساوی 372 باشد، انتخاب می‌کند. آن را از 372 کم می‌کند (باقی‌مانده را formula_116 بنامید) و به‌طور مشابه ادامه می‌دهد. یعنی بزرگترین عضور از formula_63 را که کوچکتر یا مساوی formula_116 باشد انتخاب می‌کند و این فرایند را تا زمانی که به باقی‌مانده ی 0 برسد ادامه می دهد:formula_119اعضایی که از کلید خصوصی انتخاب کردیم، متناظر با بیت‌های یکِ پیامِformula_120بودند. وقتی از حالت دودویی به رشته‌ای از حروف تبدیل می‌شود، مشاهده می‌شود پیام دریافتی به درستی رمزگشایی شده و همان پیام فرستاده شده‌است.