ارائه یک روش برای پیاده‌سازی ماتریس‌های دودویی و کاربرد آن در پیاده‌سازی ماتریس‌های MDS

الموضوعات :

سید محسن موسوی ¹

1 - مجتمع علوم کاربردی، دانشگاه صنعتی مالک اشتر، اصفهان، ایران

تاريخ الإرسال : 27 الإثنين , رجب, 1443 تاريخ التأكيد : 17 الخميس , ذو القعدة, 1443 تاريخ الإصدار : 21 الأحد , شوال, 1443

الکلمات المفتاحية: الگوریتم‌های ابتکاری, ماتریس MDS, پیاده‌سازی ماتریس‌های دودویی,

ملخص المقالة :

ماتریس‌های MDS نقش مهمی در رمزنگاری و کدگذاری دارند. ماتریس‌های MDS به‌عنوان لایه انتشار در سیستم‌های رمزنگاری و همچنین در ساخت کدهایی با بیشترین میزان تصحیح خطا استفاده می‌شوند. ازیک‌طرف، درایه‌های ماتریس‌های MDS عناصر میدان‌های متناهی هستند. از طرف دیگر، پیاده‌سازی میدان‌های متناهی در رمزنگاری سبک‌وزن مشکل است. بنابراین برای بکار بردن ماتریس‌های MDS در رمزنگاری سبک‌وزن، در ابتدا این دسته از ماتریس‌ها را به ماتریس‌های دودویی تبدیل نموده و در ادامه با استفاده از الگوریتم‌های ابتکاری، پیاده‌سازی می‌شوند. در این مقاله، یک روش برای پیاده‌سازی ماتریس‌های دودویی با هزینه XOR کم پیشنهادشده و در ادامه با استفاده از روش پیشنهادی، یک الگوریتم ابتکاری برای پیاده‌سازی ماتریس‌های MDS معرفی می‌گردد. عملکرد الگوریتم ابتکاری معرفی‌شده بر این اساس است که فرض کنید A یک ماتریس دودویی (یا شکل دودویی یک ماتریس MDS) باشد. در ابتدا با استفاده از یک روش تکراری-تصادفی یک لیست S از ماتریس دودویی A به دست می‌آید. سپس، با استفاده از لیست S یک ماتریس دودویی به نام B تشکیل می‌گردد. در ادامه یک ارتباط بین پیاده‌سازی ماتریس‌های A و B پیدا می‌شود. به‌عبارت‌دیگر با استفاده از پیاده‌سازی ماتریس B یک پیاده‌سازی کم‌هزینه برای ماتریس A ارائه می‌گردد. در ساختار الگوریتم ابتکاری پیشنهادشده از یکی از الگوریتم‌های متداول SLP به نام Paar استفاده‌شده است.

المصادر:

[1] K. C. Gupta, S.K. Pandey, I.G. Ray and S. Samanta, “Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results,” Advances in Mathematics of Communications, vol. 13, no. 4, pp. 779-843, 2019, Doi: 10.3934/amc.2019045.

[2] L. Kolsch, “XOR-Counts and Lightweight Multiplication with Fixed Elements in Binary Finite Fields,” Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 285–312, 2019, Doi: 10.1007/978-3-030-17653-2_10.

[3] C. Paar, “Optimized arithmetic for Reed-Solomon encoders,” Proceedings of IEEE International Symposium on Information Theory, pp. 250-250, Jun. 1997, Doi: 10.1109/ISIT.1997.613165.

[4] J. Boyar, P. Matthews and R. Peralta, “Logic Minimization Techniques with Applications to Cryptology,” Journal of Cryptology, vol. 26, no. 2, pp. 280-312, Apr. 2013, Doi: 10.1007/s00145-012-9124-7.

[5] S. Banik, Y. Funabiki and T. Isobe, “More Results on Shortest Linear Programs,” International Workshop on Security, pp. 109-128, Jul. 2019, Doi: 10.1007/978-3-030-26834-3_7.

[6] Q. Q. Tan and T. Peyrin, “Improved Heuristics for Short Linear Programs,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2020, no. 1, pp. 203-230, Nov. 2019, Doi: 10.13154/tches.v2020.i1.203-230.

[7] F. J. MacWilliams and N.J.A. Sloane, “The Theory of Error Correcting Codes,” NorthHolland, 1977.

[8] H. Kranz, G. Leander, K. Stoffelen and F. Wiemer, “Shorter Linear Straight-Line Programs for MDS Matrices,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 4, pp. 188-211, Nov. 2017, Doi: 10.13154/tosc.v2017.i4.188-211.

[9] M. Mousavi, (2020), GitHub repository, https://github.com/mousavi-codes/Implementation-of-Binary-Matrices.

[10] J. Daemen and V. Rijmen, “The Design of Rijndael: AES-The Advanced Encryption Standard,” Springer-Verlag, 2002, Doi: 10.1007/978-3-662-04722-4.

[11] Q. Liu, W. Wang, Y. Fan, L. Wu, L. Sun and M. Wang, “Towards Low-Latency Implementation of Linear Layers,” IACR Transactions on Symmetric Cryptology, vol. 2022, pp. 158-182, Mar. 2022, Doi: 10.46586/tosc.v2022.i1.158-182.

[12] S. Sarkar, and H. Syed, “Analysis of Toeplitz MDS matrices,” Australasian Conference on Information Security and Privacy, vol. 10343, pp. 3-18, May. 2017, Doi: 10.1007/978-3-319-59870-3_1.

[13] P. Barreto and V. Rijmen, “The Khazad Legacy-Level Block Cipher,” In Proceedings of the first open NESSIE Workshop, Belgium, Nov. 2000.

[14] S. M. Sim, K. Khoo, F. Oggier and T. Peyrin, “Lightweight MDS Involution Matrices,” International Workshop on Fast Software Encryption, vol. 9054, pp. 471-493, Mar. 2015, Doi: 10.1007/978-3-662-48116-5_23.