Whats wrong with my RSA implementation

Question

I wrote a small implementation of RSA encryption but it doesn't give the correct result ,sometimes the decryption gives 0 when using other values for p & q (primes). What could be wrong here ?

    #include <stdio.h>
 #define uint unsigned long long
uint modpow(uint base,uint exp,uint modulus)
{
  base %= modulus;
  unsigned long long result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }

  return result;
}
uint modinv(uint a,uint p) {
    uint ex = p-2, result = 1;
    while (ex > 0) {
        if (ex % 2 == 1) {
            result = (result*a) % p;
        }
        a = (a*a) % p;
        ex /= 2;
    }
    return result;
}

int main()
{
    uint p = 4294967291;
    uint q = 1073741789;
    uint e = 3;
    uint m = p*q;
    uint phi = (p -1)*(q -1);
    uint d = modinv(e,phi);
    uint c = 0x41424344;
    uint en = modpow(c,e,m);
    printf("Encrypting: %llX\nEncrypted: %llX\nDecrypted: %llX",c,en,modpow(en,d,m));
}

Answer 1

One problem is that unsigned long long is probably only 64 bits, and the intermediates result*base and base*base can easily overflow 64 bits in your modpow function. You need an __int128 intermediate type here (if your compiler supports it).

Another problem is that RSA only works for plaintext/cipphertext values that map to integers that are NOT mulitples of p or q. If you choose a plaintext that is a multiple of p or q, the decryption will fail. This is not a problem with realistic (large) moduli, as the likelyhood of hitting a multiple of p or q randomly is astronomically small (its roughly the same as the chance of guessing the private key given only the public key).

The first problem is probably what is causing you grief.