Given e and d as the encryption and decryption component respectively, textbook RSA has the property $ed\equiv 1\pmod {\phi(n)} $. The requirement is that suppose there is another function $\lambda(n)$ such that $$\lambda(n) = {\phi(n)\over gcd (p-1, q-1)}$$ and $$ed\equiv 1\pmod{\lambda(n)}$$I need to prove that e and d still work as encryption and decryption components. I know that $\lambda(n ) = lcm(p-1,q-1)$ but I am totally lost about how this general proof proceeds. PKCS#1 uses this function instead of $\phi(n)$ but I am not able prove that this works.


So this all comes down to showing that $a^{\lambda(n)} \equiv 1 \pmod n$.

So for ease, call $\lambda = \text{lcm}(p-1,q-1) = \text{lcm}(\varphi(p),\varphi(q))$.

Consider $a^\lambda \pmod {pq}$. On the one hand, $\lambda = \varphi(p)m$ for some multiple $m$ of $\varphi(p)$, so that $a^\lambda = a^{\varphi(p)m} \equiv 1^m \equiv 1 \pmod p$. On the other hand, $\lambda \equiv \varphi(q)n$ for some multiple $n$ of $\varphi(q)$, so that $a^\lambda = a^{\varphi(q)n} \equiv 1^n \equiv 1 \pmod q$.

So by the Chinese Remainder Theorem, we must have that $a^{\lambda(pq)} \equiv 1 \pmod{pq}$.

So if you have $ed \equiv 1 \mod {\lambda(pq)}$, then in particular we have some positive coefficient $k$ such that $ed = k\lambda(pq) + 1$. Then $a^{ed} = a^{\lambda(pq)}a \equiv 1 \cdot a \equiv a \mod pq$.

So if you transmit $a^e$, then you can recover $a$ by raising to the $d$, where $d$ is the multiplicative inverse of $e \mod \lambda(pq)$.


Because $\lambda(n) = \mathrm{lcm}(p-1,q-1)$, $ed \equiv 1 \pmod{\lambda(n)}$ implies that $ed\equiv 1 \pmod{p-1}$. Then $$a^{ed} = a^{1+k(p-1)} = a\cdot \left(a^{p-1}\right)^k$$ If $a\equiv 0\pmod p$, then $a^{ed} \equiv 0^{ed} \equiv 0 \pmod p$. Otherwise, $a^{p-1} \equiv 1 \pmod p$ by Fermat's theorem, so in the end we obtain $a^{ed} \equiv a\pmod p$ in all cases. The same reasoning applies modulo $q$, so we obtain $$\left\{\begin{array}{l} a^{ed} \equiv a \pmod p \\ a^{ed} \equiv a \pmod q \end{array}\right., $$ which implies $a^{ed}\equiv a \pmod{pq}$ by the Chinese theorem since $p$ and $q$ are coprime.


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.