RSA Decryption in C: Can't get the correct message

Question

Good night, guys. I am struggling for a week with an exercise of programming in C. It was basically:

"Imagine you know my public RSA key which has the modulus n = 16076635963 and the public exponent e = 456233 and you could intercept a message that was encrypted with this key and reads 5395334961. Decipher this message.

P.S.: The message is ASCII encoded."

I made plenty of tries and get these informations:

p: 123341 q: 130343 n: 16076635963 e: 456233 d: 3693459617 Public key (n, e): (16076635963, 456233)

My code is:

#include <stdio.h>

unsigned long long mod_exp(unsigned long long base, unsigned long long exponent, unsigned long long modulus) {
    unsigned long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

void decrypt_message(unsigned long long encrypted_message, unsigned long long private_key, unsigned long long modulus) {
    unsigned long long decrypted_message = mod_exp(encrypted_message, private_key, modulus);

    printf("Decrypted Message: ");
    while (decrypted_message > 0) {
        unsigned char ascii_value = decrypted_message & 0xFF;
        printf("%c", ascii_value);
        decrypted_message >>= 8;
    }
    printf("\n");
}

int main() {
    unsigned long long modulus = 16076635963;
    unsigned long long public_exponent = 456233;
    unsigned long long private_key = 3693459617;
    unsigned long long encrypted_message = 5395334961;

    decrypt_message(encrypted_message, private_key, modulus);

    return 0;
}

But it only returns me: ║≈2♂

Please, help me. I lost 30% of my soul in this exercise and couldn't complete it. I am on Windows 10 Pro and using CodeBlocks 20.03 to compile.

Answer 1

Thank you, guys. 128 bits worked as well!