Private key for RSA decryption C++

Question

I've tried to write a function to find the private key for RSA using the Extended Euclidean algorithm, I can't find the error but I really don't want to start again from scratch! For certain values it is correct but for others it isn't and I can't work out why, I really appreciate the help and I'm sorry if this question is too vague (I know that tends to annoy people on here). Can anyone find the error? Thank you very much in advance:

unsigned long long int  modinv(unsigned long long int  u, unsigned long long int  v)
{
    unsigned long long int  inv, u1, u3, v1, v3, t1, t3, q;
    unsigned long long int  iter;

    u1 = 1;
    u3 = u;
    v1 = 0;
    v3 = v;

    iter = 1;

    while (v3 != 0)
    {

        q = u3 / v3;
        t3 = u3 % v3;
        t1 = u1 + q * v1;

        u1 = v1; v1 = t1; u3 = v3; v3 = t3;
        iter = -iter;
    }

    if (u3 != 1)
        return 0;
    if (iter < 0)
        inv = v - u1;
    else
        inv = u1;
    return inv;
}

Answer 1

Do not use unsigned values here because it invalidates the algorithm. So instead of unsigned long long int you could use long long int. Also note that iter = -iter will not work as you intended when using unsigned values because it will underflow. Let's say you have iter = 1 then -iter won't be -1 but instead 18446744073709551615 (=2^64 - 1). The check for iter < 0 will always be false, too.

For any real life applications you will need much larger numbers than you can fit into 64-bit types. There are many ways of doing this but GMP (GNU Multiple Precision lib) has mpz_powm(r, base, exp, mod) that you can use in the decryption phase. More info here.

So basically if you had your cipher text c and your private key defined as n (=p*q) and d then you could decrypt c into plaintext m like this:

#include <gmp.h> // requires GMP lib to be installed.
void rsaDecrypt(const mpz_t c, const mpz_t n, const mpz_t d, mpz_t m) {
  mpz_init(m);
  mpz_powm(m, c, d, n); // m = c^d (mod n)
}