Abstract: For an AES S box, the algebraic expression, which only has 9 items, is too simple, and the period of affine transform pair and iterative output is too short. For these reasons, a new solution to construct a S box is proposed. The algebraic expression coefficients of the S box and Inv S box are obtained using the coefficients of fully expanded Lagrange interpolation formula in finite field. Compared with deriving the algebraic expression from the construction principle of AES S box, this new method is intuitive and simple universal. The MATLAB simulation results show that the new S box has the shortest construction time. The period of affine transform pair and iterative output are up to 16 and 256 respectively. The strict avalanche criterion distance of S box and Inv S box reduce separately to 376 and 304. S box’s algebraic expression items are improved to 253. All of these prove that the new S box has a more complex algebraic structure, better difference characteristics and nonlinearity. At the same time, the affine transform times and the construction time of S box further explain the conciseness and high efficiency of the new S box design.