Optimization of Area and Delay for Implementation of the Composite Field Advanced Encryption Standard S-Box

摘要

Among different implementations of the Advanced Encryption Standard (AES) S-box, the implementation based on composite field arithmetic (CFA) has the smallest size. In this study, to eliminate the redundant gates in the implementation of CFA-based S-box, a new optimization algorithm named common subexpression elimination (CSE)-shortest critical path constructing (SCPC) algorithm is proposed. The CSE-SCPC algorithm combines an efficient CSE technology with the SCPC method, therefore not only area cost but also the delays are taken into account in the optimization process. For facilitating the search of common subexpressions (CSs), the main operation of CFA-based S-box - the multiplicative inverses (MI) over galois field (GF)((2(4))(2)) - is divided into six parts and each part is expressed by logical expressions directly. Furthermore, the parts with same input are classified into the same group, as there are CSs among them. Each part of the S-box is optimized by the CSE-SCPC algorithm. For the MI over GF((2(4))(2)), both the CSs in each part and the CSs among the parts are eliminated by the CSE-SCPC algorithm. Compared to the previous works, our design has not only the minimal area cost but also the shorter critical path in both theoretical computing evaluation and experimental evaluation.