Elliptic curve cryptography (ECC) is capable of providing high security than to other cryptosystems with same key size. The aim of this paper is twofold. Firstly, we present new methods for the construction of substitution boxes (S-boxes), and the generation of pseudo random numbers (PRN) by using a total order on an elliptic curve (EC) over a prime field. A search method is used to efficiently generate an EC instead of the more traditional group law which is computationally expensive. The S-box generation technique uses the x -coordinates of the points of an ordered elliptic curve (OEC), while a generalization of the Frobenius map and n -norm are used on the points of an OEC to generate PRN. Secondly, a two phase image encryption system based on the newly developed S-box and PRN generation methods is proposed. In this security system, the plain-image is first diffused by masking it by the proposed PRN which is then confused by a proposed dynamic S-box. Rigorous analysis and comparison with some of the existing S-box and image encryption methods reveal that the proposed techniques are capable of generating cryptographically strong S-boxes, PRN with high entropy and optimal resistance against modern image cryptanalysis .