A Reversible data hiding through encryption (RDTE) scheme will consider an original image and a sequence of bits as the input and generate an encrypted image as the output. This encrypted image will be able to transmit through the network securely, and the authorized receiver can take out the hidden details along with the restoration of the actual image. This paper proposes a new RDTE scheme with a good rate of embedding without any issues during the restoration of the original image. We have used the well-known RC4 pseudo-random generator for the image encryption, and we performed data hiding during block-wise image encryption. In the proposed scheme, the original image is considered as non-overlapping blocks of size B × B pixels, and these blocks will be encrypted using a sequence of pseudo-random integers. During the RDTE process, all the possible unique permutations of the encryption key, K, will be generated, say (K0, K1,.., KN). Further, the sender will be capable of embedding one integer value from the set {0, 1,.., N} in a selected image block. A selected block will be encrypted using the pseudo-random sequence of integers using the key KQ to embed the integer Q in the selected block. The proposed scheme prefers to select keys with unique characters with sufficient length to ensure the maximum embedding capacity. The message extraction and image restoration are performed by analyzing the entropy measure from each block after attempting the decryption.