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 eZn,
  • Compute the private decryption key as d such that ed=1modϕ(N),
  • Encryption of message m:c=memodN,
  • Decryption of ciphertext c:m=cdmodN.

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

aϕ(n)1(modn)

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


The number of integers in Zm , relatively prime to m is denoted by ϕ(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,
ed1(modϕ(n))

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

m=6, Z6={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 ϕ(6)=2 which is the count of values nZn  such that gcd(m,n)=1


Computing ϕ(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
m=pe11pe22penn,
Where the pi are distinct prime numbers and ei are positive integers, then
ϕ(m)=ni=1(peiipei1i) [3]

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

Writing m by its prime factors yields,
m=24·3·5
=pe11pe22pe33


Applying to the equation, n=3 since only 3 distinct prime factors exists above.
ϕ(240)=(2423)(3130)(5150)=824=64, so you get 64 lines where gcd1

Given two integers d and e, If an inverse function d for e then, ed1 (modϕ(n)) by definition.

ed=1+kϕ(n) for some integer k.

If cme(modn) then,
cdmedm1+kϕ(n)m(mϕ(n))km1k, since mϕ(n)1(modn),

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

m(modn)
Hence m=cdmodn is a unique integer in the range 0m<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

    Popular posts from this blog

    Introducing Java Reactive Extentions in to a SpringBoot Micro Service

    Optimal binary search trees

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