Wednesday, May 22, 2019

[pudujsxx] Ultimate slideshow

Create a program that displays a slideshow of every possible picture for given image dimensions.  This is easy: just enumerate all the (w*h*24)-bit numbers, assuming 24-bit color.  There are 2^(w*h*24) such numbers, so of course, it will take a very long time, much much longer than the age of the universe, to run through the whole slideshow.

One could be more fancy and enumerate YUV420, or even things like all pictures which compress at least a given amount with a given image compression algorithm like JPEG.

To prevent the slideshow from being boring, let's require that successive frames tend to be different from each other.  So, display all possible pictures in a pseudorandom order.

Also, it would be nice to be able to calculate when a specific image will come up in the pseudorandom order.

These two features suggest using encryption.  Enumerate all (w*h*24)-bit numbers in normal order, then apply encryption as a pseudorandom permutation among (w*h*24)-bit numbers, mapping to an image.  (Things become trickier with more complicated image formats.)  Decryption of a given image would give you its slide number, when it will come up in sequence, probably a date in the extreme far future, long after heat death has destroyed the universe as we know it.

The most common block cipher modes of operation don't work: In ECB, similar input images will have similar outputs.  Consecutive slide numbers will typically have many identical blocks of bits, and identical input blocks map to the identical output blocks.  With CTR, we use the same initialization vector for each encryption (typically a big no if security were a concern, which it is not for this application) because the output image must be the same size as the input image so we don't have space to store the IV.  Because we would therefore be XORing the same stream each time, similar input will map to similar output.  For the same reason, stream ciphers also don't work.

CBC, again with a fixed initialization vector (probably the zero block for simplicity), will have inputs with the same prefix encrypt to the same output prefix.  If the numbers are encoded big-endian, then this will result in many similar consecutive output images.  However, little-endian would work, because the least significant bits change the fastest among numbers in order.

We could also build our own large block cipher, for example using the Feistel construction, with block size equal to the image size, then use it in ECB mode.

No comments :