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

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

انظر أيضاً


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

المراجع

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

وصلات خارجية