In the previous two weeks we have discussed encrypted messages and the first and simplest techniques used to encrypt them (the substitution cipher and the shift cipher or Caesar cipher), as well as the supposedly unbreakable Vigenère cipher, which introduces the concept of key: a word or phrase that is necessary to know in order to decipher the message.
Now let’s change the subject for a moment (albeit only apparently). What numbers complete the following sequence?
4, 6, 9, 10, 14, 15, 21…
And, even more difficult, what numbers complete this other sequence, first cousin of the previous one?:
121, 143, 169, 187, 209, 221, 247…
The “first cousin” comes to mind because the thing is about prime numbers. And that’s why she said that the change of subject was only apparent, because prime numbers play an important role in modern cryptography.
Until a few decades ago, cryptography, apart from its theoretical (and also recreational) interest, was only a practical matter for intelligence services; but with the emergence of information technology and the universalization of network operations, the possibility of sending confidential information (account numbers, passwords, etc.) in a secure way, but at the same time fluid and easy to handle, has become become a priority. And that’s where the elusive prime numbers come in.
Without going into details (for now: we’ll do it later), let’s say that there are encryption and decryption systems that are based on handling public and private keys at the same time, and that the former can be based on the product of two very large prime numbers. large. Let’s look at a simplified example:
I receive, publicly (or insecurely), the number 135143, which is the product of two primes, of which I know one, which is 149; Dividing 135143 by 149 I obtain the other prime factor, 907, which will allow me, after the pertinent operations, to decode a message or access reserved information. Too easy to discover? If you didn’t know that 149 was one of the factors, you would have to try about thirty primes before you found the factorization. If it still sounds easy, try factoring the following numbers, which are the product of two primes:
2117
4087
7387
9167
They all end in 7, but obviously it doesn’t have to be that way. In how many different ways can the product of two multi-digit prime numbers end?
RSA
But what for human brains is long and laborious, for electronic brains it is an almost instantaneous task, and that is why huge prime numbers are currently used, with hundreds of digits, unassailable even for the most powerful computers.
The best-known algorithm based on the product of great primes is RSA (by the initials of its creators: Rivest, Shamir and Adleman), developed in 1979 and widely used since then. Some think that quantum computers will easily solve the factorization problem; but others think that not even those very powerful machines will be able -when we have them- to decipher messages encrypted with the RSA algorithm and the like. Has the goal of unbreakable encryption finally been achieved?
You can follow MATTER in Facebook, Twitter and Instagramor sign up here to receive our weekly newsletter.
#Encryption #prime #numbers