How does one deal with a negative "d" in RSA?

Question

I'm trying to write my own RSA implementation using the textbook approach — which I know is not optimal — of picking primes $p$ and $q$, then computing Euler's totient $phi$, then randomly picking an 'e' which is relatively prime to $phi$, and then computing a $d$ such that ($d*e$) mod $phi$ = 1.

For that last step, I'm using the algorithm provided at http://www.pagedon.com/extended-euclidean-algorithm-in-c/my_programming/

This algorithm often yields a negative $d$, which sure enough does satisfy $d*e$ mod $phi$ = 1. But obviously I can't use a negative $d$ as the exponent during decryption.

Is there some straightforward way I can amend this algorithm, Or is it rather my understanding that needs amending?

Answer 1

In modular arithmetic all of $a + k \cdot m$ with modulus $m$ and integral $k$ are equivalent. You need to solve this equation modulo $\phi$. So $-x$ is equivalent to $-x + k\cdot \phi$ with a sufficiently large $k$ to make it positive.

In code you can use something like:

d = d % phi;
if(d < 0)
    d += phi;

Answer 2

In addition to what CodesInChaos stated (which does apply): the code you linked to does not support integers bigger than the maximum for the C int type, typically $2^{31}-1$. This is not enough in an RSA context, and may cause problems similar to what you have. You can

• switch to a language with built-in support for big integers, like Python, Java..
• use a C or C++ bigint package, like GMP;
• roll your own bigint package.

Also, beware of the code you linked to: it is a bit on the complicated side, and does not detect when there is no modular inverse for the given parameters..