Sistemas Distribuı́dos: Conceitos e Projeto
Criptografia Assimétrica e Funções Hash
Francisco José da Silva e Silva
Laboratório de Sistemas Distribuı́dos (LSD)
Departamento de Informática / UFMA
http://www.lsd.ufma.br
2 de julho de 2013
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
1 / 26
Sistemas Criptográficos Assimétricos
As chaves para criptografar e descriptografar são diferentes mas
juntas formam um par único;
Existe uma chave para criptografar, KE e outra para descriptografar,
KD tal que P = DKD (EKE (P))
No sistema assimétrico uma chave é mantida privada e a outra é
tornada pública. KA+ denota a chave pública pertencente a A e KA−
sua chave privada.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
2 / 26
Sistemas Criptográficos Assimétricos
O uso das chaves pública e privada varia de acordo com a finalidade
requerida:
Se Alice deseja enviar uma mensagem confidencial a Bob ela deve
usar a chave pública de Bob para criptografar a mensagem;
Se Bob deseja ter certeza que uma mensagem recebida tenha sido
escrita por Alice, ela deve criptografar a mensagem com sua
chave privada.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
3 / 26
Sistemas Criptográficos Assimétricos: Requisitos
Deve ser computacionalmente fácil para um usuário B gerar um par
de chaves pública e privada (KB+ pública; e KB− privada);
Deve ser computacionalmente fácil para um usuário A, conhecendo a
chave pública de B e a mensagem m, produzir o texto criptografado
C = EK + (m)
B
Deve ser computacionalmente fácil para o receptor B descriptografar
o texto criptografado usando a sua chave privada e obter a mensagem
m = DK − (C ) = DK − [EK + (m)]
B
B
B
Deve ser computacionalmente inviável para um oponente, conhecendo
a chave pública KB+ , determinar a correspondente chave privada KB−
Deve ser computacionalmente inviável para um oponente, conhecendo
a chave pública KB+ e o texto criptografado C , recuperar o texto
original m
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
4 / 26
Sistemas Criptográficos Assimétricos: Requisitos
Os algoritmos de criptografia e descriptografia podem ser aplicados
em qualquer ordem, ou seja: m = EK + [DK − (m)]
B
B
O segredo de obtenção de algoritmos que satisfaçam estes requisitos é
a descoberta de uma função que seja fácil de se calcular, porém seja
computacionalmente inviável se calcular a sua inversa a menos que se
tenha alguma informação adicional.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
5 / 26
Sistemas Criptográficos: RSA
RSA (Rivest, Shamir, Adleman);
Muito utilizado em sistemas criptográficos assimétricos;
Baseado nos seguintes fatos matemáticos:
Calcular o resto da divisão de uma exponenciação com um número
não-primo muito grande é fácil. Isto é, o cálculo de C ≡ M e mod n
O inverso
√ do problema anterior é difı́cil. Isto é, o cálculo de
M ≡ e C mod n
Se a fatoração desse número não-primo é conhecida, o problema
anterior torna-se fácil
Sistemas assimétricos são computacionalmente muito mais complexos
que sistemas simétricos (100 a 1000 vezes);
Por isto, muitos sistemas criptográficos utilizam RSA para troca de
chaves compartilhadas de forma segura e utilizam criptografia
simétrica para criptografar os dados.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
6 / 26
Sistemas Criptográficos: Parâmetros RSA
Chave pública: {e, n}
Chave privada: {d}
Encriptação: C ≡ M e mod n
Desencriptação: M ≡ C d mod n = (M e )d mod n = M ed mod n
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
7 / 26
Funções Hash
Uma função hash H recebe uma mensagem de tamanho arbitrário m
como entrada e produz um bit string h de tamanho fixo: h = H(m)
Funções hash utilizadas em sistemas criptográficos devem possuir as
seguintes propriedades:
Serem funções não reversı́veis (one way ): é computacionalmente
inviável encontrar a entrada m que corresponde a uma saı́da h
conhecida. Por outro lado, é fácil computar h a partir de m;
Dadas uma entrada m e sua saı́da h = H(m), é computacionalmente
inviável encontrar outra entrada diferente, m′ 6= m, tal que
H(m) = H(m′ );
Dado somente H, é computacionalmente inviável encontrar quaisquer
dois valores de entrada diferentes, m e m′ , tal que H(m) = H(m′ ).
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
8 / 26
Função Hash MD5
Função hash (Rivest) para computar um message digest de 128 bits, dada
uma entrada de tamanho arbitrário.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
9 / 26
Autenticação Usando Chaves Pública e Privada
1
Alice envia um desafio a Bob encriptado com KB+ . Somente Bob pode
descriptografar a mensagem utilizando sua chave privada KB− ;
2
Bob retorna o desafio de Alice, seu próprio desafio (RB ) e a chave de seção a ser
utilizada (KA,B ), encriptados por KA+ ;
3
Somente Alice pode descriptografar a mensagem utilizando sua chave privada KA− .
Ela retorna a Bob seu desafio encriptado pela chave de seção KA,B .
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
10 / 26
Integridade e Confidencialidade de Mensagens
Além de autenticação, um canal seguro deve também garantir a
integridade e confidencialidade das mensagens;
Confidencialidade é facilmente obtida criptografando-se as mensagens
antes de enviá-las.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
11 / 26
Assinaturas Digitais
Considere que Bob vendeu a Alice uma coleção de discos por R$
500,00 e que a negociação se deu através de email;
No final, Alice envia a Bob uma mensagem de confirmação do
negócio no valor estipulado (R$ 500,00);
Além da autenticação, duas questões relacionadas à integridade da
mensagem devem ser garantidas:
1
2
Alice necessita ter certeza que Bob não irá maliciosamente alterar os
R$ 500,00 constantes de sua mensagem e alegar que ela prometeu um
valor maior;
Bob necessita ter certeza que Alice não irá negar que ela enviou a
mensagem de confirmação do negócio.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
12 / 26
Assinatura Digital Usado Criptografia de Chave Pública
Alice não pode negar o fato de ter enviado m se a assinatura for genuı́na;
Alice está protegida de modificações de m por Bob, porque Bob terá que
provar que uma versão modificada de m foi assinada por Alice;
Uma desvantagem desta abordagem é que a mensagem inteira deve ser
criptografada com a chave privada de Alice (KA− ), o que caro;
Uma outra abordagem é utilizar um message digest, conforme
ilustrado a seguir.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
13 / 26
Assinatura Digital Usado Message Digest
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
14 / 26
Outras Questões
Alguns problemas com estas abordagens:
A assinatura de Alice é válida enquanto a chave privada for mantida
secreta. Alice poderia argumentar que teve sua chave privada roubada;
Se Alice decide trocar de chave privada (o que pode ser útil para
atrapalhar intrusos), suas mensagens enviadas a Bob tornam-se inúteis.
O que necessitamos nestes casos é de uma autoridade central que
controle as mudanças de chave.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
15 / 26
Certificação de Chaves Públicas
Através da criptografia de chaves públicas é possı́vel que duas
entidades troquem mensagens secretas sem ter que trocar chaves
secretas;
Assim, a criptografia de chaves públicas evita a necessidade de
infraestrutura de KDC;
No entanto, as entidades comunicantes ainda têm de trocar chaves
públicas.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
16 / 26
Certificação de Chaves Públicas: Exemplo
Considere uma transação comercial pela Internet onde Alice entrega
pizzas para viagem e Bob envia uma mensagem a ela que inclui sua
assinatura digital. Alice pode obter a chave pública de Bob e verificar
a assinatura, se certificando que foi ele que fez o pedido;
No entanto, a intrusa Trudy envia uma mensagem a Alice dizendo ser
Bob, fornecendo o endereço de Bob e solicitando uma pizza;
Ela também anexa uma assinatura digital, mas assina o resumo da
mensagem com sua chave privada;
Ela se faz passar por Bob, enviando a Alice sua chave pública mas
dizendo que pertence a Bob;
Alice aplicará a chave pública de Trudy (pensando ser de Bob) e
concluirá que realmente foi ele que fez o pedido...
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
17 / 26
Trudy se Passa por Bob Usando Criptografia de Chaves
Públicas
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
18 / 26
Certificação de Chaves Públicas
As entidades necessitam ter certeza que possuem a chave pública da
entidade com a qual estão se comunicando;
A vinculação de uma chave pública a uma entidade particular é feita,
tipicamente, por uma autoridade certificadora (CA - Certification
Authority) que possui as seguintes incumbências:
1
2
Verifica se uma entidade (pessoa, roteador, etc) é quem diz ser;
Cria um certificado que vincula a chave pública da entidade à
identidade verificada. O certificado contém a chave pública e a
informação exclusiva que identifica o proprietário da chave pública
(como o nome de alguém ou um endereço IP).
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
19 / 26
Bob Obtém um Certficado da CA
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
20 / 26
Certificados
A chave pública e o identificador da entidade são assinados por uma
autoridade certificadora cuja assinatura é enviada também no
certificado;
Assume-se que a chave pública da autoridade certificadora (denotada
+
) é conhecida. Por exemplo, a chave pública de diversas
por KCA
autoridades certificadoras estão embutidas na maioria dos
navegadores Web.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
21 / 26
Utilizando Certificados
Quando Alice recebe o pedido de Bob, ela obtém o certificado de
Bob;
Alice usa a chave pública da CA para verificar a validade do
certificado de Bob assinado pela CA;
Desta forma, Alice pode ter certeza que está realmente tratando com
Bob.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
22 / 26
Tempo de Vida de Certificados
Se a chave privada de uma dada entidade for comprometida, nenhum
cliente deve poder utilizar a chave pública correspondente;
Neste caso, necessitamos de um mecanismo que revogue o
certificado, tornando público que ele não é mais válido;
Uma abordagem para este problema é fazer com que a autoridade
certificadora publique regularmente uma lista de revogação de
certificados (CRL - Certificate Revogation List);
Sempre que o cliente for verificar um certificado, ele deve buscar a
CRL para ter certeza que o certificado não foi revogado;
Uma outra abordagem possı́vel é definir um tempo de vida ao
certificado. Caso o certificado deva ser revogado antes do seu prazo
de expiração, a entidade certificadora pode publicar uma CRL. No
entanto, esta abordagem forçaria novamente o cliente a
buscar a CLR ao verificar um certificado.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
23 / 26
Tempo de Vida de Certificados
Uma última solução extrema é reduzir o tempo de vida do certificado
a zero. Ou seja, o cliente terá que sempre contactar a entidade
certificadora para verificar a autenticidade de uma chave pública;
Na prática, certificados são emitidos com tempo de vida limitados.
No caso de aplicações na Internet este tempo é usualmente de um
ano. CLRs são também publicadas regularmente mas elas são
raramente consultadas.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
24 / 26
Padrões para Autoridades Certificadoras
Tanto a International Telecommunication Union (ITU) quanto a IETF
desenvolveram padrões para autoridades certificadoras;
Na recomendação ITU X.509 encontramos a especificação de um
serviço de autenticação, bem como uma sintaxe especı́fica para
certificados;
O RFC 1422 descreve um gerenciamento de chaves baseado em CA
para utilização com e-mail seguro pela Internet.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
25 / 26
Campos Selecionados de uma Chave Pública X.509 e RFC
1422
versão: número da versão da especificação X.509
número de série: identificador exclusivo emitido pela CA para um
certificado;
assinatura: especifica o algoritmo utilizado pela CA para assinar o
certificado;
nome do emissor: identidade da CA que emitiu o certificado;
perı́odo de validade: inı́cio e fim do perı́odo de validade do certificado;
nome do sujeito: identidade da entidade cuja chave pública está
associada a este certificado;
chave pública do sujeito: a chave pública do sujeito, bem como uma
indicação do algoritmo de chave pública a ser usado
com esta chave.
Francisco Silva (UFMA/LSD)
SD: Princı́pios e Algoritmos
2 de julho de 2013
26 / 26