The S-box is a key component of modern ciphers, determining the quality and performance of the cryptographic algorithms in which it is applied. Many constructions for synthesizing high-quality S-boxes have been established, and those based on Galois fields theory—for example, the Nyberg construction applied in the AES cryptographic algorithm—are particularly important. An integral component of the Nyberg construction is the affine transformation, which is used to improve the avalanche and correlation properties of the S-box. In this paper, a new approach is adopted for synthesizing affine transformations for S-boxes based on the quaternary matrices over the Galois field GF(4). We describe four basic structures that serve as the foundation for synthesizing a complete class of 648 affine transformation matrices of order n = 3 and a class of 7776 matrices of order n = 4 and introduce a recurrent structure to facilitate the synthesis of matrices for higher orders. Using these matrices in combination with the Nyberg construction, it is possible to construct bijective S-boxes that outperform the original Nyberg construction and many other known S-boxes in terms of strict avalanche criterion (SAC) and bit independence criterion strict avalanche criterion (BIC SAC) values, while maintaining a maximal level of nonlinearity and good cryptographic properties. We also propose modified GF(4) affine transformations that can be applied to specialized S-boxes which already satisfy the SAC for both component Boolean and 4-functions, as well as the criterion of minimal correlation between input and output, allowing us to enhance their nonlinearity to the value of N_f = 96. We integrate the synthesized S-boxes into the AES algorithm and evaluate their practical performance. The encryption outputs successfully pass the NIST statistical test suite in 96 out of 100 cases, outperforming both the original AES S-box and other reference constructions, confirming the practical strength of the proposed method.