# Problem with RSA encryption

Recently I was looking at the RSA encryption scheme and decided to do some examples but this seemingly simple one is bugging me a lot.

I chose $p=13$, $q=17$. Let $e=131$, be the encryption key. So, $\phi=(p-1)(q-1)=12 \times 16 = 192$

I need to compute $d$, the decryption key. So I used extended Euclid's algorithm to solve the equation $de-k\phi=1$. (Since $d$ needs to obey the condition $de \equiv 1 \pmod \phi$.)

As a result I got this strange looking solution $-85 \times 131 + 58 \times 192 = 1$. That is, it says, $-de+k\phi=1$ (to me it looks strange because it says $d$ is negative and I haven't worked with negative values of encryption or decryption keys before. If $d$ can be negative, as it seems to be in this case, how do I compute $M^d$, for example if I want to compute the digital signature of the message $M$?. Moreover, the value of $d$ that I obtained ($-85$), doesn't seem to obey the condition $de\equiv 1 \pmod \phi$. You plug in the values for $d$,$~e$ and $\phi$, and you get a different result. I am totally lost and I don't understand what's going on here. Please correct me if my understanding is wrong and point me in the right direction.

If I assume $d=85$ and compute the signature for say, $M=87$, it results in some value, which when verified with $e=131$, doesn't give $85$. I appreciate any help. Thanks.

-
$d$ is only defined up to congruence mod $\phi$. So $d=-85=192-85=107$. – Chris Eagle Oct 24 '11 at 9:57
I plugged in $d,e$ and $\phi$ and I didn't get a different result. But $-85=107\mod 192$ so that's the $d$ you should be using. – anon Oct 24 '11 at 9:59

Once you know $$-85\times 131+58\times 192 = 1$$ you can add $192\times 131-131\times 192$ from the left-hand side to get $$(192-85)\times 131+(58-131)\times 192=1$$ So your sought inverse modulo $192$ is $192-85=107$.