RSA-Implementation isn't decrypting correctly

Question

I like to learn and today I decided to finally implement RSA on my own. Basically from what I can tell my Code should work and it actually does to a certain extent.

However, even though (according to Internet learning sources) the correct keys are calculated and correctly used I get weird outputs. I checked but couldn't find where the problem is, because calculating by hand yields the same results...

So yeah, here's my cryptography.cpp-File:

#include "cryptography.h"

bool prime(const unsigned long long n) {
    //max of sqrt(n)
    unsigned long long m = 0.5 * n;

    for(unsigned int i = 2; i <= m; i++) //check every possible divisor
        if(n % i == 0)  //wheter it goes in to n perfectly
            return false;   //n is not prime if such divisor is found

    //if no divisor found
    return true;
}

bool coprime(unsigned long long p, unsigned long long q) {
    //p >= q
    if(q > p) {
        long long t = p;
        p = q;
        q = t;
    }

    //subtract smaller from bigger, keeping gcd
    while(q != 0) {
        unsigned long long r = p % q;
        p = q;
        q = r;
    }

    //gdc == 1
    return p == 1;
}

/**
 * Finds d for:
 * 1 = (d * e) % m
*/
unsigned long long modularInverse(const unsigned long long e, const unsigned long long m) {
    unsigned long long d = 1;
    while(d * e % m != 1)
        d++;
    return d;
}

unsigned long long pow(const unsigned long long base, const unsigned long long exponent) {
    unsigned long long result = 1;
    for(long long i = 0; i < exponent; i++)
        result *= base;
    return result;
}

bool RSA::generateKeys(const unsigned long long p, const unsigned long long q, unsigned long long& n, unsigned long long& d, unsigned long long& e) {
    //p & q have to be primes
    if(!(prime(p) && prime(q)) || p == q)
        return false;

    //n defined as p * q
    n = p * q;

    unsigned long long m = (p - 1) * (q - 1);

    //find e where e and (p - 1)(q - 1) are coprime
    e = 7;
    while(!coprime(m, e))
        e++;

    //1 = (d * e) % (p - 1)(q - 1)
    d = modularInverse(e, m);

    //everything worked
    return true;
}

unsigned long long RSA::encrypt(const unsigned long long message, const unsigned long long e, const unsigned long long n) {
    return pow(message, e) % n;
}

unsigned long long RSA::decrypt(const unsigned long long encryptedMessage, const unsigned long long d, const unsigned long long n) {
    return pow(encryptedMessage, d) % n;
}

Just to be sure here's how it's used in main.cpp:

#include <iostream>
#include "cryptography.h"

int main(int argc, char const *argv[]) {
    unsigned long long n, d, e;
    if(!RSA::generateKeys(7, 13, n, d, e))
        return -1;
    std::cout << "n: " << n << std::endl;
    std::cout << "d: " << d << std::endl;
    std::cout << "e: " << e << std::endl;
    std::cout << std::endl;
    unsigned long long message;
    std::cin >> message;
    std::cout << "Message: " << message << std::endl;
    unsigned long long encryptedMessage = RSA::encrypt(message, e, n);
    std::cout << "Encrypted Message: " << encryptedMessage << std::endl;
    unsigned long long decryptedMessage = RSA::decrypt(encryptedMessage, d, n);
    std::cout << "Decrypted Message: " << decryptedMessage << std::endl;
}

Answer 1

As @President James K. Polk correctly guessed the Problem was a silent Integer-Overflow. Also to anyone stuck on this: too high encryption-data-integers can cause problems on small primes easily.

I used this to replace pow(a, b) % c in the encrypt & decrypt Method with a call to modularPow(a, b, c):

unsigned long long modularPow(const unsigned long long base, const unsigned long long exponent, const unsigned long long modulus) {
    unsigned long long result = 1;
    for(unsigned long long i = 0; i < exponent; i++) {
        result *= base;
        result %= modulus;
    }
    return result;
}