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

// Função para calcular o MDC usando o Algoritmo de Euclides
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Função para calcular o inverso modular
int modInverse(int a, int m) {
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1) {
            return x;
        }
    }
    return -1; // Inverso modular não existe
}

// Função para exponenciação modular
long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;

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

    return result;
}

// Pré-codificação da mensagem
void preEncode(char *message, char *encodedMessage) {
    int index = 0;

    for (int i = 0; message[i] != '\0'; i++) {
        if (message[i] >= 'A' && message[i] <= 'Z') { // Letras maiúsculas
            sprintf(&encodedMessage[index], "%02d", message[i] - 'A' + 11);
            index += 2;
        } else if (message[i] >= 'a' && message[i] <= 'z') { // Letras minúsculas
            sprintf(&encodedMessage[index], "%02d", message[i] - 'a' + 11);
            index += 2;
        } else if (message[i] == ' ') { // Espaço
            sprintf(&encodedMessage[index], "99");
            index += 2;
        }
    }
    encodedMessage[index] = '\0';
}

// Dividir mensagem codificada em blocos com base no número de algarismos
void splitBlocks(char *encodedMessage, char blocks[][20], int blockSize, int *numBlocks) {
    int len = strlen(encodedMessage);
    *numBlocks = 0;

    for (int i = 0; i < len; i += blockSize) {
        strncpy(blocks[*numBlocks], &encodedMessage[i], blockSize);
        blocks[*numBlocks][blockSize] = '\0';
        (*numBlocks)++;
    }
}

// Decodificar mensagem descriptografada
void decodeMessage(char *decodedMessage, char *finalMessage) {
    int index = 0;

    for (int i = 0; decodedMessage[i] != '\0'; i += 2) {
        char numStr[3];
        strncpy(numStr, &decodedMessage[i], 2);
        numStr[2] = '\0';

        int num = atoi(numStr);
        if (num >= 11 && num <= 36)
            finalMessage[index++] = 'A' + num - 11;
        else if (num == 99)
            finalMessage[index++] = ' ';
    }
    
    finalMessage[index] = '\0';
}

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

    // Entrada dos números primos e do expoente público
    printf("Digite os números primos p e q: \n");
    scanf("%lld %lld", &p, &q);

    printf("Digite o número público e: \n");
    scanf("%lld", &e);

    // Cálculo de n e φ(n)
    long long n = p * q;
    long long phi_n = (p - 1) * (q - 1);

    // Verificar se e é coprimo com φ(n)
    if (gcd(e, phi_n) != 1) {
        printf("e não é coprimo com φ(n). Escolha outro valor.\n");
        return -1;
    }

    // Calcular d
    long long d = modInverse(e, phi_n);

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

	// Entrada da mensagem e tamanho do bloco
	char message[256];
	printf("Digite a mensagem: \n");
	scanf(" %[^\n]", message);

	int blockSize;
	printf("Digite o tamanho do bloco em número de: \n");
	scanf("%d", &blockSize);

	// Pré-codificar mensagem
	char encodedMessage[512];
	preEncode(message, encodedMessage);

	// Dividir em blocos
	char blocks[100][20];
	int numBlocks;
	splitBlocks(encodedMessage, blocks, blockSize, &numBlocks);

	// Criptografar os blocos
	long long encryptedBlocks[100];
	for (int i = 0; i < numBlocks; i++) {
		encryptedBlocks[i] = modExp(atoll(blocks[i]), e, n);
	}

	printf("Blocos criptografados:\n");
	for (int i = 0; i < numBlocks; i++) {
		printf("%lld ", encryptedBlocks[i]);
	}
	printf("\n");

	// Descriptografar os blocos
	char decryptedMessage[512] = "";
	for (int i = 0; i < numBlocks; i++) {
		char decryptedBlock[20];
		sprintf(decryptedBlock, "%lld", modExp(encryptedBlocks[i], d, n));
        
		while ((int)strlen(decryptedBlock) < blockSize) {
			char temp[20];
			sprintf(temp, "0%s", decryptedBlock);
			strcpy(decryptedBlock, temp);
		}
        
		strcat(decryptedMessage, decryptedBlock);
	}

	// Decodificar mensagem final
	char finalMessage[256];
	decodeMessage(decryptedMessage, finalMessage);

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

	return 0;
}