How to fool a sudoku checker | Technology

Cryptography is not just about decrypting hidden messages. This time we challenge our readers to try to break the security of a tool called “interactive demonstration system”, which serves to demonstrate that we know a secret without revealing information about it. Such constructions are essential, for example, to develop identification mechanisms, since they allow the user to prove that he knows a password, without having to reveal it to third parties who could impersonate him.

In the high school playground puzzle games were successful. And Mario, Carla, Araceli and Hugo had become fond of Sudoku. Some colleagues edited the magazine Playground, whose last page contained a really difficult sudoku puzzle. The four of them would open the magazine together at the first recess of the week and compete to see who could solve it first. The rest of the breaks were spent chatting about how to organize a sudoku competition.

–As soon as one solves the sudoku, he shows it to the rest of us, and we check it– Hugo opined.

–That can’t be, because then we already see the solution, and the fun is over– continued Carla.

–Well, he shows it to any other classmate. Checking that a sudoku is well solved is easy, so anyone would be worth a checker – Araceli joined.

–Yes, but what I want is to verify that it is well resolved without revealing the solution, so that the others can continue fighting with it– Carla insisted.

“One thing occurs to me,” Mario said as he pondered. Instead of writing numbers we can use counters to fill in the grid. We put a token in each box with the number of the solution. If the number was already in the statement, the card is turned face up, and if it is one that we put when solving it, it is turned face down, so that the number is not seen. When the Sudoku is filled, the verifier chooses the row, column or box that he wants, then the one who has solved it will collect all the cards of that row, column or box, will shuffle them and show them so that the verifier can check that all the numbers are different.

–I think it’s a great idea!– Araceli exclaimed excitedly–, but with a row, column or box you don’t show that the complete sudoku is solved. It would be better for the checker to say “rows”, “columns” or “boxes” and to check, depending on his choice, one by one all the rows, columns or boxes.

“But we’re still in the same situation,” commented Carla now. The fact that the rows (or columns, or boxes) do not have repeated numbers does not guarantee that the solution is good, all three things have to happen at the same time. This reminds me of the story that the Maths teacher told us about a lady who said that, if she was given a cup of tea with milk to try, she could distinguish whether the tea or the milk had been poured first. A certain Fisher designed an experiment to check if what the lady said was true or not. The idea was that they subjected the lady to a blind tasting of cups of tea with milk. After tasting each cup, she was required to declare whether the tea or the milk had been poured first. The experiment was repeated many times and at the end, they calculated the probability of having been right as many times as her or more, if she responded completely at random. If that probability was very small, surely the lady was telling the truth.

“I think I’m following you,” said Mario. In our case, the verifier can choose “rows”, “columns” or “boxes”. Suppose he does it completely randomly, he will choose each of them with probability 1/3. Whichever you choose, if the Sudoku solver has the correct solution, he will be able to show the checker a positive result (no repeated numbers in each group). But, even if he doesn’t have the correct answer, if there are no repeated numbers in the same structure that the verifier has chosen (rows, columns or boxes), he will deceive him. The probability that a liar guesses right in advance the structure that the verifier is going to ask for and compose the numbers according to it is 1/3… and this is where the story of the tea taster comes in. We can repeat the experiment. The one who claims to have solved the Sudoku puts the tiles back, the verifier chooses again between rows, columns and boxes and the probability that a liar cheats him twice in a row will be 1/3 x 1/3 (that is, 1/ 9). The process can be repeated more times and we will end up catching a liar.

“What a complicated method!” Hugo complained. If we get too picky, we’re going to end up with 10 rounds to be satisfied with. Also, if there are only rows, columns, and boxes, there has to be some way to do the process with only three checks.

–Of course!– Araceli was encouraged to comment–, instead of a token in each cell, the participant puts a tower of three tokens (face up if they are the fixed cells and face down if they are the ones to be filled) and then the verifier is picking up and grouping cards placed in the cells of each row, each column and each box in the order he wants. Those of each of these groups are shuffled, the cards are turned over and it is verified that there are no repeated numbers, in which case, the solution would be correct.

–Not necessarily!– Carla said.– This technique will manage to detect many frauds, but it is not infallible. To simplify things, think of a 4×4 sudoku puzzle like this one.

It should be resolved first. And then (and that’s the challenge) you have to try to find some way of placing the three tiles in each box that doesn’t give a correct solution to the sudoku, but hopefully can fool the checker.

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.

Ignacio Cascos Fernandez He is a doctor in Mathematics and a professor in the Department of Statistics at the Carlos III University of Madrid.

SOLUTION TO THE PREVIOUS CHALLENGE

The solution to the challenge The mystery of the German soldier’s letter it is: Helga, the grandparents’ jewels are all buried under the birch, in the fig orchard. She stands with her back to the trunk, facing the church, and removes about eight inches of soil.

To decrypt, we use the Vigenère key: HIAVNDS (we take the first letter of each “verse”, just as the soldier has written the poem, which intuitively does not have the original meter). Various readers have arrived at this clue, but not all from the poem. These are some of the strategies that we have been told by email:

– Using “brute force”, that is, by means of a computer program, trying all possible Vigenère keys: first of length 1, then of length 2, etc. The “brute force” that some of you have done manually must have been very tedious, but you have been very ingenious in selecting possible keys (Tomás, we loved that you tried “TELEFUNKEN”).

– Assuming that the first word of the ciphertext is HELGA (as Joaquín or Alicia have done), and thus calculating the sequence of jumps used in the first 5 letters, to later deduce the rest in a similar way. There, again, we must assume that the Vigénere key is of length 5, 6, etc… and try possible jumps to find the complete key. For that it is better to program the search, for example, in Python language, as several have used.

– Directly using some program available on the internet to decrypt Vigènere (such as Julio or Manu, who have used Cryptii.com and Vigenere Solver. This is a bit of a cheat, but, you know, in love and in war…

We now detail the first steps of the decryption process (the rest are analogous):

Ciphertext:

omlbn, osz rotnv vl ton nemlton rvlhv tjqdk lvtzeuskis wnmg lt awrgms, mn zy kmlztj qh dha hdtxwyis. nvwmhbe yr hkwilynv ss brjafg, tqrvagg oicdn os polzfls, f zeovus bvon ihaube xrqlpueoerk km tdrujh.

The 0 has been obtained by encrypting with the H key, then we look at the row 7 corresponding to the H, we look for the letter 0 and we go up to the row 0 (of clear text); the letter we find is H.

The M has been obtained by encrypting with the key I, then we look at row 8 corresponding to the I, we look for the letter M, and we go up to row 0, obtaining the letter E.

The L has been obtained by encrypting with key A, then when encrypting the letter has not really been transformed into plain, then the letter of the plain text is also an L.

The B has been obtained by encrypting with the key V, then we look at the row 21 corresponding to the V, we look for the B, we go up to the column 0 and we find the corresponding letter, the G.

The N has been obtained with key N, then just above it, in row 0, we find its corresponding one in the clear: A.

Thus, omlbn is the HELGA cipher.

You can follow THE COUNTRY TECHNOLOGY in Facebook Y Twitter or sign up here to receive our weekly newsletter.