RSA exponent d is negative

Question

Im trying to encrypt and decrypt various messages with RSA and while it is working flawlessly while d is positive, it obviously breaks when d is negative as d is supposed to be a natural number.

I am using the EXTENDED_EUCLID algorithm to find it and the code is as follows.

void EXTENDED_EUCLID(cpp_int a, cpp_int b, cpp_int&d, cpp_int&x, cpp_int&y) {
     cpp_int n_d = d,
             n_x = x,
             n_y = y;

      if(b == 0) {
          d = a;
          x = 1;
          y = 0;
      } else {      
          cpp_int n_a = a % b;
          if (n_a < 0) n_a += b;
          EXTENDED_EUCLID(b, n_a, n_d, n_x, n_y);
          d = n_d;
          x = n_y;
          y = n_x - a / b * n_y;
      }
}

The 2 lines of code before the recursive call EXTENDED_EUCLID(b, n_a, n_d, n_x, n_y); are from a solution I found on https://crypto.stackexchange.com/questions/10805/how-does-one-deal-with-a-negative-d-in-rsa. Obviously I am doing something wrong here, maybe they need to be positioned somewhere else?

The initial call of the EXTENDED_EUCLID is made with the following parameters EXTENDED_EUCLID(a, n, d, x, y); from a function named MODULAR_LINEAR_EQUATION_SOLVER. a in this case is e(public key if I'm not mistaken) and n or b in this case are φ(n).

Thank you for donating your time to this, hopefully not too silly question.

Answer 1

The solution was to move the 2 lines of code that are above the EXTENDED_EUCLID(b, n_a, n_d, n_x, n_y); recursive call to the function MODULAR_LINEAR_EQUATION_SOLVER, below the initial EXTENDED_EUCLID call. Many thanks to President James K. Polk.