In Section 2 dP and dQ are defined thusly:

      dP             p's CRT exponent, a positive integer such that

                       e * dP == 1 (mod (p-1))

      dQ             q's CRT exponent, a positive integer such that

                       e * dQ == 1 (mod (q-1))

In Appendix A.1.2 we have this:

   o  exponent1 is d mod (p - 1).

   o  exponent2 is d mod (q - 1).

I believe exponent1 = dP and exponent2 = dQ but they're using different formulas. If the formulas are equivalent it is not immediately obvious to me how.

The first formula leads to $ d_p = e^{-1} \mathrm{mod}~(p−1)$ but idk how to get the second formula from that, even when taking the $ e \cdot d \equiv 1 \pmod{\lambda(n)} $ identity into consideration.

Maybe I'm mistaken in my belief that exponent1 = dP and exponent2 = dQ? Maybe the RFC is in error? Maybe the formulas are the equivalentand I'm just not seeing it?


The formulas are equivalent.

From §3.2: $e \cdot d \equiv 1 \pmod{\lambda(n)}$, i.e. $e \cdot d - 1 \equiv 0 \pmod{\lambda(n)}$, i.e. $\lambda(n)$ divides $e \cdot d - 1$.

From §3.1: $\lambda(n) = \mathrm{lcm}(p-1, q-1)$, so $p-1$ divides $\lambda(n)$. Therefore $p-1$ divides $e \cdot d - 1$, i.e. $e \cdot d - 1 \equiv 0 \pmod{p-1}$, i.e. $e \cdot d \equiv 1 \pmod{p-1}$. Thus $d \bmod (p-1)$ is the inverse of $e$ modulo $p-1$.

Conversely, suppose $e \cdot x \equiv 1 \pmod{p-1}$ and $0 \le x \lt p-1$. Then $x$ is the inverse of $e$ in $\mathbb{Z}_{p-1}$, which is unique, so $x \equiv d \pmod{p-1}$. Since I chose $x$ in the range $[0, p-1]$, it is $d \bmod (p-1)$.


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.