RSA Example

Illustration of RSA work by example

Around the encryption algorithms with an open and private key there are many misunderstandings and mystifications. Here I would like to show very briefly and clearly, with concrete numbers and minimum formulas, how this works.

I do not go into the theory (it's not very clear what level of preparation the reader should expect), but I'm sure that after reading this short illustration, it will be easier for any person to understand the formulas and strong evidence.


So. Let's say I want to get some data from you. We do not want you to be recognized by anyone other than us. And we do not have any confidence in the reliability of the data transmission channel. Let's get started.

Step one. Preparation of keys

I need to do some preliminary steps: generate a public and private key.

I choose two prime numbers. Let it be p = 3 and q = 7.
We compute the module - the product of our p and q: n = p × q = 3 × 7 = 21.
We calculate the Euler function: φ = (p-1) × (q-1) = 2 × 6 = 12.
We choose a number e that meets the following criteria: (i) it should be simple, (ii) it should be less than φ - there are options: 3, 5, 7, 11, (iii) it should be relatively prime to φ; there remain variants 5, 7, 11. We choose e = 5. This, so-called, open exponent.
Now the pair {e, n} is my public key. I send it to you so that you encrypt your message. But for me it's not all. I need to get a private key.


I need to calculate the number d, the inverse of e modulo φ. That is, the remainder of dividing modulo φ of the product d × e must be 1. We write this in the notation adopted in many programming languages: (d × e)% φ = 1. Or (d × 5)% 12 = 1. d can be equal to 5 ((5 × 5)% 12 = 25% 12 = 1), but that it does not confuse with e in the following narrative, let's take it equal to 17. You can check for yourself that (17 × 5)% 12 is actually 1 (17 × 5-12 × 7 = 1). So d = 17. The pair {d, n} is a secret key, I leave it with me. It can not be communicated to anyone. Only the owner of the private key can decrypt that which was encrypted with the public key.

Step two. Encryption

Now it's your turn to encrypt your message. Let's say your message is 19. Let's call it P = 19. In addition to it, you already have my public key: {e, n} = {5, 21}. Encryption is performed using the following algorithm:

Raise your message to the power of e modulo n. That is, calculate 19 to the power of 5 (2476099) and take the remainder of the division by 21. It turns out 10 - this is your encoded data.
Strictly speaking, you do not need to calculate a huge number of "19 to the power of 5". For each multiplication it is enough to calculate not the complete product, but only the remainder of dividing by 21. But this is the details of the implementation of calculations, let's not go into them.

Received data E = 10, you send me.


Here it should be noted that the message P = 19 should not be greater than n = 21. otherwise nothing will turn out.

Step three. Explanation

I got your data (E = 10), and I have a private key {d, n} = {17, 21}.

Please note that the public key can not decrypt the message. And I did not tell anyone the private key. This is the beauty of asymmetric encryption.

We start to decode:

I do an operation that is very similar to yours, but I use d instead of e. I'll raise E to the power of d: I get 10 to the power of 17 (let me not write a one with seventeen zeros). I calculate the remainder of dividing by 21 and get 19 - your message.

Note that no one except me (even you!) Can decrypt your message (E = 10), since no one has a private key.

What is the guarantee of encryption reliability

The reliability of encryption is ensured by the fact that it is very difficult for a third person (trying to crack the cipher) to compute a private key over an open one. Both keys are computed from one pair of primes (p and q). That is, the keys are interconnected. But to establish this connection is very difficult. The main snag is the decomposition of the module n into simple factors p and q. If the number is the product of two very large primes, it is very difficult to factor it.

I will try to show this with an example. Let's factor the number 360:

immediately clear. that it is divided into two (got 2)
the remaining 180 too, apparently even (2 more)
90 - also even (another two)
45 is not divisible by 2, but the next attempt is successful - it is divided into three (got 3)
15 is also divisible by 3
5 - simple.
We at every step, practically without busting, were getting more and more multipliers, easily obtaining a complete decomposition 360 = 2 × 2 × 2 × 3 × 3 × 5

Now let's take the number 361. Then we'll have to suffer.

it is not even
three - no, not shared
five (for example, we act smartly and only sort out simple numbers, although, in practice, the search for large prime numbers, in itself, is a difficult task) - does not fit
seven? - no.
...
and only 19 will give us the answer: 361 = 19 × 19.

When using large numbers, the task becomes very complicated. This allows us to hope that the cracker simply does not have enough computing resources to break your code in the foreseeable future.

And how does it all work in practice?

Many readers ask how all this is applied in practice. Let's look at a slightly more close to life example. We will encrypt and decipher the word "MOLE", proposed by one of the readers. And at the same time, we will quickly consider what problems are encountered and how they are solved.

First, we generate keys with slightly larger numbers. They are not so obvious, but they will allow us to encrypt not only numbers from zero to 20.

We repulse a pair of primes {p, q} = {17, 19}. Let our public key be {e, n} = {5, 323}, and closed {d, n} = {173, 323}.

We are ready for encryption. Let's translate our word into a digital representation. We can take simply the numbers of letters in the alphabet. We get a sequence of numbers: 11, 17, 15, 19.


We can encrypt each of these numbers with the public key {e, n} = {5, 323} and get the encryption 197, 272, 2, 304. These numbers can be transferred to the recipient who has the private key {d, n} = {173, 323 } and he decodes everything.

A little about the complexities

In fact, the described encryption method is very weak and never used. The reason is simple - encryption by letter. The same letter will be encrypted with the same number. If an attacker intercepts a sufficiently large message, he will be able to guess its contents. First he will pay attention to the frequent codes of spaces and will divide the cipher into words. Then he will notice one-letter words and guess how the letters "a", "and", "o", "c", "k" are coded ... Through a short search, he will compute additional letters for short words like "but", "not ", "by". And for longer words, easily restore all the remaining letters.

Thus, an attacker does not have to guess your secret keys. He will hack your message without knowing them.

To avoid this, special additional algorithms are used, the essence of which is that each previous part of the message starts to affect the next one.

Simpler, it looks like this. Before encryption, we apply a rule to the message: b: = (b + a)% n. Where a is the previous part of the message, and b is the next. That is, our message (11, 17, 15, 19) is changing. 11 remains unchanged. 17 turns into (11 + 17)% 323 = 28. 15 becomes (15 + 28)% 323 = 43. A 19 turns into 62.

The sequence (11, 28, 43, 62) turns out to be "confusing". All the letters in it are mixed, in the sense that each code is affected not by one letter, but all the previous ones.

The person who receives your message will have to do the opposite operation, with the minus sign: b: = (b - a)% n. And only then he will receive the codes of letters.

In practice, random and meaningless letters are added to the original message in the initial message. To even the first code it was impossible to understand anything. The recipient simply discards the beginning of the message.

That is, we can add a random number to the beginning and get (299, 11, 17, 15, 19). After mixing, it turns out: 299, 310, 4, 19, 38. After encryption, it will no longer be possible to guess where there was a letter.

In real life, it's still a little more complicated. Blocks for which the message is longer than one letter. Therefore, first, alignment algorithms are applied, then blocking algorithms with entanglement, and then RSA-encryption itself is applied.

The recipient does everything in the reverse order: decrypts, "unravels" the blocks and discards unnecessary information added just for alignment (so that the message can be divided into an entire number of blocks).


Details and principles of forming blocks can be read here. I in this note wanted to tell only about RSA. Here, it was possible.