Jorge and Clara worked for months as archaeologists in a pre-Columbian pyramid in southern 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.
More information
Eight tribes had contested power in the region. A peace-making priest, head of one of the tribes, managed to form an alliance signed by seven of them, who later guarded the pyramid. The eighth tribe was considered cursed. Each tribe appeared in different archaeological remains, represented by a square figure containing a trio of symbols. For example, this was the tablet of one of the tribes:
The country
The door of the chamber they wished to enter had a sort of board drawn on the floor, with rows and columns precisely indexed with these symbols, in which for each row and column position was a single stone with the could be used in the form of one of the five different symbols found. It was known from earlier excavations that the three symbols on each panel are to be interpreted as a row-column symbol. For example, the tablet mentioned above would fit into the circuit board like this.
the country
Jorge and Clara knew that if they filled in the board correctly, that is, leaving only the space corresponding to the cursed tribe, a spring would be activated that would open the door to the secret chamber. On the other hand, if they introduced the stone associated with the cursed trunk, they would be pierced by the arrows ready to deter the pyramid robbers.
So his plan was to first fill in the table with the numbers that indicated the tablets of the allied tribes, and then add more symbols in some fashion until there was only one cell left with no number. So two questions had to be answered:
– There was a cursed tribe among the eight, and ruling out their tablet was crucial… but how to identify them?
– Suppose the cursed board was thrown away and once the seven chosen squares are included, could they fill in the remaining squares on the board?
They inserted the symbols of the eight tablets corresponding to the eight tribes and drew the partially filled tablet on one tablet.
the country
The first square of the board corresponded to the tablet of the Peacemaker’s tribe; so at least one would be well positioned.
the country
– This tablet stays – said Jorge emphatically. – Let’s see what happens to the others. And to make it easier, instead of the symbols, let’s use the numbers one through five:
the country
In this way, by adding the eight boards and using numerical coding, a kind of Sudoku remained on the board:
the country
Jorge seemed increasingly concerned.
– Which pill are we throwing away, Clara? A mistake would be fatal…
Clara began searching the internet for information about “pre-Columbian Sudoku” with little success. But he found a very interesting site that talked about so-called Latin squares.
– Look at that, Jorge – he told him – a latin square is a table with the same number of rows as columns, filled with the integers {1,2,…,N}, which in each Each of the numbers {1,2,…,N} occurs exactly once in each row and in each fulfilling column.
– And there’s more. Latin squares are used to share secrets. There is such a thing as “critical sentences”, which are precisely sets of positions that can only be completed in one way to form a Latin square, just like a newspaper sudoku has only one solution. Thus, a critical set can be divided among several people, forcing them to work together to rebuild the square, because, moreover, critical sets are minimal: if there is only 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 dispose of a pill and we better not make mistakes. Let’s rewrite the numerical coding of the tablets –
Clara didn’t push.
– We have this:
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 is to eliminate one of the eight characters from the starting 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’re risking our lives, but I think the method I just came up with will work…
Crypto Challenges are 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 themselves is advised not to read it until they crack the riddle. You can also send your answers to the email address [email protected]. With each new challenge we publish the solution of the previous ones accompanied by a comment with some original or inspiring ideas that we received.
Maria Isabel Gonzalez Vasco She is Professor of Applied Mathematics at Rey Juan Carlos University and a member of the Board of Directors of the Royal Spanish Mathematical Society.
SOLUTION TO THE PREVIOUS CHALLENGE
Hash functions are applications that assign each value in a given output set a hash value that (typically) belongs to a much smaller set. Formally, they are actually defined as applications that take a binary string (made up of zeros and ones) of arbitrary length and concatenate it into a fixed-length string. This final length is included in the implementations as part of the name of the hash function itself (see for example the case of SHA or BLAKE family functions). They’re often used for quick checks (verifying that two values match by looking to see if their digests match), but their primary role is to provide integrity checks, meaning they help detect changes to messages or code. For example, in this image we see the page from which a program to study cryptography can be downloaded, where summaries are included for each download using the SHA256 hash function.
THE COUNTRY
In this way, a user who downloads, for example, the Cryptool 1.4.42 program in Spanish should check (by running SHA256 on his computer) that the summary of the code obtained agrees with the bit sequence that appears on the page (written in hexadecimal):
62f0681356e9b3a9cb32a13eccd8a61d9deb0a108ce17c8914668e7460601eab
For a hash function to be cryptographically useful, two conditions are required:
– Efficiency: The summaries must be easy and quick to calculate with minimal computing resources (mobile phone, desktop computer, etc.).
– Collision resistance: It should not be possible to efficiently calculate two initial values with the same summary. In particular, this also implies that it is difficult to compute a value given the same summary as another, or to reverse the application of the function (compute an associated initial value given a summary).
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 goes. Since there are only 1024 summaries, at most one replay would be found if viewer 1025 entered (and at least two viewers had to enter the room for their summaries to collide).
Now let’s 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 need to count the numbers in the form 4410 + K(1024), where K is an integer, ranging from 1 to 10900 It makes sense to take K = {-4,…, 6} then there are 11 entries which are concrete:
THE COUNTRY
As for the number of entries with the same identifier but less than 99999, for the same reasoning, this would be any number of the form 4410 + K(1024) , where K is an integer ranging from 1 to 99999. So we can take K= {-4,…,93}, so there are 98.
Follow EL PAÍS TECNOLOGÍA on Facebook and Twitter or sign up here to receive our weekly newsletter.