Criptografia e ICP

Prévia do material em texto

>> Gestão da Segurança da Informação e Comunicações >> 2009-2011
Anderson Clayton do Nascimento
CRIPTOGRAFIA E INFRAESTRUTURA DE 
CHAVES PÚBLICAS
G
SI
C2
50
VERSÃO 1
Este material é distribuído sob a licença creative commons
http://creativecommons.org/licenses/by-nc-nd/3.0/br/
Secretaria Pedagógica
Andréia Lacê
Eduardo Loureiro Jr.
Lívia Souza
Odacyr Luiz Timm
Ricardo Sampaio
Assessoria Técnica
Gabriel Velasco
Secretaria Administrativa
Indiara Luna Ferreira Furtado
Jucilene Gomes
Martha Araújo
Equipe de Produção Multimídia
Alex Harlen
Lizane Leite
Rodrigo Moraes
Equipe de Tecnologia da Informação
Douglas Ferlini
Osvaldo Corrêa
Edição, Revisão Técnica e de Língua Portuguesa
Jorge Henrique Cabral Fernandes
CEGSIC
Coordenação
Jorge Henrique Cabral Fernandes
Texto e ilustrações: Anderson ClaytonNascimento | Capa, projeto gráfico e diagramação: Alex Harlen 
Desenvolvido em atendimento ao plano de trabalho do Programa de Formação de Especialistas para a Elaboração da 
Metodologia Brasileira de Gestão de Segurança da Informação e Comunicações – CEGSIC 2009-2011.
José Elito Carvalho Siqueira
Ministro do Gabinete de Segurança Institucional
Antonio Sergio Geromel
Secretário Executivo
Raphael Mandarino Junior
Diretor do Departamento de Segurança da Informação e 
Comunicações
Reinaldo Silva Simião
Coordenador Geral de Gestão da Segurança da 
Informação e Comunicações
Fernando Haddad
Ministro da Educação
UNIVERSIDADE DE BRASÍLIA
José Geraldo de Sousa Junior
Reitor
João Batista de Sousa
Vice-Reitor
Pedro Murrieta Santos Neto
Decanato de Administração
Rachel Nunes da Cunha
Decanato de Assuntos Comunitários
Márcia Abrahão Moura
Decanato de Ensino de Graduação
Oviromar Flores
Decanato de Extensão
Denise Bomtempo Birche de Carvalho
Decanato de Pesquisa e Pós-graduação
Noraí Romeu Rocco
Instituto de Ciências Exatas
Priscila Barreto
Departamento de Ciência da Computação
Dilma Rousseff
Presidente da República
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
3
Sumário
[5] Currículo resumido do autor
[6] Resumo
[7] 1 Introdução
[8] 2 Conceitos Básicos
2.1 Texto em claro, texto cifrado ou criptograma • . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Sistema criptográfico, criptossistema, cifrador e decifrador • . . . . . . . . . . 8
2.3 Processo de criptografia • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Visão Matemática do Ciframento e Deciframento • . . . . . . . . . . . . . . . . . . . 10
2.5 Tipos de Criptossistemas • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Objetivos de um Criptossistema • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6.1 Sigilo • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6.2 Integridade • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6.3 Autenticidade e Não-Repúdio. • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.7 Segurança em criptosistemas e sistemas criptográficos • . . . . . . . . . . . . . 12
[14] 3 Criptografia Simétrica
3.1 Sigilo Perfeito: O One Time Pad • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Cifras de Bloco • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Permutação • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 Substituição • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Difusão/Confusão • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.4 Redes SP • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.5 Estrutura Básica • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.6 Modos de Uso • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.7 DES • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.8 AES • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Cifras de Fluxo • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 O que são as Cifras de Fluxo? • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.2 Vantagens • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.3 Observações sobre Segurança de Cifras de Fluxo (Sigilo) •. . . . . . . . . . . 23
3.3.4 Alguns Exemplos Reais • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Funções de Hash e Aplicações • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4.1 Definições • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4.1 Aplicações • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
4
[28] 4 Criptografia de Chave Pública
4.1 Motivação • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 A Proposta de Diffie e Hellman • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Vantagens da Criptografia de Chave Pública • . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Assinaturas Digitais • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Certificados Digitais e Autoridades Certificadoras • . . . . . . . . . . . . . . . . . . . 30
4.6 Segurança na WEB: O protocolo TLS/SSL • . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
[35] 5 Conceitos Matemáticos de Criptografia de Chave 
Pública
5.1 Acordo de Chaves Diffie-Hellman •. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Criptossistema RSA • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.3 Criptossistema ElGamal • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.4 Segurança Necessária para Criptossistemas de Chave Pública Práticos •
39
5.5 Assinatura Digital • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.6 Conceitos Matemáticos • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.7 Esquema de Assinatura RSA • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.8 Algoritmo de Assinatura Digital (Digital Signature Algorithm, DSA) • . . 41
5.9 Segurança Necessária para Esquemas de Assinatura Digital Práticos • . 41
[43] 6 Conclusões
[44] Referências
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
5
CURRÍCULO RESUMIDO DO AUTOR 
Anderson Clayton do Nascimento
Possui graduação em Engenharia Elétrica pela Universidade de Brasília (1998), mestrado em 
Information And Communication Engineering - University Of Tokyo (2001) e doutorado em In-
formation And Communication Engineering - University Of Tokyo(2004). Atualmente é professor 
adjunto da Universidade de Brasília, coordenador de graduação do curso de engenharia de redes 
de comunicação e coordenador acadêmico do mestrado profissional em informática forense do 
departamento de engenharia elétrica. É revisor dos periódicos IEEE Transactions on Information 
Theory , IEICE Transactions on Fundamentals of Electronics, Journal of Physics A, Journal of Cryp-
tology, dentre outros. Tem experiência na área de Engenharia Elétrica, com ênfase em Seguran-
ça da Informação e Criptografia. É bolsista de produtividade em pesquisa do CNPq (nível 2). O 
prof. Nascimento é membro efetivo do programa de pós-graduação em engenharia elétrica e 
do programa de pós-graduação em informática da universidade de Brasília, tendo participado 
ativamente da criação de ambos os programas. Ele publicou algumas dezenas de artigos em 
conferências e periódicos científicos de alto prestígio e é detentor de uma patente internacional. 
O professor Nascimento é consultor da Agência Brasileira de Inteligência, membro designado do 
comitê técnico ICP-Brasil e vice-coordenador da comissão especial de segurança da informação 
da sociedade brasileira de computação (SBC). O professor Nascimento foi coordenador do comi-
tê de programa do IX Simpósio Brasileiro de Segurança da Informação e de Sistemas Computa-
cionais e será o coordenador geral da XI edição do mesmo evento.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
6
Resumo
A disciplina de criptografia e infra-estrutura de chaves públicas introduz ao aluno con-
ceitos elementares de criptografia presentes nas soluções de segurança de sistemas de infor-
mação correntes. A disciplina inicia-se com conceitos básicos de criptografia e segurança da 
informação tais como: modelos de segurança; definição de cifras simétricas; definição de cifras 
assimétricas e modelo adversarial. Em seguida, as principais técnicas de criptografia simétrica 
bem como as principais cifras de fluxo e de bloco atualmente em uso são explicadas. Os princi-
pais criptossistemas de chave pública são introduzidos juntamente com noções de assinaturas 
digitais. Por fim, explica-se o que são certificados digitais, autoridades certificadoras e infra-
-estrutura de chaves públicas.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
7
1 Introdução
A criptografia tem como um dos seus objetivos principais prover a troca de mensagens se-
cretas entre duas partes, geralmente chamadas de Alice e Bob, de forma que uma terceira parte 
maliciosa, geralmente chamada de Eva, não possa obter nenhuma informação relevante sobre o 
significado das mensagens secretas. A Figura 1 representa abstratamente esta situação.
Figura 1: Eva não deve obter informação relevante sobre as mensagens trocadas entre Alice e Bob.
A infra-estrutura de chaves públicas consiste numa solução geral para o uso da criptogra-
fia em redes de comunicação abertas, quando não se pode assumir que Alice e Bob tenham 
conhecimento prévio um do outro, pois uma vez que a rede é aberta e a todo instante entram e 
saem novos agentes na rede. Mesmo nestas condições, o uso de uma infra-estrutura de chaves 
públicas impede que Eva alcance seu intento.
Este texto apresenta conceitos básicos acerca de criptografia e infra-estrutura de chaves 
públicas e encontra-se organizado em sete seções. A segunda seção introduz os conceitos bá-
sicos de criptografia de uma maneira geral, com definições dos diferentes tipos de cifras (cifra 
simétrica e assimétrica), modelos adversariais1 etc. A terceira seção estabelece idéias e técnicas 
básicas a respeito de cifras simétricas e funções de hash. A quarta seção trata de criptografia 
de chaves públicas, com uso de cifras assimétricas e sua aplicação em assinaturas digitais e 
segurança na Web. A quinta seção, a mais densa do texto, aborda conceitos matemáticos da 
criptografia de chave pública e conclui com discussão sobre a segurança necessária em esque-
mas de assinatura digitais práticos. O tratamento matemático dispensado à compreensão da 
criptografia foi reduzido ao máximo, visando sua acessibilidade ao leigo que possui noções 
básicas de matemática discreta.
1 Modelos adversariais classificam os ataques a um sistema critpográfico.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
8
2 Conceitos Básicos
A seguir, serão estabelecidos conceitos básicos e terminologia relacionados à criptografia.
2.1 Texto em claro, texto cifrado ou criptograma
Com o objetivo de alcançar sigilo em um canal de comunicação que pode estar sujeito a 
escuta, Alice desordena sua mensagem, conhecida como texto em claro, respeitando algumas 
regras pré-estabelecidas, as quais são determinadas por uma chave2 previamente comparti-
lhada com Bob. Alice envia para Bob o texto desordenado. Ao receber o texto desordenado, 
Bob o reordena, de acordo com as regras previamente acordadas, representadas por sua cha-
ve, e assim recupera a mensagem. O texto desordenado é conhecido como texto cifrado ou 
criptograma, e pode ser abstratamente representado pela Figura 2. Perceba que o texto em 
claro está dentro do texto cifrado, mas apenas com a combinação da chave e do “cadeado” é 
(teoricamente) possível recuperá-lo. Em outras palavras, o texto cifrado não deve proporcionar 
a Eva qualquer informação a respeito da mensagem compartilhada entre Alice e Bob.
Figura 2 – Um texto cifrado.
Os processos de desordenar e reordenar a mensagem são conhecidos como ciframento e 
deciframento, respectivamente, e são representados na Figura 3.
Figura 3. Ciframento e Deciframento, usando uma chave criptográfica.
2.2 Sistema criptográfico, criptossistema, cifrador e 
decifrador
O ciframento e o deciframento são possíveis através do uso de um sistema criptográfico, 
que é um sistema computacional (uma combinação de hardware e software) que implemen-
2 Uma chave criptográfica é uma sequencia de caracteres (bits, números, letras etc).
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
9
tam uma cifra3 e é usado para realizar criptografia, tanto a cifragem como a decifragem. Como 
metaforicamente ilustra a Figura 4, pode-se representar uma chave criptográfica por meio de 
uma chave física, o sistema criptográfico por um cadeado, a cifra, cryptosystem ou criptossis-
tema por uma engrenagem (é um algoritmo), a parte do sistema criptográfico ou do criptosis-
tema (algoritmo) que realiza o ciframento por um cadeado fechando, e a parte do que decifra 
o texto cifrado, chamada de decifrador, por um cadeado abrindo.
Figura 4 – Uma “Chave Criptográfica”, um “Sistema Criptográfico”, um “Criptosistema”, o “cifrador” e o “decifrador”.
2.3 Processo de criptografia
O processo de criptografia pode ser representado pelas Figuras 5, 6 e 7.
Figura 5 – O processo de criptografia.
Na Figura 5 um sistema criptográfico, que implementa uma cifra ou criptosistema, é ope-
rado por meio de uma chave, que transforma um texto claro em texto cifrado. De outra forma, 
o mesmo sistema criptográfico é operado por uma chave (usualmente a mesma) para transfor-
mar o texto cifrado em texto claro.
De forma mais detalhada, o processo também pode ser representado pela Figura 6.
Figura 6 – O processo de criptografia, com destaque para a cifragem e decifragem.
3 Uma cifra, criptosistema ou cryptosystem é um algoritmo de ciframento, isto é, um conjunto de 
passos que devem ser realizados por um computador, para transformar um texto claro em um 
texto cifrado.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
10
De outra forma, usualmente os criptologistas estão preocupados com as características 
matemáticas dos algoritmos de ciframento, e estudam e representam o processo de criptogra-
fia do ponto de vista de suas cifras, como ilustra a Figura 7.
Figura 7. Criptossistemagenérico (visão de um criptologista).
Sob uma perspectiva organizacional, os processos das Figuras 5, 6 e 7 são definidos tanto 
pelo sistema criptográfico empregado, cuja implementação é baseada numa combinação de 
cifras, bem como pelos procedimentos organizacionais necessários à manipulação das chaves 
e dos sistemas criptográficos (hardware e software), à execução do ciframento e deciframento, 
ao envio e recebimento do texto cifrado.
2.4 Visão Matemática do Ciframento e Deciframento
Matematicamente, denota-se o ciframento de uma mensagem m com uma chave k por 
um algoritmo de ciframento E( ) por:
( )kE m
e o deciframento do texto cifrado acima com uma chave Kb por um algoritmo de decifra-
mento D( ) por:
( ( ))kb km D E m=
2.5 Tipos de Criptossistemas
Um esquema como o representado na Figura 6 é chamado de cryptosystem ou criptos-
sistema. Se as chaves usadas no ciframento e no deciframento são iguais, o criptossistema é 
classificado como de chave simétrica. Se as chaves utilizadas nas duas etapas forem distintas, 
então é um criptossistema de chave assimétrica. Os criptossistemas de chave simétrica mais 
comuns são as cifras de bloco e as cifras de fluxo.
Cifras de bloco operam em grupos de bits (blocos de bits) enquanto cifras de fluxo ope-
ram no texto em claro bit a bit. Maiores detalhes sobre esses dois tipos de criptossitemas simé-
tricos serão vistos adiante.
Criptossistema de chave pública é o principal tipo de criptossistema de criptografia as-
simétrica. Whitfield Diffie e Martin Hellman introduziram o conceito de criptografia de chave 
pública em 1976 em um trabalho histórico.
Criptossistemas de chave pública utilizam duas chaves distintas com o objetivo de esta-
belecer uma comunicação segura. Uma chave é pública, e a outra chave é secreta. Embora haja 
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
11
uma relação matemática precisa entre as duas chaves, é difícil gerar uma em função da outra, 
tendo-se acesso apenas às chaves. A Figura 8 apresenta, abstratamente um par de chaves assi-
métricas. São diferentes, mas uma é função matemática da outra.
Na criptografia de chave pública, dadas suas características mate-
máticas, o ciframento de uma mensagem pode ser feito por qualquer 
agente, enquanto o deciframento poderá ser feito somente por aquele 
que possui a chave secreta. Através de esquemas desse tipo, duas pesso-
as que não se conhecem podem estabelecer uma comunicação segura 
através de um canal inseguro, sem que tenham compartilhado previa-
mente de uma chave criptográfica. Uma construção prática de criptossis-
temas de chave pública foi proposta por um grupo de pesquisadores do 
MIT (Massachusetts Institute of Technology), o famoso RSA.
2.6 Objetivos de um Criptossistema
Além de prover trocas de mensagens de forma sigilosa entre usuários de um sistema, crip-
tossistemas modernos geralmente devem prover integridade, autenticidade e não-repúdio. 
O sistema busca impedir que o adversário reduza o grau de uma ou mais destes atributos de 
segurança da informação. Estes conceitos são definidos abaixo, por meio de ilustrações de 
ataques realizados pelo adversário.
2.6.1 Sigilo
Sigilo se refere à impossibilidade de um adversário descobrir uma quantidade não-des-
prezível de informação acerca da mensagem transmitida. No cenário da Figura 9, Eva não con-
segue obter informação significativa mesmo que tenha acesso aos pacotes de informação tro-
cados entre Alice e Bob, por exemplo, por meio de packet sniffing.
Figura 9 – Cenário de possível perda de confidencialidade, caso não seja usada criptografia.
2.6.2 Integridade
Integridade garante ao destinatário da mensagem, Bob, que não houve alterações no tex-
to cifrado após o envio feito pelo remetente, Alice. No cenário da Figura 10, Eva não poderia 
interceptar, modificar e enviar a Bob uma mensagem, sem que Bob descubra que a mensagem 
foi adulterada (perdeu sua integridade).
Figura 8 – Um par de 
chaves assimétricas.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
12
Figura 10 – Cenário de possível perda de integridade, caso não seja usada criptografia.
2.6.3 Autenticidade e Não-Repúdio.
Autenticidade garante ao destinatário, Bob, que a mensagem recebida foi realmente en-
viada por Alice, e por mais ninguém. Não-repúdio impossibilita um remetente de uma men-
sagem negar seu envio. Conforme ilustra a Figura 11 em algunas ataques é possível que Eva 
realize um ataque de personificação, fazendo-se passar, por exemplo, por Alice ou por outro 
agente. Alguns criptossistemas impedem que isto ocorra, garantindo autenticidade. Uma con-
seqüência da autenticidade é que Alice também não pode repudiar o envio prévio de uma 
mensagem autêntica recebida por Bob.
Figura 11 – Cenário de possível perda de autenticidade, caso não seja usada criptografia.
Em alguns casos deseja-se que o criptossistema proporcione anonimato a seus usuários, 
isto é, a identidade dos usuários do sistema é mantida oculta. Tal ocorre, por exemplo, em sis-
temas de votação secreta realizados por computador.
2.7 Segurança em criptosistemas e sistemas criptográficos
Como já dito anteriormente, um criptosistema é uma abstração matemática (algoritmo) 
que possibilita o uso da criptografia, enquanto que o sistema criptográfico é a implementação 
computacional da criptografia (hardware e software), o que pode envolver o uso de um ou 
mais criptosistemas. Para que se possa discutir a respeito da segurança de criptossistemas e 
sistemas criptográficos é necessário que, antes, seja especificado o que está disponível a um 
adversário, para que este tente quebrar a segurança do criptosistema (um ataque de nível teó-
rico) ou do sistema (um ataque de ordem prática, isto é, por meio de manipulação e acesso ao 
sistema). A seguir estão os principais tipos de ataques considerados na literatura. É usual em 
criptografia assumir que o adversário possui uma descrição completa do criptossistema em 
uso, a menos de sua chave secreta.
1. Ataque de texto cifrado (Ciphertext-only attack): Nesse ataque o adversário possui 
acesso somente a uma certa quantia de texto cifrado.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
13
2. Ataque de texto em claro conhecido (Known-plaintext attack, KPA): O adversário possui 
acesso ao texto em claro de uma quantidade de dados, além do acesso ao texto cifrado.
3. Ataque de texto em claro escolhido (Chosen-plaintext attack, CPA): O adversário pode 
escolher quais dados e seus respectivos textos cifrados e ter acesso aos mesmos A 
Figura 12 ilustra um exemplo deste tipo de ataque onde, mesmo sem ter acesso ao 
sistema criptográfico contido dentro de um terminal ATM, um atacante escolhe um 
número de identificação pessoal (PIN – Personal Identification Number) que é cripto-
grafado e capturado quando em tráfego através de uma rede.
4. Ataque adaptativo de texto em claro escolhido (Adaptive chosen-plaintext attack, 
CCA2): O adversário tem acesso ao sistema criptográfico e pode escolher pares de 
texto cifrado/texto em claro de forma adaptativa, isto é, o adversário pode modificar 
suas decisões a respeito dos pares de texto cifrado/texto em claro baseado nos dados 
previamente recebidos. Estas mudanças adaptativas são usualmente efetuadas por 
algoritmos de busca, e demandam que o atacante tenha acesso direto ao sistema 
criptográfico.
Figura 12 – Um Exemplo de Ataque CPA (chosen plaintext attack) ao sistema criptográfico de um Banco.
1. Ataque de texto cifrado escolhido (Chosen-ciphertext attack, CCA1): Nesse tipo de ata-
que o adversário possui acesso ao decifrador que decifra outros textos cifrados dife-
rentes do criptograma que lhe interessa. O objetivo aqui é garantir que uma cifra pos-
sua segurança mesmo que alguns textos em claro correspondentes a certos textos 
cifrados pela mesmatenham sido disponibilizados para um adversário. O decifrador 
pode ser, na prática, implementado através de suborno de uma pessoa responsável 
pela operação da maquina de ciframento, por exemplo. É importante ressaltar que 
em criptologia deve-se desenvolver sistemas criptográficos assumindo-se que o adver-
sário possui acesso à descrição completa dos algoritmos de ciframento e deciframen-
to, o que é conhecido como o Princípio de Kerckhoff, que expressa que a segurança 
de um criptossistema deve depender apenas da segurança de sua chave. Deve-se 
procurar seguir o princípio de Kerckhoff ao construir um criptossistema, uma vez que 
um adversário sempre pode roubar um dispositivo criptográfico e utilizar engenharia 
reversa, ou reconstruir um dispositivo de ciframento baseado apenas em pares de 
texto em claro/texto cifrado.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
14
3 Criptografia Simétrica
Esquemas de ciframento simétrico podem ser desenvolvidos a partir de diferentes técnicas 
e conceitos. Exemplos de cifras simétricas são o one-time pad, cifras de bloco e cifras de fluxo.
3.1 Sigilo Perfeito: O One Time Pad
Um dos grandes desafios no desenvolvimento de criptossistemas está relacionado a como 
definir e medir a segurança deste sistema. O estudo científico da segurança de criptossiste-
mas se deu início com o trabalho de Claude Shannon [1]. Entre outros trabalhos relevantes de 
Shannon encontra-se o uso de álgebra booleana na análise de circuitos digitais, criando o que 
é chamado hoje de chaveamento lógico. Um trabalho posterior de Shannon, A Mathematical 
Theory of Communication [2], que iniciou uma área que conhecemos hoje como Teoria da In-
formação, descreve a medida da informação por dígitos binários, que representam alternativas 
de sim/não, e que é a base fundamental das telecomunicações existentes hoje em dia.
Shannon também provou que uma cifra proposta por Gilbert Vernan, um pesquisador 
da AT&T, é um esquema de ciframento perfeito, isto é, um esquema que garante o sigilo da 
mensagem até mesmo contra os adversários mais poderosos. Este esquema é conhecido 
como o One-Time Pad. Sem perda de generalidade, o one-time pad será descrito por men-
sagens binárias {0,1}.
Suponha que ambos agentes, remetente e destinatário, possuem uma cópia de uma sequ-
ência aleatória de 0’s e 1’s (a chave). O remetente, Alice, pode cifrar a mensagem combinando-a 
com a chave através de um ou-exclusivo bit a bit. A operação de ou-exclusivo será denotada 
pelo símbolo , e é caracterizada pelas seguintes relações:
•	 0 0=0
•	 0 1=1
•	 1 0=1
•	 1 1=0.
Em termos gerais, quando dois termos da operação forem iguais, o resultado é zero. Quan-
to dois termos da operação forem diferentes o resultado é um. Ainda, observe que quaisquer 
que sejam as mensagens a e b, sempre é sempre verdade que:
•	 a b b = a.
Voltando ao one-time pad, Alice cifra a mensagem M, usando uma chave aleatória K, ge-
rando um texto cifrado C, da seguinte maneira:
C = M K
Onde é a operação de Ou-Exclusivo, realizada bit a bit em cada um dos bits da mensagem.
Ao receber o texto cifrado C, que é igual a M K, Bob, o destinatário, pode facilmente 
recuperar a mensagem M, realizando a seguinte operação:
M= C K,
•	 Isto é sempre verdade porque, como já dissemos, se a b b = a. então M = M K K.
Este processo é ilustrado na Figura 13.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
15
Figura 13. O one-time pad.
Observe que ambos, texto em claro e chave, possuem o mesmo tamanho. O one- time pad 
é completamente seguro quanto ao sigilo, caso o texto cifrado, formado pelo ou-exclusivo 
da mensagem com a chave aleatória seja completamente aleatório. Porém, para garantir este 
completo sigilo, a chave deve ser usada somente uma única vez, pois se a mesma chave for 
reutilizada para cada nova cifragem o atacante poderá o ou-exclusivo destes diferentes cripto-
gramas, cancelando assim a chaves comum, e recuperar alguma informação acerca das mensa-
gens em questão (sabendo, por exemplo, se as duas mensagens cifradas com a mesma chave 
são idênticas ou nao). Na verdade, se as mensagens cifradas com a mesma chave possuírem 
um grau de redundância elevado, é factível recuperar cada uma delas a partir do ou-exclusivo 
das mesmas. Para realizar uma nova cifragem de uma mensagem, Alice e Bob devem gerar 
uma nova chave completamente aleatória.
A restrição acima, e o fato da chave ter que ser do mesmo tamanho da mensagem, fa-
zem do one-time pad um esquema de criptografia não-prático. Sua utilização fica restrita à 
situações que exigem uma comunicação com o mais alto nível de segurança. Por exemplo. O 
one-time pad era usado na comunicação entre a Casa Branca, em Washington, e o Kremlin, em 
Moscow, para cifrar as comunicações do famoso telefone vermelho.
Shannon não somente provou que o one-time pad garantia sigilo perfeito, como também 
provou que qualquer criptossistema com sigilo perfeito deve possuir chave do mesmo tama-
nho da mensagem a ser transmitida. Isso faz com que criptossistemas com sigilo incondicional 
sejam muito custosos e de difícil uso.
Contudo, em um cenário realista, é comum considerar que os adversários possuem res-
trições computacionais quando atacando sistemas criptográficos. Em outras palavras, pode-se 
considerar a existência de tarefas computacionais que são difíceis de serem realizadas por um 
adversário. Essa idéia é usada no que é chamado de criptossistemas com segurança computa-
cional. Nesse tipo de criptossistema, a segurança é baseada na dificuldade de realizar algumas 
operações computacionais.
No caso de criptografia simétrica as principais cifras com segurança computacional que 
estudaremos são as cifras de bloco e as cifras de fluxo.
3.2 Cifras de Bloco
Cifras de bloco são os criptossistemas simétricos mais utilizados. Esse tipo de cifra age 
cifrando blocos de texto em claro e transformando-os em texto cifrado. Dois importantes pa-
râmetros de uma cifra de bloco são o tamanho da chave e o tamanho dos blocos com o qual a 
cifra opera. Duas importantes técnicas utilizadas na construção de cifras simétricas são permu-
tação e substituição. A seguir, encontram-se detalhes sobre cada uma das técnicas.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
16
3.2.1 Permutação
Em uma permutação, as letras de uma mensagem são simplesmente reordenadas, crian-
do um anagrama. Nesse tipo de criptossistema, as regras de transposição compõem a chave. 
Pode-se ver facilmente que, para mensagens muito curtas, essa técnica não é segura, pois ao 
reordenar, obtém-se um número pequeno de possibilidades de mensagens “embaralhadas”. 
Contudo, com o aumento do número de caracteres, o número de possibilidades de mensagens 
desorganizadas aumentam exponencialmente, tornando impossível recuperar a mensagem 
sem saber a chave. Um alto nível de segurança é atingido ao utilizar transposição aleatória, 
porém para que seja eficiente, as regras de transposição devem seguir um sistema direto, o 
que restringe muito o conjunto de possíveis chaves.
Figura 14 - Exemplo de Permutação.
3.2.2 Substituição
Além da transposição, outra técnica muito utilizada para a construção de cifras é a subs-
tituição. Em cifras de substituição, cada caracter da mensagem é substituído por um outro ca-
racter do mesmo alfabeto. Caracteres podem ser substituídos individualmente ou em grupos. 
Um exemplo trivial de substituição é ordenar os caracteres de um alfabeto em pares, aleato-
riamente, e substituir as letras de uma mensagem por seus pares determinados na ordenação 
aleatória. Por exemplo, as letras da primeira linha podem ser substituídas pelas letras da se-
gunda linha na Tabela 1.
Texto em Claro A B C D E F G H I J K L M
Texto Cifrado Q W E R T Y U I O P A S D
Texto em Claro N O P Q R ST U V X W Y Z
Texto Cifrado F G H J K L Z X C V B N M
Tabela 1: Uma tabela de substituição.
Para um texto em claro com a mensagem “Iloveyou”, o texto cifrado seria “osgctngx”. O 
primeiro documento que se teve notícia de usar cifras de substituição é o famoso “Guerras 
da Gália”, escrito por Caesar. O mais famoso sistema usado por Caesar foi a Cifra de Caesar. 
Nesse sistema o remetente substitui cada letra do texto em claro por uma letra que está três 
posições à frente no alfabeto. Por exemplo, a letra A é substituída pela letra D, B pela letra E, e 
assim por diante. Pode-se ver facilmente que este sistema é fácil de ser atacado. Se o alfabeto 
é composto por 25 letras, o número de possíveis chaves é 25, e, portanto, quebrar este siste-
ma por um simples método de tentativa e erro é plausível, mesmo sem usar um computador. 
Observa-se que uma condição necessária para um criptossistema ser seguro quanto ao sigilo, 
é que o mesmo possua um espaço de chaves possíveis grande. Porém, essa condição não é 
suficiente. Por exemplo, uma técnica de substituição genérica baseada numa chave binária 
com comprimento de 30 digitos possui um espaço de chaves contendo 2ˆ30 (dois elevado à 
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
17
trigésima potência) possíveis chaves, um número da ordem de 1 bilhão. Mesmo usando que se 
use uma chave grande, uma forma de se quebrar uma cifra de substituição é usar um método 
conhecido como análise de frequência. Em análise de frequência, a frequência em que aparece 
cada caracter do texto cifrado é computada e comparada com a frequência em que aparecem 
caracteres em um texto normal na língua em que o texto em claro foi escrito. A proximidade 
entre as frequências dos caracteres do texto em claro e do texto cifrado indicam prováveis 
regras de ciframento e deciframento. Isto é, mesmo que a chave criptográfica seja grande, um 
sistema completamente baseado em cifra de substituição é bastante susceptível a ataques.
Outro famoso exemplo de cifra de substituição é o usado no sistema Enigma, o sistema de 
ciframento usado por Nazistas Alemães durante a Segunda Guerra Mundial. A grande inova-
ção do Enigma foi de implementar um algoritmo criptográfico em uma máquina. Este era o fim 
da era da criptografia de papel e lápis. O Enigma era um grande avanço em muitos aspectos, 
uma vez que tornou possível o ciframento de grandes quantidades de documentos em um 
espaço muito curto de tempo. Além disso, algoritmos mais complicados, e mais seguros, po-
deriam ser implementados. O Enigma era um máquina de ciframento formidável e complexa, 
ilustrada na Figura 15.
Figura 15 – O sistema criptográfico Enigma. Fonte: Wikipédia.
O Enigma foi lançado como produto comercial em 1923, e foi produzida por um alemão 
chamado Arthur Scherbius com o objetivo de suprir a necessidade do comércio de comunica-
ções seguras. Era um dispositivo de fácil manuseio, onde após ajustá-lo para uso, o operador 
digitava o texto em claro da mensagem. Cada vez que uma tecla era apertada, uma letra em 
um painel era acesa, e essa letra corresponderia à letra do texto cifrado. O operador simples-
mente anotava o texto cifrado, e assim continuava até o fim da mensagem.
Os alemães viam o Enigma como um sistema criptográfico praticamente inquebrável. E 
eles estavam errados. A cifra usada na implementação do Enigma, e os procedimentos que 
este utilizava para cifrar mensagem, continham várias fragilidades, as quais foram exploradas 
pelos oponentes dos alemães para investigar táticas e estratégias secretas do exército alemão.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
18
3.2.3 Difusão/Confusão
Em seu trabalho, Shannon afirma que bons criptossistemas devem proporcionar confusão 
e difusão. Confusão tenta garantir uma relação entre o texto em claro e o texto cifrado que seja 
a mais complicada possível. A difusão significa que a influência de cada bit do texto em claro 
no texto cifrado deve ser a mais distante possível, e assim resultando em um texto cifrado com 
propriedades estatísticas aparentemente não relacionadas ao texto em claro. Shannon tam-
bém propôs que se combinasse cifras simples e talvez inseguras na construção de um sistema 
criptográfico, e assim obter criptossistemas mais fortes e potencialmente mais seguros, com 
boas propriedades de confusão e difusão. Essas cifras construídas através da combinação de 
cifras mais simples são conhecidas como cifras produto. Uma forma trivial de implementar tais 
cifras seria cifrando uma mensagem múltiplas vezes, cada vez utilizando uma chave distinta. O 
deciframento seria feito de forma similar, porém na ordem inversa.
3.2.4 Redes SP
O conceito de cifras produto é utilizado no que é conhecido como redes SP, onde S re-
presenta substituição e P permutação. Em uma rede SP, a cada passo a mensagem é subs-
tituída e permutada. As substituições são executadas por algoritmos denominados S-boxes, 
que consistem em tabelas de consulta que mapeiam n bits em m bits (onde muitas vezes n 
e m são iguais). Geralmente, bits da chave são usados para determinar qual substituição será 
empregada ao texto em claro. Os algoritmos S-boxes aumentam a confusão do texto cifrado. 
As permutações são ferramentas muito utilizadas para misturar bits (aumentando a difusão). 
Permutações são operadores lineares, e, portanto, não são suficientes para garantir sigilo. Con-
tudo, quando usados com bom algoritmos S-boxes não-lineares, permutações são de grande 
importância para a segurança, uma vez que essas ferramentas propagam a não-linearidade 
uniformemente por todos os bits. Estes conceitos estão ilustrados na Figura 16.
Figura 16 Uma cifra de Redes-SP.
Diversas cifras modernas possuem sua estrutura baseada em redes-SP.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
19
3.2.5 Estrutura Básica
A maioria das cifras de bloco utilizadas atualmente são baseadas em redes-SP. Em particu-
lar, a rede Feistel é uma interessante rede-SP. A rede Feistel é composta por diversos passos. A 
cada passo, um bloco de dados é utilizado como entrada e é gerado um bloco de saída do mes-
mo tamanho. Os passos basicamente repetem as mesmas operações. Inicialmente, a mensa-
gem é dividida ao meio. A segunda parte da mensagem é usada como entrada de uma função 
não-linear F (onde geralmente depende da chave secreta usada no processo de ciframento). 
A saída da função não-linear é então somada (operação de ou-exclusivo, por se tratar de bits) 
à primeira metade da mensagem. A saída de operação de ou-exclusivo será a segunda parte 
do bloco de saída. A primeira parte do bloco de saída será uma repetição da segunda parte do 
bloco de entrada. Esse procedimento é ilustrado na Figura 17.
Figura 17. Redes Feistel
Assim como a função F é usada para aumentar a confusão de um texto cifrado, o swapping 
(inversão da primeira e segunda metades) é utilizado para aumentar a difusão.
3.2.6 Modos de Uso
Existem várias formas de cifrar utilizando cifras de bloco. Abaixo, uma lista dos modos 
mais utilizados.
•	 Electronic Codebook Book (ECB), onde a mensagem é dividida em blocos independen-
tes de tamanho igual ao utilizado pela cifra de bloco, e depois os blocos são todos 
cifrados com uma única chave, conforme ilustra a Figura 18.
Figura 18: Cifra de Bloco no Modo ECB.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
20
•	 Cipher Block Chaining (CBC) (Veja Figura 19), onde a mensagem também é divida em 
blocos, porém nesse caso, na operação de ciframento há uma ligação entre os blocos 
e um vetor de inicialização. Isto é, um vetor de inicialização (uma cadeia de bits), com 
tamanho igual ao tamanho utilizado na cifra de bloco é cifrado. É feita uma operação 
de ou-exclusivo entre esse bloco cifrado e um bloco de texto em claro, e o resultado 
é cifradomais uma vez resultando em um novo bloco de texto cifrado. Esse processo 
se repete até que todos os blocos de texto em claro estejam cifrados.
Figura 19 – Cifra de Bloco no modo CBC
•	 Cipher FeedBack (CFB) (Veja figura 20), onde mensagem é vista como uma cadeia de 
bits, adicionada à uma cadeia de bits gerada pela cifra de bloco a partir de um vetor 
de inicialização. O ciframento procede da seguinte forma. O vetor de inicialização é 
cifrado e o resultado é somado (operação de ou-exclusivo) ao primeiro de texto em 
claro gerando o primeiro bloco de texto cifrado. O bloco de texto cifrado é então 
cifrado novamente, e o resultado é somado com o segundo bloco de texto em claro, 
onde o resultado será um feedback para o próximo estágio. 
Figura 20 - Cifra de Bloco no modo CFB.
•	 Output FeedBack (OFB), onde mensagem é tratada como uma cadeia de bits, assim 
como no modo CFB, porém no OFB o feedback é independente da mensagem. Isto é, 
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
21
um valor de inicialização é cifrado e depois somado ao primeiro bloco de texto em 
claro. Para gerar um segundo bloco de texto cifrado, o valor de inicialização cifrado 
é cifrado mais uma vez e o resultado é somado ao segundo bloco de texto em claro. 
Esse processo se repete até que todos os blocos de texto em claro estejam cifrados.
Cifras de Bloco no modo ECB são inseguras, uma vez que o ciframento de blocos idênticos 
de texto em claro resultam em blocos idênticos de texto cifrado. Os modos CBC e CFB são mais 
seguros, contudo, se existirem erros durante o processo de transmissão do texto cifrado, esses 
erros se propagam ao longo do processo de deciframento, para todos os blocos subsequentes.
3.2.7 DES
Indiscutivelmente, a mais famosa cifra de bloco é o DES, abreviação para Digital Encryp-
tion Standard. O DES foi o primeiro algoritmo proposto por uma agência oficial de um governo, 
e neste caso foi a NSA (National Security Agency) pertencente ao governo dos Estados Unidos.
O DES é uma cifra de bloco com blocos de tamanho de 64 bits, e utiliza chaves de 56 bits. 
O mesmo algoritmo é usado com a mesma para converter o texto cifrado em texto claro. O DES 
consiste de 16 passos de operações que combinam os dados e a chave de maneira determina-
da usando as operações fundamentais de permutação e substituição. A maior parte das cifras 
de bloco usadas atualmente consistem em redes SP, e o DES não é exceção.
De fato, o DES pode ser visto como uma rede Feistel. O objetivo é “embaralhar” comple-
tamente os dados e a chave, de forma que qualquer bit do texto cifrado dependa de todos os 
bits do texto em claro e de todos os bits da chave (Uma string de 56 bits, para o DES). O DES 
é suscetível à procura de chave por exaustão através de computadores modernos e hardware 
com objetivos específicos. O DES é ainda forte o suficiente contra a maioria dos hackers e in-
divíduos, porém é quebrado facilmente através de hardware especial criado por organizações 
com acesso à supercomputação, como governo, grandes organizações criminosas ou grandes 
corporações.
Um variante do DES, o Triple-DES (também conhecido como 3DES) é baseado em usar o 
DES três vezes com chaves diferentes. O Triple-DES é mais forte que o DES padrão e é conside-
rado uma cifra segura, porém, é mais lento comparado a algumas cifras de bloco modernas.
3.2.8 AES
O Advanced Encryption Standard (AES) foi o nome escolhido para o substituto do DES. O 
AES foi selecionado entre inúmeros criptosistemas submetidos por candidatos a uma consulta 
pública efetuada pelo National Institute of Standards and Technology (NIST). A cifra escolhida, o 
Rijndael, foi proposta pelos pesquisadores Belgas Rinjmen and Daemen.
O Rijndael é uma cifra de com blocos de 128 bits, e três possibilidades de tamanhos de 
chaves, 128 bits, 192 bits e 256 bits (esses parâmetros foram especificações do NIST). Apesar 
de ser baseado em uma arquitetura de rede SP, o Rijndael não é baseado em redes Feistel. O 
número de passos depende do tamanho da chave. São 10 passos se a chave é de 128 bits, 12 
se é uma chave de 192 bits, e 14 se a chave for de 256 bits.
O Rijndael é aparentemente resistente a todos os ataques conhecidos contra cifras de blo-
cos. Até o presente momento, não há nenhum ataque mais eficiente que busca de chave por 
exaustão para o Rijndael. A Figura 21 apresenta a estrutura básica do Rijndael.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
22
Figura 21 - Estrutura Básica do Rijndael – AES.
3.3 Cifras de Fluxo
3.3.1 O que são as Cifras de Fluxo?
Cifras de fluxo são algoritmos de ciframento simétrico que atuam bit a bit do texto em 
claro. Essas cifras são semelhantes ao one-time pad, contudo, ao invés de fazer uma operação 
de ou-exclusivo entre a mensagem e uma sequência de bits perfeitamente aleatória , cifras de 
fluxo operam através de ou-exclusivo a mensagem e uma sequência de bits pseudo-aleatória, 
que é chamada de keystream, gerada a partir de uma pequena sequência de bits perfeita-
mente aleatória. Uma sequência é pseudo-aleatória se for computacionalmente impraticável 
para um adversário distinguir a sequência pseudo-aleatória de uma sequência perfeitamente 
aleatória. O processo de deciframento procede operando, através de ou-exclusivo, o texto ci-
frado e o keystream. Cifras de bloco também podem ser usadas como cifras de fluxo quando 
usados os modos CFB e OFB. Cifras de fluxo são geralmente categorizadas em síncronas e 
auto-sincronizáveis.
•	 Cifras de fluxo síncronas: a geração do keystream pode ser independente do texto 
cifrado e do texto em claro.
•	 Cifras de fluxo auto-sincronizáveis: a geração do keystream depende dos dados e sua 
cifra. A Figura 22 ilustra um esquema genérico de cifra de fluxo.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
23
Figura 22. Esquema de uma Cifra de Fluxo.
3.3.2 Vantagens
Essa abordagem apresenta várias vantagens das cifras de fluxos, quando comparadas ao 
one-time pad e às cifras de bloco:
•	 Diferentemente do one-time pad, o tamanho da chave pode ser muito menor que o 
tamanho da mensagem a ser cifrada.
•	 A operação de ciframento é muito rápida, e geralmente cifras de fluxo são muito mais 
rápidas que as cifras de blocos.
•	 Não há propagação de erro, isto é, se partes do texto cifrado forem corrompidas du-
rante a transmissão, isto não afetará as partes não corrompidas.
Observe que as cifras de fluxo não são basaedas nos princípios de confusão e difusão 
criados por Shannon.
3.3.3 Observações sobre Segurança de Cifras de Fluxo 
(Sigilo)
Existem algum pontos que devem ser ressaltados ao estudar as cifras de fluxo:
•	 Se a chave for usada mais de uma vez, o sistema pode ser comprometido, uma vez 
que o adversário, se capturar mensagens, possuirá dois textos cifrados que foram 
cifrados com a mesma chave, e assim ele pode computar o ou-exclusivo dos dois 
textos cifrados e obter como resultado o ou-exclusivo das duas mensagens em claro. 
Utilizando-se métodos estatísticos apropriados e assumindo um certo grau de redun-
dância presente nas mensagens em questão, pode-se separá-las facilmente.
•	 Outro detalhe a ser observado é que todas as cifras de fluxo são periódicas, isto é, a 
cifra repete a saída do keystream após um tempo. Assim, ao cifrar mensagens muito 
grandes, tem-se o mesmo efeito de usar a mesma chave duas vezes. O período da 
repetição depende do desenho da cifra de fluxo.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
24
3.3.4 Alguns Exemplos Reais
Aqui, são apresentados alguns exemplos de cifras de fluxo que foram propostas e postas em uso:
•	 RC4: É um algoritmo proposto por Ron Rivest (um dos criadores do RSA). O algoritmo 
é muito simples, e não há resultados de cripto-análise eficiente conhecidos.
•	 SEAL:Desenvolvido por Phil Rogaway e Don Coppersmith. Este algoritmo expande 
uma chave aleatória de tamanho 160 e uma string n de 32 bits, em uma sequência 
pseudo aleatória de até 65kbytes.
3.4 Funções de Hash e Aplicações
3.4.1 Definições
Funções de hash são componentes fundamentais de criptossistemas modernos. Elas pos-
suem aplicações em identificação de usuários, na garantia de autenticidade e integridade no 
contexto de criptografia simétrica e assimétrica. Um função de hash criptográfica, também 
conhecida como função de hash one-way, mapeia uma entrada arbitrária em uma saída de 
tamanho constante. Em termos gerais, uma função de hash one-way de possuir as seguintes 
propriedades:
•	 Qualquer mensagem de tamanho arbitrário pode ser uma entrada;
•	 O tamanho da saída é fixo, um valor constante;
•	 É relativamente fácil computar a saída a partir de uma dada entrada;
•	 Para uma dada saída da função, é difícil encontrar a entrada correspondente, uma vez 
que a função é one-way;
•	 Não deve ser factível do ponto de vista computacional descobrir entradas distintas 
que produzam saídas idênticas.
3.4.1 Aplicações
Uma das principais aplicações de funções de hash é na garantia de integridade e autenti-
cidade no contexto de criptossistemas simétricos.
Seja o seguinte cenário: Alice e Bob compartilham uma chave simétrica denominada CHA-
VE e desejam garantir a integridade a autenticidade de uma mensagem a ser enviada de Alice 
para Bob. Uma maneira de conseguir tal objetivo é Alice enviar para Bob a mensagem “m” se-
guida por HASH(CHAVE, mensagem) onde HASH denota uma função de hash criptográfica e a 
virgula denota a operação de concatenação. HASH(CHAVE, mensagem) é denominado código 
de autenticação de mensagem (ou MAC do inglês message authentication code). Ao receber 
“m” Bob computa por conta própria HASH(CHAVE, mensagem) e verifica se o valor obtido é 
igual ao enviado por Alice. Caso seja diferente isso significa que alguém alterou a mensagem 
no decorrer da transmissão. A idéia aqui, sumarizada nas Figuras 23 e 24, é que somente gerará 
um código de autenticação de mensagens correto aquela parte que conhecer CHAVE.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
25
Figura 23. Integridade e Autenticação (Parte 1).
Figura 24 –Integridade e Autenticação (Parte 2).
Uma outra aplicação de grande relevância prática de funções de hash é nos sistemas de 
identificação de usuários do tipo “login/password”.
Uma maneira de implementar determinado sistema de identificação em um computa-
dor, por exemplo, seria armazenar no computador em questão todas as senhas de todos os 
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
26
usuários e exigir que as senhas sejam digitadas pelos usuários no momento da identificação. 
Assim o sistema poderia comparar a senha digitada com a senha armazenada. Uma obvia vul-
nerabilidade desse tipo de solução é a necessidade de armazenar todas as senhas. Isto possi-
bilita que um adversário roube o arquivo de senhas e comprometa totalmente a segurança do 
sistema de identificação em questão. Com o uso de funções de hash podemos implementar 
uma solução mais segura. Ao invés de armazenar as senhas do usuário, armazenaríamos o 
hash das senhas. Um usuário que quer se identificar para o sistema deveria digitar a sua senha. 
O sistema, por sua vez, calcularia o hash da senha e compararia o resultado com o o hash da 
senha original que foi armazenado. Assim, caso caia nas mãos de um adversário, o arquivo de 
hash de senhas seria inútil. Esta solução foi adotada nos sistemas operacionais UNIX, conforme 
ilustra a Figura 25.
Figura 25 – Uso de hashes para guarda de senhas em sistemas UNIX.
Outro uso das funções de hash ocorre nos chamados “One-Time Passwords” (OTP) tam-
bém conhecidos como Hash de Lamport, em homenagem ao seu criador. Estes mecanismos 
são muito empregados no contexto de acesso bancário pela internet. Neste caso, o banco for-
nece ao usuário um dispositivo que contem uma senha secreta. Ao usar este dispositivo para 
acessar o sistema bancário pela primeira vez, o dispositivo fornecerá ao usuário o resultado de 
n (onde n é um parâmetro pré-acordado do sistema) aplicações repetidas de uma função de 
hash criptográfica usando como entrada a senha. Esta valor será fornecido ao banco. O banco 
por sua vez realizará as mesmas operações que foram efetuadas pelo dispositivo (também 
conhecido como token), ou seja calculará o resultado da aplicação repetida de uma função de 
hash sobre a senha pré-compartilhada, caso o resultado seja igual ao apresentado pelo usuáio 
ele será identificado com sucesso e terá acesso ao sistema. Na segunda vez em que o usuário 
for se autenticar, o mesmo procedimento será realizado, porem, nao mais n vezes, mas n-1 ve-
zes. A idéia é que computar as funções de hash em uma direção é fácil, dado o conhecimento 
da senha, porem inverter a função de hash seria impraticável para um adversário. Este sistema 
permite que n autenticações sejam feitas. Depois de n autenticações deve-se trocar a senha.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
27
Figura 26 – Uso de One-Time-Passwords.
A seguir serão apresentados conceitos básicos de criptografia de chave pública, assinatu-
ras digitais, alguns conceitos matemáticos necessários, e modelos adversariais.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
28
4 Criptografia de Chave Pública
4.1 Motivação
No mundo das redes abertas, como é o caso da internet, o sigilo de dados a serem trans-
mitidos não pode ser garantido usando somente esquemas simétricos. Isto é, para que seja 
possível a troca de dados sigilosos entre agentes que não se conheceram previamente os usu-
ários não devem ser obrigados a compartilhar uma chave em comum como usada em esque-
mas de criptografia simétrica. Ocorre que se os usuários distantes não puderem, usando um 
canal inseguro, estabelecer a chave de forma segura, algum adversário pode de forma ilegal 
obter a chave, e dessa forma, ter acesso à mensagem. Uma das melhores soluções práticas para 
este problema é utilizar criptografia de chave pública, onde um remetente cifra uma mensa-
gem (ou uma chave de sessão) usando apenas as informações públicas do destinatário.
4.2 A Proposta de Diffie e Hellman
A idéia da criptografia de chave pública (usando algoritmos assimétricos) foi proposta por 
Diffie e Hellman em um trabalho pioneiro em 1976, onde as chaves para cifrar e decifrar eram 
conhecidas como chave pública e chave privada, respectivamente. A idéia revolucionária dos 
autores foi estabelecer uma troca segura de mensagens entre o remetente e o destinatário, sem 
que os agentes nunca tivessem se encontrado para estabelecer uma chave secreta comum.
Criptografia de chave pública pode ser modelada de seguinte forma: em uma situação 
onde Bob tem a intenção de enviar uma mensagem à Alice, primeiramente, Alice gera uma 
chave pública, que é publicada em seu nome em um diretório público acessível a qualquer 
usuário, e também gera uma chave privada, a qual é função matemática da chave pública, mas 
está acessível somente a ela. Para mandar uma mensagem secreta a Alice, Bob procura a chave 
de Alice no diretório público, Bob então cifra a mensagem usando a chave pública. O texto 
cifrado resultante será enviado a Alice através de um canal público, por exemplo, Internet. 
Finalmente, ao receber o texto cifrado, Alice poderá decifrar e recuperar a mensagem usando 
sua chave secreta (ver Figura 27). O mecanismo de ciframento de chave pública é baseado na 
dificuldade de resolver certos tipos de problemas matemáticos, por exemplo, fatoração de 
inteiros e logaritmo discreto, e isso garante que seria necessário um tempo muito grande para 
que se pudesse encontrar a chave privada a partir da chave pública somente.Figura 27. Criptossistema de Chaves Públicas
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
29
Até o momento, diversas técnicas de criptografia de chave pública foram desenvolvidas 
de forma intensa, o que resultou em diferentes níveis de eficiência e segurança. Um dos pro-
gressos mais importantes é o relacionado ao tópico de segurança demonstrável, que é a segu-
rança onde pode ser rigorosamente provada a impossibilidade de um adversário quebrar um 
criptossistema, enquanto este adversário não for capaz de resolver um problema matematica-
mente difícil.
Antes, aproximações heurísticas eram constantemente utilizadas para analisar a seguran-
ça de esquemas criptográficos, isto é, se ninguém fosse capaz de quebrar o esquema após 
muitos anos, então sua segurança era amplamente aceita. Contudo, essa abordagem está sen-
do substituída pela abordagem de segurança demonstrável. Segurança demonstrável vem 
se tornando uma condição indispensável para criptossistemas padrão, e assim, a maioria dos 
criptossistemas atuais atendem a essa condição. Posteriormente nessa seção, será analisada a 
segurança demonstrável em detalhes.
4.3 Vantagens da Criptografia de Chave Pública
Observa-se que uma das maiores vantagens da criptografia de chave pública é o estabe-
lecimento de comunicação segura utilizando apenas dados publicamente acessíveis. Ainda, o 
número de chaves correspondente a cada parceiro de comunicação que um usuário precisa 
administrar em esquemas convencionais é reduzido de forma significante ao utilizar cripto-
grafia de chave pública, onde um usuário precisa guardar apenas sua própria chave privada.
À primeira vista, parece que em todos os aspectos a criptografia de chave pública é supe-
rior à criptografia de chave privada. Contudo, isso não é sempre verdade. Umas das desvanta-
gens da (atual) criptografia de chave pública é sua velocidade: esses tipos de criptossistemas 
demanda muitos recursos computacionais e o tamanho da mensagem é significantemente 
limitado. A melhor solução é, portanto, uma combinação das vantagens da criptografia con-
vencional e da criptografia de chave pública. Isto é, não é prático cifrar a mensagem inteira 
usando apenas criptografia de chave pública. É mais sensato usar criptografia de chave pública 
para cifrar a chave de uma sessão de trabalho, de natureza temporária, a qual então será uti-
lizada como uma chave simétrica comum entre o remetente e o destinatário, enquanto eles 
estabelecem a sessão de trabalho.
4.4 Assinaturas Digitais
Uma conseqüência do conceito de criptografia de chaves públicas é a idéia de assinatu-
ras digitais. Conforme explicado anteriormente, uma chave pública e uma chave privada são 
atribuídas a cada agente no contexto de criptografia de chaves públicas. A chave privada é 
usualmente empregada para decifrar mensagens cifradas com a chave pública. No entanto, a 
mesma pode ser usada para “cifrar” uma mensagem quando o objetivo em vista é autenticida-
de e não confidencialidade. Quando uma determinada parte, por exemplo Alice, deseja provar 
a outras partes que é a originadora de uma determinada mensagem, ela “cifra” a mensagem 
em questão com sua chave privada resultando em uma assinatura digital. A assinatura digital 
pode ser verificada por qualquer parte que conheça a chave pública de Alice. Por exemplo, se 
Bob recebe a mensagem mais a respectiva assinatura de Alice, ele pode verificar se a assinatura 
foi realmente criada por Alice ou não. Assumindo que Bob conhece a chave pública de Alice, 
ele pode aplicar a chave publica de Alice a assinatura recebida. A chave pública cancela a ope-
ração feita pela sua respectiva chave privada. Logo, se a assinatura for realmente produzida 
por Alice, o resultado desse processo de verificação deve ser a mensagem original.
Na maioria dos esquemas de assinatura digital, geralmente a transação de assinatura ini-
cia gerando resumo da mensagem usando função de hash one-way. Em vez de computar a as-
sinatura da própria mensagem, um resumo da mensagem é usado para gerar assinaturas. Isso 
porque é muito mais fácil computar assinaturas a partir de resumo de mensagens comparadas 
às mensagens originais, que podem ser muito longas.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
30
Figura 28 – Assinatura Digital: Idéia Básica.
4.5 Certificados Digitais e Autoridades Certificadoras
Uma hipótese implícita em toda a nossa argumentação acerca de criptografia de chaves 
públicas é de que as chaves públicas de seus respectivos usuários são conhecidas. Essa é uma 
hipótese que não se reflete na prática. Dessa forma é importante instalar mecanismos que 
garantem a relação entre a chave pública e a identidade de uma determinada pessoa. Uma 
solução prática que tipicamente é usada para este problema é registrar uma terceira parte con-
fiável, para ambos remetente e destinatário, conhecida como autoridade certificadora (CA), 
responsável por determinar a relação entre a identidade de uma parte e a sua respectiva chave 
pública. A CA garante que o vínculo entre a identidade de um agente e certifica que a chave 
pública atribuída a ele no banco de dados público realmente a ele pertence. Uma vez que a Au-
toridade Certificadora verifica a correta associação entre a identidade de um usuário e sua cha-
ve pública, a CA emite um certificado. Um certificado é um relatório computacional que atesta 
a ligação entre uma chave pública e um agente (indivíduo ou uma entidade). Este relatório é 
assinado pela autoridade certificadora. É importante frisarmos que assume-se que a chave pú-
blica da autoridade certificadora é conhecida por todos os seus usuários. Se o destinatário qui-
ser verificar se é válida a associação entre o remetente e sua chave pública, o destinatário pode 
verificar a assinatura digital da autoridade certificadora diretamente no certificado anexado. 
A CA deve ser uma terceira parte imparcial, com uma reputação estabelecida, e que adota um 
conjunto de medidas de segurança de elevadíssimo grau, para que os certificados emitidos 
possuam credibilidade confiável. A Figura 29 apresenta, de forma conceitual, um certificado 
emitido por uma autoridade certificadora. Note que o certificado contém três elementos:
•	 Dados sobre a identidade do agente ou usuário, que pode ser um sítio web, por 
exemplo cegsic.unb.br.
•	 A chave criptográfica pública, referente ao agente ou usuário.
•	 A assinatura digital da autoridade certificadora, que atesta que a chave criptográfica 
pertence ao usuário indicado.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
31
Figura 29. Visão abstrata de um certificado emitido por uma Autoridade Certificadora.
Um certificado contém o nome do remetente, sua chave pública, um numero de série, 
data de validade, e assim por diante, e mais importante, contém a assinatura digital da Autori-
dade Certificadora, de forma que o destinatário possa verificar que o certificado é verdadeiro. 
O conceito de assinatura digital é discutido na seção 2.16. De forma concreta, o modelo de 
certificado digital atualmente em uso da Web é o X.509. O protocolo X 509 especifica que in-
formações devem constar no certificado digital, tais como cifras utilizadas, prazo de val;idade 
do certificado, numero serial do mesmo, identificação da autoridade certificadora etc.
Em redes de grande escala, a certificação de chaves públicas pode ser considerada muito 
onerosa, e uma única CA pode não ser suficiente para controlar a emissão de certificados e ve-
rificação de identidades para todos usuários. Considere, por exemplo, que 25% da população 
mundial tem acesso a internet, e à medida que aumenta o comércio eletrônico, bilhões de con-
versações seguras precisam ser estabelecidas entre os sítios web de comércio eletrônico e seus 
clientes. Apesar desse problema parecer se resolver com o uso demúltiplos CAs, é difícil de ad-
ministrar vários CAs (confiáveis) simultâneamente. A principal solução vigente é construir um 
sistema hierárquico de autoridades certificadoras. Tipicamente, redes hierárquicas de CAs são 
construídas da seguinte forma: uma CA raiz serve para sublicenciar CAs pais, as quais emitem 
certificados da mesma maneira para seus CAs filhos. Cada CA filho gera certificados para um 
pequeno subgrupo de usuários, que podem servir como nós para a hierarquia completa. Essa 
estrutura hierárquica tem estabelecido interrupção mínima para os serviços de autenticação 
de certificados.
No caso específico do Brasil, o governo criou uma infra-estrutura de chaves públicas 
composta por autoridades certificadores organizadas de maneira hierárquica denominada 
ICP-Brasil. A autoridade certificadora raiz é mantida pelo Instituto Nacional de tecnologia da 
Informação. A AC raiz assina os certificados de autoridades certificadoras de níveis inferiores. A 
ICP-Brasil foi constituída pela medida provisória 2.200-2 de 24 de agosto de 2001.
4.6 Segurança na WEB: O protocolo TLS/SSL
Apresentaremos nesta seção como os conceitos até agora discutidos podem ser reunidos 
para implementar uma tarefa relativamente complexa: a garantia de segurança nas comunica-
ções que ocorrem na World Wide Web (WWW).
No contexto das comunicações WEB, usualmente, temos um cliente (aquele que inicia a 
conversação) e um servidor (aquele que recebe a primeira mensagem da conversação). O pro-
tocolo TLS (Transport Layer Security) é a versão atual do protocolo SSL (Secure Sockets Layer) 
e foi criado com o objetivo de prover sigilo, integridade e autenticidade as comunicações WEB.
O protocolo TLS consiste de duas fases. A primeira fase é denominada fase de Handshake 
enquanto a segunda fase é conhecida como fase Record. Explicaremos brevemente estas duas 
fases, com o auxílio das Figura 30, 31 e 32.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
32
Figura 30 – Handshake no protocolo TLS.
Na fase handshake o cliente (normalmente um navegador ou browser) envia, inicialmente 
uma mensagem contendo um numero aleatório Nc, uma lista como o nome do conjunto de 
cifras simétricas e assimétricas por ele suportadas (denominadas de suite) bem como indica a 
versão do protocolo suportada.
O servidor (por exemplo, um servidor de um website bancário) responde enviando um 
numero aleatório Ns, o conjunto de cifras suportadas pelo servidor bem como o seu certificado 
digital, contendo sua identidade S e sua chave pública Pks. O certificado digital é assinado por 
uma autoridade certificadora válida.
Ao receber o cetificado digital do servidor normalmente o cliente (navegador do usuário) 
verificará a assinatura digital do mesmo para determinar a sua validade. As chaves públicas das 
principais autoridades certificadoras encontram-se disponíveis nos principais navegadores do 
mercado. Neste momento, o usuário recebe uma mensagem informando que a assinatura di-
gital do certificado foi validade e se concorda em utilizar o certificado digital em questão. A 
Figura 31 ilustra esta situação.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
33
Figura 31 – Sucesso na verificação de uma assinatura digital.
Caso o usuário concorde em utilizar o certificado em questão, o navegador (cliente) esco-
lhera uma função de hash, uma cifra simétrica e um criptossistema de chave pública compatí-
veis com as cifras suportadas tanto pelo navegador quanto pelo servidor.
Uma vez escolhidas essas cifras, o navegador cifrara uma chave de sessão simétrica 
(Secret_C) com a chave pública do servidor.
A chave de sessão estabelecida no Handshake será utilizada na próxima fase do protocolo 
TLS, denominada de Record.
Na fase de Record, quando uma mensagem deve ser trocada pelo cliente e servidor, os 
seguintes passos são executados:
1. Inicialmente esta será segmentada
2. A mensagem é então comprimida com algum algoritmo de compressão de dados;
3. Calcula-se um código de compressão de mensagem para cada segmento baseado na 
chave de sessão acordada na fase de Handshake.
4. Cifra-se a mansagem concatenada com o código de autenticação de mensagem.
5. Adiciona-se um cabeçalho ao criptograma resultante do passo 4.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
34
Figura 32 – Fase Record do TLS.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
35
5 Conceitos Matemáticos de Criptografia 
de Chave Pública
Esta seção faz uma breve revisão alguns conceitos matemáticos relacionados à criptogra-
fia de chave pública, visando aprofundar a discussão da seção anterior. Suponha que Bob envie 
uma mensagem a Alice utilizando criptografia de chave pública. Seja m a mensagem, c seu 
correspondente texto cifrado, skAlice a chave privada do destinatário e pkAlice sua chave pública. 
Como c é calculado usando m e pkAlice, c pode pode ser representado matematicamente como 
c=fpkAlice(m), onde fpkAlice(x) é uma função de ciframento que depende de pkAlice. Note que, em 
um sistema de criptografia de chave pública prático, um valor aleatório é também escolhido 
por Bob, e esse valor também será usado para calcular c. Uma condição necessária (porém não 
suficiente) para que se tenha um criptossitema de chave pública seguro, é garantir que a chave 
privada do destinatário, fpkAlice(x), tenha a seguinte propriedade: deve ser significantemente di-
fícil calcular x0 a partir de fpkAlice(x0) para todo x0. Pode-se ver como um processo fácil de se fazer, 
porém muito difícil, ou até mesmo impossível de se desfazer. Um tipo de função que satisfaz 
essa condição é chamado de funções one-way ou de mão única(Alice é capaz de quebrar a ca-
racterística one-way usando sua chave privada skAlice, mais precisamente, fpkAlice(x) deve ser uma 
função trap-door one-way. ou função de mão única com alçapão )
Todos os criptossitemas de chave pública práticos são baseados em funções (trap-
-door) one-way. A seguir um exemplo de como as funções one-way são geralmente 
usadas em criptografia de chave pública.
Definimos a função módulo para inteiros a, b da seguinte maneira: sejam a,b,c, inteiros, 
a mod b = c onde c é o resto da divisão de a por b. Defina fg,p(x)=g
xmod p. Uma função f7,11(x) é 
expressa como f7,11(x)= 7
xmod 11 e para x=1,2,…,10 esta função é eficientemente calculada da 
seguinte forma:
f7,11(1)=7 mod 11=7
f7,11(2)=f(1)*7 mod 11=5
f7,11(3)=f(2)*7 mod 11=2
f7,11(4)=f(2)*f(2) mod 11=3
f7,11(5)=f(2)*f(3) mod 11=10
f7,11(6)=f(3)*f(3) mod 11=4
f7,11(7)=f(3)*f(3)*7 mod 11=6
f7,11(8)=f(2)*f(3)*f(3) mod 11=9
f7,11(9)=f(3)*f(3)*f(3) mod 11=8
f7,11(10)=f(3)*f(3)*f(3)*7 mod 11=1
Contudo, temos o seguinte problema: para um y0, calcular x0 tal que y0= f7,11(x0). Pode-se 
observar que é muito mais difícil de obter a resposta neste caso. De fato, não se conhece ne-
nhum método eficiente para resolver este problema popularmente conhecido como o proble-
ma do logaritmo discreto. Imediatamente, pode-se calcular f7,11(4) para ser 3, porém não é fácil 
calcular x0 onde f7,11(x0)=3 (talvez para o problema acima, a maneira mais rápida seria produzir 
uma tabela de possíveis pares de x e f7,11(x), para todo x).
O problema do logaritmo discreto é o problema de encontrar o inverso de fg,p(x), e este 
problema tem um papel importante em diversos esquemas criptográficos. A diferença no cus-
to computacional para fg,p(x) e para seu inverso aumenta significantemente à medida que os 
parâmetros aumentam. Para um cenário de parâmetros grandes, pode-se assumir que a fun-
ção fg,p(x) é uma função one-way. Em termos gerais, computar o inverso de fg,p(x) é considerado 
impraticável quando um p de tamanho de 1024 bits (ou maior) é selecionado (juntamente com 
outros parâmetros escolhidos apropriadamente). Por causa de suanatureza intratável, a cons-
trução de funções one-way é possível, onde essas são o coração de esquemas de criptografia 
de chave pública.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
36
Assim como o problema do logaritmo discreto, o problema de fatoração de inteiros é conside-
rado um problema difícil: sejam p e q primos grandes, e n = p*q, então, para um dado n, encontrar 
p e q é considerado uma tarefa difícil. Esse problema se torna extremamente difícil à medida que 
o tamanho dos números aumentam. Criptossitemas RSA são baseados no problema de fatoração 
de inteiros, o que implica em o RSA ser quebrado ao se resolver a fatoração de inteiros envolvida.
5.1 Acordo de Chaves Diffie-Hellman
O acordo de chaves Diffie-Hellman [3] foi a primeira solução para o problema de distribui-
ção de chaves, permitindo que duas partes, as quais nunca haviam se encontrado, acordassem 
uma chave secreta usando somente discussões que podem ser publicamente vistas. Protoco-
los de acordo de chaves são diferentes de protocolos de ciframento de chave pública, no sen-
tido em que eles não são feitos para cifrar mensagem, mas sim usados para que partes possam 
entrar em acordo a respeito de algum segredo a ser usado para cifrar mensagens.
Até o momento foram desenvolvidos muitos algoritmos práticos e seguros que permitem 
o acordo de chaves , e a técnica do acordo de chaves Diffie-Hellman é uma das propostas 
clássicas e ainda é utilizada em muitas aplicações. A Figura 33 sumariza alguns elementos do 
Protocolo Difie-Hellman.
Suponha que Alice e Bob queiram entrar em acordo a respeito de alguma chave secreta 
usando o protocolo de acordo de chaves Diffie-Hellman. Primeiramente, Alice gera sua chave 
secreta, escolhendo aleatoriamente um valor, xAlice entre 1 e p-2, onde p é um número primo 
grande. De forma semelhante, bob gera sua chave secreta, xBob. Então, para algum parâmetro 
público apropriado g (isto é, g é um “gerador” de um grupo cíclico de ordem p-1 pertencente a 
{1,2,…,p-1}), Alice e Bob calculam suas chaves públicas, yAlice = fg,p(xAlice) e yBob= fg,p(xBob), respec-
tivamente. Procedem trocando suas chaves públicas entre si. Finalmente, Alice computa K= f 
yBob,p(xAlice) e Bob computa K’= f yAlice,p(xBob) . Como K=K’, Alice e Bob podem usar essa chave como 
uma chave secreta segura para cifrar suas comunicações nessa sessão.
Atualmente o melhor método conhecido para quebrar o protocolo de acordo de chaves Diffie-
-Hellman é resolvendo o problema de logaritmo discreto relacionado, que acredita-se ser one-way.
Figura 33 – Protocolo Diffie-Hellman.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
37
5.2 Criptossistema RSA
O criptossistema Rivest-Shamir-Adleman (RSA) [4] é um dos métodos de ciframento de 
chave pública mais aceitos atualmente. O algoritmo RSA é baseado na dificuldade de fatorar 
números inteiros muito grandes.
O RSA usa aritmética modular e teoria de números básica para realizar alguns cálculos.
O algoritmo procede da seguinte maneira: Alice escolhe dois primos grandes p e q e com-
puta n=p*q. Posteriormente, Alice calcula l , que é o mínimo múltiplo comum de p-1 e q-1. 
Então Alice seleciona aleatoriamente um inteiro e tal que 1 < e < l onde e e l são primos entre 
si. Alice também calcula d tal que e*d = 1 mod l (esse procedimento pode ser eficientemente 
realizado por técnicas matemáticas conhecidas). A chave pública de Alice é o par n e e, e sua 
chave privada é d.
Para cifrar uma mensagem m, onde m não pode ser maior que n-1, Bob (o remetente) 
calcula o texto cifrado c da seguinte forma:
c = me mod n
E, Bob envia c a Alice.
Para decifrar c, Alice computa
cd mod n = m
A segurança do criptossistema RSA é baseada na dificuldade do problema de fatoração de 
inteiros (isto é, acredita-se que é extremamente difícil fatorar números inteiros muitos grandes, 
formados por 100 a 200 dígitos). Se um adversário é capaz de fatorar n em p e q e computar a 
chave de deciframento d, seu ataque é considerado bem sucedido. A descoberta de d é consi-
derado o pior cenário, isto é, o adversário será capaz de ler todas as mensagens cifradas com a 
chave pública e ainda falsificar assinaturas. Como nenhum outro método para determinar d sem 
fatorar n é conhecido, um n grande o suficiente deve ser usado para garantir a segurança do RSA. 
Atualmente, n de tamanho de 1024 bits são recomendados para uso em sistemas práticos.
A seguir, apresentamos uma noção mais forte de segurança para o RSA. A Implementação 
“livro texto” do RSA, que é a implementação direta do algoritmo, é considerada insegura por 
causa da seguinte observação: mesmo que seja impossível de quebrar a característica one-way 
do RSA, ainda é possível obter certas informações sobre a mensagem a partir do texto cifrado.
Como um exemplo extremo, considere o caso onde um adversário saiba que Bob vai enviar 
uma mensagem do tipo sim/não para Alice. O adversário pode facilmente descobrir a mensagem 
ao obter o texto cifrado que Bob enviou a Alice e comparando-o com o texto cifrado gerado a 
partir do ciframento da palavra sim utilizando a chave pública da Alice. Se esses dois textos cifra-
dos forem idênticos, sem mesmo nunca ter decifrado nada, o adversário saberá que a mensagem 
transmitida era sim, e se os texto cifrados forem diferentes, o adversário saberá que a mensagem 
era não. Outra situação, um adversário pode ter a permissão de gerar qualquer texto cifrado 
(com exceção do texto cifrado alvo ) e pedir para Alice para decifrar e ainda ver o correspondente 
texto em claro. Se isso for possível, o adversário pode obter o texto em claro correspondente ao 
texto cifrado alvo, sem mesmo pedir a Alice para decifrar o texto cifrado alvo. Esse tipo de mode-
lo de ataque é conhecido como ataque de texto cifrado escolhido (chosen ciphertext attack, CCA).
Inicialmente, desenvolvedores não consideraram proteger seus sistemas contra ambientes 
de fortes ataques. Contudo, no final dos anos 90, foi mostrado por Daniel Bleichenbacher do Bell 
Labs, Lucent Technologies que um adversário é de fato capaz de efetuar tais tipos de ataques em 
criptossistemas reais. Ele ainda encontrou uma falha em um tipo de protocolo baseado no RSA, que 
é o tipo de criptossistema mais utilizado no ciframento e deciframento de dados. Proteção contra 
ataques como os ataques CCA atualmente possui grande importância, e novos criptossistemas são 
implementados de forma mais segura do que costumavam ser. Criptossistemas RSA, por exemplo, 
atualmente são complementados com Optimal asymmetric encryption padding (OAEP) [5] que é um 
tipo de envelope digital, um conhecido método para intensificar a segurança.
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
38
5.3 Criptossistema ElGamal
O criptossitema ElGamal [6] é um criptossistema de chave pública baseado no problema 
do logaritmo discreto. O acordo de chaves Diffie-Hellman, também é baseado na dificuldade 
do problema do logaritmo discreto. Contudo, o acordo de chaves não é um esquema de ci-
framento de chaves pública. Por outro lado, o criptossistema de ElGamal cryptosystem é uma 
versão modificada do acordo de chaves Diffie-Hellman e também possui funcionalidade de 
ciframento de chave pública.
O algoritmo de ciframento do criptossistema de ElGamal tem sua natureza semelhante ao 
acordo de chaves Diffie-Hellman. Considere que Bob envie uma mensagem a Alice, Primeira-
mente Alice escolhe aleatoriamente sua chave secreta x (não maior que p-2, onde p é um primo 
grande). Alice então calcula, para um g apropriado, sua chave pública y= fg,p(x) , e a publica.
Para cifrar uma mensagem m (mais uma vez, m não pode ser maior que p-1), Bob procura 
pela chave pública da Alice y= fg,p(x), e escolhe uma chave aleatória one-time, r (não maior que 
p-2), e calcula o correspondente texto cifrado {c1, c1}