In order to make sense of some of the things we mentioned in class, it is useful to see them in action on image files; for we, as humans, are quite good at visually detecting patterns in an array of pixels. This "cloud" interface to Sage is somewhat similar to the regular "notebook" one; use SHIFT+ENTER (or the green "Run" button above) to evaluate a cell.
Internally, it's just a matrix of pixels, each of which is colored according to a RGB triple of integers between 0 and 255:
Recall that the goal of encryption would be to reversibly make it look like a random image of the same size just like this one:
As a single pixel is encoded on bits, a block of pixels is encoded on bits, which give us more than enough room to store a secure symmetric encryption key.
Et voilà! Here's the picture, encrypted by a 384-bit key:
Discuss the result. Would you say that this cipher provides perfect secrecy?
This scheme certainly does not provide perfect secrecy, as we cleary recognize some features of the original image leaking into the ciphertext (structure of the mansion, patches of grass and sky...). In particular, note that repeating blocks in the plaintext yield repeating blocks in the ciphertext, thus breaking semantic security.
The problem is that the key is a perfectly good one-time pad that provides 384 bits of security if used to mask a single image block; but it is used here to encrypt such blocks, thus providing (cf. discussion of the many-time pad) an effective bit of security...
Go through the same process, this time with a genuine randomly generated one-time pad. What's the key-length this time? Verify that the cipher decrypts correctly, i.e. play both the roles of Alice and Bob to see that everything works as it should. Also make sure to take a look at what Eve actually sees on the insecure channel.
Here's the one-time pad that we'll use:
The effective key length (assuming perfect strength of the random number generation) is the actual number of bits needed to specify this image:
To encrypt the image, Alice applies this random key as a mask:
Only the resulting ciphertext transits on the insecure communication channel; what Eve sees looks just like random noise.
To decrypt, Bob removes (i.e. reapplies) the pad:
You may check that the actual pixel values of the decrypted image are actually identical to the original ones:
Wow, this works well. In the excitation of the moment, I started encrypting all my images... but forgot to apply one of the most important usage rules of the one-time pad when I encrypted the following two images. Can you find out what they were?
The single most important thing to remember with the one-time pad is to use it only once... One may suspect that the same encryption key was used twice, and this would enable an attacker to access the sum (xor) or the plaintexts by xoring the ciphertexts:
Indeed! We clearly recognize Alice and Bob, semantic security is completely broken.
After realizing my mistake, I decided to generate pads from a 128-bit key by using it as a seed for a linear congruence generator modulo the following 128-bit prime:
Since such a PRNG is characterized by two 128-bit integers and which were chosen at random, there should be more than enough entropy to protect my 128-bit key, right? Prove me wrong by finding out what the seed used to produce the first few outputs from the LCG was:
Recall that a linear congruence generator works by iterating a simple affine function modulo : By substrating the formula for from the formula for , one sees that: that is, the differences between successive outputs form a geometric progression.
To perform division mod , we use the extended Euclidean algorithm to a modular inverse (or just regular integer division followed by the remainder operator since Sage is permissive):
Now the value of is easily recovered:
And we can even go backwards in time:
We verify that we are able to recover the given terms (three of them were actually enough to completely reverse engineer the LGC) by using as a seed (as well as predict future values):
Linear congruence generators (and linear shift feedback registers) were not designed to be secure pseudo-random number generators, and should never be used as such.
Alice generates a pseudo-random pad of the required size by using the pixel values supplied by the PRNG:
and then applies it to the image to encrypt it:
Upon reception of the ciphertext, Bob initializes his own PRNG with the secret key to compute the exact same pad in order to remove it: