RSA cryptosystem - Proofs of correctness

RSA Introduction

Most of us know RSA cryptosystem which is the most widely spread cryptosystem even today. The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem. In RSA, the process of encryption and decryption is depicted in the following illustration.






RSA Algorithm

Now let’s drill down this $encryption (E)$ and $decryption (D)$ process furthermore. As we all know the RSA algorithm [1] works as follows:

  • Choose two prime numbers $p$ and $q$,
  • Compute the modulus in which the arithmetic will be done: $N = pq$,
  • Pick a public encryption key $e \in Z_n$,
  • Compute the private decryption key as $d$ such that $ed = 1\; mod\; \phi(N)$,
  • Encryption of message $m: c = m^e\; mod\; N$,
  • Decryption of ciphertext $c: m=c^d\; mod\; N$.

Proof

Our simple proof  uses the Euler-Fermat Theorem. Let’s first have a look at it.

Euler-Fermat Theorem

Let $n$ be a positive integer, and let $a$ be an integer that is relatively prime to $n$. Then

$$\Large a^{\phi(n)} \equiv 1 \; (mod \; n)$$

Where $\phi(n)$ is Euler’s totient function, which counts number of positive integers $\le n $ which are relatively prime to $n$. [2] 


The number of integers in $Z_m$ , relatively prime to $m$ is denoted by $\phi(m)$.
It works for messages $m$ that are relatively prime to the modulus $n$, such that $gcd(m, n) = 1$ by definition where $gcd$ stands for greatest common divisor of $m$ and $n$.
 

Suppose $gcd(m, n) = 1$.
Since $e (encryption)$ and $d (decryption)$ are inverse functions, by definition,
$ed \equiv 1 (mod\; \phi(n))$

To get the $\phi(n)$, you have to use Euler's Totient Function. Let’s take an example[2] to clarify this.

$m = 6$, $Z_6 = \{0, 1, 2, 3, 4, 5\}$
$gcd(0, 6) = 6$
$gcd(1, 6) = 1$
$gcd(2, 6) = 2$
$gcd(3, 6) = 3$
$gcd(4, 6) = 2$
$gcd(5, 6) = 1$

So according to Euler's Phi Function $\phi(6) = 2$ which is the count of values $n \in Z_n$  such that $gcd(m, n) = 1$


Computing $\phi(m)$ for a large number which has $1024$ bits following the above naïve approach is not possible. So how can we compute this for really long numbers say $1000$ bits long numbers. Luckily there’s a way: Euler's Phi Function.


Theorem 6.3.1 Let $m$ have the following canonical factorization
$$\Large m = p_1^{e_1} \cdot p_2^{e_2}\cdot \ldots \cdot p_n^{e_n}$$,
Where the $p_i$ are distinct prime numbers and $e_i$ are positive integers, then
$$\Large \phi(m) = \prod_{i=1}^n (p_i^{e_i}-p_i^{e_i-1})$$ [3]

Notice the canonical use of prime factors above. Let’s take an example.
$m = 240, \phi(240) = ?$

Writing $m$ by its prime factors yields,
$$m = 2^4 · 3 · 5 $$
$$= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3}$$


Applying to the equation, $n = 3$ since only $3$ distinct prime factors exists above.
$$\phi(240) =  (2^4 - 2^3) \cdot (3^1 - 3^0) \cdot  (5^1 - 5^0) = 8 \cdot 2 \cdot 4 = 64$$, so you get $64$ lines where $gcd \equiv  1$

Given two integers $d$ and $e$, If $\exists$ an inverse function $d$ for $e$ then, $ed \equiv 1$ $(mod \phi(n))$ by definition.

$ed = 1 + k\cdot \phi(n)$ for some integer $k$.

If $c \equiv m^e (mod\; n)$ then,
$\large c^d \equiv m^{ed}  \equiv m^{1+k \phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k,
$ since $\large m^{\phi(n)} \equiv 1 (mod \; n)$,

by the Euler-Fermat theorem, as $\large gcd(m, n)=1$

$\large \equiv m (mod\; n)$
Hence $m = c^d\;  mod\; n$ is a unique integer in the range $0 \le m \lt n$.


References


[1] https://people.csail.mit.edu/rivest/Rsapaper.pdf
[2] https://www.amazon.com/Understanding-Cryptography-Textbook-Students-Practitioners/dp/3642446493
[3] https://www.youtube.com/watch?v=fq6SXByItUI




    Comments

    Post a Comment

    Popular posts from this blog

    Introducing Java Reactive Extentions in to a SpringBoot Micro Service

    Image
    Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
    Read more

    Optimal binary search trees

    Image
    Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
    Read more

    Combining the emissions of multiple Observables together using RxJava Zip operator in a Spring Boot Micro service

    Image
    Introduction Well, today we are going to discuss an advanced RxJava operator called Zip. Let’s first take a look at the zip operator at a glance and then move on to a real world example that leverages the capabilities of the operator. In fact, zip is a very powerful and useful operator provided in the RxJava library. Prerequisites : Good knowledge of Java8, Functional Programming, RxJava, Spring Boot, Microservices. User Level : Advanced Since this is an advanced article, I am not going to walk you through the basics of RxJava or Spring Boot microservices. If you need to get some basic understanding of RxJava, I thoroughly recommend you to go through one of my previous blog posts [1] [2] or any other good introductory article about RxJava. If you need to learn more about Spring Boot microservices please go through some of the spring tutorials which are really comprehensive and impressive. RxJava Zip Operator Combines the emissions of multiple Observables together via a speci
    Read more