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

bool eh_primo(int num) {
    if (num <= 1) return false;
    if (num == 2 || num == 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

int mdc(int x, int y) {
    while (x != 0) {
        int temp = x;
        x = y % x;
        y = temp;
    }
    return y;
}

int mdc_extendido(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int mdc = mdc_extendido(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return mdc;
}

int inverso_modular(int a, int m) {
    int x, y;
    int mdc = mdc_extendido(a, m, &x, &y);
    if (mdc != 1) {
        return -1; 
    }
    return (x % m + m) % m; 
}

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

void mensagem_para_numeros(char *mensagem, int *numeros, int tamanho, int bloco) {
    int indice = 0;
    for (int i = 0; i < tamanho; i += bloco) {
        long long bloco_num = 0;
        for (int j = 0; j < bloco; j++) {
            if (i + j < tamanho) {
                char c = mensagem[i + j];
                if (c >= 'A' && c <= 'Z') {
                    bloco_num = bloco_num * 100 + (c - 'A' + 11); // A = 11, ..., Z = 36
                } else if (c == ' ') {
                    bloco_num = bloco_num * 100 + 37; // Espaço = 37
                } else {
                    printf("Erro: A mensagem contém caracteres inválidos. Use apenas letras maiúsculas e espaços.\n");
                    exit(1);
                }
            }
        }
        numeros[indice++] = bloco_num;
    }
}

void numeros_para_mensagem(int *numeros, int tamanho, char *mensagem, int bloco, int total_blocos) {
    int indice_mensagem = 0;
    for (int i = 0; i < total_blocos; i++) {
        long long num = numeros[i];
        for (int j = bloco - 1; j >= 0; j--) {
            if (num > 0 && indice_mensagem + j < tamanho) {
                int letra = num % 100;
                if (letra >= 11 && letra <= 36) {
                    mensagem[indice_mensagem + j] = (char)(letra - 11 + 'A');
                } else if (letra == 37) {
                    mensagem[indice_mensagem + j] = ' ';
                } else {
                    mensagem[indice_mensagem + j] = '?';
                }
                num /= 100;
            }
        }
        indice_mensagem += bloco;
    }
    mensagem[tamanho] = '\0';
}

int main() {
    int p, q, e, bloco;
    long long n, phi, d;

    printf("Digite o valor do primo p: \n");
    scanf("%d", &p);
    if (!eh_primo(p)) {
        printf("Erro: p deve ser um número primo.\n");
        return 1;
    }

    printf("Digite o valor do primo q:\n ");
    scanf("%d", &q);
    if (!eh_primo(q)) {
        printf("Erro: q deve ser um número primo.\n");
        return 1;
    }

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

    if (n <= 37) {
        printf("O valor de n deve ser maior que 37 para evitar colisões. Escolha outros valores para p e q.\n");
        return 1;
    }

    printf("Digite o valor de E (co-primo com phi(n)): \n");
    scanf("%d", &e);

    if (mdc(e, phi) != 1) {
        printf("E não é coprimo com phi(n). Escolha outro valor.\n");
        return 1;
    }

    d = inverso_modular(e, phi);
    if (d == -1) {
        printf("Não foi possível calcular o inverso modular.\n");
        return 1;
    }

    printf("Chave pública: (n = %lld, e = %d)\n", n, e);
    printf("Chave privada: (n = %lld, d = %lld)\n", n, d);

    printf("Digite o tamanho do bloco: ");
    scanf("%d", &bloco);

    char mensagem[256];
    printf("Digite a mensagem para criptografar (apenas letras maiúsculas e espaços): ");
    getchar(); 
    fgets(mensagem, 256, stdin);

    mensagem[strcspn(mensagem, "\n")] = '\0'; 

    int tamanho = strlen(mensagem);
    if (bloco <= 0 || bloco > tamanho) {
        printf("Erro: O tamanho do bloco deve ser maior que 0 e menor ou igual ao tamanho da mensagem.\n");
        return 1;
    }

    int total_blocos = (tamanho + bloco - 1) / bloco; 
    int numeros[total_blocos];
    mensagem_para_numeros(mensagem, numeros, tamanho, bloco);

    for (int i = 0; i < total_blocos; i++) {
        if (numeros[i] >= n) {
            printf("Erro: O bloco %d (%d) excede o valor de n (%lld). Ajuste p, q ou o tamanho do bloco.\n", i, numeros[i], n);
            return 1;
        }
    }

    printf("Mensagem criptografada: ");
    for (int i = 0; i < total_blocos; i++) {
        long long criptografado = potencia_modular(numeros[i], e, n);
        printf("%lld ", criptografado);
        numeros[i] = criptografado; 
    }
    printf("\n");

    printf("Mensagem descriptografada: ");
    for (int i = 0; i < total_blocos; i++) {
        long long descriptografado = potencia_modular(numeros[i], d, n);
        numeros[i] = (int)descriptografado;
    }

    char mensagem_decifrada[256];
    numeros_para_mensagem(numeros, tamanho, mensagem_decifrada, bloco, total_blocos);
    printf("%s\n", mensagem_decifrada);

    return 0;
}