Cryptography is the science and study of protecting data in computer and communication systems from unauthorized disclosure and modification. An ordinary difference equation (a map) can be used in encryption–decryption algorithms. In particular, the Arnold’s cat and the sine-Gordon linear maps can be used in cryptographic algorithms for encoding digital images. In this article, a two-dimensional linear mKdV map derived from an ordinary difference mKdV equation will be used in a cryptographic encoding algorithm. The proposed encoding algorithm will be compared with those generated using sine-Gordon and Arnold’s cat maps via the correlations between adjacent pixels in the encrypted image and the uniformity of the pixel distribution. Note that the mKdV map is derived from the partial discrete mKdV equation with Consistency Around the Cube (CAC) properties, whereas the sine-Gordon map is derived from the partial discrete sine-Gordon equation, which does not have CAC properties.