To encrypt a message

$$ P = 53, Q=59, n=PQ=3127, e =3 $$

let message M, for example, $ 89

$$ cipher = 89^{e}mod\quad n. $$ cipher = 1394 this is the encrypted message

$$ \phi=(P-1)(Q-1)=3016 $$

$$ d=\frac{2(\phi(n))+1}{e} = 2011 $$

decrypt $$ 89 = 1394^{2011}mod\quad 3127. $$

This is the original message

But I don't understand the mathematical logic behind this.

  1. I can't understand what logic behind the generation of those successive equations that magically generate the original message

  2. why P Q should be prime number?


When you exponentiate a number $x$ modulo $n$ to the $i$-th power, as you increase $i$, you will eventually reach $x$ again. In your example, $89^{3017} \pmod{3127} = 89$. This "magic exponent" is computed as $\phi(n) + 1 = (p-1)(q-1) + 1$.

This is Euler's Theorem, see the Wikipedia article for a proof.

In RSA, we choose the numbers $e$ and $d$ such that, when multiplied, they are equal to $\phi(n) + 1$, i.e. the "magic exponent" that gets you back to the original number.

Now, you encrypt with $c = m^e \pmod{n}$. This will get you "half way" into the exponentiation, into a seemingly "random" number that has nothing to do with $m$. Then, in order to decrypt, you compute $c^d \pmod{n}$ which will finish the exponentiation and get the result back to $m$. This is because $c^d = (m^e)^d = m^{ed} \pmod{n}$, and $e$ and $d$ were chosen precisely to be equal to $\phi(n)+1$, a.k.a. the "magic exponent".

If $p$ and $q$ weren't prime numbers, then your adversary can compute $p$ and $q$ from $n$ (which is part of public key together with $e$, and as the name says, is public). This is because factoring a number is easier the larger the number of factors it has, and if $p$ and $q$ aren't prime, then they are multiple of two or more prime factors, making $n$ have 4 or more prime factors, instead of just two as intended. If the adversary computes $p$ and $q$, they can compute $d$, which allows they to decrypt any message that was encrypted to you.

I glossed over many fine details and this is not a 100% accurate description of what's going on, but should give you an idea of the process. I'm also obligated to point out that this "raw" RSA is insecure, as it needs proper padding to be safe; not to mention that much larger parameters are needed.


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.