شبكة الاستبدال والتباديل
في علم التشفير ، شبكة SP ، أو شبكة الاستبدال والتبديل ( SPN )، هي سلسلة من العمليات الرياضية المرتبطة المستخدمة في خوارزميات تشفير الكتل مثل AES (Rijndael) و 3-Way و Kalyna و Kuznyechik و PRESENT و SAFER و SHARK و Square .
تستقبل هذه الشبكة كتلة من النص الأصلي والمفتاح كمدخلات ، وتُطبّق عدة جولات أو طبقات متناوبة من صناديق الاستبدال (S-boxes) وصناديق التبديل (P-boxes) لإنتاج كتلة النص المشفر . تُحوّل صناديق الاستبدال والتبديل كتلًا (فرعية) من بتات الإدخال إلى بتات إخراج. من الشائع أن تكون هذه التحويلات عمليات فعّالة في التنفيذ على مستوى الأجهزة، مثل عملية XOR ( أو الحصرية) والتدوير على مستوى البت . يُضاف المفتاح في كل جولة، عادةً على شكل " مفاتيح جولة " مُشتقة منه. (في بعض التصاميم، تعتمد صناديق الاستبدال نفسها على المفتاح).
يتم فك التشفير ببساطة عن طريق عكس العملية (باستخدام معكوسات صناديق S وصناديق P وتطبيق مفاتيح الجولة بترتيب عكسي).
عناصر
يستبدل صندوق الاستبدال (S -box) مجموعة صغيرة من البتات (مدخلات صندوق الاستبدال) بمجموعة أخرى من البتات (مخرجات صندوق الاستبدال). يجب أن يكون هذا الاستبدال واحدًا لواحد لضمان إمكانية عكسه (وبالتالي فك التشفير). على وجه الخصوص، يجب أن يكون طول المخرجات مساويًا لطول المدخلات (يحتوي الشكل على اليمين على صناديق استبدال بأربعة بتات للمدخلات وأربعة بتات للمخرجات)، وهو ما يختلف عن صناديق الاستبدال بشكل عام التي يمكن أن يتغير طولها، كما هو الحال في معيار تشفير البيانات (DES) على سبيل المثال. عادةً لا يكون صندوق الاستبدال مجرد تبديل للبتات. بل في صندوق الاستبدال الجيد، يتأثر كل بت من بتات المخرجات بكل بت من بتات المدخلات. بتعبير أدق، في صندوق الاستبدال الجيد، يتغير كل بت من بتات المخرجات باحتمالية 50% عند تغيير كل بت من بتات المدخلات. وبما أن كل بت من بتات المخرجات يتغير باحتمالية 50%، فإن حوالي نصف بتات المخرجات ستتغير فعليًا عند تغيير بت من بتات المدخلات (انظر معيار الانهيار الصارم ). [ 1 ]
صندوق P هو عبارة عن تبديل لجميع البتات: فهو يأخذ مخرجات جميع صناديق S في جولة واحدة، ويبدل البتات، ثم يُدخلها إلى صناديق S في الجولة التالية. يتميز صندوق P الجيد بخاصية توزيع بتات مخرجات أي صندوق S على أكبر عدد ممكن من مدخلات صناديق S.
في كل جولة، يتم دمج مفتاح الجولة (الذي تم الحصول عليه من المفتاح ببعض العمليات البسيطة، على سبيل المثال، باستخدام صناديق S وصناديق P) باستخدام عملية مجموعة معينة، عادةً XOR .
ملكيات
لا يمتلك صندوق الاستبدال (S-box) أو صندوق التعميم (P-box) النموذجي وحده قوة تشفيرية كبيرة: يمكن اعتبار صندوق الاستبدال بمثابة تشفير استبدال ، بينما يمكن اعتبار صندوق التعميم بمثابة تشفير تبديل . ومع ذلك، فإن شبكة SP المصممة جيدًا والتي تتضمن عدة جولات متناوبة من صناديق الاستبدال والتعميم تُحقق بالفعل خصائص التشويش والانتشار لشانون .
- يكمن سبب الانتشار فيما يلي: عند تغيير بت واحد من النص الأصلي، يُغذى هذا النص إلى صندوق استبدال (S-box)، الذي تتغير مخرجاته عند عدة بتات. ثم يقوم صندوق معالجة (P-box) بتوزيع هذه التغييرات على عدة صناديق استبدال، وبالتالي تتغير مخرجات هذه الصناديق عند عدة بتات، وهكذا. مع تكرار هذه العملية عدة مرات، يتغير كل بت ذهابًا وإيابًا، مما يؤدي في النهاية إلى تغيير النص المشفر بالكامل بطريقة شبه عشوائية . على وجه الخصوص، بالنسبة لكتلة إدخال مختارة عشوائيًا، إذا تم قلب البت رقم i ، فإن احتمال تغير البت رقم j في المخرجات يساوي تقريبًا النصف، لأي قيمتين i و j ، وهو ما يُعرف بمعيار الانهيار الصارم . على العكس من ذلك، إذا تم تغيير بت واحد من النص المشفر ثم محاولة فك تشفيره، ستكون النتيجة رسالة مختلفة تمامًا عن النص الأصلي - إذ يصعب تغيير تشفيرات SP .
- إن سبب الارتباك هو نفسه تمامًا كما هو الحال بالنسبة للانتشار: تغيير بت واحد من المفتاح يغير العديد من مفاتيح الجولة، وكل تغيير في كل مفتاح جولة ينتشر على جميع البتات، مما يغير النص المشفر بطريقة معقدة للغاية.
- إذا تمكن المهاجم بطريقة ما من الحصول على نص عادي واحد يتوافق مع نص مشفر واحد - هجوم النص العادي المعروف ، أو الأسوأ من ذلك، هجوم النص العادي المختار أو هجوم النص المشفر المختار - فإن الارتباك والانتشار يجعلان من الصعب على المهاجم استعادة المفتاح.
أداء
على الرغم من أن شبكة فيستل التي تستخدم صناديق الاستبدال (مثل DES ) تشبه إلى حد كبير شبكات SP، إلا أن هناك بعض الاختلافات التي تجعل إحداهما أكثر ملاءمة في حالات معينة. فبالنسبة لمستوى معين من التشويش والانتشار ، تتمتع شبكة SP بقدر أكبر من "التوازي المتأصل" [ 2 ] ، وبالتالي - مع وحدة معالجة مركزية ذات وحدات تنفيذ متعددة - يمكن حسابها بشكل أسرع من شبكة فيستل. [ 3 ] أما وحدات المعالجة المركزية ذات وحدات التنفيذ القليلة - مثل معظم البطاقات الذكية - فلا يمكنها الاستفادة من هذا التوازي المتأصل. كما تتطلب خوارزميات تشفير SP أن تكون صناديق الاستبدال قابلة للعكس (لإجراء فك التشفير)؛ بينما لا تخضع الدوال الداخلية لشبكة فيستل لهذا القيد، ويمكن بناؤها كدوال أحادية الاتجاه .
انظر أيضاً
مراجع
- ↑ ويبستر، أ. ف.؛ تافاريس، ستافورد إي. (1985). "حول تصميم صناديق الاستبدال". التطورات في علم التشفير - كريبتو 85. سلسلة محاضرات في علوم الحاسوب. المجلد 218. نيويورك، نيويورك: سبرينغر-فيرلاغ نيويورك، ص 523-534 . ISBN 0-387-16463-4.
- ↑ "مبادئ وأداء الخوارزميات المشفرة" بقلم بارت برينيل، وفينسنت ريجمان، وأنتون بوسيلرز.
- ↑ "عائلة وظائف التجزئة Skein" مؤرشفة في 2009-01-15 في Wayback Machine 2008 بواسطة Niels Ferguson و Stefan Lucks و Bruce Schneier و Doug Whiting و Mihir Bellare و Tadayoshi Kohno و Jon Callas و Jesse Walker صفحة 40.
للمزيد من القراءة
- كاتز، جوناثان؛ ليندل، يهودا (2007). مقدمة في علم التشفير الحديث . مطبعة سي آر سي. رقم ISBN 9781584885511.
- ستينسون، دوغلاس ر. (2006). التشفير: النظرية والتطبيق ( الطبعة الثالثة). تشابمان آند هول/سي آر سي. رقم ISBN 1584885084.
- الخوارزميات التشفيرية
- تشفير الكتل
- التباديل