الأفعى (شفرة)

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

سيربنت هي خوارزمية تشفير متناظرة المفتاح ، وصلت إلى المرحلة النهائية في مسابقة معيار التشفير المتقدم (AES) ، حيث احتلت المرتبة الثانية بعد خوارزمية رينديل . [ 2 ] صمم سيربنت كل من روس أندرسون ، وإيلي بيهام ، ولارس كنودسن . [ 3 ]

على غرار خوارزميات التشفير الأخرى المُقدمة من AES ، تتميز خوارزمية Serpent بحجم كتلة يبلغ 128 بت، وتدعم أحجام مفاتيح تبلغ 128 أو 192 أو 256 بت. [ 4 ] تعتمد هذه الخوارزمية على شبكة استبدال-تبديل من 32 جولة، تعمل على كتلة مكونة من أربع كلمات ، كل منها 32 بت. في كل جولة، يتم تطبيق أحد صناديق الاستبدال الثمانية (S-boxes) المكونة من 4 بت إلى 4 بت، 32 مرة بالتوازي. صُممت Serpent بحيث يمكن تنفيذ جميع العمليات بالتوازي ، باستخدام شرائح 32 بت . هذا يُعظم التوازي، كما يسمح بالاستفادة من أعمال تحليل التشفير المكثفة التي أُجريت على خوارزمية DES .

اتخذ برنامج Serpent نهجًا متحفظًا في مجال الأمن، فاختار هامش أمان كبير: إذ رأى المصممون أن 16 جولة كافية ضد أنواع الهجمات المعروفة، لكنهم حددوا 32 جولة كضمان ضد أي اكتشافات مستقبلية في تحليل الشفرات. [ 5 ] صنّف تقرير المعهد الوطني للمعايير والتكنولوجيا (NIST) الرسمي حول مسابقة معيار التشفير المتقدم (AES) برنامج Serpent ضمن فئة البرامج ذات هامش الأمان العالي، مثل برنامجي MARS و Twofish ، وذلك على عكس هامش الأمان الكافي لبرنامجي RC6 وRijndael (المعتمد حاليًا كمعيار AES). [ 2 ] في التصويت النهائي، حصل برنامج Serpent على أقل عدد من الأصوات السلبية بين المتأهلين للتصفيات النهائية، لكنه احتل المركز الثاني إجمالًا لأن برنامج Rijndael حصل على عدد أكبر بكثير من الأصوات الإيجابية، وكان العامل الحاسم هو أن Rijndael يسمح بتنفيذ برمجي أكثر كفاءة.

خوارزمية تشفير سيربنت متاحة للعموم ولم تُسجّل كبراءة اختراع . [ 6 ] الشفرة المرجعية متاحة للعموم، والشفرة المُحسّنة مرخصة بموجب رخصة جنو العمومية (GPL) . [ 7 ] لا توجد أي قيود أو شروط على استخدامها. ونتيجةً لذلك، يُمكن لأي شخص دمج سيربنت في برامجه (أو في تطبيقات الأجهزة) دون دفع رسوم ترخيص.

الجدول الزمني الرئيسي

يتألف جدول مفاتيح Serpent من ثلاث مراحل رئيسية. في المرحلة الأولى، تتم تهيئة المفتاح بإضافة حشو إذا لزم الأمر. ويتم ذلك لجعل المفاتيح القصيرة تُطابق مفاتيح طويلة بطول 256 بت، حيث تُضاف بتة "1" واحدة إلى نهاية المفتاح القصير متبوعة ببتات "0" حتى يُطابق المفتاح القصير طول المفتاح الطويل. [ 4 ]

في المرحلة التالية، تُشتق "المفاتيح الأولية" باستخدام المفتاح المُهيأ مسبقًا. تُجرى عملية XOR على أجزاء المفتاح ذات 32 بت، ثم تُجرى عملية XOR على نسبة FRAC (وهي جزء من النسبة الذهبية) ومؤشر الجولة مع أجزاء المفتاح، ويتم تدوير نتيجة عملية XOR إلى اليسار بمقدار 11. أُضيفت نسبة FRAC ومؤشر الجولة لتحقيق توزيع متساوٍ لبتات المفتاح خلال الجولات. [ 4 ]

وأخيرًا، تُشتق "المفاتيح الفرعية" من "المفاتيح الأولية" التي تم إنشاؤها مسبقًا. وينتج عن ذلك ما مجموعه 33 "مفتاحًا فرعيًا" بطول 128 بت. [ 4 ]

في النهاية، يتم وضع مفتاح الجولة أو "المفتاح الفرعي" في "التبديل الأولي IP" لوضع بتات المفتاح في العمود الصحيح. [ 4 ]

الجدول الزمني الرئيسي في لغة C

#define FRAC 0x9e3779b9 // الجزء الكسري من النسبة الذهبية #define ROTL(A, n) ((A) << n | (A) >> 32-n)uint32_t key [ 8 ]; // مفتاح مُدخل من المستخدم uint32_t subkey [ 33 ][ 4 ]; // مفاتيح التقريب const uint8_t S [ 8 ][ 16 ] = {}; // صناديق الاستبدال/* جدول المفاتيح: الحصول على المفاتيح المسبقة */ void get_pre ( uint32_t w [ 4 * 33 ], const uint32_t k [ 8 ]) { uint32_t x [ 4 * 33 + 8 ]; for ( int i = 0 ; i < 8 ; i ++ ) x [ i ] = k [ i ]; for ( int i = 8 ; i < 140 ; ​​i ++ ) { x [ i ] = ROTL ( x [ i -8 ] ^ x [ i -5 ] ^ x [ i -3 ] ^ x [ i -1 ] ^ FRAC ^ ( i -8 ), 11 ); w [ i -8 ] = x [ i ]; } }/* جدول المفاتيح: الحصول على المفاتيح الفرعية */ void get_sk ( const uint32_t w [ 4 * 33 ], uint32_t ( * sk )[ 4 ]) {uint8_t i , p , j , s , k ; for ( i = 0 ; i < 33 ; i ++ ) { p = 32 + 3 - i ; for ( j = 0 ; j < 4 ; j ++ ) sk [ i ][ j ] = 0 ; for ( k = 0 ; k < 32 ; k ++ ) { s = S [ p % 8 ][(( w [ 4 * i + 0 ] >> k ) & 0x1 ) << 0 | (( w [ 4 * i + 1 ] >> k ) & 0x1 ) << 1 | (( w [ 4 * i + 2 ] >> k ) & 0x1 ) << 2 | (( w [ 4 * i + 3 ] >> k ) & 0x1 ) << 3 ]; for ( j = 0 ; j < 4 ; j ++ ) { sk [ i ][ j ] |= (( s >> j ) & 0x1 ) << k ; } } } }void key_schedule () { uint32_t w [ 4 * 33 ]; get_pre ( w , key ); get_sk ( w , subkey ); }

صناديق S

صناديق الاستبدال في Serpent عبارة عن تباديل مكونة من 4 بتات ، وتخضع للخصائص التالية:

  • لن يؤدي اختلاف الإدخال بمقدار بت واحد إلى اختلاف الإخراج بمقدار بت واحد، وتكون احتمالية الخاصية التفاضلية 1:4 أو أقل. [ 8 ]
  • تتراوح احتمالية الخصائص الخطية بين 1:2 و 1:4، وتتراوح احتمالية العلاقة الخطية بين بتات الإدخال والإخراج بين 1:2 و 1:8. [ 8 ]
  • إن الترتيب غير الخطي لبتات الإخراج كدالة لبتات الإدخال هو 3. ومع ذلك، فقد تم العثور على بتات إخراج يكون ترتيبها كدالة لبتات الإدخال هو 2 فقط. [ 8 ]

تم إنشاء صناديق الاستبدال (s-boxes) الخاصة بـ Serpent استنادًا إلى صفوف صناديق الاستبدال (s-boxes) الخاصة بـ DES البالغ عددها 32 صفًا . وتم تحويل هذه الصناديق عن طريق تبديل المدخلات، ثم تم تخزين المصفوفات الناتجة ذات الخصائص المطلوبة كصناديق استبدال (s-boxes) خاصة بـ Serpent. تكررت هذه العملية حتى تم العثور على 8 صناديق استبدال (s-boxes) إجمالاً. استُخدم المفتاح التالي في هذه العملية: "sboxesforserpent". [ 4 ]

التباديل والتحويلات

التبديل الأولي (IP)

يعمل التبديل الأولي على 128 بت في كل مرة عن طريق تحريك البتات.

for i in 0 .. 127 swap ( bit ( i ), bit (( 32 * i ) % 127 ) )

التبديل النهائي (FP)

يعمل التبديل النهائي على 128 بت في كل مرة عن طريق تحريك البتات.

for i in 0 .. 127 swap ( bit ( i ), bit (( 4 * i ) % 127 ) )

التحويل الخطي (LT)

تتضمن هذه العملية عمليات XOR، وإزاحة البتات إلى اليسار، وتدوير البتات إلى اليسار. وتُجرى هذه العمليات على 4 كلمات من 32 بت.

// المدخلات هي نتيجة مزج المفاتيح واستبدالها. for ( short i = 0 ; i < 4 ; i ++ ) { X [ i ] = S [ i ][ B [ i ] ^ K [ i ]]; }// Linear transformation.X[0]=ROTL(X[0],13);X[2]=ROTL(X[2],3);X[1]=X[1]^X[0]^X[2];X[3]=X[3]^X[2]^(X[0]<<3);X[1]=ROTL(X[1],1);X[3]=ROTL(X[3],7);X[0]=X[0]^X[1]^X[3];X[2]=X[2]^X[3]^(X[1]<<7);X[0]=ROTL(X[0],5);X[2]=ROTL(X[2],22);// The output becomes the new state.for(shorti=0;i<4;i++){B[i+1]=X[i];}

Rijndael vs. Serpent

رينديل هي شبكة استبدال-تحويل خطي تتكون من عشر أو اثنتي عشرة أو أربع عشرة جولة، حسب حجم المفتاح، وبأحجام مفاتيح 128 بت أو 192 بت أو 256 بت، يتم تحديدها بشكل مستقل. أما سيربنت فهي شبكة استبدال-تبديل تتكون من اثنتين وثلاثين جولة، بالإضافة إلى تبديل أولي ونهائي لتبسيط التنفيذ الأمثل. تتكون وظيفة الجولة في رينديل من ثلاثة أجزاء: طبقة غير خطية، وطبقة مزج خطي، وطبقة XOR لمزج المفاتيح. بينما تتكون وظيفة الجولة في سيربنت من XOR لمزج المفاتيح، واثنين وثلاثين تطبيقًا متوازيًا لنفس صندوق الاستبدال 4×4، وتحويل خطي، باستثناء الجولة الأخيرة، حيث يحل XOR آخر لمزج المفاتيح محل التحويل الخطي. تستخدم الطبقة غير الخطية في رينديل صندوق استبدال 8×8، بينما تستخدم سيربنت ثمانية صناديق استبدال مختلفة 4×4. بفضل 32 جولة، يتمتع خوارزمية سيربنت بهامش أمان أعلى من خوارزمية رايندال؛ ومع ذلك، فإن رايندال، بعشر جولات، أسرع وأسهل في التطبيق للكتل الصغيرة. [ 9 ] لذا، تم اختيار رايندال كفائز في مسابقة معيار التشفير المتقدم (AES).

سيربنت-0 ضد سيربنت-1

عُرضت النسخة الأصلية من خوارزمية Serpent، Serpent-0، في ورشة العمل الخامسة حول التشفير البرمجي السريع ، ولكن تم تقديم نسخة مُعدّلة منها، Serpent-1، إلى مسابقة AES. وتناقش ورقة التقديم الخاصة بمسابقة AES التغييرات، والتي تشمل اختلافات في جدولة المفاتيح.

حماية

إن هجوم XSL ، إن نجح، سيُضعف خوارزمية Serpent (وإن لم يكن بنفس القدر الذي أضعف به خوارزمية Rijndael التي أصبحت فيما بعد AES ). مع ذلك، يعتقد العديد من محللي التشفير أنه بمجرد أخذ اعتبارات التنفيذ في الحسبان، سيكون هجوم XSL أكثر تكلفة من هجوم القوة الغاشمة .

في عام 2000، قدمت ورقة بحثية من تأليف كوهنو وآخرون هجومًا من نوع "اللقاء في المنتصف" ضد 6 من أصل 32 جولة من لعبة سيربنت، وهجومًا معززًا من نوع "البوميرانج" ضد 9 من أصل 32 جولة في لعبة سيربنت. [ 10 ]

يُقدّم هجومٌ نفّذه إيلي بيهام وأور دانكلمان وناثان كيلر عام 2001 هجومًا تحليليًا خطيًا للشفرات ، نجح في كسر 10 جولات من أصل 32 جولة من خوارزمية Serpent-128 باستخدام 2118 نصًا عاديًا معروفًا و 289 وقتًا، و11 جولة من خوارزمية Serpent-192/256 باستخدام 2118 نصًا عاديًا معروفًا و 2187 وقتًا. [ 11 ]

أشارت ورقة بحثية نُشرت عام 2009 إلى أن الرتبة غير الخطية لصناديق S-boxes في خوارزمية Serpent لم تكن 3 كما ادعى المصممون. وبالتحديد، كان لأربعة عناصر رتبة 2. [ 8 ]

تمكن هجوم شنه هونغجون وو وهواكسيونغ وانغ وفونغ ها نغوين عام 2011، باستخدام التحليل الخطي للتشفير، من كسر 11 جولة من خوارزمية Serpent-128 باستخدام 2116 نصًا عاديًا معروفًا، و 2107.5 من الوقت، و 2104 من الذاكرة. [ 1 ]

تصف الورقة البحثية نفسها هجومين قادرين على اختراق 12 جولة من خوارزمية Serpent-256. يتطلب الهجوم الأول 2118 نصًا أصليًا معروفًا، و 2228.8 من الوقت، و 2228 من الذاكرة. أما الهجوم الثاني فيتطلب 2116 نصًا أصليًا معروفًا، و 2121 من الذاكرة، ولكنه يتطلب أيضًا 2237.5 من الوقت.

انظر أيضاً

  • Tiger – دالة تجزئة من نفس المؤلفين

الحواشي

  1. 1 2 هواكسيونغ وانغ، وهونغجون وو، وفونغ ها نغوين (2011). "تحسين الخوارزمية 2 في التحليل الخطي متعدد الأبعاد للتشفير" (ملف PDF) . أمن المعلومات والخصوصية . سلسلة محاضرات في علوم الحاسوب. المجلد  6812. ACISP 2011. الصفحات 61-74 . doi : 10.1007/978-3-642-22497-3_5 . ISBN  978-3-642-22496-6تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 14 أبريل 2017. تم الاطلاع عليه بتاريخ 25 سبتمبر 2014 .
  2. 1 2 نيشفاتال، ج.؛ باركر، إ.؛ باشام، ل.؛ بور، و.؛ دوركين، م.؛ فوتي، ج.؛ روباك، إ. (مايو 2001). "تقرير عن تطوير معيار التشفير المتقدم (AES)" . مجلة البحوث للمعهد الوطني للمعايير والتكنولوجيا . 106 (3): 511-577 . doi : 10.6028/jres.106.023 . ISSN 1044-677X . PMC 4863838. PMID 27500035 .   
  3. ↑ "الصفحة الرئيسية لـ Serpent" .
  4. 1 2 3 4 5 6 روس ج. أندرسون (23 أكتوبر 2006). "سيربنت: خوارزمية تشفير كتلية مرشحة لمعيار التشفير المتقدم" . مختبر الحاسوب بجامعة كامبريدج . تم الاطلاع عليه في 14 يناير 2013 .
  5. ↑ "serpent.pdf" (ملف PDF) . تم الاطلاع عليه بتاريخ 25 أبريل 2022 .
  6. ↑ برنامج Serpent يحمل مفتاح أمن الإنترنت – الإعلان عن المتأهلين للتصفيات النهائية في مسابقة التشفير العالمية (1999)
  7. ↑ سيربنت – خوارزمية تشفير كتلية مرشحة لمعيار التشفير المتقدم (AES ): "أصبحت خوارزمية سيربنت متاحة الآن للاستخدام العام بالكامل، ولا نفرض أي قيود على استخدامها. وقد أُعلن عن ذلك في 21 أغسطس في المؤتمر الأول لمرشحي معيار التشفير المتقدم. تخضع التطبيقات المُحسّنة في حزمة التقديم الآن لرخصة جنرال بابليك (GPL)، على الرغم من أن بعض التعليقات في الكود لا تزال تشير إلى خلاف ذلك. نرحب باستخدامكم لخوارزمية سيربنت في أي تطبيق. إذا استخدمتموها، فنرجو إبلاغنا بذلك!" (1999)
  8. 1 2 3 4 بهوبيندرا سينغ؛ ليكسي ألكسندر؛ سانجاي بورمان (2009). "حول العلاقات الجبرية لصناديق S-boxes في Serpent" (PDF) .
  9. ↑ بروس شناير؛ جون كيلسي؛ دوغ وايتينغ؛ ديفيد فاغنر؛ كريس هول. نيلز فيرغسونك؛ تادايوشي كوهنو؛ مايك ستاي (2000). "التعليقات النهائية لفريق توفيش على اختيار AES" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 2 يناير 2010. تم الاطلاع عليه في 19 يناير 2015 .
  10. ↑ كوهنو، تادايوشي؛ كيلسي، جون؛ شناير، بروس (2000). "تحليل تشفيري أولي لخوارزمية سيربنت ذات عدد الجولات المخفّض" . المؤتمر الثالث لمعايير التشفير المتقدمة المرشحة، 13-14 أبريل 2000، نيويورك، نيويورك، الولايات المتحدة الأمريكية . المعهد الوطني للمعايير والتكنولوجيا. الصفحات 195-211 . 
  11. ↑ بيهام، إيلي ؛ دانكلمان، أور ؛ كيلر، ناثان (2001). "التحليل الخطي لخوارزمية Serpent ذات الجولات المخفضة". في ماتسوي، ميتسورو (محرر). التشفير البرمجي السريع، ورشة العمل الدولية الثامنة، FSE 2001، يوكوهاما، اليابان، 2-4 أبريل 2001، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد 2355. سبرينغر. الصفحات 16-27 . doi : 10.1007/3-540-45473-X_2 . ISBN   978-3-540-43869-4.

للمزيد من القراءة