بخشی از مقاله
چکیده:
تحلیل تفاضلی روشی متداول برای ارزیابی الگوریتم های رمز قطعهای است. جهت یافتن بهترین مشخصه تفاضلی در یک الگوریتم رمز، مدل بازنمایی عملکرد تفاضلی الگوریتم رمز قطعه ای توسط مؤلف ارائه شده است. توسط این مدل، الگوریتم رمز مورد نظر با یک گراف جهت دار وزن دار بازنمایی میشود و یافتن بهترین مشخصه تفاضلی معادل یافتن کوتاهترین مسیر بین دو گره مشخص در گراف حاصل است. در این مقاله، شبکه عصبی هاپفیلد برای یافتن بهترین مسیر در گراف حاصل از بازنمایی الگوریتم رمز قطعهای بکارگرفته شده است. مقایسه نتایج حاصل از بکارگیری مدل بازنمایی عملکرد تفاضلی در این مقاله با مشخصههای منتشر شده از الگوریتم رمز سرپنت در مقالات دیگر نشان میدهد در شش مورد نتایج حاصل از بکارگیری مدل بازنمایی عملکرد تفاضلی بهتر از نتایج منتشر شده در مقالات دیگر است و در دو مورد احتمال مشخصه تفاضلی بدست آمده برابر احتمال مشخصههای نظیر در مقالات دیگر میباشد. نتایج بدست آمده در این مقاله در مقایسه با مشخصه های منتشر شده در مقالات دیگر نشان دهنده کارایی مدل بازنمایی عملکرد تفاضلی در طراحی حمله مبتنی بر تحلیل تفاضلی است.
کلمات کلیدی : تحلیل تفاضلی ، ساختار جانشینی-جایگشتی، الگوریتم رمز قطعهای سرپنت، شبکه عصبی هاپفیلد.
١- مقدمه
تحلیل تفاضلی در سال ٩٠ توسط بیهام و شامیر ابداع شد.[7] این روش تحلیل در دو مرحله طراحی حمله و اجرای حمله انجام میشود. در مرحله طراحی حمله، تحلیلگر با بکارگیری ویژگیها و نقاط ضعف الگوریتم رمز بدنبال یافتن یک مشخصه تفاضلی با احتمال بالا است. در مرحله اجرای حمله، تحلیلگر بایستی به اندازه کافی زوج متن رمزشده با تفاضل بدست آمده در مرحله طراحی را جمع آوری کرده و توسط آنها کلیدهای موثر در مشخصه را با انجام یک شیوه شمارش بدست آورد.
در ]١[ روشهای الگوریتمی مانند برنامه ریزی پویا و بازگشت به عقب برای دست یافتن به یک مشخصه مناسب برای طراحی حمله مبتنی بر تحلیل تفاضلی مورد بررسی قرار گرفت. اگر چه در ]١[ نتایج مناسبی بدست آمده است، اما بعلت تعیین توابع محدود کننده جستجو توسط تحلیلگر ، محدودیت هایی از جمله : حذف ناخواسته جوابهای مطلوب، پیچیدگی محاسباتی بالا، وابستگی به شخص تحلیلگر وجود دارد . در ]٢[ و [17] برای فائق آمدن به این محدودیتها مدل بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای ارائه شد. در این مدل هریک از اجزاﺀ الگوریتم رمز توسط یک گراف جهت دار وزن دار نشان داده میشود. از ترکیب گرافهای متناظر با هر یک از اجزاﺀ یک الگوریتم رمز قطعهای، یک گراف جهت دار وزن دار بدست میآید. درنتیجه، جهت یافتن یک مشخصه تفاضلی k دوری ، یک گراف k٢ سطحی بدست آمده و مساله یافتن بهترین مشخصه برای این الگوریتم رمز معادل یافتن مسیری از سطح اول به سطح انتهایی این گراف است، بطوریکه جمع مسیرهای آن کمترین مقدار ممکن باشد.
در این مقاله ابتدا الگوریتم رمز قطعهای سرپنت و مدل بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای بطور خلاصه معرفی میشود. سپس نحوه بکارگیری شبکه عصبی در یافتن مسیر مناسب در گراف حاصل از بازنمایی الگوریتم رمز تشریح شده و در ادامه مشخصه های تفاضلی بدست آمده برای الگوریتم رمز سرپنت توسط شیوه ابداعی بیان میگردد. در انتها نتایج بدست آمده در این مقاله با مشخصه های منتشر شده در دیگر مقالات مقایسه شده و کارهای آینده مطرح میگردد.
٢- معرفی سرپنت
سرپنت یک شبکه SP با اندازه قطعه ورودی/خروجی ١٢٨ بیت و اندازه کلید از ١٢٨ تا ٢٥٦ بیت است. [3 ] ساختار رمز دارای بخشهای جایگشت اولیه IP ، ٣٢ بار تکرار نابع دور و جایگشت نهاییFP است. در این الگوریتم از هشت S-Box با ورودی و خروجی ٤ بیت که مطابق جدول(١) با S0 , . . . , S7 مشخص میشوند ، استفاده شده است . در هر تابع دور ، . . R i , i ∈{0, . , 31} ، فقط از تکرار یک S-Box مشخص استفاده میشود که شماره آن ( ( j طبق رابطه زیر مشخص میشود :
j = i mod 8 , i ∈{0, . . . , 31}
در هر دور ،i ∈{0 , . . . , 31} ، ورودی B^i با کلید K^i تحت عمل Xor ترکیب شده و سپس ٣٢ S-Box مشابه بطور موازی به آن اعمال میشود . بعنوان مثال R 0 فقط از ٣٢ بار تکرار موازی S 0 استفاده میکند. آنگاه بردار میانی با استفاده از تبدیل خطی تغییر یافته و B^1 را تولید میکند . بطور مشابه R 1 نیز ٣٢ نسخه موازی S 1 را روی B^1 ⊕ K^1 اعمال و بردار میانی حاصل را با اعمال تبدیل خطی به خروجی B^2 تغییر میدهد . دور آخر اندکی با بقیه تفاوت دارد ، بطوریکه ابتدا S 7 را روی
B^31 ⊕ K^31 اعمال کرده و سپس بجای اعمال تبدیل خطی بر بردار میانی حاصل آنرا با xor K^32 و B^32 را تولید میکند .
اعمال نگاشت FP بر B^32 متن رمز را بدست خواهد داد .
جدول١- توابع جانشینی در الگوریتم رمز سرپنت
F E D C B A 9 8 7 6 5 4 3 2 1 0 Input
Sbox#
C 9 0 7 2 4 D E B 5 6 A 1 F 8 3 0
4 3 D 6 8 E B 1 A 5 0 9 7 2 C F 1
2 5 B 0 4 E 1 D F A C 3 9 7 6 8 2
E 5 7 A 4 2 1 D 3 6 9 C 8 B F 0 3
D 7 E 9 A 4 5 2 6 B 0 C 3 8 F 1 4
1 7 6 D 8 E 3 0 C 9 A 4 B 2 5 F 5
0 A 3 D F 1 9 E B 6 4 8 5 C 2 7 6
6 5 3 9 A C 4 7 B 2 8 E 0 F D 1 7
٣- مدل بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای
در این مدل توزیع تفاضلات ورودی/خروجی در یک تابع جانشینی توسط یک گراف جهتدار دوبخشی G(V,E,W) با n٢m+٢ گره بیان میشود، که m و n بترتیب اندازه ورودی و خروجی تابع جانشینی میباشد. m٢ گره بعنوان گرههای آغازی که با اندیسهای دودویی ٠ تا ١m- ٢ نامگذاری میشود و n٢ گره بعنوان گرههای پایانی که با اندیسهای دودویی ٠ تا ١n- ٢
نامگذاری میشود. یالهای این گراف بر اساس جدول توزیع تفاضلات تعیین میگردد و وزن هر یال برابر قرینه لگاریتم مقدار متناظر با آن در جدول توزیع تفاضلات در مبنای ٢ است. بعبارت دیگر اگر مقدار متناظر با یال (X,Y) در جدول توزیع نفاضلات برابر p باشد، وزن این یال بصورت W X ,Y − Log2 ( p) خواهد بود. بطور مثال بازنمایی تابع جانشینی Sbox3
در الگوریتم رمز سرپنت بصورت شکل(١) میباشد.
F 1 2 3 4 5 6 7 8 9 A B C D E
0
F 1 2 3 4 5 6 7 8 9 A B C D E
شکل ١- بازنمایی عملکرد تفاضلی Sbox3 در الگوریتم رمز سرپنت
0
در این مدل به جای هر یک از اجزای الگوریتم رمز ، گراف معادل آن قرار میگیرد، درنتیجه الگوریتم رمز به یک گراف جهتدار وزندار چند سطحی تبدیل خواهد شد. با بکارگیری این مدل جهت یافتن یک مشخصه k دوری در یک الگوریتم رمز قطعهای با ساختار جانشینی-جایگشتی ، یک گراف k٢ سطحی بدست میآید . اگر اندازه ورودی/خروجی الگوریتم رمز
n و اندازه ورودی/خروجی توابع جانشینی بکار رفته درآن m باشد تعداد گره گراف حاصل برابر m٢k× n ×٢ خواهد بود، m
یعنی اندازه گراف با افزایش تعداد دور بصورت خطی افزایش مییابد. بطور مثال بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای سرپنت سه دوری مطابق شکل(٢) است. دراین شکل پیکان های پررنگ بیانگر تبدیل خطی است که یک نگاشت ثایت میباشد.
یافتن بهترین مشخصه پیشرو برای یک الگوریتم رمز معادل یافتن مسیری از سطح اول به سطح انتهایی از گراف ترکیبات ممکن مشخصه های یک دوری آن است، بطوریکه جمع مسیر های آن کمترین مقدار ممکن باشد. یافتن بهترین مشخصه پسرو به معنی یافتن مسیری از سطح آخر به سطح ابتدایی این گراف است، بطوریکه جمع مسیر های آن کمترین مقدار ممکن باشد.
[13][26] VLSI
1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0
. . .
1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0
1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 0
. . .
1 2 3 4 5 6 7 8 9 A B C D E F
1 2 3 4 5 6 7 8 9 A B C D E F
1 2 3 4 5 6 7 8 9 A B C D E F
0
0
0
1 2 3 4 5 6 7 8 9 A B C D E F
1 2 3 4 5 6 7 8 9 A B C D E F
0
0
1 2 3 4 5 6 7 8 9 A B C D E F
1 2 3 4 5 6 7 8 9 A B C D E F
. . .
0
0
1 2 3 4 5 6 7 8 9 A B C D E F
1 2 3 4 5 6 7 8 9 A B C D E F
0
0
1 2 3 4 5 6 7 8 9 A B C D E F
0
1 2 3 4 5 6 7 8 9 A B C D E F
0
1 2 3 4 5 6 7 8 9 A B C D E F
0
شکل٢- بازنمایی عملکرد تفاضلی الگوریتم رمز قطعهای سرپنت سه دوری
٤- یافتن مسیر مناسب در گراف حاصل از بازنمایی با استفاده از شبکه عصبی
بهینهسازی با شبکههای عصبی برای حل مسائل متعدد و متنوعی از جمله جایگذاری قطعات در طراحی ،
n وزیر [24] ، خوشه بندی [11] [5] [21] ، برش و بسته بندی [14] [8]، رنگ آمیزی گراف [9] [15] [25] [23]، مسیریابی ترافیک شبکه[12]، یافتن کوتاهترین مسیر[30] [4] [29] [28] [18] [19] و فروشنده دوره گرد [22] [16] [10] بکار برده شده است.
