Elliptic curve cryptography is known for its complexity due to its discrete logarithm problem, and this gives advantage to the system used since the formula developed using this concept is hard to break, therefore this criteria has given mathematicians a courage to explore this area of research. Earlier in [10], we have showed a new method for imbedding plaintexts using complementary elliptic curve and now in this paper we will extend our work to obtain a new modified method for Nyberg-Rueppel message recovery signature scheme using complementary curve. By applying this method, we will eventually enlarge the block of message of elliptic curve cryptosystems and this resulted in faster communication and processing time and at the same time the security level remain tight.