موضوع مقاله: سیستم رمزنگاری کوله پشتی مرکل-هلمن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # سیستم رمزنگاری کوله پشتی مرکل-هلمن | مقدمه: به این معنی که برای ارتباط، به دو کلید نیاز داریم: یک کلید عمومی و یک کلید خصوصی. | ## بخش 1: سیستم رمزنگاری کوله پشتی مرکل-هلمن | یعنی از کلید عمومی فقط برای رمزنگاری و از کلید خصوصی فقط برای رمز گشایی استفاده می‌شود.بنابراین توسط امضای دیجیتال تصدیق نمی‌شود. سیستم مرکل-هلمن بر پایه ی مسئله جمع زیرمجموعه ها ( نوع خاصی از مسئله کوله‌پشتی ) بناشده است. مسئله جمع زیر مجموعه ها از این قرار است: مجموعه‌ای از اعداد به نام و عددی به نام داده شده‌اند. اما اگر مجموعه ی اعداد (یا همان کوله پشتی) سوپر افزایشی باشد، مسئله در زمان چندجمله ای با استفاده از الگوریتم حریصانه قابل حل می‌شود. منظور از سوپر افزایشی این است که: هر عضو در مجموعه، از جمع اعضای قبل از آن اکیداً بزرگتر باشد. کلید عمومی یک کوله پشتی 'سخت' و کلید خصوصی یک کوله پشتی 'آسان'، یا سوپرافزایشی، است. اما برای کلید خصوصی، از تغییر هوشمندانه‌ای استفاده می کنیم: با استفاده از یک ضریب و یک پیمانه . این تبدیل یک کوله پشتی ساده از نوع سوپرافزایشی را به یک کوله پشتی سخت تبدیل می‌کند. بار دیگر از اعداد و برای تبدیل جمع زیرمجموعه ی مسئله ی سخت به جمع زیر مجموعه ی مسئله ی ساده، که در زمان چندجمله‌ای حل می‌شود، استفاده می‌شود. به این ترتیب که متن را که در قالب تعدادی 0 و 1 نمایش داده می‌شود با مسئله ی کوله پشتی ای با طول مشابه مقایسه می کنیم. | ## بخش 2: سیستم رمزنگاری کوله پشتی مرکل-هلمن | اگر در جایگاه ام متن، 1 دیدیم، شی شماره را انتخاب می کنیم و در غیر این صورت انتخاب نمی‌شود. رمز گشایی رمز گشایی پیغام به این صورت انجام می‌گیرد: ضریب و پیمانه‌ای که برای تبدیلِ کوله پشتی ساده به سخت، استفاده شدند، می‌توانند برای تبدیل پیام رمز شده به جمع اعضای مورد نظرِ کوله پشتی سوپرافزایشی نیز مورد استفاده قرار گیرند. سپس با استفاده از یک الگوریتم حریصانه ی ساده، مسئله ی کوله پشتی آسان با مرتبه ی زمانی O(n) حل می‌شود و پیغام رمزگشایی می‌شود. روش ریاضی تولید کلید برای رمز نگاری پیام‌های n- بیتی، یک رشته ی سوپرافزایشی مانند را انتخاب کنید که از عدد طبیعیِ ناصفر تشکیل شده‌است. سپس دو عدد صحیح تصادفیِ و را طوری انتخاب کنید که : و بزرگترین مقسوم علیه مشترک و برابر با 1 باشد. (یعنی دو عدد نسبت به هم اول باشند.) به گونه‌ای انتخاب شده که پیام رمز شده به‌طور یکتا تعیین شود. رمز نگاری برای رمزکردن یک پیام n-بیتیِ: که بیتِ امِ پیام است و ، مقدارِ: را محاسبه کنید. رمز گشایی برای رمزگشاییِ پیامِ رمز شده ی ، دریافت‌کننده ی پیام باید بیت‌های را پیدا کند، طوری که: این مسئله در صورتی که ‌ها مقادیری تصادفی باشند، بسیار دشوار است. زیرا دریافت‌کننده ی پیام باید مسئله‌ای از نوع جمع زیرمجموعه‌ها را حل کند، که در حالت کلی NP-سخت است. اما ‌ها طوری انتخاب شده اند که اگر کلیدِ خصوصی معلوم باشد، پیام به سادگی رمز گشایی شود. | ## بخش 3: سیستم رمزنگاری کوله پشتی مرکل-هلمن | برای رمزگشایی، باید عدد صحیح را طوری بیابیم که وارون پیمانه‌ای ِ به پیمانه ی باشد. یعنی در نامساوی: صدق می‌کند یا به عبارتی، عدد صحیح وجود دارد طوری که: از آنجایی که طوری انتخاب شده بود که ، با استفاده از الگوریتم اقلیدسی توسعه یافته می‌توان و را محاسبه نمود. سپس دریافت‌کننده ی پیام، محاسبات زیر را انجام می دهد: بنابراین: از آنجایی که و داریم: بنابراین: مجموع تمام مقادیر کوچکتر از است. بنابراین دریافت‌کننده ی پیام، باید مسئله ی جمع زیر مجموعه‌ها ی زیر را حل کند: مسئله ساده است زیرا یک دنباله ی سوپرافزایشی است. مثال در ابتدا، یک دنباله ی سوپر افزایشی می سازیم و آن را نام‌گذاری می کنیم: این پایه ی کلید خصوصی است. از این دنباله، جمع اعضا را محاسبه کنید: سپس عدد را طوری انتخاب کنید که بزرگتر از مجموع باشد: همچنین عدد را طوری انتخاب کنید که در محدوده ی بوده و نسبت به q اول باشد: کلید خصوصی از ، و تشکیل شده‌است. برای محاسبه ی کلید عمومی، دنباله ی را با ضرب کردن هر عضوِ در و باقی‌مانده گرفتن نسبت به بدست می آوریم: زیرا: دنباله ی ، کلید عمومی را می سازد. (با استفاده از ASCII یا UTF-8 ) او بیت ام را در عضو شماره از دنباله ی ضرب کرده، آن‌ها را با هم جمع می‌کند: و در نهایت عدد بدست آمده، یعنی 1129 را به دریافت‌کننده ی پیام می فرستد. (برای اطلاعات بیشار وارون پیمانه ای را ببینید.) حال باب بزرگترین عضو را که کمتر یا مساوی 372 باشد، انتخاب می‌کند. یعنی بزرگترین عضور از را که کوچکتر یا مساوی باشد انتخاب می‌کند و این فرایند را تا زمانی که به باقی‌مانده ی 0 برسد ادامه می دهد: اعضایی که از کلید خصوصی انتخاب کردیم، متناظر با بیت‌های یکِ پیامِ بودند. | ## جمع‌بندی | وقتی از حالت دودویی به رشته‌ای از حروف تبدیل می‌شود، مشاهده می‌شود پیام دریافتی به درستی رمزگشایی شده و همان پیام فرستاده شده‌است.