////////////////////////////////////////////////////
// Entrada esperada no formato:
// <p>
// <q>
// <e>
// <blockSize>
// <mensagem>
// Exemplo:
// 101
// 23
// 157
// 3
// Testando
/////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long extendedEuclid(long long a, long long b, long long *x, long long *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    long long x1, y1;
    long long mdc = extendedEuclid(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;
    return mdc;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extendedEuclid(a, m, &x, &y);
    if (g != 1) {
        return -1;
    }
    long long res = (x % m + m) % m;
    return res;
}

long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

int charToCode(char c) {
    if (c >= 'a' && c <= 'z') {
        c = c - 'a' + 'A';
    }
    if (c >= 'A' && c <= 'Z') {
        return (c - 'A') + 11;
    } else {
        return 0;
    }
}

char codeToChar(int code) {
    if (code >= 11 && code <= 36) {
        return (char)((code - 11) + 'A');
    } else {
        return '?';
    }
}

long long maxBlockValue(int blockSize) {
    long long valor = 0;
    for (int i = 0; i < blockSize; i++) {
        valor = valor * 100 + 36;
    }
    return valor;
}

int main() {
    long long p, q, e;
    int blockSize;
    char mensagem[1024];

    printf("=================== RSA =================\n");
    printf("Entre com o valor de p (primo): ");
    scanf("%lld", &p);

    printf("Entre com o valor de q (primo): ");
    scanf("%lld", &q);

    printf("Entre com o valor de e (coprimo de (p-1)*(q-1)): ");
    scanf("%lld", &e);

    printf("Entre com o tamanho do bloco (quantos caracteres por bloco): ");
    scanf("%d", &blockSize);

    long long n = p * q;
    long long phi = (p - 1) * (q - 1);

    if (gcd(e, phi) != 1) {
        printf("ERRO: e = %lld nao eh coprimo de phi(n) = %lld.\n", e, phi);
        printf("Escolha outro valor de e.\n");
        return 1;
    }

    long long d = modInverse(e, phi);
    if (d == -1) {
        printf("ERRO: Nao foi possivel encontrar inverso modular.\n");
        return 1;
    }

    printf("\nChave Publica (e, n)  = (%lld, %lld)\n", e, n);
    printf("Chave Privada (d, n) = (%lld, %lld)\n\n", d, n);

    while (blockSize > 0) {
        long long blocoMax = maxBlockValue(blockSize);
        if (blocoMax < n) {
            break;
        }
        blockSize--;
    }

    if (blockSize <= 0) {
        printf("ERRO: N muito pequeno, nem blockSize=1 cabe!\n");
        return 1;
    }

    printf("BlockSize ajustado para %d (para garantir blocos < n)\n\n", blockSize);

    getchar();

    printf("Digite a mensagem (somente letras A-Z, sem acentos):\n");
    fgets(mensagem, sizeof(mensagem), stdin);

    int len = strlen(mensagem);
    if (len > 0 && mensagem[len - 1] == '\n') {
        mensagem[len - 1] = '\0';
        len--;
    }

    printf("\n--- ENCRIPTACAO ---\n");
    printf("Mensagem original: %s\n", mensagem);

    long long *blocosCriptografados = (long long *)malloc(sizeof(long long) * ((len / blockSize) + 2));
    int blocoIndex = 0;
    int i = 0;

    while (i < len) {
        long long blocoNumero = 0;
        for (int j = 0; j < blockSize; j++) {
            int code = 0;
            if ((i + j) < len) {
                code = charToCode(mensagem[i + j]);
            }
            blocoNumero = blocoNumero * 100 + code;
        }
        long long cript = modExp(blocoNumero, e, n);
        blocosCriptografados[blocoIndex++] = cript;

        i += blockSize;
    }

    printf("\nBlocos criptografados (numeros):\n");
    for (int k = 0; k < blocoIndex; k++) {
        printf("%lld ", blocosCriptografados[k]);
    }
    printf("\n");

    printf("\n--- DESCRIPTACAO ---\n");
    char mensagemDescript[2048];
    int pos = 0;

    for (int k = 0; k < blocoIndex; k++) {
        long long descriptNum = modExp(blocosCriptografados[k], d, n);

        int codes[128];
        for (int z = 0; z < blockSize; z++) {
            codes[z] = descriptNum % 100;
            descriptNum /= 100;
        }
        for (int z = blockSize - 1; z >= 0; z--) {
            char c = codeToChar(codes[z]);
            mensagemDescript[pos++] = c;
        }
    }
    mensagemDescript[pos] = '\0';

    printf("Mensagem descriptografada: %s\n", mensagemDescript);

    free(blocosCriptografados);
    return 0;
}