I am a programmer, While I was studying the RSA encryption I found some difficulties with some mathematical matters
RSA algorithm has the following concepts
Modulo, Modular multiplicative inverse, Prime numbers, Totient ϕ
For me I understand all these concepts but to make my question clear let me take an example
The steps to encrypt some text are :
First find two prime numbers
Lets take 5 and 7
Then find the modulus by multiplying these numbers 5*7 = 35
Now find the totient ϕ \implies ϕ(5*7) = (5-1) * (7-1) = 24
Now to fin the public key I have to find a number which has GCD with the totient equals to one which is 11 \implies \gcd(11,24) = 1
The private key is the modular multiplicative inverse of 11, in this case 107 is the multiplicative inverse of 11 because 11*107 \equiv 1 \pmod{24}.
Now we have the public key 11 and the private key is 107.
Lets denote the the public key by e and the private key by d Now If we want to encrypt a message the equation is c \equiv m^e \pmod n
and if we want to decrypt the message the equation is m \equiv c^d \pmod n
Quick test let's decrypt m = 5
5^{11} \bmod 35 = 10 \implies c= 10
10^{107} \bmod 35 = 5 \implies m= 5
this is magic, actually I understand the concepts but I do not understand how is that done, I understand that d is the inverse of e because we got it using the modular multiplicative inverse but I do not understand why the modulus is n and not ϕ I do not understand why the public key must have gcd equals 1 with ϕ not with n, I am confuses and I need your help to explain that to me.
No comments:
Post a Comment