The popularization of 5G and the development of cloud computing further promote the application of images. The storage of images in an untrusted environment has a great risk of privacy leakage. This paper outlines a design for a lightweight image encryption algorithm based on a message-passing algorithm with a chaotic external message. The message-passing (MP) algorithm allows simple messages to be passed locally for the solution to a global problem, which causes the interaction among adjacent pixels without additional space cost. This chaotic system can generate high pseudorandom sequences with high speed performance. A two-dimensional logistic map is utilized as a pseudorandom sequence generator to yield the external message sets of edge pixels. The external message can affect edge pixels, and then adjacent pixels interact with each other to produce an encrypted image. A MATLAB simulation shows the cipher-image performs fairly uniform distribution and has acceptable information entropy of 7.996749. The proposed algorithm reduces correlation coefficients from plain-image 1 to its cipher-image 0, which covers all of the plain-image characters with high computational efficiency (speed = 18.200374 Mbit/s). Theoretical analyses and experimental results prove the proposed algorithm’s persistence to various existing attacks with low cost.