خوارزمية التوقيع الرقمي للمنحنى الإهليلجي
في علم التشفير ، تقدم خوارزمية التوقيع الرقمي للمنحنى الإهليلجي ( ECDSA ) نوعًا مختلفًا من خوارزمية التوقيع الرقمي (DSA) التي تستخدم تشفير المنحنى الإهليلجي .
أحجام المفاتيح والتوقيعات
كما هو الحال مع تشفير المنحنيات الإهليلجية بشكل عام، فإن حجم بتات المفتاح الخاص المطلوب لخوارزمية ECDSA يبلغ ضعف حجم مستوى الأمان تقريبًا ، بالبتات. [ 1 ] على سبيل المثال، عند مستوى أمان يبلغ 80 بتًا - أي أن المهاجم يحتاج إلى حد أقصى يبلغ حواليتتطلب عمليات البحث عن المفتاح الخاص - يبلغ حجم المفتاح الخاص لخوارزمية ECDSA حوالي 160 بت. من ناحية أخرى، يكون حجم التوقيع متطابقًا لكل من خوارزميتي DSA وECDSA: تقريبًاأجزاء، حيثالأس في الصيغةأي ما يعادل حوالي 320 بت لمستوى أمان يبلغ 80 بت، وهو ما يعادلالعمليات.
خوارزمية توليد التوقيع
لنفترض أن أليس تريد إرسال رسالة موقعة إلى بوب . في البداية، يجب أن يتفقا على معلمات المنحنى.بالإضافة إلى مجال ومعادلة المنحنى، نحتاج إلى، نقطة أساسية من رتبة أولية على المنحنى؛هو الترتيب الجمعي للنقطة.
| المعلمة | |
|---|---|
| منحنى | مجال المنحنى الإهليلجي والمعادلة المستخدمة |
| جي | نقطة أساس المنحنى الإهليلجي، وهي نقطة على المنحنى تولد مجموعة فرعية من رتبة أولية كبيرة n |
| ن | الترتيب الصحيح لـ G يعني أن، أينهو عنصر الهوية. |
| المفتاح الخاص (يتم اختياره عشوائياً) | |
| المفتاح العام(محسوبة بواسطة منحنى إهليلجي) | |
| م | الرسالة المراد إرسالها |
الطلبنقطة الأساسيجب أن يكون عددًا أوليًا . في الواقع، نفترض أن كل عنصر غير صفري في الحلقةقابلة للعكس، بحيثيجب أن يكون حقلاً . وهذا يعني أنيجب أن يكون عدداً أولياً (انظر متطابقة بيزو ).
تقوم أليس بإنشاء زوج من المفاتيح، يتكون من مفتاح خاص وعدد صحيح، تم اختيارها عشوائياً في الفترةونقطة منحنى المفتاح العامنحن نستخدمللدلالة على ضرب نقطة المنحنى الإهليلجي في عدد قياسي .
لكي توقع أليس على الرسالة، وهي تتبع هذه الخطوات:
- احسب(هنا HASH هي دالة تجزئة تشفيرية ، مثل SHA-2 ، مع تحويل الناتج إلى عدد صحيح.)
- يترككنأقصى الأجزاء اليسرى من، أينيمثل طول البت لترتيب المجموعة. (لاحظ أنيمكن أن يكون أكبر منولكن ليس لفترة أطول . [ 2 ] )
- اختر عددًا صحيحًا عشوائيًا آمنًا تشفيرًامن.
- احسب نقطة المنحنى.
- احسب. لو، ارجع إلى الخطوة 3.
- احسب. لو، ارجع إلى الخطوة 3.
- التوقيع هو الزوج. (و(يُعتبر أيضاً توقيعاً صحيحاً.)
كما تشير الملاحظات القياسية، فإن ذلك ليس مطلوبًا فقط من أجليجب أن يبقى الأمر سراً، ولكن من المهم أيضاً اختيار خيارات مختلفةبالنسبة للتوقيعات المختلفة. وإلا، يمكن حل المعادلة في الخطوة 6 لـالمفتاح الخاص: معطى توقيعانوباستخدام نفس المجهوللرسائل معروفة مختلفةويمكن للمهاجم أن يحسبوو منذ ذلك الحين(جميع العمليات في هذه الفقرة تتم باستخدام باقي القسمة)) يمكن للمهاجم أن يجد. منذوبذلك يستطيع المهاجم الآن حساب المفتاح الخاص.
استُخدم هذا الفشل في التنفيذ، على سبيل المثال، لاستخراج مفتاح التوقيع المستخدم لجهاز ألعاب بلاي ستيشن 3. [ 3 ]
هناك طريقة أخرى قد تؤدي بها توقيعات ECDSA إلى تسريب المفاتيح الخاصة، وهي عندمايتم توليدها بواسطة مولد أرقام عشوائية معيب . تسبب هذا الخلل في توليد الأرقام العشوائية في فقدان مستخدمي محفظة بيتكوين على نظام أندرويد لأموالهم في أغسطس 2013. [ 4 ]
لضمان ذلكبما أن التوقيع فريد لكل رسالة، يمكن تجاوز توليد الأرقام العشوائية تمامًا وإنشاء توقيعات حتمية عن طريق اشتقاقها.من كل من الرسالة والمفتاح الخاص. [ 5 ]
خوارزمية التحقق من التوقيع
لكي يقوم بوب بالتحقق من صحة توقيع أليسفي رسالةيجب أن يكون لديه نسخة من نقطة منحنى المفتاح العام الخاصة بهايمكن لبوب أن يؤكد ذلك.تُعتبر نقطة المنحنى صالحة كما يلي:
- تأكد من ذلكلا يساوي العنصر المحايد O ، وإحداثياته صالحة بخلاف ذلك.
- تأكد من ذلكيقع على المنحنى.
- تأكد من ذلك.
بعد ذلك، يتبع بوب هذه الخطوات:
- تحقق من أن r و s عددان صحيحان فيوإلا، فإن التوقيع غير صالح.
- احسب، حيث أن HASH هي نفس الوظيفة المستخدمة في إنشاء التوقيع.
- يترككنأقصى أجزاء e اليسرى .
- احسبو.
- احسب نقطة المنحنى. لوإذن، التوقيع غير صالح.
- يكون التوقيع صحيحاً إذاوإلا فهي غير صالحة.
لاحظ أن التنفيذ الفعال سيحسب المعكوسمرة واحدة فقط. كذلك، باستخدام خدعة شامير، يكون مجموع عمليتي ضرب عددين قياسيينيمكن حسابها بشكل أسرع من عمليتي ضرب عددين قياسيين يتم إجراؤهما بشكل مستقل. [ 6 ]
صحة الخوارزمية
ليس من الواضح للوهلة الأولى سبب عمل عملية التحقق بشكل صحيح. لفهم السبب، لنرمز بـ C إلى نقطة المنحنى المحسوبة في الخطوة 5 من عملية التحقق.
من تعريف المفتاح العام على النحو التالي،
لأن عملية الضرب القياسي في المنحنى الإهليلجي تتوزع على عملية الجمع،
توسيع تعريفومن خطوة التحقق الرابعة،
جمع المصطلحات الشائعة،
توسيع تعريف s من خطوة التوقيع 6،
بما أن معكوس المعكوس هو العنصر الأصلي، وحاصل ضرب معكوس العنصر في العنصر نفسه هو العنصر المحايد، فإننا نتبقى مع
انطلاقاً من تعريف r ، فإن هذه هي خطوة التحقق السادسة.
هذا يوضح فقط أن الرسالة الموقعة بشكل صحيح سيتم التحقق منها بشكل صحيح؛ هناك خصائص أخرى مطلوبة لخوارزمية توقيع آمنة، مثل فشل الرسائل الموقعة بشكل غير صحيح في التحقق منها بشكل صحيح ومقاومة الهجمات التحليلية المشفرة.
استعادة المفتاح العام
بافتراض وجود رسالة m وتوقيع أليسبناءً على تلك الرسالة، يمكن لبوب (ربما) استعادة المفتاح العام لأليس: [ 7 ]
- تحقق من أن r و s عددان صحيحان فيوإلا، فإن التوقيع غير صالح.
- احسب نقطة المنحنىأينهو أحد،،إلخ. (شريطة(ليست كبيرة جدًا بالنسبة لمجال المنحنى) وهي قيمة تحقق معادلة المنحنى. لاحظ أنه قد توجد عدة نقاط على المنحنى تحقق هذه الشروط، وكل قيمة مختلفة لـ R تؤدي إلى مفتاح مستعاد مميز.
- احسب، حيث أن HASH هي نفس الوظيفة المستخدمة في إنشاء التوقيع.
- ليكن z هوأقصى أجزاء e اليسرى .
- احسبو.
- احسب نقطة المنحنى.
- يكون التوقيع صحيحاً إذا، يطابق المفتاح العام لأليس.
- التوقيع غير صالح إذا تم تجربة جميع نقاط R الممكنة ولم يتطابق أي منها مع المفتاح العام لأليس.
لاحظ أن التوقيع غير الصالح، أو التوقيع من رسالة مختلفة، سيؤدي إلى استعادة مفتاح عام خاطئ. لا يمكن استخدام خوارزمية الاستعادة للتحقق من صحة التوقيع إلا إذا كان المفتاح العام للموقّع (أو تجزئته) معروفًا مسبقًا.
صحة خوارزمية الاسترداد
ابدأ بتعريفمن الخطوة السادسة من عملية التعافي،
من التعريفبدءًا من خطوة التوقيع الرابعة،
لأن عملية الضرب القياسي في المنحنى الإهليلجي تتوزع على عملية الجمع،
توسيع تعريفومن الخطوة الخامسة للتعافي،
توسيع تعريف s من خطوة التوقيع 6،
بما أن حاصل ضرب معكوس عنصر ما في ذلك العنصر هو العنصر المحايد، فإننا نتبقى مع
يلغي الحدان الأول والثاني بعضهما بعضاً،
من تعريفهذا هو المفتاح العام لأليس.
يُظهر هذا أن الرسالة الموقعة بشكل صحيح ستستعيد المفتاح العام الصحيح، بشرط مشاركة معلومات إضافية لحساب نقطة المنحنى بشكل فريد.من قيمة التوقيع r .
حماية
في ديسمبر 2010، أعلنت مجموعة تُطلق على نفسها اسم fail0verflow استعادة المفتاح الخاص لخوارزمية ECDSA الذي استخدمته سوني لتوقيع برامج جهاز ألعاب بلاي ستيشن 3. ومع ذلك، لم ينجح هذا الهجوم إلا لأن سوني لم تُطبّق الخوارزمية بشكل صحيح، لأنكانت ثابتة بدلاً من أن تكون عشوائية. وكما هو موضح في قسم خوارزمية توليد التوقيع أعلاه، فإن هذا يجعلقابلة للحل، مما يجعل الخوارزمية بأكملها عديمة الفائدة. [ 8 ]
في 29 مارس 2011، نشر باحثان ورقة بحثية في مؤتمر IACR [ 9 ] تُثبت إمكانية استرجاع مفتاح TLS الخاص بخادم يستخدم OpenSSL للمصادقة باستخدام خوارزمية Elliptic Curves DSA على حقل ثنائي، وذلك عبر هجوم زمني . [ 10 ] وقد تم إصلاح هذه الثغرة الأمنية في OpenSSL 1.0.0f. [ 11 ]
في أغسطس 2013، تم الكشف عن أن الأخطاء في بعض تطبيقات فئة Java SecureRandom كانت تتسبب أحيانًا في حدوث تصادمات فيالقيمة. وقد سمح هذا للمخترقين باستعادة المفاتيح الخاصة، مما منحهم نفس التحكم في معاملات البيتكوين الذي كان يتمتع به أصحاب المفاتيح الشرعية، باستخدام نفس الثغرة التي استُخدمت للكشف عن مفتاح توقيع PS3 في بعض تطبيقات أندرويد ، التي تستخدم جافا وتعتمد على ECDSA لمصادقة المعاملات. [ 12 ]
يمكن منع هذه المشكلة عن طريق التوليد الحتمي لـ k، كما هو موضح في RFC 6979.
مخاوف
بعض المخاوف التي تم التعبير عنها بشأن قانون استئصال الندبة الإكلينيكية:
- مخاوف سياسية : تثار الشكوك حول مصداقية المنحنيات التي ينتجها المعهد الوطني للمعايير والتكنولوجيا (NIST) بعد الكشف عن قيام وكالة الأمن القومي الأمريكية (NSA) بإدخال أبواب خلفية عمدًا في البرامج ومكونات الأجهزة والمعايير المنشورة؛ وقد أعرب خبراء تشفير معروفون [ 13 ] [ 14 ] [ 15 ] عن شكوكهم حول كيفية تصميم منحنيات NIST، كما ثبت سابقًا وجود تلوث متعمد [ 16 ] [ 17 ] . (انظر أيضًا مقدمة مكتبة libssh curve25519 [ 18 ] ) . ومع ذلك، لا يزال الدليل على أن منحنيات NIST المذكورة تستغل ثغرة أمنية نادرة غير متوفر.
- المخاوف التقنية : صعوبة تطبيق المعيار بشكل صحيح، وبطء تنفيذه، وعيوب التصميم التي تقلل من الأمان في التطبيقات غير الدفاعية بشكل كافٍ. [ 19 ]
التطبيقات
فيما يلي قائمة بمكتبات التشفير التي توفر الدعم لخوارزمية ECDSA:
انظر أيضاً
مراجع
- ↑ جونسون، دون؛ مينيزيس، ألفريد (1999). "خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA)". أبحاث سيرتيكوم. كندا . CiteSeerX 10.1.1.38.8014 .
- ↑ "NIST FIPS 186-4، يوليو 2013، الصفحتان 19 و26" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 27 ديسمبر 2016. تم الاطلاع عليه بتاريخ 17 مارس 2014 .
- ↑ اختراق أجهزة الألعاب 2010 - فشل ذريع لجهاز بلاي ستيشن 3 ، مؤرشف في 15 ديسمبر 2014، في أرشيف الإنترنت ، الصفحات 123-128
- ↑ "ثغرة أمنية في نظام أندرويد" . مؤرشف من الأصل في 7 أبريل 2019. تم الاطلاع عليه في 24 فبراير 2015 .
- ↑ بورنين، ت. (2013). RFC 6979 - الاستخدام الحتمي لخوارزمية التوقيع الرقمي (DSA) وخوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA) (تقرير فني). doi : 10.17487/RFC6979 . تاريخ الاسترجاع: 24 فبراير 2015 .
- ↑ "نظام الأرقام ذو الأساس المزدوج في تشفير المنحنيات الإهليلجية" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 26 يوليو 2011. تم الاطلاع عليه بتاريخ 22 أبريل 2014 .
- ↑ دانيال آر إل براون، SECG SEC 1: تشفير المنحنيات الإهليلجية (الإصدار 2.0) https://www.secg.org/sec1-v2.pdf
- ↑ بيندل، مايك (29 ديسمبر 2010). "مخترقون يصفون أمن جهاز بلاي ستيشن 3 بالفشل الذريع، ويحصلون على وصول غير مقيد" . Exophase.com. مؤرشف من الأصل في 7 أبريل 2019. تم الاطلاع عليه في 5 يناير 2011 .
- ↑ "أرشيف الطباعة الإلكترونية لعلم التشفير: التقرير 2011/232" . مؤرشف من الأصل في 8 ديسمبر 2018. تم الاطلاع عليه في 24 فبراير 2015 .
- ↑ «ملاحظة حول الثغرة الأمنية VU#536044 - تسريب OpenSSL للمفتاح الخاص ECDSA من خلال هجوم توقيت عن بُعد» . www.kb.cert.org . مؤرشف من الأصل بتاريخ 7 أبريل 2019. تم الاطلاع عليه بتاريخ 24 مايو 2011 .
- ↑ "الثغرات الأمنية" . مشروع OpenSSL . تم الاطلاع عليه في 13 يونيو 2026 .
- ↑ "خلل في نظام أندرويد يُلحق الضرر بمحافظ البيتكوين" . ذا ريجستر. ١٢ أغسطس ٢٠١٣. مؤرشف من الأصل في ١٥ أغسطس ٢٠١٣. تم الاطلاع عليه في ٢٧ أغسطس ٢٠١٧ .
- ↑ شناير، بروس (5 سبتمبر 2013). "وكالة الأمن القومي تخترق معظم أنظمة التشفير على الإنترنت" . شناير حول الأمن . مؤرشف من الأصل في 15 ديسمبر 2017. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ "المنحنيات الآمنة: اختيار المنحنيات الآمنة لتشفير المنحنيات الإهليلجية" . 25 أكتوبر 2013. مؤرشف من الأصل في 7 أبريل 2019. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ بيرنشتاين، دانيال جيه؛ لانج، تانيا (31 مايو 2013). "مخاطر أمنية لمنحنيات المعهد الوطني للمعايير والتكنولوجيا" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 28 مايو 2019. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ شناير، بروس (15 نوفمبر 2007). "القصة الغريبة لـ Dual_EC_DRBG" . شناير حول الأمن . مؤرشف من الأصل في 23 أبريل 2019. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ غرينماير، لاري (18 سبتمبر 2013). "جهود وكالة الأمن القومي للتهرب من تقنية التشفير أضرت بمعيار التشفير الأمريكي" . مجلة ساينتفك أمريكان. مؤرشف من الأصل في 24 ديسمبر 2017. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ "curve25519-sha256@libssh.org.txt\doc - projects/libssh.git" . مستودع libssh المشترك . مؤرشف من الأصل في 23 مارس 2019. تم الاطلاع عليه في 11 يناير 2018 .
- ↑ بيرنشتاين، دانيال ج. (23 مارس 2014). "كيفية تصميم نظام توقيع باستخدام منحنى إهليلجي" . مدونة cr.yp.to. مؤرشف من الأصل في 23 مارس 2014. تم الاطلاع عليه في 11 يناير 2018 .
للمزيد من القراءة
- لجنة المعايير المعتمدة X9 ، ASC X9، تصدر معيارًا جديدًا لتشفير المفتاح العام/ECDSA ، 6 أكتوبر 2020. المصدر
- لجنة المعايير المعتمدة X9 ، المعيار الوطني الأمريكي X9.62-2005، التشفير بالمفتاح العام لصناعة الخدمات المالية، خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA) ، 16 نوفمبر 2005.
- Certicom Research، معايير التشفير الفعال، SEC 1: تشفير المنحنى الإهليلجي ، الإصدار 2.0، 21 مايو 2009.
- لوبيز، ج. ودهب، ر. نظرة عامة على تشفير المنحنى الإهليلجي ، التقرير الفني IC-00-10، جامعة كامبيناس الحكومية، 2000.
- دانيال ج. بيرنشتاين ، خوارزمية بيبنجر للأس ، 2002.
- دانيال آر إل براون، المجموعات العامة، ومقاومة التصادم، وECDSA ، التصاميم، والرموز، والتشفير، 35 ، 119-152، 2005. نسخة إلكترونية مطبوعة
- إيان إف. بليك، جاديل سيروسي، ونيجل سمارت ، محررون، التقدم في تشفير المنحنيات الإهليلجية ، سلسلة محاضرات الجمعية الرياضية بلندن 317، مطبعة جامعة كامبريدج، 2005.
- هانكرسون، د.؛ فانستون، س .؛ مينيزيس، أ. (2004). دليل تشفير المنحنيات الإهليلجية . سبرينغر للحوسبة الاحترافية. نيويورك: سبرينغر . doi : 10.1007/b97644 . ISBN 0-387-95273-X. S2CID 720546 .
روابط خارجية
- معيار التوقيع الرقمي؛ يتضمن معلومات حول ECDSA
- خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA)؛ دليل شامل حول خوارزمية ECDSA . رابط Wayback
- التشفير بالمفتاح العام
- التشفير باستخدام المنحنى الإهليلجي
- أنظمة التوقيع الرقمي
- معيار التوقيع الرقمي
