Dúvida criptografia com: or, not, and

pedraoljr · 3 de maio de 2011

Saudações!

Faço Análise de Sistemas, e numa cadeira de segurança de TI o professor dividiu vários assuntos entre a turma.

A mim, foi passada a tarefa de explicar o que é criptografia com or, and e not, como funciona, como pode ser usado em criptografia e um pequeno exemplo de código.

Pois bem, já pesquisei em tudo que é lugar mas nada me leva ao objetivo.

Será que é apenas explicar que são operadores lógicos? Mas como isso influencia na criptografia?

Aguardo ajuda!

Grato pela atenção e boa semana a todos!

Ghost Killer · 3 de maio de 2011

Vou começar usando outras portas lógicas pra mostrar como dá pra criptografar uma mensagem e depois descriptografar ela:

Imagine a seguinte mensagem: 10101010111010

E a seguinte chave de criptografia: 01000101010010

Vou criptografar a mensagem fazendo um NOT XOR entre a mensagemas e a chave. Pra ficar mais claro, segue a tabela verdade do NOT XOR:

A B Y

0 0 1

1 0 0

0 1 0

1 1 1

Sendo A e B duas entradas, e Y a saída. Resumindo: Valores iguais sai 1, valores diferentes sai 0.

Resultado do NOT XOR (mensagem criptografada): 00010000010111

Da mensagem criptografada, sem saber qual a chave e a regra de criptografia, ninguem consegue descobrir qual é a mensagem original, pois ela é bem diferente da mensagem criptografada (10101010111010). Quem souber a senha, pode voltar a mensagem original fazendo outro NOT XOR entre a mensagem criptografada e a chave (faça o teste). Perceba ainda, que se um unico bit da chave fosse trocado, a resposta não seria a mesma (voce não retornaria para a mensagem original).

Agora vem a parte interessante: voce disse que precisava utilizar portas AND, NOT e OR, mas eu utilizei outras. Isso é porque com as portas NOT e AND ou as portas NOT e OR é possível obter todas as outras (inclusive a NOT XOR que eu usei pra criptografar).

Construindo uma porta XOR usando portas NOT e AND:

Ou construindo uma porta XOR usando portas NOT e OR:

Lembrando a legenda básica das portas lógicas:

AND:

OR:

e o NOT é a bolinha que aparece na porta.

Fiquei pelo menos uma meia hora pensando numa lógica que desse certo, cheguei nesse capeta que mostrei e acho que dá certo sempre mesmo...

Um código em C++ para criptografar um dado binário baseado no que foi dito aqui:

#include <cstdlib>
#include <iostream>

using namespace std;

int main() {

bool mensagem[8];
bool chave[8];
bool criptografado[8];
bool reverso[8];
bool teste[8];
bool acertou = 0;
int conta = 0;
cout << "Programa que codifica e decodifica mensagem de 8 bits\n";
for (int i = 0; i < 8; i++)
{
	cout << "\nEscreva o digito numero " << i+1 << " da mensagem a ser criptografada: ";
	cin >> mensagem[i];
}
cout << "\nA mensagem a ser criptografada e: \n";
for (int i = 0; i < 8; i++)
{
	cout << mensagem[i];
}
for (int i = 0; i < 8; i++)
{
	cout << "\nEscreva o digito numero " << i+1 << " da senha de encriptacao: ";
	cin >> chave[i];
}
cout << "\nA chave de criptografia e: \n";
for (int i = 0; i < 8; i++)
{
	cout << chave[i];
}
for (int i = 0; i < 8 ; i++)
{
    criptografado[i] = (!(!(mensagem[i] && chave[i]) && mensagem[i])) && (!(!(mensagem[i] && chave[i]) && chave[i])); //not xor
}
cout << "\nA mensagem criptografada e: ";
for (int i = 0; i < 8; i++)
{
    cout << criptografado[i];
}
while (!acertou)
{
	for (int i = 0; i < 8; i++)
	{
		cout << "\nInsira o digito numero " << i+1 << " da chave para descriptografar a mensagem: ";
		cin >> teste[i];
	}
	for (int i = 0; i < 8 ; i++)
	{
		reverso[i] = (!(!(criptografado[i] && teste[i]) && criptografado[i])) && (!(!(criptografado[i] && teste[i]) && teste[i])); //not xor
		if (reverso[i] == mensagem[i])
		{
			conta = conta+1;
		}
	}
	if (conta == 8)
	{
		cout << "\nSenha correta!";
		cout << "\nMensagem original: ";
		for (int i = 0; i < 8; i++)
		{
			cout << mensagem[i];
		}
		cout << "\nMensagem descriptografada: ";
		for (int i = 0; i < 8; i++)
		{
			cout << reverso[i];
		}
		acertou = 1;
	}
	else
	{
		cout << "\nSenha incorreta!";
		cout << "\nMensagem original: ";
		for (int i = 0; i < 8; i++)
		{
			cout << mensagem[i];
		}
		cout << "\nMensagem descriptografada: ";
		for (int i = 0; i < 8; i++)
		{
			cout << reverso[i];
		}
	}
}
cout << "\n";
system("PAUSE");
return 0;
}

Fiz esse código agora, testei e está funcionando no Dev C++

Passo o paypal pra voce transferir o dinheiro agora, ou depois que voce tirar o 10?

pedraoljr · 3 de maio de 2011

Ghost, eu ja vi ajudas boas por aí.

Mas essa, foi um ESCULACHO!

Sem palavras para agradecer-lhe!

Te devo uma!

Ghost Killer · 3 de maio de 2011

voce deu sorte que apesar de estar todo atarefado e ser preguiçoso, eu gosto de um desafio. Quebrei a cabeça por cerca de meia hora pra pensar em como utilizar portas lógicas pra isso (se fosse usando if e else e operações aritméticas ao invés de lógica, sairia em segundos).

pedraoljr · 6 de maio de 2011

Ghost, sua resposta ajudou muito.

Mas fico cabrero porque não acho nada a respeito no google e tal. Como saber se minha explicação está certa mesmo se não consigo achar material pra comparar?

Isso que o professor falou que esse método é bastante usado. Será que eu é que estou procurando errado? hehehe

Abraço!

É incrível, cara.

Coloco criptografia com XOR e aparecem milhares de sites.

Coloco com or, and ou not e só aparece lixo. Será que o professor me sacaneou? hahaha

Ah, e esse código aí em cima é com XOR né?

Ghost Killer · 6 de maio de 2011

Ele não te sacaneou, como falei, o XOR é uma união de NOTs e ANDs ou de NOTs e OR... voce chegou a ler toda a minha explicação? Eu usei um NOT XOR (fiz um XOR e depois neguei ele). E depois expliquei como fazer um XOR usando NOT e AND.

Essa linha aqui do meu código, como eu já disse, tem um NOT XOR. Repare que nesse NOT XOR, só tem ANDs e NOT, e ainda assim é um NOT XOR:

(!(!(mensagem && chave) && mensagem)) && (!(!(mensagem && chave) && chave))

Essa linha é EXATAMENTE igual a essa aqui:

!(mensagem XOR chave)

Pra verificar se meu método está certo, pegue o Dev C++, compile o programa que eu passei e rode. Insira qualquer mensagem de 8 bits, qualquer senha de 8 bits, e veja que ao colocar a senha errada, voce não obtem a mensagem original. Já colocando a senha correta, voce obtem a mensagem original.

Se voce pesquisar por criptografia em qualquer material (não tenho pra te fornecer, a minha formação é engenharia, não sistemas de informação ou algo do tipo), voce vai ver que o objetivo da criptografia é garantir que somente o destinatário da mensagem tenha acesso ao conteúdo dela, e que pra isso ocorrer normalmente é usada uma chave de criptografia (uma senha), e voce vai conferir que isso é também o que ocorre nesse método que eu inventei e te passei.

Resumindo: Errado não está, voce pode conferir isso de várias maneiras.

Agora, se voce quiser usar algum método famoso e não apenas um que funcione (coisa que acaba sendo complicada se for para fins didáticos), voce vai ter que procurar por AES, WPA, WEP entre outros e ver se algum deles explica como é feito usando portas lógicas AND, NOT, OR... O tenso é que essas formas de criptografia que eu falei não usam chaves de 8 bits como a minha, e sim chaves de 128 bits pra cima (mas é mais eficiente porque eles criptografam mensagens de milhares de bits também e não de apenas 8 bits...). Acho difícil voce encontrar essa explicação, eles provavelmente usam uma lógica mais de alto nivel (o AND, NOT e OR devem ser usados de forma implicita dentro de um IF por exemplo, sem voce ver de fato um AND, NOT ou OR)...

É bom também não confundir um CRC da vida com um método de criptografia, pois o CRC só serve pra garantir que duas mensagens são iguais, mas com apenas o código CRC voce não consegue voltar ao código original...