سیستم رمزنگاری کوله پشتی مرکل-هلمن

روش مرکل-هلمن، یک روش رمزنگاری نامتقارن است. به این معنی که برای ارتباط، به دو کلید نیاز داریم: یک کلید عمومی و یک کلید خصوصی. همچنین بر خلاف الگوریتم RSA، یک طرفه است. یعنی از کلید عمومی فقط برای رمزنگاری و از کلید خصوصی فقط برای رمز گشایی استفاده می‌شود.بنابراین توسط امضای دیجیتال تصدیق نمی‌شود.

سیستم مرکل-هلمن بر پایه ی مسئله جمع زیرمجموعه ها ( نوع خاصی از مسئله کوله‌پشتی ) بناشده است. مسئله جمع زیر مجموعه ها از این قرار است: مجموعه‌ای از اعداد به نام ${\displaystyle A}$

تولید کلید

در سیستم مرکل-هلمن، کلیدها همان کوله پشتی‌ها هستند. کلید عمومی یک کوله پشتی 'سخت' و کلید خصوصی یک کوله پشتی 'آسان'، یا سوپرافزایشی، است. اما برای کلید خصوصی، از تغییر هوشمندانه‌ای استفاده می کنیم: با استفاده از یک ضریب ${\displaystyle r}$

رمز نگاری

برای رمز کردن یک پیغام، زیر مجموعه‌ای از کوله پشتی سخت انتخاب می‌شود. به این ترتیب که متن را که در قالب تعدادی 0 و 1 نمایش داده می‌شود با مسئله ی کوله پشتی ای با طول مشابه مقایسه می کنیم. اگر در جایگاه ${\displaystyle i}$

رمز گشایی

رمز گشایی پیغام به این صورت انجام می‌گیرد: ضریب و پیمانه‌ای که برای تبدیلِ کوله پشتی ساده به سخت، استفاده شدند، می‌توانند برای تبدیل پیام رمز شده به جمع اعضای مورد نظرِ کوله پشتی سوپرافزایشی نیز مورد استفاده قرار گیرند. سپس با استفاده از یک الگوریتم حریصانه ی ساده، مسئله ی کوله پشتی آسان با مرتبه ی زمانی O(n) حل می‌شود و پیغام رمزگشایی می‌شود.

تولید کلید

برای رمز نگاری پیام‌های n- بیتی، یک رشته ی سوپرافزایشی مانند ${\displaystyle w=(w_1,w_2,\dots ,w_n)}$

${\displaystyle q}$

حال رشته ی β را محاسبه کنید : ${\displaystyle \beta =({\beta }_1,{\beta }_2,\dots ,{\beta }_n)}$

رمز نگاری

برای رمزکردن یک پیام n-بیتیِ:

${\displaystyle \alpha =({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)}$

که ${\displaystyle {\alpha }_i}$

${\displaystyle c=\sum _{i=1}^n{\alpha }_i{\beta }_i}$

را محاسبه کنید. پیام رمز شده همان ${\displaystyle c}$

رمز گشایی

برای رمزگشاییِ پیامِ رمز شده ی ${\displaystyle c}$

${\displaystyle c=\sum _{i=1}^n{\alpha }_i{\beta }_i.}$

این مسئله در صورتی که ${\displaystyle {\beta }_i}$

برای رمزگشایی، باید عدد صحیح ${\displaystyle s}$

${\displaystyle s\ast r\equiv 1(\mathrm{mod}q)}$

صدق می‌کند یا به عبارتی، عدد صحیح ${\displaystyle k}$

${\displaystyle s\ast r=k\ast q+1}$

از آنجایی که ${\displaystyle r}$

${\displaystyle c^{\prime }\equiv cs(\mathrm{mod}q)}$

بنابراین:

${\displaystyle c^{\prime }\equiv cs\equiv \sum _{i=1}^n{\alpha }_i{\beta }_{i}s(\mathrm{mod}q)}$

از آنجایی که ${\displaystyle r\ast s\equiv 1(\mathrm{mod}q)}$

${\displaystyle {\beta }_{i}s\equiv w_{i}rs\equiv w_i(\mathrm{mod}q)}$

بنابراین:

${\displaystyle c^{\prime }\equiv \sum _{i=1}^n{\alpha }_i{w}_i(\mathrm{mod}q)}$

مجموع تمام مقادیر ${\displaystyle w_i}$

${\displaystyle c^{\prime }=\sum _{i=1}^n{\alpha }_i{w}_i}$

مسئله ساده است زیرا ${\displaystyle w}$

در ابتدا، یک دنباله ی سوپر افزایشی می سازیم و آن را ${\displaystyle w}$

${\displaystyle w=\{2,7,11,21,42,89,180,354\}}$

این پایه ی کلید خصوصی است. از این دنباله، جمع اعضا را محاسبه کنید:

${\displaystyle \sum w=706}$

سپس عدد ${\displaystyle q}$

${\displaystyle q=881}$

همچنین عدد ${\displaystyle r}$

${\displaystyle r=588}$

کلید خصوصی از ${\displaystyle q}$

برای محاسبه ی کلید عمومی، دنباله ی ${\displaystyle \beta }$

${\displaystyle \beta =\{295,592,301,14,28,353,120,236\}}$

زیرا:

${\displaystyle 2\ast 588\equiv 295(\mathrm{mod}881)}$

${\displaystyle 7\ast 588\equiv 592(\mathrm{mod}881)}$

${\displaystyle 11\ast 588\equiv 301(\mathrm{mod}881)}$

${\displaystyle 21\ast 588\equiv 14(\mathrm{mod}881)}$

${\displaystyle 42\ast 588\equiv 28(\mathrm{mod}881)}$

${\displaystyle 89\ast 588\equiv 353(\mathrm{mod}881)}$

${\displaystyle 180\ast 588\equiv 120(\mathrm{mod}881)}$

${\displaystyle 354\ast 588\equiv 236(\mathrm{mod}881)}$

دنباله ی ${\displaystyle \beta }$

برای مثال فرض کنید آلیس می‌خواهد رشته ی ${\displaystyle a}$

${\displaystyle 01100001}$

او بیت ${\displaystyle i}$

${\displaystyle a=01100001}$

${\displaystyle 0\ast 295}$

${\displaystyle +1\ast 592}$

${\displaystyle +1\ast 301}$

${\displaystyle +0\ast 14}$

${\displaystyle +0\ast 28}$

${\displaystyle +0\ast 353}$

${\displaystyle +0\ast 120}$

${\displaystyle +1\ast 236}$

${\displaystyle =1129}$

و در نهایت عدد بدست آمده، یعنی 1129 را به دریافت‌کننده ی پیام می فرستد.

باب برای رمزگشایی پیام، عدد 1129 را در ${\displaystyle r^{-1}(\mathrm{mod}q)}$

${\displaystyle 1129\ast 442\equiv 372(\mathrm{mod}881)}$

حال باب بزرگترین عضو ${\displaystyle w}$

${\displaystyle 372-354=18,18-11=7,7-7=0}$

اعضایی که از کلید خصوصی انتخاب کردیم، متناظر با بیت‌های یکِ پیامِ

${\displaystyle 01100001}$

بودند. وقتی از حالت دودویی به رشته‌ای از حروف تبدیل می‌شود، مشاهده می‌شود پیام دریافتی به درستی رمزگشایی شده و همان پیام فرستاده شده‌است.