Crypto Challenge: A Mystery Hidden in Little Black and White Squares

After Jordi understood in the previous challenge what the Vernam or One Time Pad encryption consisted of, he continued with the video call with Paz, his mother.

"Mom, what does visual cryptography have to do with anything?"

My tutor, Paolo, insists that it is more or less the same as the Vernam Cipher, but I don't see where he is going...

More information

The why of the crypto challenges.

See previous challenges

Paz smiled at her son's impatience.

—Well, part of the previous idea, only here the information is not encoded in the form of a binary string, but as an image.

Therefore, no mathematical operations have to be done to recover the secret: the human eye is in charge.

I send you some photos to the mobile.

THE COUNTRY

the country

"Try to overlap them."

You just have to print on a slightly thin paper and put them one on top of the other on a window glass.

And you will get the following:

The country

Now, notice: if you take the first transparency and overlap it with the one I send you next, you will see that you get a different letter.

Which?

the country

Jordi thought he'd better leave it for later... his mother was still talking, and he didn't want to lose the thread.

"But there is something else," added Paz, "visual cryptography often includes an essential ingredient for any good cryptographer: mistrust."

-The distrust??

-That's it.

If the sender of a message does not even fully trust a specific recipient, he can distribute the ability to decrypt among several recipients.

To do this, the image that acts as a key is "fragmented" into several transparencies: to recover it, it will be necessary to carefully place the key-transparencies one on top of the other.

Then, by placing this "stack" on the transparency-message, the decrypted image can be seen.

George was intrigued.

―But how are these images made from the initial one?

-Is not difficult.

To distribute a black pixel of the original image we must choose for each of the transparencies one of the following two combinations of pixels:

THE COUNTRY

The choice of one combination or another has to be done randomly.

In the same way it is done to distribute a white pixel, but using a material such that when superimposing two black transparencies the white color is obtained (as this is not easy to reproduce on paper, which will be the material used by the readers, we will play with shades of gray).

Thus, for each white original pixel we must randomly choose between one of these two decompositions:

the country

"But it's a lot of work...

-Of course: it has to be implemented in programs that do it quickly.

The original image above is 100 pixels.

But does anyone hand-encrypt a message so that it travels safely over the Internet?

the country

the country

The country

The country

Paz hung up, thinking that she could have even given Jordi a more demanding challenge;

with which perhaps some of our readers will dare.

We will love to see your proposals, and we will comment on the best ones with the solution of this challenge.

Germán Saez Moreno

is a researcher at the MAC group and a professor of Applied Mathematics at the Polytechnic University of Catalonia.

SOLUTION TO THE PREVIOUS CHALLENGE

FIRST EXERCISE

The first question to the reader of the previous challenge was whether we could get any original messages by trying different keys.

And the answer is yes, given a cipher, we can make it “match” any message m sent, setting the string c ⨁ m as the key, since obviously if we add the string of bits c ⨁ m to ac we get, again, the starting message, m.

This occurs because the XOR operation is self-inverse (and the two "c's" cancel each other out).

For the concrete example proposed, it suffices to see that

c⨁k'= 01101 11010 00001 10101+01111 11010 00100 10001=00010 00000 00101 00100

that is, we get the word COFFEE.

SECOND EXERCISE:

The second challenge was to decipher a hidden message knowing that the key was "an invaluable witness of the times", and the original message was related to a god of the sea.

As an additional clue, both terms were related to the place where the protagonist of the challenge was located (Salerno, Italy).

Many readers have found the solution and have sent it to us by email.

For some, like Efraim, Zoe and Gonzalo or Mariona, knowing the area has helped them;

others, such as Luis, Ramiro or Manolo have tried possible keys such as Vesuvius, Neptune and even pizza maker.

The correct one, and the one that fits the "witness of the times", was POMPEII which is encoded as:

K = 10000 01111 01100 10000 000100 11001 00000

added to the encrypted string

C=00000 01111 01000 00011 10000 01100 01100

We get the sent message:

10000 00000 00100 10011 10100 10101 01100

which is decoded as PAESTUM (ancient city of Poseidonia, in the province of Salerno).

There was another “covert clue” in the statement, because as the first letter of the cipher was 00000, the key and message sent must necessarily be words that began with the same letter.

We thought that this hint could be useful to reduce the check of possible keys;

if one uses “Google/Wikipedia” and searches for two 7-letter words related to Salerno and that begin with the same letter, the options are greatly reduced….

This challenge focuses on the so-called Vernam Cipher, proposed at the beginning of the 20th century by Gilbert S. Vernam, an engineer at the AT&T telephone company.

This method served as the basis for Claude Shannon's definition of the notion of

Renamed One-time Pad, it was introduced by Shannon in his famous work “Communication Theory of Secrecy Systems” Bell System Technical Journal 28(4) pp.

656–715, where he further showed that this method is secure as long as the keys are single-use and of the same length as the texts to be encrypted.

You can follow EL PAÍS TECNOLOGÍA on