Algoritmos/Criptografia

Criptografia (em grego: kryptós, "escondido", e gráphein, "escrita"), é uma área de estudo que busca desenvolver técnicas de transformar informações claras em conteúdos aparentemente sem sentido, onde somete alguma outra pessoa ou máquina que tenha uma "chave de acesso" consiga transformar aqueles dados em informação legível.

A utilização da criptografia se faz essencial quando precisamos guardar informações sigilosas onde poucas pessoas podem ter acesso, pois caso alguém consiga estes dados, seu conteúdo continua incompreensível, já que para ter acesso as informações é preciso utilizar sua "chave de acesso". Um filme que retrata muito bem uma das utilizações e a importância da utilização da criptografia em assuntos delicados é o filme "O Jogo da Imitação" de 2014, que conta a história de Alan Turing um criptoanalista Inglês e como ele junto de sua equipe conseguiu descriptografar as mensagens da máquina Enigma da Alemanha Nazista, sendo fundamental para o desfecho da Segunda Guerra Mundial.

Cifras de substituição

Uma cifra de substituição tem como característica a permanência do caracter do texto plano em sua posição original, mas o mesmo é substituído por outro caracter ou símbolo de um conjunto pré-escolhido, chamado de alfabeto de substituição ou alfabeto de cifra. Além de caracteres isolados, palavras ou até mesmo frases podem ser substituídas.

Existem algumas classificações para as cifras de substituição: monoalfabéticas ou simples, homófonas, polialfabéticas, poligrâmicas e poligráficas.

A substituição simples ou monoalfabética é aquela em que para cada caracter do texto plano corresponde um só caracter ou símbolo do alfabeto de substituição.

A substituição homófona possui um ou mais símbolos para alguns caracteres do alfabeto normal.

Já as cifras de substituição polialfabéticas são as que utilizam mais de um alfabeto de substituição para o alfabeto normal.

Por último, as cifras de substituição poligráficas substituem grupos de caracteres da mensagem por símbolos.

Uma das mais conhecidas cifras de substituição simples é a Cifra de César utilizada pelo imperador romano Julius Caesar. Nesta cifra um valor de deslocamento é definido, então cada letra do texto é substituída pela letra do alfabeto referente a esse deslocamento. Por exemplo, com um deslocamento de 3, a letra A é substituída pela letra D, B se torna E e assim sucessivamente. As letras do final do alfabeto, são substituídas pelas primeiras: X se torna A, Y se torna B e Z se torna C.

Aqui temos um exemplo da Cifra de César em Java:

public static String cifrar(int chave, String texto){
      //Variavel que guarda o texto cifrado 
      StringBuilder textoCifrado = new StringBuilder();
      //Variavel com tamanho do texto a ser cifrado 
      int tamanhoTexto = texto.length();
      
      //Criptografa um caracter de cada vez
      for(int c=0; c < tamanhoTexto; c++){
         //Transforma o caracter em codigo ASCII e faz a criptografia
         int letraCifradaASCII = ((int) texto.charAt(c)) + chave;
         
         //Verifica se o codigo ASCII esta no limite dos caracteres que podem ser impressos
         while(letraCifradaASCII > 126)
            letraCifradaASCII -= 94;

         //Transforma codigo ASCII cifrado em caracter no novo texto
         textoCifrado.append( (char)letraCifradaASCII );
      }
      
      //Retorna a mensagem completa criptografada 
      return textoCifrado.toString();
   }

http://rennerocha.com/2013/01/criptografia--cifras-de-substituicao/

Cifras de Transposição

Outro tipo simples de cifra é a de transposição que, diferente da cifra de substituição, consiste em realizar a criptografia através da re-ordenação dos caracteres do texto a ser criptografado. Essa troca dos caracteres deve ser baseada numa chave para que seja possível tanto a cifragem quanto a decifragem.

Uma cifra de transposição simples e bem conhecida é a Cifra das Colunas, onde o texto a ser criptografado é escrito em linhas cujo tamanho é definido por uma chave que corresponderá ao cabeçalho. Os espaços que restarem podem ser deixados em branco ou preenchidos com caracteres sem significado. Ao fim da escrita, o texto estará dividido em colunas e, para que o texto cifrado seja obtido, basta escrever os caracteres de cada coluna tendo como base a ordem alfabética do cabeçalho. Por exemplo, o texto "TROCA DE POSTO" ao ser cifrado com a chave "ZEBRA" teria o seguinte resultado:

Z	E	B	R	A
T	R	O	C	A
	D	E		P
O	S	T	O

Seguindo a ordem alfabética do cabeçalho:

Coluna A -> "AP"

Coluna B -> "OET"

Coluna E -> "RDS"

Coluna R -> "C O"

Coluna Z -> "T O"

Escrevendo o texto cifrado completo:

"APOETRDSC OT O"

Para a decifragem do texto o destinatário, tendo conhecimento da chave, deve inicialmente recriar a tabela utilizando-a como cabeçalho. Em seguida, devem ser contados o número de caracteres da mensagem cifrada e divididos pelo número de caracteres da chave, sendo o quociente o número de linhas completamente preenchidas, e o resto o número de caracteres da última linha da tabela. Por fim, basta inserir a mensagem nas linhas como no processo de cifragem. Utilizando o mesmo exemplo:

Construímos a tabela vazia baseada na chave:

Z	E	B	R	A
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.

"APOETRDSC OT O" -> 14 caracteres

"ZEBRA" -> 5 caracteres

Realizando a divisão temos quociente 2 e resto 4 ou seja, 2 linhas totalmente preenchidas e a última linha com 4 caracteres, tendo um total de 3 linhas.

Z	E	B	R	A
T	R	O	C	A
	D	E		P
O	S	T	O

Cifra de Vigenère

A cifra de Vigenère é uma estratégia adotada pela criptografia, onde são utilizadas diversas cifras de César, fazendo com que a cifra de Vigenère seja classificada como uma cifra de substituição. Esta maneira de criptografar dados foi desenvolvida inicialmente pelo criptologista italiano Giovan Battista Bellaso, que publicou seus resultados e ideias sobre esta forma de codificação no livro de sua autoria "La cifra del. Sig. Giovan Battista Bellaso", em 1553, porém os créditos foram dados de maneira errada a Blaise de Vigenère no século XIX, nomeado assim a técnica como "Cifra de Vigenère".

A principal diferença da cifra de Vigenère para a cifra de César, é com relação a maneira como os carácteres de uma mensagem são deslocados para codificar a mensagem. Enquanto a cifra de César utiliza os mesmos valores para deslocar TODOS os elementos de uma mensagem (ex.: em uma mensagem de 20 carácteres, e o valor de deslocamento de uma mensagem seja 20, todos os carácteres irão deslocar 20 posições, independente de sua posição), porém quando falamos sobre a cifra de Vigenère, percebemos que maneira como os carácteres são deslocados acontece de forma diferente, pois o valor de deslocamento de cada carácter se dá em função de uma senha(chave de acesso) fornecida na hora da codificação, e a posição do carácter em relação a mensagem.

Como acontece a codificação

Como descrito acima, a codificação acontece de maneira similar a cifra de César, porém o valor de deslocamento de cada letra acontece de maneira diferente, pois esse número depende de sua posição na mensagem, mas os valores utilizados para deslocar os carácteres repetem de maneira uniforme a cada $N$ carácteres da mensagem, onde $N$ é o tamanho da senha utilizada no momento da codificação da mensagem.

Para explicação e ilustração do funcionamento da cifra, o alfabeto será limitado a letras maiúsculas e enumeradas de (0-25), porém é preciso lembrar que se tratando de computadores, existem diversos símbolos que podem ser utilizados para deixar a codificação ainda mais confusa para alguém que receba a informação no meio do caminho e não tenha acesso a senha utilizada.

Após escolher uma senha, iremos utilizar a cifra de César em todas os carácteres da mensagem que será criptografada, e para o cálculo do valor de deslocamento de cada carácter, iremos utilizar os valores 0-25, onde A = 0, B = 1 e assim por diante. Os valores de deslocamento dos carácteres da mensagem estarão diretamente relacionados a sua posição na mensagem, seu valor numérico e ao valor numérico do carácter presente na senha que esteja em uma posição equivalente ou igual. A seguir veremos um exemplo:

Suponha que queremos mandar uma mensagem com o conteúdo "VENCEMOS" com a seguinte senha "CRYPT", utilizando a explicação acima temos como valores numéricos:

V	E	N	C	E	M	O	S		C	R	Y	P	T
21	4	13	2	4	12	14	18		2	17	24	15	19

Depois de termos os valores numéricos de cada carácter, iremos fazer a cifragem de acordo com a posição da letra e de sua equivalente na senha.

"Quadrado de Vigenère" ou tabula recta, que auxilia na codificação e decodificação de mensagens utilizando a cifra de Vigenère

• A letra V está na primeira posição da mensagem, a primeira letra da senha é C, ou seja iremos adicionar o valor numérico da letra C ao valor numérico da letra V e utilizar o valor resultante para encontrar a letra "gerada" após essa adição, ou seja, temos V(21) + C(2) = X(23), agora faremos o mesmo procedimento para todas as letras da mensagem;
• A letra E está na segunda posição da mensagem, letra R na segunda posição da senha, logo temos E(4) + R(17) = V(21);
• 3ª posição: N(13) + Y(24) = ?(37), nesse caso o valor 37 excedeu o maior número da nossa lista, onde são adimitos números de 0-25. O que faremos a seguir é calcular o resto da divisão(mod) do valor total com o maior número possível de ser representado na nossa cifragem, no caso queremos o resto da divisão de 37 por 26(número total de carácteres possíveis, que no nosso exemplo são 26), ou 37%26(37 mod 26), que resulta em 11, logo o valor é L;
• 4ª posição: C(2) + P(15) = R(17);
• 5ª posição: E(4) + T(19) = X(23);
• Chegamos ao final da senha, mas como dito anteriormente, os valores utilizados irão se repetir a cada $N$ vezes onde $N$ é o tamanho da senha, e é nesse momento que essa repetição começa. Como chegamos ao final da senha, iremos recomeçar a soma dos valores numéricos da primeira posição da senha. Ou seja para a 6ª posição teremos M(12) + C(2) = O(14), e continuaremos com esse procedimento até o fim da mensagem;
• 7ª posição: O(14) + R(17) = ?(31) = F(5);
• 8ª posição: S(18) + Y(24) = ?(42) = Q(16);
• Por fim temos o resultado: xvlrxofq

Também é possível fazer a utilização do "Quadrado de Vigenère" ou "tabula recta", onde para encontrar o valor gerado, basta buscar pelo valor presente na linha da letra atual da senha, com a coluna do valor que será codificado.

Como fazer a decodificação

A função da criptografia, é permitir o embaralhamento de mensagens e torná-las ilegíveis para qualquer pessoa sem acesso a uma senha, e apesar de a cifra de Vigenère ser fácil de ser quebrada hoje, foram precisos 300 anos para que alguém conseguisse descobrir como quebrar esta tática de criptografia.

Para fazer a decodificação é feito o mesmo processo da codificação, porém ao invés de serem somados os valores numéricos, o valor total é subtraído do valor numérico do elemento presente na senha. Ou seja fazendo o caminho inverso do exemplo anterior teríamos:

X	V	L	R	X	O	F	Q		C	R	Y	P	T
23	21	11	17	23	14	5	16		2	17	24	15	19

• 1ª posição: X(23) - C(2) = V(21)
• 2ª posição: V(21) - R(17) = E(4)
• 3ª posição: L(11) - Y(24) = ?(-13), como temos um número negativos, faremos 26(Número total de carácteres disponíveis) + valor negativo, ou seja, nesse caso temos: 26 - 13 = 13, logo o valor numérico é 13, representado pela letra N(13)

• 4ª posição: R(17) - P(15) = C(2)
• 5ª posição: X(23) - T(19) = E(4)
• 6ª posição: O(14) - C(2) = M(12)
• 7ª posição: F(5) - R(17) = ?(-12) = O(14)
• 8ª posição: Q(16) - Y(24) = ?(-8) = S(18)
• Por fim temos a mensagem: VENCEMOS

http://www.bosontreinamentos.com.br/seguranca/criptografia-cifra-de-vigenere/

Como quebrar a codificação

No caso da chave de codificação ser desconhecida podemos usar de outros meios para decodificar a mensagem. A estrategia mais comum é o uso de métodos estatísticos para descobrir o tamanho da chave, e com esse tamanho usar algoritmos de frequência de analise para obter a resposta.

Comece por fazer uma busca de Strings que se repetem no texto cifrado, dando preferencia a Strings maiores, e as marque.

Conte quantas letras possuem entre as Strings repetidas. Por exemplo se o texto criptografado for "KPQRE IIJKO KPQAE", entre o primeiro e o segundo "K" possuem 10 letras contando com o K.

Descubra os fatores desse numero, excluindo o 1, e os armazene.

Repita o processo para todas as repetições de String, o fator que mais aparece é provavelmente o tamanho da chave que foi usada para criptografar, chamaremos aqui de "X".

Agora podemos usar da frequência de analise para descobrir a chave. Crie uma tabela com X colunas e reescreva o texto dentro dessa tabela, com isso em cada coluna possui um texto que foi encriptado usando a criptografia de César.

Um dos métodos mais simples, de força bruta, é criar 26 linhas com os candidatos possíveis de texto real, apenas faça a troca dos caracteres como no exemplo a seguir.

Rotação/Chave	Texto possível
0	ExeuyiEksve
1	DwdtxhDjrud
2	CvcswgCiqtc
3	BubrvfBhpsb
4	AtaqueAgora
...
24	GzgwakGmuxg
25	FyfvzjFltwf

• https://www.math.cornell.edu/~mec/2003-2004/cryptography/polyalpha/polyalpha.html
• https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#Cryptanalysis