Atividade 2
Guia de Uso
Este programa implementa três funcionalidades principais:
- Resolução de sistemas de congruências utilizando o Teorema do Resto Chinês.
- Criptografia RSA para codificação e decodificação de mensagens baseadas em caracteres alfabéticos.
- Validação de CPF e ISBN.
Link dos códigos separados
- https://onecompiler.com/cpp/436nm2pyz
- https://onecompiler.com/cpp/436nmr48b
- https://onecompiler.com/cpp/436nmzv3n
Como Executar o Programa
O programa exibe um menu para o usuário escolher uma das funcionalidades. Basta compilar e rodar o código em um ambiente C++ compatível.
g++ programa.cpp -o programa
./programa
O menu aparecerá com as opções:
Escolha a funcionalidade:
1 - Resolver sistema de congruência (Teorema do Resto Chinês)
2 - Realizar criptografia RSA
3 - Validar CPF e ISBN
0 - Sair
Escolha:
O usuário deve inserir um número correspondente à opção desejada.
1️⃣ Resolver Sistema de Congruências (Teorema do Resto Chinês)
Este modo permite resolver um sistema de congruências do tipo:
ax ≡ b (mod m)
Exemplo de Entrada:
1
Número de equações (até 4): 3
Equação 1 no formato ax ≡ b (mod m)
Coeficiente 'a': 1
Resto 'b': 2
Módulo 'm': 5
Equação 2 no formato ax ≡ b (mod m)
Coeficiente 'a': 2
Resto 'b': 1
Módulo 'm': 7
Equação 3 no formato ax ≡ b (mod m)
Coeficiente 'a': 3
Resto 'b': 4
Módulo 'm': 11
Saída Esperada:
Solução: x = 74
2️⃣ Realizar Criptografia RSA
Este modo permite criptografar e descriptografar mensagens utilizando RSA.
Exemplo de Entrada:
2
Digite dois números primos (p e q): 17 23
Digite o expoente de criptografia (e): 7
Digite uma mensagem (apenas letras, ex: 'Acz'): Acz
Saída Esperada:
Chave Pública: (7, 391)
Chave Privada: (151, 391)
Mensagem Criptografada: 120 321
Mensagem Descriptografada: Acz
3️⃣ Validar CPF e ISBN
Exemplo de Entrada:
3
Digite o CPF (11 dígitos): 12345678909
Digite o ISBN (10 dígitos): 8535902775
Saída Esperada:
CPF é válido
ISBN é válido
Se o CPF ou ISBN forem inválidos, o programa informará:
CPF é inválido
ISBN é inválido
0️⃣ Sair do Programa
Para encerrar a execução, basta inserir 0 no menu.
0
Tchau!
Observações
- O programa só aceita caracteres alfabéticos para criptografia RSA.
- O sistema de congruências exige que
aseja invertível módulom. - O CPF deve conter 11 dígitos numéricos.
- O ISBN deve conter 10 dígitos.
Código
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
// Função para calcular o inverso modular usando o Algoritmo de Euclides Estendido
int modInverse(int a, int m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
// Função para resolver sistema de congruências usando o Teorema do Resto Chinês
int chineseRemainder(vector<int> num, vector<int> rem, int k) {
int prod = 1;
for (int i = 0; i < k; i++) prod *= num[i];
int result = 0;
for (int i = 0; i < k; i++) {
int pp = prod / num[i];
result += rem[i] * modInverse(pp, num[i]) * pp;
}
return result % prod;
}
// Função para calcular a potência modular
long long modExp(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Função para validar CPF
bool validateCPF(string cpf) {
int sum1 = 0, sum2 = 0, d1, d2;
if (cpf.length() != 11) return false;
for (int i = 0; i < 9; i++) sum1 += (cpf[i] - '0') * (10 - i);
d1 = (sum1 * 10) % 11;
if (d1 == 10) d1 = 0;
for (int i = 0; i < 9; i++) sum2 += (cpf[i] - '0') * (11 - i);
sum2 += d1 * 2;
d2 = (sum2 * 10) % 11;
if (d2 == 10) d2 = 0;
return d1 == (cpf[9] - '0') && d2 == (cpf[10] - '0');
}
// Função para validar ISBN-10
bool validateISBN(string isbn) {
if (isbn.length() != 10) return false;
int sum = 0;
for (int i = 0; i < 9; i++) sum += (isbn[i] - '0') * (10 - i);
char check = isbn[9];
int d = (check == 'X') ? 10 : (check - '0');
return (sum + d) % 11 == 0;
}
// Função para mapear caractere para número baseado em A=11, Z=36, a=37, z=62
int charToNumber(char c) {
if (c >= 'A' && c <= 'Z') return 11 + (c - 'A');
if (c >= 'a' && c <= 'z') return 37 + (c - 'a');
return 0; // Caso inválido
}
// Função para mapear número para caractere
char numberToChar(int num) {
if (num >= 11 && num <= 36) return 'A' + (num - 11);
if (num >= 37 && num <= 62) return 'a' + (num - 37);
return '?'; // Caso inválido
}
// Função para codificar uma string em um vetor de números (blocos para RSA)
vector<int> encodeMessage(const string& message, int n) {
vector<int> encodedBlocks;
for (char c : message) {
int num = charToNumber(c);
if (!encodedBlocks.empty() && encodedBlocks.back() * 100 + num < n) {
encodedBlocks.back() = encodedBlocks.back() * 100 + num;
} else {
encodedBlocks.push_back(num);
}
}
return encodedBlocks;
}
// Função para decodificar um vetor de números de volta para string
string decodeMessage(const vector<int>& decryptedBlocks) {
string message = "";
for (int block : decryptedBlocks) {
while (block > 0) {
int num = block % 100;
block /= 100;
message = numberToChar(num) + message;
}
}
return message;
}
// Menu
void menu() {
cout << "Escolha a funcionalidade:\n";
cout << "1 - Resolver sistema de congruência (Teorema do Resto Chinês)\n";
cout << "2 - Realizar criptografia RSA\n";
cout << "3 - Validar CPF e ISBN\n";
cout << "0 - Sair\n";
cout << "Escolha: ";
}
int main() {
int choice;
do {
menu();
cin >> choice;
if (choice == 1) {
int k;
cout << "Número de equações (até 4): ";
cin >> k;
vector<int> num(k), rem(k);
for (int i = 0; i < k; i++) {
int a, b, m;
cout << "Equação " << i + 1 << " no formato ax ≡ b (mod m)\n";
cout << "Coeficiente 'a': ";
cin >> a;
cout << "Resto 'b': ";
cin >> b;
cout << "Módulo 'm': ";
cin >> m;
int a_inv = modInverse(a, m);
if (a_inv == 0) {
cout << "Erro: Não há inverso modular para a = " << a << " mod " << m << "\n";
return 1;
}
num[i] = m;
rem[i] = (b * a_inv) % m;
}
cout << "Solução: x = " << chineseRemainder(num, rem, k) << "\n" << endl;
} else if (choice == 2) {
int p, q, e;
cout << "Digite dois números primos (p e q): ";
cin >> p >> q;
cout << "Digite o expoente de criptografia (e): ";
cin >> e;
int n = p * q;
int phi = (p - 1) * (q - 1);
int d = modInverse(e, phi);
cout << "Chave Pública: (" << e << ", " << n << ")\n";
cout << "Chave Privada: (" << d << ", " << n << ")\n";
string inputMessage;
cout << "Digite uma mensagem (apenas letras, ex: 'Acz'): ";
cin >> inputMessage;
vector<int> encodedBlocks = encodeMessage(inputMessage, n);
vector<int> encryptedBlocks, decryptedBlocks;
for (int block : encodedBlocks) encryptedBlocks.push_back(modExp(block, e, n));
cout << "Mensagem Criptografada: ";
for (int block : encryptedBlocks) cout << block << " ";
cout << "\n" << endl;
for (int block : encryptedBlocks) decryptedBlocks.push_back(modExp(block, d, n));
cout << "Mensagem Descriptografada: " << decodeMessage(decryptedBlocks) << "\n" << endl;
} else if (choice == 3) {
string cpf, isbn;
cout << "Digite o CPF (11 dígitos): ";
cin >> cpf;
cout << "CPF é " << (validateCPF(cpf) ? "válido" : "inválido") << "\n" << endl;
cout << "Digite o ISBN (10 dígitos): ";
cin >> isbn;
cout << "ISBN é " << (validateISBN(isbn) ? "válido" : "inválido") << "\n" << endl;
}
} while (choice != 0);
return 0;
}