خوارزمية توقيع رابين

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 57 صور
الموسوعة الحرة

في علم التشفير ، تعد خوارزمية توقيع رابين طريقة للتوقيع الرقمي نشرها مايكل أو. رابين في الأصل عام 1979. [ 1 ] [ 2 ]

كانت خوارزمية توقيع رابين من أوائل أنظمة التوقيع الرقمي المقترحة. وباستخدامها دالة "الباب الخلفي" مع تجزئة الرسالة بدلاً من الرسالة نفسها، على عكس المقترحات السابقة للتوقيعات القائمة على التجزئة لمرة واحدة أو التوقيعات القائمة على "الباب الخلفي" بدون تجزئة، [ 3 ] [ 4 ] كان تصميم رابين أول تصميم منشور يفي بما يُعرف الآن بالمعيار الحديث لأمان التوقيعات الرقمية لأكثر من رسالة واحدة، وهو عدم إمكانية التزوير الوجودي في ظل هجوم الرسالة المختارة . [ 5 ]

تشبه توقيعات رابين توقيعات RSA ذات الأسهـ=2{\displaystyle e=2}لكن هذا يؤدي إلى اختلافات نوعية تُتيح تنفيذًا أكثر كفاءة [ 5 ] وضمانًا أمنيًا يتناسب مع صعوبة تحليل الأعداد الصحيحة إلى عواملها الأولية [ 1 ] [ 2 ] [ 6 ] ، وهو ما لم يُثبت بالنسبة لـ RSA . مع ذلك، لم تشهد توقيعات رابين استخدامًا أو توحيدًا معياريًا يُذكر خارج معيار IEEE P1363 [ 7 ] مقارنةً بأنظمة توقيع RSA مثل RSASSA-PKCS1-v1_5 و RSASSA-PSS .

تعريف

يتم تحديد مخطط توقيع رابين بواسطة دالة تجزئة عشوائيةح(م،u){\displaystyle H(m,u)}رسالةم{\displaystyle m}وك{\displaystyle k}سلسلة عشوائية بتu{\displaystyle u}.

المفتاح العام
المفتاح العام هو زوج من الأعداد الصحيحة(ن،ب){\displaystyle (n,b)}مع0≤ب<ن{\displaystyle 0\leq b<n}ون{\displaystyle n}غريب.ب{\displaystyle b}يتم اختيارها بشكل تعسفي وقد تكون ثابتة.
إمضاء
توقيع على رسالةم{\displaystyle m}هو زوج(u،x){\displaystyle (u,x)}منك{\displaystyle k}سلسلة بتu{\displaystyle u}وعدد صحيحx{\displaystyle x}بحيثx(x+ب)≡ح(م،u)(تعديلن).{\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}
المفتاح الخاص
المفتاح الخاص للمفتاح العام(ن،ب){\displaystyle (n,b)}هو التحليل السري للعوامل الأولية الفرديةص⋅q{\displaystyle p\cdot q}لن{\displaystyle n}، يتم اختيارها بشكل عشوائي منتظم من مساحة كبيرة من الأعداد الأولية.
توقيع رسالة
لعمل توقيع على رسالةم{\displaystyle m}باستخدام المفتاح الخاص، يبدأ المُوقِّع باختيارك{\displaystyle k}سلسلة بتu{\displaystyle u}بشكل عشوائي منتظم، ويحسبج:=ح(م،u){\displaystyle c:=H(m,u)}. يتركد=(ب/2)تعديلن{\displaystyle d=(b/2){\bmod {n}}}. لوج+د2{\displaystyle c+d^{2}}هو باقي تربيعي moduloن{\displaystyle n}، يبدأ المُوقِّع من جديد باستخدام قيمة عشوائية مستقلةu{\displaystyle u}[ 1 ] : ص 10 وإلا ، يقوم المُوقِّع بالحسابxص:=(-د±ج+د2)تعديلص،xq:=(-د±ج+د2)تعديلq،{\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {p}},\\x_{q}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {ف}}،\نهاية {محاذاة}}}باستخدام خوارزمية قياسية لحساب الجذور التربيعية بتردد عدد أولي - اختيارص≡q≡3(تعديل4){\displaystyle p\equiv q\equiv 3{\pmod {4}}}يجعل ذلك الأمر أسهل. الجذور التربيعية ليست فريدة، وتختار المتغيرات المختلفة لنظام التوقيع جذرًا تربيعيًا مختلفًا؛ [ 5 ] على أي حال، يجب على المُوقِّع التأكد من عدم الكشف عن جذرين مختلفين لنفس التجزئة.ج{\displaystyle c}. xص{\displaystyle x_{p}}وxq{\displaystyle x_{q}}تحقق المعادلاتxص(xص+ب)≡ح(م،u)(تعديلص)،xq(xq+ب)≡ح(م،u)(تعديلq).{\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}} ثم يستخدم المُوقِّع نظرية الباقي الصينية لحل النظامx≡xص(تعديلص)،x≡xq(تعديلq)،{\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}لx{\displaystyle x}، لهذا السببx{\displaystyle x}يرضيx(x+ب)≡ح(م،u)(تعديلن){\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}حسب الاقتضاء. يكشف الموقع(u،x){\displaystyle (u,x)}كتوقيع علىم{\displaystyle m}.
عدد التجارب لـu{\displaystyle u}قبلx(x+ب)≡ح(م،u)(تعديلن){\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}يمكن حلها لـx{\displaystyle x}يتوزع التوزيع الهندسي بمتوسط ​​يقارب 4 تجارب، لأن حوالي ربع جميع الأعداد الصحيحة هي بواقي تربيعية moduloن{\displaystyle n}.

حماية

الحماية ضد أي خصم يتم تعريفه بشكل عام من حيث دالة التجزئةح{\displaystyle H}(أي أن الأمان في نموذج أوراكل العشوائي ) ينبع من صعوبة التحليل إلى عواملن{\displaystyle n}أي خصم من هذا القبيل يتمتع باحتمالية عالية للنجاح في التزوير، يمكنه، باحتمالية عالية مماثلة تقريبًا، إيجاد جذرين تربيعيين مختلفينx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}عدد صحيح عشوائيج{\displaystyle c}moduloن{\displaystyle n}. لوx1±x2≢0(تعديلن){\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}ثمالقاسم المشترك الأكبر(x1±x2،ن){\displaystyle \gcd(x_{1}\pm x_{2},n)}وهو عامل غير تافه منن{\displaystyle n}، منذx12≡x22≡ج(تعديلن){\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}لذان|x12-x22=(x1+x2)(x1-x2){\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}لكنن∤x1±x2{\displaystyle n\nmid x_{1}\pm x_{2}}[ 2 ] يتطلب إضفاء الطابع الرسمي على الأمن بمصطلحات حديثة ملء بعض التفاصيل الإضافية، مثل المجال المشترك لـح{\displaystyle H}إذا حددنا حجمًا قياسيًاك{\displaystyle K}بالنسبة للعوامل الأولية،2ك-1<ص<q<2ك{\displaystyle 2^{K-1}<p<q<2^{K}}ثم يمكننا تحديدح:{0،1}*×{0،1}ك→{0،1}ك{\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}[ 6 ]​

تم إدخال عشوائية دالة التجزئة لتمكين المُوقِّع من إيجاد باقي تربيعي، ولكن التجزئة العشوائية للتوقيعات أصبحت لاحقًا ذات أهمية في حد ذاتها لنظريات أمنية أكثر صرامة [ 2 ] ومقاومة لهجمات التصادم على دوال التجزئة الثابتة. [ 8 ] [ 9 ] [ 10 ]

المتغيرات

إزالة ب

الكميةب{\displaystyle b}لا يضيف استخدام المفتاح العام أي أمان، حيث أن أي خوارزمية لحل التطابقاتx(x+ب)≡ج(تعديلن){\displaystyle x(x+b)\equiv c{\pmod {n}}}لx{\displaystyle x}منحب{\displaystyle b}وج{\displaystyle c}يمكن استخدامها بسهولة كإجراء فرعي في خوارزمية لحساب الجذور التربيعية moduloن{\displaystyle n}والعكس صحيح، حتى تتمكن التطبيقات من الضبط بأمانب=0{\displaystyle b=0}من أجل التبسيط؛ب{\displaystyle b}تم استبعادها تمامًا من العلاجات بعد الاقتراح الأولي. [ 11 ] [ 2 ] [ 7 ] [ 5 ] بعد إزالةب{\displaystyle b}المعادلات الخاصة بـxص{\displaystyle x_{p}}وxq{\displaystyle x_{q}}تصبح في خوارزمية التوقيع ما يلي:xص:=±جتعديلص،xq:=±جتعديلq.{\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}

رابين ويليامز

تم تعديل مخطط توقيع رابين لاحقًا بواسطة ويليامز في عام 1980 [ 11 ] لاختيارص≡3(تعديل8){\displaystyle p\equiv 3{\pmod {8}}}وq≡7(تعديل8){\displaystyle q\equiv 7{\pmod {8}}}، واستبدل الجذر التربيعيx{\displaystyle x}بواسطة جذر تربيعي معدل(هـ،و،x){\displaystyle (e,f,x)}، معهـ=±1{\displaystyle e=\pm 1}وو∈{1،2}{\displaystyle f\in \{1,2\}}بحيث يفي التوقيع بدلاً من ذلك بالغرض. هـوx2≡ح(م،u)(تعديلن)،{\displaystyle efx^{2}\equiv H(m,u){\pmod {n}},} مما يسمح للموقّع بإنشاء توقيع في محاولة واحدة دون المساس بالأمان. يُعرف هذا النوع باسم رابين-ويليامز . [ 5 ] [ 7 ]

آحرون

تتيح المتغيرات الأخرى المفاضلة بين حجم التوقيع وسرعة التحقق، واستعادة الرسائل جزئياً، وضغط التوقيع (حتى نصف الحجم)، وضغط المفتاح العام (حتى ثلث الحجم)، دون المساس بالأمان. [ 5 ]

نُشرت صيغٌ بديلةٌ لا تستخدم دالة التجزئة في الكتب الدراسية، [ 12 ] [ 13 ] حيث يُنسب الفضل في الأس 2 إلى رابين، ولكن ليس في استخدام دالة التجزئة. ويمكن كسر هذه الصيغ بسهولة ، على سبيل المثال، التوقيع.x=2{\displaystyle x=2}يمكن لأي شخص تزويرها كتوقيع صالح على الرسالةم=4{\displaystyle m=4}إذا كانت معادلة التحقق من التوقيع هيx2≡م(تعديلن){\displaystyle x^{2}\equiv m{\pmod {n}}}بدلاً منx2≡ح(م،u)(تعديلن){\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}.

في الورقة الأصلية، [ 1 ] دالة التجزئةح(م،u){\displaystyle H(m,u)}كُتبت باستخدام التدوينج(ميو){\displaystyle C(MU)}، مع استخدام C للضغط ، واستخدام التجاور للدلالة على تسلسلم{\displaystyle M}ويو{\displaystyle U}كسلاسل بت:

بحسب العرف، عند الرغبة في توقيع رسالة معينة،م{\displaystyle M}[الموقع]P{\displaystyle P}يضيف لاحقة إلى الكلمةيو{\displaystyle U}بطول متفق عليهك{\displaystyle k}اختياريو{\displaystyle U}يتم توليدها عشوائيًا في كل مرة يتم فيها توقيع رسالة. يقوم المُوقِّع الآن بضغطها.م1=ميو{\displaystyle M_{1}=MU}عن طريق دالة التجزئة إلى كلمةج(م1)=ج{\displaystyle C(M_{1})=c}، بحيث يكون كرقم ثنائيج≤ن{\displaystyle c\leq n}...

وقد أدى هذا الترميز إلى بعض الارتباك بين بعض المؤلفين اللاحقين الذين تجاهلواج{\displaystyle C}جزء وسوء فهمميو{\displaystyle MU}بمعنى الضرب، مما يؤدي إلى سوء فهم نظام التوقيع المعيب بشكل تافه. [ 14 ]

مراجع

  1. 1 2 3 4 رابين، مايكل أو. (يناير 1979). التوقيعات الرقمية ووظائف المفتاح العام معقدة مثل التحليل إلى عوامل (ملف PDF) (تقرير فني). كامبريدج، ماساتشوستس، الولايات المتحدة: مختبر علوم الحاسوب في معهد ماساتشوستس للتكنولوجيا. TR-212.
  2. 1 2 3 4 5 بيلاري، ميهير ؛ روغاواي، فيليب (مايو 1996). ماورر، أولي (محرر). الأمان الدقيق للتوقيعات الرقمية - كيفية التوقيع باستخدام RSA ورابين . التطورات في علم التشفير - EUROCRYPT '96 . سلسلة محاضرات في علوم الحاسوب. المجلد 1070. سرقسطة، إسبانيا: سبرينغر. الصفحات 399-416 . doi : 10.1007/3-540-68339-9_34 . ISBN   978-3-540-61186-8.
  3. ↑ ديفي، ويتفيلد ؛ هيلمان، مارتن (نوفمبر 1976). "اتجاهات جديدة في علم التشفير" (ملف PDF) . معاملات IEEE في نظرية المعلومات . 22 (6). IEEE : 644-654 . Bibcode : 1976ITIT...22..644D . doi : 10.1109/TIT.1976.1055638 .
  4. ↑ ريفست، آر إل ؛ شامير، أ. شامير ؛ أدلمان، إل. (فبراير 1978). غراهام، إس إل؛ ريفست، آر إل ؛ ماناشر، جي كي (محررون). "طريقة للحصول على التوقيعات الرقمية وأنظمة التشفير بالمفتاح العام" . اتصالات رابطة مكائن ​​الحوسبة . 21 (2). رابطة مكائن ​​الحوسبة : 120-126 . doi : 10.1145/359340.359342 .
  5. 1 2 3 4 5 6 بيرنشتاين، دانيال ج. (31 يناير 2008). توقيعات RSA وتوقيعات رابين-ويليامز: أحدث التقنيات (تقرير).(للحصول على معلومات إضافية، يرجى زيارة الرابط التالي: https://cr.yp.to/sigs.html )
  6. 1 2 بيرنشتاين، دانيال ج. (أبريل 2008). سمارت، نايجل (محرر). إثبات أمان محكم لتوقيعات رابين-ويليامز . التطورات في علم التشفير - يورو كريبت 2008. سلسلة محاضرات في علوم الحاسوب. المجلد 4965. إسطنبول، تركيا: سبرينغر. الصفحات 70-87 . doi : 10.1007/978-3-540-78967-3_5 . ISBN   978-3-540-78966-6.
  7. 1 2 3 المواصفات القياسية لمعهد مهندسي الكهرباء والإلكترونيات (IEEE) لتشفير المفتاح العام . IEEE Std 1363-2000. معهد مهندسي الكهرباء والإلكترونيات. 25 أغسطس 2000. doi : 10.1109/IEEESTD.2000.92292 . ISBN 0-7381-1956-3.
  8. ↑ بيلار، ميهير ؛ روغاواي، فيليب (أغسطس 1998). مُقدَّم إلى IEEE P1393—PSS: طريقة ترميز آمنة قابلة للإثبات للتوقيعات الرقمية (PDF) (تقرير). مؤرشف من الأصل (PDF) بتاريخ 13 يوليو 2004.
  9. ↑ هاليفي، شاي ؛ كراوتشيك، هوغو (أغسطس 2006). دورك، سينثيا (محررة). تعزيز التوقيعات الرقمية عبر التجزئة العشوائية (ملف PDF) . التطورات في علم التشفير - CRYPTO 2006. سلسلة محاضرات في علوم الحاسوب. المجلد 4117. سانتا باربرا، كاليفورنيا، الولايات المتحدة: سبرينغر. الصفحات 41-59 . doi : 10.1007/11818175_3 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 19 مارس 2022.  
  10. ↑ دانغ، كوين (فبراير 2009). التجزئة العشوائية للتوقيعات الرقمية (تقرير). منشور خاص من المعهد الوطني للمعايير والتكنولوجيا. المجلد 800-106 . وزارة التجارة الأمريكية، المعهد الوطني للمعايير والتكنولوجيا . doi : 10.6028/NIST.SP.800-106 . 
  11. 1 2 ويليامز، هيو سي. "تعديل لإجراء تشفير المفتاح العام RSA" . معاملات IEEE في نظرية المعلومات . 26 (6): 726-729 . doi : 10.1109/TIT.1980.1056264 . ISSN 0018-9448 . 
  12. ↑ مينيز، ألفريد ج .؛ فان أورشوت، بول س .؛ فانستون، سكوت أ. (أكتوبر 1996). "§11.3.4: مخطط رابين للتوقيع بالمفتاح العام" (ملف PDF) . دليل التشفير التطبيقي . مطبعة CRC. الصفحات 438-442 . ISBN  0-8493-8523-7.
  13. ↑ غالبريث، ستيفن د. (2012). "§24.2: نظام رابين التشفيري في الكتب الدراسية". رياضيات التشفير بالمفتاح العام . مطبعة جامعة كامبريدج. ص 491-494 . ISBN  978-1-10701392-6.
  14. ^ إيليا ميشيل. شيباني ، ديفيد (2011). على توقيع رابين (PDF) . ورشة عمل حول الأمن الحاسوبي. مركز أبحاث الرياضيات، برشلونة، إسبانيا.