#include <stdio.h>

#define mod(a, b) (((a) % (b) + (b)) % (b))

int euclidesFuncaoMDC(int a, int b) {
    if (b == 0) return a;
    return euclidesFuncaoMDC(b, mod(a, b));
}

int inversoModular(int e, int z) {
    for (int d = 1; d < z; d++) {
        if (mod((e * d), z) == 1) {
            return d;
        }
    }
    return -1; // Caso nao exista inverso modular
}

int exponenciacaoModular(int base, int expoente, int modulo) {
    int resultado = 1;
    base %= modulo;
    while (expoente > 0) {
        if (expoente % 2 == 1) resultado = (resultado * base) % modulo;
        base = (base * base) % modulo;
        expoente /= 2;
    }
    return resultado;
}

int main() {
    int p, q, e, tamanhoBloco;

    // Entrada de dados
    printf("Digite os valores de p e q (numeros primos):\n");
    scanf("%d %d", &p, &q);
    printf("Digite o valor de E (chave publica):\n");
    scanf("%d", &e);
    printf("Digite tamanho do bloco:\n");
    scanf("%d", &tamanhoBloco);

    // Cálculo de n e z
    int n = p * q;
    int z = (p-1)*(q-1);

    // Verifica se e e z são coprimos (MDC entre e e z deve ser 1)
    if (euclidesFuncaoMDC(e, z) != 1) {
        printf("Erro: E nao e coprimo com z\n");
        return 1;
    }

    int d = inversoModular(e, z);

    printf("Chave publica (n, e): (%d, %d)\n", n, e);
    printf("Chave privada (n, d): (%d, %d)\n", n, d);

    getchar(); 
    char mensagem[100];
    printf("Insira a mensagem para criptografar:\n");
    fgets(mensagem, sizeof(mensagem), stdin);

    // Pre-codificar a mensagem
    int mensagemPreCodificada[100];
    int tamanhoPreCodificada = 0;
    for (int i = 0; mensagem[i] != '\0'; i++) {
        char c = mensagem[i];
        int valor;

        // Converte letras para números (A=11, B=12, ..., Z=36) e mantém outros caracteres
        if(c == ' ') valor = 0;
        else if ('A' <= c && c <= 'Z') valor = c - 'A' + 11;
        else if ('a' <= c && c <= 'z') valor = c - 'a' + 11;
        else valor = (int)c;  // Mantém outros caracteres como estão

        mensagemPreCodificada[tamanhoPreCodificada++] = valor;
    }

    // Exibe a mensagem pre-codificada
    printf("Mensagem pre-codificada:\n");
    for (int i = 0; i < tamanhoPreCodificada; i++) {
        printf("%d ", mensagemPreCodificada[i]);
    }
    printf("\n");

    // Codificar a mensagem
    int blocosCriptografados[100];
    int tamanhoCriptografados = 0;
    for (int i = 0; i < tamanhoPreCodificada; i += tamanhoBloco) {
        int valorBloco = 0;
        int mult = 1;

        // Combina os valores em blocos de tamanho tamanhoBloco
        for (int j = 0; j < tamanhoBloco && (i + j) < tamanhoPreCodificada; j++) {
            valorBloco += mensagemPreCodificada[i + j] * mult;
            mult *= 100;  // Ajusta o multiplicador para base 100
        }

        // Exponenciação modular para criptografar o bloco
        int blocoCriptografado = exponenciacaoModular(valorBloco, e, n);
        blocosCriptografados[tamanhoCriptografados++] = blocoCriptografado;
    }

    // Exibe a mensagem codificada
    printf("Mensagem codificada:\n");
    for (int i = 0; i < tamanhoCriptografados; i++) {
        printf("%d ", blocosCriptografados[i]);
    }
    printf("\n");

    // Decodificar a mensagem
    int mensagemDecodificada[100];
    int tamanhoDecodificados = 0;
    for (int i = 0; i < tamanhoCriptografados; i++) {
        int blocoDecodificado = exponenciacaoModular(blocosCriptografados[i], d, n);
        
        // Divide o bloco em partes menores
        while (blocoDecodificado > 0) {
            int valor = blocoDecodificado % 100;
            mensagemDecodificada[tamanhoDecodificados++] = valor;
            blocoDecodificado /= 100;
        }
    }

    // Exibe a mensagem pre-codificada decodificada
    printf("Mensagem pre-codificada decodificada:\n");
    for (int i = 0; i < tamanhoDecodificados; i++) {
        printf("%d ", mensagemDecodificada[i]);
    }
    printf("\n");

    // Converte os valores de volta para caracteres e exibe a mensagem final
    printf("Mensagem decodificada:\n");
    for (int i = 0; i < tamanhoDecodificados; i++) {
        int valor = mensagemDecodificada[i];
        if (valor >= 11 && valor <= 36) {
            printf("%c", (char)(valor - 11 + 'A'));  // Converte números para letras
        } else {
            printf("%c", (char)valor);  // Outros caracteres
        }
    }

    printf("\n");
    return 0;
}