C++ Criptografia Simétrica em C++ (Utilização de chave)

[Vitor G. Delgallo]

Recentemente tenho tentado desenvolver um programa de criptografia em c++ para um projeto escolar, no entanto, apesar da criptografia funcionar, não consigo fazer a função para descriptografar a string.
Depois de vários testes, percebi que o int de cada char da string ao criptografar e fazer os calculos eram números como "1354", "341".... no entanto, ao testa-los novamente, ao descriptografar, davam números negativos ou absurdamente grandes... Não sei se o que eu disse faz algum sentido, mas se puderem me ajudar eu agradeço.
Segue em anexo o programa!

crypt.rar

[RafaelCLP]

Vou copiar a parte importante do código que você postou acima aqui só pra não ter que ficar baixando o arquivo:

string symmetricCrypt(string str, string chave){
	unsigned long valor = 0, chave_int = 0;
	string strC = "";

    for(int aux = 0; aux < str.length(); ){
        for(int i = 0; i < chave.length(); i++){
            chave_int = chave[i];
            valor = str[aux] * chave_int;            
            strC += (unsigned char) valor;
            aux++;
        }
    }

    return strC;
}

string symmetricDecrypt(string str, string chave){
    unsigned long valor = 0, pos_chave = 0;
	string strDec = "";
	
	for(int i = 0; i < str.length(); i++){
		valor  = str[i];
		valor /= chave[pos_chave];
		strDec += (char) valor;
		
		if(pos_chave == (chave.length() - 1)){
            pos_chave=0;
        }else{
            pos_chave++;
        }
	}

	return strDec;
}

Eu sei qual o problema, mas não sei como explicar de uma forma fácil de entender =/.

 

Primeira coisa que você deve corrigir é no Crypt. Se str.length() não for um múltiplo de chave.length() dá problema, porque você continua aumentando o aux e acessando str[aux] mesmo após acabar a string.

 

Agora, vamos ao real problema de sua criptografia

Tanto str[aux] quando chave[ i ] podem ter um valor de 0 a 255 (ou -128 a 127), assumindo que pode receber um binário pra ser criptografado. Isso significa que str[aux] * chave[ i ] dão um valor de até 255².

 

Só que em seguida você concatena o resultado convertido para unsigned char em uma string. Como unsigned char só vai de 0 a 255, o que você está fazendo é idêntico a:

strC += (unsigned char) (valor % 256); // o resto da divisão de valor por 256

O que isso significa é que strC[ i ] é o equivalente a:

strC[i] = (unsigned char) (((unsigned int) str[i] * chave[i % chave.length()]) % 256);

Que pode ser simplificado para:

strC[i] = str[i] * chave[i % chave.length()];

Note que o % 256 é aplicado implicitamente por causa do overflow. Para prosseguir, vamos escrever isso da seguinte forma:

SCi = Si * Ci (mod 256),
	onde SCi = strC[i], Si = str[i] e Ci = chave[i % chave.length()]

 

Agora vem a sua descriptografia.

strD[i] = strC[i] / chave[i % chave.length()] % 256 // esse % 256 está implicito no cast: (char)

Vou deixar sua equação no mesmo formato da de cima:

SDi = SCi / Ci (mod 256),
	onde SDi = strD[i], SCi = strC[i] e Ci = chave[i % chave.length()]

Por que isso não funciona? Esta é a parte difícil de te explicar. Você precisaria de estudar teoria dos números para entender. Mas vou tentar ao menos te mostrar que não funciona.

 

Vamos dizer que Si = 65 ('A') e Ci = 66 ('B'). Pela fórmula da criptografia, temos:

SCi = Si * Ci (mod 256)
SCi = 65 * 66 (mod 256)
SCi = 4290 (mod 256)
SCi = 194

Agora vamos descriptografar:

SDi = SCi / Ci (mod 256)
SDi = 194 / 66 (mod 256)
SDi = 2 (mod 256)
SDi = 2

Bem diferente do original 65. Isso acontece por causa do mod. Você não pode realizar divisões quando há mod envolvido. Multiplicações funcionam, divisões não!!

 

O que você pode fazer? Em vez de dividir por 66 (mod 256), pode multiplicar por 66^-1 (mod 256). Mas lembre-se que 66^-1 = 1/66, e você não pode dividir, então precisa de outra forma de calcular o valor de 66^-1 (mod 256). Para calcular o inverso modular (b^-1 mod M), veja: http://mathworld.wolfram.com/ModularInverse.html

 

O problema é que para um número N (mod M) ter inverso modular, N e M devem ser coprimos (não devem ter nenhum fator primo em comum). Não é o caso aqui (66 e 256, por exemplo, têm o 2 como fator em comum). Logo, sua descriptografia jamais poderia funcionar se Ci for par.

 

Você pode tentar chutar um valor pra SDi e ver se ao criptografá-lo dá SCi. Em outras palavras, testar todos os possíveis valores de SDi e achar aqueles que, ao criptografar, resultam em SCi. Só que vários caracteres distintos em Si podem resultar no mesmo SCi. Por exemplo, no caso acima em que Ci = 66, tanto Si = 65 quanto Si = 193 resultariam no mesmo SCi = 194. Como saber qual dos dois é o correto? Não dá...

 

Em resumo, sua criptografia não funciona. Ela não pode ser descriptografada.

 

O que fazer para resolver o problema?

Em vez de jogar essa criptografia fora e fazer outra, você pode simplesmente alterar o valor de Ci tal que seja possível calcular o inverso modular. O usuário digita a chave, mas em vez de você usar Ci, você usa 2*Ci + 1. Isso resulta num número ímpar, que sempre é coprimo de 256 (2^8), e portanto o inverso modular existe. A existência do inverso modular implica que pra todo par (SCi, 2*Ci + 1), só existe um Si que poderia ter produzido tal SCi.

 

Para calcular o inverso modular (lembre-se: você não poderá realizar a divisão, terá que substituí-la por uma multiplicação) veja o link que te mandei ou pesquise vídeos a respeito.

adicionado 23 minutos depois

Pra facilitar tua vida, aqui está um jeito bem simples de encontrar o inverso modular que eu considero fácil de entender:

int invmod(int b, int m) {
	int bb = b;
	while (bb > 0 && (bb * b) % m != 1)
		bb = (bb * b) % m;
	return bb;
}

Repare que eu paro quando ( bb * b ) % m dá 1 e retorno bb.

 

Por que? Existe um ciclo aí. Depois que multiplicarmos bb por b uma certa quantidade de vezes, ele vai voltar para seu valor inicial. Afinal, se eu sempre aplico % m, apenas m valores distintos podem ser obtidos, e uma hora vão ter que começar a se repetir.

 

Note que b^0 % m = 1.

Logo, se b^e % m = 1, o ciclo resetou (b^e seria equivalente a b^0), então b^(e-1) % m = (b^0 * b^-1) % m = 1 * b^-1 % m = b^-1 % m. Exatamente o que queremos!

 

Esse código é pouco eficiente, O(m), então eu recomendo usar o algoritmo de euclides e usar o código acima só pra entender a ideia.