الانتقال إلى المحتوى
العودة إلى نتائج البحث

التحليل الخطي للتشفير

قدّمه
Mitsuru Matsui
السنة
1993
النوع
linear approximation attack
العائلة
Cryptanalytic technique

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

التحليل الخطي للتشفير هو هجوم يعتمد على نص واضح معروف (known-plaintext attack) يستغل التقريبات الخطية للتحويلات غير الخطية في الشفرة لاستعادة بتات المفتاح السري. قدمه ميتسورو ماتسوي في عام 1993، ويوفر التحليل الخطي للتشفير هجمات عملية على شفرات مثل DES بتعقيد حسابي أقل من القوة الغاشمة. تقنية التحليل الخطي تدرس التحيزات الإحصائية في كيفية ارتباط التركيبات الخطية لبتات النص الواضح وبتات النص المشفر ببتات المفتاح، مما يتيح استعادة المفتاح بمتطلبات بيانات مخفضة.

الفكرة الحدسية وراء الطريقة

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

التاريخ

قدم ماتسوي التحليل الخطي للتشفير في عام 1993 كهجوم يعتمد على نص واضح معروف على DES. في عام 1994، أظهر ماتسوي أول تحليل تشفير تجريبي لمعيار DES باستخدام التحليل الخطي للتشفير، واستعاد مفتاحًا باستخدام 2^43 نصًا واضحًا معروفًا. أظهر هذا الاختراق هجمات عملية ضد معيار منشور وأثر على تطوير AES بحدود مقاومة مثبتة.

متى تُستخدم

يُستخدم التحليل الخطي للتشفير في أبحاث تحليل التشفير وتقييم تصميم الشفرات. يوجه مصممي الشفرات في اختيار صناديق الاستبدال (S-boxes) والتحويلات التي تقاوم التقريبات الخطية. تم تصميم الشفرات الحديثة بحدود مثبتة لقوة التقريب الخطي.

الحدود والاعتبارات

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

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • هجوم عملي على DES يتطلب 2^43 زوجًا من النص الواضح والنص المشفر و 2^39 عملية.
  • إطار رياضي مُصاغ جيدًا (قاعدة التكديس - piling-up lemma) لتحليل انحرافات التقريب.
  • يكمل التحليل التفاضلي للتشفير (differential cryptanalysis)، حيث يجد نقاط ضعف قد يغفلها التحليل التفاضلي.
  • يشكل متطلبات تصميم الشفرات لاختيار صناديق الاستبدال وتحويلات الجولات.

التطبيقات

  • تحليل التشفير للشفرات الكتلية (block ciphers) لتقييم الخصائص الأمنية في البحث والتوحيد القياسي.
  • تصميم الشفرات واختيار صناديق الاستبدال لضمان حدود تقريب خطي كافية.
  • التحقق من معايير التشفير (مثل NIST، ETSI) التي تتطلب تحليل المقاومة الخطية.
  • تقييم الشفرات القديمة لاتخاذ قرارات الإحالة إلى التقاعد والاستبدال.

كيف يعمل

كيف يعمل

1

إيجاد تقريبات خطية: علاقات خطية بين بتات النص الواضح وبتات النص المشفر وبتات المفتاح تصدق باحتمالية تختلف بشكل كبير عن 0.5.

2

تقدير انحراف (الفرق عن 0.5) كل تقريب خطي باستخدام التحليل الإحصائي لتحويلات الجولات.

3

بالنسبة لقيم المفاتيح المرشحة، عد عدد المرات التي يصدق فيها التقريب الخطي في أزواج النص الواضح والنص المشفر المعروفة. المفتاح الصحيح يجعل التقريب يصدق في أغلب الأحيان.

4

التحقق من بتات المفتاح المستعادة عن طريق فك تشفير النص المشفر والتحقق من صحته.

الأخطاء الشائعة

  • افتراض أن جميع التقريبات الخطية قابلة للاستغلال؛ التقريبات الضعيفة توفر ميزة ضئيلة.
  • التقليل من تقدير صعوبة الهجوم العملي عندما تبدو متطلبات البيانات النظرية معقولة.
  • إهمال التفاعل بين الخصائص الخطية والتفاضلية في تحليل الشفرات.

الأسئلة الشائعة

ما هي قاعدة التكديس (piling-up lemma)؟

توفر قاعدة التكديس طريقة لحساب انحراف التقريبات الخطية عبر جولات متعددة عن طريق دمج انحرافات تقريبات الجولات الفردية. وهي أساسية للتحليل الخطي للتشفير.

كيف تقاوم AES التحليل الخطي للتشفير؟

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

ما الفرق بين التحليل الخطي والتحليل التفاضلي للتشفير؟

يدرس التحليل التفاضلي فروق المدخلات والمخرجات، بينما يدرس التحليل الخطي التقريبات الخطية (XOR لبتات النص الواضح والنص المشفر). كلاهما يستغل نقاط الضعف الهيكلية في الشفرات.

هل يمكن للتحليل الخطي للتشفير كسر الشفرات الحديثة؟

ليس عمليًا. الشفرات الحديثة مثل AES لديها حدود مثبتة للتقريبات الخطية تجعل الهجمات غير ممكنة حسابيًا.

كيف أقوم بتقييم المقاومة الخطية في تصميم شفرتي؟

حلل جداول تقريب صناديق الاستبدال الخطية واحسب الانحراف الأقصى عبر الجولات باستخدام قاعدة التكديس. تأكد من أن الانحراف الأقصى ضئيل عبر جميع التقريبات الخطية الممكنة.

طرق ذات صلة

المصادر

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    افتح مرجع DOI
    تم النسخ.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    افتح مرجع DOI
    تم النسخ.