In this paper, we propose a novel reversible data hiding algorithm, which can recover the original image if it is deemed authentic or detect the block-wise malicious manipulation if it is classified as manipulated. We explore the strong spatial correlation of neighboring pixels in digital images to achieve very high embedding capacity and keep the distortion low. Also, this technique provides cryptographic strength when verifying image integrity because the probability of making undetectable modifications to the image is directly related to a secure cryptographic element, such as a hash function. The algorithm has been successfully applied to a wide range of images, including commonly used images, biometric images, texture images, and aerial images. Experimental results and performance comparison with other reversible data hiding schemes are presented to demonstrate the validity of the proposed algorithm.