3
$\begingroup$

I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm:

RSA Key Generation

Output: public key: $k_{pub} = (n,e)$ and private key: $k_{pr} = (d)$

  1. Choose two large primes $p$ and $q$.
  2. Compute $n$ = $pq$.
  3. Compute $\varphi(n) = (p−1)(q−1)$.
  4. Select the public exponent $e \in \{1,2,\ldots,\varphi(n)−1\}$ such that $\gcd(e,\varphi(n)) = 1.$
  5. Compute the private key $d$ such that $d\cdot e \equiv 1 \bmod \varphi(n)$

Decryption: $x=d_{kpr}(y)\equiv y^{d} \bmod n$

Encryption: $y=e_{kpub}(x)\equiv x^{e} \bmod n$

I don't find intuitive on why we perform encryption and decryption in modulus $n$, but compute the inverse of $e$ in modulus $\varphi(n)$. Any help is appreciated.

$\endgroup$
  • 2
    $\begingroup$ Hint: did you see Euler and Fermat's theorems? $\endgroup$ – kelalaka Sep 29 at 8:28
  • $\begingroup$ I've seen some theorems I did not fully grasp on intuitive level. When they were used to proof that xˆ(de) = x mod n, that was not intuitive as well. $\endgroup$ – sanjihan Sep 29 at 8:33
4
$\begingroup$

What's relevant here is that the Carmichael totient $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the exponent of the multiplicative group of integers modulo $n$, i.e. the smallest positive integer such that $x^{\lambda(n)} \equiv 1 \pmod n$ for all $x$.*

This means that if $ed$ is one more than an integer multiple of $\lambda(n)$, i.e. if $ed \equiv 1 \pmod{\lambda(n)}$ or, equivalently, if $ed = k\lambda(n)+1$ for some integer $k$, then $$x^{ed} = x^{k\lambda(n)+1} = (x^{\lambda(n)})^k x \equiv 1^kx = x \pmod n.$$

(Of course, the Euler totient $\varphi(n) = (p-1)(q-1)$ is itself an integer multiple of $\lambda(n)$, so $ed \equiv 1 \pmod{\varphi(n)}$ implies $ed \equiv 1 \pmod{\lambda(n)}$.)


*) To be precise, $x^{\lambda(n)} \equiv 1 \pmod n$ only holds for $x$ coprime with $n$, since if $x$ shares a prime factor with $n$, it won't be invertible modulo $n$ and no power of it can be congruent to $1$ modulo $n$. That's why the definition of the modular multiplicative group requires the elements to be coprime to the modulus. However, the slightly weaker congruence $x^{\lambda(n)+1} \equiv x \pmod n$ does hold for all $x$ as long as $n$ is squarefree, and that's all we really need for RSA. Not to mention that finding a positive $x < n$ that's not coprime to the modulus $n$ is literally equivalent to factoring $n$.

$\endgroup$
2
$\begingroup$

To get the decrypted value $x^e \pmod n$ of the meesage $x$ you need the Euler's theorem : $$a^{\varphi (n)} \equiv 1 \pmod{n}$$

Replace $a$ with $x$; $$x^{\varphi (n)} \equiv 1 \pmod{n}$$

Now, take any value as the decryption exponent $d'$ to figure out

$$x^{e\cdot d'} \equiv \;? \pmod{n}$$

Now, consider $e\cdot d' \bmod \varphi (n)$ that is equal to $$ e\cdot d' = k \varphi (n) +t.$$

Pun back into the equation.

$$x^{e\cdot d'} \equiv x^{k \varphi (n) +t} \equiv x^{k \varphi (n)} x^t \equiv 1^{k} x^t \equiv x^t \pmod{n} $$

For decryption, you want the $d'$ so that $x^{e\cdot d'} \equiv x \pmod{n}$

For this we need $t=1$ this means that

$$ e\cdot d' \equiv 1 \bmod{\varphi (n)}.$$ i.e. word the inverse.

Note 1: RSA is actually defined with Carmichael lambda $\lambda(n)$ See $\lambda$ versus $\varphi$ in RSA

Note 2: The only cases in which a message $(m,n)\not\equiv 1 $ is when $m$ is $p$ and $q$. RSA works with that, too. One can see this with CRT. See Does RSA work for any message M? for details.

$\endgroup$
  • $\begingroup$ 𝑎 and 𝑛 should be coprime. How can one know that the input to be encrypted x, is also coprime with n? I believe n is a product of 2 primes, so it isn't prime. $\endgroup$ – sanjihan Sep 29 at 9:21
  • $\begingroup$ The only cases are $p$ and $q$ and RSA works with that, too. See Does RSA work for any message M? $\endgroup$ – kelalaka Sep 29 at 9:27

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.