💻 computer science

Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers

تقدم هذه الدراسة خوارزمية جينية مبتكرة معززة بدالة تكلفة طيف "والش-هادامارد" تولد بكفاءة صناديق S-box بحجم 8x8 ذات عدم خطية تبلغ 104 ومعدل نجاح بنسبة 100%، مما يقلل بشكل كبير من عدد التكرارات مقارنة بالطرق السابقة مع مضاهاة أداء أفضل الأساليب المعروفة.

المؤلفون الأصليون: Oleksandr Kuznetsov, Nikolay Poluyanenko, Emanuele Frontoni, Marco Arnesano, Oleksii Smirnov

نُشر 2026-04-13

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

CC BY 4.0

المؤلفون الأصليون: Oleksandr Kuznetsov, Nikolay Poluyanenko, Emanuele Frontoni, Marco Arnesano, Oleksii Smirnov

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

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

فكر في الـ S-box كأنه مشفر ضخم ومعقد. تضع رقماً في الداخل، فيخرج لك رقماً مختلفاً تماماً. إذا كان المشفر بسيطاً للغاية (مثل مجرد إضافة 1 إلى كل رقم)، فيمكن للمخترق تخمين النمط بسهولة. أما إذا كان المشفر فوضوياً وغير قابل للتوقع، فسيتحول إلى كابوس للمخترقين.

المشكلة: البحث عن المشفر المثالي

إن إنشاء S-box مثالي يشبه محاولة العثور على حبة رمل واحدة محددة في شاطئ بحجم كوكب. هناك الكثير من الطرق الممكنة لترتيب الأرقام بحيث أن فحصها جميعاً واحداً تلو الآخر سيستغرق وقتاً أطول من عمر الكون.

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

الحل: التطور داخل الحاسوب

هنا يأتي دور مؤلفي الورقة البحثية. لقد قرروا التوقف عن محاولة تصميم الـ S-box المثالي، وبدلاً من ذلك، تركوا الطبيعة تقوم بالعمل. لقد استخدموا خوارزمية جينية (Genetic Algorithm)، وهو برنامج حاسوبي يحاكي التطور.

إليك كيف يعمل هذا "التطور الرقمي" باستخدام تشبيه بسيط:

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

المفاجأة الكبرى: القليل يعني الكثير

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

اكتشف المؤلفون شيئاً يخالف المنطق السائد:
لقد وجدوا أن امتلاك مجتمع مكون من فرد واحد فقط من المشفرات هو الذي يعمل بشكل أفضل!

فكر في الأمر على هذا النحو:

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

في تجربة المؤلفين، وجد هذا النهج (نهج "الشخص الواحد") الـ S-box المثالي في حوالي 49,400 محاولة. وهذا سريع للغاية ويتوافق مع سرعة أفضل الأساليب المستخدمة حالياً من قبل نخبة خبراء التشفير في العالم.

لماذا يهم هذا الأمر؟

السرعة والكفاءة: لقد وجدوا طريقة لتوليد هذه الأقفال فائقة القوة بشكل أسرع بكثير من الطرق الجينية السابقة (التي كانت تستغرق ملايين المحاولات).
الموثوقية: طريقتهم تعمل بنسبة 100% من الوقت. في كل مرة يشغلون فيها البرنامج، يجدون S-box مثالياً.
خيارات جديدة: قبل هذا، إذا كنت تريد S-box عشوائياً وقوياً، كان عليك غالباً استخدام "تسلق التل" (Hill Climbing) (وهو نوع آخر من التحسين). الآن، أصبح لدى خبراء التشفير أداة قوية جديدة (الخوارزميات الجينية) تقوم بنفس المهمة. امتلاك أدوات مختلفة أمر رائع، لأنه إذا "علق" أحد الأساليب أو تم اكتشاف نقطة ضعف فيه، فلدينا أداة أخرى جاهزة للاستخدام.

الخلاصة

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

إنها تذكير بأنه في العالم الرقمي، أحياناً يأتي أقوى أنواع التطور من خط واحد مركز من التحسين، وليس من حشد فوضوي.

إليك ملخص تقني مفصل لورقة بحثية بعنوان: "نهج تطوري لتوليد صناديق S-box: تحسين الاستبدالات غير الخطية في التشفير المتماثل".

1. بيان المشكلة

يعد توليد صناديق الاستبدال (S-boxes) القوية تشفيرياً تحدياً حرجاً في التشفير بالمفاتيح المتماثلة. توفر صناديق S-box اللازمة من عدم الخطية (Nonlinearity) لمقاومة تحليل التشفير الخطي والتفاضلي.

التحدي: مساحة البحث لصندوق S-box بحجم $8 \times 8$ هي تقريباً $2^{256}$ (تحديداً $8! \approx 5 \times 10^{10}$ للتبديلات البيجكتية، رغم أن الورقة تشير إلى أن مساحة التكوين شاسعة)، مما يجعل البحث الشامل مستحيلاً.
الهدف: توليد صناديق S-box بحجم $8 \times 8$ ذات عدم خطية (NL) لا يقل عن 104 (وهو معيار هام يقترب من الحد الأقصى النظري البالغ 112) مع الحفاظ على خصائص أخرى مثل الانتظام التفاضلي والحصانة الجبرية.
الفجوة: بينما توجد بناءات جبرية (مثل AES)، إلا أنها تمتلك هياكل متأصلة تجعلها عرضة للهجمات الجبرية. استُخدمت طرق استدلالية (مثل التبريد المحاكي Simulated Annealing، وتسلق التل Hill Climbing)، لكن الخوارزميات الجينية (GAs) عانت تاريخياً من ضعف الكفاءة، حيث كانت تتطلب غالباً ملايين التكرارات للوصول إلى عدم خطية عالية مقارنة بالأساليب الاستدلالية الأخرى.

2. المنهجية

يقترح المؤلفون خوارزمية جينية معدلة تبتعد عن الخوارزميات الجينية التقليدية متعددة المجموعات عبر دمج عناصر من "تسلق التل العشوائي" (Stochastic Hill Climbing).

أ. هيكل الخوارزمية

استراتيجية الجمهرة (Population Strategy): على عكس الخوارزميات الجينية القياسية التي تحافظ على مجموعات متنوعة كبيرة، تستكشف الدراسة تكويناً يتم فيه غالباً تقليل حجم الجمهرة ( $K_{pop}$ ) إلى 1. وهذا يحول الخوارزمية الجينية فعلياً إلى عملية تسلق تل عشوائي حيث يتم تعديل صندوق S-box "نخبة" واحد بشكل متكرر.
عامل الطفرة (Mutation Operator): يتضمن العامل الأساسي تبديل عنصرين مختلفين تم اختيارهما عشوائياً داخل تبديل صندوق S-box. هذا يحافظ على خاصية الـ "بيجيكشن" (الارتباط المتبادل واحد لواحد) الضرورية لصناديق S-box.
الاختيار (Selection): تقوم دالة elite_selection بترتيب صناديق S-box بناءً على عدم الخطية وقيمة دالة الهدف، مع الاحتفاظ فقط بأفضل العناصر لأداء الجيل التالي.
الإنهاء (Termination): تتوقف الخوارزمية عند العثور على صندوق S-box بـ $NL \geq 104$ أو عند الوصول إلى حد أقصى من التكرارات (150,000).

ب. دالة الهدف (دالة التكلفة)

تستخدم الدراسة دالة تكلفة طيف هادامارد-والش (WHS) المقترحة من قبل كلارك وآخرون.

الصيغة: $R = \sum_{b=0}^{255} \sum_{i=0}^{255} |WHT[b, i]| - X$
المعلمات: تم ضبطها تجريبياً لتكون $R=12$ و $X=0$ .
الغرض: تقيم هذه الدالة مدى ابتعاد الدوال المكونة لصندوق S-box عن الدوال الأفينية، وهو ما يرتبط مباشرة بعدم الخطية.

ج. الإعداد التجريبي

التنفيذ: لغة C++ مع استخدام التوازي عبر 8 خيوط معالجة (threads) لتسريع تقييم دالة الهدف.
مسح المعلمات (Parameter Sweep): أجرى المؤلفون 12,100 تشغيل مستقل (100 تشغيل لكل تكوين) مع تغيير:
- حجم الجمهرة ( $K_{pop}$ ): من 1 إلى 21 (بخطوة 2).
- معدل الطفرة ( $K_{mut}$ ): من 1 إلى 31 (بخطوة 3).
المقياس: المقياس الأساسي للكفاءة هو $K_{Sbox}$ ، وهو عدد صناديق S-box التي تم توليدها وتقييمها قبل الوصول إلى الحل المستهدف.

3. المساهمات الرئيسية

التكافؤ مع أفضل الطرق: تثبت الدراسة أن الخوارزمية الجينية يمكنها تحقيق أداء مكافئ لأفضل طرق "تسلق التل" (Hill Climbing) المعروفة، والتي كانت تُعتبر سابقاً متفوقة لهذا المهمة تحديداً.
تحسين معلمات الخوارزمية الجينية: حدد البحث تكويناً مثالياً غير متوقع: حجم الجمهرة = 1. وهذا يشير إلى أن فائدة "الاستكشاف" (Exploration) في الجمهرات الكبيرة تتضاءل أمام كفاءة "الاستغلال" (Exploitation) في البحث المركز لفرد واحد (تسلق التل العشوائي).
تحسين جذري في الكفاءة: قللت الخوارزمية الجينية المقترحة عدد التكرارات المطلنة بمقدار أضعاف مضاعفة مقارنة بالتطبيقات السابقة للخوارزميات الجينية (على سبيل المثال، تقليلها من حوالي 3.8 مليون تكرار في الأعمال السابقة إلى حوالي 49,000).
نسبة نجاح 100%: حققت الطريقة المحسنة نسبة نجاح 100% في توليد صناديق S-box بعدم خطية 104، مما يضاهي موثوقية الطرق الحتمية أو الهجينة رفيعة المستوى.

4. النتائج

التكوين الأمثل: تم تحقيق أفضل أداء باستخدام $K_{pop} = 1$ و $K_{mut} = 7$ .
مقاييس الأداء:
- متوسط التكرارات: 49,277 (تحديداً 49,399 في الملخص النهائي) للوصول إلى $NL=104$ .
- نسبة النجاح: 100%.
- المقارنة: هذا يعادل إحصائياً عمل "تسلق التل" الخاص بالمؤلفين (50,000 تكرار)، وهو أفضل بكثير من محاولات الخوارزميات الجينية الأخرى (التي تراوحت بين 741,000 و 3.8 مليون تكرار).
القابلية للتوسع: أدى زيادة حجم الجمهرة عموماً إلى تدهور الأداء (زيادة $K_{Sbox}$ )، ويرجع ذلك على الأرجح إلى العبء الحسابي لتقييم الجمهرات الأكبر وبطء التقارب.
التوازي (Parallelization): قلل استخدام 8 خيوط معالجة من وقت التنفيذ الفعلي (wall-clock time) بشكل كبير، خاصة بالنسبة للتكوينات ذات الجمهرات الأكبر.

5. الأهمية والآثار المترتبة

توسيع مجموعة الأدوات: من خلال إثبات أن الخوارزميات الجينية يمكنها مضاهاة كفاءة "تسلق التل"، توسع هذه الدراسة مجموعة الأدوات التشفيرية. توفر الخوارزميات الجينية مزايا فريدة في القابلية للتكيف (سهولة التعديل لتحسين الأهداف المتعددة) وإمكانات التوازي.
العشوائية مقابل الهيكل: تدعم الطريقة توليد صناديق S-box تبدو عشوائية وتفتقر إلى الهياكل الجبرية الموجودة في البناءات القياسية (مثل AES)، مما قد يوفر مقاومة أفضل ضد التحليل الجبري.
الأبحاث المستقبلية: تشير النتائج إلى أن توليد صنادي-S-box في المستقبل يجب أن يركز على:
- دمج الخوارزميات الجينية مع الاستدلالات الأخرى (Hybridizing).
- دمج معايير إضافية (الحصانة الجبرية، الانتظام التفاضلي) مباشرة في دالة اللياقة (fitness function).
- الاستفادة من الحوسبة المتوازية لتوسيع نطاق عمليات البحث المركزة للفرد الواحد هذه.

في الختام، نجحت هذه الورقة في سد الفجوة بين الحوسبة التطورية وتصميم الأوليات التشفيرية، حيث أثبتت أنه مع الضبط الصحيح للمعلمات (تحديداً الجمهرة ذات الفرد الواحد)، فإن الخوارزميات الجينية هي طريقة فعالة للغاية وموثوقة لتوليد صناديق S-box عالية الجودة.