No artigo Criptografia assimétrica com o RSA foi abordado em detalhes os conceitos matemáticos e métodos utilizados na criptografia assimétrica, sendo que, previamente, houve uma introdução no assunto abordado pelo artigo Fundamentos da criptografia assimétrica. Farei um pequeno resumo para que este artigo possa ficar completo.

O RSA trabalha com o conceito de pares de chaves assimétricas, no qual são criadas duas chaves, a pública e a privada. A chave pública é capaz apenas de criptografar as mensagens, não sendo possível derivar dela a outra chave, e deve ser distribuída a todos de quem se queira receber as mensagens criptografadas.

A chave privada deve ser mantida no mais absoluto sigilo, sendo ela a única capaz de descriptografar as mensagens criptografadas com a chave pública. Para a geração das chaves obtém-se dois números primos grandes, na ordem de 100 dígitos em chaves relativamente fracas, um número chamado de P e e outro de Q. Eles são a base do RSA, pois a partir deles são geradas a chave pública e privada.

Usando P e Q, um outro número, chamado de N, é calculado pelo simples produto entre eles. A criação das chaves segue calculando um número chamado de D escolhendo-se um outro chamado de E. Criptografa-se então a mensagem desejada utilizando a fórmula C = M^E % N (% aqui representa a operação de módulo), onde C é a mensagem final, criptografada, M a mensagem original, a qual se deseja criptografar, N a chave pública e E um número primo escolhido respeitando algumas regras, como a de ser primo relativo a (P-1) * (Q-1)). O E não é importante para a segurança do algorítimo, sendo um primo padronizado no RSA em 65537. Para descriptografar a mensagem, faz-se M = C^D % N, no qual D é a chave privada.

Note que, no RSA, é virtualmente impossível se conseguir M com base apenas em C e N, já que foi-se tirado o módulo (resto da divisão) de uma potência grande de M por N, e apenas com o resto da divisão não se pode fazer muita coisa. Isso é chamado de algorítimo de mão única, no qual apenas com as variáveis determinadas não se consegue obter a função inversa (que desfaz a função inicial).

Quebrar o RSA consiste exatamente em se fatorar o número N e descobrir P e Q, para que, a partir deles, obter-se a chave privada. Esse é um sistema de força bruta. Entretanto, deve-se ressaltar que o número N é o produto de dois números primos gigantes. Não parece tão impressionante, mas contando que não existe uma forma prática matemática de se fatorar um número rapidamente e a única possibilidade é por tentativa e erro, um computador potente levaria alguns milhões de anos de processamento para conseguir chegar nos dois fatores de N de uma chave RSA atual relativamente forte (que é de, pelo menos, 1024 bits).

Quanto ao desafio, obviamente, as chaves eram bem menores, sendo que a mais forte poderia ser quebrada no máximo em cerca de 48h de forma direta, sem grandes otimizações (de acordo com experiências relatadas pelo autor do artigo). Oito valores de N e algumas mensagens cifradas foram enviados no desafio, que são os seguintes (mais detalhes em Ganhe um livro aqui no VOL):

N1 = 391
E1 = 7
MSG1 = 273 - 291 - 133 (São somente 3 caracteres)

N2 = 1395118689832499977
E2 = 65537
MSG2 = 326026020400037122 - 807404586589519912 - 281075936473600704 - 353132823001634071 (3 caracteres e um número inteiro)

N3 = 7037566921193896543
E3 = 65537
MSG3 = 2952982415375107879 - 1067648351130204034 - 1342021018018043152 - 5618319547902349498 (3 caracteres e um número inteiro)

Para N1, N2 e N3, havia o desafio de encontrar P e Q, para que com eles se calculasse o valor do D e depois disso se usasse este valor para descobrir qual era a mensagem cifrada.

N4 = 23085033109316605813
N5 = 252539935250032846903
N6= 1080732373142027068783
N7 = 13529301124273579600009
N8 = 52477496982124296201703

Para N4 até N8 o desafio era apenas recuperar P e Q e calcular o valor do D. Não havia mensagem cifrada.