Research and implementation of large-scale S-box for MK-3 algorithm based on polynomial basis: in FPGA

The MK-3 algorithm uses a large-scale 16x16 S-box, which is over a Galois Fields GF(2(16))and contains 65536 16-bit elements. In practical Field Programmable Gate Array engineering (FPGA), traditional look-up table method is usually used to implement the S-box in hardware, and this implementation method has problems such as large hardware resources occupancy, poor portability, limited application scenarios, etc. In addition, there are few studies available related to the optimized implementation of large-scale S-box in FPGA. To address the above problems, in this paper a hardware implementation of composite field constructions based on polynomial basis for large-scale S-box is proposed, which completes the linear affine transformation and nonlinear Galois Fields operations in large-scale S-box through logic operations. This paper proposes and implements 3 composite field constructions based on polynomial basis: GF((2(8))(2)), GF((2(4))(2))(2)) and GF((((2(2))(2))(2))(2)). According to the irreducible polynomial sets determined by the 3 construction methods, the corresponding isomorphic functions are calculated, and the corresponding isomorphic matrices and inverse isomorphic matrices are constructed. This simplifies the originally complex 16-bit Galois Fields inversion operations into 8-bit, 4-bit, and 2-bit inversion operations, respectively. Finally, Xilinx's Vivado development tool is used to perform functional simulation verification and comprehensive testing of the 3 constructions in this paper. Experiment results show that the 3 composite field constructions based on polynomial basis proposed in this paper consume 297 LUTs, 223 LUTs, and 236 LUTs respectively, and effectively solve the problem of hardware implementation difficulty of the 16x16 S-box for MK-3 algorithm. Among them, the composite field GF(((2(4))(2))(2)) construction based on polynomial basis proposed in this paper is the optimal solution, reaching the Frequency of 97.09 MHz and Frequency/LUTs of 0.43538, 0.02542 higher than that of the existing optimal scheme of 0.40996. The 3 composite field constructions based on polynomial basis in this paper satisfy the purpose of hardware optimization implementation by increasing the operation Frequency to the utmost while reducing the hardware resources.