/*
Para facilitar o o uso do algoritmo criei uma interface com switch case:
caso tente roda-lo pela propria plataforma, é nescessário colococar o numero da opção que deseja testar e logo abaixo o caso
a ser verificado
"
DIGITE PARA:
1: CPF
2: ISBN
3: CRIPTOGRAFIA RSA
4: TEOREMA CHINES
0: SAIR
"
EXEMPLO:
1
xxxxxxxxx
E o algoritmo irá retornar, no caso, o cpf com os dois digitos verificadores
*/
#include <stdio.h>
#define mod(a, b) (((a) % (b) + (b)) % (b)) // Função para calcular o módulo sempre positivo
// Função para calcular o CPF
void calcula_cpf()
{
int soma = 0;
int soma2 = 0;
char cpf[10];
// Entrada dos primeiros 9 dígitos do CPF
printf("Digite os 9 primeiros digitos do CPF:\n");
scanf("%s", cpf);
// Calcula o primeiro dígito verificador
for (int i = 0; i < 9; i++)
{
int digito = cpf[i] - '0';
soma += ((i + 1) * digito);
}
int D1 = soma % 11;
if (D1 == 10)
D1 = 0;
// Calcula o segundo dígito verificador
for (int i = 0; i < 9; i++)
{
int digito2 = cpf[i] - '0';
soma2 += (i * digito2);
}
soma2 += (D1 * 9);
int D2 = soma2 % 11;
if (D2 == 10)
D2 = 0;
// Exibe o CPF completo
printf("CPF com os digitos verificadores:\n");
printf("%s-%d%d\n", cpf, D1, D2);
}
// Função para calcular o ISBN
void calcula_isbn()
{
int soma = 0;
char isbn[10];
printf("Digite o codigo ISBN:\n");
scanf("%s", isbn);
// Cálculo do somatório
for (int i = 0; i < 9; i++)
{
int digito = isbn[i] - '0';
soma += digito * (10 - i);
}
int resto = soma % 11;
int controle = (11 - resto) % 11;
// Exibe o ISBN completo
if (controle == 10)
{
printf("%sX\n", isbn);
}
else
{
printf("%s%d\n", isbn, controle);
}
}
// Função para calcular o MDC (Máximo Divisor Comum)
int calculaMDC(int x, int y)
{
if (y == 0)
return x;
return calculaMDC(y, mod(x, y));
}
// Função para calcular o inverso modular
int calculaInversoModular(int chave, int totiente)
{
for (int i = 1; i < totiente; i++)
{
if (mod((chave * i), totiente) == 1)
{
return i;
}
}
return -1; // Caso não exista inverso modular
}
// Função para calcular exponenciação modular
int calculaExponenciacaoModular(int valorBase, int exp, int modAtual)
{
int resultadoFinal = 1;
valorBase %= modAtual;
while (exp > 0)
{
if (exp % 2 == 1)
{
resultadoFinal = (resultadoFinal * valorBase) % modAtual;
}
valorBase = (valorBase * valorBase) % modAtual;
exp /= 2;
}
return resultadoFinal;
}
// Função para resolver congruências no formato kx = b (mod n)
int resolveCongruencia(int k, int b, int n, int *x)
{
int d = calculaMDC(k, n);
if (mod(b, d) != 0)
return 0; // Sem solução
int k_inv = calculaInversoModular(k / d, n / d);
if (k_inv == -1)
return 0;
*x = mod((b / d) * k_inv, n / d);
return 1;
}
int main()
{
printf("DIGITE PARA:\n 1: CPF\n 2: ISBN\n 3: CRIPTOGRAFIA RSA\n 4: TEOREMA CHINES\n 0: SAIR\n");
int control;
scanf("%d", &control);
while (control != 0)
{
if (control == 1)
{
calcula_cpf();
}
else if (control == 2)
{
calcula_isbn();
}
if (control == 3)
{
int p, q, e, tamanhoBloco;
// Entrada dos números primos p e q, e da chave pública e
printf("Digite dois números primos (p e q):\n");
scanf("%d %d", &p, &q);
printf("Digite o valor de e (chave pública):\n");
scanf("%d", &e);
printf("Digite o tamanho do bloco:\n");
scanf("%d", &tamanhoBloco);
// Cálculo de n e z
int n = p * q;
int z = (p - 1) * (q - 1);
// Validação se e é coprimo com z
if (calculaMDC(e, z) != 1)
{
printf("Erro: O valor de e não é coprimo com z.\n");
return 1;
}
int d = calculaInversoModular(e, z);
printf("Chave pública (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 a ser criptografada:\n");
fgets(mensagem, sizeof(mensagem), stdin);
// Conversão da mensagem em valores numéricos
int mensagemCodificada[100];
int tamanhoCodificado = 0;
for (int i = 0; mensagem[i] != '\0'; i++)
{
char c = mensagem[i];
int valor;
if (c == ' ')
valor = 0; // Espaços representam 0
else if (c >= 'A' && c <= 'Z')
valor = c - 'A' + 11;
else if (c >= 'a' && c <= 'z')
valor = c - 'a' + 11;
else
valor = (int)c;
mensagemCodificada[tamanhoCodificado++] = valor;
}
// Exibição da mensagem codificada numericamente
printf("Mensagem codificada numericamente:\n");
for (int i = 0; i < tamanhoCodificado; i++)
{
printf("%d ", mensagemCodificada[i]);
}
printf("\n");
// Criptografia em blocos
int blocosCriptografados[100];
int tamanhoCriptografado = 0;
for (int i = 0; i < tamanhoCodificado; i += tamanhoBloco)
{
int bloco = 0;
int multiplicador = 1;
for (int j = 0; j < tamanhoBloco && (i + j) < tamanhoCodificado; j++)
{
bloco += mensagemCodificada[i + j] * multiplicador;
multiplicador *= 100;
}
blocosCriptografados[tamanhoCriptografado++] = calculaExponenciacaoModular(bloco, e, n);
}
// Exibição dos blocos criptografados
printf("Mensagem criptografada:\n");
for (int i = 0; i < tamanhoCriptografado; i++)
{
printf("%d ", blocosCriptografados[i]);
}
printf("\n");
// Decodificação da mensagem
int mensagemDecodificada[100];
int tamanhoDecodificado = 0;
for (int i = 0; i < tamanhoCriptografado; i++)
{
int bloco = calculaExponenciacaoModular(blocosCriptografados[i], d, n);
while (bloco > 0)
{
mensagemDecodificada[tamanhoDecodificado++] = bloco % 100;
bloco /= 100;
}
}
// Exibição da mensagem decodificada numericamente
printf("Mensagem decodificada numericamente:\n");
for (int i = 0; i < tamanhoDecodificado; i++)
{
printf("%d ", mensagemDecodificada[i]);
}
printf("\n");
// Conversão da mensagem de volta para texto
printf("Mensagem decodificada:\n");
for (int i = 0; i < tamanhoDecodificado; i++)
{
int valor = mensagemDecodificada[i];
if (valor >= 11 && valor <= 36)
{
printf("%c", (char)(valor - 11 + 'A'));
}
else
{
printf("%c", (char)valor);
}
}
printf("\n");
}
if (control == 4)
{
int a[4], n[4], totalEquacoes = 0, continuar = 1;
printf("Insira as equações no formato 'kx = b (mod n)'. Digite '0 0 0' para encerrar.\n");
for (int i = 0; i < 4 && continuar; i++)
{
int k, b, ni;
printf("Digite os valores de 'k', 'b' e 'n' para a equação %d:\n", totalEquacoes + 1);
scanf("%d %d %d", &k, &b, &ni);
if (k == 0 && b == 0 && ni == 0)
{
continuar = 0;
}
else if (ni <= 0)
{
printf("O valor de 'n' deve ser positivo. Tente novamente.\n");
i--;
}
else
{
int x;
if (!resolveCongruencia(k, b, ni, &x))
{
printf("Sem solução para a equação %dx = %d (mod %d). Tente novamente.\n", k, b, ni);
i--;
}
else
{
a[totalEquacoes] = x;
n[totalEquacoes] = ni;
totalEquacoes++;
}
}
}
if (totalEquacoes == 0)
{
printf("Nenhuma equação foi inserida.\n");
return 0;
}
int N = 1;
for (int i = 0; i < totalEquacoes; i++)
N *= n[i];
int resultado = 0;
for (int i = 0; i < totalEquacoes; i++)
{
int Ni = N / n[i];
int xi = calculaInversoModular(Ni, n[i]);
resultado += a[i] * xi * Ni;
}
resultado = mod(resultado, N);
printf("A solução para o sistema de congruências é: x = %dt + %d\n", N, resultado);
}
return 0;
}
}
