تحليل التعمية الخطي
تحليل التعمية الخطي Linear cryptanalysis يعتمد على ايجاد تقريب خطي لوصف عمليات التحويل التي تتم في خوارزمية DES. يمكن لهذه الطريقة حتى توجد مفتاح DES من خلال 247 نص مختار في تحليل التعمية التفاضلي . ومع حتى هذا يعتبر تحسينا أساسيا، ذلك لأنه من الأسهل الحصول على نصوص صريحة معروفة بدلا من نصوص صريحة مختارة، إلا حتى هذا العدد يبقى تحليل التعمية الخطي غير عملي لكسر خوارزمية DES. لذلك تم القيام بأعمال قليلة لتحقيق الكسر باستخدام تحليل التعمية الخطي.
استعراض
ليكن لدينا نظام تشفير ما، والذيقد يكون فيه طول النص الصريح هوn خانة، أما طول المفتاح فهوm خانة. ولنرمز لكتلة النص الصريح P[1] ..P [n] ، بينما نرمز لكتلة النص المشفر C [1]..C[n]، أما المفتاح فسيأخذ الرمز K[1]…K[m] ، لنعهد بعد ذلك ما يلي:
A[I, j…k] = A[i] ө A[j] ө …+ A[k]
انشاء المعادلات الخطية
يهدف تحليل التعمية الخطي إلى ايجاد معادلة خطية من الشكل:
P[α1, α2…. Αa] ө C[β1, β2….βb] = K[γ1, γ2 …γc]
(حيث X تساوي 0 أو1، 1≤C≤m، وحيث الرموز α وβ وγتمثل مواقع خانات منفردة وثابتة)، يجب حتى تكون هذه المعادلة محققة بالاحتمال P والذي لا يساوي 0.5. حدثا بعد P عن القيمة 0.5 حدثا كانت المعادلة أكثر كفاءة.
فاذا تم تحديد العلاقة المقترحة، عندها ستصبح الاجرائية هي حساب نتائج الطرف اليساري للمعادلة السابقة وذلك من أجل عدد كبير من أزواج النص الصريح-النص المشفر. اذا كانت النتيجة مساوية للصفر لأكثر من النصف عندها نفترض حتى K[γ1, γ2 .. γc] = 0. اذا كانت النتيجة مساوية للواحد معظم الوقت، عندها نفتراض حتى K[γ1, γ2 … γc] = 1. مما يعطينا معادلة خطية لحساب خانات المفتاح.
اشتقاق بـِتـّات المفتاح
Having obtained a linear approximation of the form:
انظر أيضاً
- Piling-up lemma
- Differential cryptanalysis
الهامش
وصلات خارجية
- A tutorial on linear (and differential) cryptanalysis of block ciphers
- "Improving the Time Complexity of Matsui's Linear Cryptanalysis", improves the complexity thanks to the Fast Fourier Transform
