O que é criptografia RSA e como funciona?

A criptografia RSA é um sistema que resolve o que já foi um dos maiores problemas da criptografia: Como você pode enviar a alguém uma mensagem codificada sem ter a oportunidade de compartilhar previamente o código com eles?

Este artigo ensinará tudo o que você precisa saber sobre como a criptografia RSA foi desenvolvida , como funciona , a matemática por trás disso , para que é usado bem como alguns dos maiores problemas de segurança que enfrenta . Aprender sobre a RSA lhe dará algum conhecimento básico que o ajudará a entender quantas partes de nossa vida on-line são mantidas seguras.

O que é criptografia RSA?

Digamos que você queira contar um segredo ao seu amigo. Se você estiver ao lado deles, basta sussurrar. Se você estiver em lados opostos do país, isso obviamente não funcionará. Você poderia anotar e enviar para eles ou usar o telefone, mas cada um desses canais de comunicação é inseguro e qualquer pessoa com motivação forte o suficiente poderia facilmente interceptar a mensagem.

Se o segredo fosse importante o suficiente, você não correria o risco de anotá-lo normalmente – espiões ou um funcionário dos correios desonesto poderiam estar olhando sua correspondência. Da mesma forma, alguém pode estar grampeando seu telefone sem o seu conhecimento e registrando todas as chamadas que você faz.

Uma solução para evitar que bisbilhoteiros acessem o conteúdo da mensagem é criptografar . Basicamente, isso significa adicionar um código à mensagem que a transforma em uma bagunça confusa. Se o seu código for suficientemente complexo, as únicas pessoas que poderão acessar a mensagem original serão aquelas que tiverem acesso ao código.

Se você teve a oportunidade de compartilhar o código com seu amigo de antemão, então qualquer um de vocês pode enviar uma mensagem criptografada a qualquer momento , sabendo que vocês dois são os únicos com capacidade de ler o conteúdo da mensagem. Mas e se você não tivesse a chance de compartilhar o código antes?

Este é um dos problemas fundamentais da criptografia, que foi abordado por esquemas de criptografia de chave pública (também conhecidos como criptografia assimétrica) como RSA .

Na criptografia RSA, as mensagens são criptografadas com um código chamado chave pública , que pode ser compartilhado abertamente. Devido a algumas propriedades matemáticas distintas do algoritmo RSA, uma vez que uma mensagem tenha sido criptografada com a chave pública, ela só poderá ser descriptografada por outra chave, conhecida como chave privada . Cada usuário RSA possui um par de chaves que consiste em suas chaves pública e privada. Como o nome sugere, a chave privada deve ser mantida em segredo.

Os esquemas de criptografia de chave pública diferem de criptografia de chave simétrica, onde o processo de criptografia e descriptografia usa a mesma chave privada . Essas diferenças tornam a criptografia de chave pública como a RSA útil para comunicação em situações em que não houve oportunidade de distribuir chaves com segurança antecipadamente.

Os algoritmos de chave simétrica têm suas próprias aplicações, como criptografia de dados para uso pessoal ou quando há canais seguros pelos quais as chaves privadas podem ser compartilhadas.

Veja também: Criptografia de chave pública

Onde a criptografia RSA é usada?

A criptografia RSA é frequentemente usada em combinação com outros esquemas de criptografia , ou para assinaturas digitais que pode provar a autenticidade e integridade de uma mensagem. Geralmente não é usado para criptografar mensagens ou arquivos inteiros, porque é menos eficiente e consome mais recursos do que a criptografia de chave simétrica.

Para tornar as coisas mais eficientes, um arquivo geralmente será criptografado com um algoritmo de chave simétrica e, em seguida, a chave simétrica será criptografada com criptografia RSA. Neste processo, apenas uma entidade que tenha acesso à chave privada RSA poderá descriptografar a chave simétrica.

Sem poder acessar a chave simétrica, o o arquivo original não pode ser descriptografado . Este método pode ser usado para manter mensagens e arquivos seguros, sem demorar muito ou consumir muitos recursos computacionais.

A criptografia RSA pode ser usada em vários sistemas diferentes. Pode ser implementado em OpenSSL, wolfCrypt, cryptlib e várias outras bibliotecas criptográficas.

Como um dos primeiros esquemas de criptografia de chave pública amplamente utilizados, o RSA lançou as bases para muitas das nossas comunicações seguras. Era tradicionalmente usado em TLS e também foi o algoritmo original usado em Criptografia PGP . O RSA ainda é visto em vários navegadores da web, e-mail, VPNs, chat e outros canais de comunicação.

O RSA também é frequentemente usado para fazer conexões seguras entre clientes VPN e servidores VPN. Em protocolos como OpenVPN, os handshakes TLS podem usar o algoritmo RSA para trocar chaves e estabelecer um canal seguro.

O histórico da criptografia RSA

Como mencionamos no início deste artigo, antes da criptografia de chave pública, era um desafio comunicar-se com segurança se não houvesse a oportunidade de trocar chaves com segurança antes. Se não houvesse uma oportunidade de compartilhar o código antecipadamente, ou um canal seguro através do qual as chaves pudessem ser distribuídas, não haveria como se comunicar sem a ameaça de inimigos serem capazes de interceptar e acessar o conteúdo da mensagem.

Foi só na década de 1970 que as coisas realmente começaram a mudar. O primeiro grande desenvolvimento rumo ao que hoje chamamos de criptografia de chave pública foi publicado no início da década por James H. Ellis. Ellis não conseguiu encontrar uma maneira de implementar seu trabalho, mas ele foi ampliado por seu colega Clifford Galos para se tornar o que hoje conhecemos como Criptografia RSA .

A peça final do quebra-cabeça é o que hoje chamamos de Troca de chaves Diffie-Hellman . Malcolm J. Williamson, outro colega de trabalho, descobriu um esquema que permitia que duas partes compartilhassem uma chave de criptografia, mesmo que o canal estivesse sendo monitorado por adversários.

Todo este trabalho foi realizado na agência de inteligência do Reino Unido, a Sede de Comunicações do Governo (GCHQ), que manteve a descoberta classificada . Em parte devido a limitações tecnológicas, o GCHQ não conseguia ver utilidade para a criptografia de chave pública na altura, pelo que o desenvolvimento ficou parado na prateleira, juntando pó. Somente em 1997 o trabalho foi desclassificado e os inventores originais do RSA foram reconhecidos. .

Vários anos depois, conceitos semelhantes começaram a se desenvolver na esfera pública. Ralph Merkle criou uma forma inicial de criptografia de chave pública , que influenciou Whitfield Diffie e Martin Hellman no design da troca de chaves Diffie-Hellman.

Faltava nas ideias de Diffie e Hellman um aspecto importante que tornaria seu trabalho uma base da criptografia de chave pública. Este foi um função unidirecional que seria difícil de inverter . Em 1977, Ron Rivest, Adi Shamir e Leonard Adleman , cujos sobrenomes formam a sigla RSA, encontraram uma solução após um ano de trabalho no problema.

Os acadêmicos do MIT fizeram sua descoberta após uma festa de Páscoa em 1977. Depois de uma noite de bebedeira, Rivest foi para casa, mas em vez de dormir, passou a noite escrevendo febrilmente um artigo que formalizou sua ideia para a necessária função unidirecional.

A ideia foi patenteada em 1983 pelo MIT, mas foi somente nos primórdios da Internet que o algoritmo RSA começou a ser amplamente adotado como uma importante ferramenta de segurança.

Como funciona a criptografia RSA?

O que se segue será uma simplificação, porque muitos leitores provavelmente ficaram assustados com o professor de matemática do ensino médio. Para evitar que a matemática fique muito fora de controle, estaremos simplificando alguns conceitos e usando números muito menores . Na realidade, a criptografia RSA usa números primos de magnitude muito maior e existem algumas outras complexidades.

Existem vários conceitos diferentes que você terá que entender antes de podermos explicar como tudo se encaixa. Esses incluem funções alçapão, gerando números primos, função totiente de Carmichael e os processos separados envolvidos em computando as chaves públicas e privadas usado nos processos de criptografia e descriptografia.

Funções do alçapão

A criptografia RSA funciona sob a premissa de que o algoritmo é fácil de calcular em uma direção, mas quase impossível em sentido inverso . Por exemplo, se lhe dissessem que 701.111 é um produto de dois números primos, você seria capaz de descobrir quais são esses dois números?

Mesmo com uma calculadora ou um computador, a maioria de nós não teria ideia de por onde começar, muito menos conseguiria descobrir a resposta. Mas se invertermos as coisas, fica muito mais fácil. Qual é o resultado de:

907x773

Se você estivesse entediado o suficiente, seria capaz de sacar seu telefone ou talvez calculá-lo mentalmente para descobrir que a resposta é o 701.111 mencionado anteriormente. Estes 907 e 773 são os números primos que respondem à nossa primeira pergunta, o que nos mostra que certas equações podem ser fáceis de descobrir de uma forma, mas aparentemente impossíveis ao contrário.

Outro aspecto interessante dessa equação é que é simples descobrir um dos números primos se você já tiver o outro, assim como o produto. Se lhe disserem que 701.111 é o resultado de 907 multiplicado por outro número primo, você pode descobrir o outro número primo com a seguinte equação:

701.111 ÷ 907 = 773

Como a relação entre esses números é simples de calcular em uma direção, mas incrivelmente difícil em sentido inverso, a equação é conhecida como função de alçapão . Esteja ciente de que, embora o exemplo acima seja difícil para as pessoas entenderem, os computadores podem realizar a operação em um período de tempo trivial.

Por causa disso, o RSA usa números muito maiores. O tamanho dos números primos em uma implementação RSA real varia, mas no RSA de 2.048 bits, eles se juntariam para formar chaves com 617 dígitos. Para ajudá-lo a visualizá-lo, uma chave seria um número deste tamanho:

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 999 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999999999999999999

Gerando números primos

As funções de alçapão mencionadas acima formam a base de como funcionam os esquemas de criptografia de chave pública e privada. Suas propriedades permitem que as chaves públicas sejam compartilhadas sem colocar a mensagem em risco ou revelar a chave privada. . Eles também permitem que os dados sejam criptografados com uma chave de uma forma que só pode ser descriptografada pela outra chave do par.

O primeiro passo para criptografar uma mensagem com RSA é gerar as chaves . Para fazer isso, precisamos dois números primos ( p e q ) que são selecionados com um teste de primalidade. Um teste de primalidade é um algoritmo que encontra com eficiência números primos, como o Teste de primalidade Rabin-Miller .

Os números primos em RSA precisam ser muito grandes e também relativamente distantes entre si. Números pequenos ou mais próximos são muito mais fáceis de decifrar. Apesar disso, nosso exemplo usará números menores para facilitar o acompanhamento e o cálculo.

Digamos que o teste de primalidade nos dê os números primos que usamos acima, 907 e 773. O próximo passo é descobrir o módulo (n), usando a seguinte fórmula:

n=pxq

Ondep= 907 eq= 773

Portanto:

n= 907 x 773

n= 701.111

Função totiente de Carmichael

Assim que tivermosn, nós usamos Função tociente de Carmichael:

eu(n) =lcm(p−1,q−1)

Se já faz um tempo que você não leu os livros de matemática, o que foi dito acima pode parecer um pouco assustador. Você pode pular esta parte e confiar que a matemática funciona; caso contrário, fique conosco para mais alguns cálculos. Tudo será explicado com o máximo de detalhes possível para ajudá-lo a entender o básico.

Para quem não sabe, λ(n) representa o tociente de Carmichael para n , enquanto lcm significa o menor múltiplo comum , que é o menor número que ambospeqpode dividir em. Existem algumas maneiras diferentes de descobrir isso, mas a mais fácil é confiar em um calculadora on-line para fazer a equação para você. Então, vamos colocar nossos números na equação:

eu(701.111) =lcm(907−1,773−1)

eu(701.111) =lcm(906, 772)

Usando a calculadora vinculada acima, isso nos dá:

eu ( 701.111 ) = 349.716

Gerando a chave pública

Agora que temos o tociente de Carmichael dos nossos números primos, é hora de descobrir nossa chave pública. Sob RSA, chaves públicas são compostas por um número primo e , bem como módulo n (explicaremos o que significa módulo em alguns parágrafos). O númeroepode ser qualquer coisa entre 1 e o valor deeu(n), que em nosso exemplo é 349.716.

Como a chave pública é compartilhada abertamente, não é tão importante paraeser um número aleatório. Na prática,egeralmente é definido em 65.537 , porque quando números muito maiores são escolhidos aleatoriamente, a criptografia torna-se muito menos eficiente. No exemplo de hoje, manteremos os números pequenos para tornar os cálculos eficientes. Digamos:

e= 11

Nossos dados criptografados finais são chamados de texto cifrado (c). Nós o derivamos de nossa mensagem de texto simples (eu), aplicando a chave pública com a seguinte fórmula:

c=eu^econtra n

Como mencionamos,^econtra né a chave pública. Nós já idealizamosee nós sabemosntambém. A única coisa que precisamos explicar écontra. Está um pouco fora da profundidade deste artigo, mas se refere a um operação de módulo , o que significa essencialmente o resto que sobra quando você divide um lado pelo outro. Por exemplo:

10contra3 = 1

Isso ocorre porque 3 cabe em 10 três vezes, com resto 1.

De volta à nossa equação. Para manter as coisas simples, digamos que a mensagem ( eu ) que queremos criptografar e manter em segredo é apenas um único número, 4 . Vamos conectar tudo:

c=eu^econtra n

c= 4^onze contra 701.111

c= 4.194.304contra701.111

Novamente, para fazer o operação de módulo fácil, usaremos um calculadora on-line , mas você está convidado a descobrir por si mesmo. Ao inserir 4.194.304 na calculadora online, obtemos:

c= 688.749

Portanto, quando usamos RSA para criptografar nossa mensagem, 4 , com nossa chave pública, nos dá o texto cifrado de 688.749 . As etapas anteriores podem ter parecido um pouco pesadas em matemática, mas é importante reiterar o que realmente aconteceu.

Nós tinhamos um mensagem de 4 , que queríamos manter em segredo. Aplicamos uma chave pública a ele, o que nos deu a resultado criptografado de 688.749 . Agora que está criptografado, podemos enviar com segurança o número 688.749 ao proprietário do par de chaves . Eles são a única pessoa capaz de descriptografá-lo com sua chave privada. Quando eles descriptografarem, verão a mensagem que realmente estávamos enviando, 4 .

Gerando a chave privada

Na criptografia RSA, uma vez que os dados ou uma mensagem tenham sido transformados em texto cifrado com uma chave pública, eles só podem ser descriptografados pela chave privada do mesmo par de chaves. As chaves privadas são compostas por d e n . Nós já sabemosnão,e a seguinte equação é usada para encontrard:

d=1/emod eu(n)

No Gerando a chave pública seção acima, já decidimos que em nosso exemplo,eseria igual a 11. Da mesma forma, sabemos queeu(n) é igual a 349.716 do nosso trabalho anterior em Função totiente de Carmichael . As coisas ficam um pouco mais complicadas quando nos deparamos com esta seção da fórmula:

1/econtra

Pode parecer que esta equação pede para você dividir 1 por 11, mas não é o caso. Em vez disso, isso apenas simboliza que precisamos calcular o modular inverso dee(que neste caso é 11) eeu(n) (que neste caso é 349.716).

Isto significa essencialmente que em vez de realizar uma operação de módulo padrão, usaremos o inverso . Isso normalmente é encontrado com o Algoritmo Euclidiano Estendido, mas está um pouco fora do escopo deste artigo, então vamos apenas trapacear e usar um calculadora on-line em vez de. Agora que entendemos tudo o que está acontecendo, vamos inserir nossas informações na fórmula:

d=1/onzecontra349.716

Para realizar esta operação, basta inserir 11 (ou qualquer valor que você possa ter paraese você estiver tentando fazer isso com seu próprio exemplo) onde diz Inteiro e 349.716 (ou qualquer valor que você possa ter paraeu(n) se você estiver tentando fazer isso com seu próprio exemplo) onde diz Módulo na calculadora online vinculada acima. Se você fez isso corretamente, deverá obter um resultado onde:

d= 254, 339

Agora que temos o valor ded, podemos descriptografar mensagens que foram criptografadas com nossa chave pública usando a seguinte fórmula:

eu=c^dcontra n

Agora podemos voltar ao texto cifrado que criptografamos sob o Gerando a chave privada seção. Quando criptografamos a mensagem com a chave pública, ela nos deu um valor para c de 688.749 . Do alto, sabemos que d é igual a 254.339 . Também sabemos que n é igual a 701.111 . Isso nos dá:

eu= 688.749^254.339 contra701.111.

Como você deve ter notado, tentar elevar um número à 254.339ª potência pode ser um pouco demais para a maioria das calculadoras normais. Em vez disso, usaremos um serviço on-line Calculadora de descriptografia RSA . Se você quisesse usar outro método, você aplicaria as potências como faria normalmente e realizaria a operação de módulo da mesma maneira que fizemos no exemplo. Gerando a chave pública seção.

Na calculadora vinculada acima, digite 701.111 onde diz Módulo de Alimentação: N , 254.399 onde diz Chave de descriptografia: D , e 688.749 onde diz Mensagem de texto cifrado em formato numérico , como mostrado abaixo:

Depois de inserir os dados, clique em Descriptografar , que colocará os números por meio da fórmula de descriptografia listada acima. Isso lhe dará a mensagem original na caixa abaixo. Se você fez tudo corretamente, deverá obter uma resposta de 4 , que foi a mensagem original que criptografamos com nossa chave pública.

Como a criptografia RSA funciona na prática

As seções acima devem fornecer uma compreensão razoável de como funciona a matemática por trás da criptografia de chave pública. Pode ser um pouco confuso, mas mesmo aqueles que não entenderam os meandros das equações poderão tirar algumas informações importantes sobre o processo.

Nas etapas listadas acima, mostramos como duas entidades podem se comunicar com segurança sem ter compartilhado um código previamente. Primeiro, cada um deles precisa configurar seus próprios pares de chaves e compartilhar a chave pública entre si . As duas entidades precisam manter suas chaves privadas em segredo para que suas comunicações permaneçam seguras.

Assim que o remetente tiver a chave pública do destinatário, ele poderá usá-la para criptografar os dados que deseja manter seguros. Uma vez criptografado com uma chave pública, só pode ser descriptografado pela chave privada do mesmo par de chaves . Mesmo a mesma chave pública não pode ser usada para descriptografar os dados. Isto se deve às propriedades funções de alçapão que mencionamos acima.

Quando o destinatário recebe a mensagem criptografada, ele usa sua chave privada para acessar os dados. Se o destinatário quiser retornar as comunicações de forma segura, eles podem então criptografar sua mensagem com a chave pública da parte com quem estão se comunicando . Novamente, uma vez criptografada com a chave pública, a única maneira de acessar a informação é através da chave privada correspondente.

Dessa forma, a criptografia RSA pode ser usada por partes até então desconhecidas para enviar dados com segurança entre si. Partes significativas dos canais de comunicação que utilizamos nas nossas vidas online foram construídas a partir desta base.

Como as mensagens mais complicadas são criptografadas com RSA?

No nosso exemplo, simplificamos bastante as coisas para facilitar o entendimento, por isso criptografamos apenas uma mensagem de “4”. Ser capaz de criptografar o número 4 não parece particularmente útil, então você deve estar se perguntando como você pode criptografar um conjunto de dados mais complicado , como uma chave simétrica (que é o uso mais comum do RSA) ou mesmo uma mensagem.

Algumas pessoas podem ficar perplexas com a forma como uma chave como “n38cb29fkbjh138g7fqijnf3kaj84f8b9f…” ou uma mensagem como “compre um sanduíche para mim” pode ser criptografada por um algoritmo como o RSA, que lida com números e não com letras. A realidade é que todas as informações que nossos computadores processam são armazenadas em binário (1s e 0s) e usamos padrões de codificação como ASCII ou Unicode para representá-los de maneiras que os humanos possam entender (letras).

Isso significa que chaves como “n38cb29fkbjh138g7fqijnf3kaj84f8b9f…” e mensagens como “compre um sanduíche para mim” já existem como números , que pode ser facilmente calculado no algoritmo RSA. Os números pelos quais eles são representados são muito maiores e mais difíceis de gerenciar, e é por isso que preferimos lidar com caracteres alfanuméricos em vez de uma confusão de binários.

Se você quisesse criptografar uma chave de sessão mais longa ou uma mensagem mais complexa com RSA, isso envolveria simplesmente um número muito maior .

Preenchimento

Quando o RSA é implementado, ele usa algo chamado preenchimento para ajudar a prevenir uma série de ataques . Para explicar como isso funciona, começaremos com um exemplo. Digamos que você esteja enviando uma mensagem codificada para um amigo:

Prezada Karen,

Espero que você esteja bem. Ainda vamos jantar amanhã?

Com os melhores cumprimentos,

James

Digamos que você codificou a mensagem de forma simples, mudando cada letra para a seguinte no alfabeto . Isso mudaria a mensagem para:

Efbs Lbsfo,

J ipqf zpv bsf xfmm. Bsf xf tujmm ibwjoh ejoofs upnpsspx?

zpvst tjodfsfmz,

Kbnft

Se seus inimigos interceptaram esta carta, existe um truque que eles poderiam usar para tentar decifrar o código. Eles poderiam observe o formato da sua carta e tente adivinhar o que a mensagem pode estar dizendo. Eles sabem que as pessoas normalmente começam suas cartas com “Oi”, “Olá”, “Querido” ou uma série de outras convenções.

Se tentassem aplicar “Oi” ou “Olá” como primeira palavra, veriam que não caberia no número de caracteres. Eles poderiam então tentar “Querido”. Cabe, mas isso não significa necessariamente nada. Os atacantes simplesmente tentariam e veriam aonde isso os levaria. Então eles mudariam as letras “e”, “f”, “b” e “s” por “d”, “e”, “a” e “r” respectivamente. Isso lhes daria:

Prezado Laseo,

J ipqe zpv são xemm. Xe tujmm iawjoh djooes são upnpsspx?

Zpvrt tjoderemz,

Pato

Ainda parece muito confuso, então os invasores podem tentar consultar outras convenções, como como concluímos nossas cartas . As pessoas costumam adicionar “De” ou “Atenciosamente” no final, mas nenhum deles se ajusta ao formato. Em vez disso, os invasores podem tentar “Atenciosamente” e substituir as outras letras para ver onde isso as leva. Trocando “z”, “p”, “v”, “t”, “j” “o”, “d” e “m” por “y”, “o”, “u”, “s”, “ i”, “n”, “c” e “l” respectivamente, eles obteriam:

Prezado Lasen,

Eu acho que você é excelente. Xe tuill iawinh dinnes é uonossox?

Com os melhores cumprimentos,

Pato

Após essa modificação, parece que os invasores estão começando a chegar a algum lugar. Eles encontraram as palavras “eu”, “você” e “é”, além das palavras que compuseram seus palpites iniciais.

Vendo que as palavras estão na ordem gramatical correta, os invasores podem ter certeza de que estão indo na direção certa. Até agora, eles provavelmente também já perceberam que o código envolvia a mudança de cada letra para aquela que a segue no alfabeto. Depois que eles perceberem isso, será mais fácil traduzir o resto e ler a mensagem original .

O exemplo acima era apenas um código simples, mas como você pode ver, a estrutura de uma mensagem pode dar aos invasores pistas sobre seu conteúdo . Claro, foi difícil descobrir a mensagem apenas a partir de sua estrutura e foram necessárias algumas suposições, mas você precisa ter em mente que os computadores são muito melhores nisso do que nós. Isso significa que eles podem ser usados ​​para descobrir códigos muito mais complexos em um tempo muito mais curto. , com base em pistas provenientes da estrutura e de outros elementos.

Se a estrutura pode levar à quebra de um código e revelar o conteúdo de uma mensagem, então precisamos de alguma forma de ocultar a estrutura para manter a mensagem segura. Isto nos leva a preenchimento .

Quando uma mensagem é preenchida, dados aleatórios são adicionados para ocultar as pistas de formatação originais que podem levar à quebra de uma mensagem criptografada . Com o RSA, as coisas são um pouco mais complicadas, porque uma chave criptografada não tem a formatação óbvia de uma carta que ajudou a nos dar pistas no exemplo acima.

Apesar disso, os adversários podem usar vários ataques para explorar as propriedades matemáticas de um código e quebrar dados criptografados. Devido a esta ameaça, implementações de RSA usam esquemas de preenchimento como OAEP para incorporar dados extras na mensagem . Adicionar esse preenchimento antes que a mensagem seja criptografada torna o RSA muito mais seguro.

Assinando mensagens

O RSA pode ser usado para mais do que apenas criptografar dados. Suas propriedades também o tornam um sistema útil para confirmar que uma mensagem foi enviada pela entidade que afirma tê-la enviado, bem como provar que uma mensagem não foi alterada ou adulterada .

Quando alguém deseja provar a autenticidade de sua mensagem, pode calcular um cerquilha (uma função que pega dados de tamanho arbitrário e os transforma em um valor de comprimento fixo) do texto simples e, em seguida, assina-os com sua chave privada. Eles assine o hash aplicando a mesma fórmula usada na descriptografia (m = cdcontra n). Assim que a mensagem for assinada, eles enviam esta assinatura digital ao destinatário junto com a mensagem.

Se um destinatário receber uma mensagem com assinatura digital, ele poderá usar o assinatura para verificar se a mensagem foi assinada autenticamente pela chave privada da pessoa que afirma tê-la enviado . Eles também podem ver se a mensagem foi alterada pelos invasores após ser enviada.

Para verificar a assinatura digital, o destinatário primeiro usa a mesma função hash para encontrar o valor hash da mensagem recebida. O destinatário então aplica o chave pública do remetente à assinatura digital, usando a fórmula de criptografia (c = mecontra n),para fornecer a eles o hash da assinatura digital.

Por comparando o hash da mensagem que foi recebida junto com o hash da assinatura digital criptografada , o destinatário poderá saber se a mensagem é autêntica. Se os dois valores forem iguais, a mensagem não foi alterada desde que foi assinada pelo remetente original. Se a mensagem tivesse sido alterada por um único caractere, o valor do hash seria completamente diferente.

Segurança e ataques RSA

Como a maioria dos criptosistemas, a segurança do RSA depende de como ele é implementado e utilizado. Um fator importante é o tamanho da chave. O quanto maior o número de bits em uma chave (essencialmente o tamanho da chave), mais difícil será quebrar ataques como força bruta e factoring.

Como algoritmos de chave assimétrica, como RSA, podem ser quebrados por fatoração de inteiros, enquanto algoritmos de chave simétrica, como AES não pode, as chaves RSA precisam ser muito mais longas para atingir o mesmo nível de segurança.

Atualmente, o o maior tamanho de chave fatorado é de 768 bits . Isto foi feito por um equipe de acadêmicos durante um período de dois anos, usando centenas de máquinas.

Como o factoring foi concluído no final de 2009 e o poder computacional cresceu significativamente desde então, pode-se presumir que uma tentativa de intensidade semelhante agora poderia fatorar uma chave RSA muito maior .

Apesar disso, o tempo e os recursos necessários para este tipo de ataque colocam-no fora do alcance da maioria dos hackers e dentro do domínio dos Estados-nação. O melhor comprimento de chave a ser usado dependerá do seu modelo de ameaça individual. O Instituto Nacional de Padrões e Tecnologia recomenda um tamanho mínimo de chave de 2048 bits , mas chaves de 4.096 bits também são usadas em algumas situações onde o nível de ameaça é maior.

O factoring é apenas uma forma de quebrar o RSA. Vários outros ataques têm o potencial de quebrar a criptografia com uma quantidade menor de recursos, mas dependem da implementação e de outros fatores, não necessariamente do próprio RSA. Alguns deles incluem:

Os primos são realmente aleatórios?

Algumas implementações de RSA usam geradores fracos de números aleatórios para chegar aos números primos. Se esses números não forem suficientemente aleatórios, será muito mais fácil para os invasores considerá-los e quebrar a criptografia. Este problema pode ser evitado usando um gerador de números pseudo-aleatórios criptograficamente seguro .

Má geração de chaves

As chaves RSA precisam estar dentro de determinados parâmetros para que sejam seguras. Se os primos p e q estão muito próximos, a chave pode ser facilmente descoberta . Da mesma forma, o número d que faz parte da chave privada não pode ser muito pequeno . Um valor baixo facilita a resolução. É importante que esses números tenham comprimento adequado para manter sua chave segura.

Ataques de canal lateral

Esse é um tipo de ataque que não quebra o RSA diretamente, mas usa informações de sua implementação para dar dicas aos invasores sobre o processo de criptografia. Esses ataques podem incluir coisas como analisando a quantidade de energia que está sendo usada , ou análise de previsão de ramificação , que usa medidas de tempo de execução para descobrir a chave privada.

Outro tipo de ataque de canal lateral é conhecido como ataque de temporização. Se um invasor tiver a capacidade de medir o tempo de descriptografia no computador do alvo para diversas mensagens criptografadas diferentes, essas informações podem permitir que o invasor verifique a chave privada do alvo .

A maioria das implementações de RSA evita esse ataque adicionando um valor único durante o processo de criptografia, o que remove essa correlação. Este processo é chamado cegueira criptográfica .

A criptografia RSA é segura para o futuro?

A boa notícia é que atualmente o RSA é considerado seguro para uso, apesar desses possíveis ataques. A ressalva é que ele precisa ser implementado corretamente e usar uma chave que esteja dentro dos parâmetros corretos. Como acabamos de discutir, implementações que não usam preenchimento, usam números primos de tamanho inadequado ou têm outras vulnerabilidades não podem ser consideradas seguras.

Se você quiser usar criptografia RSA, certifique-se de usar uma chave de pelo menos 1024 bits . Aqueles com modelos de ameaças mais elevados devem usar chaves de 2.048 ou 4.096 bits se quiserem usar o RSA com confiança.

Contanto que você esteja ciente dos pontos fracos do RSA e o use corretamente, você deve se sentir seguro para usar o RSA para compartilhamento de chaves e outras tarefas semelhantes que exigem criptografia de chave pública.

Embora o RSA seja seguro por enquanto, espera-se que o surgimento da computação quântica represente alguns desafios no futuro.

A computação quântica afetará o RSA?

O campo da computação quântica continua a fazer melhorias constantes, mas ainda levará alguns anos até que seja muito utilizado fora do contexto de pesquisa. Embora os computadores quânticos tenham um imenso potencial para aprimorar nossas capacidades, eles também trarão algumas complicações ao mundo da criptografia.

Isso ocorre porque os computadores quânticos podem resolver facilmente certos problemas que atualmente são considerados imensamente difíceis, e essa dificuldade é muitas vezes o que torna nossos sistemas criptográficos seguros. No caso de algoritmos de chave simétrica como AES, poderosos computadores quânticos rodando Algoritmo de Grover seria capaz de acelerar significativamente os ataques.

Embora isto certamente represente uma ameaça contra os nossos mecanismos criptográficos atuais, também é relativamente fácil de corrigir. Tudo o que teremos que fazer é dobrar o tamanho da chave para proteger esses algoritmos de chave simétrica.

Quando se trata de criptografia de chave pública como RSA, enfrentamos um problema muito maior. Assim que os computadores quânticos se tornarem fortes o suficiente para poderem executar efetivamente o algoritmo de Shor, será viável resolver os três problemas matemáticos a seguir:

• O problema de fatoração de inteiros
• O problema de logaritmo discreto
• O problema de logaritmo discreto de curva elíptica

Isto é uma má notícia, porque a segurança dos nossos algoritmos de chave pública mais utilizados baseia-se na premissa de que estes são atualmente impraticáveis ​​de resolver com os recursos computacionais atuais. No caso do RSA, é o problema de fatoração de inteiros.

Embora a computação quântica e o algoritmo de Shor sejam certamente uma ameaça futura para a RSA, a boa notícia é que temos tempo para mudar a nossa infraestrutura criptográfica para garantir a nossa segurança futura.

Embora seja difícil saber quando exatamente será viável para os computadores quânticos quebrarem o RSA, pesquisas e desenvolvimentos significativos já estão em andamento. O Instituto Nacional de Padrões e Tecnologia dos EUA (NIST) está atualmente solicitando e avaliando vários algoritmos de chave pública que serão seguros em um mundo pós-quântico.

No momento em que este artigo foi escrito, o NIST estava em sua terceira rodada e está atualmente avaliando 15 candidatos para criptografia de chave pública e assinaturas digitais. A padronização é um processo lento, portanto ainda serão necessários vários anos até que os algoritmos finais sejam selecionados. Até lá, não temos muito com que nos preocupar, porque as ameaças da computação quântica estão ainda mais distantes.

Veja também: Tipos comuns de criptografia explicados