Gustavo Abrantes de Souza
212008160
Questão 09 - Teorema Chinês
#include <stdio.h>
// Função para calcular o inverso modular de a mod m
int inversoModular(int a, int m) {
a = a % m;
for (int x = 1; x < m; x++) {
if ((a * x) % m == 1)
return x;
}
return -1; // Se não existir inverso
}
// Função para resolver o sistema de congruências usando o Teorema Chinês do Resto
int teoremaChines(int n[], int a[], int k, int *N) {
*N = 1; // Produto de todos os n_i -> N = n1.n2.n3
for (int i = 0; i < k; i++) {
*N *= n[i];
}
int X = 0;
for (int i = 0; i < k; i++) {
int Ni = *N / n[i]; // Calculo dos N1, N2, N3, na qual é dado por -> N/n_i
int Xi = inversoModular(Ni, n[i]); // Inverso de Ni módulo n_i, na qual é dado por Ni.Xi ≡ 1 (mod ni)
if (Xi == -1) {
printf("Erro: Nao existe inverso modular para %d modulo %d\n", Ni, n[i]);
return -1;
}
// Calculo do X -> X ≡ (a1.X1.N1 + a2.X2.N2 + a3.X3.N3) mod N
X += a[i] * Ni * Xi;
}
return X % (*N);
}
int main() {
int n[4], a[4];
int k, N;
// Leitura do número de equações (máximo 4)
printf("Digite o numero de equacoes (ate 4): ");
scanf("%d", &k);
if (k > 4) {
printf("Numero maximo de equacoes e 4.\n");
return 1;
}
// Leitura dos módulos (n_i) e dos restos (a_i), seguindo o formato
// X ≡ a1 (mod n1)
// X ≡ a2 (mod n2)
// X ≡ a3 (mod n3)
for (int i = 0; i < k; i++) {
printf("Digite n[%d] (modulo da equacao %d): ", i + 1, i + 1);
scanf("%d", &n[i]);
printf("Digite a[%d] (resto da equacao %d): ", i + 1, i + 1);
scanf("%d", &a[i]);
}
// Chamando a função para calcular o resultado
int result = teoremaChines(n, a, k, &N);
if (result != -1) {
printf("A solucao do sistema de congruencias e X = %d (mod %d)\n", result, N);
}
return 0;
}
Questão 10 - Criptografia RSA
#include <stdio.h>
#include <string.h>
#include <math.h>
// Função para calcular o MDC (Máximo Divisor Comum)
int mdc(int a, int b) {
if (b == 0)
return a;
return mdc(b, a % b);
}
// Função para calcular a função phi ou totient de Euler
int phi(int p, int q) {
return (p - 1) * (q - 1);
}
// Função para calcular o inverso modular de e (Achar o d):
// -> e.d ≡ 1 mod phi(n)
int inversoModular(int a, int m) {
a = a % m;
for (int x = 1; x < m; x++) {
if ((a * x) % m == 1)
return x;
}
return -1; // Se não existir inverso
}
// Função para fazer o calculo da congruência com expoente, como em:
// m^e mod n
// c^d mod n
int exponenciacaoModular(int base, int exp, int m) {
int resulto = 1;
base = base % m; // definindo resto da div da base por n
while (exp > 0) { // enquanto e (para o caso de encryptRSA) ou d (para o caso de decryptRSA) > 0
if (exp % 2 == 1)
resulto = (resulto * base) % m;
exp = exp >> 1;
base = (base * base) % m;
}
return resulto;
}
// Função para criptografar a mensagem
void criptografandoRSA(char *message, int e, int n) {
printf("\n__ __ __ __ __ __ __ __ __ __ __\n");
printf("\nMensagem criptografada: ");
for (size_t i = 0; i < strlen(message); i++) {
int codigo = message[i] - 'A' + 11; // Convertendo o caractere para código (A=11, B=12, etc...)
int encrypted = exponenciacaoModular(codigo, e, n);
printf("%d ", encrypted);
}
printf("\n");
printf("__ __ __ __ __ __ __ __ __ __ __\n\n");
}
// Função para descriptografar a mensagem
void descriptografandoRSA(int *encrypted, int length, int d, int n) {
printf("\n__-__-__-__-__-__-__-__-__-__-__\n");
printf("\nMensagem decifrada: ");
for (int i = 0; i < length; i++) {
int decrypted = exponenciacaoModular(encrypted[i], d, n);
printf("%c", (decrypted - 11) + 'A'); // Convertendo o cod de volta para caractere
}
printf("\n");
printf("__-__-__-__-__-__-__-__-__-__-__\n");
}
int main() {
int p, q, e, n, d, totiente;
printf("Digite os primos p e q:\n");
scanf("%d %d", &p, &q);
n = p * q; // calculo do n
totiente = phi(p, q); // calculo do phi
printf("--------------------\n");
printf("Valor de n: %d\n", n);
printf("Valor de phi(%d): %d\n", n, totiente);
printf("--------------------\n");
// Entrada de "e"
printf("Digite o valor de 'e' (1 < e < %d, coprimo com %d): ", totiente, totiente);
scanf("%d", &e);
if (mdc(e, phi(p,q)) != 1) { // verificando se os numeros "e" e "phi" são coprimos
printf("Erro: %d nao e coprimo com %d.\n", e,totiente);
return 1;
}
// Calculando d (inverso modular de e mod phi)
d = inversoModular(e, totiente);
if (d == -1) {
printf("Erro: Nao foi possivel calcular o inverso modular.\n");
return 1;
}
printf("Valor de d: %d\n", d);
// Entrada da mensagem
char message[100];
printf("Digite a mensagem a ser criptografada (LETRAS MAIUSCULAS TEACHER): ");
scanf("%s", message);
// Criptografando a mensagem
criptografandoRSA(message, e, n);
// Exemplo de mensagem criptografada (entrada para descriptografia)
int menssagemCriptografada[100], numLetras;
printf("\nDigite o numero de letras criptografadas: "); // ex: se for AMOR a mensagem -> 4 letras
scanf("%d", &numLetras);
// Exemplo de entrada para ajudar professora -> 13 16 29 16
printf("Digite o respectivo numero das letras criptografadas (COM ESPACO ENTRE UMA E OUTRA, ASSIM COMO FOI APRESENTADO ACIMA EM 'MENSAGEM CRIPTOGRAFADA'): ");
for (int i = 0; i < numLetras; i++) {
scanf("%d", &menssagemCriptografada[i]);
}
// Descriptografando a mensagem
descriptografandoRSA(menssagemCriptografada, numLetras, d, n);
return 0;
}
Questão 11 - Validador de CPF e ISBN usando congruência
#include <stdio.h>
#include <string.h>
// Função para calcular os dígitos verificadores do CPF
void calcularCPF(char cpf[]) {
int soma = 0, peso = 10, i;
// Calculando o primeiro dígito verificador
for (i = 0; i < 9; i++) {
soma += (cpf[i] - '0') * peso;
peso--;
}
int digito1 = (soma * 10) % 11;
if (digito1 == 10) digito1 = 0;
// Calculando o segundo dígito verificador
soma = 0;
peso = 11;
for (i = 0; i < 9; i++) {
soma += (cpf[i] - '0') * peso;
peso--;
}
soma += digito1 * 2;
int digito2 = (soma * 10) % 11;
if (digito2 == 10) digito2 = 0;
// Dígitos verificadores calculados
printf("-----------------------------------------------\n");
printf("Primeiro digito verificador calculado: %d\n", digito1);
printf("Segundo digito verificador calculado: %d\n", digito2);
printf("-----------------------------------------------\n");
// Comparando com os dígitos fornecidos
if (digito1 == (cpf[9] - '0') && digito2 == (cpf[10] - '0')) {
printf("CPF valido!\n");
} else {
printf("CPF invalido!\n");
}
}
// Função para calcular a validade do ISBN-10
void calcularISBN(char isbn[]) {
int soma = 0;
// Calculando a soma ponderada
for (int i = 0; i < 9; i++) {
soma += (isbn[i] - '0') * (i + 1);
}
int checksum = soma % 11;
// Exibindo o dígito verificador calculado
printf("Digito verificador calculado: ");
if (checksum == 10) {
printf("X\n");
} else {
printf("%d\n", checksum);
}
// Verificando validade
char ultimo = isbn[9];
if (ultimo == 'X') {
if (checksum == 10) {
printf("ISBN valido!\n");
} else {
printf("ISBN invalido!\n");
}
} else {
if (checksum == (ultimo - '0')) {
printf("ISBN valido!\n");
} else {
printf("ISBN invalido!\n");
}
}
}
int main() {
char cpf[12], isbn[11];
// Entrada do CPF
printf("Digite o CPF (apenas numeros, 11 digitos): ");
scanf("%s", cpf);
if (strlen(cpf) != 11) {
printf("Erro: CPF deve ter 11 digitos.\n");
return 1;
}
calcularCPF(cpf);
// Entrada do ISBN
printf("\nDigite o ISBN-10 (apenas numeros, 10 digitos): ");
scanf("%s", isbn);
if (strlen(isbn) != 10) {
printf("Erro: ISBN-10 deve ter 10 digitos.\n");
return 1;
}
calcularISBN(isbn);
return 0;
}
