The situation is this: there are Two allies who are in war against an enemy with spies very unplanted: how they can do for exchange secret messages Without these fall into the enemy’s hands? The great protagonists of the answer to this question are the prime numbers, that is, those positive internal numbers that do not have other dividers if not 1 and themselves. But what do the prime numbers have to do with two kings who want to communicate with each other safely? By solving this problem we will discover the key idea behind many Safe communication protocolsbased on the fact that the multiplication of very large prime numbers It is an easy operation that can be used to make an illegible message, while break down a number into first factorsThat is, trying to recover the initial message can take a long time.
But how? We see it in this article.
The problem of the two kings who want to communicate in secret
To understand what it means encrypt (or encryp) a message in order to make it illegible To any unknown person who finds him in his hands, we consider this imagination situation.
King Gino must send to King Pino, without being intercepted by the skilled enemy spies, a vital message for the fate of the two kingdoms. The blacksmiths of the two kings know how to create indestructible bauli and packets, impossible to open without a key. Re Gino puts the message in a trunk, closes it with a padlock and sends it to King Pino. If during the journey the trunk was intercepted by a spy could not be opened, but even King Pino could open it without a key. King Gino could then send the key to King the key separately from the trunk, but a spy could intercept both key and trunk and thus opening it: the key cannot travel, it is too dangerous! So, how to make the trunk that cannot be opened for the spies, but can be opened by King Pino?
To find an answer to this question, we must think of a particular key, i.e. i Prime numbers.
The long journey of the message: how to make it secret for everyone but not for the two kings?
The two kings realize that sending a physical key is risky, and thus conceive the stratagem of Two Padlocks:
- Re Gino puts the message in the trunk, closes it with a blue padlock of which only he has the key and sends the trunk so tight to King Pino
- King Pino receives the trunk and strengthens his closure with a Second red padlock of which only he has the key, and refers him to King Gino very closed with the two padlocks
- King Gino at this point takes away The red padlock From the trunk using his key and postpone it to Pino. At this point the trunk is still closed with the blue padlock, of which King Pino has the key!
- King Pino receives the trunk and, having the right key, takes away The blue padlock, thus managing to open the trunk e Read the secret message.
The message starts from King Gino and arrives and King Pino well hidden inside the trunk without any spy can read it, because the two keys necessary for reading the trunk have always remained safe in the hands of the two kings!
We can say that the message It was in fact cipheras those who deal with encryptionthe discipline that studies how transform a message clear – that is, clearly legible – In another message cipher – that is, counterfeit – so that it is incomprehensible to those who do not know the details of the technique used for transformation.
At this point comes to be wondered: But what do the prime numbers have to do with it?
Prime numbers are an excellent secret key to hiding a message
What we have just seen was, of course, an example of fantasy in which to “tighten” a message we used of the padlocks. In practice, how do we allucatar a message, considering that the channels we use to communicate are digital and non -physical? A trunk and two padlocks are not enough.
The exchange of digital messages – like sms or WhatsApp – takes place substantially in the form of Numbers sequences. For example the word “HI” could travel like “39115”where each letter was replaced by its position in the alphabet. It is clear, however, that such a encryption is very easy to decipher: by combining the letter of the corresponding alphabet with each number of the sequence, we have three possible hypotheses: 3-9-1-1-5 which corresponds to ciaae, 3-9-15 which corresponds to HI, or 3-9-11-5 that is Cike. It is not difficult to guess that the word sent is the second hypothesis, that is HI.
Something more complex must therefore be thought: not only therefore to combine numbers in letters, but make certain operations on these numbers. We try to understand it with an example.
Suppose ours secret message Both the number and the letter F to which we combine the number 6. To disguise the message, we can multiply it by a secret number that we decide – said key – So as to obtain an additional number. For example, we choose the number 5, which multiplied by our message 6 gives the number 30 as it will be, which will be ours cyphrus. If a light intercepted the number 30, not knowing the key, it would have difficulty recognizing the secret message because he does not know he must divide for 5 thus obtaining 6 and finally the letter F. However, he could imagine that we have obtained the number through a simple operation And after some attempt it would probably come to guess that it is a multiplication and, writing all the products that give 30 as a result, would obtain: 6 × 5, 2 × 15, 3 × 10, 2x3x5, 30 × 1. At this point the light would not know what exactly the message is, but it would certainly have restricted the possibilities: he knows that it is a number between 1, 2, 3, 5, 6, 10, 15, 30. In short, multiply by 5 seems Don’t be a tactic then so impenetrable. So how to do it?
This is where i Prime numbers: break up A number as a product of numbers is all the more difficult The larger the first numbers that make it up. If instead of the number 5 we used a huge first number as a key, for our warning light to decomposing the number it could become such an arduous and long task that it makes it desist.
From the trunk to prime numbers: what digital kings would have done
Let’s go back to the history of Two kings And we try to better understand how numbers can replace the two Padlocks with two secret numerical keys, Each of the two notes only to the king who owns it. Let’s imagine that King Gino and King Pino live today and then use digital. What could they do to cheat the spies? For example, they could do this:
- King Gino figure the message 6 multiplying it by the first numerical keyfor example 5 (we use a small first number for convenience, but as we mentioned above the best choice is to use a huge first number!); Once encrypted, send 6 × 5 =30 to King Pino;
- King Pino Multiply 30 for the second personal keyfor example 7, and send 30 × 7 =210 to King Gino;
- King Gino takes his “padlock” dividend 210 for the first keyMeaning what 5, and send 42 to King Pino;
- At this point King Pino can completely decipher the message with the second keydividend 42 For 7 And get the starting message: 6.
In the image above you can see how the message 6 starts from King Gino and arrives at King Pino without ever being visible since he always travels hidden, first inside the number 30then in 210 and finally in 42.
Many communication protocols – that is, the processes that are used to make the messages we use as sure as possible – are based on solutions similar to that adopted by the two digital kings and, even if they encrypt messages with more complicated operations than simple multiplication, still use the product of very large prime numbers. One of the most popular is called RSA And it was made public in 1977 through a challenge that provided for the decomposition into first factors of a number of 129 digits: only in 1994 a team of 600 volunteers managed to complete the challenge, after 17 years, once that would have made any light desists !
