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.
I think the "magic" you are looking for is
Eulers Theorem
which states that $a^{\phi(n)} \equiv 1 \mod n$ if $\gcd(a,n)=1$.