Why  RSA Criptography works?
Tags: proofofconcept, crypto, mathematics, python
Published: 2019-04-06 16:08:25

---
title: Why  RSA Criptography works?
published: true
tags: proof-of-concept,crypto,mathematics,python
canonical_url: 
---

![](https://cdn-images-1.medium.com/max/1024/1*Y3_lZTDC3ARsNpGSbyg0Pg.jpeg)

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.](https://dev.to/pemtajo/euler-fermat-and-primality-test-2dc8)  
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:

![](https://cdn-images-1.medium.com/max/198/1*4zDFCGccZ8DMo1umjGetXg.png)

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:

![](https://cdn-images-1.medium.com/max/212/1*px6aU2jIUGYE5TpsUQfKhQ.png)

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)_.

![Alt Text](https://media.giphy.com/media/hyPsnhMnltMhq/giphy.gif)

### 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:

![](https://cdn-images-1.medium.com/max/335/1*SYMXQkVQAvE7ZIrnsrKljQ.png)

But _d_ is the inverse of _e_ module _φ(n)_. Then there is an integer _k_ such that _ed=1 + kφ (n)._  
Soon,

![](https://cdn-images-1.medium.com/max/282/1*o_rMOeSCjobzqpDrqgH47Q.png)

If _b_ and _n_ are relatives primes, then we can use [Euler’s Theorem](https://dev.to/pemtajo/euler-fermat-and-primality-test-2dc8):

![](https://cdn-images-1.medium.com/max/313/1*VBny99LCYz9khl8KHta3Cw.png)

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,

![](https://cdn-images-1.medium.com/max/215/1*zIXL3s2Xuv69nQ9K0PXk8g.png)

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,

![](https://cdn-images-1.medium.com/max/196/1*M-3_xtH9Jv4B8iC72TYrqw.png)

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

![](https://cdn-images-1.medium.com/max/1024/1*zL2la0u4YBEtTofwqbDBtw.png)<figcaption>The code is <a href="https://github.com/pmdragon/scripts/blob/master/rsa.py">here</a></figcaption>