0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am a programmer not a mathematics student so I do not know a lot about these things, thanks a lot for the reference. $\endgroup$ – Mohamad Sep 12 '15 at 23:48
  • $\begingroup$ Euler's theorem is not enough here, because RSA also works when the message is not coprime to the modulus (because it might be a multiple of one of the secret primes). This is a particular case for square-free moduli, which you can prove using only Fermat's little theorem and the Chinese Remainder Theorem. $\endgroup$ – Henning Makholm Sep 12 '15 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.