تأثير الانهيار الجليدي

في علم التشفير ، يُعدّ تأثير الانهيار خاصية مرغوبة في خوارزميات التشفير ، وخاصةً تشفيرات الكتل ^{[ 1 ]} ودوال التجزئة التشفيرية ، حيث يؤدي تغيير بسيط في المدخلات (مثلاً، قلب بت واحد) إلى تغيير كبير في المخرجات (مثلاً، انقلاب نصف بتات المخرجات). في حالة تشفيرات الكتل عالية الجودة، يُفترض أن يُحدث هذا التغيير الطفيف في المفتاح أو النص الأصلي تغييراً جذرياً في النص المشفر . وقد استخدم هورست فيستل هذا المصطلح لأول مرة ^{[ 1 ]،} على الرغم من أن المفهوم يعود على الأقل إلى نظرية شانون .

إذا لم تُظهر خوارزمية التشفير الكتلي أو دالة التجزئة التشفيرية تأثير الانهيار بدرجة كبيرة، فإنها تعاني من ضعف في العشوائية، وبالتالي يستطيع محلل التشفير التنبؤ بالمدخلات بناءً على المخرجات فقط. قد يكون هذا كافيًا لتعطيل الخوارزمية جزئيًا أو كليًا. لذا، يُعد تأثير الانهيار شرطًا مرغوبًا فيه من وجهة نظر مصمم خوارزمية التشفير أو الجهاز. يؤدي إغفال هذه الخاصية إلى تعريض دالة التجزئة لهجمات تشمل هجمات التصادم ، وهجمات تمديد الطول ، وهجمات الصورة العكسية . ^{[ 2 ]}

يُعدّ بناء خوارزمية تشفير أو تجزئة تُظهر تأثيرًا تراكميًا كبيرًا أحد الأهداف التصميمية الرئيسية، ويستفيد هذا البناء رياضيًا من تأثير الفراشة . ^{[ 3 ]} ولهذا السبب، فإن معظم خوارزميات التشفير الكتلية هي خوارزميات تشفير ضربية . كما أن هذا هو السبب في احتواء دوال التجزئة على كتل بيانات كبيرة. تسمح هاتان الميزتان للتغييرات الصغيرة بالانتشار بسرعة عبر تكرارات الخوارزمية.

معيار الانهيار الصارم ( SAC ) هو صياغة رسمية لتأثير الانهيار. يتحقق هذا المعيار إذا تغيرت قيمة كل بت من بتات الإخراج باحتمالية 50% عند قلب بت واحد من بتات الإدخال. بتعبير أدق، يتحقق هذا المعيار إذا كان هناك احتمال بنسبة 50%، لجميع مواضع البتات i و j ، عند اختيار إدخال عشوائي X ، أن تختلف f ( X ) و f ( Xi ₎ عند الموضع j ، حيث Xi _هي X مع قلب البت الموجود في الموضع i . ^{[ 4 ]} يستند معيار الانهيار الصارم إلى مفهومي الاكتمال والانهيار ، وقد قدمه ويبستر وتافاريس عام 1985. ^{[ 5 ]}

يوجد في الأدبيات تعريف بديل واحد على الأقل لمعيار الانهيار الصارم. يُعرّف فون وبوروزاك المعيار بأنه مُتحقق إذا، عند اختيار مدخلين عشوائيين X و Y يختلفان في موضع واحد فقط، فإن مسافة هامينغ بين f ( X ⁾ و f ( Y ) تتوزع وفقًا للتوزيع ذي الحدين B( n , 1/2)، حيث n هو عدد البتات في X أو Y. ^{[ 6} ]

تتضمن التعميمات ذات الرتبة الأعلى لـ SAC بتات إدخال متعددة. الدوال المنطقية التي تحقق أعلى رتبة من SAC هي دائمًا دوال منحنية ، وتسمى أيضًا دوال غير خطية قصوى، أو دوال "غير خطية مثالية". ^{[ 7 ]}

ينص معيار استقلال البتات ( BIC ) على أنه يجب أن تتغير بتات الإخراج j و k بشكل مستقل عندما يتم عكس أي بت إدخال واحد i ، وذلك لجميع قيم i و j و k . ^{[ 8 ]}

• تأثير الفراشة
• الارتباك والتشتت