>> Gestão da Segurança da Informação e Comunicações >> 2009-2011
Anderson Clayton do Nascimento
GSIC250
CRIPTOGRAFIA E INFRAESTRUTURA DE
CHAVES PÚBLICAS
VERSÃO 1
Dilma Rousseff
Presidente da República
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
CEGSIC
Coordenação
Jorge Henrique Cabral Fernandes
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
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.
Este material é distribuído sob a licença creative commons
http://creativecommons.org/licenses/by-nc-nd/3.0/br/
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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
3
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
[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
4
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 Information 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 Cryptology, 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 comitê de programa do IX Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais e será o coordenador geral da XI edição do mesmo evento.
5
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Resumo
A disciplina de criptografia e infra-estrutura de chaves públicas introduz ao aluno conceitos elementares de criptografia presentes nas soluções de segurança de sistemas de informaçã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 principais 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.
6
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
1 Introdução
A criptografia tem como um dos seus objetivos principais prover a troca de mensagens secretas 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 criptografia 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 esquemas 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.
7
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 compartilhada 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 chave, 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 implemen2
Uma chave criptográfica é uma sequencia de caracteres (bits, números, letras etc).
8
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 criptossistema por uma engrenagem (é um algoritmo), a parte do sistema criptográfico ou do criptosistema (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, é operado 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 transformar 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.
9
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 criptografia do ponto de vista de suas cifras, como ilustra a Figura 7.
Figura 7. Criptossistema gené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:
Ek (m)
e o deciframento do texto cifrado acima com uma chave Kb por um algoritmo de deciframento D( ) por:
m = Dkb ( Ek (m))
2.5 Tipos de Criptossistemas
Um esquema como o representado na Figura 6 é chamado de cryptosystem ou criptossistema. 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 operam 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 assimé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 estabelecer uma comunicação segura. Uma chave é pública, e a outra chave é secreta. Embora haja
10
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 assimétricas. São diferentes, mas uma é função matemática da outra.
Na criptografia de chave pública, dadas suas características matemá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 pessoas que não se conhecem podem estabelecer uma comunicação segura
através de um canal inseguro, sem que tenham compartilhado previamente de uma chave criptográfica. Uma construção prática de criptossisFigura 8 – Um par de temas de chave pública foi proposta por um grupo de pesquisadores do
chaves assimétricas.
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, criptossistemas 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-desprezível de informação acerca da mensagem transmitida. No cenário da Figura 9, Eva não consegue obter informação significativa mesmo que tenha acesso aos pacotes de informação trocados 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 texto 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).
11
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 enviada por Alice, e por mais ninguém. Não-repúdio impossibilita um remetente de uma mensagem 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 conseqüê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 sistemas 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.
12
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 é criptografado 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 ataque o adversário possui acesso ao decifrador que decifra outros textos cifrados diferentes do criptograma que lhe interessa. O objetivo aqui é garantir que uma cifra possua segurança mesmo que alguns textos em claro correspondentes a certos textos
cifrados pela mesma tenham 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 adversário possui acesso à descrição completa dos algoritmos de ciframento e deciframento, 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.
13
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 criptossistemas 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 Informaçã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 mensagens 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. Quanto 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, gerando 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.
14
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 criptogramas, cancelando assim a chaves comum, e recuperar alguma informação acerca das mensagens 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, fazem 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 tamanho 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 restriçõ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 computacional. 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 parâ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 permutação e substituição. A seguir, encontram-se detalhes sobre cada uma das técnicas.
15
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
3.2.1 Permutação
Em uma permutação, as letras de uma mensagem são simplesmente reordenadas, criando 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 substituição. Em cifras de substituição, cada caracter da mensagem é substituído por um outro caracter 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, aleatoriamente, 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 segunda linha na Tabela 1.
K
L
M
U I
O P A
S
D
S
T
U
V
X W Y
Z
L
Z X
C
V B
M
Texto em Claro
A
B
C
D
E
F
G
Texto Cifrado
Q
W
E
R
T
Y
Texto em Claro
N
O
P
Q
R
Texto Cifrado
F
G
H
J
K
H
I
J
N
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 sistema 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 à
16
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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, poderiam 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 simplesmente 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.
17
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 també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 representa substituição e P permutação. Em uma rede SP, a cada passo a mensagem é substituí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. Contudo, 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.
18
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
3.2.5 Estrutura Básica
A maioria das cifras de bloco utilizadas atualmente são baseadas em redes-SP. Em particular, 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 mesmo tamanho. Os passos basicamente repetem as mesmas operações. Inicialmente, a mensagem é 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 independentes 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.
19
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
•
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
é cifrado mais 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 é,
20
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 Encryption 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 determinada 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” completamente 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 indiví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 é considerado 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 blocos. 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.
21
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 perfeitamente 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 cifrado 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.
22
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 durante 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 redundâ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.
23
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 possuem 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 autenticidade no contexto de criptossistemas simétricos.
Seja o seguinte cenário: Alice e Bob compartilham uma chave simétrica denominada CHAVE 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” seguida 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.
24
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 computador, por exemplo, seria armazenar no computador em questão todas as senhas de todos os
25
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 vulnerabilidade desse tipo de solução é a necessidade de armazenar todas as senhas. Isto possibilita 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) també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 fornece 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 vezes. 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.
26
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Figura 26 – Uso de One-Time-Passwords.
A seguir serão apresentados conceitos básicos de criptografia de chave pública, assinaturas digitais, alguns conceitos matemáticos necessários, e modelos adversariais.
27
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 transmitidos 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 esquemas 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 mensagem (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
28
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 progressos mais importantes é o relacionado ao tópico de segurança demonstrável, que é a seguranç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 matematicamente 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á sendo 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 estabelecimento 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 criptografia 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 é superior à criptografia de chave privada. Contudo, isso não é sempre verdade. Umas das desvantagens 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 convencional 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á utilizada 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 assinaturas 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 é autenticidade 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 operaçã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 inicia gerando resumo da mensagem usando função de hash one-way. Em vez de computar a assinatura 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.
29
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 confiá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 Autoridade Certificadora verifica a correta associação entre a identidade de um usuário e sua chave 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 quiser 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.
30
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 Autoridade 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 informaçõ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 verificaçã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 conversaçõ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 de múltiplos CAs, é difícil de administrar 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 protocolo 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.
31
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 digital do certificado foi validade e se concorda em utilizar o certificado digital em questão. A
Figura 31 ilustra esta situação.
32
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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) escolhera 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.
33
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Figura 32 – Fase Record do TLS.
34
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
5 Conceitos Matemáticos de Criptografia
de Chave Pública
Esta seção faz uma breve revisão alguns conceitos matemáticos relacionados à criptografia 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 difí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 caracterí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)=gxmod p. Uma função f7,11(x) é
expressa como f7,11(x)= 7xmod 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 nenhum método eficiente para resolver este problema popularmente conhecido como o problema 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 custo 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 sua natureza intratável, a construção de funções one-way é possível, onde essas são o coração de esquemas de criptografia
de chave pública.
35
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Assim como o problema do logaritmo discreto, o problema de fatoração de inteiros é considerado 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. Protocolos de acordo de chaves são diferentes de protocolos de ciframento de chave pública, no sentido 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), respectivamente. 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.
36
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 computa 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 é considerado 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 cifrados 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 modelo 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.
37
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
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 ciframento 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, Primeiramente 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} da seguinte forma:
c1=gr mod p
c2=m*yr mod p
Bob envia {c1, c1} a Alice.
Para decifrar {c1, c1} Alice computa
c2 *(c1x ) −1 mod p = m
onde
(c1x ) −1 mod p é definido como (c1x ) −1 * c1x mod p = 1
Diferentemente do criptossistema RSA que envolve duas chaves, uma pública e uma secreta, o criptossistema ElGamal usa uma valor aleatório como uma terceira chave pra cifrar. A
terceira chave funciona como uma chave descartável, usada uma vez para cifrar somente uma
mensagem, e podem existir múltiplos textos cifrados para uma mesma mensagem (esse tipo
de criptossistema é conhecido como ciframento probabilístico). Apesar de ser essencial para o
funcionamento do criptossistema ElGamal, isso não aparece em outros criptossistems de chave pública e não apresenta um papel importante no conceito de criptografia de chave pública.
Contudo, isso garante que qualquer observação de textos cifrados não oferece nenhuma informação relevante a respeito do correspondente texto em claro. Por exemplo, se os possíveis
texto em claro forem somente dois: sim ou não, para um dado texto cifrado, um adversário
pode tentar adivinhar qual é o texto em claro comparando o texto cifrado com algum outro
texto texto cifrado gerado a partir do ciframento da mensagem sim. É improvável, porém, que
esses dois textos cifrados (mesmo que sejam produzidos a partir da mesma mensagem) sejam
idênticos. Dessa forma, observação de diferentes ciframentos da mesma mensagem não ajuda
o adversário a descobrir qual é a mensagem original. Contudo, o ElGamal como foi apresentado (sua versão “livro texto”ou direta), assim como o RSA quando implementado de maneira
direta, não é seguro contra ataques CCA. Mais especificamente, quando Bob envia uma mensagem cifrada {c1, c1} a Alice, uma adversário pode decifrar ilegalmente da seguinte maneira:
o adversário escolhe um valor aleatório r, e pede ao oráculo (este oráculo está presente em
alguns modelos de segurança, como segurança de texto cifrado escolhido) para decifrar {c1,r*
c1}. O oráculo enviará como resposta r*m, e então o adversário pode obter m por uma simples
divisão, r*m/r. Dessa forma, é importante levar tal problema em consideração (considerando
se é necessário ou não alcançar tal nível de segurança) ao implementar criptossistemas. Alguns
métodos que podem intensificar a segurançao criptossistema ElGamal padrão serão apresentados na próxima seção.
38
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
5.4 Segurança Necessária para Criptossistemas de Chave
Pública Práticos
Como discutido anteriormente, os criptossistemas RSA e o ElGamal padrão são vulneráveis a certos tipos de ataques, e uma implementação direta desses esquemas podem não ser
ideais em sistemas práticos. Assim, ao construir um sistema de comunicação prático baseado
no criptossistema RSA ou ElGamal padrão, são necessárias algumas modificações nesses sistemas para garantir certos níveis de segurança.
Atualmente, deseja-se satisfazer o seguinte requisito de segurança ao implementar criptossistemas de chave pública práticos: para qualquer texto cifrado, nenhum adversário deverá
obter nenhuma informação relevante sobre o texto em claro mesmo que lhe seja permitido pedir
ao destinatário decifrar qualquer texto cifrado, excluindo o texto cifrado alvo [7,8]. Isso significa
que em criptossistemas práticos de chave pública, é melhor prevenir qualquer quebra parcial
até mesmo contra os adversários mais poderosos.
Por muitos anos, tal noção tão forte de segurança em criptografia de chave pública foi
pensada ser um preocupação somente de ordem teórica, e a maioria dos desenvolvedores na
época não viram necessidade em eliminar e controlar ameaças e vulnerabilidades em nível tão
elevado de segurança ao construir criptossistemas. Contudo, no final dos anos 90, foi identificado por Daniel Bleichenbacher do Bell Labs que em situacões práticas, criptossistemas RSA
em PKCS4#1 ver 1.55 era de fato vulnerável contra ataques de texto cifrado escolhido [9]. Esse
incidente fez muitos desenvolvedores perceberem a necessidade de proteger seus sistemas
de tal ataque, e ao implementar, medidas de defesa devem ser adotadas impedindo o ataque.
O Optimal Asymmetric Encryption Padding (OAEP) é um método conhecido para codificar
mensagens e usado para incrementar criptossistemas como o RSA, e resulta em segurança
demonstrável contra ataques de texto cifrado escolhido. O OAEP pode ser pensado como um
pré-processamento antes de se cifrar com o RSA, que converte o texto em claro em uma forma
que pode ser cifrada por um ciframento RSA. O criptossistema RSA, melhorado com OAEP, tem
sua segurança demonstrável, isto é, é seguro no sentido que nenhum adversário é capaz de
nenhuma informação relevante acerca do texto em claro mesmo que lhe seja permitido ataques a texto cifrado escolhido. Atualmente o OAEP é amplamente usado na implementação do
criptossistema RSA em PKCS#1ver2.1.
Para o criptossistems ElGamal, a aplicação direta do OAEP torna-se um pouco complicada,
porém outros métodos para melhorar a segurança do criptossistema ElGamal foram propostos
[10,11]. Ao aplicar essas técnicas, é possível atingir segurança demonstrável contra o modelo
de ataques de texto cifrado escolhido (CCA) para o criptossistema de ElGamal.
5.5 Assinatura Digital
A assinatura digital é a substituta eletrônica para a assinatura feita à mão, e busca atingir
teoricamente a mesma funcionalidade da assinatura manual. É um identificador criado por um
computador, ao invés de uma caneta. Semelhantemente aos sistemas de comunicação físicos,
também é importante ser possível assinar uma mensagem de forma segura a fim de se proibir
substituição ou personificação por atacantes em sistemas de comunicação eletrônicos. Existem inúmeros métodos de assinaturas digital para uso prático, e são utilizados em vários tipos
de aplicações, como por exemplo em comércio eletrônico.
Como assinar digitalmente uma mensagem? Antes de Alice poder assinar digitalmente
uma mensagem eletrônica que pretende enviar a Bob, ela deve criar um par de chaves pública/
privada (já discutido anteriormente).
4 PKCS refere-se a um conjunto de padrões de criptografia criados e publicados pela empresa RSA
Security. Para mais detalhes ver, por exemplo, http://en.wikipedia.org/wiki/PKCS.
5 O padrão PKCS#1ver1.5 é uma versão do padrão de criptografia RSA, que foi lançado em 1993, e
ganhou grande popularidade, sendo um dos protocolos mais utilizados.
39
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
A chave privada (de assinatura) é mantida confidencial, e é usada com o propósito de criar
assinaturas digitais. A chave pública (de assinatura) é de livre acesso, onde o destinatário da mensagem assinada digitalmente pode acessá-la. Alice então seleciona uma mensagem m para ser
assinada. Sua assinatura digital SigAlice,m é gerada como uma função de sua chave privada e da
mensagem m. Ao receber a mensagem assinada digitalmente, m e SigAlice,m, Bob pode verificar
a validade da assinatura usando a chave pública da Alice. A verificação da assinatura é feita em
função de m, SigAlice,m e da chave pública de Alice. Adicionalmente, diferentemente de assinaturas
feias à mão, que s!ao únicas a cada um que assina, a assinatura digital é consistente para todos
os documentos assinados. Isto acontece porque a assinatura digital é derivada a partir do documento a ser assinado. Qualquer mudança no documento redundará em um documento diferente. As abstrações básicas no uso de assinatura digital são apresentadas na Figura 21.
Qualquer usuário é capaz de verificar assinaturas digitais, pois nenhuma informação secreta é exigida para a verificação. Quando um destinatário obtém a chave pública de alguém
de quem ele recebeu uma mensagem assinada digitalmente, como ele poderá ter certeza se,
de fato, a chave pertence a quem seria o remetente? A discussão feita até o momento possui
uma hipótese crítica, isto é, que o par de chaves pública/privada gerado pelo remetente, de
fato pertence ao remetente. Com o intuito de prevenir o ataque por substituição de uma chave
pública, a relação entre a chave pública (o par de chaves pública/privada) e a pessoa identificada de ser garantida. A solução para esse problema é recrutar uma terceira parte confiável pelo
remetente e pelo destinatário, chamada de autoridade certificadora (CA), já discutida anteriormente. A CA certifica que a chave pública pertencente a um par de chaves pública/privada
usado para criar assinaturas digitais realmente pertence a um dado usuário.
5.6 Conceitos Matemáticos
Assim como em ciframentos de chave pública, funções one-way possuem um papel importante nos mecanismos de assinatura digital. Esse fato pode ser imediatamente verificado
a partir da seguinte observação. Para uma dada mensagem m, a geração de uma assinatura
pode ser vista como uma função da chave de quem assina (Alice). Dessa forma, não é possível
recuperar a chave privada de Alice usando somente a assinatura e dados públicos. O que significa que a função de assinatura é também uma função one-way, e dessa forma, é impossível
construir esquemas de assinatura digital sem funções one-way. De forma mais precisa, foi provado que a partir de qualquer função one-way pode-se construir um esquema de assinatura
digital. Isto é, a existência de funções one-way é uma condição necessária e suficiente para a
existência de um esquema de assinatura digital seguro. Existem dois principais tipos de funções one-way que são geralmente usados em sistemas de assinatura digital. Um dos tipos são
as funções one-way algébricas que resultam na maioria das assinaturas, e essas funções são
baseadas no problema do logaritmo discreto ou no problema de fatoração de inteiros.
5.7 Esquema de Assinatura RSA
O criptossistema RSA pode ser facilmente convertido para um esquema de assinatura digital. O esquema de assinatura digital RSA é amplamente usado em diversos sistemas práticos,
como por exemplo PKCS#1.
Em um esquema de assinatura digital RSA, Alice escolhe dois números primos grandes p
e q, computa n=p*q e calcula l , que é o mínimo múltiplo comum de p-1 e q-1. Depois, Alice seleciona aleatoriamente um inteiro e tal que 1<e<l onde e e l são primos entre si. Alice também
computa d tal que e*d=1 mod l (esse procedimento pode ser realizado eficientemente por técnicas matemáticas conhecidas). A chave pública de Alice é o par n e e, e sua chave privada é d.
Para assinar uma mensagem m, Alice calcula a assinatura s de seguinte forma:
s = H(m)d mod n
onde H é uma função de hash one-way apropriada. Alice então publica m e s como sua
mensagem assinada.
40
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Ao receber m e s Bob aceita a assinatura se a seguinte equação for satisfeita:
se mod n = H(m)
Intuitivamente, com o teste acima, Bob pode confirmar que s é equivalente a H(m)d mod
n uma vez que H(m)d*e=H(m) mod n, e esse fato implica que s foi realmente gerado pela Alice,
uma vez que ela é a única a saber o valor d. Come se pode ver, o uso de funções de hash one-way é crucial nesse caso, sem as funções de hash one-way, o adversário poderia facilmente
forjar a assinatura de Alice: seja m1, s1 e m2 s2 be assinaturas válidas gerad por Alice. Usando
essas assinaturas, um adversário poderia calcular s3 = s1*s2 que seria a assinatura válida para
uma mensagem m3 = m1* m2. Deve estar claro agora o quão é indispensável o uso de funções
de hash one-way ao implementar assinaturas RSA para previnir tais ataques. Porém, isso não
implica que o esquema de assinatura RSA é seguro se uma função de hash one-way for usada
para gerar o resumo da mensagem.
De fato, em 1999, uma implementação prática da assinatura RSA, que foi padronizada
como ISO 9796-2, foi mostrada vulnerável. Desde então, segurança demonstrável contra todos
os possíveis ataques (e não apenas contra certos tipos de ataques) é desejada até mesmo para
sistemas práticos, e diversos métodos para a melhoria da segurança do esquema de assinatura
RSA tem sido propostos.
5.8 Algoritmo de Assinatura Digital (Digital Signature
Algorithm, DSA)
O Digital Signature Algorithm (DSA) é um algoritmo de assinatura digital proposto pelo
U.S. National Institute of Standards and Technology (NIST), como um padrão federal americano
(U.S. Federal Information Processing Standard, FIPS 186). A segurança do DSA é baseada no problema do logaritmo discreto.
No DSA, Alice seleciona primos p e q tal que q divide (p-1), e os tamanhos de p e q são
1024 bits e 160 bits, respectivamente. Seja g um elemento apropriado de 1,2,…,p. (mais especificamente, g é um gerador de um grupo cíclico de ordem q pertencente a {1,2,…,p}). Então
Alice escolhe aleatoriamente um inteiro x (um inteiro positivo menor que q-1) como sua chave
privada e computa y = gx mod p. A chave privada de Alice é (p,q,g,y). Ao assinar m, Alice primeiro
calcula H(m) onde H é um algoritmo de hash seguro Secure Hash Algorithm (SHA-1) que é uma
função de hash one-way. Então, Alice seleciona aleatoriamente um inteiro secreto k (um inteiro
positivo menor que q-1), e computa
r = (gk mod p) mod q
s = k-1{H(m)+ar
onde k-1 é um inteiro tal que k-1* k = 1 mod q. O par (r,s) será publicado como a assinatura
de Alice para m.
Bob recebe (m,r,s), e aceita se a seguinte equação for satisfeita:
r = gs
−1
*H ( m )
−1
y r*s mod p mod q
onde s-1 é um inteiro tal que s-1*s = 1 mod q
5.9 Segurança Necessária para Esquemas de Assinatura
Digital Práticos
Como descrito até o momento, existem muitos problemas de segurança que devem ser
considerados para estabelecer sistemas de assinaturas digitais seguros e práticos. Foi mostrado que uma implementação direta da assinatura RSA é vulnerável a certos tipos de ataques,
41
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
e ainda, não se sabe se o DSA atende a todos os requisitos de segurança de um esquema de
assinatura digital. Lembrando que, atualmente, para que um sistema de assinatura digital seja
usado em um sistema prático, deseja-se que esse satisfaça o seguinte requisito de segurança:
para qualquer mensagem, nenhum adversário deverá ser capaz de falsificar uma assinatura válida que um assinante válido não tenha gerado, mesmo que o adversário esteja permitido a pedir
ao assinante assinar qualquer mensagem que o adversário escolha [12]. O que significa que um
sistema de assinaturas prático deve prevenir qualquer existência de falsificação, até mesmo
contra os adversários mais poderosos.
De forma semelhante à discussão anterior relacionada à segurança de esquemas de ciframento de chave pública, pode ser dito praticamente o mesmo para esquemas de assinatura digital. A natureza do mecanismo da ameaça contra assinaturas digitais era muito pouco entendida, e a maioria dos desenvolvedores avaliavam seus produtos para os recentes ataques de
segurança descobertos, e não consideravam a possibilidade de tomar medidas efetivas para
impedir tais ataques. Contudo, no final dos anos 90, foi mostrado que uma implementação do
esquema de assinatura RSA, que foi padronizada como ISO 9796-2, era vulnerável a ataques de
mensagem escolhida [13].
Existem dois principais métodos para proteger e melhorar a assinatura RSA e estabelecer segurança demonstrável para o modelo de segurança acima. Um é conhecido como esquema Full Domain
Hash (FDH)[14], e o outro é conhecido como esquema probabilístico de assinaturas (PSS)[14].
Como foi provado que a assinatura RSA era vulnerável a certos ataques se o resumo de
mensagem fosse pequeno o suficiente que pudesse ser fatorado, possíveis medidas de precaução podem ser tomadas, como por exemplo aumentar o tamanho do valor do hash para ser o
maior possível. O esquema de assinatura RSA o qual a mensagem é resumida para o domínio
completo da função é chamada de esquema Full Domain Hash (FDH). A segurança da assinatura RSA com FDH pode ser provada deixando o tamanho da saída da função de hash one-way
ser de mesmo tamanho do módulo utilizado no RSA, porém, uma construção segura de uma
função de hash one-way de tal tamanho ainda não foi estudada em detalhes, e consequentemente, o FDH não é frequentemente utilizado em sistemas reais.
O PSS é um método alternativo que efetivamente acrescenta aleatoriedade a esquemas
de assinatura RSA. Para um esquema de assinatura probabilístico, haverá duas assinaturas diferentes para mesma mensagem. É uma técnica muito semelhante ao OAEP para esquemas de
ciframento de chave pública, no sentido que o PSS também pré-processa a mensagem antes
de assinar. O esquema de assinatura RSA com PSS é demonstravelmente seguro, e é geralmente usado para a implementação do criptosistema RSA em sistemas de comunicação práticos,
como por exemplo PKCS#1ver2.1.
Para o DSA, não existe nenhum método de ataque geral que possa comprometer a “não-falsificação” existente, mesmo que um adversário seja capaz de pedir ao assinante para assinar
qualquer mensagem que deseje. Sua segurança ainda não foi provada, porém ela resistiu ao
teste do tempo e atualmente é uma técnica usada e amplamente aceita.
42
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
6 Conclusões
Este texto apresentou uma introdução a criptografia e infra-estrutura de chaves públicas,
um conjunto de técnicas essenciais que são empregadas para garantia de diversas propriedades de segurança necessárias em sistemas de informação, sobretudo sigilo e integridade.
43
>> CEGSIC 2009-2011 >> Criptografia e infraestrutura de chaves públicas
Referências
[1] Shannon, C. “Communication theory of secrecy systems”, Bell System Technical Journal, Vol 28, 1949, pp.656—715
[2] Shannon, C. E., ``A mathematical theory of communication,’’ Bell System Technical
Journal, vol. 27, pp. 379-423 and 623-656, 1948.
[3] Diffie, W. and M.E. Hellman’s, “New directions in cryptography”, IEEE transactions on
Information Theory, vol 22, 1976, pp.644-654.
[4] Rivest R., A. Shamir and L. Adleman, ``A method for obtaining digital signature and
public-key cryptosystems,’’ Communication of the ACM, vol.21, no.2, 1978, pp.120126.
[5] Bellare, M. and P. Rogaway, ``Optimal asymmetric encryption,’’ Advances in Cryptology--EUROCRYPT’94, Lecture Notes in Computer Science 950, Springer-Verlag, pp.92111, 1994.
[6] ElGamal, T. ``A public key cryptosystem and a signature scheme based on discrete
logarithms,’’ IEEE Trans. on Inform. Theory, IT-31,4,1985, pp.469-472.
[7] Rackoff C. and D.R. Simon, ``Non-interactive zero-knowledge proof of knowledge
and chosen ciphertext attack,’’ Advances in Cryptology--CRYPTO’91, Lecture Notes
in Computer Science 576, Springer-Verlag, pp.433-444, 1992.
[8] Bellare M., A. Desai, D. Pointcheval and P. Rogaway, ``Relations among notions of
security for public-key encryption schemes,’’ Advances in Cryptology--CRYPTO’98,
Lecture Notes in Computer Science 1462, Springer-Verlag, pp.26-45, 1998.
[9] Bleichenbacher D., ``Chosen ciphertext attacks against protocols based on the RSA
encryption standard PKCS \#1,’’ Advances in Cryptology--CRYPTO’98, Lecture Notes
in Computer Science 1462, Springer-Verlag, pp.1-12, 1998.
[10] Cramer R. and V. Shoup, ``A practical public key cryptosystem provably secure
against adaptive chosen ciphertext attack,’’ Advances in Cryptology--CRYPTO’98,
Lecture Notes in Computer Science 1462, Springer-Verlag, pp.13-25, 1998.
[11] Fujisaki E. and T. Okamoto, ``Secure integration of asymmetric and symmetric encryption schemes,’’ Advances in Cryptology--CRYPTO’99, Lecture Notes in Computer
Science 1666, Springer-Verlag, pp.537-554, 1999.
[12] Goldwasser S., S. Micali and R. Rivest, ``A digital signature scheme secure against
chosen-message attacks, SIAM J. on Computing 17,1988, pp.281--308.
[13] Coron J.S., D. Naccache, J. Stern, ``On the security of RSA padding,’’ Advances in
Cryptology--CRYPTO’99, Lecture Notes in Computer Science 1666, Springer-Verlag,
pp.1-18, 1999.
[14] Bellare M. and P. Rogaway, ``The exact security of digital signatures - how to sign
with RSA and Rabin,’’ Advances in Cryptology--EUROCRYPT’96, Lecture Notes in
Computer Science 1070, Springer-Verlag, pp.399-416, 1996.
44