Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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... –  K.G. Oct 6 '13 at 20:10

2 Answers 2

up vote 3 down vote accepted

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;
share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.