Skip to main content
added 70 characters in body
Source Link
Daniel S
  • 26.4k
  • 1
  • 29
  • 69

Although RSA keys are usually described as solutions to $de\equiv 1\pmod{\phi(N)}$, there is a more precise equation $de\equiv 1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael functionCarmichael function. Any solution to the usual equation is a solution to the more precise equation.

In your case the Carmichael function is $\mathrm{LCM}(p-1,q-1)=12$. The choice of $e=5$ leads to the solution $d\equiv 5\pmod{12}$ to the precise equation, and $d=29$ is an equivalent decryption exponent.

Generically, this will occur when the choice of $e$ is a square root of one modulo the Carmichael function (in this case $5^2\equiv 1\pmod{12}$, but 1, 7 and 11 are other examples). In general, a number $n$ has $2^{\omega(n)}$ square roots of 1 where $\omega$$\omega(n)$ is the number of distinct prime factors of $n$.

Although RSA keys are usually described as solutions to $de\equiv 1\pmod{\phi(N)}$, there is a more precise equation $de\equiv 1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael function. Any solution to the usual equation is a solution to the more precise equation.

In your case the Carmichael function is $\mathrm{LCM}(p-1,q-1)=12$. The choice of $e=5$ leads to the solution $d\equiv 5\pmod{12}$ to the precise equation, and $d=29$ is an equivalent decryption exponent.

Generically, this will occur when the choice of $e$ is a square root of one modulo the Carmichael function (in this case $5^2\equiv 1\pmod{12}$, but 1, 7 and 11 are other examples). In general, a number $n$ has $2^{\omega(n)}$ square roots of 1 where $\omega$ is the number of distinct prime factors of $n$.

Although RSA keys are usually described as solutions to $de\equiv 1\pmod{\phi(N)}$, there is a more precise equation $de\equiv 1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael function. Any solution to the usual equation is a solution to the more precise equation.

In your case the Carmichael function is $\mathrm{LCM}(p-1,q-1)=12$. The choice of $e=5$ leads to the solution $d\equiv 5\pmod{12}$ to the precise equation, and $d=29$ is an equivalent decryption exponent.

Generically, this will occur when the choice of $e$ is a square root of one modulo the Carmichael function (in this case $5^2\equiv 1\pmod{12}$, but 1, 7 and 11 are other examples). In general, a number $n$ has $2^{\omega(n)}$ square roots of 1 where $\omega(n)$ is the number of distinct prime factors of $n$.

Source Link
Daniel S
  • 26.4k
  • 1
  • 29
  • 69

Although RSA keys are usually described as solutions to $de\equiv 1\pmod{\phi(N)}$, there is a more precise equation $de\equiv 1\pmod{\lambda(N)}$ where $\lambda$ is the Carmichael function. Any solution to the usual equation is a solution to the more precise equation.

In your case the Carmichael function is $\mathrm{LCM}(p-1,q-1)=12$. The choice of $e=5$ leads to the solution $d\equiv 5\pmod{12}$ to the precise equation, and $d=29$ is an equivalent decryption exponent.

Generically, this will occur when the choice of $e$ is a square root of one modulo the Carmichael function (in this case $5^2\equiv 1\pmod{12}$, but 1, 7 and 11 are other examples). In general, a number $n$ has $2^{\omega(n)}$ square roots of 1 where $\omega$ is the number of distinct prime factors of $n$.