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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

سیستم رمزنگاریِ کوله پشتی ِ مرکل-هلمن یکی از اولین رمزنگاری های کلید عمومی است که توسط رالف مرکل و مارتین هلمن در سال 1987 ارائه شد .[۱] با وجود اینکه ایده های این الگوریتم ساده تر و بسیار هوشمندانه تر از الگوریتم آر اس ای است، این سیستم رمزنگاری شکسته شده است. [۲]

تعریف[ویرایش]

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

سیستم مرکل-هلمن بر پایه ی مسئله جمع زیرمجموعه ها ( نوع خاصی از مسئله کوله‌پشتی ) بناشده است. مسئله جمع زیر مجموعه ها از این قرار است: مجموعه ای از اعداد به نام  A و عددی به نام  b داده شده اند. زیر مجموعه ای از  A را بیابید که جمع اعضایش برابر با  b شود. در حالت کلی، این مسئله NP کامل است. اما اگر مجموعه ی اعداد (یا همان کوله پشتی) سوپر افزایشی باشد، مسئله در زمان چندجمله ای با استفاده از الگوریتم حریصانه قابل حل می شود. منظور از سوپر افزایشی این است که: هر عضو در مجموعه، از جمع اعضای قبل از آن اکیداً بزرگتر باشد.

تولید کلید[ویرایش]

در سیستم مرکل-هلمن، کلید ها همان کوله پشتی ها هستند. کلید عمومی یک کوله پشتی 'سخت' و کلید خصوصی یک کوله پشتی 'آسان'، یا سوپرافزایشی، است. اما برای کلید خصوصی، از تغییر هوشمندانه ای استفاده می کنیم: با استفاده از یک ضریب  r و یک پیمانه  q . به این ترتیب که هر عدد دلخواه  a را به عدد:  a*r  \pmod{q} تبدیل می کنیم. این تبدیل یک کوله پشتی ساده از نوع سوپرافزایشی را به یک کوله پشتی سخت تبدیل می کند. بار دیگر از اعداد  r و  q برای تبدیل جمع زیرمجموعه ی مسئله ی سخت به جمع زیر مجموعه ی مسئله ی ساده، که در زمان چند جمله ای حل می شود، استفاده می شود.

رمز نگاری[ویرایش]

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

رمز گشایی[ویرایش]

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

روش ریاضی[ویرایش]

تولید کلید[ویرایش]

برای رمز نگاری پیام های n- بیتی، یک رشته ی سوپرافزایشی مانند  w= (w_1, w_2, \ldots, w_n) را انتخاب کنید که از  n عدد طبیعیِ ناصفر تشکیل شده است. سپس دو عدد صحیح تصادفیِ  q و  r را طوری انتخاب کنید که :  q>\sum_{i = 1}^n w_i و بزرگترین مقسوم علیه مشترک  r و  q برابر با 1 باشد. (یعنی دو عدد نسبت به هم اول باشند.)

 q به گونه ای انتخاب شده که پیام رمز شده به طور یکتا تعیین شود. اگر  q کوچکتر از این مقدار باشد، ممکن است بیش از یک پیام به یک رمز تبدیل شوند.  r هم باید نسبت به q اول باشد، در غیر این صورت به پیمانه ی  q وارون نخواهد داشت. وجود وارون  r برای رمزگشایی ضروری است.

حال رشته ی β را محاسبه کنید :  \beta= (\beta_1, \beta_2, \ldots, \beta_n) که  \beta_i \equiv r*w_i \pmod{q} . کلید عمومی  \beta و کلید خصوصی  ( w , q , r ) است.

رمز نگاری[ویرایش]

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

\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_n )

که  \alpha_i بیتِ  i امِ پیام است و \alpha_i \in \{ 0 , 1 \} ، مقدارِ:

c = \sum_{i = 1}^n \alpha_i \beta_i

را محاسبه کنید. پیام رمز شده همان  c است.

رمز گشایی[ویرایش]

برای رمزگشاییِ پیامِ رمز شده ی  c ، دریافت کننده ی پیام باید بیت های  a_i را پیدا کند، طوری که:

 c = \sum_{i = 1}^n \alpha_i \beta_i.

این مسئله در صورتی که  \beta_i ها مقادیری تصادفی باشند، بسیار دشوار است. زیرا دریافت کننده ی پیام باید مسئله ای از نوع جمع زیرمجموعه ها را حل کند، که در حالت کلی NP-سخت است. اما  \beta_i ها طوری انتخاب شده اند که اگر کلیدِ خصوصی  ( w, q, r) معلوم باشد، پیام به سادگی رمز گشایی شود.

برای رمزگشایی، باید عدد صحیح  s را طوری بیابیم که وارون پیمانه ای ِ  r به پیمانه ی  q باشد. یعنی  s در نامساوی:

 s * r \equiv  1 \pmod{q}

صدق می کند یا به عبارتی، عدد صحیح  k وجود دارد طوری که:

 s * r =k*q+1

از آنجایی که  r طوری انتخاب شده بود که  gcd(r,q)=1، با استفاده از الگوریتم اقلیدسی توسعه یافته می توان  s و  k را محاسبه نمود. سپس دریافت کننده ی پیام، محاسبات زیر را انجام می دهد:

 c' \equiv cs \pmod{q}

بنابراین:

c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}

از آنجایی که  r*s \equiv 1 \pmod{q} و  \beta_i \equiv r*w_i \pmod{q} داریم:

\beta_i s\equiv w_i r s\equiv w_i\pmod{q}

بنابراین:

 c' \equiv \sum_{i = 1}^n \alpha_i w_i \pmod{q}

مجموع تمام مقادیر  w_i کوچکتر از  q است. بنابراین \sum_{i = 1}^n \alpha_i w_i هم در بازه ی  [0,q-1] قرار دارد. بنابراین دریافت کننده ی پیام، باید مسئله ی جمع زیر مجموعه ها ی زیر را حل کند:

 c' = \sum_{i = 1}^n \alpha_i w_i

مسئله ساده است زیرا  w یک دنباله ی سوپرافزایشی است. بزرگترین عضو  w را در نظر بگیرید؛ فرض کنیم  w_k باشد. اگر  w_k> c' باشد،  \alpha_k =0 و در غیر اینصورت  \alpha_k =1 است. سپس  w_k * \alpha _k را از  c' کم کنید و این مراحل را تکرار کنید تا  \alpha به طور کامل بدست آید.

مثال[ویرایش]

در ابتدا، یک دنباله ی سوپر افزایشی می سازیم و آن را  w نام گذاری می کنیم:

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

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

 \sum w = 706

سپس عدد  q را طوری انتخاب کنید که بزرگتر از مجموع باشد:

 q =881

همچنین عدد  r را طوری انتخاب کنید که در محدوده ی [1, q) بوده و نسبت به q اول باشد:

 r = 588

کلید خصوصی از  q ،  w و  r تشکیل شده است.

برای محاسبه ی کلید عمومی، دنباله ی  \beta را با ضرب کردن هر عضوِ  w در  r و باقی‌مانده گرفتن نسبت به  q بدست می آوریم:

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

زیرا:

 2 * 588 \equiv 295 \pmod{881}

 7 * 588 \equiv 592 \pmod{881}

 11 * 588 \equiv 301 \pmod{881}

 21 * 588 \equiv 14 \pmod{881}

 42 * 588 \equiv 28 \pmod{881}

 89 * 588 \equiv 353 \pmod{881}

 180 * 588 \equiv 120 \pmod{881}

 354 * 588 \equiv 236 \pmod{881}

دنباله ی  \beta ، کلید عمومی را می سازد.

برای مثال فرض کنید آلیس می خواهد رشته ی  a را رمز کند. ابتدا باید  a را به صورت دودویی نمایش داده، به رشته ای از 0 و 1 تبدیل کند. (با استفاده از ASCII یا UTF-8 )

  01100001

او بیت  i ام را در عضو شماره  i از دنباله ی  \beta ضرب کرده، آنها را با هم جمع می کند:

 a = 01100001

 0 * 295

  + 1 * 592

  + 1 * 301

  + 0 * 14

  + 0 * 28

  + 0 * 353

  + 0 * 120

  + 1 * 236

  = 1129

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

باب برای رمزگشایی پیام، عدد 1129 را در  r^{-1} \pmod {q} ضرب می کند. (برای اطلاعات بیشار وارون پیمانه ای را ببینید.)

1129 * 442 \equiv 372 \pmod {881}

حال باب بزرگترین عضو  w را که کمتر یا مساوی 372 باشد، انتخاب می کند. آن را از 372 کم می کند (باقی‌مانده را  x بنامید) و به طور مشابه ادامه می دهد. یعنی بزرگترین عضور از  w را که کوچکتر یا مساوی  x باشد انتخاب می کند و این فرایند را تا زمانی که به باقی‌مانده ی 0 برسد ادامه می دهد:

 372 - 354 = 18 ,\quad 18 - 11 = 7 ,\quad 7 - 7 = 0

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

 01100001

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

یادداشت ها[ویرایش]

  1. Merkle, Ralph and Martin Hellman, "Hiding information and signatures in trapdoor knapsacks," Information Theory, IEEE Transactions on, vol.24, no.5, pp. 525-530, Sep 1978 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=1055927
  2. Shamir, Adi, "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem," Information Theory, IEEE Transactions on, vol.30, no.5, pp. 699-704, Sep 1984 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=4568386

منابع[ویرایش]

  1. Merkle, Ralph and Martin Hellman, "Hiding information and signatures in trapdoor knapsacks," Information Theory, IEEE Transactions on, vol.24, no.5, pp. 525-530, Sep 1978 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=1055927
  2. Shamir, Adi, "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem," Information Theory, IEEE Transactions on, vol.30, no.5, pp. 699-704, Sep 1984 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=4568386