معيار تشفير المعطيات Data Encryption Standard-DES هوالتشفير المتناظر الأكثر استخداماً. ومع أنه تم الاتفاق على استبدال هذه الخوارزمية بخوارزمية "مقياس التشفير المتقدم " (Advanced Encryption Sartndard-AES) بقيت خوارزمية DES الأكثر أهمية بين الخوارزميات المتشابهة. بالاضافة إلى ما تم ذكرة تعتبر دراسة خوارزمية DES بشكل مشروح الأساس لفهم المبادئ المستخدمة في الشتفير المتناظر. سنقوم في الفصولخمسة و6 بدراسة مجموعة طرق التشفير المتناظر الهامة بما في ذلك AES.

تعتبر خوارزمية DES ومعظم خوارزميات التشفير المتناظر معقدة جدا، اذا ما قورنت بخوارزميات المفتاح العمومي مثل RSA، وبالتالي لا يمكن شرحها ببساطة كما هي الحال في خواركية RSA والخوارزميات المتشابهة. لذلك سنبدأ بنسخة مبسطة للخوارزمية DES. تسمح هذه النسخة للقارئ باجراء عمليتي التعمية وفك التعمية يدويات وذلك من أجل اكتساب الفهم الجيد لكيفية عمل هذه الخوارزمية. وقد دلت خبرات التدريس على حتى الفهم الجيد لهذه النسخة المبسطة يحسن ويسهل فهم خوارزمية DES.

يبحث هذا الكتاب، بعد مناقشة النسخة المبسطة من DES، في المبادئ العامة للتشفير الكتلي المتناظر ، والذي يمثل نوع التشفير المتناظر الذي سيتم بحثه في هذا الكتاب (ماعدا التشفير التسلسلي RCS المطروح في الفصل السادس). ثم ينتقل الكتاب بعد ذلك إلى عرض خوارزمية DES الكاملة. يعود الكتاب، بعد مناقشة هذه الخوارزمية الخاصة، إلى مناقشة عامة لتصميم أنظمة التشفير الكلي.

خوارزمية DES المبسطة

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

نظرة عامة

يوضح الشكل 3-1 البنية العامة للخوارزمية S- DES . ولج خوارزمية التعمية S- DES، هوكتلة ذات ثماني خانات من النص الصريح (على سبيل المثال 10111101)، بالإضافة إلى مفتاح بطول عشر خانات. أما خرجها فهوتعبير عن كتلة من النص المشفر بطول ثماني خانات أيضا. أما خوارزمية S- DES لفك التعمية فهي تأخذ كتلة من النص المشفر بطول ثماني خانات بالاضافة إلى نفس المفتاح ذي العشر خانات لتعطي كتلة ذات طول ثماني خانات من النص الصريح.

تتضمن خوارزمية التعمية خمسة توابع: التبديل الأولي للمواقع (IP)؛ وظيفة معقدة باسم Fk، والتي تتضمن عمليتي تبديل أحرف وتبديل مواضع معتمدتين على المفتاح، عملية تبديل مواقع بسيطة (SW)، تقوم بتبديل مواقع نصفي المعطيات بين بعضها بعض، ثم الوظيفة Fk مرة أخرى، وأخيرا وظيفة تبديل المواقع التي تعاكس عملية التبديل الأولى للمواقع والتي يشار إليها بالرمز (IP-1). تؤدي المراحل المتعددة في عمليات تبديل الحروف وتبديل المواقع، كما أشرنا في الفصل الثاني، إلى انتاج خوارزميات معقدة، تزيد الصعوبات أمام محللي التشفير.

دخل التابع Fk، هوكتلة خانات المعطيات المراد تشفيرها (بعد مرورها بالتابع IP) بالاضافة إلى ثماني خانات من المفتاح. كان من الممكن تصميم الخوارزمية لتعمل مع مفتاح بطول ستة عشرة خانة، بحيث يتم تقسيمه إلى مفتاحين جزئيين طول جميع منهما ثماني خانات. وبحيث يتم استخدام جميع جزء مع إحدى الوظائف Fk المكررة في الخوارزمية. يمكن عوضا عن ذلك استخدام مفتاح وحيد بطولثمانية خانات بحيث يستخدم نفسه مرتين في الخوارزمية. الحل الأمثل هواستخدام مفتاح بطولعشرة خانات، بحيث يتم توليد مفتاحين منه طول جميع منهماثمانية خانات وذلك كما هومشروح في الشكل 3-1. وفي هذه الحالة يطبق على المفتاح تابع تبديل المواضع P10 والذي سينتج خرجا ذوثماني خانات هوالمفتاح الأول K1. كذلك يطبق خرج عملية الازاحة على عملية ازاحة أخرى ومن ثم على عملية تبديل المواقع P8، لانتاج المفتاح الثاني K2 ذوالثماني خانات.

{{{{الشكل 3-1: مخطط خوارزمية DES المبسطة

يمكن التعبير عن خوارزمية التعمية باختصار كهجريب للتوابع كما يلي:

IP-1 o fk2oSWk1oIP والذي يمكن كتابته أيضا كما يلي:

Ciphertext = IP-1 (fk2 (SW(fk1(IP(plaintext))))

حيث: K1=P8 (shift(P10(Key))) K2= P8(Shift(shift(P10(key))))

يبين الشكل 3-1 أيضا عملية فك التعمية والذي يعتبر بشكل مبدئي عكس عملية التشفير:

Plaintext – (IP-1(fk1(SW(fk2(IP(ciphertext))))

سنقوم الآن بدراسة عناصر خوارزمية S-DES بالتفصيل.

توليد مفاتيح الخوارزمية S-DES

تعتمد خوارزمية S-DES على استخدام مفتاح مشهجر بين المرسل والمستقبل بطول عشرة خانات. يتم انتاج مفتاحين جزئيين من هذا المفتاح، طول جميع واحد ثماني خانات وذلك لاستخدامهما في المراحل المتنوعة من خوارزمية التشفير وفك التشفير. يوضح الشكل 3-2 المراحل المتبعة لانتاج المفاتيح الجزئية.

تقوم المستوى الأولى بعملية تبديل مواقع خانات المفتاح بالكيفية التالي. لنعطي خانات المفتاح العشر رموزا كما يلي P10(K1,K2,K3,K4,K4,K5,K6,K7,K8,K9,K10)

يمكن التعبير عن التابع P10 باختصار في الشكل التالي:

P10 9 8 9 1 10 4 7 2 2 5 3

يقرأ هذا الجدول من اليسار إلى اليمين، حيث يعبر محتوى جميع موضع في الجدول عن هوية خانة الدخل التي ستعطي خانة الخرج في هذا الموضع. وبالتالي خانة الخرج الأولى ستكون هي خانة الدخل الثالثة، وخانة الخرج الثانية ستكون هي خانة الدخل الخامسة.. إلى غير ذلك. عملى سبيل الثمال اذا كان مفتاح الدخل هو(1010000010) فان خرج تابع تبديل المواضع P10 سيكون الخمس خانات الأولى والخمس خانات الثانية من خرج عملية تبديل المواقع P10 بشكل مستقل وبالتالي فإن خرج هذه العملية سيكون (000001 11000).

نقوم بعد ذلك بتطبيق تابع تبديل المواضع P8 والذي يقوم بانتخاب وتبديل مواقع ثماني خانات من أصل عشرة وذلك حسب القاعدة التالية:

P8 9 10 5 8 4 7 3 6

وستكون النتيجة هي المفتاح الجزئي الأول k1 وفي مثالنا يفترض أن ينتج (10100100).

نعود بعد ذلك إلى زوج السلاسل المؤلفة من خمس خانات الناتجة عن عمليتي الازاحة SL-1 ونطبق عليهما عمليتي ازاحة دوارنيتين بمقادر خانتين لكل منهما، وهوما يعبر عنه بالتوابع SL-2 في الشكل 3-2. ستكون النتيجة في مثالنا هي (0010000011). نقوم أخيرا بتطبيق تابع تبديل المواقع P8 نفسه على الناتج للحصول على المفتاح الجزئي الثاني K2، والذي سيكون في مثالنا (001000011).

{{{الشكل 3-2:توليد المفاتيح في خوارزمية DES المبسطة

التعمية حسب خوارزمية S-DES

يبين الشكل 3-2 خوارزمية التعمية S-DES بالتفصيل. تتألف عملية التعمية، كما ذكرنا سابقا، من تطبيق متسلسل لخمسة توابع. سندرس جميع من هذه التوابع بشكل مستقل.

{{{الشكل 3-3: مخطط تفصيلي للتعمية وفق خوارزمية S-DES

تبديلات المواقع البدائية والنهائية

يتألف ولج الخوارزمية من كتلة من معطيات الدخل بطول ثماني خانات، والتي يطبق عليها تابع تبديل المواقع IP التالي:

IP 7 5 8 4 1 3 6 2

من الواضح حتى خرج هذا التابع هونفس خانات الدخل ولكن بعد تبديل مواقعها، ولذلك نرى أنه سيتم تطبيق التابع IP-1 لعكس هذا الترتيب في نهاية الخوارزمية.

IP-1 6 8 2 7 5 3 1 4

يمكن ببساطة عن طريق مثال توضيح حتى عملية تبديل المواقع التالية هي في الحقيقة عكس عملية الترتيب الأولى تماما، أي حتى IP-1 (IP (x))=x

التابع fk

يعتبر التابع fk العنصر الأكثر تعقيدا بينا عناصر الخوارزمية S-DES ، حيث يتألف من مجموعة توابع تبديل المواقع وتبديل الحروف. يمكن وصف هذا التابع كما يلي: لنفرض حتى L وR هي تعبير عن الخانات الأربع اليسارية والخانات الأربع اليمينية من الدخل المؤلف من ثماني خانات للتابع fk على الترتيب، ولنفرض حتى F هي تعبير عن عملية تحويل من سلسلة ذات أربع خانات إلى سلسلة أخرى ذات أربع خانات أيضا (ليس بالضرورة حتىقد يكون التحويل واحدا واحدا). عندها يمكن حتى نخط :

Fk (L,R) = (L ө F(R, SK),R

حيث حتى SK هوتعبير عن المفتاح الجزئي، وөهي تعبير عن عملية PR القسرية Exclusive-OR) المطبقة على مستوى الخانة. لنفرض على سبيل المثال حتى خرج الفترة IP في الشكل 3-3 هو(10111101) وأن F(1101, SK) = (1110) من أجل SK ما، عندها سيكون fK (10111101) = (0101 1101) وذلك لأن (1011) ө (1110) = (0101).

سنقوم الآن بشرح عملية التحويل F. ولج هذه العملية هوتعبير عن رقم من أربع خانات (n1 n2 n3 n4). المستوى الأولى في هذا التحويل هي تعبير عن عملية توسيع وتبديل مواقع كما هومبين فيما يلي:

E/P 1 4 3 2 3 2 1 4

من الأفضل كتابة هذه المستوى كما يلي وذلك للاستفادة منه لاحقا:

n3 n2 n1 n4 n1 n4 n3 n2

تتم بعد ذلك اضافة المفتاح الجزئي ذوالثماني خانات k1= (k11,k12,k13,k14,k15,k16,k17,k18) إلى القيمة السابقة باستخدام XOR: n3+ k14 n2+ k13 n1+ k12 n4+ k11 n1+k18 n4+k17 n3+ k16 n2+ k15

لنقم الآن باعادة تسمية هذه الخانات الثمانية:

P0.3 P0.2 P0.1 P0.0 P1.3 P1.2 n3 P1.0

يتم ادخال الأربع خانات الأولى (السطر الأول في المصفوفة السابقة) إلى صندوق S المسمى SO لانتاج خانتي خرج، كذلك يتم إدخال الأربع خانات الباقية (السطر الثاني) إلى الصندوق S1 لإنتاج خانتي خرج أيضا. تعهد هذه الصناديق كما يلي:

{{{شكل الصناديق

تعمل صناديق S كما يلي: تعامل خانتا الدخل الأولى والرابعة كعدد واحد مؤلف من خانتين لتحديد رقم السطر في الصندوق S، بينما تحدد الخانتان الثانية والثالثة رقم العمود في نفس الصندوق. يعتبر الرقم الواقع في تقاطع السطر والعمود المحددان خرج الصندوق بعد تمثيله ثنائيا وبخانتين فقط. عملى سبيل المثال اذا كان (P0.0 P0.3) = (00) وكان (P0.1 P0.2) = (10) عندها سيتم الحصول على الخرج من السطر رقم 0 والعمود رقم 2 من الصندوق S0، أي سيكون الخرج هوثلاثة أو2(11) . تستخدم الخانات (P11 P12) = (P10 P13) لتحديد السطر والعمود في صندوق S1 وبالتالي الحصول على خانتي خرج إضافيتين.

يتم بعد ذلك تطبيق عملية تبديل مواقع على الخانات الأربع الناتجة من الصناديق S0 وS1 كما يلي:

P4 1 3 4 2

تابع التبديل

قام التابع fk بتبديل الخانات الأربع اليسارية فقط. لذلك يقوم تابع التبديل (SW) بتبديل الأربع خانات اليسارية مع الأربع خانات اليمينية وذلك كي يعالج التابع fk، والذي سيتم تطبيقه مرة أخرى على الخانات الأربع التالية. في الفترة الثانية يتم تكرار تطبيق التوابع P4, S1, S0, E/P ذاتها ، غير حتى المفتاح في هذه الفترة سيكون k2.

تحليل خوارزمية DES المبسطة

يعتبر كسر خوارزمية DES المبسطة بالتجريب محققا حتما. فعندماقد يكون طول المفتاح عشر خانات فإنه يوجد 210 = 1024 احتمالا فقط. فاذا كان لدينا نص مشفر ما، عندها يمكن تجريب جميع حالة من حالات المفتاح وتحليل النتيجة لفهم فيما اذا كان النص الناتج مقروءا أم لا.

ماذا عن تحليل التعمية،يا ترى؟ لنفرض حالة الهجوم على نص صريح معروف، حيث لدينا نص صريح واحد معروف هو(P1,P2, P3. P4, P5, P6, P7, P8) والنص المشفر المرافق له معروف أيضا وهو(c1,c2,c3,c4,c5,c6,c7,c8)أما المفتاح (k1,k2,k3,k4,k5,k6,k7,k8,k9k,k10) فهوغير معروف. يمكن في هذه الحالة وصف جميع c1 على شكل تابع كثير حدود g1 للمعاملات k1, p1. يمكن بهذا الشكل التعبير عن عملية التعمية بثماني معادلات غير خطية ذات عشرة مجاهيل. هناك عدد من الحلول المحتملة، ولكن يجب حساب جميع منها وتحليله. إذا عمليتي تبديل المواقع والاضافة هما عمليتان خطيتان في الخوارزمية. وتأتي عدم الخطية من الصناديق s. لذلك من المفيد كتابة المعادلات التي تصف هذه الصناديق. وللتوضيح فقط سنقوم بتغير تسمية المتحولات لتصبح كما يلي: (P0.0, P0.1, P0.2, P0.3) = (a, b, c, d) و(P1.0, P1.1, P1.2, P1.3) = (w, x,y, z) وسنسمي الخرج ذا الأربع خانات (q, r, s, t). عندها يمكن وصف العملية S0 بالمعادلات التالية:

Q = abcd + ab +ac + b +d R = abcd +abd + ab + ac + a + c +1

حيث تتم جميع عمليات الجمع بالقياس 2. يمكن بنفس الطريقة كتابة المعادلات التي تصف S1. استبدال هذه المعادلات غير الخطية بتحويلات خطية سينتج تعابير كثيرات حدود معقدة جدا، مما يجعل عملية تحليل التعمية صعبة جدا. ولتوضيح المشكلة يجب ملاحظة حتى للمعادلات كثيرة الحدود بعشرة مجاهيل في الحسابات الثنائية 210 حدا محتملا. وبشكل وسطي يمكن حتى نتسقط لكل معادلة من المعادلات الثماني حوالي 29 حدا. يمكن للقارئ المهتم حتى يجرب وضع هذه المعادلات باستخدام أي معالج رموز ومن المؤكد حتى القارئ أوالبرنامج سيتسلم قبل المضي طويلا في المعالجة.

الارتباط بخوارزمية DES

تتعامل خوارزمية DES مع كتلة ولج بطول 64 خانة، يمكن التعبير عن مخطط التعمية كما يلي: IP -1 ofk16 ofk15 oSW …….oSW ofx1oIP

يستخدم مع هذه الخوارزمية مفتاح بطول 56 خانة، حيث يتم توليد 16 مفتاحا فرعيا منه طول جميع منها 48 خانة. هناك عملية تبديل مواقع أولية ل56 خانة، تتبع بسلسلة من عمليات الازاحة وتبديل المواقع ل48 خانة.

يتم الاستعاضة ضمن خوارزمية التعمية عن التابع F الذي يؤثر على أربعة خانات (n1, n2,n3,n4) بآخر يتعامل مع 32 خانة (n1,n2,n3 …n32). يمكن بعد عملية توسيع/تبديل المواقع الأولية التعبير عن الخرج ذي الثماني والأربعين خانة بالشكل:

{{{شكل توضيحي

تتم اضافة هذه المصفوفة بواسطة (XOR) إلى المفتاح الفرعي ذوالثماني والأربعين خانة. هناك ثمانية أسطر موافقة لثمانية صناديق S. لكل صندوق S أربعة أسطر وستة عشر عمودا. الخانتان الأولى والأخيرة من أسطر المصفوفة السابقة تحددان رقم السطر في الصندوق S، بينما تحدد الخانات الأربع في الوسط رقم العمود في هذا الصندوق.

مبادئ التشفير الكتلي

تعتمد جميع خوارزميات التشفير الكتلي المتناظر المستخدمة حاليا على البنية المسماة تشفير فسيتيل الكتلي (Feistel Black Cipher) . لذلك من الضروري دراسة مبادئ تشفير فيستيل. سنبدأ هذه الدراسة بمقارنة بين التشفير الكتلي والتشفير التسلسلي. سندرس بعد ذلك الدوافع وراء تشفير فيستيل، ومن ثم ننتقل إلى بعض ما يتضمنه هذا التشفير.

التشفير التسلسلي والتشفير الكتلي

التشفير السيلي هوذاك النوع من التشفير الذي يقوم بتعمية سيالة من المعطيات الرقمية بشكل تسلسلي، بحيث تتم تعمية خانة واحدة أوثمانية واحدة (byte) في جميع لحظة زمنية. من أبرز الأمثلة الكلاسيكية على التشفير التلسلي يمكن حتى نذكر تشفير فيجينر وتشفير فيرنام. أما في التشفير الكلي فتتم معالجة كتلة من النص الصريح كوحدة متكاملة بحيث تنتج كتلة من النص المشفر مساوية لها في الطول. طول الكتلة القياسية المستخدمة هو64 خانة أو128 خانة. يمكن باستخدام بعض أنماط العمل الخاصة، التي سيتم توضيحها لاحقا، جعل التشفير الكتلي يعطي نفس تأثير التشفير التسلسلي.

لقد انصبت الجهود بشكل أساسي على تطوير التشفير الكتلي، ويعود السبب في ذلك إلى المجال الأكبر للتطبيقات التي يمكن حتى تستخدم هذا النوع من التشفير. معظم تطبيقات التعمية المتناظرة الخاصة بالشبكات تستخدم التشفير الكتلي. نتيجة لما تجاوز سنركز في هذا الفصل على التشفير الكتلي وفي فوصل الكتاب الآتية الخاصة بالتعمية المتناظرة.

الدوافع لبنية تشفير فيستيل

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

تحويل معكوس النص الصريح النص المشفر 00 11 01 10 10 00 11 01

تحويل غير معكوس النص الصريح النص المشفر 00 11 01 10 10 01 11 01

نلاحظ في الحالة الأخيرة أنه يمكن إنتاج الشفرة 01 من إحدى كتلتي نص صريح متباينتين، لذلك لا يمكن اعتبار هذا النوع من التحويل عكوس، أي إذا كان لدينا النص المشفر 01 فلا يمكن فهم النص الصريح المرتبط به بدقة.

يوضح الشكل 3-4 منطق التشفير بتبديل الحروف عموما، ولذلك من أجل n=4. يمكن للدخل المؤلف من أربع خانات حتى يأخذ ست عشرة حالة ولج ممكنة، والتي يمكن ربطها عن طريق التشفير بتبديل الحروف بست عشرة حالة خرج فريدة، بحيث يمكن تمثيل جميع منها بأربع خانات من النص المشفر. يمكن وصف تحويلات التعمية وفك التعمية بالجداول كما هومبين في الجدول 3-1. تعتبر هذه الحالة الشكل الأكثر عمومية للتشفير الكتلي والذي يمكن استخدامه لتعريف أي عملية تحويل عكوسة بين النص الصريح والنص المعمى.

هناك معضلة عملية مرتبطة بهذه الطريقة. إذا تم استخدام كتلة صغيرة نسبيا، مثل n=4 عندها سيكافئ هذا النظام التشفير التقليدي بتبديل الحروف والذي يعتبر ضعيفا تجاه التحليل الاحصائي. لا تنتج نقطة الضعف هذه نتيجة استخدام التشفير "تبديل الحروف" ، إنما تنتج من استخدام كتلة صغيرة الحجم نسبيا. أما اذا كان "كبير بشكل كاف وكان بالامكان تغيير قاعدة التحويل بين النص الصريح والنص المشفر، عندها ستضيع الخصائص الاحصائية للنص الصريح وسيصبح كسر التعمية بهذه الطريقة غير فعال.

{{{{الشكل 3-4: عملية تبديل حروف عامة n خانة n- (n-4)

يعتبر التشفير بتبديل الحروف، عندماقد يكون حجم الكتلة كبيرا وعندما يمكن تغيير قاعدة التحويل بشكل حر غير عملي من وجخة نظر التطبيق والآداء معا. حيث تعتبر عملية التحويل في هذه الحالة هي بحد ذاتها مفتاح التعمية. لننظر مرة أخرى إلى الجدول 3-1 والذي يعهد عملية تحويل عكوسة من النص الصريح إلى النص المشفر وذلك من أجل n=4. يتم تعريف التحويل عن طريق مداخل أوخلايا العمود الثاني والتي تبين قيم النص المشفر المرافقة لكل كتلة ممكنة من النص الصريح وهذا في الجوهر هوالمفتاح الذي يحدد عملية تحويل ما من بين جميع عمليات التحويل الممكنة. يحتاج المفتاح في هذه الحالة 64 خانة. وبشكل عام من أجل التشفير الكتلي بتبديل الحروف وبطول n خانة،قد يكون طول المفتاح هوn X 2n. فمن أجل كتلة بطول 64 خانة (وهي الحالة المطلوبة لمقاومة الكسر بطريقة الاحصاء) سيكون طول المفتاح هو64 X 264 = 270 = 1021.

الجدول 3-1 جداول التعمية وفك التعمية من أجل التشفير بتبديل الحروف الواردة في الشكل 3-4

{{{{{جدول 3-1

أخذ فيستيل هذه الصعوبات بعين الاعتبار، وأشار إلى حتى المطلوب هوالاقتراب من نظام التشفير الكتلي المثالي ذوعدد الخانات n الكبير نسبيا، والذي يجب بناؤه من مجموعة من العناصر سهلة التحقيق. ولكن قبل الانتنطق إلى طريقة فيستيل لابد من وضع ملاحظة أخرى. يمكننا تقييد أنفسنا بهذا التشفير العام بتبديل الحروف لكن، لجعل عملية التطبيق ممكنة، سنقيد أنفسنا بمجموعة جزئية من احتمالات التحويل العكوسة والتي عددها 2n، لنفرض على سبيل المثال، أننا حددنا التحويل على شكل مجموعة من المعادلات الخطية. فعندماقد يكون n=4 سيكون لدينا:

Y1 = k11 x1 + k12 x2 + k 13 x3 + k14 x4 Y2 = k21 x1 + k22 x2 + k23 x3 + k24 x4 Y3 = k31 x1 + k32 x2 + k33 x3 + k34 x4 Y4= k412 x1 + k42 x2 + k43 x3 + k44 x4

حيث حتى x1 هي الخانات الأربع لكتلة النص الصريح، وy1 هي الخانات الأربع لكتلة النص المشفر، أما kij فهي تعبير عن معاملات ثنائية، فهما بأن جميع العمليات الحسابية تجرى بالقياس 2. طول المفتاح هوn2 فقط، وفي هذه الحالة سيكون 16 خانة.

تنبع خطورة هذا النوع من التشكيل من الضعف تجاه تحليل التعمية من قبل مهاجم لدية معلومات عن بنية الخوارزمية. ما لدينا في هذا المثال هوفي الحقيقة تشفير هيل الذي تمت مناقشته في الفصل الثاني، ولكن مطبق على معلومات ثنائية بدلا من الحروف. وكما رأينا في الفصل الثاني هذا النظام الخطي ضعيف جدا تجاه الكسر.

تشفير فيستيل

اقترح فيستيل أنه يمكن تطوير تشفير تبديل الحروف البسيط عن طريق تطبيق مفهوم ضرب التشفير، حيث يمكن تطبيق تشفيرين متتالين أوأكثر بحيث تكون النتيجة النهائية، من وجهة نظر التعمية، أقوى من أي من مركباتها. وفي الحقيقة ما لدينا هوتعبير عن تطبيق عملي لمقترح كلاود شانون (claude Shannon) بانتاج تشفير مؤلف من تعاقب تابعي البعثرة والنشر (Confusion and Dissusion).

سنلقي نظرة على هذين المفهومين ومن ثم نتابع شرح تشفير فيستيل. لكن أولا من الجدير التعليق على الحقيقة التالية: معظم بنى أنظمة التشفير الكتلي المتناظر الهامة والمستخدمة في هذه الأيام مبنية على أساس بنية نظام تشفير فيستيل، الذي يعود لحوالي ربع قرن ماضي والمبني على أساس اقتراح شينون عام 1945.

النشر والبعثرة

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

بالاضافة إلى الاستعانة بالنظام المثالي، اقترح شانون طريقتين لاحباط تحليل التعمية الاحصائي: النشر والبعثرة. في النشر يتم تشتيت البنية الاحصائية للنص الصريح في مجال طويل من احصائيات النص المشفر، يمكن انجاز ذلك عن طريق تاثير جميع رقم من النص الصريح على قيم عدة أرقام من النص المشفر، أوما يكافئ القول بأن جميع من النص المشفر يتم التاثير عليه من قبل عدة أرقام من النص الصريح. والمثال على عملية النشر هوتشفير رسالة ما من المحارف M= m1, m2, m3 … عن طريق عملية المعدل الوسطي كما يلي:

{{{{معادلة يجب حتى تصور

أي باضافة k حرف متتالي للحصول على حرف مشفر واحد yn. يمكن تبيان كيف من الممكن أن تمت ازالة البنية الاحصائية للنص الصريح. أي حتى تردداد ظهور الحروف في النص المشفر ستكون متقاربة. كذلك الأمر بالنسبة لتردد ظهور الثنائيات .. إلى غير ذلك. يمكن في التشفير الكتلي الثنائي انجاز عملية النشر عن طريق القيام بعملية تبديل مواقع متكررة للمعطيات ومن ثم تطبيق تابع ما على هذا التبديل. وفي النهاية سيكون التاثير الحاصل هوتأثير خانات من مواقع مختلفة من النص الصريح على خانة واحدة من النص المشفر.

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

وبالتالي، حتى لواستطاع المهاجم تجميع معلومات احصائية معينة حول النص المشفر، فإنه لن يستطيع تخمين المفتاح المستخدم بسبب تعقيد طريقة استخدام المفتاح لانتاج النص المشفر. يتم انجاز ذلك عن طريق خوارزمية تبديل حروف معقدة.

تعتبر عملية النشر والبعثرة الناجحة جوهر عملية التشفير الكتلي والتي أصبحت حجر الأساس في تصميم نظم التشفير الكتلي الحديثة.

بنية نظام تشفير فيستيل

يبين الشكل 3-5 البنية المقترحة من قبل فيستيل. ولج خوارزمية التشفير هوتعبير عن كتلة من النص الصريح بطول 2w والمفتاح k. يتم تقسيم كتلة النص الصريح إلى نصفين L0 وR0. يمر هذا النصفان من خلال n حلقة معالجة ومن ثم يتم ضمهمها لانتاج كتلة النص المشفر. ولج الحلقة i هوLi-1 وRi-1 الناتجين من الحلقة السابقة بالاضافة إلى المفتاح الجزئي k1 الناتج من المفتاح الأساسي k. المفاتيح الجزئية ki مختلفة بشكل عام عن المفتاح الاساسي k وعن بعضها البعض.

{{{{الشكل 3-5: شبكة فيستيل التقليدية

تملك جميع الحلقات نفس البنية تماما. يتم تطبيق عملية تبديل الحروف على النصف اليساري من المعطيات، وذلك عن طريق تطبيق تابع الحلقة F على النصف الأيمن من المعطيات. ومن ثم جمع ناتج هذا التابع مع القسم الأيسر من المعطيات بواسطة عملية XOR. يملك تابع الحلقة F نفس البنية في جميع الحلقات، إلا أنه يتم تحديد عوامله بالمفتاح الجزئي k1 الخاص بكل حلقة. بعد عملية تبديل الحروف المشروحة أعلاه تنفذ عملية تبديل مواقع والتي تتكون من تبديل نصفي المعطيات فيما بينهما. تعتبر هذه البنية حالة خاصة من شبكة تبديل الحروف – تبديل المواقع (substitution-permutation network-SPN) المقترحة من قبل شانون.

يعتمد التطبيق الحقيقي لشبكة فيستيل على اختيار المعاملات وخصائص التصميم التالية: • طول الكتلة: حدثا كانت الكتلة أطول كان مستوى الأمن أكبر (ومع الاحتفاظ ببقية الأمور كما هي) ولكن ذلك على حساب سرعة عمليتي التعمية وفك التعمية. يعتبر الطول 64 خانة معقولا وقد أصبح قياسا معتمدا تقريبا في تصميم نظام التشفير. على جميع الأحوال طول الكتلة في خوارزمية AES الجديدة هو128 خانة. • طول المفتاح: المفتاح الأطول يعني مستوى أمن أكبر ولكن سرعة تعمية وفك تعمية أقل. تعتبر المفاتيح ذات الطول 64 خانة أوأقل غير كافية حاليا. وبشكل عام تم اعتماد المفتاح ذوالطول 128 خانة. • عدد الحلقات: يعتمد جوهر نظام تشفير فيستيل على حتى الحلقة الواحدة لا تعطي مستوى أمن كافي، غير حتى تعدد الحلقات يزيد من مستوى الأمن. عدد الحلقات القياسي هو16. • خوارزمية توليد المفاتيح الجزئية: تؤدي زيادة تعقيد هذه الخوارزمية إلى زيادة الصعوبات أمام تحليل التعمية. • تابع الحلقة F: من الواضح أنه حدثا زاد تعقيد هذا التابع زادت المقاومة ضد تحليل التعمية.

هناك أيضا اعتباران آخران أثناء تصميم نظام تشفير فيستيل: • برمجيات تعمية/فك تعمية سريعة: يتم في كثير من الأحيان تضمين التعمية في التطبيقات والوظائف الخدمية ، ومن الممكن حتى يتم تحقيق ذلك جهازيا، لذلك تلعب سرعة التطبيق دورا هاما جدا. • سهولة التحليل: مع أننا نسعى لأن تكون خوارزميتنا صعبة قدر المستطاع ضد تحليل التعمية، إلا أنه من المفيد جدا جعل الخوارزمية سهلة التحليل. ذلك لأنه اذا كان بالامكان شرح الخوارزمية بسهولة وبوضوح، فإنه من السهل تحليل الخوارزمية وايجاد نقاط الضعف، وبالتالي تطويرها للحصول على مستوى أمن أعلى. لا يمكن تحليل عمل خوارزمية DES على سبيل المثال بسهولة.

بالرجوع إلى الأشكال 3-1، 3-3 نرى حتى خوارزمية S-DES تبدي نفس بنية نظام فيستيل ذي الحلقتين. الفارق الوحيد عن بنية نظام فيستيل هوحتى هذه الخوارزمية تبدأ وتنتهي بتابع تبديل مواقع. يظهر هذا الخلاف أيضا في خوارزمية DES الكاملة.

خوارزمية فيستيل لفك التعمية

عملية فك التعمية بنظام تشفير فيستيل هي بالمبدأ نفس عملية التعمية. والقاهدة هي كما يلي: يستخدم النص المشفر كدخل للخوارزمية، ولكن تستخدم المفاتيج الجزئية بترتيب معكوس أي يستخدم المفتاح الجزئي kn في الحلقة الأولى، kn-1 في الحلقة الثانية إلى غير ذلك حتى الحلقة الأخيرة حيث يستخدم المفتاح kl . تعتبر هذه الميزة هامة. وذلك لأننا لسنا بحاجة إلى تحقيق خوارزميتين مختلفتين، واحدة للتعمية وأخرى لفك التعمية.

وللتأكد من حتى نفس الخوارزمية ولكن بترتيب مفاتيح معكوسة تعطي نتائج سليمة سنتتبع الشكل 3-6 ، والذي يظهر عملية التعمية تسير من الأعلى إلى الأسفل في الجزء اليساري، بينما عملية فك التعمية فتنتجه من الأسفل إلى الأعلى في الجزء اليميني من الشكل، وللتوضيح فقط استخدمنا الرموز LE1 وRE1 للتعبير عن المعطيات التي تنتقل خلال خوارزمية التعمية، بينما استخدمنا الرموز LD1 وRD1 للتعبير عن المعطيات التي تتنتقل خلال خوارزمية فك التعمية. يوضح المخطط حتى القيم المرحلية في حلقة عملية فك التعمية تساوي القيم الموافقة في حالة التعمية بعد تبديل الأنصاف بين بعضهما بعض. ولتوضيح ذلك بطريقة أخرى نفرض حتى خرج الحلقة I من خوارزمية التعمية هوLE1||RE1 (التعبير || يعني وصل السلسلة Li بالسلسلة Ri). عندها سيكون الدخل الموافق لحلقة فك التعمية رقم (16-i) هوREi//Lei ومكافئه RD16-i||LD16. خرج هذه الحلقة هوالنص المشفر النهائي. لنأخذ هذا النص ونجعله دخلا لنفس الخوارزمية. ولج الحلقة الأولى هوRE16||LE16 والذي يوافق خرج حلقة التعمية رقم 16 بعد تبديل نصفيه بين بعضهما بعض.

نريد حتى نوضع الآن حتى خرج حلقة فك التعمية الأولى هي في الحقيقة ولج حلقة التعمية رقم 16 بعد تبديل نصفيه بعضهما ببعض. لنأخذ أولا عملية التعمية. نرى أن:

LE16 = RE15 RE16 = LE15 ө (RE15, K16)

{{{{الشكل 3-6: التعمية وفك التعمية في نظام فيستيل

وفي جهة فك التعمية لدينا :

LD1 = RD0 = LE16= RE15 RD1 = LD0 ө F(RD0, K16) = RE16 ө F(RE15, K16) = [LE15 ө F(RE15, K16)] ө F(RE16, K16)

وبما حتى عملية XOR تملك الخصائص التالية:

[A өB] ө C = A ө [B өC] D өD = 0 E ө 0 = E

نجد حتى LD1 = LE15 وLD1= RE15، وبالتالي فإن خرج حلقة فك التعمية الأولى هوLE1||RE15. وهوتعبير عن ولج حلقة التعمية رقم 16 بعد تبديل نصفيه بعضهما ببعض. يسري هذا التوافق على جميع الحلقات الست عشرة. يمكن تلخيص ذلك برموز عامة: فمن أجل التكرار ذي الرقم i من خوارزمية التعمية يمكن حتى نخط:

Lei = REi REi = Lei-1 ө F (REi-1, Ki)

وبإعادة ترتيب الرموز نحصل على:

REi-1 = Lei LEi-1 = REi ө F(REi-1, Ki) = REi ө F(Lei, Ki)

نكون بذلك قد عبرنا عن ولج التكرار ذي الرقم i كتابع للخرج، وتثبت هذه المعادلات التناسب المبين على الطرف اليميني من الشكل 3-6.

نرى أخيرا حتى خرج الحلقة الأخيرة من عملية فك التعمية هوRE0||LE0، وهوتعبير التبديل العكسي لأنصاف النص الصريح الأساسي، وبذلك نكون قد بينا صحة عملية فك التشفير لنظام فيستيل.

لاحظ حتى هذا الاستنتاج لا يحتاج حتىقد يكون التابع F عكوسا. وللتأكد من ذلك نأخذ حالة خاصة بيحث ينتج التابع F خرجا ثابتا (على سبيل المثال واحدات) بعض النظر عن قيمة دخليه. لاحظ حتى المعادلات السابقة لا تزال سارية المفعول.

تأريخ

التعمية القياسية للمعطيات

تعتمد مخططات التعمية الأكثر انتشارا على مقياس تعمية المعطيات (Data Encryption Standard-DES) والتي تم نشرها والاعتراف بها من قبل المخط العالمي للقياسات عام 1977. تسمى الخوارزمية بحد ذاتها "بخوارزمية تشفير المعطيات " (Data Encrytion Algorithm-DEA) . يتم وفق خوارزمية DES تعمية المعطيات على شكل كتل بطول 64 خانة وباستخدام مفتاح بطول 56 خانة. تقوم هذه الخوارزمية بتحويل كتلة الدخل ذات الأربع وستون خانة عبر سلسلة من المراحل لتعطي خرجا بطول 64 خانة أيضا. تستخدم نفس المراحل ونفس المفتاح لعكس عملية التعمية، بمعنى آخر لفك التعمية.

لاقت خوارزمية DES انتشارا واسعا. كما أنها كانت موضوعا للجدل حول إثبات مستوى الأمن الذي تحققه. ولتبيان طبيعة هذا الجدل سنستعرض بسرعة تاريخ هذه الخوارزمية.

هيأت شركة IBM في أواخر الستينات مشروعا بحثيا حول التعمية بإشراف هورست فيستيل Horst Feistel. انتهى هذا المشروع عام 1971 بانتاج خوارزمية تعمية باسم LUCIFER ، والتي تم بيعها لشركة لويد اللندنية Lloyd’s of London للتجارة البحرية من أجل استخدامها في النظام المالي لهذه الشركة، والذي تم تطويره أيضا من قبل شركة IBM. خوارزمية LUCIFER هي تعبير عن نظام تشفير فيستيل الكتلي والذي يعمل على طول كتلة 64 خانة. ومع مفتاح بطول 128 خانة. وبسبب النتائج الواعدة لمشروع LUCIFER، قامت شركة IBM بتكثيف الجهود لتطوير منتج تعمية تجاري قابل للترويج، بحيث يمكن تحقيقه في شريحة واحدة. قاد هذه الجهود جميع من ولتر تاتشمان Walter Tachman وكارل ميير Carl Meyer، وقد عمل في هذا المشروع باحثون ومستشارون من خارج شركة IBM ومرشدين تقنيني من NSA. ناتج هذه الجهود هونسخة معدلة من LUCIFER والتي كانت أكثر مقاومة لتحليل التعمية، ولكن كانت بمفتاح ذو56 خانة وذلك لتضمينها على شريحة واحدة.

طرح مخط القياسات القومي عام 1973 طلبا حول الحاجة لاعتماد نظام تشفير قياسي قومي. قدمت شركة IBM نتائج مشروع تاتشمان-ميير، وقد كانت هذه الخوارزمية الأفضل إلى حد كبير بين الخوارزميات المقدمة وقد تم اعتمادها عام 1977 كخواركية تشفير معطيات قياسية.

تعرضت هذه الخوارزمية قبل اعتمادها لأ، تكون محط انتقاد كثيف، والذي لم ينته حتى هذا اليوم. هناك ناحيتان أشعلتا الانتقاد. أولهما حتى طول المفتاح لخوارزمية LUCIFER الأصلية هو128 خانة، أما طول المفتاح في الخوارزمية المقدمة فقد أصبح 56 خانة، أي حتى هناك تخفيض محسوس لطول المفتاح بطول 72 خانة. خاف المنتقدون من حتىقد يكون المفتاح قصير جدا لمقاومة محاولات كسر التعمية بالتجريب. الناحية الثانية من الانتقاد كانت تخص البنية الداخلية لخوارزمية DES أي الصناديق S. حيث لم يكن المستخدمون متأكدين من خلوالبنية الداخلية غير حتى الأحداث المتلاحقة، وخاصة الأعمال الأخيرة في تحليل التعمية التفاضلي، بينت حتى خوارزمية DES تملك بنية داخلية قوية. والأكثر من ذلك، صرح أعضاء IBM حتى التغيير الوحيد الذي طرأ على ما قدمته الشركة هوتغيير صناديق S حسب اقتراح NSA ، وذلك لإزالة نقاط الضغف التي تم تحديدها أثناء عملية التطوير.

في جميع الأحوال، نجحت خوارزمية DES ولاقت انتشارا واسعا خصوصا في التطبيقات المالية. أعاد المعهد القومي للمقاييس والتقنيات عام 1997 (NIST) التأكيد على استخدام خوارزمية DES فيدراليا ولمدة خمسة سنوات جدد. نصح NIST استخدام خوارزمية DES للتطبيقات الأخرى. غير تلك التي تحمي المعلومات المصنفة. وفي عام 1999 طرح NIST نسخته الجديدة من المقاييس والتي أشارت إلى استخدام خوارزمية DES الثلاثية (Triple-DES) والتي تتضمن في جوهرها تكرار خوارزمية DES ثلاث مرات لنفس النص الصريح وباستخدام مفتاحين أوثلاثة مفاتيح مختلفة وذلك لانتاج النص المشفر. يفترض أن ندرس خوارزمية DES الثلاثية في الفصل السادس ولأن البنية التحتية لخوارزميات التعمية وفك التعمية في هذه الخوارزمية هي نفسها المستخدمة في خوارزمية DES فلا ضير من فهم الأخيرة بشكل مشروح وجيد.

التعمية وفق خوارزمية DES

يبين الشكل 3-7 البنية العامة لمخطط التعمية وفق خوارزمية DES. وكما هوالحال في أي مخطط تعمية، هناك دخلان: الأول هوتعبير عن النص الصريح المطلوب تعميته والآخر هوالمفتاح. طول النصح الصريح في هذه الحالة 64 خانة، وطول المفتاح هو56 خانة (تقبل الخوارزمية عمليا 64 خانة كمفتاح، لكن يتم استخدام 56 خانة فقط. أما الخانات الثمانية الباقية فتستخدم كخانات ازدواجية).

يمكن بالنظر إلى الطرف اليساري من الشكل ملاحظة حتى معالجة النص الصريح تمر من خلال ثلاث مراحل. تمر كتلة النص الصريح ذات الطول 64 خانة في الفترة الأولى من خلال عملية تبديل مواقع أولية (IP). والتي تعيد ترتيب الخانات. يتبع ذلك فترة ثانية مؤلفة من 16 حلقة لها نفس الوظيفة. والتي تتضمن تابعي تبديل حروف وتبديل مواقع. يتألف خرج الحلقة الأخيرة (السادس عشر) من 64 خانة والذي هوفي الأصل تابع للنص الصريح والمفتاح معا. يتم بعد ذلك تبديل نصفي هذا الخرج مع بعضهما بعض لانتاج خرج مبدئي. يمر هذا الخرج عبر عملية تبديل المواقع (IP-1) والتي تعاكس عملية التبديل الأولى، وبذلك يتم انتاج النص المشفر النهائي . نلاحظ حتى خوارزمية DES تملك نفس بنية نظام تشفير فيستيل والمبينة في الشكل 3-5، ولكن بعد استثناء عمليتي التبديل الأولى والثانية.

يبين القسم الأيمن من الشكل 3-7 طريقة استخدام المفتاح ذوالطول 56 خانة. يمر المفتاح عبر تابع تبديل مواقع. يتم بعد ذلك انتاج مفتاح جزئي k1 من أجل جميع فترة من المراحل الست عشرة، وذلك عن طريق تطبيق وظيفتين متتاليتين هما ازاحة دائرة يسارية وتبديل مواقع. عملية تبديل المواقع متناظرة في جميع المراحل، إلا أنه يتم انتاج مفاتيح مختلفة نتيجة الازاحة المتكررة لخانات المفتاح.

{{{{الشكل 3-7: الوصف العام لخوارزمية تعيمة DES

عملية التبديل الأولية

يتم تحديد عميليتي التبديل الأولى ومعاكستها عن طريق الجدوال 3.2b, 3.2a على التوالي. يمكن تفسير هذه الجدوال كما يلي: يتألف الدخل من 64 خانة يتم ترقيمها من 1 وحتى 64. تحوي المداخل الأربعة والستون من جدول تبديل المواقع أرقام الخانات البديلة من 1 وحتى 64. أي حتى جميع خلية في جدول تبديل المواقع تشير إلى مسقط خانة الدخل التي ستشكل خانة الخرج.

لإظهار حتى تابعي تبديل المواقع هما في الحقيقة عكس بعضهما البعض سندرس خانات الدخل M، التالية والتي عددها 64:

M8 M7 M6 M5 M4 M3 M2 M1 M16 M15 M14 M13 M12 M11 M10 M9 M24 M23 M22 M21 M20 M19 M18 M17 M32 M31 M30 M29 M28 M27 M26 M25 M40 M39 M38 M37 M36 M35 M34 M33 M48 M47 M46 M45 M44 M43 M42 M41 M56 M55 M54 M53 M52 M51 M50 M49 M64 M63 M62 M61 M60 M59 M58 M57

حيث M1 هي تعبير عن خانة ثنائية. عندها يمكن وصف تبديل المواقع X = IP(M) كما يلي:

M2 M10 M18 M26 M34 M42 M50 M58 M4 M12 M20 M28 M36 M44 M52 M60 M6 M14 M22 M30 M38 M46 M54 M62 M8 M16 M24 M32 M40 M48 M56 M64 M1 M9 M17 M25 M33 M41 M49 M57 M3 M11 M19 M27 M35 M43 M51 M59 M5 M3 M21 M29 M37 M45 M53 M61 M7 M15 M23 M31 M39 M47 M55 M63

اذا أخذنا بعد ذلك تبديل المواقع العكسي Y = IP-1(X) = IP-1(IP(M))، عندها يمكن التبيان أنه ستتم استعادة الترتيب الأصلي.

تفصيلات حلقة واحدة

يبين الشكل 3-8 البنية الداخلية لكل حلقة. لنبدأ مرة أخرى بالهجريز على الطرف اليساري من المخطط. تتم معالجة النصفين اليساري واليمين لكل 64 خانة مرحلية كقيم منفصلة ذات 32 خانة مرمزة بالشكل L (يساري) وR (يميني). وكما هوالحال في أي نظام تشفير فيستيل تقليدي، يمكن تلخيص المعالجة الكلية لكل حلقة بالمعادلات التالية:

Li = Ri-1 (1-3) Ri = Li-1 ө F(Ri-1, k1) (2-3)

الجدول3-2: جدول تبديل المواقع لخوارزمية DES

يتألف مفتاح جميع حلقة من 48 خانة. الدخل R مؤلف من 32 خانة. يتم توسيع الدخل R إلى 48 خانة باستخدام الجدول 3-2C الذي يحدد عمليتي تبديل مواقع وتوسيع بنفس الوقت. والذي يتضمن تكرار 16 خانة من خانات الدخل R. يتم بعد ذلك جمع الخانات الثماني والأربعون الناتجة مع المفتاح الجزئي k1 عن طريق XOR. يتم تمرير الخانات الثماني والأربعين الناتجة عبر تابع تبديل حروف والذي ينتج خرجا بطول 32 خانة، والتي يتم اعادة ترتيبها عن طريق الجدول 3-2d.

الشكل 3-8: حلقة واحدة من خوارزمية DES

يبين الشكل 3-9 دور الصناديق S في التابع F. تتألف عمليتي تبديل الحروف من مجموعة مؤلفة من ثمانية صناديق S، يقبل جميع منها ست خانات ولج وينتج أربع خانات خرج. يتم تحديد هذه التحويلات في الجدول 3-3، والذي يتم تفسيره كما يلي: تشكل الخانات الأولى والأخيرة من ولج الصندوق Si رقما ثنائيا مؤلفا من خانتين والذي يحدد واحدة من أربع عمليات تبديل حروف فهم بواسطة أربعة أسطر من جدول الصندوق Si. بينما تساعد الخانات الأربع الوسطى على اختيار أحد الأعمدة الستة عشر. تحوي الخلية الواقعة على تقاطع السطر والعمود المختارين قيمة عشرية. القيمة الثنائية المؤلفة من أربع خانات عن تحويل هذه القيمة العشرية هي بالحقيقة الخرج المطلوب. عملى سبيل المثال اذا كان ولج صندوق si هو011001، عندها سيكون السطر المختار هوالسطر ذي الرقم 01 (السطر الأول)، والعمود المختار هوالعمود ذوالرقم 1100 (العمود رقم 12) . الخلية الواقعة على تقاطع السطر الأول والعمود رقم 12 تحوي القيمة 9، أي حتى الخرج هو1001.

يحدد جميع سطر من الصندوق S عملية تبديل حروف عكوسة. يمكن حتى يساعد الشكل 3-4 على فهم عملية التحويل. يبين الشكل عملية تبديل الحروف للسطر رقم 0 من الصندوق Si.

يستحق عمل صناديق S تعليقات أكثر. لنهمل حاليا تأثير المفتاح k1. اذا تفحصت جدول التوسيع سترى أنه تم تقسيم خانات الدخل الاثنتين والثلاثين إلى مجموعات ذات أربع خانات، تصبح بعد ذلك مجموعات ذات ست خانات عن طريق تكرار الخانات الخارجية لكل مجموعتين متتاليتين. عملى سبيل المثال اذا كانت العبارة التالية جزءا من كتلة الدخل.

….efgh ijkl mnop….

عندها ستصبح بعد التحويل:

…..defghi hijklm lmnopq ….

الشكل 3-9: حساب التابع F (R,K.

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

الجدول 3-3: تعريفات صناديق s في خوارزمية DES

يمكن التعبير عن مخطط التعمية وفق خوارزمية DES كما يلي: • الدخل: النص الصريح M= m1, m2 ….m64 ومفتاح بطول 64 خانة K = k1, k2, l3 …k64 (يضم ثماني خانات ازدواجية). • الخرج: نص مشفر بطول 64 خانة C = c1, c2 … c64. • الإجرائية:

1- (توليد المفاتيح( يتم توليد 16 مفتاحا جزئيا k1 للحلقات، طول جميع منها 48 خانة، وذلك باستخدام مخطط توليد المفاتيح الوارد في الفقرة التالية. 2- IP (m1, m2 …m64) → (L0, R0) . يستخدم لذلك التبديل IP المبين في الجدول 3-2a وذلك لتبديل مواقع الخانات. ومن ثم تقسم النتيجة إلى نصفين يميني ويساري جميع منهما بطول 32 خانة R0 = m57, m49 … m7 وL0 = m58, m50 …m8. 3- يتم تطبيق 16 حلقة متناظرة بحيث يتم حساب R1, L1 (حيث 1 ≤ i ≤ (16 وذلك باستخدام المعادلات 3.1 و3.2. يتم حساب F(Ri-1, Ki) = P(E(Ri-1)ө Ki)) كما يلي: أ‌- نوسع Ri-1 = r1, r2, r3, …r52 من 32 خانة وذلك باستخدام وظيفة التبديل – التوسيع E المبينة في الجدول 3-2C:

(T = r32 r1 r2 .. r32 r1) E(Ri-1) → T

ب‌- T ө K1 → T تخط T على شكل ثماني سلاسل جميع منها حرف بست خانات ، T = (B1, ….B8). ج – (S1(B1), S2(B2) .. S8(B8)، حيث تحول الوظائف S1(B1) جميع سلسلة Bi = b1 b2 …b6 إلى قيمة بأربع خانات موجودة بشكل عشري في السطر r والعمود c من الصندوق Si المشروح في الجدول 3-3، حيث b2 b3 b4 , r = 2.b1 + b6 هي التمثيل الثنائي لرقم العمود C (أي 0 ≤ c≤15). وبالتالي فإن (011011) Si يفترض أن تعطي r = 1 , c = 13 وقيمة الخرج هيخمسة أومكافئها الثنائي (0101). د- P(T) → T يستخدم لذلك الجدول 3-2d. وذلك لتبديل مواقع الخانات الاثنتين والثلاثين الناتجة عن T.

4- (R16, L16) → b1 b2 … b64. (يتم تبديل الكتل النهائية R16, L16 فيما بينهما). 5- IP-1(b1 b2 … b64). يستخدم لذلك التبديل IP-1 المشروح في الجدول 3-2b، (أي C= b40 bثمانية … b25).

توليد المفاتيح

بالعودة إلى الأشكال 3-7 و3-8 نجد حتى المفتاح ذا الطول 64 خانة هوولج الخوارزمية. يتم ترقيم خانات المفتاح من 1 وحتى 64. يتم اهمال جميع خانة ثامنة وذلك كما هومشار غليه في الجدول 3-4a. وهوما يميز عملية التبديل المشروحة في جدول خيار التبديل الأولي (Permuted Choice One) المشروح في الجدول 3-4b. تتم معالج المفتاح ذي الست والخمسين خانة بعدئذ على شكل نصفين جميع منهما 28 خانة، مرمزين D0, C0. تنفذ عملية ازاحة دورانية يسارية في جميع دورة على Di-1, Ci-1 بشكل مستقل، إما لخانة واحدة أولخانتين كما هووارد في الجدول 3-4d. تصبح هذه القيم المزاحة ولج الحلقة التالية. كذلك تصبح دخلا لخيار التبديل الثاني Permuted Choice Two والذي ينتج خرجا بطول 48 خانة يعطي بدوره للتابع P(Ri-1, Ki).

يمكن بشكل عام التعبير عن مخطط توليد المفاتيح كما يلي:

• الدخل: مفتاح ذو64 خانة K = k1 k2 … k64 يضم ثماني خانات ازدواجية. • الخرج: ستة عشر مفتاحا K1 طول جميع منها 48 خانة، حيث 1 ≤ I ≤ 16. • الإجرائية: 1- تعهد v1، حيث 1 ≤ i ≤ 16، كما يلي: v1 = 1 من أجل i ε {1, 2, 9, 16 وv1 = 2 من أجل بقية قيم i (هذا ما سيمثل عدد خانات الإزاحة اليسرى الدورانية لكل 28 خانة). 2- PC1 (K) → T يتم تمثيل T على شكل نصفين (C0, D0) يتألف جميع منهما من 28 خانة. (يستخدم لذلك التبديل PC1 المبين في الجدول 3-4b وذلك لاختيار الخانات من C0 = K56 K49 .. K26 وD0= K63 K55 .. K4). 3- نحسب K1، من أجل 1 ≤ i ≤ 16، كما يلي: Ki , Di ← (Di-1 <<< vi), Ci ← (Ci-1 >>> vi) ← PC2 (Ci, Di) (يستخدم التبديل PC2 المبين في الجدول 3-4C لاخيتار 48 خانة نتيجة وصل السلاسل b1 b2 b2 .. b56 و(Ki= b14 b17 … b32 – الرمز >>> يعبر عن ازاحة دورانية بمقدار vi.

فك التعمية وفق خوارزمية DES

تستخدم عملية فك التعمية ، كما هوالحال في أي نظام تشفير فيستيل، نفس خوارزمية التعمية ، ما عدا حتى ترتيب المفاتيح الجزئية سيكون مقلوبا.

{{{الجدول 4-3: مخطط توليد المفاتيح في خوارزمية DES{

تأثير الانهيار الثلجي – أوالتأثير التراكمي

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

تتميز خوارزمية DES بتاثير انهياري قوي. يبين الجدول 3-5 بعض نتائج الاحصائيات الدراسية. تم استخدام نصان صريحان مختلفان بخانة واحدة في الجدول 3-5a:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000

والمفتاح المستخدم هو:

0110010 0011100 0011000 0011100 1100010 0100100 1001011 00000001

يبين الجدول أنه بعد الحلقة الثالثة فقط سيكون الخلاف بين الكتلتين هو21 خانة. وبعد نهاية جميع الحلقات سيصبح عدد الخانات المتنوعة هو34 خانة.

يبين الجدول 3-5b نفس الاختيار ولكن عند استخدام نص صريح واحد هو:

10100100 11101011 01110110 00010011 01111010 00101111 10000101 01101000

بينما يتم استخدام مفتاحين مختلفين بخانة واحدة:

1101110 0110001 0000100 0011101 0011000 1101111 1111011 1110010 1101110 0110001 0000100 00111001 0011000 1101111 1111011 0110010

تبين النتائج مرة أخرى بأنه حوالي نصف الخانات في النص المشفر يفترض أن تتغير وأن التأثير الانهياري سيكون ملحوظا بعد بضع دورات فقط.

الجدول 3-5: التأثير الانهياري في خوارزمية DES:

(a) تغيير في النص الصريح	 (b) تغيير في المفتاح

0 1 0 0 1 6 1 2 23 21 23 14 4 35 4 28 5 39 5 32 6 34 6 30 7 32 7 32 8 31 8 6 9 29 9 34 10 42 10 40 11 44 11 38 12 32 12 31 13 30 13 33 14 30 14 28 15 26 15 26 16 29 16 34 34 34

قوة خوارزمية DES

بقيت خوارزمية DES منذ اعتمادها على الصعيد الحكومي محط الاهتمام للتحقق من مستوى الأمن الذي تحققه. وقد توزع هذا الاهتمام على مجالين: الأول هوطول المفتاح، والثاني هوطبيعة الخوارزمية بحد ذاتها.

استخدام مفاتيح بطول 54 خانة

عندماقد يكون طول المفتاح 56خانة فإن هذا يعني حتى هناك 556 مفتاحا مختلفا، أوما يقارب 1016 X 7.2 مفتاحا مختلفا. نستنتج من هذا حتى محاولة كسر المفتاح عن طريق "الهجوم الأعمى" (التجريب) غير عملية نهائية. فاذا افترضنا أنه يجب تجريب حوالي نصف عدد المفاتيح للوصول إلى المفتاح المطلوب، وبفرض حتى الحاسب الواحد يستغرق حوالي 1 ميكروثانية فقط لانجاز عملية فك تشفير باعتماد خوارزمية DES، فسنجد حتى عملية الكسر يفترض أن تستغرق أكثر من 1000 سنة (انظر الجدول 2-2). لكن الافتراض حتى عملية التعمية أوفك التعمية تستغرق حوالي 1 ميكروثانية، هوافتراض مبالغ فيه وقد تم عرضه للتوضيح فقط. افترض Diffie وHellman بأن التقنية الموجودة كفيلة ببناء حواسب متوازية، مزودة بمليون جهاز تعمية، يستطيع جميع منها تطبيق عملية التعمية بحوالي ميكروثانية واحدة، يمكن بذلك تخفيض الزمن اللازم إلى حوالي عشرة ساعات. أما كلفة ذلك فقد قدر بحوالي 20 مليون دولار عام 1977.

ثبت أخيرا وبشكل قاطع عام 1998 عدم سرية النظام DES ، وذلك عندما أعربت احدى الشركات عن كسر خوارزمية DES باستخدام طريقة خاصة أسمتها "آلة كسر DES" DES cracker machine والتي تم بناؤها بأقل من 250 ألف دولار. استغرقت عملية الكسر أقل من ثلاثة أيام. وقد نشرت هذه الشركة وصفا مفصلا عن هذه الآلة، سامحة بذلك للآخرين ببناء مثل هذه الآلة. وبما حتى ثمن الحواسب ينخفض بسرعة كبيرة مع زيادة سرعتها، نجد حتى خوارزمية DES أصبحت الآن بلا قيمة عملية.

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

لحسن الحظ هناك الكثير من بدائل DES، أهمها خوارزمية AES وخوارزمية DES الثلاثية والتي سيتم شرحها في الفصلين الخامس والسادس على التوالي.

طبيعة خوارزمية DES

هناك ناحية أخرى تسبب القلق وهي الاحتمالات الممكنة لتحليل التعمية عن طريق السيطرة على خصائص خوارزمية DES . ركز هذا الاهتمام بشكل خاص على جدوال التبديل أوما يسمى صناديق S، والتي تستخدم في جميع دورة. نتيجة للخصائص التصميمية فهذه الصناديق بشكل خاص وللخوارزمية ككل بشكل عام، والتي لم تنشر للعوام، هناك شك بأنه قد تم تصميم هذه الصناديق بشكل يجعل تحليل التعمية ممكنا بالنسبة للمهاجم الذي يعهد نقاط الضعف الخاصة بهذه الصناديق. ومع مرور الوقت تم اكتشاف قوانين هذه الصناديق والتصرفات غير المتسقطة لها. وعلى الرغم من ذلك، لم يتسنى لأحد اكتشاف نقاط الضعف القاتلة والمتسقطة لهذه الصناديق.

الهجوم الزمني

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

تحليل التعمية التفاضلي والخطي

التساؤل الأول، على طول حياة خوارزمية DES، هوحول مدى ضعف هذه الخوارزمية تجاه الهجوم الأعمى، وذلك نتيجة لقصر طول المفتاح (56 خانة). لكن كان هناك أيضا اهتمام في ايجاد طريقة الهجوم على خوارزمية DES باستخدام تحليل التعمية. ومع زيادة شعبية نظم التعمية الكتلية ذات المفاتيح الطويلة، بما في ذلك خوارزمية DES الثلاثية، أصبح الهجوم الأعمى غير فعال. لذلك ازداد التأكيد على ايجاد طرق هجوم على خوارزمية DES وعلى بقية أنظمة التعمية المتناظرة باستخدام تحليل التعمية. سنقدم في هذا المبتر نظرة مختصرة على أكثر طريقتين فعالتين وواعدتين: تحليل التعمية التفاضلي، وتحليل التعمية الخطي.

تحليل التعمية التفاضلي

يعتبر تحليل التعمية التفاضلي واحدا من أبرز التطورات التي طرأت على تحليل التعمية في السنوات الأخيرة. سنناقش في هذا المبتر هذه التقنية وتطبيقاتها على خوارزمية DES.

تاريخ

لم يتم نشر أي شئ حول تحليل التعمية التفاضلي حتى عام 1990. وأول جهود تم نشرها كانت متعلقة بتحليل التعمية لخوارزمية التشفير المدعوة FEAL وذلك من قبل Murphy. بعد ذلك ظهرت سلسلة من النشرات لكل من Shamir , Biham والتي بينت هذا النوع من الهوم على عدد من خوارزميات التعمية وتوابع المزج والتوزيع (has function).

النتائج الأكثر انتشارا لهذه المواضيع هي تلك التي تطبق على خوارزمية DES. يعتبر تحليل التعمية التفاضلي أول هجوم تم نشره يحقق كسر خورازمية DES بأقل من 255 حالة. يمكن حتى ينجح كسر خوارزمية DES عند استخدام تحليل التعمية التفاضلي بجهود من مرتبة 247 محتاجين بذلك إلى 247 نص صريح مختار. ومع حتى القيمة 247 أقل بكثير من القيمة 255 ، إلا حتى هذا النوع من الهجوم يبقى للدراسات النظرية فقط، والسبب في ذلك هوالحاجة إلى 247 نص صريح مختار.

ومع حتى تحليل التعمية التفضالي يعتبر أداة قوية، إلا أنه لم يؤثر بشكل جيد على خوارزمية DES ويعود السبب في ذلك، حسب ما أدلى به عضوفريق IBM الذي صمم هذه الخوارزمية، إلى حتى تحليل التعمية التفاضلي عهد من قبل الفريق عام 1974، حيث لعبت الحاجة إلى تقوية خوارزمية DES ضد الكسر باستخدام التحليل التفاضلي دورا كبيرا في تصميم صناديق S وعملية تبديل المواضع P. وكدليل على هذا الدور سنطرح المقارنة التالية: يحتاج تحليل التعمية التفاضلي لخوارزمية LUCIFER ذات الثماني مراحل إلى 256 نص صريح مختار، بينما يحتاج الهجوم على نموذج من خوارزمية DES بثماني مراحل أيضا إلى 214 نص صريح مختار.

الهجوم باستخدام تحليل التعمية التفاضلي

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

سنبدأ بتغيير الوصف الخاص بخوارزمية DES. اذا افترضنا حتى كتلة النص الصريح هي m والمؤلفة من النصفين m0, m1، يجري في جميع فترة نقل نصف الدخل الأيمن إلى نصف الخرج الأيسر، أما نصف الخرج الأيمن فيكون نتيجة تابع دخله نصف الدخل الأيسر والمفتاح الجزئي الخاص بهذه الفترة. لذلك سيتم في جميع فترة انتاج كتلة جديدة بطول 32 خانة فقط. اذا أعطينا جميع كتلة جديدة الرمز m1 (حيثسبعة ≥ i ≥ 2)، عندها سيكون أنصاف الرسالة المرحلية مرتبطين بالشكل:

Mi+1 = mi-1 ө F(mi, Ki I = 1, 2, 3, …. 16

نبدأ في تحليل التعمية التفاضلي بالرسالتين m1, m مع فهم فارق XOR بينهما، أي ∆ m = m ө m1 ، وليكن الفارق بين أنصاف الرسالة المرحلية هو∆ m = m ө m11، عندهاقد يكون لدينا:

∆ mi-1 = mi+1 ө m1i-1 = [mi-1 ө F(mi, ki)] ө [mi-1 ө F(mi-, ki)] = ∆mi-1 ө [F(mi, ki) ө f(mi, ki)]

لنفترض الآن بأن عدة أزواج من الدخل التابع f وبنفس الفارق تعطي نفس الفارق في الخرج اذا تم استخدام نفس المفتاح الجزئي. ولطرح ذلك بشلك أدق سنقول بأن X يمكن حتى تنتج Y باحتمال مقداره P اذا كان الكسر P يميز جميع الأزواج التيقد يكون من أجلها ولج XOR هوX وخرج XOR هوY. فرضا ان هناك عددا من القيم X التي تعطي باحتمال كبير فرقا معينا في الخرج. لذلك، اذا فهمنا ∆ mi-1, ∆ mi باحتمال كبير، عندها يمكن فهم ∆ mi-1 باحتمال كبير أيضا. والأكثر من ذلك، اذا أمكن تحديد عدد هذه الفروق فمن المحتمل تحديد المفتاح الجزئي المستخدم كدخل للتابع f.

تعتمد الاستراتيجية العامة لتحليل التعمية التفاضلي على هذه الاعتبارات لفترة واحدة. وتتلخص الاجرائية بالبدء بنصين صريحين m, m1 وفرق معطى، ومتابعتهما خلال نموذج محتمل من الفروقات بعد جميع فترة وذلك لانتاج فرق محتمل للنص المشفر. عمليا هناك فرقان محتملان للنصين المؤلفين من 32 خانة (∆ m17||∆ m16). نخضع بعد ذلك m1, m للتعمية من أجل تحديد الفرق الحقيقي تحت مفتاح غير معروف ونقارن النتيجة مع الفرق المحتمل . اذا كان هناك تطابق، أي:

Ek (m) ө Ek (m1) = ∆ m17||∆m16

عندها نشك بأن جميع النماذج المحتملة في جميع المراحل هي سليمة. يمكن مع هذا الافتراض حتى تجرى بعض التخمينات حول خانات المفتاح. يجب تكرار هذه الاجرائية عدة مرات لاستنتاج جميع خانات المفتاح.

يوضح الشكل 3-10 كيفية توليد الفروقات لثلاث مراحل من خوارزمية DES. تشير الاحتمالات المشروحة على اليمين إلى الاحتمالات التي يمكن حتى تظهرها مجموعة معطاة من الفروقات كتابع لفروقات الدخل. أخيرا، كما هومبين، فإن احتمال فرق الخرج بعد ثلاثة مراحل يساوي 0.25X1X0.25 = 0.0625.

{{{{الشكل 3-10: التوليد التفاضلي خلال ثلاث مراحل من خورازمية DES (الأرقام مكتوبة بالست عشري

تحليل التعمية الخطي

أتى هذا النوع من التحليل بعد تحليل التعمية الفاضلي . يعتمد هذا الهجوم على ايجاد تقريب خطي لوصف عمليات التحويل التي تتم في خوارزمية 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. مما يعطينا معادلة خطية لحساب خانات المفتاح.

مبادئ تصميم نظم التشفير الكتلي

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

معايير تصميم DES

هجرز المعايير المستخدمة لتصميم خوارزمية DES على تصميم صناديق S والتابع P الذي يأخذ خرج الصناديق S (الشكل 3-9). معايير الصناديق S:

1- يجب ألا تكون أية خانة خرج من أي صندوق S قريبة جدا من ناتج تابع خطي ما دخله خانات الدخل. وبالتحديد اذا اخترنا أية خانة خرج وأية مجموعة جزئية من خانات الدخل الستة، فان قيمة الجزء الناتج عن قيم الدخل التي تكون من أجلها قيمة هذه الخانة من الخرج مساوية لناتج عملية XOR على الخانات من الدخل، يجب ألا تكون قريبة من الواحد أومن الصفر، بل يجب حتى تكون حوالي 0.5. 2- يجب حتى يحتوي جميع سطر من الصندوق S (والمحدد من خلال الخانتين الأكثر أهمية والاقل أهمية من خانات الدخل) على جميع تشكيلات الخرج المحتملة والبالغ عددها 16. 3- اذا اختلفت قيمتا ولج الصندوق S بخانة واحدة فقط، عندها يجب حتى تختلف قيم الخرج بخانتين على الأقل. 4- اذا اختلف دخلان اثنان إلى الصندوق S في قيم الخانتين الواقعتين في الوسط بالضبط، عندها يجب حتى تختلف قيم الخرج بخانتين على الاقل. 5- اذا اختلف دخلان اثنان إلى الصندوق S في أول خانتين وكانت الخانتان الأخيرتان متناظرتين، عندها يجب حتى تكون قيمتا الخرج متاينتين. 6- من أجل أية قيمة فرق غير صفرية مؤلفة منستة خانات بين قيم الدخل، يجب ألا يتواجد أكثر من ثمانية أزواج ولج (من بين جميع أزواج النص البالغ عددها 32)، والتي تنتج هذا الفارق، تؤدي إلى نفس الفارق في الخرج. 7- هذا المعيار شبيه بالذي قبله ولكن من أجل ثلاثة صناديق S.

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

أما معايير تابع تبديل المواضع P فهي:

1- يتم توزيع خانات الخرج الأربع من جميع صندوق S في الفترة i بحيث تؤثر خانتان منهما (تكون دخلال) على الخانات الوسطة للفترة i+1 ، أما الخانتان الباقيتان فتؤثرن على الخانات النهائية. لا تكون خانتا الدخل الوسطى في ولج صندوق S مشهجرتين بين صناديق S المجاورة. الخانات النهائية هي الخانتان الواقعتان إلى أقصى اليسار والخانتان الواقعتان إلى أقصى اليمين والتي تتم بالمشاركة عليها مع صناديق S المجاورة. 2- تؤثر خانات الخرج الأربعة من جميع صندوق S على ستة صناديق S مختلفة في الفترة التالية، ولا يمكن حتى تؤثر اثنتان منهما على نفس الصندوق S. 3- ليكن لدينا صندوقي S التالييت k, j. اذا أثرت خانة خرج من الصندوق si على خانة وسطى من الصندوق sk في الفترة التالية، عندها لا يمكن حتى تؤثر خانة خرج من الصندوق sk على خانة وسطى من الصندوق Si . وهذا يقتضي أنه من أجل j=k، فإن خانة خرج من Si لا يمكن حتى تؤثر على خانة وسطى من Sj.

تهدف هذه المعايير بمجملها إلى زيادة البعثرة في الخوارزمية.

عدد المراحل

تنبع قوة التعمية في نظام تشفير فيستيل من ثلاث نقاط تصميمية: عدد المراحل، التابع f، وطريقة استخراج المفاتيح. لنلق نظرة أولا على طريقة اختيار عدد المراحل.

حدثا كان عدد المراحل أكبر حدثا تعقد انجاز تحليل التعمية، حتى ولوكان التابع f، ضعيفا نسبيا. وبشكل عام يجب حتىقد يكون المعيار هوحتى يتم اختيار عدد المراحل بحيث يحتاج تحليل التعمية المعروف جهودا أكبر من تلك المصروفة على الهجوم بالبحث عن المفتاح بطريقة "الكسر الأعمى" البسيطة. تم استخدام هذا المعيار بالتأكدي أثناء تصميم خوارزمية DES. لا حظ Schneier بأنه من أجل خوارزمية DES ذات 16 فترةقد يكون الكسر باستخدام تحليل التعمية التفاضلي أقل كفاءة بقليل من الكسر بطريقة الكسر الأعمى 255 عملية. اذا تضمنت خوارزمية DES 15 فترة أوأقل فان تحليل التعمية التفاضلي يحتاج جهودا أقل من طريقة البحث عن المفتاح بطريقة الكسر الأعمى.

يعتبر هذا المعيار هاما لأنه يسمح بسهولة الحكم على قوة الخوارزمية وبالتالي مقارنة الخوارزميات. طالما غياب الاختراق بواسطة تحليل التعمية، يتم الحكم على قوة الخوارزمية من خلال طول المفتاح.

تصميم التابع f

يعتبر التابع f قلب نظام فيستيل للتشفير الكتلي. يعتمد هذا التابع، كما رأينا، على استخدام الصناديق S.وهذ هي حالة معظم أنظمة التشفير الكتلي المتناظر، كما سنرى في الفصل السادس. يمكننا على جميع الأحوال وضع ملاحظات عامة حول المعايير التصميمية للتابع f. بعد ذلك، سندرس بشكل خاص تصميم الصناديق S.

المعايير التصميمية للتابع f

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

يجب الأخذ بعين الاعتبار معايير أخرى عند تصميم التابع f. نرغب بأنقد يكون للخوارزمية خاصية تراكمية جيدة. لنتذكر بشكل عام حتى هذا يعني ما يلي: تغيير خانة ولج واحدة تؤدي إلى تغيير عدة خانات خرج. النسخة الأكثر تشددا من هذا هومايدعى المعيار التراكمي (أوالانهياري) الدقيق (SAC-Strict Avalanch Ctrterion) ، والتي تقول حتى أية خانة خرج j من الصندوق S يجب حتى تتغير باحتمال مقداره ½ عندما يتم عكس حالة أية خانة ولج مفردة، وذلك من أجل قيم I,j. ومع حتى المعيار SAC مخصص للصناديق S، إلا أنه يمكن تطبيق نفس المعيار على جميع F ككل. يعتبر هذا الموضوع هاما بشكل خاص عند الحديث عن تصميمات لا تحوي صناديق S.

هناك معيار آخر وهومعيار استقلالية الخانة (BIC-Bit Independence Criterion)، والتي تقوم بأنه يجب حتى تتغير خانات الخرج k,j بشكل مستقل عن بعضها عندما تنعكس أية خانة ولج مفردة i، وذلك من أجل جميع قيم k,j,i. يعمل المعياران BIC, SAC على تقوية فعالية تابع البعثرة.

تصميم صندوق S

يعتبر تصميم صندوق S من المواضيع الأكثر تطرقا للبحث في حقل التشفير الكتلي المتناظر فالنشرات التي تطرح هذا الموضع أكثر من حتى تعد. سنذكر هنا بعض المبادئ العامة.

نريد في الجوهر حتى ينعكس أي تغيير في شعاع الدخل للصندوق S على شكل تغير عشوائي في الخرج. يجب حتى تكون علاقة الخرج بالدخل غير خطية وأنقد يكون من الصعب التقريب إليها عن طريق معادلات خطية.

يعتبر الحجم من المميزات الواضحة لصندوق S. يملك صندوق S ذوالأبعاد m x m دخلا مكونا من m خانة. أبعاد صناديق S الخاصة بخوارزمية DES هيستة x 4، بينما صناديق S الخاصة بخوارزمية Blowfish، والتي سيتم شرحها لاحقا، تمتلك الأبعادثمانية x 32.

انظر أيضاً

• Triple DES
• Skipjack (cipher)
• Symmetric key algorithm

الهامش

المراجع

وصلات خارجية

• FIPS 46-3: The official document describing the DES standard (PDF); An older version in HTML
• COPACOBANA, a $10,000 DES cracker based on FPGAs by the Universities of Bochum and Kiel
• A Fast New DES Implementation in Software - Biham
• On Multiple Linear Approximations
• RFC4772 : Security Implications of Using the Data Encryption Standard (DES)
• A simple DES / Triple DES implementation documentation