Criptoanálise
Gabriel Leite Baptista da Silva

História



Introdução



Criptografia e a Criptoanálise
Criptoanálise nas Guerras
Propósito
Cifras e Códigos
Criptoanálise


Quebrando Cifras
Tipos de Cifras



Famosos Ataques




Substituição
Transposição
Ataque do Aniversário
Conclusões
Perguntas Sobre Criptoanálise
Bibliografia
Criptografia e a Criptoanálise
 Primeira mensagem criptografada: 1900 a.C.
 Posteriormente, comunicação através de
mensageiros
 Cifra de Júlio César:
 Interceptação de Mensagens  Criptoanálise
Criptoanálise nas Guerras
 1917: Mensagem Alemã interceptada pela
inteligência Britânica
 Grã-Bretanha na 2ª Guerra: 30,000
Criptoanalistas
 Vitória Americana na Ilha de Midway graças à
Criptoanálise
Propósito
 Estudo de linguagem extintas
 Casos de sucesso:

1587: Mary, Rainha da Escócia
 Governos criam entidades especializadas:


GCHQ (Government Communications
Headquarters)
NSA (National Security Agency)
 Fortalecimento da Criptografia:

Transações feitas através da rede
Cifras e Códigos
 Código:



Frases são substítuidas por 4 ou 5 letras,
encontrados em um livro de código
Podem existir vários códigos para 1 palavra
Códigos são cifras, mas nem todas as cifras
são códigos
 Cifras:

Não fazem uso do livro de código
Quebrando Cifras
 Quebra:


Encontrar uma fraqueza na cifra
Número de testes menor do que a força bruta
 Passos:



Identificação
Quebra
Configuração
Cifras de Substituição
 Quebra da cifra de Júlio César:


Escrever as 26 posições deslocadas da Cifra
Filtrar as inteligíveis
 Aumentando a complexidade:
 Espaços são substituídos por uma letra
menos frequente
Cifras de Substituição
 Quebra:
TLZQVTVXDQVQHKTLTFZQEQGVRTVKTRTLVRGOL
VRGVEXKLGVRTVEGDHXZQEQGVRQVXYKP
Mapa de Frequências
TLZQ T XDQ QHKTLTFZQEQG RT KTRTL RGOL RG
EXKLG RT EGDHXZQEQG RQ XYKP
Conhecimentos Linguísticos
ESTA E UMA APRESENTACAO DE REDES DOIS DO
CURSO DE COMPUTACAO DA UFRJ
Cifras de Transposição
 Cifra:


Possui uma Chave
A cifra é escrita em uma tabela:


3 1
O A
Número de colunas = Chave
Removida coluna por coluna segundo chave
5
T
2 4
A Q
U E S E R
A N O D I
A D N A H
O R A H X
O ATAQUE SERA NO DIA D
NA HORA H
AENDR AEDAH OUAAO
QRIHX TSONA
Cifras de Transposição
 Quebra:
A
A
O
Q
T
 5-2; 1-5
E
E
U
R
S
 3-1; 2-4
N
D
A
I
O
D
A
A
H
N
R
H
O
X
A
Linha
Análise de
Dígrafos
Dígrafos
Colunas
1 ao-ta-to
1-3;5-1;5-2;5-3
2 ue-re-ru-se-es
3-1;3-2;4-1;4-2;4-3;5-1;5-2;1-5
3 na-ni-no-di-an
1-3;1-4;1-5;2-4;3-1
4 da-na
1-2;1-3;5-2;5-3
5 ro-ra
1-3;1-5
Ataque do Aniversário
 Baseado no Paradoxo do Aniversário
Ataque do Aniversário
 Explora a resistência a colisão de uma
função Hash:

Para qualquer par (x, y) deve ser impossível
encontrar h(x) = h(y)
 P(n, k) = 1 – P(A’)
Conclusões
 Poder benéfico da Criptoanálise:


Desenvolvimento das comunicações
Decisiva em guerras
 Criptoagrafia e Criptoanálise andam juntas:

Novas técnicas de Criptografia requerem
novas quebras e vice-versa
Perguntas
 O que é considerada uma quebra de cifra?
Uma quebra de cifra acontece quando o número de
testes necessários para quebrar aquelae tipo de cifra
é menor do que o número de teste que seriam
necessários se utilizassemos o método da força
bruta.
 A cifra de Júlio César é considerada de qual
tipo? Porque?
A cifra de Júlio César é considerada uma cifra de
substiuição pois ela substitui os caracteres pelo seu
3º sucessor no alfabeto.
Perguntas
 Dada uma letra com a maior frequência em
uma Cifra de Substituição, o que podemos
suspeitar dela?
Como os espaços representam 15 a 20% da
mensagem, podemo suspeitar de que essa letra é a
representação do espaço.
 O que é uma Cifra de Transposição?
Uma cifra de transposição é aquela que “rearruma”
os caracteres da mensagem original de acordo com
algum sistema específico.
Perguntas
 O que é o Paradoxo do Aniversário?
O Paradoxo do Aniversário consiste na probabilidade
de, numa coleção randômica de n pessoas, duas
pessoas fazerem aniversário no mesmo dia.
Leituras Recomendadas
 Criptoanálise:

Churchhouse, “Codes and Ciphers: Julius
Ceasar, the Enigma and the Internet”
 Ataque do Aniversário

Julio Heitor Silva Nóbrega, “Segurança em
Redes de Computadores: Funções de Hash
em Autenticação, Paradoxo do Aniversário e
aplicações no protocolo WEP”