💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

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

المؤلفون الأصليون: Najmul Hasan, Prashanth BusiReddyGari

نُشر 2026-02-06

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Najmul Hasan, Prashanth BusiReddyGari

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

لقد أجرى المعهد الوطني للمعايير والتقنية (NIST) مسابقة لإيجح أفضل 10 "أقفال" لهذه الروبوتات الصغيرة. وقد اختبروها في العالم الحقيقي، لكنهم لم يمتلكوا صيغة رياضية موحدة واحدة لتفسير لماذا كان بعضها أسرع من غيره على الورق.

هذه الورقة البحثية التي كتبها نجم الحسن وبراشانت بوسي ريديملي تسد هذه الفجوة. إليك ما فعلوه، مشروحاً ببساطة:

1. المشكلة: قياس "وزن" القفل

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

لقد أرادوا إنشاء خريطة لـ "التعقيد الزمني" (Time Complexity). وبالمعنى البسيط، هذه هي الصيغة التي تخبرك: "إذا كانت لديك رسالة قصيرة، فما مدى سرعة القفل؟ وإذا كانت لديك رسالة طويلة، فإلى أي مدى سيصبح أبطأ؟"

2. الحل: خط التجميع ثلاثي المراحل

قام المؤلفون بتفكيك كل خوارزمية تشفير من المتأهلة العشر إلى ثلاث مراحل بسيطة، مثل خط تجميع في مصنع:

المرحلة 1: التهيئة (الإعداد): قبل أن تتمكن من تعبئة أي شيء، يجب عليك إعداد الآلة. تقوم بإدخال المفتاح و"الرقم العشوائي" (nonce) (وهو رقم فريد للجلسة). يستغرق هذا وقتاً ثابتاً، بغض النظر عن حجم رسالتك. إنه يشبه تسخين محرك السيارة؛ فهو يستغرق نفس الوقت سواء قدت ميلاً واحداً أو 100 ميل.
المرحلة 2: معالجة البيانات (التعبئة): هنا يتم تشفير الرسالة الفعلية والبيانات الإضافية. هذا هو العمل الشاق. يعتمد الوقت المستغرق هنا كلياً على مقدار البيانات التي لديك. لقد وضع المؤلفون صيغاً لحساب عدد "الخطوات" (العمليات الرياضية) المطلوبة لكل كتلة من البيانات بدقة.
المرحلة 3: الإنهاء (الختم): بمجرد تعبئة كل شيء، تحتاج إلى ختم الصندوق وإرفاق علامة أمنية لإثبات عدم العبث به. هذا عمل ثابت آخر، مثل وضع ملصق نهائي على الطرد.

3. النتائج: من هو الأخف وزناً؟

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

إليك بعض النتائج المثيرة للاهتمام التي كشفوا عنها باستخدام صيغهم الجديدة:

عداؤو "الخط المستقيم البسيط": خوارزميات مثل GIFT-COFB و Grain-128AEAD و ISAP تشبه الطريق السريع المستقيم. نمو وقتها يسير تماماً بالتوازي مع حجم الرسالة. إذا ضاعفت الرسالة، تضاعف الوقت. ليس لديهم "ضرائب" إضافية أو مضاعفات معقدة. GIFT-COFB بسيط للغاية، مما يجعله فعالاً جداً للرسائل الكبيرة.
عداؤو "الكتل": تعمل خوارزميات مثل TinyJambu و Romulus مثل حزام ناقل لا يقبل إلا العناصر في صناديق ذات أحجام محددة. إذا لم تتناسب رسالتك تماماً داخل صندوق، فعليهم إضافة "حشوة" (مساحة فارغة) لملئه. هذا يضيف عبئاً إضافياً، خاصة للرسائل الصغيرة، لكنهم منظمون للغاية.
عداؤو "التبديل": تستخدم خوارزميات مثل ASCON (التي اختارها NIST في النهاية كفائز) و Xoodyak طريقة "الخلط". يأخذون البيانات ويمزجونها حول بعضها بنمط محدد. تظهر صيغهم أنها فعالة للغاية، حيث تأتي تكلفة الوقت أساساً من عدد المرات التي يتعين عليهم فيها خلط البيانات.
العداء "الهجين": ISAP هو مزيج من تقنيات مختلفة. فهو ينشئ مفتاحاً مؤقتاً لكل جلسة، مما يضيف وقتاً ضئيلاً للإعداد ولكنه يجعله آمناً جداً ضد أنواع معينة من الاختراق.

4. لماذا هذا مهم؟

لا تكتفي الورقة البحثية بالقول إن "الخوارزمية أ أسرع"، بل تشرح لماذا من خلال النظر في الرياضيات الكامنة وراء التصميم.

خيارات التصميم: يوضح المؤلفون أن "شكل" الخوارزمية هو ما يحدد سرعتها. فبعضها مبني مثل طريق ذي مسار واحد (تشفير التدفق/stream ciphers)، بينما البعض الآخر مبني مثل طريق سريع متعدد المسارات مع بوابات تحصيل رسوم (تشفير الكتل/block ciphers).
القدرة على التنبؤ: الآن، يمكن للمهندسين الذين يصممون هذه الأجهزة الصغيرة التنبؤ بالضبط بكمية عمر البطارية التي ستستهلكها خوارزمية ما قبل أن يبنوا الجهاز حتى.

الخلاصة

توفر هذه الورقة البحثية "مترجماً عالمياً" لأداء التشفير. بدلاً من التخمين أو إجراء اختبارات لا تنتهي، يمكن للمهندسين الآن استخدام هذه الصيغ الرمزية لاختيار "القفل" المثالي لجهازهم الخاص.

إذا كنت بحاجة إلى المسار الأبسط والأخف تماماً للرسائل الضخمة، فإن الرياضيات تشير إلى GIFT-COFB.
إذا كنت بحاجة إلى توازن بين الأمان والسرعة للاستخدام العام، فإن الرياضيات تسلط الض الضوء على ASCON.
إذا كنت بحاجة إلى معالجة البيانات بت (bit) بت دون انتظار كتل كاملة، فإن Grain-128AEAD هو الخيار الواضح.

يخلص المؤلفون إلى أنه من خلال فهم هذه "الأوزان" النظرية، يمكننا تأمين إنترنت الأشياء بشكل أفضل، مما يضمن بقاء أجهزتنا الصغيرة آمنة دون نفاد بطاريتها. وهم يخططون لاختبار هذه الصيغ في سيناريوهات من العالم الحقيقي مثل بطاقات الهوية الرقمية لمعرفة ما إذا كانت الرياضيات ستصمد في الواقع.

ملخص تقني: توصيف التعقيد الزمني للمرشحين النهائيين في معيار المعهد الوطني للمعايير والتقنية (NIST) للتشفير خفيف الوزن

بيان المشكلة
بما أن التقنيات الناشئة في أنظمة الهوية الرقمية وإنترنت الأشياء (IoT) تعتمد بشكل متزايد على أجهزة ذات قدرات معالجة وذاكرة وطاقة محدودة، فقد أصبح الطلب على التشفير خفيف الوزن (LWC) أمراً بالغ الأهمية. وبينما أتم المعهد الوطني للمعايير والتقنية (NIST) عملية تقييم لعشر خوارزميات مرشحة نهائية، فإن الأدبيات الحالية تعتمد بشكل كبير على المقاييس التجريبية (وقت التنفيذ والإنتاجية) بدلاً من الفهم النظري الموحد. وتركز الوثائق الحالية لخوارزميات مثل Ascon وISAP وTinyJAMBU على تحسينات التنفيذ، لكنها تفتقر إلى تعبيرات رسمية للتعقيد الزمني. هذا الغياب لإطار عمل نظري يعيق القدرة على التمييز المنهجي بين كفاءة الخوارزميات والتنبؤ بأداء التوسع عبر البيئات المتنوعة والمقيدة.

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

يتم نمذجة إجمالي التعقيد الزمني ( $T_{total}$ ) كمجموع لـ:

التهيئة ( $T_{init}$ ): التكاليف الثابتة لإعداد المفتاح والـ nonce ($ck + cn$)، وهي مستقلة عن حجم المدخلات.
معالجة البيانات ( $T_{process}$ ): التكاليف المرتبطة بمعالجة البيانات المصاحبة ( $A$ ) وكتل الرسائل ( $M$ ). ويتم تفكيكها إلى $T_A$ و $T_M$ ، وتُحسب بناءً على عدد الكتل، وأوقات التبديل ( $T_p$ )، والأعباء التشغيلية.
الإنهاء ( $T_{finalize}$ ): تكاليف الوقت الثابت ( $c_f$ ) لتوليد أو التحقق من علامة المصادقة (authentication tag).

باستخدام هذا التفكيك ثلاثي المراحل، يشتق المؤلفون تعبيرات التعقيد الرمزي لجميع المرشحين العشرة النهائيين (Ascon، Elephant، GIFT-COFB، Grain-128AEAD، ISAP، PHOTON-Beetle، Romulus، SPARKLE، TinyJAMBU، وXoodyak) بناءً على مواصفاتهم الخوارزمية، بما في ذلك أحجام الحالة، وتصميمات التبديل، وأنماط التشغيل.

المساهمات والنتائج الرئيسية
تقدم الورقة تحليلاً مقارناً لتوسع الحوسبة للمرشحين العشرة، مع تصنيفهم حسب استراتيجياتهم الهيكلية الأساسية:

الخوارزميات القائمة على التبديل (Permutation-Based): تستخدم خمس خوارزميات مرشحة (Ascon، Elephant، PHOTON-Beetle، SPARKLE، Xoodayk) بناءات قائمة على الإسفنج (sponge) أو التبديل المركز. ويتحدد تعقيدها عموماً بتكلفة التبديل ( $b$ ) وعدد الكتل المعالجة. فعلى سبيل المثال، تحقق Ascon توسعاً فعالاً ( $O(l_A \cdot b + l_P \cdot b)$ ) من خلال تهيئة مبسطة مكونة من 12 جولة، بينما تتضمن SPARKLE حدوداً ثابتة إضافية لدعم وظائف التشفير والتدوين (hashing) معاً.
الخوارزميات القائمة على تشفير الكتل (Block Cipher-Based): تستخدم ثلاث خوارزميات مرشحة (GIFT-COFB، Romulus-N، TinyJAMBU) بناءات تشفير الكتل أو السجلات. وقد تم تسليط الضوء على GIFT-COFB لتوسعها الخطي البسيط بشكل ملحوظ ( $O(\ell_A + \ell_M)$ ) دون عوامل ضرب، مما يجعلها عالية الكفاءة للرسائل الكبيرة. وتستخدم TinyJAMBU عمليات تبديل مزدوجة ( $P_{640}$ و $P_{1024}$ ) لمراحل مختلفة، مما يضيف تكاليف تهيئة ثابتة محددة وتكاليف معالجة منفصلة للبيانات المصاحبة والرسائل.
خوارزميات التشفير المتدفق والهجينة (Stream Cipher and Hybrid): تعد Grain-128AEAD هي المرشح الوحيد من نوع التشفير المتدفق، حيث تقدم تعقيداً ( $O(|M| + |AD|)$ ) يتوسع مباشرة مع عدد البتات، مما يلغي عبء الحشو (padding). وتجمع ISAP بين التشفير القائم على الإسفنج واستخلاص مفتاح الجلسة، محققة توسعاً خطياً ( $O(|A| + |M|)$ ) مع توفير المقاومة ضد هجمات القنوات الجانبية من خلال فصل المفاتيح.

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

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

1. المشكلة: قياس "وزن" القفل

2. الحل: خط التجميع ثلاثي المراحل

3. النتائج: من هو الأخف وزناً؟

4. لماذا هذا مهم؟

الخلاصة

أبحاث مشابهة