In this article, we shall adopt the concepts of elliptic curve cryptosystems and self-certified public keys to build a novel digital signature scheme with message recovery. The public key and the identity of the user can be authenticated simultaneously in recovering the message. In addition, we shall also present three extended digital signature schemes based on the proposed scheme. The first is an authenticated encryption scheme that only allows a designated verifier to retrieve and verify the message. The second is an authenticated encryption scheme with message linkages used to deliver a large message. And the third is for message flows. The authenticated encryption scheme with message linkages for message flows allows the verifier to recover partial message blocks before obtaining the whole signature. Some possible attacks will be considered, and our security analysis will show that none of them can successfully break any of the proposed schemes.
