Elliptic curve cryptography has been used in many security systems due to its small key size and high security compared with other cryptosystems. In many well-known security systems, a substitution box (S-box) is the only non-linear component. Recently, it has been shown that the security of a cryptosystem can be improved using dynamic S-boxes instead of a static S-box. This necessitates the construction of new secure S-boxes. We propose an efficient method to generate S-boxes that are based on a class of Mordell elliptic curves over prime fields and achieved by defining different total orders. The proposed scheme is devel-oped in such a way that for each input it outputs an S-box in linear time and constant space. Due to this property, our method takes less time and space than the existing S-box construction methods over elliptic curves. Computational results show that the pro-posed method is capable of generating cryptographically strong S-boxes with security comparable to some of the existing S-boxes constructed via different mathematical structures.