INF712 – Gerência de
Segurança da Informação
Conceitos básicos de Criptografia Computacional
Prof. Ricardo Dahab
IC-UNICAMP
14/12/2002
Fontes principais
Livros


Cryptography and Network Security,
Principles and Practice, de William
Stallings.
Capítulo 1 do Handbook of Applied
Cryptography, de Menezes, van
Oorschot e Vanstone. (.ps, .pdf).
14/12/2002
INF712 - Gerência de Segurança
da Informação
2
Criptografia e mecanismos de
segurança


Vários mecanismos são empregados
para prover serviços de segurança.
Quase todos são baseados em
ferramentas criptográficas:
– Primitivas
– Protocolos criptográficos de vários níveis de
complexidade.
14/12/2002
INF712 - Gerência de Segurança
da Informação
3
Qual criptografia?


14/12/2002
Clássica X Moderna
Convencional, simétrica
ou de chave secreta
X
Moderna, assimétrica
ou de chave pública
INF712 - Gerência de Segurança
da Informação
4
Criptografia Convencional

Técnicas clássicas

Técnicas modernas

Algoritmos modernos

Sigilo e autenticação com criptografia
convencional, ou simétrica.
14/12/2002
INF712 - Gerência de Segurança
da Informação
5
Criptografia Convencional



O modelo convencional de ciframento
pressupõe a existência de uma chave
previamente combinada entre as duas
partes em comunicação.
Esse segredo autentica uma parte perante
a outra.
Esse tipo de criptossistema, também
chamado de simétrico ou de chave secreta,
perdurou até meados da década de 70.
14/12/2002
INF712 - Gerência de Segurança
da Informação
6
Criptografia Convencional
Categorias dos sistemas convencionais:
 Tipo de operação no texto claro:
substituição e/ou transposição.
 Interação entre chave e texto:
– blocos: divisão do texto em blocos e reaplicação do
algoritmo em cada bloco;
– fluxo: texto é combinado com chave bit a bit.
Não confundir com esteganografia.
14/12/2002
INF712 - Gerência de Segurança
da Informação
7
Criptoanálise


Descoberta total ou parcial da chave
e/ou texto claro por métodos
sistemáticos.
Formas de ataque <T2.1> são
classificadas de acordo com o nível de
conhecimento a que o criptoanalista
tem acesso.
14/12/2002
INF712 - Gerência de Segurança
da Informação
8
Criptoanálise
Segurança de um criptossistema:
– incondicional: poder computacional do criptoanalista
é irrelevante;
– computacional: poder computacional é irrelevante
na prática, num horizonte de tempo predizível;
– comprovada: poder computacional é irrelevante no
presente mas nada se pode dizer do futuro.
Busca exaustiva <T2.2> é a opção “fácil”, na prática.
14/12/2002
INF712 - Gerência de Segurança
da Informação
9
Técnicas clássicas

Substituição:
– Monoalfabética: um caractere por outro de acordo
com uma tabela (chave). Ex: César. Mantém a
freqüência relativa dos caracteres.
– Monogrupos: grupos de caracteres por outros grupos
fixos de caracteres. Ex: Playfair, Hill.
– Polialfabética: monoalfabética variando ao longo
<T2.4> do texto claro.
14/12/2002
INF712 - Gerência de Segurança
da Informação
10
Técnicas clássicas

Transposição:
– Embaralhamento dos caracteres de acordo
com alguma tabela (chave).


Causam um efeito de dispersão no
texto claro.
Os métodos de substituição causam
um efeito de confusão no texto.
14/12/2002
INF712 - Gerência de Segurança
da Informação
11
Técnicas clássicas



Produtos: substituição e transposição.
Máquinas com rotores implementavam
essa idéia.
Algoritmos modernos refinaram e
multiplicaram o poder de tais
máquinas, implementadas em
computadores.
14/12/2002
INF712 - Gerência de Segurança
da Informação
12
Técnicas Modernas


Técnicas clássicas são inseguras
porque não supunham a existência de
computadores em mãos de
criptoanalistas.
O primeiro método moderno foi
proposto em meados da década de 70,
o conhecido D.E.S.
14/12/2002
INF712 - Gerência de Segurança
da Informação
13
O D.E.S.


D.E.S (Data Encryption Standard), foi
o método oficial do governo dos
E.U.A. para ciframento de informação
não “sensível”, até muito pouco tempo.
Ainda é muito usado em toda a
Internet, em sua forma mais
fortalecida, o 3-DES.
14/12/2002
INF712 - Gerência de Segurança
da Informação
14
O D.E.S.



Processa blocos de texto de 64 bits cada
vez, sob a ação de uma chave de 56 bits,
produzindo 64 bits de texto cifrado.
É composto de 16 rodadas de produtos de
transposições e substituições, cada uma
usando uma porção diferente da chave.
O efeito avalanche <T3.5> garante que
qualquer mudança no texto claro ou chave
cause mudança de metade do texto cifrado.
14/12/2002
INF712 - Gerência de Segurança
da Informação
15
O D.E.S.


Critérios de projeto do D.E.S. não foram
totalmente revelados pelos
desenvolvedores (originalmente um projeto
da IBM).
Isso causou, por anos, desconfiança de que
o algoritmo contivesse armadilhas secretas
que permitiriam à comunidade de
informação acesso a mensagens cifradas
dos usuários.
14/12/2002
INF712 - Gerência de Segurança
da Informação
16
Cifras de bloco
Modos de operação <T3.6>:
 ECB (Electronic Codebook)
 CBC (Cipher Block Chaining)
 CFB (Cipher Feedback)
 OFB (Output Feedback)
Cada um tem suas vantagens do ponto de
vista de propagação e recuperação de
erros, localidade, etc.
14/12/2002
INF712 - Gerência de Segurança
da Informação
17
Outros algoritmos
simétricos modernos

Triple D.E.S (3-DES)
– Modo preferido de uso do D.E.S.
– Pode ser usado com uma, duas ou três
chaves.
– Só é efetivo porque o D.E.S. não é um grupo
algébrico.
– Passível de ataques quando duas chaves são
usadas.
14/12/2002
INF712 - Gerência de Segurança
da Informação
18
O mundo pós-D.E.S.



IDEA (International Data Encryption
Algortihm)
Blowfish, RC-5, um sem-número de
outros...
...e o novo padrão A.E.S. (Advanced
Encrytpion Standard), resultado de
um concurso público de 4 anos.
14/12/2002
INF712 - Gerência de Segurança
da Informação
19
Usando ciframento simétrico





Pontos de vulnerabilidade são muitos.
Há duas possibilidades de inserção
das funções de ciframento numa rede:
nos links ou nas pontas.
Diferentes características <T5.1>.
Veja detalhes de um exemplo usando
uma aplicação típica de e-mail.
Veja os detalhes nos pacotes.
14/12/2002
INF712 - Gerência de Segurança
da Informação
20
Distribuição de chaves




O problema de distribuir e gerenciar
chaves criptográficas num ambiente
de rede não é trivial.
É necessária uma hierarquização do
processo.
Veja um protocolo centralizado de
distribuição de chaves.
E agora um protocolo descentralizado.
14/12/2002
INF712 - Gerência de Segurança
da Informação
21
Criptografia de chave pública
Tópicos:
 Conceitos básicos e exemplos.
 A matemática necessária.
 Autenticação e o papel das funções de
resumo (hashing) criptográfico.
 Algoritmos de resumo criptográfico.
 Assinaturas digitais.
14/12/2002
INF712 - Gerência de Segurança
da Informação
22
Criptografia de chave pública
conceitos básicos 

-
Criptografia simétrica não resolve um
problema básico: o estabelecimento seguro
da chave secreta entre as duas partes
comunicantes.
Outra deficiência desses sistemas é a
incapacidade das partes de demonstrar a
autoria de uma mensagem a uma terceira
parte. Um mecanismo equivalente a
assinaturas poderia suprir essa deficiência.
14/12/2002
INF712 - Gerência de Segurança
da Informação
23
Criptografia de chave pública
- conceitos básicos 

A criptografia de chave pública tem
resposta a esses dois problemas.
Os princípios básicos dessa tecnologia
foram propostos em meados da década de
70 por Whitfield Diffie e Martin Hellman
no artigo “New directions in Cryptography”,
que tornou-se um marco na história da
criptografia moderna.
14/12/2002
INF712 - Gerência de Segurança
da Informação
24
Contribuições de Diffie e Hellman


Um método para estabelecimento de uma
chave secreta usando um canal inseguro.
A idéia de que poderiam existir sistemas
criptográficos onde cada parte A teria
duas chaves distintas: uma pública, para
ciframento de mensagens para A; outra,
privada, de conhecimento exclusivo de A,
para deciframento de tais mensagens.
14/12/2002
INF712 - Gerência de Segurança
da Informação
25
Criptossistemas de chave pública



A primeira idéia ficou conhecida como
método Diffie-Hellman para troca de
chaves. Veremos detalhes adiante.
A segunda idéia só se materializou
como um criptossistema de fato
alguns meses depois.
O conhecido RSA foi o primeiro
desses sistemas.
14/12/2002
INF712 - Gerência de Segurança
da Informação
26
Criptossistemas de chave pública

Para que um sistema de chave pública
seja efetivo, é necessário que:
– a função de ciframento seja difícil de
inverter;
– seja muito difícil descobrir a chave privada,
apesar do conhecimento da chave pública.
14/12/2002
INF712 - Gerência de Segurança
da Informação
27
Sistemas de chave pública x
chave secreta


Sistemas de chave pública são chamados de
assimétricos, já que o “dono” do par de
chaves sendo usadas numa comunicação tem
controle da situação.
Sistemas assimétricos poderiam substituir
completamente sistemas simétricos, não
fosse por dois aspectos importantes:
eficiência e obtenção segura da chave
pública.
14/12/2002
INF712 - Gerência de Segurança
da Informação
28
Sistemas de chave pública x
chave secreta



Na prática, sistemas de chave pública
são usados para estabelecer chaves
secretas de um sistema simétrico.
Isso combina a flexibilidade dos
sistemas assimétricos com a
eficiência dos sistemas simétricos.
Veja outras diferenças (Tab. 6.1)
14/12/2002
INF712 - Gerência de Segurança
da Informação
29
Assinaturas Digitais



Talvez a contribuição mais surpreendente das
idéias de Diffie-Hellman seja a possibilidade de se
fazer assinaturas digitais.
A posse da chave privada por apenas uma pessoa,
seu “dono”, também o identifica unicamente; p. ex.,
se for possível demonstrar que a confecção de uma
mensagem exigiu o uso da chave privada, temos o
efeito de uma assinatura digital sobre aquela
mensagem.
Essa demonstração é feita utilizando-se a chave
pública, que é a “face” pública da chave privada.
14/12/2002
INF712 - Gerência de Segurança
da Informação
30
Um exemplo - O R.S.A.



Proposto por R. Rivest, A. Shamir e L.
Adleman em 1977, foi o primeiro
criptossistema de chave pública e
permanece até hoje o mais popular.
Baseia sua força na dificuldade de se
encontrar a fatoração de números
inteiros muito grandes.
Aqui está o RSA e um exemplo.
14/12/2002
INF712 - Gerência de Segurança
da Informação
31
O R.S.A. - implementação
Ciframento e deciframento:
 para garantir um nível razoável de
segurança, os primos p e q devem ter
cerca de 300 a 400 dígitos decimais.
 Operações de exponenciação e mod
são eficientes. Veja um algoritmo de
exponenciação modular rápido.
14/12/2002
INF712 - Gerência de Segurança
da Informação
32
O R.S.A. - implementação
Geração de chaves:


Algoritmos para geração de números primos
são probabilísticos já que, às vezes,
mentem. Mas é possível determinar se um
dado número é primo ou não com boa dose
de certeza.
Inversos multiplicativos modulares são
cálculáveis eficientemente, usando o
algoritmo estendido de Euclides.
14/12/2002
INF712 - Gerência de Segurança
da Informação
33
O R.S.A. - segurança

A segurança do R.S.A. baseia-se no fato de
que inverter a função
e
C = M mod n,
isto é, dados C, e, n, obter M é uma tarefa

computacionalmente difícil quando n tem
300 ou mais dígitos.
Não é difícil verificar que se o criptoanalista conhecer os números p, q, então é
fácil obter d e portanto M facilmente.
14/12/2002
INF712 - Gerência de Segurança
da Informação
34
O R.S.A. - segurança


Assim, a “força” do RSA reside também
num segundo pilar: é difícil obter os primos
p, q a partir de n, isto é, a fatoração de n,
quando n tem 300 dígitos ou mais.
Os melhores algoritmos para fatoração vêm
melhorando seu desempenho (Tab 6.3). Já
se fala que 300 dígitos é pouco e há quem
advogue o uso de 600 dígitos para se ter
um horizonte razoável de segurança.
14/12/2002
INF712 - Gerência de Segurança
da Informação
35
O R.S.A. - segurança


É possível pensar em formas
alternativas de ataques, isto é, tentar
descobrir a chave privada d por
outros meios.
Veja, por exemplo, que, dado o valor
de f(n), então é fácil descobrir o
valor da chave d.
14/12/2002
INF712 - Gerência de Segurança
da Informação
36
O R.S.A. - segurança

Por outro lado, é possível demonstrar
matematicamente que as seguintes três
possibilidades são equivalentes; isto é, dada
uma é possível realizar as outras duas:
– Encontrar a fatoração de n.
– Encontrar o valor de f(n).
– Encontrar o valor da chave d.

Mas, descobrir M a partir de C, e, n, pode
ser mais fácil. Ninguém sabe dizer...
14/12/2002
INF712 - Gerência de Segurança
da Informação
37
Autenticidade de chaves públicas.


Se, por um lado, chaves públicas são
fáceis de obter, são também fáceis
de manipular e fraudar.
É muito importante que o remetente
de uma mensagem tenha certeza da
identidade do destinatário e de que
uma chave pública seja de fato
daquele destinatário. Caso contrário...
14/12/2002
INF712 - Gerência de Segurança
da Informação
38
Autenticidade de chaves públicas

Há várias formas de se vincular a
identidade de uma entidade a uma
chave pública:
– “Broadcast” individual de chaves.
– Disponibilização em diretórios públicos.
– Autoridades de distribuição de chaves.
– Certificados e autoridades certificadoras.
14/12/2002
INF712 - Gerência de Segurança
da Informação
39
Estabelecimento de
chaves secretas



Como já vimos, é possível estabelecer
uma chave secreta entre duas partes
usando chaves públicas.
Eis outro protocolo, um pouco mais
elaborado.
Há porém, a idéia original de Diffie e
Hellman que dispensa o uso de chaves
públicas.
14/12/2002
INF712 - Gerência de Segurança
da Informação
40
O método Diffie-Hellman


Baseia-se na dificuldade de se
inverter uma outra função, similar à
do R.S.A. Dados um primo p e
números x e y para os quais existe k
tal que
y = xk mod p,
descubra o valor do inteiro k.
É o problema do logaritmo discreto.
14/12/2002
INF712 - Gerência de Segurança
da Informação
41
O método Diffie-Hellman
Suponha a existência de parâmetros públicos p e g.
 Entidade A(lice), escolhe um aleatório a e envia
MA = ga mod p
para a entidade B(eto).
 Beto faz o mesmo e envia para Alice
MB = gb mod p.
 Alice calcula
(MB)a mod p = gba mod p.
b
 Beto calcula (MA) mod p = gab mod p.

14/12/2002
INF712 - Gerência de Segurança
da Informação
42
O método Diffie-Hellman


É seguro mas passível de um ataque
de um intermediário.
Há técnicas para evitar esse ataque.
14/12/2002
INF712 - Gerência de Segurança
da Informação
43
Outros métodos de chave pública


Curvas elípticas são o maior
concorrente do R.S.A. atualmente.
Maior vantagem está no tamanho
reduzido dos parâmetros para o
mesmo nível de segurança, quando
comparado (Tab. 6.5) com o R.S.A.
14/12/2002
INF712 - Gerência de Segurança
da Informação
44
Autenticação e Hashing
Tópicos:
 A necessidade de autenticação
 Funções para provimento de autenticação:
–
–
–
–
Ciframento
Códigos de autenticação (MACs e MDCs)
Assinaturas digitais.
Funções de hashing com propriedades
criptográficas.
14/12/2002
INF712 - Gerência de Segurança
da Informação
45
A necessidade de autenticação

Autenticação (da origem e do conteúdo) de
mensagens é um conjunto de técnicas
fundamentais para proteção contra:
– personificação da autoria de uma mensagem
– modificação acidental ou não de uma mensagem
– modificação na ordem de uma seqüência de
mensagens
– atraso ou re-envio de mensagens
– repúdio da autoria de uma mensagem
14/12/2002
INF712 - Gerência de Segurança
da Informação
46
Técnicas para autenticação

São quatro as técnicas criptográficas
empregadas em autenticação:
–
–
–
–

Ciframento
MACs (Message Authentication Codes)
MDCs (Manipulation Detection Codes)
Assinaturas Digitais
Assinaturas digitais são as únicas que
provêem proteção contra repúdio de
autoria. Veremos essas técnicas a seguir.
14/12/2002
INF712 - Gerência de Segurança
da Informação
47
Autenticação com ciframento


Ciframento simétrico (Fig. 8.1 (a)) provê
autenticação mútua de duas partes em
comunicação, desde que se saiba o que se
espera do resultado de um deciframento.
De qualquer forma, sabendo ou não, é útil
adicionar um controle de erros às
mensagens cifradas. Além da detecção de
erros, essa técnica verifica o deciframento
correto de mensagens sem redundância.
14/12/2002
INF712 - Gerência de Segurança
da Informação
48
Autenticação com MACs


Um MAC (Message Authentication Code) de
uma mensagem M é o resultado do cálculo
de uma função de mão única Ck (M), onde M
é a mensagem em questão e k é uma
informação secreta, conhecida somente
pelas duas partes em comunicação.
Uma parte envia M e seu MAC. A outra
parte recalcula o MAC e aceita M se o valor
obtido é igual ao MAC recebido. Veja Fig.
8.4 (a).
14/12/2002
INF712 - Gerência de Segurança
da Informação
49
Autenticação com MACs


Exceto pelo fato de que a mensagem passa
em claro, a técnica de MACs é parecida com
a de ciframento simétrico, para esse fim.
De fato, é possível usar uma função de
ciframento no papel de Ck( ). Na prática,
usa-se uma função de hash com
propriedades criptográficas; a forma de
combinar M e k segue a RFC 2104 e a
função resultante é chamada de HMAC.
Discutiremos tais funções mais adiante.
14/12/2002
INF712 - Gerência de Segurança
da Informação
50
Autenticação com MDCs



Um MDC (Manipulation Detection Code) de uma
mensagem M é o resultado do cálculo de uma
função de mão única C (M), onde M é a mensagem
em questão.
Uma parte envia M e seu MDC. A outra parte
recalcula o MDC e aceita M se o valor obtido é
igual ao MDC recebido. Veja Fig. 8.5 (a).
Veja que, além de ser de mão única, a função C( )
deve ser resistente a colisões. Esses dois são
atributos de funções de hash, ou resumo
criptográfico.
14/12/2002
INF712 - Gerência de Segurança
da Informação
51
Autenticação com MDCs


A técnica vista na transparência
anterior não provê autenticação
mútua, já que qualquer terceira parte
pode produzir o MDC de uma
mensagem.
Há outros usos de funções de resumo
criptográfico ilustrados em Fig. 8.5ac e Fig. 8.5c-d e explicados na Tab.
8.3 de cada uma.
14/12/2002
INF712 - Gerência de Segurança
da Informação
52
Funções de resumo (hash)
criptográfico

Têm propriedades interessantes do
ponto de vista criptográfico:
– podem ser aplicadas a mensagens de
qualquer tamanho;
– a saída é uma cadeia de tamanho fixo;
– h(M) é fácil de calcular e muito difícil de
inverter;
– tem resistência a colisões, forte e fraca.
14/12/2002
INF712 - Gerência de Segurança
da Informação
53
Funções de resumo
criptográfico populares

Três funções de maior popularidade:
– MD5 (RFC 1321): desenvolvida por Ron Rivest (do
RSA). Produz uma saída de tamanho fixo, de 128
bits, a partir de entradas de tamanho arbitrário. Em
declínio.
– SHA-1 (FIPS PUB 180-1): desenvolvida pelo NIST.
Produz saídas de 160 bits a partir de entradas de
tamanho arbitrário. Em uso crescente.
– RIPEMD-160: projeto europeu, saída de 160 bits,
pouco usada entre nós.
14/12/2002
INF712 - Gerência de Segurança
da Informação
54
HMACs



Como já dissemos, a RFC 2104
especifica uma forma de combinar
mensagem (M) e chave (k) para
produzir um MAC.
Veja a estrutura de um HMAC.
Veja uma implementação eficiente de
um HMAC.
14/12/2002
INF712 - Gerência de Segurança
da Informação
55
Assinaturas digitais

São, ao mesmo tempo, similares e
diferentes das assinaturas usuais:
– Devem revelar, sem engano, o autor, data e hora da
assinatura;
– devem autenticar o conteúdo do que foi assinado, no
momento da assinatura;
– devem ser verificáveis, independentemente, por
terceiras partes, sem cooperação do autor.
14/12/2002
INF712 - Gerência de Segurança
da Informação
56
Assinaturas digitais

Traduzindo em características concretas:
– Deve ser uma cadeia de bits que depende do que
está sendo assinado;
– deve usar alguma informação unicamente associável
ao autor;
– deve ser fácil de produzir;
– deve ser fácil de reconhecer e verificar;
– deve ser computacionalmente difícil de forjar;
– deve ser facilmente armazenável.
14/12/2002
INF712 - Gerência de Segurança
da Informação
57
Assinaturas digitais

Há dois esquemas básicos:
– Sem arbitragem: Somente o emitente e
destinatário de uma assinatura são
suficientes para verificar assinaturas e
resolver conflitos.
– Com arbitragem: Um árbitro confiável pode
ser usado, para aumentar a robustez do
esquema não-arbitrado.
14/12/2002
INF712 - Gerência de Segurança
da Informação
58
Assinaturas digitais

Sem arbitragem
– Baseadas em criptografia assimétrica.
– Esquema básico é o da Fig. 8.1(c) ou sua
versão mais eficiente, da Fig. 8.5(c)
– Ambos esquemas dependem da segurança
da chave privada do autor da assinatura: seu
sigilo, integridade e validação temporal.
14/12/2002
INF712 - Gerência de Segurança
da Informação
59
Assinaturas digitais

Com arbitragem
– Baseadas em criptografia simétrica ou
assimétrica.
– A idéia geral é que o árbitro “abençoe”
cada assinatura produzida,
emprestando sua credibilidade ao
esquema.
– Veja exemplos (Tab. 10.1).
14/12/2002
INF712 - Gerência de Segurança
da Informação
60
Algoritmos para assinaturas
digitais
Os algoritmos mais usados em
esquemas de assinaturas digitais
são o RSA e o DSS (Digital
Signature Standard), baseado no
método de ElGamal, que por sua
vez é baseado no problema do
logaritmo discreto.
14/12/2002
INF712 - Gerência de Segurança
da Informação
61
Algoritmos para assinaturas
digitais


O paradigma do RSA é diferente
daquele do DSS.
O DSS não possui a propriedade
comutativa do RSA: se PA, RA são as
chaves pública e privada de A, então
D(RA, E(x, PA)) = E(PA, D(x, RA)),
onde E e D são os algoritmos para
ciframento e deciframento do RSA.
14/12/2002
INF712 - Gerência de Segurança
da Informação
62
Algoritmos para assinaturas
digitais


Essa propriedade possibilita um esquema de
assinatura como o ilustrado na Fig. 10.1(a).
Em contraste, o DSS necessita de um
esquema mais complicado. Veja primeiro a
Fig. 10.1(b). Após seguir em aula a descrição
completa do método, desde a escolha de
chaves até a confecção e verificação de
uma assinatura, veja então um resumo do
DSS na Fig. 10.3.
14/12/2002
INF712 - Gerência de Segurança
da Informação
63