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

لأغراض التحليل الخطي للشفرات، تُعبّر المعادلة الخطية عن تساوي تعبيرين يتكونان من متغيرات ثنائية مُدمجة بعملية XOR (أو الحصرية). على سبيل المثال، تُبيّن المعادلة التالية، من شفرة افتراضية، مجموع XOR لأول وثالث بت من النص الأصلي (كما في كتلة شفرة الكتلة)، ويكون أول بت من النص المشفر مساويًا للبت الثاني من المفتاح:

${\displaystyle P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.}$

في التشفير المثالي، أي معادلة خطية تربط النص الأصلي والنص المشفر وبتات المفتاح ستكون صحيحة باحتمالية 1/2. وبما أن المعادلات التي يتم التعامل معها في التحليل الخطي للتشفير ستختلف في احتماليتها، فمن الأدق الإشارة إليها على أنها تقريبات خطية .

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

بعد الحصول على تقريب خطي بالشكل التالي:

${\displaystyle P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots }$

يمكننا بعد ذلك تطبيق خوارزمية مباشرة (خوارزمية ماتسوي 2)، باستخدام أزواج النص العادي والنص المشفر المعروفة، لتخمين قيم بتات المفتاح المشاركة في التقريب.

لكل مجموعة من قيم بتات المفتاح على الجانب الأيمن (يُشار إليها بالمفتاح الجزئي )، احسب عدد مرات صحة التقريب على جميع أزواج النص الأصلي والنص المشفر المعروفة؛ ولنسمِّ هذا العدد T. يُعتبر المفتاح الجزئي الذي يكون T الخاص به ذا أكبر فرق مطلق عن نصف عدد أزواج النص الأصلي والنص المشفر هو المجموعة الأكثر احتمالاً من قيم بتات المفتاح تلك. وذلك لأنه يُفترض أن المفتاح الجزئي الصحيح سيؤدي إلى صحة التقريب بانحياز عالٍ. يُعد مقدار الانحياز مهمًا هنا، على عكس مقدار الاحتمال نفسه.

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