Signcryption is a new cryptographic primitive which simultaneously provides both confidentiality and authenticity. This paper proposes an improved signcryption scheme and a variant scheme providing message recovery. The first scheme is revised from an authenticated encryption scheme which has been found to have a security-flaw. Our scheme solves the security-flaw and provides an additional property called the public verifiability of the signature. The second scheme is a message recovery type. It surpasses most of the current signcryption schemes on the size of the signcrypted ciphertext. That is, in our second scheme, we require only two parameters, (r, s), with r e Zp and s e Zq while most signcryption schemes require three parameters (c, r, s) with the additional parameter c ? Zp. This second scheme is modified from an authenticated encryption scheme with message recovery and surpasses the based authenticated encryption scheme on the property of non-repudiation of the origin.