The Chamber of Secrets Riddle | Technology

Jorge and Clara had been working for months as archaeologists in a pre-Columbian pyramid in the south of the Yucatan. They had been trying to break into a secret chamber for weeks. But to do so they had to solve a riddle that could lead to success or death.

Eight tribes had disputed power in the region. A peacemaker priest, head of one of the tribes, managed to establish an alliance signed by seven of them, who went on to guard the pyramid. The eighth tribe was considered cursed. Each tribe appeared in different archaeological remains represented through a square figure, which contained a trio of symbols. For example, this was the tablet of one of the tribes:

The door of the chamber into which they wanted to enter had a kind of board drawn on the floor, with rows and columns indexed exactly by those symbols, in which could be fitted, for each position of row and column, a single stone with the shape of one of the five different symbols that had been found. From earlier excavations, it was known that the three symbols on each tablet were to be interpreted as row-column-symbol. The tablet cited above, for example, would fit into the board like this.

Jorge and Clara knew that if they completed the board correctly, that is, leaving only the square corresponding to the cursed tribe empty, a spring would be activated that would open the door to the secret chamber. If, on the other hand, they introduced the stone associated with the cursed tribe, they would be pierced by the darts prepared to scare away the pyramid raiders.

Thus, his plan was to fill in the table using first the figures that indicated the tablets corresponding to the allied tribes, and then continue adding symbols in some way, until only one square was left without a figure. Thus, there were two questions to be resolved:

– There was a cursed tribe among the eight, and it was crucial to exclude their tablet…but how to identify it?

– Assuming the cursed tablet has been discarded and once the seven chosen squares have been included, would they be able to fill in the rest of the squares on the board?

Inserting the symbols of the eight tablets corresponding to the eight tribes, they drew the partially filled board on a blackboard.

The first square of the board corresponded to the tablet of the tribe of the peacemaker priest; so, at least, that one would be well placed.

– That tablet stays – Jorge said emphatically. – Now let’s see what happens with the others. And, to make it easier, let’s use the numbers one through five, instead of the symbols:

In this way, adding the eight tablets and using the numerical encoding, they were left with a kind of sudoku on the board:

Jorge seemed increasingly worried.

– What tablet do we discard, Clara? A mistake would be fatal…

Clara began to search the Internet for information on “pre-Columbian sudoku”, with little success. But she found a very interesting page that talked about something called Latin squares.

– Look at this, Jorge – he told him – a Latin square is a table with the same number of rows as columns, which is filled with the integers {1,2,…,N} fulfilling that in each row and each column each of the numbers {1,2,…,N} appears exactly once.

– And there are still more. Latin squares are used to share secrets. There is something called “critical sets”, which are precisely sets of positions that can only be completed in one way to form a Latin square, just as a newspaper sudoku only has one solution. Thus, a critical set can be distributed among several people, forcing them to collaborate to rebuild the square because, furthermore, critical sets are minimal: if there is only one part of the critical set, it turns out that there is more than one way to complete the board, so it is not known which is the correct solution.

– Clara, I’m not sure I understand everything – Jorge got impatient – you help me decide how to eliminate a tablet and we better not make mistakes. Let’s rewrite the numerical encoding of the tablets –

Clara didn’t push herself.

– This is what we have:

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)

– The challenge consists of eliminating one of the eight figures from the initial position, which will correspond to the cursed tribe. And fill in the rest of the table… – Clara’s eyes were shining now – I know we are risking our lives, but I think the method that just occurred to me will work…

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.

Maria Isabel Gonzalez Vasco She is a professor of Applied Mathematics at the Rey Juan Carlos University and a member of the Governing Board of the Royal Spanish Mathematical Society.

SOLUTION TO THE PREVIOUS CHALLENGE

The functions hashes they are applications that assign to each value of a certain output set a summary value that (typically) belongs to a much smaller set. Formally, in fact, they are defined as applications that take a binary string (of zeros and ones) of any length and summarizes it into a string of fixed length. This final length is included in the implementations as part of the name of the hash function itself (see, for example, the case of functions of the SHA or BLAKE family). They are often used for quick checks (checking if two values ​​match by looking to see if their digests do) but their main role is to provide integrity checks, that is, they help detect changes to messages or code. For example, in this image we see the page from which a program for studying cryptography can be downloaded, where summaries are included for each download using the SHA256 hash function.

In this way, a user who downloads, for example, the Cryptool 1.4.42 program in Spanish, should check (by executing SHA256 on his computer) that the summary of the code obtained matches the string of bits that appears on the page (written in hexadecimal):

62f0681356e9b3a9cb32a13eccd8a61d9deb0a108ce17c8914668e7460601eab

For a function hashes be cryptographically useful, two conditions are required:

– Efficiency: the summaries must be easy and quick to calculate with minimal computational resources (a mobile phone, a desktop computer, etc.)

– Resistance to collisions: it should not be possible to efficiently calculate two initial values ​​with the same summary. This, in particular, will also imply that it is difficult to calculate a value with the same summary as another given one, or to reverse the application of the function (given a summary, calculate an associated initial value)

In the previous challenge, the proposed hash function performs a simple operation; keep the remainder by dividing each number by 1024. There are 1024 possible remainders {0,…, 1023}. It’s a really bad feature, as far as crash resistance is concerned. Since there are only 1024 summaries, at most one replay would be found when viewer 1025 entered (and at least two viewers had to enter the room for their summaries to collide).

Let us now answer the other questions; If we want to know how many tickets, within the allowed capacity, had the same summary as the number 4410, we have to count the numbers of the form 4410 + K(1024), with K an integer, that are between 1 and 10900. It is useful to take K = {-4,…, 6}, then there are 11 entries, which are specifically:

As for the number of entries with the same identifier but less than 99999, they would be, reasoning the same, all the numbers of the form 4410 + K(1024) , with K an integer, that are between 1 and 99999. We can therefore take K= {-4,…,93}, so there are 98.

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