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.
Best Answer
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$.