A message in Neapolitan code hidden between ones and zeros | Technology

Beeeeeeep… Beeeeep… Beeeeep

Sunday morning. the baby he is not at home and there is a strange emptiness; for the first time he will not be here for a few months; He has gone to do his final degree project at the University of Salerno, very close to Naples.

-Yessss?

“Hello mom,” says Jordi with a worried tone on the other side of the screen, “I’ve been in the Cryptography Department for a week but I don’t understand anything. Can you explain to me what this Vernam cipher is? And why did the great American mathematician Claude Shannon call it “perfect”?

Paz smiles – Ea, let’s go there. Vernam or One Time Pad encryption is a system used to encrypt messages with one-time keys. I’ll explain how it works. For example, if you want to send the word HELLO, you first encode it in binary, because strings of ones and zeros are easier to transmit. It will suffice to use five bits for an alphabet of 27 letters.

ABCDEFGHIJKLMNOPQRSTU WXYZ

And you would do it this way. First, you assign each letter a number according to its order in the alphabet: A=0, B=1, C=2… Z=26. Then you convert those numbers to binary, breaking them down into sums of powers of two (from 1, which is 2 to the power of 0, to 16, which is 2 to the power of 4 ). Notice:

A=0, which in binary with five bits is written 00000, since 0= 0x16 + 0x8 + 0x4 + 0x2 +0x1

B=1, in binary it is written as 00001, since 1 = 0x16 + 0 x 8 + 0x4 + 0x2 + 1×1

C=2, following the same method it would be 00010, since 2 = 0x16 + 0 x 8 + 0x4 + 1×2 + 0x1

D=3, which would be 00011, since 3= 0x16 + 0x8 +0x4 +1×2 +1×1

E=4, and it would be coded 00100, since 4= 0x16 + 0x8 + 1×4 + 0x2 + 0x1

And so, until Z=26, which would be 11010, since 26= 1×16 + 1×8 + 0x4 + 1×2 +0x1

Thus, your message M =HELLO would be encoded in four blocks of five bits, one for each letter. and taking

H=00111, 0=01111, L=01011, A=00000, we are left with:

ORIGINAL MESSAGE (M) = 00111 01111 01011 00000

That is the original message. But to encrypt it so that nobody can understand it, apart from your receiver, you have to use a key of the same length of bits. In this case, a 20-bit strip in four blocks that you and I have previously agreed upon. For example:

KEY (K) = 01010 10101 01010 10101 (equivalent to the word KUKU, which is easy to remember)

What you encrypt and send will be the result of adding the message and the key, bit by bit. But beware! It is not a conventional sum. It is a sum called XOR, or modulo 2, for which we use the symbol ⨁ and which is done like this:

0⨁0=0

1⨁0=1

1⨁1=0

―Therefore, ―Jordi can’t stand it without intervening, ―what he would send in this case would be… the following encrypted message:

MESSAGE SENT (C) = M⨁K= 00111 01111 01011 00000 ⨁ 01010 10101 01010 10101= 01101 11010 00001 10101

-Exact! On the other hand, this method, apart from being secure, is very agile: when I receive your message, I simply have to do the bit-by-bit addition with the key that we have in common and I recover the original message. But the revolutionary thing about this method – Paz makes a theatrical pause – which Shannon rightly underlined, is that a person who intercepts the sent message will not know anything about it, since the C bit string could contain inside any message with that number of letters. Imagine that someone intercepts the message we sent earlier and, since they have no idea what the key is, they try to see if it is, say, K’=01100 11010 00000 10101

-Wait… you know I’m very fast… I would get that the original message is:

C+K’=00001 00000 00001 00000

I mean BABA, my favorite Neapolitan sweet… mmmm.

“Hahahahaha… I knew you would like it. Surprising, isn’t it? Do you think any original message could come out by trying different keys? What would be the original message if the key used had been this other one, K*=01111 11010 00100 10001? I’ll leave it to you to think about it. And now… I propose a much more difficult challenge: decipher a message when you don’t have the key…

“But that’s impossible…

“Not if I give you any clues. The key is a priceless witness of the times, and the original message is related to a god of the sea; you will reach both if you do not forget the place where you are. The intercepted message is this:

C=00000 01111 01000 00011 10000 01100 01100

– A witness, mom, what a clue! – Jordi protested indignantly – it can be so many things… a monument, a place, even a pasta recipe… but maybe… I’ll get down to it!

Crypto challenges will be published every 15 days. Readers can leave their solutions and discuss the problem in the comments on this page, so anyone who wants to solve it on their own is advised not to read it until they have cracked the puzzle. You can also email your responses [email protected]. In each new challenge we will publish the solution of the previous one, accompanied by a comment with some original or inspiring ideas that we have received.

German Saez Moreno He is a researcher for the MAC group and a professor of Applied Mathematics at the Universitat Politècnica de Catalunya.

SOLUTION TO THE PREVIOUS CHALLENGE

We need to fill in 7 boxes, including (1,1,1) ―since it is the peacemaker’s tablet― so that a critical set is defined, that is, that leads us to a single possible Latin square starting from:

The correct sequence is the sequence is T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T5 = (5,3,2) T6=(1,1, 1) T7=(2,5,3) T8=(5,1,5) }, which partially fills the square like this:

Any other set of 7 tablets taken from the 8 possible ones does not define a critical set, that is, it can be filled giving rise to several Latin squares. With ours, the only complete Latin square that comes out is:

Remark: This Latin square contains the “cursed tribe”, the (1,5,5) tablet, which, however, we have to remove if we want our solution sequence to define a critical set.

DETAILED RESOLUTION:

The Latin square that we seek to complete must contain seven of the positions described on the ceramic tablets:

T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1, 1,1) T7=(2,5,3) T8=(5,1,5)

In addition, to get a critical set it is essential to include the (1,1,1), which is what the peacemaker priest tablet is for.

There are therefore 7 possible sets (the ones that exist by eliminating a triple of the 8 possible if we always keep (1,1,1) ). Let’s see case by case:

– C1 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2, 5,3) T8=(5,1,5) }

It is not a critical set. If we start to solve the sudoku, there is no single solution. In this case, two compatible Latin squares come out

– C2 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5, 1.5) }

It is not a critical set, seven compatible Latin squares come out

– C3 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

It is not a critical set, four compatible Latin squares come out

– C4 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

This is a critical set. The sudoku I would only have one solution.

– C5 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

It is not a critical set, there are 14 compatible Latin squares

– C6 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6 =(1,1,1) T7=(2,5,3) T8=(5,1,5) }

It is not a critical set, eight compatible Latin squares come out

– C7 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6 =(1,1,1) T7=(2,5,3) T8=(5,1,5) }

It is not a critical set, 6 compatible Latin squares come out

Thus, the correct sequence is the one that determines the set C4, which is the only critical set.

C4 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

There are tools available on the internet to do the calculations without having to solve all sudokufor example this one: https://www.dcode.fr/latin-square

Several readers, like Joaquín, have found the cursed tribe to have a simpler reasoning, realizing that the card (1,5,5) is unnecessary: ​​by removing it, and filling the square with the rest of the tablets, there is no no choice but to put a 5 in position 1-5 (in fact, as the set formed by the other boards is critical, any other square on the board is determined, since there will never be more than one solution). This method, however, is not useful for identifying critical sets in general (because there could be elements that are left over without being “deductible” starting exclusively from the rest of those that make up the set).

ABOUT SECRETS SHARING SCHEMES

This challenge is based on a secret sharing scheme published in the paper Secret sharing schemes arising from latin squaresby Joan Cooper, Diane Donovan and Jennifer Seberry.

Secret sharing schemes are tremendously useful cryptographic designs, especially in scenarios where it is important to fragment information and force potential recipients to group together according to a certain information access policy. A very current example of use is access control through passwords. Let us suppose that the users of a system are identified through a password. If the list of valid passwords is kept on a single server (even slightly masked) the danger that exists if said server becomes controlled by an external malicious entity is evident. However, if this list is fragmented by distributing it among several servers, so that each access is validated by them collaboratively, the passwords will be protected when a single server is attacked.

Secret sharing schemes were introduced by Adi Shamir in his article How to share a secret and George Blakey (Safeguarding cryptographic keys). Both authors also proposed the most widely used scheme to date, which is based on polynomial interpolation.

You can follow EL PAÍS TECNOLOGÍA at Facebook Y Twitter or sign up here to receive our weekly newsletter.