2
$\begingroup$

I am only taking baby steps in RSA.

If $p=11$, $q=7$ and $e=3$,

$$\phi(n) = 10*6 = 60$$

Then:

$$d = (2 (\phi(n)) + 1 ) / 3 = 121/3$$

Should $d$ be kept as a non-integer or is such a $d$ invalid?

$\endgroup$
4
  • 3
    $\begingroup$ $d$ must be an integer. In this case you have to calculate what is called the "modular multiplicative inverse" of $3\bmod 60$. AND you need to ensure that $\gcd(e,\phi(n))=1$ $\endgroup$
    – SEJPM
    Nov 29 '15 at 15:41
  • 1
    $\begingroup$ For such small numbers, you can choose $d$ by testing $k=1,2,3\dots$ until finding $k$ such that $e$ divides $k\cdot\varphi(N)+1$; then taking your $d$ as $(k\cdot\varphi(N)+1)/e$. That construction insures that $e\cdot d-1$ is a multiple of $\varphi(N)$, otherwise said $e\cdot d\equiv1\pmod{\varphi(N)}$, which is sufficient for $d$ to be a valid private exponent. That method to find $d$ will be inefficient for realistic $\varphi(N)$, and sometime will not work within a reasonable time. $\;$ Caution: your parameters $p=11$, $q=7$ and $e=3$ can not work, because $\gcd(e,q-1)\ne1$. $\endgroup$
    – fgrieu
    Nov 29 '15 at 16:25
  • $\begingroup$ Thanks all. I get it now. Quick question: is it possible to have more than one value of k that is valid? $\endgroup$
    – Old Geezer
    Nov 29 '15 at 17:17
  • $\begingroup$ @Old Geezer: yes, there can be several possible $k$, if you don't require that $d<\varphi(N)$ (something that is mathematically not a requirement, but customary). On second though, as long as $e$ is small, finding $k$ by enumeration will allways work, since one $k\le e$ will be suitable (when $e$ is valid w.r.t. $p$ and $q$). $\endgroup$
    – fgrieu
    Nov 29 '15 at 20:23
1
$\begingroup$

$d$ must indeed be an integer.

To calculate $d$ you need to calculate $d=e^{-1}\bmod{\phi(n)}$ which is called the modular multiplicative inverse of $e\bmod{\phi(n)}$. For $d$ be computable you need to ensure that $$\gcd(e,\phi(n))=\gcd(e,(p-1)(q-1))=1$$

holds, which isn't the case with your sample parameters as $\gcd(3,60)=3\neq1$.

As fgrieu pointed out in the comments you can find the private exponent by finding the smallest $k$ for which $(k\cdot\phi(n)+1)/e$ is an integer. The run-time of this approach likely will grow linearly with the size of the $e$ value which is in the order of $2^{16}$ usually.

Of course $k$ isn't unique unless you take the smallest possible $k$, meaning there will be other (larger) values of $k$ yielding a valid decryption exponent.

$\endgroup$
5
  • $\begingroup$ Thanks. I used en.wikipedia.org/wiki/Extended_Euclidean_algorithm to get x and y for given values of $\varphi$ and $e$. How do I derive the $k$ from these? $\endgroup$
    – Old Geezer
    Nov 29 '15 at 19:47
  • $\begingroup$ @OldGeezer $k$ is completely uninteresting for RSA. Either $x$ or $y$ (=$x$) will be the interesting $e^{-1}$ value which you can check by computing $(e^{-1}*e)/\phi(n)$ and checking if the result is an integer. $\endgroup$
    – SEJPM
    Nov 29 '15 at 19:55
  • $\begingroup$ It turns out that the approach of finding $k$ by trial an error works including for realistic parameters: $k$ is never above $e$, which is typically small. Thus the cost grows no faster than $\mathcal O(e\cdot\log(N))$. $\endgroup$
    – fgrieu
    Nov 29 '15 at 20:26
  • $\begingroup$ My math is insufficient to understand modular multiplicative inverse. From my reading thus far, I thought I can get a valid $d$ by trying $k$ from 1 until I achieve an integral $(k\cdot\varphi(N)+1)/e$. I did that, for small values of $p$ and $q$ (7&11, 11&13, 11&17, 19&17, 53&59, etc) and taking the first valid $k$, I was able to encrypt and decrypt short messages. But when I apply this to a bigger $p$ and $q$ pair, it did not work. Are there any other conditions for $k$ that a layman like me can understand? $\endgroup$
    – Old Geezer
    Nov 30 '15 at 8:45
  • $\begingroup$ @OldGeezer, this approach should always work. It may be the case that the pairs you picked didn't fulfill the GCD requirement or (more likely?) you couldn't distinguish between an integral result and a floating point result due to internal rounding. $\endgroup$
    – SEJPM
    Nov 30 '15 at 13:56

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.