Les nombres premiers en cryptographie

Good morning everyone, today as you can see on the board, I am going to talk to you about prime numbers and how it can be very useful in cryptography but also in the protection of our data.

First of all, cryptography is the art of encrypting messages or data in order to insure its protection. In other words, cryptography seeks to insure the confidentiality of data by turning a normal massage (plaintext) into an unintelligible one (cipher text) for any other person who is not the addressee.

Over time, cryptography became an essential tool in many regards such as the protection of private data, securing highly confidential messages, the protection of bank operation on the Internet, etc.

By the way, a memorable step of the evolution of cryptography is definitely the Second World War, with the use of the Enigma machine by Germans, which was defeated by British and polish mathematicians including Alan Turing.

The advent of computer science and Internet has considerably increased available resources to decode an encrypted message. Indeed, a computer can realize billions of calculations in one second.

Let’s take an example: The PIN code of a mobile phone or a debit card is composed of four digits. There are 10 possibilities for each digit (0, 1, 2, 3 and so on until 9), there are 10 000 different PIN codes (10 to the 4th power). If a human being tries to find the right code by trying all the possibilities out, it would take several hours. However, a computer which can do over millions of tests per second would have tested all the possibilities in one-hundredth of a second. Only parry was to limit the number of attempts to three. Computer or not, there is only 0.03% of chances to find the good code during the 3 attempts.

Faced with the development of those machines, cryptography had to reinvent itself. Since then, it has to use methods whose deciphering needs a huge number of calculations, unbearable including for computers. That’s where prime numbers step in.

Before we continued: What is a prime number? : It’s a whole number greater than 1 that cannot be exactly divided by any whole number other than itself and 1. For instance, 2, 3, 29 and 71 are prime numbers but not 1.

The RSA encryption system uses prime numbers to encrypt data. The reason for this is that of how difficult or hard it is to find the prime factorization. This system, which was developed by Ron Rivest, Leonard Adleman, and Adi Shamir in 1977, allows for secure transmission of data like credit card numbers online.

Based on all kinds of arithmetic calculations (exponent, division with remainders, etc.), it uses an elementary theorem of arithmetic which is: “all whole numbers strictly greater than 1 can be written as a product of prime numbers.” But its security key depends on prime numbers.

The RSA algorithm is the basis of a cryptosystem which enables public key encryption and is widely used to secure sensitive data, particularly when it is being sent over an insecure network like the internet.

Public key cryptography, also known as asymmetric cryptography, uses two different but mathematically linked keys - one public and one private. The public key can be shared with everyone, whereas the private key must be kept secret. In RSA cryptography, both the public and the private keys can encrypt a message. The opposite key from the one used to encrypt a message is used to decrypt

...