It’s much easier to multiply numbers together than to factor them apart. That’s the basics of RSA encryption.

In particular, the RSA encryption works with two large primes *p* and *q*, is quickly and easy to find the product *pq* but it is harder to recover the factors *p* and *q* from *n*. Generally *p* and *q* are numbers with hundreds of digits, factoring a number of this magnitude is very slow.

### The algorithm

To encode the message we need *n = pq* and a positive integer *e* that

be reversible module φ (n). We talk about the Euler’s totient function before.

We will call the **encoding key** pair *(n, e)* of the RSA system. We will encode each message block separately and the final message will be the coded blocks sequence.

Important: Blocks already encoded can not be assembled to form a new number. This should make decoding impossible, as we’ll see later!

Let’s now show how to encode each block *b*. We will call the coded block of *C(b)*. First, remember that *b* is an integer smaller than *n*. We calculate *C(b)* as follows:

where *0≤C (b) <n*.

Let’s see how to decode a block of the encoded message. The information we need to be able to decode consists of two numbers: *n* and the inverse of *e* module *φ(n)*, which we denote *d*. We will call the pair *(n, d)* of **decode key.** Be the one block of the message encoded. Then *D(a)* will be the result of the decoding process. The way to calculate *D(a)* is:

where *0 ≤ D (a) <n.*

First, it is very easy to calculate *d*, if we have *φ(n)* and *e* : simply apply the extended Euclidean algorithm. On the other hand, it is clear that if *b* is a block of the original message, then we expect *D(C(b)) = b*, otherwise we will not have a useful code.

Finally, since the beginning of the notes we have been insisting that we encode using *n* and decode using *p* and *q*; so you need to factor *n* to decode. At this point we see that is not strictly true. In addition to the *n* itself, we only need to know the inverse *d* of *e* modulo *φ(n)* to decode. It turns out that we only know how to calculate *d* by applying the extended algorithm to *e* and *φ(n)*.

### Proof that RSA works

The obvious question which now arises is: *D(C(b)) = b*?

That is, by decoding a coded message block, can we find a block of the original message? Because otherwise all our effort was meaningless …

Consider then *n = pq*. We will prove that *D(C(b)) ≡ b mod (n)*.

How *1≤ b, D (C (b)) ≤ n-1*.

By definition, we have:

But *d* is the inverse of *e* module *φ(n)*. Then there is an integer *k* such that *ed=1 + kφ (n).*

Soon,

If *b* and *n* are relatives primes, then we can use Euler’s Theorem:

Suppose that *b* and *n* are not prime to each other. Since *n = pq*, *p* and *q* are distinct primes, then *φ(n) = (p-1)(q-1)*.

Soon,

If *b* and *p* are relative prime, then we can use Fermat’s Theorem, and we have bᵖ⁻¹ ≡ 1 mod (p).

Therefore, *bᵉᵈ ≡ b mod (p)*, whichever is *b*.

We do the same for prime q, we get, *bᵉᵈ ≡ b mod (q).*

Therefore,

as we wanted.

### Implementation

As an developer I have a necessary to put code in everywhere, even when don’t need it, so I will put here a simple implementation of this algorithm, and that can be useful later

## Discussion (0)