How does one deal with a negative "d" in RSA?
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 &lt; 0)
    d += phi;