criptografia - UnB

Prévia do material em texto

1
Criptografia
Prof. Ricardo S. Puttini, MSc
Departamento de Engenharia Elétrica
Universidade de Brasília
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Conteúdo
• Princípios de Teoria da Informação
• Introdução aos Sistemas Criptográficos
• Criptografia Simétrica
• Criptografia Assimétrica
• Funções de Condensação (Hash Functions) 
• Infra-estrutura de Chaves Públicas (ICP)
2
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Princípios de Teoria da Informação
• O problema da codificação consiste na busca de 
formas eficientes de representação da informação:
– Economia de símbolo utilizados (compressão);
– Proteção contra erros (detecção/correção de erros);
– Serviços de segurança da informação (criptografia).
• Teoria da Informação: construção de modelos 
matemáticos para linguagem.
• Linguagem: conjunto de características da 
informação que se deseja codificar.
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Quantidade de Informação
• Teoria de Shannon (1948): modelo probabilístico para a 
linguagem.
• Quantidade de Informação
I(E) = -log2 p(E)
• A base 2 do logaritmo permite que a quantidade de 
informação seja medida em bits
• Exemplos:
– E1 = “o sol nascerá amanhã”;
p(E1) = 1 ® I(E1) = 0
– E2 = “ao lançar-se a moeda, obteve-se cara”;
p(E2) = 0,5 ® I(E2) = 1 (bit)
3
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Princípios de Teoria da Informação
• Exemplo: Considere uma fonte que gere símbolos 
0’s e 1’s de forma independente e equiprováveis. 
Então, a quantidade de informação obtida pelo 
conhecimento de “n” bits de uma seqüência gerada 
por essa fonte é:
• Isto é, a quantidade de informação contida em 
uma seqüência de n bits é igual n bits.
nSI nn =÷ø
ö
ç
è
æ-=
2
1log)( 2
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Entropia
• Entropia é a quantidade de informação contida em um 
evento qualquer, i.e. a quantidade de informação média de 
um evento típico.
• É uma medida da incerteza associada a uma ocorrência de 
um evento: quanto maior a entropia, maior a incerteza 
associada ao evento.
• Para uma v.a. X, que pode assumir um número finito de 
valores com probabilidades p1, p2, ..., pn, tem-se a seguinte 
definição de entropia:
å
=
-=
n
i
ii ppXH
1
2 )(log)(
4
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Entropia
• Entropia conjunta de um vetor X = [A,B], onde A e B são 
v.a. assumindo um número finito de valores:
• Note que:
å ====-==
ji
jiji bBaApbBaApBAHXH
,
2 ),(log),(),()(
)()(),( BHAHBAH +£
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Entropia
• Dado duas v.a. X e Y, a incerteza acerca de X, dado que 
uma ocorrência particular de Y é conhecida pode ser 
expressa como:
• Define-se entropia condicional, H(X/Y), ou equivocação 
de X dado Y por:
• Assim, a entropia condicional representa a incerteza em 
relação a uma ocorrência de X, quando uma ocorrência de 
Y é conhecida.
å ====-==
i
ii yYXXpyYXXpyYXH ),(log),()/( 2
å ==-=
j
jj yYpyYXHYXH )()/()/(
5
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Propriedades da Entropia
)(log)(log)( 2
1
2 nppXH
n
i
ii £-= å
=
)(),()/(
)(),()/(
XHYXHXYH
YHYXHYXH
-=
-=
III) Se X e Y são v.a. independentes:
)()(),(
)()/(
)()/(
YHXHYXH
YHXYH
XHYXH
+=
=
=
I)
II)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Informação Mútua
• É a quantidade de informação que a ocorrência de um evento Y = y
fornece a respeito da ocorrência de um evento X = x:
• O valor esperado de I(x,y) é definido como a informação mútua entre 
X e Y:
• Note que:
)]/(log[)(log 
)/()(),(
22 yYxXpxXp
yxIxIyxI
==--=-
=-=
å ===
ji
jiji yxIyYxXpYXI
,
),()/(),(
),()()(),( YXHYHXHYXI -+=
6
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelos de Linguagens e Fontes de Texto
• Associa-se um alfabeto de m-letras,A = {a0, a1, an-1}, ao 
conjunto dos inteiros módulo m:
ai « i; i Î Zm = {0,1,..., m}
• Conjunto de todos os n-gramas de A, Zmn , forma um 
novo alfabeto de mn símbolos.
• Texto: um n-grama sobre um alfabeto Zm. 
• Fontes de texto: modelo capaz de produzir textos 
pertencentes a uma determinada linguagem.
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelos de Linguagens e Fontes de Texto
• Fonte de texto de primeira ordem: considera a freqüência 
relativa dos caracteres de uma linguagem.
– Não leva em conta a dependência inter-símbolos.
• Fonte de texto de segunda ordem: considera a freqüência 
relativa de digramas.
• Fonte de texto de ordem superior: considera a freqüência 
relativa de n-gramas.
• Fontes Markovianas: considera as probabilidades de 
transição inter-simbolos.
7
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Distribuição de Probabilidades de 1-gramas em 
Português
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Distribuição de Probabilidades de 2-gramas em Português (1/2)
8
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Distribuição de Probabilidades de 2-gramas em Português (2/2)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Probabilidades de Transição para o Português, em % (1/2)
9
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Probabilidades de Transição para o Português, em % (2/2)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Entropia e Redundância de Fontes de Texto
• Uma vez admitido o modelo estatístico de uma linguagem, 
pode-se calcular a entropia da linguagem
– Entropia, usando um modelo de fonte de texto de primeira ordem:
– Entropia, usando um modelo de fonte de texto de segunda ordem:
 bits/letra 53,3),(log),(
2
1
2
,
2 =-=£ å jipjipHH
ji
portuguesportugues
 bits/letra 97,3log2
1 =-=£ å i
i
iportuguesportugues ppHH
10
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Entropia do Inglês (Shannon)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Dada uma fonte sobre um alfabeto Zm e entropia 
H, pode-se codificar textos produzidos por essa 
fonte em um código compacto, onde um n-grama 
típico pode ser codificado com l(n) letras de Zm.
• l(n) é o comprimento médio dos códigos 
necessário para representar um n-grama.
Entropia e Redundância de Fontes de Texto
m
nHn
2log
)( =l
11
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Define-se redundância de uma fonte como a diferença 
entre o número de símbolos utilizados em um n-grama, 
obviamente n, e o número médio mínimo de símbolos l(n) 
que poderiam ser utilizados por uma codificação mais 
apropriada:
• Estima-se normalmente que a redundância da língua 
inglesa seja de, aproximadamente, 40%.
• Shannon mostrou que, considerando-se efeitos mais 
amplos, a entropia do inglês se reduziria a 1bit por letra, o 
que equivale a uma redundância de cerca de 75%.
Entropia e Redundância de Fontes de Texto
m
HR
2log
1-=
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Introdução aos Sistemas Criptográficos
• Criptologia: estudo dos processos criptográficos. 
• Formada por duas disciplina:
– Criptografia: como projetar e construir de sistemas 
criptográficos
– Criptoanálise: como “quebrar” sistemas criptográficos.
12
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Serviços de segurança:
– Confidencialidade: confiança em que a mensagem 
possa ser lida apenas pelo receptor desejado
– Autenticação da Origem: garantia sobre quem originou 
a mensagem
– Integridade: confiança em que a mensagem não tenha 
sido modificada desde o momento da criação
– Não-retratação: quem originou a mensagem não pode 
negar tê-lo feito.
Introdução aos Sistemas Criptográficos
mai-04 Criptografia
Prof. Ricardo StaciariniPuttini
Introdução aos Sistemas Criptográficos
• Sistema Criptográfico Convencional
canal seguro
CIFRA DECIFRAM
C=EK(M)
M=DK(C)
canal
inseguro
KK
Criptoanalista
13
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Uma mensagem (M) é um n-grama de um 
alfabeto A
• O processo de cifração de m gera um 
criptograma (C), designado por c = E(M)
• Claramente, deve haver D(C) = D (E(M)) = m
• O processo de cifração pode ser visto como um 
conjunto de transformações E={En,1£n<¥}, 
En:Zmn ® Zmn
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Sistemas Criptográficos
– Família de transformações criptográficas 
E={EK,KÎK}, onde cada transformação é indexada por 
um parâmetro k, denominado chave criptográfica.
– Composto de uma tripla (M,K,C)
• M: espaço das mensagens
• K: espaço das chaves
• C: espaço dos criptogramas
14
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
M1
M2
M3
Mn
C1
C2
C3
Cn
EK1
EK2
EKn
cifração
decifração
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Criptoanálise
– Supõe-se sempre que o criptoanalista conhece
• Algoritmo;
• Linguagem do texto em claro;
• Contexto das mensagens (algumas mensagens são conhecidas).
– Ataques contra algoritmos criptográficos
• Ataque com mensagem conhecida;
• Ataque com mensagem escolhida;
• Ataque com criptograma escolhido;
• Ataque ao criptograma apenas.
– Segurança do algoritmo criptográfico:
• No mínimo, deve suportar ataques com mensagens conhecidas.
• Em geral, deve suportar ataques com mensagens/criptograma escolhido.
Modelo Estatístico de um Sistema Criptográfico
15
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Cifra de César (substituição simples):
– Cifração: Ci = E (K,Mi) = (Mi + K) mod m
– Decifração: Mi= D(K,Ci) = (Ci - K) mod m
• Exemplo: K=7, m = 27 (27 letras + espaço)
M = TROPAS
C = _YVWHZ
• Ataque com mensagem conhecida...
• Ataque com mensagem escolhida...
Modelo Estatístico de um Sistema Criptográfico
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Substituição mono-alfabética: cada letra do alfabeto da 
mensagem corresponde a uma letra do alfabeto do 
criptograma:
– chave = correspondência entre letras
– Exemplo: ABCDEFGHIJKLMNOPQRSTUVWVXYZ_
HZEVGVAJXK_MPNQFROIUBWSTYCLD
• Ataque com mensagem conhecida: qual o tamanho da 
mensagem para permitir revelar a chave completa?
• Ataque com mensagem escolhida...
Modelo Estatístico de um Sistema Criptográfico
16
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Dado um modelo estatístico para a linguagem que 
será a fonte de mensagens, as distribuições de 
probabilidade P(M) e P(K) permitem obter:
å
=
=
)(;,
)()()(
MECKM K
KPMPCP
å
=
=
)(;
)()(),(
MECK K
KPMPCMP
å
=
=
)(;
)()(),(
MECM K
KPMPCKP
)()(),( KPMPKMP =
)(
),()/(
CP
CMPCMP =
)(
),()/(
CP
CKPCKP =
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Função de Decisão: função que faça d(C) = M, se 
C = EK(M).
• Esta função deverá maximizar p(M/C)
17
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Ex1 - Cifra de César:
K=7, m = 27
M = TROPAS
C = _YVWHZ
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modelo Estatístico de um Sistema Criptográfico
• Obs1: o processo não destrói as estatísticas de 
n-gramas da linguagem do texto claro.
• Obs2: o espaço de chaves é pequeno, tornando um 
ataque por força bruta possível.
18
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Ex2: M = MANDE_TROPAS
C = THUKLG_YVWHZ
Modelo Estatístico de um Sistema Criptográfico
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Segredo Perfeito
• Equivocação da chave: H(K|C) (medida de quanto 
da chave é revelado pelo criptograma):
– Para um universo de mensagens M finito e distribuições 
de probabilidades de M e K independentes:
H(K|C)= H(M|C)+H(K|(M,C))
• Segredo perfeito: H(M|C)=H(M)
– Assim, p(M|C)=p(M)
– Ou, p(C|M)=p(C)
19
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Segredo Perfeito
• Uma condição necessária a um sistema 
criptográfico para ter segredo perfeito é que o 
espaço de chaves seja pelo menos tão grande 
quanto o espaço de mensagens
– Um sistema com |K|=|M|=|C| tem segredo perfeito sss
toda chave é usada com igual probabilidade, e para todo 
MiÎM e todo CjÎC existe um único KÎK, tal que 
EK(Mi)= Cj
– Ex: one-time pad
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Teorema da Equivocação da Chave
– H(M,C,K) = H(C) + H(K|C) + H(M|C,K)
– H(M,C,K) = H(K) + H(M|K) + H(C|M,K)
Mas, H(M|C,K) = H(C|M,K) = 0 e H(M|K) = H(M)
Assim: 
H(K|C)=H(K)+H(M)-H(C)
– Se H(K|C) = 0 => código quebrado.
– Se H(K|C) > 0 => duas ou mais chaves podem ter sido 
utilizadas para produzir o criptograma.
– As possíveis chaves extras são chamadas de espúrias.
20
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Chaves espúrias
• Seja KC o conjunto de chaves para o qual existem 
textos em claro que fazem sentido para a cifração
C=EK(M)
• O número esperado de chaves espúrias é: 
s=åCÎC p(C)| KC |-1
• H(K|C)= åCÎCp(C)H(K|C)
• H(K|C)£log2| KC |
• Usando a desigualdade de Jensen temos
• H(K|C)£log2(s+1)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Distância de Unicidade
• A recuperação da mensagem a partir de um dado 
criptograma é deve ser função da quantidade de 
criptograma disponível para análise.
• Para uma mensagem Mn de tamanho n (n-grama), e um 
criptograma Cn de tamanho n, tem-se:
– H(K|Cn) = H(K) + H(Mn) - H(Cn);
– H(M)»nHL=n(1-RL)log2m, onde RL é a redundância da linguagem 
e HL é a entropia da linguagem (Hport»2,209 bits/letra);
– H(K) = log2|K| (chaves são identicamente distribuídas);
– H(C)£nlog2m;
• Assim:
– H(K|C) ³ H(K) - nRLlog2m = log2|K| - nRLlog2m
– s ³ |K|/[m^(nRL)]-1
21
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Distância de Unicidade
• Na média será possível quebrar o sistema 
criptográfico quando o número de caracteres 
interceptados é suficiente para fazer o número 
médio de chaves espúrias igual a zero:
• U = log2|K|/(RLlog2m)
– Exemplo: cifra de substituição |K|=26! e RL=75%, 
estime s para n=25 e encontre a distância de unicidade
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Dificuldade Computacional
• Algoritmos precisam ser eficientes
• Força bruta: tentativa de todas as chaves possíveis
• Qualquer sistema (exceto segredo perfeito) pode ser 
quebrado Þ questão de dinheiro e tempo
• Chaves longas Þ maior segurança
– Cifração: O(N+1)
– Força bruta: O(2N+1)
• Ferramentas de criptoanálise:
– Hardware especial
– Máquinas paralelas
– ...
22
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Chave secreta x Algoritmo secreto
• Algoritmo secreto Þ dificuldade adicional
• Difícil de manter segredo se for largamente utilizado:
– Engenharia reversa
– Engenharia social
• Uso comercial: algoritmos publicados
• Uso militar: algoritmo mantido em segredo
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Ataques de Força Bruta
• Número de cifrações/seg: 1 milhão a 1 bilhão bits/sec
• 1999: chave de 56 bits quebrada em 22.5 h com 1800 chips 
(US$250.000,00) (245x109 chaves/s, veja eff.org); ajudado 
por distributed.net
• 1995: chave de 56 bits quebrada em 1 semana com 
120.000 processadores (US$6,7M)
• Loteria chinesa:
– Com máquinas que testam a uma taxa de um milhão de chaves por 
segundo, necessita-sede 64 segundos para quebrar o DES com um 
milhão dessas máquinas rodando em paralelo
23
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Segurança Computacional
• Difusão: a estrutura estatística herdada do texto 
em claro é difundida em uma estrutura estatística 
envolvendo longas combinações de letras no texto.
• Confusão: tem por objetivo fazer a relação entre as 
estatísticas de C e a descrição do conjunto de 
chaves muito complexa e intrincada.
– É implementada usando um conjunto de equações de 
cifrações não-lineares e múltiplos elementos de chave.
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia Simétrica
canal seguro
CIFRA DECIFRAM
C
M
canal
inseguro
KK
24
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Criptografia com ‘Chave Secreta’ ou ‘Simétrica’
• Mesma chave usada para cifrar e decifrar
Criptografia Simétrica
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Cifrador seqüencial
– Cifra uma seqüência de dados digitais um bit ou um 
byte por vez
• Cifrador de bloco
– Um bloco do texto em claro é tratado como um todo e 
usado para produzir um bloco cifrado de tamanho igual
Criptografia Simétrica
25
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cifradores Seqüenciais (Stream Ciphers)
• Modelo geral de um cifrador seqüencial
Fonte da 
mensagem
Gerador
de chaves
K, semente
+
Cifra
c = c1 + c2...
m = m1 + m2...
k = k1 + k2... One-time-pad: diferentes mensagens 
são cifradas por 
diferentes seqüências de chaves
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC4
• É um cifrador seqüencial com operações 
orientadas a bytes
• O algoritmo é baseado no uso de uma permutação 
pseudo-aleatória da chave
• O período do cifrador é aproximadamente 10100
• 8 a 16 operações de máquinas são necessárias por 
byte (cifrador rápido)
• É usado em protocolos de segurança como o SSL 
e o WEP
26
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Cifrador de cadeia de bytes (byte stream)
• Operação XOR aplicada entre uma seqüência pseudo-
randômica chaveada e os dados: a mesma para cifrar e 
decifrar
• Tamanho da chave variável: até 2048 bits
• Propriedade da RSA, exportável
• Tamanho do código = 1/10 de DES
• Velocidade = de 40 a 100 vezes DES
RC4
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC4
• Operações
– O estado interno do RC4 em um tempo t consiste de 
uma tabela de permutação St de 2n palavras de n bits e 
de dois ponteiros de n bits it e jt
– Estas palavras são usadas a cada estado para indexar a 
palavras diferentes tabela St, realizando sempre adições 
módulo 2n
27
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC4
• Ataques ao RC4
– Chave de 40 bits é fraca
– Ataque de VI conhecido e escolhido
– Ataque de invariância
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
A5
• A5/1 e A5/2 são cifradores seqüenciais para sigilo 
de conversações de telefones GSM
• Chaves de 64 bits geram seqüências de chaves de 
228 bits cada para cifração de um quadro
– Utiliza três registradores de deslocamento e uma 
transformação não-linear para gerar a seqüência de 
chave
28
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cifradores de bloco
• Blocos e chaves de tamanho fixo
– Não podem ser muito pequenos Þ segurança comprometida
– Não devem ser muito grandes Þ problemas de desempenho
– Tamanho típico de bloco: 64 bits
• Mensagem deve ser quebrada em blocos
• Texto em claro e texto cifrado não devem ter correlação 
– metade deve permanecer igual e metade diferente
– espalhamento de bits
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
1 2 3 4 5 6 7
Valor Inicial
Chave
Hora/
Data Banco Conta MontanteDepositante
1 2 3 4 5 6 7
Hora/
Data Banco Conta MontanteDepositante
1 2 3 4 5 6 7
Hora/
Data Banco Conta MontanteDepositante
Cifradores de Bloco
29
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
1 2 3 4 5 6 7
Valor Inicial
Chave
Hora/
Data Banco Conta MontanteDepositante
1 2 3 4 5 6 7
Hora/
Data Banco Conta MontanteDepositante
1 2 3 4 5 6 7
Hora/
Data Banco Conta MontanteDepositante
Cifradores de Bloco
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
1 2 3 4 5 6 7
Hora/
Data Banco Conta MontanteDepositante
Valor Inicial
• Cifragem em blocos, usualmente de 64-bit;
• Cifragem de blocos em cadeia (CBC) bastante comum;
• Em geral, mais lenta que a cifragem em fluxo.
Cifradores de Bloco
30
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cifradores de Bloco
• Conceitos gerais:
– Substituição (alfabeto permutado): mapeamento de um 
bloco de k bits em 2k blocos de k bits
– Transposição (permutação no bloco): mudança da 
posição de cada bit no bloco
– Round (rodada): combinação de substituição de grupos 
de bits com permutação, de tal forma que um bit da 
entrada possa afetar todos os bits da saída
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cifração de bloco
64 bits de entrada
8 bits 8 bits 8 bits 8 bits
S1 S2 S3 S8
8 bits 8 bits 8 bits 8 bits
64 bits intermediários
64 bits de saída
Permutação
Substituiçãoro
da
da
31
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rede Feistel
• Objetivos:
– Difusão
• Refere-se ao remanejamento dos bits na mensagem tal que 
qualquer redundância do texto em claro é espalhada sobre o 
criptograma
• Uma transposição em uma rodada é dita adicionar difusão
– Confusão
• Visa tornar o relacionamento entre a chave e o criptograma tão 
complexo quanto possível
• Uma substituição em uma rodada é dita adicionar confusão
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rede Feistel
• Parâmetros:
– tamanho do bloco
– tamanho da chave
– número de rodadas
– algoritmo de geração de subchaves
– função de rodada
32
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Texto em claro (2w bits)
+ F
K1
+ F
K2
E0 D0
E1
D1
Criptograma (2w bits)
En+1 Dn+1
w bits w bits
Rede Feistel
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
DES
• Publicado em 1977 pelo National Bureau of 
Standards
• Desenvolvido pela IBM (Lucifer)
• Chaves de 56 bits com paridade
• Blocos de 64 bits
• Fácil de implementar em hardware, lento em 
software (na época)
• Throughput superior a 20 Mbps em máquinas 
típicas
33
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Visão Geral do DES
• Permutação inicial
• Chave de 56 bits Þ 16 chaves por round de 48 bits
• 16 rodadas: 64 bits de entrada + 48 bits de chave ® 64 bits 
de saída
• Permutação final (inversa da inicial)
• Decifração: execução ao contrário com a chave na ordem 
inversa
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
DES: geração das chaves de rodadas
• Bits 8, 16, ..., 64 são de paridade
• Permutação inicial dos 56 bits válidos
• Divisão em dois grupos de 28 bits
• A cada rodada a chave é deslocada um ou dois bits à 
esquerda
• Permutação entre as metades esquerda e direita da chave
• Descarte de 8 bits por rodada
34
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
DES
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Uma Rodada DES
35
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Função F
entrada (32
bits)
S1E S2E S3E S4E S5E S6E S7E S8E
E
48 bits
S1K S2K S3K S4K S5K S6K S7K S8K
subchave 48 bits
S1 S2 S3 S4 S5 S6 S7 S8
S1I S2I S3I S5IS4I S6I S7I S8I
S1O S2O S3O S4O S5O S6O S7O S8O
P
saída (32 bits)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Ataques ao DES
• Força bruta: 0,5 MMY
• É necessário saber alguma informação sobre o 
texto em claro (ASCII, GIF, ...)
• Quebras documentadas usando hardwarededicado 
(custom chip ou lógica programável)
– www.eff.org
– distributed.net
• Pode-se usar cifrações repetidas para melhorar 
segurança
36
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Ataques ao DES
• criptoanálise diferencial
– Biham e Shamir, 92
– ataque de mensagem escolhida
– baseada em propagação de diferenças conhecidas nas 
mensagems em claro
– no caso do DES: são necessários 247 pares de 
mensagens em claro e criptogramas
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Ataques ao DES
• criptoanálise linear
– Matsui, 93
– ataque de mensagem conhecida
– procura encontrar expressões lineares para as caixas-S, 
estendendo estas expressões para a cifra inteira.
– no caso do DES: são necessários 247 pares de 
mensagens em claro e criptogramas
37
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modos de Operação do DES
• Electronic Code Book (ECB)
– Cada bloco de 64 bits de texto aberto é codificado 
independentemente, usando a mesma chave
– Transmissão segura de valores únicos (por exemplo, 
uma chave de criptografia)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Electronic Code Book (ECB)
38
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modos de Operação do DES
• Cipher Block Chaining (CBC)
– A entrada para o algoritmo de criptografia é o resultado 
da operação XOR do próximo bloco de 64 bits de texto 
aberto e o bloco precedente de 64 bits de texto cifrado
– Transmissão orientada a blocos de propósito geral
– Autenticação
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cipher Block Chaining (CBC)
39
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modos de Operação do DES
• Cipher Feedback (CFB)
– Processa-se j bits de cada vez. O texto cifrado 
precedente é usado como entrada para o algoritmo de 
criptografia para produzir uma saída pseudo-aleatória, 
que é, então, operada usando XOR com o texto em 
claro para produzir a próxima unidade de texto cifrado.
– Transmissão orientada a cadeias de propósito geral
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cipher Feedback (CFB)
40
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Cipher Feedback (CFB)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Modos de Operação do DES
• Output Feedback (OFB)
– Similar ao CFB, exceto que a entrada para o algoritmo 
de criptografia é a saída DES precedente
– Transmissão orientada a cadeias sob canal ruidoso (por 
exemplo, comunicação por satélite)
41
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Output Feedback (OFB)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Output Feedback (OFB)
42
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Geração de MICs
• Message Integrity Code
– Enviar somente o último bloco do CBC (resíduo CBC)
– Qualquer modificação no texto em claro modifica o 
resíduo CBC
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
3-DES
• Cifração-decifração-cifração (EDE):
– Duas chaves: K1, K2
K1 K2 K1
M E D E C
– Decifração
K1 K2 K1
C D E D M
43
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
3-DES
• Ataque
– encontro-no-meio (meet-in-the-middle)
• Decifra-se o resultado da segunda cifra e armazena-
se todas as possíveis entradas
• Cifra-se todos os textos em claro com a primeira 
cifra e compara-se com a tabela
• As coincidências são armazenadas como possíveis 
pares corretos de chaves
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
• International Data Encryption Algorithm 
(originalmente IPES)
• Autores: Lai e Massey da ETH Zurich, 1991
• Blocos de 64 bits
• Chaves de 128 bits
44
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
• Operações primitivas
– Å
– + mod 216
– Ä mod 216+1:
• Inversível: x Ä y = 1 mod 216+1
• Razão: 216+1 é primo
• Trata 0 como código para 216
45
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
• Expansão da chave:
– Chave de 128 bits ® 52 chaves de 16 bits
– Cifração e decifração usam chaves diferentes
– Geração da chave
• Divide-se os 128 bits em o subchaves de 16 bits
• Começando no bit 25, toma-se mais 8 chaves de 16 
bits
• Deslocamento de 25 bits e repetição da operação
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
• 17 rodadas:
– Pares e ímpares
– 64 bits ® 4 entradas de 16 bits: Xa, Xb, Xc, Xd
– Saídas: Xa´, Xb´, Xc´, Xd´
– Rounds ímpares usam quatros chaves de entrada: Ka, 
Kb, Kc, Kd
– Rounds pares usam somente 2 chaves: Ke, Kf
46
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
IDEA
Uma rodada
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5
• Características:
– Tamanho de palavra variável (w)
• valores permitidos: 16, 32, 64
– Número variável de rodadas (r)
• valores permitidos: 0, 1, …, 255
– Chave de tamanho variável (b)
• número de bytes permitidos: 0, 1, …, 255
– Exemplo: RC5-32/12/16
47
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5
• Operações
– Expansão de chave: t=2r+2
• S[0], S[1], …, S[t-1]
– Cifração
• adição módulo 2w
• ou exclusivo
• rotação circular à esquerda
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5 - Expansão da Chave
48
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5
Texto em claro (2w bits)
+ +
A B
Å Å
<<< <<<
+ +
LE0 RE0
S[0] S[1]
S[2] S[3]
LE1 RE1
Rodada 1
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5
+ +
Å Å
<<< <<<
+ +
LEr-1 REr-1
S[2r-2] S[2r-1]
S[2r] S[2r+1]
LEr REr
Rodada r
Texto cifrado (2w bits)
49
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5
• Modos de operação
– RC5 block cipher
• semelhante ao ECB
– RC5-CBC
– RC5-CBC-Pad
– RC5-CTS (ciphertext stealing mode)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RC5 - stealing mode
50
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
• Características
– operações realizadas no nível de byte
– tamanhos de chaves: 128, 192, 256 bits
– tamanhos de blocos: 128, 192, 256 bits
– número de rodadas: 9, 11, 13 (além de uma rodada 
extra no final)
– cada rodada composta de quatro passos: substituição de 
bytes, deslocamento de linhas, mistura de colunas, 
soma da sub-chave de rodada
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
51
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael - Substituição de Bytes
• Transformação definida por
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael - Substituição de Bytes
• Efeito da substituição de bytes
52
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael – Deslocamento de Linhas
• Deslocamentos definidos pela tabela abaixo, 
conforme o tamanho do bloco Nb
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Efeito do deslocamento de linhas
Rijndael – Deslocamento de Linhas
53
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael – Mistura de Colunas
• Transformação sobre as colunas
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael – Mistura de Colunas
• Efeito da mistura de colunas
54
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael – Soma de Sub-Chave de Rodada
• Operação XOR
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
• última rodada
– igual às anteriores sem a mistura de colunas
• geração das sub-chaves de rodada
– chave original expandida e seleção da chave de rodada
– expansão baseada
• em rotação 
• caixas-S da substituiçãode bytes 
• XOR com constante da rodada
55
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
• Modos de operação
– CTR (Counter mode): modificação do OFB
– OCB (Offset Codebook): permite autenticação
• Ataques
– Pouco susceptível às criptoanálises diferencial e linear
– Há dúvidas sobre sua resistência a ataques algébricos
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
• OCB
56
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Rijndael
• Counter Mode
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia Simétrica – Vantagens e Desvantagens
• Vantagens
– Relativamente Segura
– Amplamente utilizada
– Rápida
• Desvantagens
– Requer compartilhamento da chave secreta
– Chaves devem ser guardadas com segurança
– Grande número de chaves
– Administração complexa
– Não permite a não-retratação
57
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Funções de Autenticação
• Três classes de autenticadores
– cifração de mensagens
• o criptograma da mensagem inteira serve como 
autenticador
– código de autenticação de mensagem (MAC)
• função da mensagem e de uma chave secreta que 
produz um valor de comprimento fixo
– funções de condensação
• função que mapeia uma mensagem de qualquer 
comprimento em um valor resumo de tamanho fixo
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Funções Hash
• Funções hash ou de condensação são funções 
unidirecionais: d = h(m), mas não é tratável 
m = h-1(d).
– Levam mensagens de tamanho arbitrário em resumos 
(hash) de tamanho fixo
• Funções hash tem como premissa:
– evitar que se encontre a mensagem dado o resumo
– evitar que se encontre m1, m2 tal que d1=d2
– dado m1, evitar que se encontre m2 com mesmo resumo
58
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Aleatoriedade:
– Distribuição uniforme
• para muitas entradas, as saídas devem ser ‘1’ 
na metade do tempo
• cada saída deve ter 50% de bits ‘1’
– Independência
• entradas parecidas devem levar a saídas não 
relacionadas (metade dos bits deve diferir na 
saída)
Funções Hash
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Muitas mensagens podem levar ao mesmo 
resumo:
– Suponha resumos de 128 bits e mensagens com 1000 
bits de comprimento
– Na média, existem 2872 mensagens que mapeiam para o 
mesmo resumo
– Mas, na média, são necessárias 2128 tentativas para se 
encontrar duas tais mensagens
Funções Hash
59
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Paradoxo do aniversário:
– quantas pessoas deve haver numa sala para que se tenha 
50% de chances de se encontrar duas pessoas que 
possuam a mesma data de aniversário?
– Seja n a quantidade de entradas
– Sejam k = 365 as possíveis saídas
– Há no total n(n-1)/2 pares de entrada
– Probabilidade de não haver colisão: p=(1/k)n(n-1)/2
– Por exemplo, se n=23, ptodosdiferentes=0,49
Funções Hash
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Paradoxo do Aniversário
– Para m bits, são necessários cerca de 2m/2 mensagens para que se 
encontre uma colisão
– Lembrando que este problema é diferente de pegar h e encontrar o
m relativo
– Exemplo:
• Alex, cuja secretária é Bia quer demitir Melo
• Bia é amiga de Melo
• Bia compõe duas mensagens com o mesmo hash: uma para ser 
lida por Alex e outra para ser enviada para Melo
Funções Hash
60
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Funções Hash
• Exemplos:
– RFC: www.normos.org, www.rfc-editor.org
Nome Inventor Documentação Objeto Hash
MD2 Ron
Rivest
RFC1319 bytes 128
MD4 Ron
Rivest
RFC1320 32-bits 128
MD5 Ron
Rivest
RFC1321 32-bits 128
SHA-1 NIST FIPS PUB 180 32-bits 160
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Autenticação usando MAC=MD[Ks|m1] 
Alex Bia
ra
MD(Ks,ra)
rb
MD(Ks,rb)
Funções Hash
61
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Cifração: one-time pad
– b1=MD[Ks|IV]
– b2=MD[Ks|b1]
– bi=MD[Ks|bi-1]
– b é usado como one-time pad
Funções Hash
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Cifração: misturando no texto em claro
– similar ao CFB
– quebra a mensagem em grupos de comprimento do 
resumo pi
– b1=MD[Ks|IV], c1=p1Åb1
– b2=MD[Ks|c1], c2=p2Åb2
– bi=MD[Ks|ci-1], ci=piÅbi
Funções Hash
62
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD2
• Características
– resumo de 128 bits
– pad para múltiplo de 16 bytes
– anexa MD2 checksum no final
– processa mensagens inteiras
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD2
• Checksum MD2
– mnk: byte nk da mensagem
– cn=p(mnk Åcn-1)
– p: tabela de substituição
• 0®41
• 1 ®46
• ...
63
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD2
• Passagem final
– opera em grupos de 16 bytes
– quantidade q de 48 bytes: 
• (resumo corrente|grupo|resumo Ågrupo)
– 18 passagens sobre q
– cn= cn Å p(cn-1) para n=1...47, c-1=0
– após 17 passagens usa os primeiros 16 bytes como o 
novo resumo
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD2
• Passagem final
bloco de 16 bytes
intermediário bloco msg
Å
byte nbyte n-1 byte 47
0
substituição p Å para n de 0 até 47+
passagem #
(0 a 17)
para próximo
bloco msg resumo
final
valor inicial=0
descartado
64
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD4
• Características:
– qualquer número de bits
– opera sobre quantidades de 32 bits
– faz pad para múltiplos de 512 bits
– resumo=f(blocos de 512 bits, resumo anterior)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD4
100…0
comprimento
da mensagem
(k mod 264)
padding
(1 a 512 bits)
mensagem
k bits
Lx512 bits=Nx32 bits
... ...Y0 Y1 Yq YL-1
HMD4
512
128
VI
HMD4
128
512
CV1
HMD4
128
512
CVq
HMD4
128
512
CVL-1
128
65
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD4
• Operações
– ëxû
– ~: complemento de bit
– xÙy
– xÚy
– adição módulo 232
– rotação à esquerda por y bits
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD4
• Passagem 1: seleção
– função de seleção: F(x,y,z)=(xÙy)Ú(~xÙz)
• Passagem 2: majoração
– função de majoração: G(x,y,z)=(xÙy)Ú(xÙz)Ú(yÙz)
• Passagem 3: xor
– função: H(x,y,z)=xÅyÅz
• Obs
– A cada um dos 16 passos de cada passagem, é feita uma rotação à 
direita com A, B, C, D (descritos no esquema seguinte), passando as 
3 últimas palavras a assumir os papéis de x, y e z
66
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD4
F, X[i], 16 passos
G,5A82799916, X[i], 16 passos
H, 6ED9EBA116, X[i], 16 passos
A B C D
A B C D
A B C D
CVq
128
+ + + +
CVq+1
Yq
512
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD5
• Características:
– mesmo padding do MD4
– MD5: 4 passagens
67
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD5
100…0
comprimento
da mensagem
(k mod 264)
padding
(1 a 512 bits)
mensagem
k bits
Lx512 bits=Nx32 bits
... ...Y0 Y1 Yq YL-1
HMD5
512
128
VI
HMD5
128
512
CV1
HMD5
128
512
CVq
HMD5
128
512
CVL-1
128
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD5
• Passagem 1 e 3:
– como em MD4
• Passagem 2: 
– função G(x,y,z)=(xÙz)Ú(yÙ~z)
• Passagem 4: 
– I(x,y,z)=yÅ(xÚ~z)
• Obs
– A cada um dos 16 passos de cada passagem, é feita uma rotação à 
direita com A, B, C, D (descritos no esquema seguinte), passando as 
3 últimas palavras a assumir os papéis de x, y e z
68
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
MD5
CVq+1
F, T[1…16], X[i], 16 passos
G,T[17…32], X[i], 16 passos
H, T[33…48], X[i], 16passos
A B C D
A B C D
A B C D
CVq
128
+ + + +
Yq
512
A B C D
I, T[49…64], X[i], 16 passos
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
SHA-1
• Características:
– 64 bits para 160 bits
– similar ao MD4
– 5 passagens
– Resumo:
• CV0=IV
• CVq+1=SOMA32(CVq,ABCDEq)
• MD=CVL
• onde 
– ABCDEq= saída do último round de processamento do q-ésimo
bloco
– L=número de blocos da mensagem
– SOMA32= soma módulo 32
69
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
SHA-1
• Passagem 1: seleção
– função f1(x,y,z)=(xÙy)Ú(~xÙz)
• Passagem 2: 
– função f2(x,y,z)= xÅyÅz(xÙz)Ú(yÙ~z)
• Passagem 3: Xor
– função f3(x,y,z)=(xÙy)Ú(xÙz)Ú(yÙz)
• Passagem 4: 
– função f4(x,y,z)= xÅyÅz
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
SHA-1
f1, K, W[0…19]
A B C D
A B C D
A B C D
CVq
160
+ + + +
CVq+1
Yq
512
A B C D
+
E
E
E
E
f2, K, W[20…39]
f3, K, W[40…59]
f4, K, W[60…79]
70
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
HMAC
• Objetivos de projeto RFC 2104 
– usar, sem modificações, funções de condensação 
disponíveis
– permitir fácil substituição da fção condens.
– preservar desempenho original da fção condens.
– usar e manipular chaves de forma simples
– permitir análise criptográfica de sua força
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
HMAC
• Operação
– HMACK=H[(K+Åopad)||H[(K+ Åipad)||M]]
• H: fção condens.
• M: msg
• Yi: i-ésimo bloco de M
• L: nr de blocos em M
• b: número de bits num bloco
• n: comprimento do resumo
• K: chave secreta
• K+: K preenchida com zeros à esq até b bits de compr.
• ipad: 00110110 repetido b/8 vezes
• opad: 01011010 repetido b/8 vezes
71
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
HMAC
Si Y0 Y1
Å
K+ ipad
b bits
YL-1...
HashVI n bits
n bits
H(Si||M)Å
K+ opad
So Y0
HashVI n bits
n bits
HMACK(M)
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Problemas da criptografia convencional
– na distribuição de chaves os comunicantes devem
• já compartilhar a chave
• ter um centro de distribuição de chaves
– não possibilita assinatura digital
Criptografia Assimétrica
72
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Algoritmos de chave pública baseiam-se em uma 
chave para cifração e outra para decifração
– Deve ser computacionalmente intratável determinar a 
chave de decifração dado somente conhecer o algoritmo 
de criptografia e a chave de cifração
– Em alguns algoritmos as chaves relacionadas podem ser 
usadas para cifração, com a outra sendo usada para 
decifração
Criptografia Assimétrica
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Os passos essenciais de um processo de cifração
de chave pública
– Cada sistema final numa rede gera um par de chaves
– Cada sistema publica sua chave de cifração colocando-a 
em um registro ou arquivo público
– Se Alex deseja enviar uma mensagem para Bia, ele 
envia a mensagem usando a chave pública de Bia
– Quando Bia recebe a mensagem, ela a decifra usando 
sua chave privada
Criptografia Assimétrica
73
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia Assimétrica
Chave
Pública
(KU)
canal inseguro
Chave
Secreta
(KR)
CIFRA DECIFRAM
C
M
canal
inseguro
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
– Confidencialidade
fonte da
mensagem
algoritmo
de cifração
algoritmo de
decifração
destino
fonte do
par de 
chaves
criptanalista X
KRb
^
^
KRb
KUb
X
Y
X
Criptografia Assimétrica
74
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
– Autenticação
fonte da
mensagem
algoritmo
de cifração
algoritmo de
decifração
destino
fonte do
par de 
chaves
criptanalista
KRa
^
KRa
KUa
X
Y
X
Criptografia Assimétrica
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Categorias de algoritmos de chave pública:
– Cifração/decifração
• Ex: RSA
– Assinatura digital
• Ex: RSA, DSS
– Troca de chaves
• Ex: RSA, Diffie-Hellman
Criptografia Assimétrica
75
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Condições dos algoritmos de chave pública
– fácil de gerar o par KU e KR
– fácil de computar C=EKU(M)
– fácil de computar M=DKR(C)
– difícil de determinar KR a partir de KU
– difícil de computar M, dado KU e C
– M=EKU[DKR(M)]
Criptografia Assimétrica
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Básico de Teoria dos Números
• Divisibilidade
– símbolo “|” significa divide
• a|b: a divide b ou b é divisível por a
– propriedades
• se a|1, então a=±1
• se a|b e b|a, então a=±b
• todo b¹0 divide 0
• se b|g e b|h, então b|(mg+nh) para m e n inteiros 
arbitrários
• ex: 7|(3x14+2x63), pois 7\7(3x2+2x9)
76
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Básico de Teoria dos Números
• Inteiros relativamente primos
– a e b são relativamente primos se mdc(a,b)=1
• Aritmética modular
– a=qn+r, 0£r<n; q=ëa/nû
– propriedades
• aºb mod n se n|(a-b)
• se (a mod n)=(b mod n), então aºb mod n
• se aºb mod n, então bºa mod n
• se aºb mod n e bºc mod n, então aºc mod n
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Básico de Teoria dos Números
• Aritmética modular (cont)
– operações
• [(a mod n)+(b mod n)] mod n = (a+b) mod n
• [(a mod n)-(b mod n)]mod n = (a-b) mod n
• [(a mod n)*(b mod n)]mod n = (a*b) mod n
• Função tociente de Euler
– f(n) é o número de inteiros menores que n e 
relativamente primos a n
– para p primo, f(p)=p-1
• se n=pq, p¹q, então f(n)=(p-1)(q-1)
77
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Básico de Teoria dos Números
• Teorema de Euler
– para todo a, n relativamente primos, 
af(n)º1 mod n
– para p primo apºa mod n
• Cálculo do inverso modular aºb-1mod n
– algoritmo estendido de euclides
• se mdc(n,a)=1, então o algoritmo estendido de 
Euclides proporciona o inverso modular de a mod n
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Básico de Teoria dos Números
• Algoritmo estendido de Euclides
– Exemplo: mdc(13,5)
– o número em negrito é o inverso modular de 5 mod 13, 
ou seja 5º-5-1 mod 13º8 mod 13
i r q s t
-1 13 1 0
0 5 0 1
1 3 2 1 -2
2 2 1 -1 3
3 1 1 2 -5
4 0 2
78
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Criado em 1977 por Rivest, Shamir e Adleman
• Bases matemáticas
– dificuldade de fatorar o produto de dois números 
primos
– inversibilidade da exponenciação em módulo, se usados 
determinados pares de números primos como expoentes
• Chave pública e chave privada
• Velocidade: 100 vezes mais lento que DES
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Encontrar 2 fatores primos do número 77
• Encontrar 2 fatores primos do número
34.812.398.461.263.861.234.861.324.986.123.846.
198.234.674.365.874.223.487.129.867.356.512.390.
348.723.487.231.785.345.987.234.586.234.230.476.
897.234.634.598.734.587.987.235.879.823.458.789.
234.589.789.342.683
• Tempo de fatoração de um simples módulo de 200 dígitos RSA é maior 
que70,000,000 MIPS-years
• Mesmo nas máquinas mais rápidas, a vantagem é sempre do cifrador, pois 
chaves maiores podem ser usadas com maior eficiência do que a dos 
métodos de fatoração
79
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Chave pública
– n produto de dois números primos, p and q
– e primo relativo de (p-1) x (q-1)
• Chave privada
– n = p x q
– d =e-1(mod (p-1) x (q-1))
• Cifração (usando a chave pública)
– c=me(mod n)
– e vale tipicamente 65536 (216)
• Decifração (usando a chave privada)
– m=cd(mod n)
– d vale de 2510 a 2512 para módulo de 512-bits
– Operação mais demorada que a cifraçãomai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
– Texto em claro é cifrado em blocos
• cada bloco deve ter tamanho menor que log2n, para 
algum inteiro n
• na prática, o tamanho do bloco é 2k, 2k<n£ 2k+1
– Forma da cifração e decifração:
• C=Memod n
• M=Cdmod n = (Me)dmod n = Medmod n
80
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
– Cálculo do par de chaves
• Seja F(n) a função tociente de Euler (número de 
inteiros positivos menores que n e relativamente 
primos a n
• Se n=pq, então F(n)=(p-1)(q-1)
• Pelo teorema de Euler: dados p e q primos, n e m 
inteiros, tq n=pq e 0<m<n, e um inteiro arbitrário k:
mkF(n)+1=mk(p-1)(q-1)+1ºm mod n
• Assim, ed=kF(n)+1
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
– Esquema RSA:
• p, q dois números primos (privado, escolhido)
• n=pq (público, calculado)
• e, com mdc(F(n),e)=1; 1<e<F(n) (público, 
escolhido)
• dºe-1mod F(n) (privado, calculado)
– Assim,
• KU={e,n} e KR={d,n}
81
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Segurança do RSA
– Possibilidades de ataques:
• força bruta
• ataques matemáticos
– fatorar n em seus dois fatores primos
– determinar F(n) diretamente
– determinar d diretamente
• ataques de temporização
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Progresso na fatoração
• RSA Challenge: 
http://www.rsasecurity.com/rsalabs/challenges/factoring/ 
numbers.html
Nº dígitos decimais Data MIPS-ano Método
100 1991 7 MPQS
110 1992 75 MPQS
120 1993 830 MPQS
129 1994 5000 MPQS
130 1996 500 NFS
140 1999 2000 NFS
155 1999 8000 NFS
82
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
RSA
• Ataques de temporização
– Baseado em diferenças de tempo no cálculo de uma 
operação (por exemplo: exponenciação modular) com 
operandos diferentes
– Formas de se evitar:
• tempo de exponenciação constante
• atrasos aleatórios
• cegueira: multiplicação por um aleatório r
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
-10
-8
-6
-4
-2
0
2
4
6
8
10
-4 -3 -2 -1 0 1 2 3 4 5 6
P
Q
-R
R=P+Q
Criptografia de Curva Elíptica
– CE no corpo dos reais: Forma de Weierstrass: 
y2+a1xy+a3y=x3+a2x2+a4x+a6
83
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia de Curva Elíptica
– A curva elíptica E é composta por todos os pontos (x,y), 
x e y Î K, que satisfazem a definição da curva, 
juntamente com o ponto no infinito O.
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia de Curva Elíptica
– Regras de adição:
P+O=O+P=P
(x,y)+(x,-y)=O
P=(x1,y1) e Q=(x2,y2). Então, P+Q=(x3,y3), onde:
• x3=l2-x1-x2
• y3= l(x3-x1)+y1
• l=(y2-y1)/(x2-x1), se P¹Q
• l=(3x12+a)/2y1, se P=Q
– Regra de multiplicação: refere-se ao produto entre um escalar k e 
um ponto sobre a curva P
• Q=kP
84
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia de Curva Elíptica
• Cifração e decifração
– embutir dados na curva
• PA=kAG
• PB=kBG
• Alex envia Cm={kG,Pm+kPB}
• Bia calcula 
(Pm+kPB)-kB(kG)=Pm+k(kBG)-kB(kG)=Pm
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Criptografia de Curva Elíptica
•Alex •Bia
Comum
Tamanho do
corpo
Ponto Base
G
Privado Alex Público Alex Curva
E
Público Bia Privado Bia
Chave
privada
kA
Chave
pública
PA=kAG
Base
matemática
Chave
pública
PB=kBG
Chave
privada
kB
85
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Combinações: Envelope Digital
Chave
Randômica
DES
“Envelope Digital ”
hghsdhghsd nbhsdbh
jhjsdhjsdhj
jhjsd hgsdd hghghs
uhwefsd mnsdf u
hweuqhuwedhu
Chave
Pública
do Receptor
Chave
Randômica
DES
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Combinações: Assinatura Digital
DigeridoMD5
Chave
Privada do
Assinado
Digerido
Cifrado
Assinatura
86
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Combinações: Assinatura Digital
MD5
Digerido
Recalculado
Chave Pública
do Assinado
Digerido
Recebido
=?
Verificação
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Requisitos:
– depende da mensagem
– utiliza informação única da fonte
– fácil de produzir
– fácil de reconhecer
– intratável de forjar
– armazenamento prático
Combinações: Assinatura Digital
87
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Abordagens
– assinatura direta
– assinatura arbitrada
• usando criptografia simétrica
– (1) X®A: M || EKXA[IDX || H(M)]
– (2) A®Y: EKXB[IDX || M || EKXA[IDX || H(M)] || T]
• chave secreta compartilhada previamente entre X e Y
– (1) X®A: IDX || EKXY[M] || EKXA[IDX || H(EKXY[M])]
– (2) A®Y: EKAY[ IDX || EKXY[M] || EKXA[IDX || H(EKXY[M]) || T]
• usando criptografia assimétrica
– (1) X®A: IDX || EKRX[IDX || EKUY(EKRX[M])]
– (2) A®Y: EKRA[IDX || EKUY(EKRX[M]) || T]
Combinações: Assinatura Digital
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Digital Signature Standard (DSS)
M
H Sig
|| M
s
r
H KUG KUA
compara
Combinações: Assinatura Digital
88
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Chaves privadas
– Muito grandes, não permitem memorização
– Necessidade de proteção para mantê-las privadas
• Chaves Públicas
– Devem ser amplamente divulgadas
– Conveniente ligá-las a um nome
• Dilema da incerteza sobre identidade do dono de uma chave
– Qualquer um pode gerar um par de chaves pública/privada
– Qualquer um pode dar um nome a uma chave pública
– Qualquer um pode divulgar uma chave pública em um diretório público
– Dilema: Como saber com certeza que o nome em uma chave pública 
representa realmente o receptor com quem se quer comunicar?
– Solução: Certificados Digitais
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Considerações:
– distribuição de chaves públicas
– uso de criptografia de chave pública para distribuição 
de chaves secretas (key exchange)
89
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Distribuição de chaves públicas
– Esquemas
• anúncio público (ex: PGP)
• diretório disponível publicamente
• autoridade de chave pública
• certificados de chave pública
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Distribuição de chaves secretas
– Esquemas
• Distribuição simples de chave secreta
– Alex gera par de chaves
– Bia cifra segredo com chave pública de Alex
– Alex decifra
• Distribuição com confidencialidade e autenticação
• Esquema Híbrido
– Uso de um KDC (key distribution center)
90
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
• Problema comum a DES, RC2, RC4: acordo prévio entre 
emissor e receptor quanto à chave de criptografia
• Algoritmo Diffie-Hellman
– permite aos dois lados derivar uma chave sem necessidade de 
trocar nenhuma informação secreta
– tem base na dificuldade de calcular logaritmos discretos
– troca de chave simétrica
– vulnerabilidade man-in-the-middle
• Troca de chave através de um canal não-seguro
– Confidencialidade garantida
– Autentificação não garantida
Diffie-Hellman
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Diffie-Hellman
– Baseado na dificuldade de se calcular logaritmos 
discretos
– A Função Logaritmo Discreto é inversa da função 
exponenciação modular, definida como y=gx mod p, 
onde p é primo e g é um gerador de Z/pZ
91
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
A B
p,g p,g1.
p = número primo, g = base do logaritmo
y1=gx1 mod p y2=gx2 mod p2.
x1 = valor privado da 1a. parte
x2 = valor privado da 2a. parte
Diffie-Hellman
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
A B
p,g p,gy1=gx1 mod p y2=gx2 mod p
y1y2
1.
2.
3.
y1 = valor público da 1a. parte
y2 = valor público da 2a. parte
K=y2x1 mod p K=y1x2 mod p4.
K = chave secreta
Diffie-Hellman
92
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Autoridade de chave pública
autoridade
de chave
pública
Alex Bia
pedido|tempo1
EKRaut[KUb|pedido|tempo1]
EKUb[IDA|N1]
EKUa[N1|N2]
EKUb[N2]
pedido|tempo2
EKRaut[KUa|pedido|tempo2]
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Gerenciamento de Chaves
• Certificados de chave pública
autoridade
certificadora
Alex Bia
KUa
CA=EKRaut[tempo1,IDA,KUa]
CA
CB
KUb
CB=EKRaut[tempo2,IDA,KUb]
93
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Certificados Digitais
• Características
– Como uma carteira de identidade eletrônica, um 
Certificado Digital assegura que alguma autoridade fez 
checagens razoáveis da identidade do portador
– Um Certificado Digital notariza a ligação entre uma 
chave pública e um Emissor, assim como o R.G. prova 
a identidade de alguém
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Certificados Digitais
Nome,
Organização, Endereço
Chave Pública do Portador
Datas de Validade do
Certificado
Número de Série
Assinatura Digital da
Autoridade Certificadora
Documento
Assinatura Digital
Certificado Digital
94
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Autoridades Certificadoras
• São o equivalente eletrônico dos cartórios (notários): "terceira parte 
confiável"
• Emitem, autenticam e gerenciam certificados digitais
• Serviço contínuo, confiável, operando 24 horas por dia, 7 dias por 
semana, e acessíveis globalmente pelos clientes
• Recursos tecnológicos
– protocolos e padrões de segurança
– sistema de mensagens seguro
– infraestrutura adequada: instalações seguras, banco de dados, home-page
– serviço de suporte ao cliente
• Conjunto de práticas: 
– normas e procedimentos de utilização dos serviços pelos clientes
– resolução de disputas
mai-04 Criptografia
Prof. Ricardo Staciarini Puttini
Infra-Estrutura de Chave Pública
Autoridade
Raiz
Autoridade
Nomeadora Repositório
CA Primária
Classe 2
CA Primária
Classe 3
CA Primária
Classe 1
CA
Classe 1
CA
Classe 1
CA
Classe 2
CA
Classe 2
CA
Classe 3
CA
Classe 3
CA
Subordinada
Classe 2
CA
Subordinada
Classe 3