The Limited Times

Now you can see non-English news...

A message in Neapolitan code hidden between ones and zeros

2022-09-02T08:52:25.649Z


The fifth cryptographic challenge of EL PAÍS consists of finding out an encrypted word with a method that some have defined as "perfect"


Beeeeeeep… Beeeeep… Beeeeep

Sunday morning.

The baby

is not at home and there is a strange emptiness;

for the first time he is not going to be around 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"?

More information

The why of the crypto challenges.

See previous challenges

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 + 1x1

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

D=3, which would be 00011, since 3= 0x16 + 0x8 +0x4 +1x2 +1x1

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

And so, until Z=26, which would be 11010, since 26= 1x16 + 1x8 + 0x4 + 1x2 +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 pauses theatrically― 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

any

message with that number of letters inside.

.

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, for example, 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 send your answers to the email

desafioscriptograficos@gmail.com

.

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.

Germán Sáez Moreno

is a researcher at 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 country

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:

THE COUNTRY

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:

THE COUNTRY

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.

Sudoku

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

sudoku puzzles

, for 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 work

Secret sharing schemes arising from latin squares

, by 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 said list is fragmented by distributing it among several servers, so that each access is validated by them collaboratively,

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 on

Facebook

and

Twitter

or sign up here to receive our

weekly newsletter

.

Source: elparis

All tech articles on 2022-09-02

You may like

Trends 24h

Tech/Game 2024-03-27T18:05:36.686Z

Latest

© Communities 2019 - Privacy

The information on this site is from external sources that are not under our control.
The inclusion of any links does not necessarily imply a recommendation or endorse the views expressed within them.