3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can use negative d for decryption: $c^{-d} = (c^{-1})^d$, $x$ to minus $d$ is the inverse of $x$ to $d$. Not that anyone would do it that way... $\endgroup$ – K.G. Oct 6 '13 at 20:10
7
$\begingroup$

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;
$\endgroup$
5
$\begingroup$

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..

$\endgroup$

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.