Read the original

Last article we introduced the basics of cryptography, I believe you have a good understanding of cryptography and related knowledge, if not read, you can click here to view 👉 RSA encryption (a) cryptography basics.

This article mainly explains the RSA encryption process, but before we talk about the encryption process we need to understand a few mathematical formulas. Are very simple, I believe that you will understand, the article encountered a link to the place, can skip first does not affect the reading. Let’s take a look at the introduction of RSA encryption.

Introduction to RSA Encryption

The diagram at the beginning of this article shows the three authors of RSA encryption, an algorithm developed in 1977 by Rivest, Shamir and Adleman, all of whom happened to be working at THE Massachusetts Institute of Technology (MIT), who put together the first letters of their surnames.

In 1973, four years before RSA was proposed, Clifford Cocks, a mathematician working at GCHQ, proposed an equivalent algorithm in an internal document, but it was kept secret until (sadly) published in 1997.

As we know from the previous article, RSA encryption algorithm is achieved by the difficulty of prime factor decomposition. In other words, the more difficult it is to factor an extremely large integer, the more reliable RSA algorithm is. If someone were to find a fast algorithm for factorization, the reliability of information encrypted with RSA would be severely reduced. But the chances of finding such an algorithm are pretty slim. Today only short RSA keys can be forcefully cracked. Until now, there was no reliable way to attack the RSA algorithm in the world. As long as the length of the key is long enough, the information encrypted with RSA can not be cracked. Because of the security of RSA encryption, RSA encryption algorithm is widely used in the current Internet information transmission.

It is no exaggeration to say that RSA encryption has been around for as long as there has been a computer network.

A mathematical formula

In order to understand RSA encryption, you need to know some number theory knowledge first. Here I have summarized some necessary formulas to better understand the encryption process.

1. Mutual relationship

Definition of a prime number: a number that is not divisible by any number except 1 and itself. For example: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…

2. Any two primes form a prime relationship. For example, 5 and 7 are divisible by no number except 1.

3. Prime A is interprime with numbers that are not multiples of it. For example, 5 can be interchangeable with 1, 2, 3, 4, 6, 7, 8, 9, 11.

2. Euler function

For any positive integer n, the Euler function is to calculate the number of numbers smaller than n that are mutually compatible with nFor example:

Calculate the euler function of the integer 8: the mutual relationship with 8 is 1, 3, 5, 7, so φ(8) = 4.

From the third article in the mutuality relation above, we can know that when n is a prime number, all numbers smaller than n form a mutuality relation with n, so:

N is prime: φ(n) = n-1

According to the Chinese residual theorem (also known as Sun Tzu theorem), we can get: The Euler function of the product of two mutually quality integers P and q is:

φ(PXQ) = φ(p)φ(q)

So when p and q are both prime numbers, according to the above formula φ(n)=n-1, we can get:

Phi (PXQ) = (p – 1) (q) – 1)

It is enough to know euler’s formula for this case. For more information about Euler’s function, you can go to 👉

Euler’s theorem

Now, before WE introduce Euler’s theorem, let’s do the mod. We all know that the remainder of 5 divided by 4 is 1, which is expressed as 5=1(mod4) in mathematics. Because the symbol for calculating the remainder in the computer is %, the following formula is uniformly expressed in the form of 5%4=1, which is both concise and easy to understand.

Euler’s theorem: if positive integers A and N are mutually prime

% n=1

Like the above, the greatest theorems are often quite succinct. ** How to prove Euler’s theorem, interested students can check 👉 here

Another related concept is that if positive integers A and N are mutually prime, there exists an integer B such that:

ab % n=1

B is called the modular antielement of A. Does b exist? Euler’s theorem can be written as:

a x % n=1

So b =When the above formula is true, so B must exist.

For the following encryption and decryption process, we mainly use the following two formulas:

RSA encryption and decryption process

Generate public and private keys

1. Randomly find two unequal prime numbers P and Q

For convenience, we take p=5 and q=11 (in practice, larger p and q are harder to crack).

2. Calculate the product of p and q n = p x q

N = 5 x 11 = 55 (the binary length of n is called the key length of RSA encryption, where 55 is represented as the binary number 110111, the length is only 6 bits, in practice, 1024 bits or 2048 bits higher)

3. Calculate the Euler function φ(n) of n, according to the euler function we deduced above, get: φ(n)=(p-1)(Q-1)

φ(n) = 4 x 10 = 40

4. Select an integer e at random, if 1< e < φ(n) and e and φ(n) are mutually prime.

E and 40 should be mutually quality. For convenience, we take E = 3 (65537 in practice).

5. Calculate the inverse element d of e with respect to φ(n)

3d = k40+1, when k=2, we get d=27.

6. Encapsulate E and N as public keys (e,n) and D and n as private keys (D,n).

Public key :(e=3, n=55)

Private key :(d=27, n=55)

encryption

Above we have calculated the public and private keys according to the asymmetric encryption flow in the previous article. Send Sends the encryption operation after receiving the public key.

Suppose we now want to send a message m=4 and the public key is (e=3,n=55)

M must be an integer (to convert the sent message to decimal via ASCII) and m

Calculate ciphertext: c = % n

That is, ciphertext C =%55 = 64%55 = 9

Sending Convenience Ciphertext 9 is sent to the recipient over the network.

decryption

After receiving the ciphertext c=9, the recipient uses its own private key (d=27,n=55) to decrypt it.

Calculation text: m = % n

That is, m =% 55 = 4 (see 👉 for a simple derivationhere, or programmatically verified)

The receiver then gets the message the sender wants to send, and the whole encryption and decryption process is over.

conclusion

It can be seen that the RSA encryption and decryption process is not complicated, and there are only two formulas used, but there are still some problems waiting for us to explore, for example:

  • M
  • Is RSA really secure between public keys and ciphertext?
  • Why is m equal to% n?

Let us know what you think in the comments, and we’ll bring you answers in our next post.