کاهش پیچیدگی محاسباتی تبدیل والش و درجه غیرخطی برای تسریع در ارزیابی جعبه های جانشانی بزرگ رمزنگاری

پیچیدگی زمانی و پیچیدگی حافظه الگوریتم های موجود برای محاسبه تبدیل والش و درجه غیرخطی جعبه های جانشانی بزرگ با n بیت ورودی و m بیت خروجی از مرتبه نمایی (۲n+m)O هستند. به همین دلیل تسریع در محاسبه تبدیل والش - هادامارد و درجه غیرخطی برای توابع بولی و جعبه های جانشانی بزرگ یکی از چالش های عمده در تحقیقات رمزنگاری مدرن برای مقاوم سازی طرح های رمزنگاری در برابر حملات خطی و تفاضلی است. در این مقاله سه روش جدید تسریع پیشنهاد شده است که به ترتیب از موازی سازی محاسبه الگوریتم والش سریع، تعریف و دسترسی به ترانهاده ماتریس والش به جای خود این ماتریس و در ادامه با ترکیب یک بخش مهم از عملیات محاسبه درجه غیرخطی در داخل الگوریتم محاسبه ماتریس والش، استفاده می کنند. برای ارزیابی صحت الگوریتم های پیشنهادی از شبیه سازی و آزمایش استفاده شده است و تحلیل کلی منابع مصرفی الگوریتم های پیشنهادی در مقایسه با الگوریتم های قبلی انجام شده است. نتایج شبیه سازی نشان می دهند که با استفاده از روش های پیشنهادی این مقاله، زمان محاسبه ماتریس والش تا ۳۹ برابر و زمان محاسبه درجه غیرخطی تا ۵۶۳ برابر بهبود یافته است.

Keywords:

جعبه های جانشانی , تبدیل سریع والش - هادامارد , درجه غیرخطی , پیچیدگی محاسباتی , موازی سازی , پیاده سازی