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

التشفير الكتلي Block cipher تعتمد جميع خوارزميات التشفير الكتلي المتناظر المستخدمة حاليا على البنية المسماة تشفير فايستل الكتلي (Feistel Block 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

أخذ فيستيل هذه الصعوبات بعين الاعتبار، وأشار إلى حتى المطلوب هوالاقتراب من نظام التشفير الكتلي المثالي ذوعدد الخانات 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 خانة.

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

شفرة فايستل

اقترح فيستيل أنه يمكن تطوير تشفير تبديل الحروف البسيط عن طريق تطبيق مفهوم ضرب التشفير، حيث يمكن تطبيق تشفيرين متتالين أوأكثر بحيث تكون النتيجة النهائية، من وجهة نظر التعمية، أقوى من أي من مركباتها. وفي الحقيقة ما لدينا هوتعبير عن تطبيق عملي لمقترح كلود شانون بانتاج تشفير مؤلف من تعاقب تابعي البعثرة والنشر (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 خرجا ثابتا (على سبيل المثال واحدات) بعض النظر عن قيمة دخليه. لاحظ حتى المعادلات السابقة لا تزال سارية المفعول.

انظر أيضاً

فهم التعمية
Block cipher modes of operation
Block cipher security summary
Confusion and diffusion
Pseudorandom permutation
Advanced Encryption Standard process
Topics in cryptography
Disk encryption

المراجع

د. م. سائد محمود الناظر، اعداد (2005). التعمية وأمن الشبكات – الجزء الأول (الطبعة الأولى ed.). سوريا: شعاع للنشر والعلوم.
M. Liskov, R. Rivest, and D. Wagner, "Tweakable Block Ciphers", Crypto 2002 PDF.