Entendendo a criptografia - Parte 13

Exercício prático com o S-DES

Hoje vamos ver então um exemplo prático de criptografia com o S-DES. Não vou colocar aqui novamente todas aquelas imagens e explicações, vou direto ao ponto.

A única coisa que vou buscar dos outros posts antes de começar é as subchaves que criamos.

K1 = 11110010

K2 = 11000111

Recomendo que abra abas com os textos passados do S-DES para ir acompanhando as operações.

Para não cortar o fluxo do exercício vou comentar antes sobre os XOR que aparecerão no texto. Teoricamente se você está lendo este texto provavelmente você tem uma noção de binário e operações com eles, caso não tenha já sabe o que precisa estudar! :)

Esta é a tabela do XOR. Mesmo sem ter estudado operações em binário da para ter uma noção do que ela faz. Caso ainda ficou alguma dúvida veremos na prática logo abaixo.

Chega de enrolação e vamos a prática!

Nossa primeira operação é a IP, que acho que esqueci de colocar nos textos anteriores sua caixa.

O texto claro que vamos criptografar, chamaremos de X:

X = 01010001

Etapa 1: Ao passarmos a entrada X pela caixa IP teremos como resultado "10001100".

Etapa 2: Dividimos X em duas partes, a primeira parte segue para o fim e a segunda parte entra em E/P. O "1100" que entra no E/P sai como "01101001".

Etapa 3: Saída de E/P entra em um XOR com a subchave K1:

01101001 --> E/P
11110010 --> K1
10011011 --> Resultado

Etapa 4: Saída do XOR é dividida em duas partes e cada uma entra em uma Caixa-S:

Saída = 10011011
S0 = 1001
S1 = 1011
Resultado S0 = Linha 11, Coluna 00, Valor 3 = 11
Resultado S1 = Linha 11, Coluna 01, Valor 1 = 01

Etapa 5: Resultado das Caixas-S é unido novamente e usado como entrada na caixa P4. "11" e "01" entram em P4 e como resultado geram "1101".

Etapa 6: XOR com a primeira parte de IP:

1000 --> IP
1101 --> P4
0101 --> Resultado

Etapa 7: Realizado a inversão de entradas com a caixa SW. Entradas "0101" (XOR - Etapa 6) e "1100" (IP - Etapa 1) viram as Saídas "1100" e "0101".

Etapa 8: Iniciando a segunda função complexa, a primeira metade da saída anterior vai para o fim do algoritmo e a segunda vai para a caixa E/P. Resultado de E/P é "10101010".

Etapa 9: XOR com a segunda subchave:

10101010 --> E/P
11000111 --> K2
01101101 --> Resultado

Etapa 10: Saída do XOR é dividida em duas partes e cada uma entra em uma Caixa-S:

Saída = 01101101
S0 = 0110
S1 = 1101
Resultado S0 = Linha 00, Coluna 11, Valor 2 = 10
Resultado S1 = Linha 11, Coluna 10, Valor 0 = 00

Etapa 11: Resultado das Caixas-S é unido novamente e usado como entrada na caixa P4. "10" e "00" entram em P4 e como resultado geram "0001".

Etapa 12: XOR com a primeira parte de SW:

1100 --> IP
0001 --> P4
1101 --> Resultado

Etapa 13: Por fim, o resultado do XOR (1101) e o segundo resultado de SW (0101) juntam-se e entram em IP -1 que gerará nosso texto cifrado. Temos então nesta prática como texto cifrado o valor "11000111".

E era isso! Se estivessemos usando o algoritmo DES normal, teríamos que repetir essas operações por mais 14 vezes.

Compare nossa entrada X = 01010001 com a saída final "11000111". Completamente diferente e sem nenhum sentido. Claro que neste exemplo usamos apenas um bloco, mas se quiser testar pode fazer com um algoritmo de verdade, com algum software de criptografia que comentarei em algum post futuro. Verá que o resultado é totalmente ilegível.

Efeito Avalanche

O efeito avalanche explica o motivo de um algoritmo de criptografia ter de repetir diversas vezes o mesmo conjunto de operações. A mínima mudança no texto plano ou na chave deve gerar grandes mudanças no texto cifrado. Quanto mais rodadas, mais o texto cifrado sofre do efeito avalanche e maior é o impacto dessa mudança. Veja a imagem do efeito avalanche do DES:

E com isso eu fico por aqui, dando um fim nessa jornada de criptografia com o S-DES. Aguarde o próximo texto com conteúdos novos!

Se esta gostando dos textos não esqueça de compartilhar com seus amigos e conhecidos o texto e o blog.

Até a próxima!

Read More

Entendendo a criptografia - Parte 12

Criptografando com o S-DES

Seguindo com a série de criptografia, neste post vamos criptografar uma mensagem em texto claro com o algoritmo S-DES. No testo anterior vimos que o algoritmo necessita de subchaves, e vimos também o algoritmo de como são geradas.

Neste texto vamos ver como funciona a função complexa (fK) do algoritmo S-DES, e no próximo post, vamos fazer o processo completo da criptografia pelo algoritmo.

A função complexa tanto do DES quanto do S-DES é similar, a diferença está no número de rodadas. Veja abaixo o conteúdo, de uma forma simplificada, da função complexa.

As operações são similares as que vimos no algoritmo de geração de subchaves, então não tem necessidade de explicar novamente cada uma das operações.

O algoritmo representado na imagem é o DES, que possui 16 rodadas, chaves de 56 bits e blocos de 64 bits. Sabemos que no caso do S-DES temos apenas 2 rodadas. Caso não se lembra confira a imagem abaixo do S-DES:

Pode-se ver no algoritmo que a primeira rodada é onde a chave K1 entra, e a segunda rodada onde a chave K2 entra.

Se expandirmos a função fK temos as seguintes operações:

Na imagem acima podemos ver a Permutação Inicial (IP), quais operações compõe o fK (E/P, S0, S1, P4 e XOR),  o funcionamento do SW, uma segunda função fK com a segunda chave, e por fim a Permutação Final (IP -1).

As caixas E/P, S0, S1 e P4 funcionam do mesmo modo que as caixas P10, P8 e LS-1 do texto anterior.

Veja abaixo a organização das caixas:

As caixas E/P e P4 são simples, como as outras já apresentadas. Basta substituir a entrada de acordo com a ordem apresentada na imagem acima. Por exemplo, se recebermos como entrada na caixa E/P o número (binário) "1101", na saída teremos os bits dispostos de acordo com a imagem do E/P. Neste caso seguiremos a ordem 4º bit, 1º bit, 2º bit, 3º bit, 2º bit, 3º bit, 4º bit e por fim o 1º bit novamente. Neste caso a saída seria "11101011".

Já no caso da caixa S0 e S1, comumente chamadas de Caixas-S, são um pouco diferentes. A entrada da caixa-S é sempre 4 bits. O primeiro e o último bit representam a linha na matriz e o segundo e o terceiro bit representam a coluna da matriz. O resultado das coordenadas em decimal representa a saída da caixa-S, que deve ser convertido em binário.

Vamos a um exemplo. Vou usar aqui como entrada da caixa S0 o número "1010". Sabendo que o primeiro e quarto bit formam a linha (1º = 1, 4º = 0, ou seja, 10 binário = 2 decimal), e o segundo e terceiro formam a coluna (2º = 0, 3º = 1, ou seja, 01 binário = 1 decimal), temos as coordenadas da matriz.

O valor na posição (2, 1) é 2, ou seja, a saída da caixa S0 neste exemplo é 2 decimal = 10 binário.

Lembre-se que as linhas e colunas começam em 0 e não 1. As 4 linhas/colunas são 0, 1, 2 e 3.

Seguindo com o algoritmo, após a permutação inicial (P1) de 8 bits, os 8 bits são divididos em 2 blocos de 4 bits, a primeira metade vai para o fim do algoritmo para o XOR e a segunda metade para a caixa E/P e para o SW para a próxima rodada. A saída de 8 bits do E/P passa por um XOR com a primeira subchave e seu resultado é dividido e 2 blocos de 4 bits que entrarão nas caixas-S S0 e S1.

Os 2 blocos de 2 bits como saída das caixas-S entram na caixa P4. O resultado de 4 bits da saída de P4 passa por um XOR com a primeira parte do bloco que foi dividido na permutação inicial (IP), que ainda não tinha sido usado.

A saída do XOR e o segundo bloco de 4 bits da permutação inicial entram no SW, que inverte a ordem das entradas e usa na segunda rodada da função complexa.

Após realizar novamente as operações da função complexa, sua saídas vão para a permutação final (IP -1) e a saída desta permutação é o texto cifrado.

Neste caso a teoria é muito mais difícil que a prática, mas a teoria é necessária. Caso não tenha entendido alguma coisa, releia e acompanhe o texto com as imagens de referência, seguindo o fluxo do algoritmo.

No próximo texto vamos fazer todo o processo de criptografia, usando as subchaves que criamos no texto anterior.

Caso não tenha entendido alguma coisa poste sua dúvida aqui no post ou no grupo do Facebook que responderei e explicarei novamente se for necessário.

Read More

Entendendo a criptografia - Parte 11

Gerando subchaves com S-DES

Vamos então a uma prática usando o algoritmo Simplified DES.

O DES é um algoritmo complexo demais para se trabalhar neste primeiro momento, então estamos usando o S-DES. A imagem abaixo é a mesma do post passado, coloquei ela aqui apenas para refrescar a memória.

Vimos no texto passado, que nesta imagem, K1 e K2 representam chaves. Vamos ver hoje que essas chaves são na verdade subchaves derivadas da chave usada na entrada. Na imagem acima vemos uma chave de 10 bits na entrada do algoritmo. Essa chave passa por diversas operações e produz como saída 2 subchaves.

Para facilitar a explicação vamos esquecer completamente das partes de cifragem e decifragem. Na imagem abaixo temos as mesmas operações da geração das subchaves da imagem acima, mas sem o resto do algoritmo.

Entre as duas imagens a única diferença de nomes que pode confundir é o LS-1 e o LS-2, que são o Shift da primeira imagem.

Só para lembrar também, os algoritmos usados atualmente tem blocos muito maiores que este que estamos usando para aprender. Aqui, blocos de 8 bits com chaves de 10 bits estão sendo usados.

Agora vamos ver o que cada uma dessas caixinhas quer dizer:

OK! Essas caixinhas tem números, mas o que isso realmente quer dizer? Simples, essas 3 caixinhas são operações de substituição. Estes números representam a posição do bit que será substituído. Vamos a prática que é mais fácil de entender.

Para esse e futuros exemplos com o S-DES vamos usar como chave os bits "1001101011". Muito importante! Lembre-se desse número, pois vamos usar ele como chave daqui para frente. Também é importante ressaltar que estamos trabalhando com binário, e é bom você ter uma noção disso para poder seguir em frente.

Agora com nossa chave de 10 bits em mãos vamos a geração de subchaves. Começando de cima para baixo, a primeira caixinha que passamos com os 10 bits é a P10. Vamos então fazer a substituição de acordo com a tabela acima do P10.  Devemos colocar os bits de nossa chave na ordem mostrada ali, ou seja, 3º bit, 5º bit, 2º bit, e assim por diante.

Ao passar pelo P10 nossa chave deve virar "0101111100" se você fez as operações corretamente.

Feito isso o próximo passo são duas caixas LS-1. Pode-se interpretar pela imagem que a chave de 10 bits é dividida em 2 chaves de 5 bits e cada uma passa por uma caixa diferente.

Fazendo o mesmo tipo de substituição, mas dessa vez usando a caixa do LS-1, vamos ter "10110" de um lado e "11001" do outro.

O próximo passo pode ser um pouco mais complicado de entender. Se você olhar para a imagem do algoritmo de geração de subchaves, temos que fazer 2 coisas agora, alimentar o P8 com o resultado das caixas LS-1 e "ao mesmo tempo" encaminhar estes resultados para a LS-2. Vamos fazer primeiro a caixa do P8.

Até aqui temos "10110" e "11001". Vamos passar isso pela caixa P8 e como resultado obter "11110010". De acordo com a imagem do algoritmo, este resultado é a primeira subchave, aqui chamada de K1. Note que as subchaves tem 8 bits e não 10 bits.

Agora sim vamos para as caixas LS-2 com as duas saídas de LS-1. Neste caso a caixa que usaremos é a mesma de LS-1, já que é a mesma operação. Vamos obter como resultado "01101" e "10011".

Passando isso para a próxima caixa, a P8, vamos ter na saída "11000111", nossa segunda subchave K2.

Guarde a chave e as subchaves para o próximo texto, que vamos cifrar um pequeno bloco de 10 bits com o S-DES.

Read More

Entendendo a criptografia - Parte 10

Data Encryption Standard - DES

O algoritmo DES era inicialmente um projeto da IMB, chamado de LUCIFER, e olhem só, o projeto era dirigido por ninguém mais ninguém menos que Horst Feistel, nome familiar? :)

Como já comentei diversas vezes antes, a maioria destes algoritmos mais famosos tem seu código fonte público. Normalmente estes algoritmos usados hoje em dia são os ganhadores, ou os que mais se destacaram nas seleções do NIST dos projetos para um padrão nacional de criptografia, obviamente nos Estados Unidos, mas que foi amplamente adotado e teve presença mundial (ainda tem em alguns lugares).

A IBM então enviou seu projeto LUCIFER para a seleção do NIST, que na época se chamava NBS, estamos falando lá dos anos 70. O projeto foi o escolhido para se tornar o padrão nacional de criptografia para criptografar informações e documentos menos sigilosos.

O projeto foi muito criticado, várias suspeitas de enfraquecimento do algoritmo foram levantadas. Não querendo entrar em teorias da conspiração ou assuntos de espionagem (o que já é tecnicamente público) mas já entrando, no desenvolvimento do DES a NSA convenceu a IBM de que a chave poderia ser bem menor. Outra modificação que alegam é a alteração das Caixas-S do algoritmo.

Caixa-S é uma parte fundamental de um algoritmo de criptografia, a caixa-S é o bloco que mantém as operações do algoritmo.

Até teve um relato do Alan Konheim, desenvolvedor do DES:

"Enviamos as Caixas-S para Washington para avaliação, e quando voltaram estavam completamente diferentes."

Algum tempo depois, quando o poder computacional cresceu, se tornou simples quebrar o DES através de bruteforce. Para tentar resolver o problema foi criado o Triple DES, ou 3DES, mas outros problemas apareceram, o que fez o DES perder um pouco de espaço para outro algoritmo que veremos mais a frente, o AES.

Simplified DES

Agora sim vamos falar um pouco do algoritmo. Pare sua leitura e vá procurar no google sobre o algoritmo DES. Vou facilitar para você, apenas clique aqui.

É um algoritmo extremamente complexo né? Não temos como analisar tudo aquilo no ponto que estamos aprendendo como funciona a coisa. Para facilitar para todo mundo, inclusive seus alunos, o professor Edward Schaefer criou uma versão simplificada do DES, o S-DES. Com ele seus alunos poderiam estudar um algoritmo de criptografia de verdade e atual de uma forma mais simples. A funcionalidade básica é a mesma, mas o tamanho das chaves e blocos é menor para simplificar como o próprio nome já diz.

Este algoritmo usa blocos de 8 bits e chave de 10 bits para produzir um texto cifrado de 8 bits. É claro que com isso o algoritmo seria quebrado em segundos, por isso ele é apenas usado para questões de estudo.

Vamos agora dar uma olhada em como ficou o DES neste modelo simplificado:

Algumas coisas da imagem já vimos em textos passados, como por exemplo o uso de chaves (K1 e K2 nesse exemplo), algumas pode-se deduzir como entrada e saída, e algumas vou explicar. Não se preocupe se a explicação agora for superficial e não ajudar muito, nos próximos textos vamos ver na prática isso "funcionando" para ter uma noção do que é cada coisa.

IP = Permutação inicial
Fk = Função complexa (função necessária de acordo com a cifra de Feistel)
SW = Permutação simples
P10 = Permutação com 10 bits
P8 = Permutação com 8 bits
Shift = Substituição
IP-1= Permutação final ou permutação inicial inversa

Então aguardo você para o próximo texto para brincarmos um pouco com o algoritmo S-DES.

Até a próxima!

Read More