O algoritmo RSA é a base de um criptosistema — um conjunto de algoritmos criptográficos são utilizados para serviços de segurança específicos ou meramente — que permite a criptografia de chave pública e é amplamente usada para proteger os dados sensíveis, especialmente quando o assunto está sendo enviada através de uma rede insegura como a internet.,

RSA foi descrita publicamente pela primeira vez em 1977 por Ron Rivest, Adi Shamir e Leonard Adleman do Massachusetts Institute of Technology, embora a criação de 1973 de um algoritmo de chave pública pelo matemático britânico Clifford Cocks foi mantido classificado pelo GCHQ do Reino Unido até 1997.

criptografia de chave pública, também conhecida como criptografia assimétrica, usa duas chaves diferentes mas matematicamente ligadas — uma pública e uma privada. A chave pública pode ser compartilhada com todos, enquanto a chave privada deve ser mantida em segredo.,

na criptografia RSA, tanto as chaves públicas como as privadas podem criptografar uma mensagem; a chave oposta da usada para criptografar uma mensagem é usada para descriptografá-la. Este atributo é uma das razões pelas quais a RSA se tornou o algoritmo assimétrico mais amplamente utilizado: ela fornece um método para garantir a confidencialidade, integridade, autenticidade e não repúdio de comunicações eletrônicas e armazenamento de dados.

muitos protocolos como secure shell, OpenPGP, S/MIME, e SSL/TLS dependem de RSA para funções de encriptação e assinatura digital., Ele também é usado em programas de software — navegadores são um exemplo óbvio, como eles precisam estabelecer uma conexão segura sobre uma rede insegura, como a internet, ou validar uma assinatura digital. A verificação de assinatura RSA é uma das operações mais comumente realizadas em sistemas conectados à rede.

Why the RSA algorithm is used

RSA derives its security from the difficulty of factoring large integers that are the product of two large prime numbers., Multiplicar estes dois números é fácil, mas determinar os números primos originais do total — ou factoring — é considerado inviável devido ao tempo que levaria usando até os supercomputadores de hoje.

O algoritmo de geração de chaves públicas e privadas é a parte mais complexa da criptografia RSA. Dois grandes números primos, p e q, são gerados usando o algoritmo de teste de primalidade Rabin-Miller. Um módulo, n, é calculado multiplicando p e Q. este número é usado pelas chaves públicas e privadas e fornece a ligação entre elas., Seu comprimento, geralmente expresso em bits, é chamado de comprimento chave.

A chave pública consiste no módulo n e um expoente público, e, que é normalmente definido em 65537, uma vez que é um número primo que não é muito grande. A figura e não tem que ser um número primo secretamente selecionado, como a chave pública é compartilhada com todos.

a chave privada consiste no módulo n e no expoente privado d, que é calculado usando o algoritmo euclidiano estendido para encontrar o inverso multiplicativo em relação ao totiente de N.,

Leia ou assista o vídeo abaixo para uma explicação mais detalhada de como o algoritmo RSA funciona.

como funciona o algoritmo RSA?

Alice gera suas chaves RSA selecionando dois primos: p = 11 e q = 13. O módulo de elasticidade é n = p×q=143. O totiente é N ϕ(n)=(p−1)x (q−1)=120. Ela escolhe 7 para sua chave pública e RSA e calcula sua chave privada RSA usando o algoritmo euclidiano estendido, o que lhe dá 103.

Bob quer enviar a Alice uma mensagem criptografada, M, então ele obtém sua chave pública RSA (n, e) que, neste exemplo, é (143, 7)., A sua mensagem de texto sem formatação é apenas o número 9 e é criptografada em texto cifrado, C, da seguinte forma:

Me mod n = 97 mod 143 = 48 = C

Quando Alice Bob recebe a mensagem, ela descriptografa usando sua chave privada RSA (d, n) da seguinte forma:

Cd mod n = 48103 mod 143 = 9 = M

Para usar chaves RSA para assinar digitalmente uma mensagem, Alice precisa para criar um hash — um resumo de mensagem de sua mensagem para Bob — criptografar o valor de hash com sua chave privada RSA, e adicionar a chave para a mensagem., Bob pode então verificar que a mensagem foi enviada por Alice e não foi alterada descriptografando o valor de hash com sua chave pública. Se este valor corresponde ao hash da mensagem original, então somente Alice poderia tê-lo enviado — autenticação e não-repúdio — e a mensagem é exatamente como ela a escreveu — integridade.a Alice podia, claro, encriptar a mensagem com a chave pública do Bob, a confidencialidade, antes de a enviar ao Bob. Um certificado digital contém informações que identificam o proprietário do certificado e também contém a chave pública do proprietário., Os certificados são assinados pela Autoridade de certificação que os emite, e podem simplificar o processo de obtenção de chaves públicas e verificação do proprietário.

RSA security

RSA security baseia-se na dificuldade computacional de factorar inteiros grandes. À medida que o poder de computação aumenta e algoritmos de factoring mais eficientes são descobertos, a capacidade de fator maior e maior também aumenta.

A força de encriptação está directamente ligada ao tamanho da chave, e a duplicação do comprimento da chave pode proporcionar um aumento exponencial na força, embora prejudique o desempenho., As chaves RSA têm normalmente 1024 – ou 2048-bits de comprimento, mas os especialistas acreditam que as chaves de 1024-bits já não são totalmente seguras contra todos os ataques. É por isso que o governo e algumas indústrias estão se movendo para um comprimento chave mínimo de 2048-bits.

salvo um avanço imprevisto na computação quântica, serão muitos anos antes de chaves mais longas serem necessárias, mas criptografia de curva elíptica (ECC) está ganhando favor com muitos especialistas em segurança como uma alternativa à RSA para implementar criptografia de chave pública. Ele pode criar chaves criptográficas mais rápidas, menores e mais eficientes.,

hardware e software modernos são ECC-ready, e sua popularidade é provável que cresça, uma vez que pode oferecer segurança equivalente com menor poder de computação e uso de recursos de bateria, tornando-o mais adequado para aplicativos móveis do que RSA. Finalmente, uma equipe de pesquisadores, que incluiu Adi Shamir, um co-inventor da RSA, criou com sucesso uma chave RSA de 4096 bits usando criptoanálise acústica; no entanto, qualquer algoritmo de criptografia é vulnerável a ataque.