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∈Zn,
- 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,
ed≡1(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 n∈Zn 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=pe11⋅pe22⋅…⋅penn,
Where the pi are distinct prime numbers and ei are positive integers, then
ϕ(m)=n∏i=1(peii−pei−1i) [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
=pe11⋅pe22⋅pe33
Applying to the equation, n=3 since only 3 distinct prime factors exists above.
ϕ(240)=(24−23)⋅(31−30)⋅(51−50)=8⋅2⋅4=64, so you get 64 lines where gcd≡1
Given two integers d and e, If ∃ an inverse function d for e then, ed≡1 (modϕ(n)) by definition.
ed=1+k⋅ϕ(n) for some integer k.
If c≡me(modn) then,
cd≡med≡m1+kϕ(n)≡m⋅(mϕ(n))k≡m⋅1k, 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 0≤m<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