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...