توضیحات

عنوان تحقیق: تحلیل تفاضلی رمزهای بلوکی با استفاده از برنامه‌ریزی خطی اعداد صحیح آمیخته

مقدمه
تاریخچه
مسئله MILP برای محاسبه حداقل تعداد S-boxفعال
تحلیل رمز تفاضلی
معادلات توصیف کننده تبدیل خطی
تحلیل رمز خطی
توصیف Enocoro-128v2
تابع بروزرسانی
تحلیل-رمز تفاضلی Enocoro-128v2
ساختار مسئله MILP برای Enocoro-128v2
حداقل تعداد S-box های فعال برای تحیل تفاضلی رمز
تحلیل رمز خطی Enocoro-128v2
اعمال برنامه MILP
حداقل تعداد S-box های فعال برای تحلیل رمز خطی
تعداد S-box برای AES فعال
مراجع

مقدمه:

در سالهای اخیر نشان داده شده است که تحلیل رمز تفاضلی [22] و خطی [1] ، دو مورد از تکنیک های مهم در تجزیه و تحلیل ابتدایی رمزنگاری کلید متقارن است. برای رمز های بلوکی، تحلیل رمز تفاضلی آنالیز می کند که چگونه ورودی تفاضلی در متن منجر به اختلاف های خروجی در متن رمز می شود. تحلیل رمز خطی احتمال رابطه های خطی متن ساده، متن رمز و کلید را مطالعه می کند. اگر یک رمز به طور متفاوت از یک رمز تصادفی برای انجام تحلیل رمز تفاضلی یا خطی رفتار کند، می توان آن را برای ساخت یک تمایز دهنده یا حتی یک بازیابی کلید اصلی استفاده کرد.

برای رمز ها، تحلیل رمز تفاضلی می تواند در مفهوم یک حمله resynchronization بکار رود [13]. در یک تنظیم ممکن، داده های مشابه چندین بار با کلید مشابه اما با مقادیر اولیه متفاوت^[1] (IV) رمز می شوند. در واقع این بعنوان یک مدل استاندارد (کلید غیر مرتبط) است که در آن فرض می شود که مقدار IV تحت کنترل مهاجم می باشد. یک مدل حمله حتی قوی تر، تنظیم کلید مرتبط است، جایی که داده های مشابه با IV های مختلف و کلیدهای مختلف رمزگذاری می شوند. نه تنها مقادیر IV، بلکه تفاوت بین کلیدها نیز تحت کنترل حمله کننده قرار می گیرند. مشابه تحلیل رمز تفاضلی، تحلیل رمز خطی نیز می تواند برای حمله به جریانهای رمز در هر دو مدل استاندارد و کلید مرتبط مورد استفاده قرار گیرد.

مقاومت در برابر تحلیل رمزهای خطی و تفاضلی یک معیار استاندارد برای طراحی رمزهای جدید می باشد. برای رمز بلوکی AES [15] ، امنیت قابل اتکا در برابر تحلیل رمزهای خطی و تفاضلی از استراتژی طرح دنباله گسترده پیروی می کند [14]. در این کار، سعی داریم تا مشابه این استراتژی عمل کنیم. پس از اثبات حد پایین تعداد S-box های فعال برای هر دو تحلیل رمز خطی و تفاضلی، سعی میکنیم تا احتمال اختلاف حداکثر[2] (MDP) S-box ها را برای بدست آوردن حد بالای احتمال بهترین مشخصه بدست آوریم.

فرض می کنیم که (همانطور که بطور معمول صورت می گیرد) احتمال اختلاف می تواند به طور دقیق توسط احتمال بهترین مشخصه تخمین زده شود. چندین کار در زمینه محاسبه حداقل تعداد S-box های فعال در هر دو زمینه شبکه های جایگزینی – جایگشتی[3] [14] و ساختار تعمیم یافته فیستل[4] [5, 6, 19, 27] صورت گرفته است. متاسفانه، به نظر می رسد در بکار بردن این تکنیک ها نیاز به صرف زمان و تلاش بیشتری در برنامه ریزی می باشد. در این کار، یک روش جدید بر اساس برنامه ریزی خطی آمیخته اعداد صحیح به منظور غلبه براین مشکلات مورد استفاده قرار گرفته است.

تاریخچه:

برنامه ریزی خطی[5] مطلعه بر روی بهینه سازی (حداقل یا حداکثر کردن) یک تابع هدف خطی f(x1, x2, . . . , xn) ، به ازای نامعادلات خطی شامل متغیرهای تصمیم xi ، است. برای برخی مسائل بهینه سازی این چنین، لازم است متغیرهای تصمیم به اعداد صحیح محدود گردند یعنی برای برخی مقادیر i ، خواهد بود. روش هایی که برای فرموله کردن و حل اینگونه مسائل مورد استفاده قرار می گیرند برنامه ریزی خطی اعداد صحیح آمیخته[6] نامیده می شوند. اگر همه متغیرهای تصمیم اعداد صحیح باشند آنگاه از اصطلاح برنامه ریزی اعداد صحیح[7] نیز استفاده می شود. تکنیک های برنامه ریزی خطی اعداد صحیح آمیخته کاربردهای زیادی در اقتصاد و تجارت دارند اما کاربرد آن در رمزنگاری تا کنون محدود بوده است. برای آشنایی با روش های برنامه ریزی خطی و برنامه ریزی خطی اعداد صحیح میتوان از مرجع [26] سود برد.

مدل برنامه ریزی خطی با اعداد صحیح، مدل برنامه ریزی ریاضی است که متغیرهای آن عدد صحیح هستند. مدلی که در آن تنها تعدادی از متغیرها اعداد صحیح باشند مدل برنامه ریزی خطی عدد صحیح آمیخته (MILP) نامیده می شود. شکل کلی یک مسئله MILP از نوع مینیمم با تابع هدف[8] f به صورت زیر می باشد:

که در آن ، و می باشد.

روشهای مختلفی برای حل مسائل برنامهریزی خطی با اعداد صحیح وجود دارد که از متداولترین آنها میتوان به روش صفحه برشی[9] و روش شاخه و کران[10] نام برد. اخیراً برنامهریزی خطی عدد صحیح آمیخته برای به دست آوردن یک مشخصه خطی یا تفاضلی در طرحهای رمز مورد استفاده قرار گرفته است. برای پیدا کردن یک مشخصه خطی باید در جاهایی که عملگر XOR مورد استفاده قرار میگیرد، بیتهای فعال ماسکهای ورودی باهم برابر باشند بنابراین برای عملگر XOR با ورودیهای a و b و خروجی c و تعریف ماسک های ورودی به ترتیب با ، و ماسک خروجی داریم:

در ابتدا برای هر بیت از ورودی و خروجی از عملگرهای طرح، متغیر را به عنوان ماسکهای ورودی و خروجی[11] طوری تعریف، می کنیم که بازای بیتهای فعال مقدار یک و بازای بیتهای غیرفعال مقدار صفر را اختیار کند. هم چنین برای هر S-box یک متغیر تعریف میشود که بر اساس اینکه خروجی S-box مربوطه فعال یا غیرفعال باشد به ترتیب مقادیر یک ی ا صف ر را اختیار می کند. بنابراین جمع ها تعداد S-box های فعال را نشان می دهد. در اینجا عملگر غیرخطی AND را بعنوان یک S-box با دو مقدار ورودی و یک خروجی در نظر می گیریم. لذا با توجه به این انتخاب، میتوانیم تابع هدف را به صورت مینیمم جمع ها در نظر بگیریم تا کمترین S-box ممکن را داشته باشیم.

ساختار تابع هدف: از آنجا که هدف پیدا کردن یک رابطه خطی با کمترین تعداد S-box های فعال میباشد، بنابراین تابع هدف به صورت مینیمم مجموع ماسک های خروجی S-box ها تعریف می شود.

در [7]، Borghoff و همکارانش معادلات درجه دوم توصیف کننده جریان رمز Bivium را به یک مسئله برنامه ریزی خطی اعداد صحیح آمیخته تبدیل کردند. بسته نرم افزاری تجاری CPLEX [17] ، سپس برای حل نتایج این مسئله برنامه ریزی خطی اعداد صحیح آمیخته مورد استفاده قرار گرفت. در مورد Bivium A ، حل این مسئله MILP کمتر از 4.5 ساعت طول می کشد، که سریعتر از روش Raddum (در حد یک روز) [25]، اما کندترا ز روش MiniSAT (21 ثانیه) [9] می باشد.

برای تابع هش SIMD، Bouillaguet و همکارانش در [8] از یک ILP برای یافتن مشخصه تفاضلی بر پایه تداخل های محلی استفاده کردنذ. با استفاده از روش SYMPHONY [10]، آنها نتوانستند به یک راه حل بهینه برسند، اما یک حد پایینی برای IMD-256 و SIMD-512 رسیدند. محاسبات برای SIMD-512 بر روی کامپیوتر 4 هسته در حدود یک ماه طول کشید.

در [5, 6]، Bogdanov حداقل تعداد S-box فعال شبکه های فیتسل[12] نامتوازن در تحلیل رمز خطی و تفاضلی با انتشار MDS محاسبه کردند. او اثبات کرد که برخی از توزیع های وزن تفاضل بریده شده[13] غیزممکن یا معادل یکدیگر هستند. برای مابقی توزیع وزن های تفاضل بریده شده او یک مسئله برنامه ریزی خطی اعداد صحیح آمیخته تشکیل داد که سپس آن را با MAGMA [11] Computational Algebra System [4] حل نمود.

توجه:

برای دانلود فایل word کامل ترجمه از گزینه افزودن به سبد خرید بالا استفاده فرمایید.
لینک دانلود فایل بلافاصله پس از خرید بصورت اتوماتیک برای شما ایمیل می گردد.