نظام تشفير حقيبة الظهر ميركل-هيلمان

الموسوعة الحرة

كان نظام التشفير ميركل -هيلمان للحقيبة أحد أوائل أنظمة التشفير بالمفتاح العام . نُشر بواسطة رالف ميركل ومارتن هيلمان عام 1978. ونُشر هجوم زمني متعدد الحدود بواسطة آدي شامير عام 1984. ونتيجة لذلك، يُعتبر نظام التشفير الآن غير آمن. [ 1 ] : 465 [ 2 ] : 190

تاريخ

طُرح مفهوم التشفير بالمفتاح العام لأول مرة على يد ويتفيلد ديفي ومارتن هيلمان عام 1976. [ 3 ] في ذلك الوقت، اقترحا المفهوم العام لـ "دالة أحادية الاتجاه ذات باب خلفي"، وهي دالة يستحيل حساب معكوسها حسابيًا دون وجود "معلومات سرية ذات باب خلفي"؛ لكنهما لم يعثرا بعد على مثال عملي لمثل هذه الدالة. ثم اقترح باحثون آخرون خلال السنوات القليلة التالية عدة أنظمة تشفير محددة بالمفتاح العام، مثل RSA عام 1977 و Merkle-Hellman عام 1978. [ 4 ]

وصف

ميركل-هيلمان هو نظام تشفير بالمفتاح العام، أي أنه يستخدم مفتاحين: مفتاح عام للتشفير ومفتاح خاص لفك التشفير. وهو مبني على مسألة مجموع المجموعات الجزئية (وهي حالة خاصة من مسألة حقيبة الظهر ). [ 5 ] وتتلخص المسألة فيما يلي: بفرض وجود مجموعة من الأعداد الصحيحةأ{\displaystyle A}وعدد صحيحج{\displaystyle c}، أوجد مجموعة جزئية منأ{\displaystyle A}وهو ما يعادلج{\displaystyle c}بشكل عام، من المعروف أن هذه المشكلة من فئة NP-complete . ومع ذلك، إذاأ{\displaystyle A}إذا كانت المجموعة فائقة التزايد ، مما يعني أن كل عنصر من عناصر المجموعة أكبر من مجموع جميع الأرقام في المجموعة الأصغر منه، فإن المشكلة "سهلة" ويمكن حلها في وقت متعدد الحدود باستخدام خوارزمية جشعة بسيطة .

في خوارزمية ميركل-هيلمان، يتطلب فك تشفير الرسالة حل مسألة حقيبة ظهر تبدو "صعبة". يحتوي المفتاح الخاص على قائمة متزايدة من الأرقام.دبليو{\displaystyle W}والمفتاح العام يحتوي على قائمة أرقام غير متزايدة بشكل مفرطب{\displaystyle B}، وهو في الواقع نسخة "مُقنّعة" مندبليو{\displaystyle W}يحتوي المفتاح الخاص أيضًا على بعض المعلومات "الخفية" التي يمكن استخدامها لتحويل مشكلة حقيبة الظهر الصعبة باستخدامب{\displaystyle B}تحويلها إلى مسألة حقيبة ظهر سهلة باستخدامدبليو{\displaystyle W}.

على عكس بعض أنظمة التشفير الأخرى ذات المفتاح العام مثل RSA ، فإن المفتاحين في خوارزمية Merkle-Hellman غير قابلين للتبديل؛ فلا يمكن استخدام المفتاح الخاص للتشفير. وبالتالي، لا يمكن استخدام Merkle-Hellman مباشرةً للمصادقة عن طريق التوقيع المشفر ، على الرغم من أن شامير نشر نسخة معدلة منه يمكن استخدامها للتوقيع. [ 6 ]

توليد المفاتيح

  1. اختر حجم الكتلةن{\displaystyle n}الأعداد الصحيحة حتىن{\displaystyle n}يمكن تشفير البيانات التي يبلغ طولها بتات باستخدام هذا المفتاح.
  2. اختر متتالية عشوائية متزايدة بشكل فائق منن{\displaystyle n}الأعداد الصحيحة الموجبة
    دبليو=(w1،w2،...،wن){\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}
    يعني هذا الشرط المتزايد بشكل كبير أنwك>∑أنا=1ك-1wأنا{\displaystyle w_{k}>\sum _{i=1}^{k-1}w_{i}}، ل1<ك≤ن{\displaystyle 1<k\leq n}.
  3. اختر عددًا صحيحًا عشوائيًاq{\displaystyle q}بحيث
    q>∑أنا=1نwأنا{\displaystyle q>\sum _{i=1}^{n}w_{i}}
  4. اختر عددًا صحيحًا عشوائيًار{\displaystyle r}بحيثالقاسم المشترك الأكبر(ر،q)=1{\displaystyle \gcd(r,q)=1}(إنه،ر{\displaystyle r}وq{\displaystyle q}( أعداد أولية فيما بينها ).
  5. احسب المتتابعة
    ب=(ب1،ب2،...،بن){\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}
    أينبأنا=رwأناتعديلq{\displaystyle b_{i}=rw_{i}{\bmod {q}}}.

المفتاح العام هوب{\displaystyle B}والمفتاح الخاص هو(دبليو،q،ر){\displaystyle (W,q,r)}.

التشفير

يتركم{\displaystyle m}كنن{\displaystyle n}رسالة مكونة من بتاتم1م2...من{\displaystyle m_{1}m_{2}\dots m_{n}}، معم1{\displaystyle m_{1}}أعلى بت. حدد كلبأنا{\displaystyle b_{i}}والتيمأنا{\displaystyle m_{i}}إذا كانت القيمة غير صفرية، فقم بجمعهما معًا. أو بعبارة أخرى، احسب

ج=∑أنا=1نمأنابأنا{\displaystyle c=\sum _{i=1}^{n}m_{i}b_{i}}.

النص المشفر هوج{\displaystyle c}.

فك التشفير

لفك تشفير نص مشفرج{\displaystyle c}، يجب علينا إيجاد المجموعة الجزئية منب{\displaystyle B}وهو ما يعادلج{\displaystyle c}نقوم بذلك عن طريق تحويل المشكلة إلى مشكلة إيجاد مجموعة جزئية مندبليو{\displaystyle W}يمكن حل هذه المشكلة في وقت متعدد الحدود لأندبليو{\displaystyle W}إنها تتزايد بشكل كبير.

  1. احسب المعكوس المعياري لـر{\displaystyle r}moduloq{\displaystyle q}باستخدام خوارزمية إقليدس الموسعة . سيكون المعكوس موجودًا لأنر{\displaystyle r}هو عدد أولي نسبيًا لـq{\displaystyle q}.
    ر′:=ر-1(تعديلq){\displaystyle r':=r^{-1}{\pmod {q}}}
    حسابر′{\displaystyle r'}وهو مستقل عن الرسالة، ويمكن القيام به مرة واحدة فقط عند إنشاء المفتاح الخاص.
  2. احسب
    ج′:=جر′تعديلq{\displaystyle c':=cr'{\bmod {q}}}
  3. حل مسألة مجموع المجموعات الجزئية لـج′{\displaystyle c'}باستخدام التسلسل المتزايد للغايةدبليو{\displaystyle W}، باستخدام خوارزمية الجشع البسيطة الموضحة أدناه. ليكنX=(x1،x2،...،xك){\displaystyle X=(x_{1},x_{2},\dots ,x_{k})}لتكن قائمة الفهارس الناتجة لعناصردبليو{\displaystyle W}والتي مجموعها يساويج′{\displaystyle c'}. (إنه،ج′=∑أنا=1كwxأنا{\displaystyle c'=\sum _{i=1}^{k}w_{x_{i}}}.)
  4. قم بصياغة الرسالةم{\displaystyle m}مع وجود 1 في كلxأنا{\displaystyle x_{i}}موضع البت و0 في جميع مواضع البت الأخرى:
    م=∑أنا=1ك2ن-xأنا{\displaystyle m=\sum _{i=1}^{k}2^{n-x_{i}}}

حل مسألة مجموع المجموعات الجزئية

تجد هذه الخوارزمية الجشعة البسيطة مجموعة جزئية من متتالية متزايدة للغايةدبليو{\displaystyle W}وهو ما يعادلج′{\displaystyle c'}، في وقت متعدد الحدود:

  1. تهيئةX{\displaystyle X}إلى قائمة فارغة.
  2. أوجد أكبر عنصر فيدبليو{\displaystyle W}وهو أقل من أو يساويج′{\displaystyle c'}، يقولwج{\displaystyle w_{j}}.
  3. طرح:ج′:=ج′-wج{\displaystyle c':=c'-w_{j}}.
  4. إلحاقج{\displaystyle j}إلى القائمةX{\displaystyle X}.
  5. يزيلwج{\displaystyle w_{j}}من التسلسل المتزايد للغايةدبليو{\displaystyle W}
  6. لوج′{\displaystyle c'}إذا كانت القيمة أكبر من الصفر، فارجع إلى الخطوة 2.

مثال

توليد المفاتيح

أنشئ مفتاحًا لتشفير الأرقام المكونة من 8 بتات عن طريق إنشاء تسلسل عشوائي متزايد بشكل فائق مكون من 8 قيم:

دبليو=(2،7،11،21،42،89،180،354){\displaystyle W=(2,7,11,21,42,89,180,354)}

مجموع هذه القيم هو 706، لذا اختر قيمة أكبر لـq{\displaystyle q}:

q=881{\displaystyle q=881}.

يختارر{\displaystyle r}أن يكون عدداً أولياً نسبياً لـq{\displaystyle q}:

ر=588{\displaystyle r=588}.

قم بإنشاء المفتاح العامب{\displaystyle B}عن طريق ضرب كل عنصر فيدبليو{\displaystyle W}بواسطةر{\displaystyle r}moduloq{\displaystyle q}:

(2*588)تعديل881=295(7*588)تعديل881=592(11*588)تعديل881=301(21*588)تعديل881=14(42*588)تعديل881=28(89*588)تعديل881=353(180*588)تعديل881=120(354*588)تعديل881=236{\displaystyle {\begin{align}&(2*588){\bmod {8}}81=295\\&(7*588){\bmod {8}}81=592\\&(11*588){\bmod {8}}81=301\\&(21*588){\bmod {8}}81=14\\&(42*588){\bmod {8}}81=28\\&(89*588){\bmod {8}}81=353\\&(180*588){\bmod {8}}81=120\\&(354*588){\bmod {8}}81=236\النهاية{محاذاة}}}

لذلكب=(295،592،301،14،28،353،120،236){\displaystyle B=(295,592,301,14,28,353,120,236)}.

التشفير

لنفترض أن الرسالة ذات 8 بت هيم=97=011000012{\displaystyle m=97=01100001_{2}}نضرب كل بت بالرقم المقابل له فيب{\displaystyle B}ثم أضف النتائج:

 0 * 295 +1 * 592 +1 * 301 + 0 * 14 + 0 * 28 + 0 * 353 + 0 * 120 + 1 * 236 = 1129

النص المشفرج{\displaystyle c}هو 1129.

فك التشفير

لفك تشفير الرقم 1129، استخدم أولاً خوارزمية إقليدس الموسعة لإيجاد المعكوس المعياري لـر{\displaystyle r}تعديلq{\displaystyle q}:

ر′=ر-1تعديلq=588-1تعديل881=442{\displaystyle r'=r^{-1}{\bmod {q}}=588^{-1}{\bmod {8}}81=442}.

الحوسبةج′=جر′تعديلq=1129*442تعديل881=372{\displaystyle c'=cr'{\bmod {q}}=1129*442{\bmod {8}}81=372}.

استخدم الخوارزمية الجشعة لتحليل العدد 372 إلى مجموعwأنا{\displaystyle w_{i}}قيم:

ج′=372w8=354≤372ج′=372-354=18w3=11≤18ج′=18-11=7w2=7≤7ج′=7-7=0{\displaystyle {\begin{aligned}c'&=372\\&w_{8}=354\leq 372\\c'&=372-354=18\\&w_{3}=11\leq 18\\c'&=18-11=7\\&w_{2}=7\leq 7\\c'&=7-7=0\end{aligned}}}

هكذا372=354+11+7=w8+w3+w2{\displaystyle 372=354+11+7=w_{8}+w_{3}+w_{2}}وقائمة الفهارس هيX=(8،3،2){\displaystyle X=(8,3,2)}يمكن الآن حساب الرسالة على النحو التالي:

م=∑أنا=132ن-xأنا=28-8+28-3+28-2=1+32+64=97{\displaystyle m=\sum _{i=1}^{3}2^{n-x_{i}}=2^{8-8}+2^{8-3}+2^{8-2}=1+32+64=97}.

تحليل الشفرات

في عام 1984، نشر آدي شامير هجومًا على نظام التشفير ميركل-هيلمان، والذي يمكنه فك تشفير الرسائل المشفرة في وقت متعدد الحدود دون استخدام المفتاح الخاص. [ 7 ] يحلل الهجوم المفتاح العامب=(ب1،ب2،...،بن){\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}ويبحث عن زوج من الأرقامu{\displaystyle u}وم{\displaystyle m}بحيث(uبأناتعديلم){\displaystyle (ub_{i}{\bmod {m}})}هي متتالية متزايدة بشكل فائق.(u،م){\displaystyle (u,m)}قد لا يكون الزوج الذي تم العثور عليه من خلال الهجوم مساوياً لـ(ر′،q){\displaystyle (r',q)}في المفتاح الخاص، ولكن مثل هذا الزوج، يمكن استخدامه لتحويل مشكلة حقيبة الظهر الصعبة باستخدامب{\displaystyle B}تحويل المسألة إلى مسألة سهلة باستخدام متتالية متزايدة بشكل مفرط. يعتمد الهجوم كلياً على المفتاح العام؛ ولا يتطلب الوصول إلى الرسائل المشفرة.

يعمل هجوم شامير على نظام التشفير Merkle-Hellman في وقت متعدد الحدود حتى لو تم خلط الأرقام في المفتاح العام بشكل عشوائي، وهي خطوة لا يتم تضمينها عادة في وصف نظام التشفير، ولكنها قد تكون مفيدة ضد بعض الهجمات الأكثر بدائية.

في عام 2025، قدم بي خوارزمية محسّنة تستعيد تسلسلًا متزايدًا جزئيًا كمفتاح خاص مكافئ. بتطبيق خوارزمية LLL على شبكة صغيرة الأبعاد مصممة خصيصًا، تمكنوا من استعادة النص الأصلي في أقل من ثانية واحدة على حاسوب محمول عادي. [ 8 ]

مراجع

  1. ↑ شناير، بروس (1996). التشفير التطبيقي . نيويورك: جون وايلي وأولاده. ISBN 0-471-12845-7.
  2. ↑ ستينسون، دوغلاس ر. (1995). التشفير: النظرية والتطبيق . بوكا راتون: مطبعة سي آر سي. رقم ISBN 0-8493-8521-0.
  3. ↑ ويتفيلد ديفي؛ مارتن هيلمان (1976). "اتجاهات جديدة في علم التشفير". معاملات IEEE في نظرية المعلومات . 22 (6): 644. CiteSeerX 10.1.1.37.9720 . doi : 10.1109/TIT.1976.1055638 . 
  4. ↑ ميركل، رالف؛ هيلمان، مارتن (1978). "إخفاء المعلومات والتوقيعات في حقائب ظهر ذات أبواب مخفية". معاملات IEEE في نظرية المعلومات . 24 (5): 525-530 . doi : 10.1109/TIT.1978.1055927 .
  5. ↑ تشيرويتزو، ويليام (2002-03-02). "نظام تشفير ميركل-هيلمان للحقيبة" . الرياضيات 5410 - علم التشفير الحديث . تم الاسترجاع في 2019-08-18 .
  6. ↑ شامير، عدي (يوليو 1978). "مخطط توقيع سريع". مذكرة فنية لمختبر علوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا . 79 (MIT/LCS/TM–107): 15240. رمز Bibcode : 1978STIN...7915240S .
  7. ↑ شامير، عدي (1984). "خوارزمية زمنية متعددة الحدود لكسر نظام التشفير الأساسي ميركل-هيلمان". معاملات IEEE في نظرية المعلومات . 30 (5): 699-704 . doi : 10.1109/SFCS.1982.5 .
  8. ↑ بي ، جينغقو (28 مايو 2025). "هجوم بسيط وفعال على نظام تشفير حقيبة الظهر ميركل-هيلمان" . PLoS One . doi : 10.1371/journal.pone.0322726 . PMC 12118879. PMID 40435178. تاريخ الاسترجاع: 14 مارس 2026 .