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

Presentation of a Method for Implementing Binary Matrices and its Application in the Implementation of MDS Matrices

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

MDS matrices have a crucial role in the cryptography and coding theory. MDS matrices are used as the diffusion layer in cryptosystems as well as in the construction of linear codes with the maximum error correction capability. On the one hand, the entries of MDS matrices are elements of finite fields. On the other hand, it is a major issue to implement finite fields in the lightweight cryptography. Therefore, to use MDS matrices in the lightweight cryptography, these matrices are first converted to binary matrices and then implemented using heuristics algorithms. In this paper, a method to implement binary matrices with low-cost XOR is proposed and then using the proposed method, a heuristics algorithm for implementing MDS matrices is introduced. The structure of the proposed heuristics algorithm is based on the assumption that let A be a binary matrix (or the binary form of an MDS matrix). First, using a random-iterative method, we obtain a list S from a binary matrix A. Then, based on the list S, we construct a binary matrix B. Next, we find a relation between the implementations of A and B. In other words, using the implementation of the matrix B, we get a low-cost implementation for the matrix A. In the structure of the proposed heuristics algorithm, one of the familiar SLP algorithms called Paar is applied.