سیستم رمزنگاری کوله پشتی مرکل-هلمن
سیستم رمزنگاریِ کوله پشتی ِ مرکل-هلمن یکی از اولین رمزنگاری‌های کلید عمومی است که توسط رالف مرکل و مارتین هلمن در سال 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_88
formula_89
formula_90
formula_91
formula_92
formula_93
formula_94
formula_95
دنباله ی formula_27، کلید عمومی را می سازد.
برای مثال فرض کنید آلیس می‌خواهد رشته ی formula_7 را رمز کند. ابتدا باید formula_7 را به صورت دودویی نمایش داده، به رشته‌ای از 0 و 1 تبدیل کند. (با استفاده از ASCII یا UTF-8 )
formula_99
او بیت formula_11 ام را در عضو شماره formula_11 از دنباله ی formula_27 ضرب کرده، آن‌ها را با هم جمع می‌کند:
formula_103
formula_104
formula_105
formula_106
formula_107
formula_108
formula_109
formula_110
formula_111
formula_112
و در نهایت عدد بدست آمده، یعنی 1129 را به دریافت‌کننده ی پیام می فرستد.
باب برای رمزگشایی پیام، عدد 1129 را در formula_113 ضرب می‌کند. (برای اطلاعات بیشار وارون پیمانه ای را ببینید.)
formula_114
حال باب بزرگترین عضو formula_63 را که کمتر یا مساوی 372 باشد، انتخاب می‌کند. آن را از 372 کم می‌کند (باقی‌مانده را formula_116 بنامید) و به‌طور مشابه ادامه می‌دهد. یعنی بزرگترین عضور از formula_63 را که کوچکتر یا مساوی formula_116 باشد انتخاب می‌کند و این فرایند را تا زمانی که به باقی‌مانده ی 0 برسد ادامه می دهد:
formula_119
اعضایی که از کلید خصوصی انتخاب کردیم، متناظر با بیت‌های یکِ پیامِ
formula_120
بودند. وقتی از حالت دودویی به رشته‌ای از حروف تبدیل می‌شود، مشاهده می‌شود پیام دریافتی به درستی رمزگشایی شده و همان پیام فرستاده شده‌است.