This paper proposes a new mutable nonlinear transformation algorithm for AES S-box to enhance the complexity of the S-Box?s structure called M_S-box that effectively provides an optimal degree of resistance against differential cryptanalysis and especially the linear cryptanalysis. The structure of the AES S-box has been expanded and modified to be congruent with the proposed algorithm and to obtain good nonlinearity of the S-box. The Cryptanalysis of the model is based on the maximum average differential probability (MADP) and maximum average linear hull probability (MALHP). The results show that proposed model significantly improves MADP and MALHP. Furthermore, the results that have been obtained exhibit good enough confusions to achieve high security level.