تحليل التعمية الخطي
تحليل التعمية الخطي 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:
