چکیده ١. مقدمه

در این مقاله، با استفاده از الگوریتمهای ﮊنتیک١ و

براساس گراف حاصل از بازنمایی تفاضلی الگوریتم رمز سرپنت٢، شیوهای جهت پیداکردن یک مشخصه تفاضلی٣ k دوری برای این الگوریتم رمز پیشنهاد میگردد. بدین منظور، ساختار کروموزومها، چگونگی تولید جمعیت اولیه، تابع برازندگی، عملگر آمیزش و عملگر جهش الگوریتم ﮊنتیک پیشنهادی معرفی میشود.

همچنین، نتایج آزمایشات انجام شده براساس این شیوه جهت پیداکردن یک مشخصه ٥ دوری مناسب برای تحلیل تفاضلی الگوریتم رمز سرپنت ٦ دوری ارائه میشود.
مقایسه مشخصههای بدست آمده توسط شیوه پیشنهادی با مشخصههای ٥ دوری منتشر شده در ]١[، ]٢[، ]٣[، ]٤[ و ]٥[
عملکرد مناسب این شیوه را تایید میکند.

ایده مطرح شده در این مقاله قابل تعمیم به سایر الگوریتمهای رمز قطعهای میباشد.

واﮊگان کلیدی: الگوریتمهای ﮊنتیک، مشخصه تفاضلی، الگوریتم رمز سرپنت

۱ Genetic Algorithms 2 Serpent 3 Differential Characteristic

تحلیل تفاضلی٤ روشی است که اثر تفاضلات خاص در زوج متنهای واضح را بر روی تفاضل زوج متنهای رمزشده متناظر با آنها بررسی میکند ]٦. [ روش تحلیل تفاضلی در دو مرحله طراحی حمله و اجرای حمله انجام میشود. در مرحله طراحی حمله، تحلیلگر سعی میکند با استفاده از ویژگیها و نقاط ضعف الگوریتم رمز، یک مشخصه تفاضلی با احتمال بالا بدست آورد. در مرحله اجرای حمله، تحلیلگر با استفاده از این مشخصه به هر کلید ممکن یک احتمال نسبت میدهد و کلید با بیشترین احتمال را تعیین میکند. در زمینه تحلیل تفاضلی الگوریتمهای رمز کارهای متعددی انجام شده است.

در ]٤[، از روشهای الگوریتمی مانند برنامهریزی پویا٥ و بازگشت به عقب٦ جهت پیداکردن یک مشخصه مناسب برای الگوریتم رمز قطعهای سرپنت ]٧[ استفاده شده است.
پیداکردن مشخصه مطلوب با استفاده از روشهای فوق به علت نیاز به تعیین توابع محدودکننده جستجو توسط تحلیلگر، دارای محدودیتهایی از قبیل حذف ناخواسته

۴ Differential Cryptanalysis 5 Dynamic Programming 6 Backtracking

جوابهای مطلوب، پیچیدگی محاسباتی بالا و وابستگی به شخص تحلیلگر میباشد. در ]٥[ برای رفع مشکلات فوق، مدل بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای سرپنت ارائه شده است. در این مدل، از ترکیب گرافهای متناظر با هر یک از اجزاﺀ الگوریتم رمز سرپنت، یک گراف جهتدار وزندار بدست میآید. با استفاده از این گراف، مساله پیداکردن بهترین مشخصه برای الگوریتم رمز به مسئله پیداکردن کوتاهترین مسیر در گراف جهتدار تبدیل میشود. در ]٥[ برای پیداکردن مسیر مناسب در این گراف، از شیوه بهینهسازی اجتماع مورچگان ]٨[ استفاده شده است.

در این مقاله، با استفاده از الگوریتمهای ﮊنتیک و براساس گراف حاصل از بازنمایی تفاضلی الگوریتم رمز سرپنت، شیوهای جهت پیداکردن یک مشخصه تفاضلی مناسب برای این الگوریتم رمز پیشنهاد میگردد. استفاده از این شیوه باعث افزایش کارآیی در پیداکردن مسیر مناسب در گراف بازنمایی میشود، به طوری که زمان پیداکردن یک مشخصه مناسب برای الگوریتم رمز سرپنت در مقایسه با ]٥[ به طور قابل ملاحظهای کاهش مییابد.

در ادامه این مقاله، در بخش دوم الگوریتم رمز سرپنت و در بخش سوم ساختار الگوریتمهای ﮊنتیک به طور مختصر معرفی میشود. در بخش چهارم، چگونگی استفاده از الگوریتمهای ﮊنتیک جهت پیدا کردن یک مشخصه تفاضلی k دوری برای الگوریتم رمز سرپنت شرح داده میشود. بدین منظور، ساختار کروموزومها، چگونگی تولید جمعیت اولیه، تابع برازندگی، عملگر آمیزش و عملگر جهش الگوریتم ﮊنتیک پیشنهادی معرفی میشود.

در بخش پنجم، نتایج آزمایشات انجام شده جهت پیداکردن یک مشخصه ٥ دوری مناسب برای تحلیل تفاضلی الگوریتم رمز سرپنت ٦ دوری ارائه میشود. در بخش ششم هم در مورد نتایج حاصل بحث به عمل میآید و پیشنهاداتی برای ادامه این تحقیق مطرح میشود.

٢. الگوریتم رمز سرپنت

سرپنت ]٧[ یک شبکه جانشینی- جایگشتی ٣٢ دوری با اندازه قطعه ١٢٨ بیتی است. ساختار رمز شامل جایگشت اولیه IP ، ٣٢ دور و جایگشت نهایی FP است. در سرپنت
ˆ ˆ
از ٣٣ زیرکلید ١٢٨ بیتی K 0 تا K 32 استفاده میشود.
جایگشت اولیه IP برروی متن واضح P اعمال میشود
وˆ۰ که ورودی به اولین دور است را نتیجه میدهد. دورها
B

از ٠ تا ٣١ شمارهگذاری میشوند. بنابراین دور ٠ اولین دور و دور ٣١ آخرین دور است. خروجی اولین دور (دور ٠) با
ˆ ˆ
B1 ، خروجی دومین دور (دور ١) با B2 و خروجی دور i
ˆ
با Bi۱ نمایش داده میشود.
در الگوریتم رمز سرپنت از هشت S-box با ورودی و
خروجی چهار بیتیS0 تا S7 استفاده میشود. در هر تابع

دور Ri (i ∈{۰,…,۳۱}) ، تنها از تکرار یک S-box مشخص
استفاده میشود. به عنوان مثال، R0 از ٣٢ نسخه ازS0
استفاده میکند. هر نسخه ازS0 چهار بیت از ˆ ˆ
B0 ⊕ K0 را
به عنوان ورودی میگیرد و چهار بیت از بردار میانی را به

عنوان خروجی برمیگرداند. سپس بردار میانی حاصل با
ˆ
استفاده از تبدیل خطی تغییر یافته و بهB1 تبدیل میشود.
به طور مشابهR1 نیز ٣٢ نسخه ازS1 را به طور موازی
ˆ ˆ
رویB1 ⊕ K1 اعمال میکند و بردار میانی حاصل را با
ˆ
استفاده از تبدیل خطی تغییر میدهد تا B2 حاصل شود.
هر S-box دقیقاﹰ در چهار دور استفاده میشود. بنابراین
پس از استفاده از S7 در دور ٧، مجدداﹰS0 در دور ٨ ، S1
در دور ٩ و … استفاده میشود.
آخرین دور (دور ٣١) با سایر دورها اندکی تفاوت
دارد. در این دور ابتداS7 ˆ ˆ اعمال
بر رویB31 ⊕ K31
ˆ
میشود، سپس به جای اعمال تبدیل خطی، K32 با نتیجه
ˆ ˆ
فوق XOR میشود تاB32 حاصل شود. در نهایت B32
با اعمال جایگشت FP برروی آن به متن رمزشده C

تبدیل میشود.

ساختار رمز سرپنت را میتوان به صورت زیر توصیف کرد:

: IP(P) ˆ
B0
ˆ ˆ
Bi۱ : Ri (Bi )
ˆ
که C : FP(B32 )

i  ۰,…,۳۰ ˆ ˆ
Ri ( X )  LT (Si ( X ⊕ Ki ))
i  ۳۱ ˆ ˆ ˆ
Ri ( X )  Si ( X ⊕ Ki ) ⊕ K32
در فرمولهای فوق، ˆi از ٣٢ بار تکرار موازی i
S S mod8

بدست میآید و LT هم تبدیل خطی است.