Saturday, August 18, 2018

modular arithmetic - cartographic RSA algorithm

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

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...