Tópico 3

Técnicas Clássicas de Criptografia

Técnicas clássicas de criptografia. Definições. Modelo

de cifra simétrica. Requisitos. Criptoanálise. Ataques.
Técnicas de substituição. Cifras de transposição. Cifras
combinadas. Máquinas criptográficas (rotor).
Esteganografia.
Sistemas Criptográficos

Técnicas que auxiliam a

implementação dos serviços de
segurança, principalmente os serviços
de confidencialidade, de integridade,
de autenticação, de irretratabilidade, e
de auditoria.
 Sistemas Criptográficos

Sistema criptográfico (SC) pode ser definido como uma quíntupla

de objetos:
SC = < M, C, K, {Ee}, {Dd}>, onde
M é o conjunto de textos legíveis
C é o conjunto de textos cifrados
K é o conjunto de chaves
Ee é o conjunto de funções Ee: M->C (funções de encriptação)
Dd é o conjunto de funções Dd: C->M (funções de decifração)
e, d é o chamado par de chaves
 Alguns termos básicos

texto claro: mensagem ou dados originais

texto cifrado: mensagem embaralhada, produzida como
saída.
cifra – algoritmo para transformar texto claro em cifrado
chave – informação usada na cifra, conhecida somente pelo
remetente e pelo destinatário
cifrar (criptografar) - converter texto claro em cifrado
decifrar (decriptografar) – recuperar um texto claro a partir
do texto cifrado
criptografia – estudo dos princípios e métodos da criptografia
criptoanálise (quebra de código) – estudo dos princípios e
métodos para decifrar um texto criptografado sem o
conhecimento da chave
criptologia – abrange as áreas de criptografia e criptoanálise
 Algorítmos Básicos (Blocos)

Criptografia simétrica (encriptação,

decifração)
Criptografia assimétrica (encriptação,
decifração)
Hash
MAC (message autentication code)
Geração de números aleatórios
Geração de chaves simétricas
Geração de chaves assimétricas
Troca de chaves
Criptografia Simétrica ou Clássica
Operações de Cifrar e Decifrar
Criptografia Simétrica
Operações de Cifrar e Decifrar
Algorítmos de HASH (Resumo)
Algoritmos MAC
Message Autentication Code
0

Geração de Números Aleatórios

1

Geração de Chaves Simétricas

2

Geração de Chaves Assimétricas

3
Particionamento de Chaves
Criação de Chaves
4
Particionamento de Chaves
Recuperação de Chaves
5

Criptologia
6

Criptologia

estudo dos princípios, métodos e

meios de ocultar informações.
7

Criptografia

Ciência que permite tornar

incompreensível uma informação, de
forma a permitir que apenas pessoas
autorizadas, consigam decifrá-la e
compreendê-la.

Conjunto de técnicas que permitem

ocultar informações
8

Criptografia

Um sistema de criptografia é caracterizado por:

Tipo de operações de criptografia usadas
substituição / transposição / produto
Número de chaves usadas
Chave única ou privada / duas chaves ou chave pública
Modo pelo qual o texto claro é processado
bloco / fluxo
9

Criptoanálise e Ataque
Criptoanálise é a ciência de recuperar
uma determinada informação
criptografada, sem possuir autorização,
através de um ataque.
ciência que abrange os princípios,
métodos e meios para se chegar a
decifração de um criptograma (cifra,
ciphertext).
Tem por objetivo a recuperação da
chave, além da mensagem.
Ataque é uma tentativa de criptoanálise.
Técnicas Gerais:
- Ataque criptoanalítico
0

Ataques criptoanalíticos
apenas texto cifrado
somente algoritmo e texto cifrado conhecidos, é
estatístico, conhece ou pode identificar texto claro
texto claro conhecido
texto claro e texto cifrado conhecido/suspeito
texto claro escolhido
seleciona o texto claro e obtém texto cifrado
texto cifrado escolhido
seleciona texto cifrado e obtém texto claro
texto escolhido
seleciona o texto claro ou cifrado para criptografar
ou decriptografar
1
Ataque por força bruta
é sempre possível experimentar todas as
chaves
quase sempre é um ataque básico,
proporcional ao tamanho de chave
pressupõe conhecer/reconhecer texto claro
Tamanho da Número de chaves Tempo necessário para Tempo necessário para106
chave (bits) Keysalternativas decriptografias/µs
1 decriptografia/s

32 232 = 4.3 109 231 µs = 35.8 minutos 2.15 milessegundos

56 256 = 7.2 1016 255 µs = 1142 anos 10.01 horas

128 2128 = 3.4 1038 2127 µs = 5.4 1024 anos 5.4 1018 anos

168 2168 = 3.7 1050 2167 µs = 5.9 1036 anos 5.9 1030 anos

26 caracteres 26! = 4 1026 2 1026 µs = 6.4 1012 anos 6.4 106 anos
(permutação)
2
Segurança Incondicional /
Computacional
segurança incondicional
não importa a potência computacional ou o tempo
que o oponente tenha disponível, o texto cifrado
não poderá ser decodificado se o texto cifrado
gerado pelo esquema não tiver informações
suficientes para determinar exclusivamente o texto
claro correspondente
segurança computacional
devido à limitação de recursos (por exemplo, o
tempo necessário para os cálculos ser maior que a
idade do universo), a cifra não poderá ser
decodificada
3

Como funciona a criptografia

4
Como funciona a criptografia
(2)

Processo de transformação, através de uma chave

secreta, de informação legível (mensagem), em
informação ilegível.
Somente os indivíduos que conhecem a chave
secreta tem capacidade de decifrar o criptograma e
recriar a mensagem
A dificuldade de decriptação reside em
descobrir a chave secreta e não o segredo do
método utilizado ( algorítmo de criptografia)
5

Classificação da Criptografia

Quanto ao número de chaves utilizadas

Simétricas
Assimétricas

Quanto à forma de processamento

Por bloco (bloco a bloco)
Por stream (bit a bit)
6

Criptografia Simétrica

Simétrica ou convencional, é quando o inverso

do algoritmo que cifra uma mensagem é utilizado
para decifrar com a mesma chave empregada na
operação de cifrar.
EK(M) = EK-1(C) ,
onde EK-1(C) = DK(C)
7

Criptografia Simétrica (2)

Utiliza uma única chave

Os parceiros devem ter conhecimento da chave
Ninguém mais deve conhecê-la
8

Criptografia Assimétrica

assimétrica ou de chave pública, é quando se

utilza uma chave para encriptar e sua chave
parceira para decifrar a mensagem.
Ee(M) = Ed-1(C) ,
onde Ed-1(C) = Dd(C)
9

Criptografia Assimétrica (2)

Utiliza duas chaves parceiras,

normalmente ...
Uma privada, apenas o dono a conhece
Uma pública, suposto que todos possam conhecê-
la
0

Processamento por bloco

Processa um bloco de elementos por vez,

produzindo assim um bloco de saída a cada vez.

Pode ser necessário completar o bloco com

sequências numéricas, utilizando métodos de
preenchimento

mais utilizado
1

Processamento por stream

Processa os elementos de entrada de forma

contínua (bit a bit, ou byte a byte)

maior custo computacional

util em mensagens pequenas

2

Onde a criptografia não ajuda

Ataques destrutivos
Destruição de mensagens
Informações não encriptadas
Antes da encriptação / depois da decifração
Chaves ou senhas roubadas ou perdidas
Traidores
Criptoanálise realizada com sucesso
3

Criptografia simétrica

também chamada de criptografia

convencional ou criptografia de chave única
remetente e destinatário compartilham uma
chave comum
todos os algoritmos de criptografia clássicos
são chaves privadas
antes da criação da chave pública, nos anos
1970, era o único tipo de criptografia em
uso
esse continua sendo, de longe, o mais usado
dos dois tipos de criptografia
4

Modelo de cifra simétrica

5

Requisitos

há dois requisitos para o uso seguro da criptografia

convencional:
um algoritmo de criptografia forte
Uma chave secreta conhecida somente pelo emissor e pelo
receptor
matematicamente, temos:
Y = EK(X)
X = DK(Y)
pressupõe que o algoritmo de criptografia seja
conhecido
implica um canal seguro de distribuição de chave
6

Cifras de substituição clássicas

em que as letras de texto claro são substituídas por outras
letras ou por números ou símbolos

ou se o texto claro for visto como uma seqüência de bits,

então a substituição envolve substituir padrões de bits de
texto claro por padrões de bits de texto cifrado.
7

Cifra de César

cifra mais antiga de que temos conhecimento

criada por Júlio César
usada primeiramente para fins militares
substitui cada letra pela que fica três posições adiante no alfabeto
exemplo:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
8

Cifra de César
pode definir transformação como:
a b c d e f g h i j k l m n o p q r s t u
v w x y z
D E F G H I J K L M N O P Q R S T U V W X
Y Z A B C
matematicamente, dá a cada letra
uma número
a b c d e f g h i j k l m n o p q r s t u v
w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22 23 24 25

os algoritmos de César são:

c = E(p) = (p + k) mod (26)
p = D(c) = (c – k) mod (26)
9

Criptoanálise da cifra de César

tem somente 26 cifras possíveis

A mapeia para A,B,..Z
poderia experimentar somente uma por vez
uma procura por força bruta
dado o texto cifrado, experimenta somente
as letras deslocadas
precisa reconhecer quando há texto claro
por exemplo, decifrar "GCUA VQ DTGCM"
0

Cifra monoalfabética

não somente desloca o alfabeto

poderia embaralhar as letras
arbitrariamente
cada letra de texto claro mapeia para uma
letra de texto cifrado aleatória
assim a chave tem 26 letras de extensão

Claro: abcdefghijklmnopqrstuvwxyz
Cifrado: DKVQFIBJWPESCXHTMYAUOLRGZN

Texto claro: ifwewishtoreplaceletters

Texto cifrado: WIRFRWAJUHYFTSDVFSFUUFYA
1

Segurança da cifra monoalfabética

tem um total de 26! = 4 x 1026 chaves

com tantas chaves, você pode pensar que é segura
mas estará !!!ENGANADO!!!
o problema são as características da linguagem
2
Redundância de linguagem e
criptoanálise

as linguagens humanas são redundantes

por exemplo "th lrd s m shphrd shll nt wnt"
as letras não são utilizadas com igual
freqüência
em inglês o E é a letra mais usada
Seguida por T,R,N,I,O,A,S
outras letras como Z,J,K,Q,X são menos
freqüentes
faça tabelas com freqüências de letras
simples, duplas ou triplas para várias
linguagens
3
Freqüência das letras no texto em
inglês
4
Freqüência das letras no texto em
português
5

Uso em criptoanálise
conceito de chave – a substituição monoalfabética
de cifras não altera a freqüência relativa das letras
descoberta por cientistas árabes no século IX
calcula a freqüência de letras no texto cifrado
compara contagem/gráficos com os valores
conhecidos
se a cifra de César procura por por freqüências
maiores/menores
maiores em: A-E-I triplo, NO par, RST triplo
menores em: JK, X-Z
no sistema monoalfabético você deve identificar
cada letra
tabelas com as letras duplas/triplas mais comuns ajudam
6

Exemplo de criptoanálise

dado o texto cifrado:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
contamos a freqüência relativa das letras (veja o
texto)
suponha que P e Z são e e t
suponha que ZW é th e, portanto, ZWP é the
continuamos com o método de tentativa e erro até
obter:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow
7

A cifra Playfair

nem mesmo um grande número de chaves em uma cifra

monoalfabética garante segurança
um método para aumentar a segurança é criptografar letras
múltiplas
a cifra Playfair é um exemplo
foi inventada por Sir.Charles Wheatstone em 1854, mas
recebeu o nome de seu amigo, Barão de Playfair
8

Matriz do algoritmo Playfair

uma matriz 5x5 de letras, baseada em uma

palavra-chave
preenchida com as letras da palavra-chave (menos
duplicatas)
preenchemos o restante da matriz com outras
letras
exemplo com o uso da palavra-chave MONARCHY:
M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
9
Criptografando e
decriptografando
o texto claro é criptografado duas letras por
vez
se o par for composto por letras repetidas, insira um
filtro, como 'X’
se ambas as letras caírem na mesma linha, substitua
cada uma pela letra que fica à direita (fazendo o
mesmo do início até o final)
se ambas as letras caírem na mesma coluna,
substitua cada uma pela letra que fica abaixo
(novamente, fazendo o mesmo de cima até em
baixo)
caso contrário, cada letra de texto claro em um par
é substituída pela letra que se encontra em
sua própria linha e na coluna ocupada pela
outra letra de texto claro
0

Segurança da cifra Playfair

oferece segurança bem maior que a monoalfabética

uma vez que tem 26 x 26 = 676 diagramas
seriam necessárias 676 entradas em uma tabela de
freqüência para analisar (versus 26 entradas no
sistema monoalfabético)
e, correspondentemente, mais texto cifrado
foi amplamente utilizada por muitos anos
Por exemplo, pelos Estados Unidos e pela Grã- Bretanha na
Primeira Guerra Mundial
pode ser decifrada, com algumas centenas de
letras
uma vez que tem muito texto claro em sua
estrutura
1

Cifras polialfabéticas

substituição polialfabética de cifras

aumenta a segurança com o uso de
múltiplas cifras alfabéticas
dificulta a criptonálise exigindo mais
caracteres para se descobrir uma freqüência
uniforme
usa uma chave para selecionar que
caractere é usado para cada letra da
mensagem
usa cada um dos caracteres por vez
repete a partir do começo, após ter
alcançado o final da chave
2

Cifra Vigenère

a mais simples cifra de substituição

polialfabética
multiplica as cifras de César
a chave tem o tamanho de múltiplas letras K
= k1 k2 ... kd
a i-ésima letra especifica a i-ésima letra do
alfabeto a ser usada
usa um caractere por vez
repete o processo a partir do início após d
letras na mensagem
a decriptografia é feita em modo reverso
3

Exemplo de cifra Vigenère

escrevemos o texto claro

escrevemos a palavra-chave repetidamente sobre
ele
usamos cada letra-chave como uma chave da cifra
de césar
criptografamos a letra corrrespondente do texto
claro
exemplo usando a palavra deceptive:
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
4

Dicas

algumas dicas podem ajudar na

de/criptografia
uma Saint-Cyr Slide é um recurso manual
simples
um slide com caracteres repetidos
colocamos em linha o texto claro 'A' com a letra-
chave, por exemplo, 'C'
então lemos cada caractere mepeando para
palavra-chave
pode ser rodado para um disco de cifras
ou expandido para uma tabela Vigenère
5

Sistema de autochave
idealmente necessita de uma chave tão
longa quanto a mensagem
Vigenère propôs o sistema de autochave,
em que a palavra-chave é conectada à
mensagem como chave
conhecendo-se a palvra-chave é possível
recuperar-se as primeiras letras
use-as sobre o resto da mensagem
mas ainda possui a mesma característica de
freqüência para o ataque, por exemplo com
a chave deceptive:
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA
6

Chave de uso único

se for usada uma chave realmente aleatória,

tão longa quanto a mensagem, a cifra será
segura
também chamada One-Time pad
é indecifráfel, uma vez que o texto cifrado
não possui relação estatística com o texto
claro
uma vez que, para cada texto claro e
cada texto cifrado, existe uma chave que
mapeia uma à outra
e só se pode usar a chave uma única vez
problemas na geração e distribuição segura
de chaves
7

Cifras de transposição

agora considere as cifras clássicas de transposição ou

permutação
elas escondem a mensagem reordenando as letras
sem alterar as letras usadas
pode-se reconhecê-las, uma vez que têm a mesma freqüência
de distribuição que o texto original
8

Cifra rail fence

escreve o texto claro diagonalmente, em

determinado número de linhas
então é lido linha a linha
por exemplo, a mensagem: meet me after the
toga party, poderia ser escrita assim:

m e m a t r h t g p r y
e t e f e t e o a a t
resultando no texto cifrado:
MEMATRHTGPRYETEFETEOAAT
9
Cifras de transposição de
linhas
uma transposição mais complexa
escreve letras em uma mensagem,
dispostas em linhas sobre um número
específico de colunas
então reordena as colunas, de acordo com
alguma chave, antes da leitura das linhas
chave: 3 4 2 1 5 6 7
Texto claro: a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Texto cifrado: TTNAAPTMTSUOAODWCOIXKNLYPETZ
0
Cifras de produto

as cifras que usam substituição ou

transposição não são muito seguras por
causa das características de linguagem
assim, procure usar várias cifras em
sucessão, para dificultar, porém:
duas substituições resultam em uma substituição
mais complexa
duas transposições resultam em uma transposição
mais complexa
mas uma substituição seguida de uma transposição
resulta em uma cifra muito mais forte
esse é um ponto de ligação entre as cifras
clássicas e as modernas
1

Máquinas de rotor

antes das cifras modernas, a máquinas de rotor

eram as mais comuns cifras complexas em uso
amplamente usadas na Segunda Grande Guerra
Mundial
Enigma (Alemanha), Hagelin (Aliados), Purple (Japão)
implementavam uma muito complexa e variável
substituição de cifras
usavam uma série de cilindros, cada qual fazendo
uma substituição, a qual era rotacionada e mudada
após a criptografia de cada letra
cada três cilindros tinham 263=17576 alfabetos
2

Máquina de rotor Hagelin

3
Esteganografia

uma alternativa para a criptografia

esconde a existência da mensagem
usada somente como subconjunto de letras/palavras dentro
de uma mensagem maior, marcado de alguma forma
usando tinta invisível
escondida em LSB, em imagem gráfica ou arquivo sonoro
tem desvantagens
exige muito esforço para esconder poucos bits de informação
4

Resumo

Vimos:
Técnicas clássicas e terminologia de cifras
Cifras de substituição monoalfabética
Criptoanálise usando freqüência de letras
A cifra Playfair
Cifras polialfabéticas
Cifras de transposição
Cifras de produto e máquinas de rotor
Esteganografia