Criptografia Assimétrica

Tópicos

• Acordo de Chaves
• Encriptação Híbrida
• Criptografia de chave pública
• Primitivas

Acordo de Chaves

Criptografia simétrica tem por base um segredo partilhado entre duas entidades. No entanto, o acordo deste segredo é muito complicado aquando num canal não seguro (99% dos casos).

Problemas complicados

• Fatorização de inteiros - dado um inteiro N, encontrar a sua fatorização em números primos.
• Logaritmo discreto - dado um a e um b, encontrar x, tal que $a^x\mathrm{mod}n=b$.
• Raiz quadrada discreta - dado um y e um n, encontrar x, tal que $x^2\mathrm{mod}n=y$.

Diffie-Hellman exchange

Funcionamento

• Dois utilizadores, Alice e Bob, concordam em dois números p e g (que podem ser públicos até).

• Alice escolhe um número aleatório a e Bob escolhe um número aleatório b como chave privadas.

• Alice calcula $A=g^a\mathrm{mod}p$ e Bob calcula $B=g^b\mathrm{mod}p$.

• Alice envia A para Bob e Bob envia B para Alice.

• Alice calcula $s=B^a\mathrm{mod}p$ e Bob calcula $s=A^b\mathrm{mod}p$.

  Repare-se que $B=g^b$, ou seja, $s=B^a\equiv s=g^{b^a}\equiv s=g^{b\ast a}$. Da mesma forma, $A=g^a$ e $s=A^b\equiv s=g^{a^b}\equiv s=g^{a\ast b}$. Visto que a multiplicação é comutativa, os dois s gerados são exatamente iguais.

Ataque Man-in-the-middle

Visto que o algoritmo Diffie-Hellman não possui uma forma de garantir a autenticidade das mensagens trocadas no canal, não é possível afirmar com certeza com quem estamos realmente a comunicar. Nada impede que um adversário intercete a comunicação fazendo uso das chaves públicas de ambos os extremos.

Encriptação Híbrida

Combina a utilização de criptografia simétrica com a utilização de criptografia assimétrica. Também pode ser chamado de envelope digital.

Funcionamento

• Chave simétrica é gerada de forma aleatória.
• Mensagem é cifrada com essa chave.
• Chave gerada é cifrada com a chave pública do destinatário.
• No destino, é decifrada, com recurso à chave privada, a chave gerada aleatoriamente.
• Com recurso a essa, é decifrada a mensagem propriamente dita.

Criptografia de chave pública

Baseia-se no princípio de existir sempre um par de chaves por utilizador. Uma chave pública, que pode ser partilhada sem qualquer problema, e uma chave privada, que deve ser mantida em segredo.

Alguns exemplos

• Conteúdo cifrado com uma chave pública só pode ser decifrado com recurso à chave privada.
• Conteúdo cifrado com uma chave privada pode ser decifrada por qualquer utilizador, visto que a chave pública é, como o nome indica, pública.

Warning

Um dos maiores problemas em seguir a abordagem de cifrar mensagens com a chave pública do destinatário é que estaremos sempre a usar a mesma chave para decifrar (a privada). Se esta for comprometida, todas as mensagens anteriormente (e futuramente) trocadas são, também, comprometidas.

Primitivas

RSA

Algoritmo proposto por Ron Rivest, Adi Shamir e Leonard Adleman em 1977/8. A sua segurança é baseada na dificuldade de fatorizar inteiros - relembrar problemas complicados. O mesmo pode ser usado tanto para criptografia de chave pública como para assinaturas digitais.

Vantagens

• Segurança, já relatada no parágrafo anterior.
• Primitiva amplamente testada no mundo inteiro.

Desvantagens

• Lento para cifrar grandes quantidades de dados.
• Requer o uso de chaves cujo tamanho é muito grande.
• Não é possível (aconselhado) encriptar mensagens maiores que o tamanho da chave.

ECs

Curvas elípticas. A sua segurança é baseada na dificuldade de encontrar o logaritmo discreto - relembrar problemas complicados.

Vantagens

• Tamanhos de chave muito menores em comparação com o RSA, para o mesmo nível de segurança (256 vs 3072 bits, por exemplo).
• Mais eficiente que o RSA.

Desvantagens

• Complexidade matemática mais elevada.
• Menos compatibilidade com hardware antigo.

Referências

Secret Key Exchange (Diffie-Hellman) - Computerphile Diffie Hellman -the Mathematics bit- Computerphile