Algoritmo de criptografia Rivest, Shamir, Adleman (RSA)
usos
RSA, que recebeu o nome desses inventores, é um algoritmo de criptografia pertencente à grande família de “criptografia assimétrica”.
RSA pode ser usado para garantir:
- confidencialidade: apenas o dono da chave privada poderá ler a mensagem criptografada com a chave pública correspondente.
- não alteração e não repúdio: apenas o dono da chave privada pode assinar uma mensagem (com a chave privada). Uma assinatura descriptografada com a chave pública irá, portanto, provar a autenticidade da mensagem.
Sua robustez reside na dificuldade de fatorar um grande número.
Principais eventos
- 1978: Ronald L. Rivest, Adi Shamir e Leonard Adleman publicam "Um Método para Obter Assinaturas Eletrônicas e Chaves Públicas de Criptossistemas". Na revista mensal da Association for Computing Machinery (ACM).
- 1982: Rivest, Shamir e Adleman fundaram a empresa “RSA Data Security” (que em 2006 se tornou “RSA, The Security Division of EMC”). "Um sistema criptográfico de comunicações e método." patenteado em 1983 no Massachusetts Institute of Technology (MIT), expirou em setembro de 2000.
- 1991: publicação dos primeiros “Padrões de criptografia de chave pública” (PKCS) e abertura da “competição de fatoração RSA” (encerrada em 2007), levando o mundo da pesquisa a desenvolver métodos para fatorar chaves públicas (e, portanto, descriptografar qualquer mensagem).
- 1994: “O algoritmo de tempo polinomial para fatoração de computador quântico” por Peter Shor, teoricamente permite quebrar qualquer chave RSA. No entanto, colocá-lo em prática requer um computador quântico (o que reacendeu um grande interesse neste campo). Em 2001, a IBM teve sucesso na fatoração quântica de uma chave RSA de 15 bits (experimento repetido em 2012).
- 2000: publicação dos padrões PKCS # 15, os mais recentes até o momento (na versão 1.1).
- 2010: a chave RSA de 768 bits da competição de 1991 foi quebrada, até o momento este é o melhor resultado (conhecido publicamente) da fatoração de uma chave RSA. Em nosso país, a Referência de Segurança Geral recomenda o uso de chaves de 2048 bits para o período 2010-2021.
Implementação RSA
Isenção de responsabilidade: este artigo estabelece o princípio básico do algoritmo publicado em 1978.
Para uma implementação rigorosa, um certo número de precauções deve ser levado em consideração a fim de evitar certas vulnerabilidades (consulte os padrões mais recentes).
Alice e Bob
- Bob tem uma mensagem confidencial que deseja enviar para Alice.
- Alice constrói duas chaves:
- uma chave de criptografia pública que ela transmite a Bob.
- uma chave de descriptografia privada que mantém com cuidado.
- Bob usa a chave pública para criptografar a mensagem e a passa para Alice.
- Alice usa a chave privada para descriptografar a mensagem recebida.
Geração de chave
- Sejam dois grandes números primos escolhidos "aleatoriamente": pe q.
- Nota: n = p * q e φ = (p-1) * (q-1)
- Deixe um grande todo ser escolhido "aleatoriamente", primeiro com φ. E o inverso do módulo d φ.
- A chave de criptografia pública é o par (n, e), a chave de descriptografia privada é o par (n, d).
Criptografia / Descriptografia
Encriptação
- Antes de ser criptografada, a mensagem original deve ser decomposta em uma série de inteiros M com valores entre 0 e n-1.
- Para cada inteiro M, temos que calcular C≡M ^ e [n].
- A mensagem criptografada é composta pela sucessão de inteiros C.
Decifrar
- De acordo com a forma como foi criptografada, a mensagem recebida deve ser composta por uma sucessão de inteiros C com valores entre 0 e n-1.
- Para cada inteiro C é necessário calcular M≡C ^ d [n].
- A mensagem original pode então ser reconstruída a partir da série de inteiros M.
Fiabilité
A segurança do algoritmo RSA depende da dificuldade de fatorar n.
Para decifrar a mensagem, é necessário encontrar d sabendo e, o que requer recomputar φ, e portanto sabendo p e q, os dois fatores primos de n.
Porém, a fatoração de um inteiro (de tamanho muito grande) em fatores primos é extremamente difícil, operação que requer uma capacidade de cálculo muito importante.
Por exemplo: em 2010, o INRIA e seus parceiros conseguiram fatorar uma chave de 768 bits. Demorou dois anos e meio de pesquisa e mais de 10 ^ 20 cálculos. Este é o resultado de fatoração mais conhecido até o momento.
Para evitar o aumento do poder de computação, é regularmente recomendado o uso de tamanhos de chave cada vez maiores (atualmente 2048 bits).
