شفرة هاستي بودنغ

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
الموسوعة الحرة

شيفرة هاستي بودنغ ( HPC ) هي شيفرة كتلية ذات حجم كتلة متغير، صممها ريتشارد شرويبل ، ولم تُوفق في المنافسة لاختيار معيار التشفير المتقدم الأمريكي (AES). تتميز هذه الشيفرة بعدد من الخصائص غير المألوفة لشيفرات الكتل: فحجم كتلة الإدخال وطول المفتاح متغيران، كما أنها تتضمن مُدخلًا إضافيًا يُسمى "التوابل" يُستخدم كمفتاح ثانوي غير سري. وكانت شيفرة هاستي بودنغ المرشح الوحيد لمعيار AES الذي صممه حصريًا خبراء التشفير الأمريكيون. [ 1 ] [ 2 ]

شفرة هاستي بودنغ متاحة للعموم ، [ 3 ] وتتوفر تطبيقات مفتوحة المصدر . [ 4 ]

الشفرة

تتكون شفرة Hasty Pudding من 5 شفرات فرعية مختلفة: [ 5 ]

HPC-Tiny0 – 35 بت
HPC-Short36 – 64 بت
HPC-Medium65-128 بت
HPC-Long129 – 512 بت
HPC-extended513+ بت

تستخدم جميع خوارزميات تشفير Hasty Pudding كلمات 64 بت داخليًا. صُممت هذه الخوارزمية للعمل على أجهزة 64 بت ، والتي يمكنها بسهولة إجراء عمليات بسيطة على كلمات 64 بت.

توسعة رئيسية

يمكن لخوارزمية التشفير "هاستي بودينغ" أن تأخذ مفتاحًا بأي عدد من البتات لأي من الخوارزميات الفرعية الخمس. وتستخدم الخوارزمية نفسها جدول مفاتيح مكونًا من 16384 بت (256 كلمة من 64 بت). ولاشتقاق جدول المفاتيح من المفتاح، تستخدم دالة توسيع المفتاح الخوارزمية التالية: [ 5 ]

  1. تُحدد الكلمات الثلاث الأولى، KX [0] و KX [1] و KX [2]، بناءً على ثوابت، والخوارزمية الفرعية، وطول المفتاح. تُحسب KX [1] بعملية ضرب؛ أما العمليات الأخرى فهي الجمع وإزاحة البتات.
  2. يتم تحديد كل كلمة متتالية، KX [ i ] من الكلمات الثلاث السابقة بواسطة صيغة تكرارية فعالة.
  3. تُجرى عملية XOR بين بتات المفتاح وبتات جدول المفاتيح، بدءًا من KX [0]، حتى يتم استخدام جميع بتات المفتاح. (تستخدم المفاتيح التي يزيد طولها عن 8192 بت إجراءً أكثر تعقيدًا).
  4. تُجرى عدة دورات على جدول المفاتيح. في كل مرة، تُطبَّق "دالة التحريك" على كل كلمة من كلمات جدول المفاتيح، بالتتابع. تستخدم دالة التحريك ثمانية متغيرات داخلية، و14 عملية منطقية ثنائية، و5 عمليات إزاحة ثنائية، و14 عملية جمع/طرح. كل استخدام لدالة التحريك يُعدِّل كلمة واحدة في جدول المفاتيح، بناءً على قيمتها السابقة، وقيم كلمات أخرى معينة، والمتغيرات الداخلية لدالة التحريك. (3 دورات إجمالاً هو العدد الافتراضي).

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

تستخدم كل خوارزمية فرعية من خوارزميات التشفير المختلفة، ولكن توجد بعض أوجه التشابه بينها. تُستخدم ثلاثة مدخلات لتحديد النص المشفر: النص الأصلي (مكون من عدة كلمات 64 بت بالإضافة إلى "جزء")، والتوابل (ثماني كلمات 64 بت، قيمتها الافتراضية 0)، وجدول المفاتيح. تتضمن العمليات داخل خوارزمية التشفير عملية دمج ، تجمع المتغيرات الداخلية بطرق مختلفة مع قيم من جدول المفاتيح والتوابل على فترات منتظمة. تستخدم خوارزمية HPC-Short تبديلين ثابتين بالإضافة إلى ذلك، بينما تتكون خوارزمية HPC-Tiny من العديد من الحالات الفرعية الخاصة.

تتضمن عملية فك التشفير التراجع عن خطوات التشفير واحدة تلو الأخرى. يمكن التراجع عن العديد من العمليات بسهولة (على سبيل المثال، يمكن التراجع عن العملية s0 = s0 + s1 بحساب s0 = s0 − s1 ). بينما تكون عمليات أخرى أكثر تعقيدًا. تتضمن بعض الأفكار المستخدمة ما يلي :    

  • يتم التراجع عن عملية مثل x = x ⊕ ( x >> 17) من خلال عملية من خطوتين: (1) x = x ⊕ ( x >> 17)، متبوعة بـ (2) x = x ⊕ ( x >> 34).
  • تستخدم هذه الشفرة عمليات بحث تعتمد على القيمة في جدول المفاتيح. يمكن التراجع عن هذه العمليات، لأن البحث يعتمد فقط على آخر 8 بتات من المتغير، وعندما يصبح من الضروري البحث عن القيمة من جدول المفاتيح في عملية فك التشفير، تكون آخر 8 بتات من القيمة عند نقطة سابقة معينة في الحساب قابلة للتنبؤ، حتى عندما لا يمكن التراجع عن جميع هذه العمليات بدون قيمة جدول المفاتيح. على سبيل المثال، إذا كان البحث عن k يعتمد على آخر 8 بتات من x ، فعندما نريد التراجع عن خطوة مثل x = x ⊕ ( k << 8)، يمكننا البحث عن k بملاحظة أن آخر 8 بتات من x لم تتغير بهذه العملية.

يمكن استخدام خوارزمية التشفير "هاستي بودينغ" لتشفير القيم ضمن نطاق لا يُترجم إلى سلاسل نصية ذات عدد صحيح من البتات؛ فعلى سبيل المثال، يمكنها تشفير عدد من 0 إلى N عن طريق إنتاج عدد آخر من 0 إلى N. ويتم ذلك باستخدام أصغر خوارزمية تشفير فرعية قادرة على التعامل مع المدخلات كسلسلة بتات، وتطبيقها على المدخلات كسلسلة بتات، بشكل متكرر، حتى يصبح الناتج ضمن النطاق الصحيح. [ 5 ]

أداء

ادّعى شرويبل أن خوارزمية التشفير "هاستي بودينغ" هي أسرع خوارزمية مرشحة لـ AES على بنية 64 بت؛ [ 6 ] وادّعى أنها أسرع بمرتين من أقرب منافسيها، DFC ، وثلاث مرات أسرع من الخوارزميات المرشحة الأخرى، وأن أداءها على جهاز 32 بت كان كافيًا. [ 6 ] لم تؤيد تعليقات أخرى هذا الرأي؛ فعلى سبيل المثال، صنّف تحليل شناير وآخرون خوارزمية "هاستي بودينغ" في المرتبة الرابعة (376 دورة) على جهاز 64 بت، بينما كان أداء خوارزميتي "راينديل" و "توفيش" تقديريًا فقط. [ 7 ] على معالج بنتيوم 32 بت ، قيّم شناير وآخرون تشفير "هاستي بودينغ" بـ 1600 دورة ساعة، ليحتل المرتبة العاشرة من بين 15 خوارزمية مرشحة. [ 7 ] لاحظ كل من شناير وآخرون، وشرويبل، أن سرعة التشفير ستتأثر بشكل كبير على جهاز 32 بت بسبب استخدامه المكثف لعمليات 64 بت، وخاصة عمليات إزاحة البتات. [ 3 ] [ 7 ]

تم تصنيف إعداد مفتاح تشفير Hasty Pudding على أنه بطيء نسبيًا؛ 120000 دورة على معالج Pentium. [ 7 ]

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

مزيد من العمل

لم تُسفر محاولات اختراق تشفير هاستي بودينغ إلا عن نتائج قليلة نسبيًا. في المراحل الأولى من تطوير معيار التشفير المتقدم (AES)، لاحظ ديفيد فاغنر أن فئات كبيرة نسبيًا من مفاتيح هاستي بودينغ متكافئة، إذ تؤدي جميعها إلى نفس جدول المفاتيح. [ 9 ] وقد توسع د'هالوين وآخرون في هذا الأمر، مشيرين إلى أنه بالنسبة للمفاتيح ذات 128 بت، فإن حوالي 2^ 120 مفتاحًا هي مفاتيح ضعيفة ، ولكل منها 2^ 30 مفتاحًا مكافئًا. [ 10 ] واستجابةً لهذا الهجوم، عدّل شرويبل خوارزمية توسيع المفاتيح لتشمل خطوة إضافية. [ 5 ]

على الرغم من قلة التحليلات التشفيرية، وُجهت انتقادات لشفرة "هاستي بودينغ" لصعوبة فهم تصميمها وافتقارها إلى أساس متين من نتائج الأبحاث. [ 9 ] [ 11 ] وقد عرض شرويبل زجاجة من شمبانيا دوم بيرينيون لأفضل ورقة بحثية تُقدم تقدماً في تطوير شفرة "هاستي بودينغ". [ 3 ] إلا أنها لم تصل إلى المرحلة الثانية من الترشيح لجائزة معيار التشفير المتقدم (AES). [ 12 ]

تعتبر شيفرة Hasty Pudding أول شيفرة كتلة قابلة للتعديل . [ 13 ]

انظر أيضاً

مراجع

  1. ↑ إيلي بيهام ، ملاحظة حول مقارنة مرشحي AES ، أبريل 1999، تعليق عام على AES.
  2. ↑ سوزان لانداو ، أمن الاتصالات للقرن الحادي والعشرين: معيار التشفير المتقدم ، إشعارات جمعية التسويق الأمريكية، المجلد 47، العدد 4، 2000.
  3. 1 2 3 ريتش شرويبل وهيلاري أورمان، نظرة عامة على شيفرة هاستي بودنغ ، يوليو 1998.
  4. ↑ iscgar/hasty-pudding على GitHub .
  5. 1 2 3 4 شرويبل، ريتش (يونيو 1998)، مواصفات تشفير هاستي بودنغ (طبعة منقحة مايو 1999  )، مؤرشفة من الأصل في 17 يوليو 2011 ، تم استرجاعها في 10 يونيو 2009
  6. 1 2 ريتش شرويبل، شفرة بودنغ هاستي: بعد عام ، تم الاطلاع عليه في 9-01-2008
  7. 1 2 3 4 بروس شناير ، جون كيلسي ، دوغ وايتينغ ، ديفيد فاغنر ، كريس هول ، ونيلز فيرغسون ، مقارنة أداء طلبات AES ، المؤتمر الثاني لمرشحي AES، 1999.
  8. ↑ إيمانويل دانيليوك، تعليق عام على مرشحي AES ، فبراير 1999.
  9. 1 2 ديفيد واغنر، مفاتيح مكافئة للحوسبة عالية الأداء ، حديث جلسة راب في المؤتمر الثاني لجمعية هندسة التشفير، روما ، مارس 1999.
  10. ↑ كارل دالوين، وجيرت بيجينس، وبارت برينيل ، وفنسنت ريمين ، المفاتيح المكافئة لـ HPC ، التقدم في علم التشفير – وقائع ASIACRYPT 1999، 1999.
  11. ↑ أوليفييه بودرون، هنري جيلبرت ، لويس جرانبولان، هيلينا هاندشوه ، أنطوان جو ، فونج نجوين ، فابريس نويلهان، ديفيد بوينتشيفال ، توماس بورنين، غيوم بوبارد، جاك ستيرن ، وسيرج فوديناي ، تقرير عن مرشحي AES ، مؤتمر AES الثاني، مارس 1999.
  12. ↑ جيمس نيشفاتال، إيلين باركر، لورانس باشام، ويليام بور، موريس دوركين، جيمس فوتي، وإدوارد روباك، تقرير عن تطوير معيار التشفير المتقدم (AES) ، إصدار رسمي من المعهد الوطني للمعايير والتكنولوجيا ، 2 أكتوبر 2000.
  13. ↑ موسى ليسكوف، رونالد ريفست ، وديفيد واغنر ، تشفيرات الكتل القابلة للتعديل ، في التقدم في علم التشفير - وقائع مؤتمر CRYPTO '02، 2002.