N* algorithm: nonlinearity-perfect substitution boxes generation method for robust cryptographic systems

Abstract

Substitution boxes (S-Boxes) are the nonlinear cores of many symmetric ciphers. They play an important role in improving resistance against linear and differential attacks. In this article, the presented N* algorithm is introduced as a simple and reproducible method for generating 8-bit bijective S-Boxes with maximum nonlinearity. The method starts from five strong ancestor S-Boxes, namely Advanced Encryption Standard (AES), APA, Gray, SM4, and Camellia. It then applies pairwise swaps and keeps only the candidates whose average nonlinearity is 112. In this way, the nonlinearity condition is enforced during generation. By applying this procedure to all five ancestors, the presented N* algorithm generated 1,275 valid S-Boxes. After merging, duplicate removal, and cleaning, a unified library of nonlinearity-perfect S-Boxes was obtained. The results showed that all generated S-Boxes preserved NL = 112, while the full library also maintained stable algebraic degree and strong bit-independence nonlinearity. Representative S-Boxes also showed competitive differential uniformity, low linear approximation probability, balanced avalanche behavior, and no opposite fixed points. These findings show that the presented N* algorithm can generate a large library of strong 8-bit S-Boxes under a clear and consistent framework. The obtained library can support cryptographic research, benchmarking, and practical design in block ciphers, stream ciphers, and hash functions. S-Boxes hide the relation between the key, plaintext, and cipher text. They also help block ciphers resist linear and differential attacks.