التشفير القائم على التجزئة

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

التشفير القائم على التجزئة هو المصطلح العام الذي يشير إلى إنشاءات أساسية للتشفير تعتمد على أمان دوال التجزئة . وهو ذو أهمية كنوع من أنواع التشفير ما بعد الكمومي .

حتى الآن، تُستخدم التشفير القائم على التجزئة لبناء أنظمة التوقيع الرقمي ، مثل نظام توقيع ميركل ، وإثباتات المعرفة الصفرية، وإثباتات سلامة الحساب، مثل نظام إثبات zk-STARK [ 1 ] ، وإثباتات النطاق على بيانات الاعتماد الصادرة عبر بروتوكول HashWires [ 2 ] . تجمع أنظمة التوقيع القائمة على التجزئة بين نظام توقيع لمرة واحدة، مثل توقيع لامبورت ، وبنية شجرة ميركل . ولأن مفتاح نظام التوقيع لمرة واحدة لا يمكنه توقيع سوى رسالة واحدة بشكل آمن، فمن العملي دمج العديد من هذه المفاتيح ضمن بنية واحدة أكبر. تُستخدم بنية شجرة ميركل لهذا الغرض. في هذه البنية الهرمية للبيانات، تُستخدم دالة التجزئة والتسلسل بشكل متكرر لحساب عقد الشجرة.

من الاعتبارات المتعلقة بأنظمة التوقيع القائمة على التجزئة أنها لا تستطيع توقيع سوى عدد محدود من الرسائل بشكل آمن، وذلك بسبب استخدامها لأنظمة التوقيع لمرة واحدة. وقد حدد المعهد الوطني الأمريكي للمعايير والتكنولوجيا (NIST) أن الخوارزميات المشاركة في مسابقة التشفير ما بعد الكمومي تدعم ما لا يقل عن 2 ^64 توقيعًا بشكل آمن. [ 3 ]

أقرّ المعهد الوطني للمعايير والتكنولوجيا (NIST) في عام 2020 معيارًا للتشفير القائم على التجزئة مع الاحتفاظ بالحالة، والمستند إلى مخطط توقيع ميركل الموسّع (XMSS) وتوقيعات لايتون-ميكالي (LMS)، [ 4 ] والتي تُطبّق في ظروف مختلفة، ولكنه أشار إلى أن شرط الاحتفاظ بالحالة عند استخدامها يجعل تنفيذها بطريقة تمنع إساءة استخدامها أكثر صعوبة. [ 5 ] [ 6 ] [ 7 ]

في عام 2022، أعلن المعهد الوطني للمعايير والتكنولوجيا (NIST) عن خوارزمية SPHINCS+ كواحدة من ثلاث خوارزميات سيتم توحيدها للتوقيعات الرقمية. [ 8 ] وفي عام 2024، أعلن المعهد عن معيار التوقيع الرقمي القائم على التجزئة عديم الحالة (SLH-DSA) [ 9 ] والمستند إلى خوارزمية SPHINCS+.

تاريخ

ابتكر ليزلي لامبورت التوقيعات القائمة على التجزئة عام 1979. وطُرحت أنظمة التوقيع القائمة على التجزئة XMSS (مخطط ميركل الموسع) [ 10 ] وSPHINCS [ 11 ] [ 12 ] عامي 2010 و2015 على التوالي. طُوّر نظام XMSS بواسطة فريق من الباحثين تحت إشراف يوهانس بوخمان ، وهو يستند إلى كلٍ من مخطط ميركل الأساسي ومخطط ميركل المعمم للتوقيع (GMSS) لعام 2007. [ 13 ] وتم وصف نسخة متعددة الأشجار من XMSS، تُسمى XMSS MT ، عام 2013. [ 14 ]

مخططات التوقيع لمرة واحدة

تعتمد أنظمة التوقيع القائمة على التجزئة على أنظمة التوقيع لمرة واحدة كعنصر أساسي. لا يمكن استخدام مفتاح التوقيع لمرة واحدة إلا لتوقيع رسالة واحدة بشكل آمن. في الواقع، تكشف التوقيعات جزءًا من مفتاح التوقيع. يعتمد أمان أنظمة التوقيع لمرة واحدة (القائمة على التجزئة) بشكل حصري على أمان دالة التجزئة الأساسية.

تشمل أنظمة التوقيع لمرة واحدة الشائعة الاستخدام نظام لامبورت-ديفي ، ونظام وينترنيتز [ 15 ] وتحسيناته، مثل نظام W-OTS + [ 16 ] . على عكس نظام لامبورت-ديفي الأصلي، يمكن لنظام وينترنيتز ومشتقاته توقيع العديد من البتات دفعة واحدة. يُحدد عدد البتات المراد توقيعها في المرة الواحدة بقيمة تُسمى مُعامل وينترنيتز. يوفر وجود هذا المُعامل توازنًا بين الحجم والسرعة. تُنتج القيم الكبيرة لمُعامل وينترنيتز توقيعات ومفاتيح قصيرة، ولكن على حساب بطء عملية التوقيع والتحقق. عمليًا، القيمة النموذجية لهذا المُعامل هي 16.

في حالة التوقيعات القائمة على التجزئة عديمة الحالة، تُستخدم أنظمة التوقيع قليلة الاستخدام. تسمح هذه الأنظمة بانخفاض مستوى الأمان تدريجيًا في حال استخدام مفتاح التوقيع قليل الاستخدام أكثر من مرة. يُعدّ HORST مثالًا على نظام التوقيع قليل الاستخدام.

دمج العديد من أزواج المفاتيح لمرة واحدة في مخطط توقيع قائم على التجزئة

تعتمد فكرة أنظمة التوقيع القائمة على التجزئة على دمج عدد كبير من أزواج المفاتيح أحادية الاستخدام في بنية واحدة، مما يتيح طريقة عملية للتوقيع أكثر من مرة (ولكن لعدد محدود). ويتم ذلك باستخدام بنية شجرة ميركل، مع إمكانية وجود اختلافات. يُنشأ مفتاح عام ومفتاح خاص من بين العديد من المفاتيح العامة والخاصة لنظام التوقيع أحادي الاستخدام الأساسي. المفتاح العام العالمي هو العقدة الوحيدة في أعلى شجرة ميركل، وقيمته ناتج دالة التجزئة المختارة، لذا يبلغ حجم المفتاح العام النموذجي 32 بايت. ترتبط صلاحية هذا المفتاح العام العالمي بصلاحية مفتاح عام أحادي الاستخدام محدد، وذلك باستخدام سلسلة من عقد الشجرة. تُسمى هذه السلسلة مسار المصادقة، وتُخزن كجزء من التوقيع، مما يسمح للمُدقِّق بإعادة بناء مسار العقد بين هذين المفتاحين العامين.

يُدار المفتاح الخاص العام عادةً باستخدام مولد أرقام شبه عشوائية. ويكفي حينها تخزين قيمة أولية. تُشتق مفاتيح سرية لمرة واحدة تباعًا من القيمة الأولية باستخدام المولد. وبهذه الطريقة، يكون حجم المفتاح الخاص العام صغيرًا جدًا، على سبيل المثال 32 بايتًا.

تُعدّ مشكلة اجتياز الشجرة بالغة الأهمية لأداء التوقيع. وقد تمّ تقديم أساليب أكثر كفاءة بشكل متزايد، مما أدى إلى تسريع وقت التوقيع بشكل كبير.

تستخدم بعض أنظمة التوقيع القائمة على التجزئة طبقات متعددة من الشجرة، مما يوفر توقيعًا أسرع على حساب حجم التوقيعات. في هذه الأنظمة، تُستخدم الطبقة الدنيا فقط من الأشجار لتوقيع الرسائل، بينما تُستخدم جميع الأشجار الأخرى لتوقيع القيم الجذرية للأشجار الأدنى منها.

يوضح عمل Naor–Yung [ 17 ] النمط الذي يتم من خلاله نقل توقيع زمني محدود من عائلة Merkle إلى مخطط توقيع غير محدود (منتظم).

خصائص أنظمة التوقيع القائمة على التجزئة

تعتمد أنظمة التوقيع القائمة على التجزئة على افتراضات أمنية تتعلق بدالة التجزئة الأساسية، ولكن يمكن استخدام أي دالة تجزئة تستوفي هذه الافتراضات. ونتيجةً لذلك، تُنتج كل دالة تجزئة مناسبة نظام توقيع مختلفًا قائمًا على التجزئة. حتى في حال أصبحت دالة تجزئة معينة غير آمنة، يكفي استبدالها بدالة أخرى آمنة للحصول على تطبيق آمن لنظام التوقيع القائم على التجزئة قيد الدراسة. بعض أنظمة التوقيع القائمة على التجزئة (مثل XMSS مع توليد مفاتيح شبه عشوائية) آمنة للأمام، ما يعني أن التوقيعات السابقة تظل صالحة حتى في حال اختراق مفتاح سري.

يُعدّ الحد الأدنى من افتراضات الأمان سمةً أخرى لأنظمة التوقيع القائمة على التجزئة. عمومًا، لا تتطلب هذه الأنظمة سوى دالة تجزئة تشفيرية آمنة (على سبيل المثال، بمفهوم مقاومة الصورة المسبقة الثانية ) لضمان أمان النظام بشكل عام. هذا النوع من الافتراضات ضروري لأي نظام توقيع رقمي؛ مع ذلك، تتطلب أنظمة التوقيع الأخرى افتراضات أمان إضافية ، وهو ما لا ينطبق هنا.

بسبب اعتمادها على نظام توقيع لمرة واحدة، لا تستطيع أنظمة التوقيع القائمة على التجزئة توقيع سوى عدد محدود من الرسائل بشكل آمن. في حالة نظامي Merkle وXMSS، يكون الحد الأقصى هو2ح{\displaystyle 2^{h}}يمكن توقيع الرسائل بشكل آمن، باستخدامح{\displaystyle h}الارتفاع الكلي لشجرة ميركل.

أمثلة على أنظمة التوقيع القائمة على التجزئة

منذ مخطط ميركل الأولي، ظهرت العديد من مخططات التوقيع القائمة على التجزئة مع تحسينات في الأداء. تشمل المخططات الحديثة XMSS، وLeighton–Micali (LMS)، وSPHINCS، وBPQS. معظم مخططات التوقيع القائمة على التجزئة تحتفظ بحالة المفتاح السري، مما يعني أن التوقيع يتطلب تحديث المفتاح السري، على عكس مخططات التوقيع الرقمي التقليدية. بالنسبة لمخططات التوقيع القائمة على التجزئة التي تحتفظ بحالة المفتاح السري، يتطلب التوقيع الاحتفاظ بحالة المفاتيح المستخدمة لمرة واحدة والتأكد من عدم إعادة استخدامها. مخططات XMSS وLMS وBPQS [ 18 ] تحتفظ بحالة المفتاح السري، بينما مخطط SPHINCS لا يحتفظ بحالة المفتاح السري. توقيعات SPHINCS أكبر من توقيعات XMSS وLMS. صُمم BPQS خصيصًا لأنظمة البلوك تشين. بالإضافة إلى مخطط التوقيع لمرة واحدة WOTS+ [ 16 ] ، يستخدم SPHINCS أيضًا مخطط توقيع (قائم على التجزئة) يُسمى HORST. يُعدّ HORST تحسينًا لخوارزمية التوقيع القديمة التي تتطلب عددًا قليلًا من المرات، وهي HORS (التجزئة للحصول على مجموعة فرعية عشوائية). [ 19 ]

تم تحديد مخططات XMSS وXMSS MT القائمة على التجزئة ذات الحالة في RFC 8391 (XMSS: مخطط توقيع ميركل الموسع). [ 20 ] وتم تحديد توقيعات لايتون-ميكالي القائمة على التجزئة في RFC 8554. [ 4 ] وقد اقتُرحت تحسينات عملية في الأدبيات العلمية لتخفيف المخاوف التي تُثيرها المخططات ذات الحالة. [ 21 ] وتشمل دوال التجزئة المناسبة لهذه المخططات SHA-2 و SHA-3 و BLAKE .

تم تحديد مخطط التجزئة عديم الحالة SLH-DSA في FIPS-205 .

التطبيقات

تتوفر أنظمة XMSS وGMSS وSPHINCS في واجهات برمجة تطبيقات التشفير الخاصة بـ Java Bouncy Castle . [ 22 ] كما تتوفر أنظمة LMS [ 23 ] وXMSS في واجهات برمجة تطبيقات التشفير الخاصة بـ wolfSSL . [ 24 ] أما نظام SPHINCS فهو مُدمج في مجموعة أدوات قياس الأداء SUPERCOP. [ 25 ] وتوجد تطبيقات مرجعية مُحسّنة [ 26 ] وغير مُحسّنة [ 27 ] لبروتوكول XMSS RFC. وقد تم تنفيذ نظام LMS بلغة Python [ 28 ] ولغة C [ 29 ] وفقًا لمسودته المنشورة على الإنترنت.

مراجع

  1. ↑ بن ساسون، إيلي وبنتوف، إيدو وهوريش، ينون وريابزيف، مايكل، 2018. سلامة الحوسبة القابلة للتطوير والشفافة والآمنة بعد الكم .
  2. ↑ خالكياس، كونستانتينوس؛ كوهين، شير؛ لوي، كيفن؛ موزينيا، فريدريك؛ رومايلر، يولان (2021). "HashWires: إثباتات نطاق فائقة الكفاءة قائمة على بيانات الاعتماد" . ندوة تقنيات تعزيز الخصوصية (PETS) 2021 .
  3. ↑ "متطلبات التقديم ومعايير التقييم لعملية توحيد معايير التشفير ما بعد الكم" (ملف PDF) . NIST CSRC .
  4. 1 2 ماكجرو، ديفيد؛ كورسيو، مايكل. فلوهرر ، سكوت (أبريل 2019). "RFC 8554 – التوقيعات المستندة إلى التجزئة من Leighton – Micali" . Tools.ietf.org . IETF.
  5. ↑ قسم أمن الحاسوب، مختبر تكنولوجيا المعلومات (2019-02-01). "طلب تعليقات عامة على Stateful HBS | CSRC" . CSRC | NIST . تم الاطلاع عليه بتاريخ 2019-02-04 .
  6. ↑ ألاغيك، غورجان؛ أبون، دانيال؛ كوبر، ديفيد؛ دانغ، كوين؛ دانغ، ثينه؛ كيلسي، جون؛ ليشتينغر، جاكوب؛ ميلر، كارل؛ مودي، داستن؛ بيرالتا، رينيه؛ بيرلنر، راي (2022-07-05). "تقرير حالة عن الجولة الثالثة من عملية توحيد معايير التشفير ما بعد الكمي التابعة للمعهد الوطني للمعايير والتكنولوجيا" . NIST Ir 8413. doi : 10.6028 /NIST.IR.8413-upd1 .
  7. ↑ كوبر، ديفيد؛ أبون، دانيال؛ دانغ، كوين؛ ديفيدسون، مايكل؛ دوركين، موريس؛ ميلر، كارل (29-10-2020). "توصية بشأن مخططات التوقيع القائمة على التجزئة ذات الحالة" . منشور خاص من المعهد الوطني للمعايير والتكنولوجيا 800-208 . doi : 10.6028/NIST.SP.800-208 .
  8. ↑ "المعهد الوطني للمعايير والتكنولوجيا يعلن عن أربع خوارزميات مقاومة للحوسبة الكمومية" . فينشر بيت . 5 يوليو 2022. تاريخ الاطلاع: 10 يوليو 2022 .
  9. ↑ "معيار التوقيع الرقمي القائم على التجزئة بدون حالة" (ملف PDF) . NIST.gov . أغسطس 2024. doi : 10.6028/NIST.FIPS.205 .
  10. ↑ بوخمان، يوهانس؛ داهمن، إريك؛ هولسينغ، أندرياس (2011). "XMSS - نظام توقيع آمن أمامي عملي قائم على افتراضات أمنية دنيا". التشفير ما بعد الكمي . سلسلة محاضرات في علوم الحاسوب. المجلد 7071. الصفحات 117-129 . CiteSeerX 10.1.1.400.6086 . doi : 10.1007/978-3-642-25405-5_8 . ISBN    978-3-642-25404-8ISSN 0302-9743​​ 
  11. ^ بيرنشتاين ، دانيال ج. هوبوود، ديرا؛ هولسينج، أندرياس. لانج, طنجة ; نيدرهاجن، روبن؛ باباكريستودولو، لويزا؛ شنايدر، مايكل. شوابي، بيتر؛ ويلكوكس أوهيرن، زوكو (2015). “SPHINCS: التوقيعات العملية القائمة على التجزئة عديمة الجنسية”. في أوزوالد, إليزابيث ; فيشلين، مارك (محرران). التقدم في علم التشفير - EUROCRYPT 2015 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 9056. سبرينغر برلين هايدلبرغ. ص 368 – 397. CiteSeerX 10.1.1.690.6403 . دوى : 10.1007/978-3-662-46800-5_15 . رقم ISBN    9783662467992.
  12. ↑ "الصمام: مقدمة" .
  13. ↑ بوخمان، يوهانس؛ داهمن، إريك؛ كلينتسيفيتش، إيلينا؛ أوكيا، كاتسويوكي؛ فيوم، كاميل (2007). "توقيعات ميركل ذات سعة توقيع غير محدودة تقريبًا". التشفير التطبيقي وأمن الشبكات . سلسلة محاضرات في علوم الحاسوب. المجلد 4521. الصفحات 31-45 . doi : 10.1007/978-3-540-72738-5_3 . ISBN   978-3-540-72737-8.
  14. ↑ هولسينغ، أندرياس؛ راوش، ليا؛ بوخمان، يوهانس (2013). "المعلمات المثلى لـ XMSS MT" . هندسة الأمن ومعلوماتية الاستخبارات . سلسلة محاضرات في علوم الحاسوب. المجلد 8128. الصفحات 194-208 . doi : 10.1007/978-3-642-40588-4_14 . ISBN   978-3-642-40587-7.
  15. ↑ دودز، سي.؛ سمارت، إن. بي.؛ ستام، إم. (2005). "مخططات التوقيع الرقمي القائمة على التجزئة". التشفير والترميز . سلسلة محاضرات في علوم الحاسوب. المجلد 3796. الصفحات 96-115 . doi : 10.1007/11586821_8 . ISBN   978-3-540-30276-6.
  16. 1 2 هولسينغ، أندرياس (2013). "W-OTS+ - توقيعات أقصر لأنظمة التوقيع القائمة على التجزئة". التقدم في علم التشفير - AFRICACRYPT 2013. سلسلة محاضرات في علوم الحاسوب. المجلد 7918. الصفحات 173-188 . doi : 10.1007/978-3-642-38553-7_10 . ISBN   978-3-642-38552-0.
  17. ↑ م. ناور، م. يونغ. "دوال التجزئة أحادية الاتجاه الشاملة وتطبيقاتها في مجال التشفير". STOC 1989..
  18. ↑ تشالكياس، كونستانتينوس؛ براون، جيمس؛ هيرن، مايك؛ ليلهاجن، تومي؛ نيتو، إيغور؛ شروتر، توماس (2018). "التوقيعات ما بعد الكمومية بتقنية البلوك تشين" (ملف PDF) . وقائع المؤتمر الدولي لتقنية البلوك تشين (Cybermatics-2018) التابع لمعهد مهندسي الكهرباء والإلكترونيات : 1196-1203 .
  19. ↑ ريزين، ليونيد؛ ريزين، ناتان (2002). "أفضل من بيبا: توقيعات قصيرة لمرة واحدة مع توقيع وتحقق سريعين". أمن المعلومات والخصوصية . سلسلة محاضرات في علوم الحاسوب. المجلد 2384. الصفحات 144-153 . CiteSeerX 10.1.1.24.7320 . doi : 10.1007/3-540-45450-0_11 . ISBN    978-3-540-43861-8.
  20. ^ هولسينج ، أندرياس. بوتين، دينيس؛ غازداغ، ستيفان؛ ريجنيفيلد، جوست. محيسن ، عزيز (مايو 2018). "RFC 8391 – XMSS: نظام توقيع Merkle الموسع" . Tools.ietf.org . IETF.
  21. ↑ ماكغرو، ديفيد؛ كامباناكيس، بانوس؛ فلوهر، سكوت؛ غازداغ، ستيفان-لوكاس؛ بوتين، دينيس؛ بوخمان، يوهانس (2016). "إدارة الحالة للتوقيعات القائمة على التجزئة" (ملف PDF) . بحث في توحيد معايير الأمن . سلسلة محاضرات في علوم الحاسوب. المجلد 10074. الصفحات 244-260 . doi : 10.1007/978-3-319-49100-4_11 . ISBN   978-3-319-49099-1. S2CID 809073 . مؤرشف من الأصل (PDF) بتاريخ 2017-08-18. 
  22. ↑ "bcgit/bc-java" . GitHub . 2018-12-18.
  23. ↑ "تطبيقات wolfCrypt لتوقيعات LMS/HSS و XMSS/XMSS^MT: خيارات البناء ومعايير الأداء (Intel x86)" . wolfSSL . 2024-06-18.
  24. ↑ "wolfSSL/wolfssl" . GitHub . 2023-11-22.
  25. ↑ "سوبر كوب" . مؤرشف من الأصل بتاريخ 15 فبراير 2015. تم الاطلاع عليه بتاريخ 31 مايو 2017 .
  26. ↑ "الرمز" . أندرياس هولسينغ . مؤرشف من الأصل بتاريخ 22-08-2017 . تم الاطلاع عليه بتاريخ 31-05-2017 .
  27. ↑ "squareUP > المنشورات" . www.pqsignatures.org .
  28. ↑ ديفيد، ماكجرو (29-05-2018). "حزمة hash-sigs: تطبيق لنظام التوقيع الهرمي لايتون-ميكالي (HSS)" . جيت هاب .
  29. ↑ ديفيد، ماكجرو (22-11-2018). "تطبيق كامل الميزات لأنظمة التوقيع القائمة على التجزئة LMS وHSS من مسودة draft-mcgrew-hash-sigs-07" . جيت هاب .
  • تي. لانج. "التوقيعات القائمة على التجزئة". موسوعة التشفير والأمن، سبرينغر الولايات المتحدة، 2011.
  • إف تي لايتون، إس. ميكالي. "مخططات توقيع رقمي كبيرة الحجم، سريعة وآمنة بشكل مثبت، تعتمد على وظائف تجزئة آمنة واحدة". براءة اختراع أمريكية رقم 5,432,852.1995.
  • جي. بيكر. "مخططات توقيع ميركل، وأشجار ميركل وتحليلها التشفيري"، ندوة "التشفير ما بعد الكمي" في جامعة روهر بوخوم، ألمانيا، 2008.أُرشف بتاريخ 30 أغسطس 2017 في أرشيف الإنترنت (Wayback Machine) .
  • E. Dahmen، M. Dring، E. Klintsevich، J. Buchmann، LC Coronado Garcia. “CMSS – نظام توقيع Merkle المحسّن”. التقدم في علم التشفير – Indocrypt 2006.
  • ر. ميركل. "السرية، والمصادقة، وأنظمة المفتاح العام / التوقيع الرقمي المعتمد". أطروحة دكتوراه، قسم الهندسة الكهربائية، جامعة ستانفورد، 1979.أُرشف بتاريخ 14 أغسطس 2018 في أرشيف الإنترنت (Wayback Machine) .
  • إس. ميكالي، إم. جاكوبسون، تي. لايتون، إم. شيدلو. "تمثيل شجرة ميركل الكسورية واجتيازها". RSA-CT 03.
  • ب. كامباناكيس، س. فلوهر. "LMS مقابل XMSS: مقارنة بين المعايير المقترحة للتوقيع القائم على التجزئة ذي الحالة". أرشيف الطباعة الإلكترونية لعلم التشفير، التقرير 2017/349.
  • د. ناور، أ. شينهاف، أ. وول. "إعادة النظر في التوقيعات لمرة واحدة: توقيعات سريعة عملية باستخدام اجتياز شجرة ميركل الكسورية". المؤتمر الرابع والعشرون لمهندسي الكهرباء والإلكترونيات في إسرائيل، 2006.أُرشف بتاريخ 5 فبراير 2018 في أرشيف الإنترنت (Wayback Machine) .
  • قائمة مع تعليقات على الأدبيات المتعلقة بمخططات التوقيع القائمة على التجزئة.
  • قائمة أخرى بالمراجع (بدون تعليق).