O RSA acaba de ser destruído por um matemático alemão aposentado?

Shutterstock

Uma grande parte do mundo digital depende da criptografia RSA para privacidade e segurança. Um artigo matemático recente que “ destrói o criptossistema RSA ” deu palpitações aos criptógrafos. Eles estão certos em se preocupar?

O que é criptografia RSA?

O sistema de criptografia Rivest-Shamir-Adleman (RSA) resolveu o problema de como criptografar dados para que só pudessem ser descriptografados pelo destinatário pretendido. Em 1977, os co-criadores — Ron Rivest, Adi Shamir e Leonard Adleman — propuseram uma solução elegante baseada em uma nova maneira de usar chaves de criptografia. Simplificando, as chaves de criptografia são valores muito grandes usados ​​nos processos matemáticos que são aplicados aos dados para criptografá-los. O avanço que a RSA trouxe para o mundo da criptografia foi o uso de chaves públicas e privadas.

Devemos também mencionar Clifford Cocks, o matemático chefe da Sede de Comunicação do Governo do Reino Unido (GCHQ), que aplicou criptografia / descriptografia de chave pública e privada à criptografia em 1973. A informação foi classificada e permaneceu secreta. Só foi desclassificado em 1997. Ótimas mentes obviamente pensam da mesma forma.

A sequência de chave pública / chave privada tem como objetivo obter a chave pública do destinatário pretendido e usá-la no processo de criptografia junto com sua chave privada. O destinatário pode então descriptografar os dados usando sua chave privada e sua chave pública. As chaves públicas podem ser tornadas públicas com segurança, e as chaves privadas são mantidas privadas com segurança. E como o destinatário não precisa ser humano, qualquer sistema, serviço ou dispositivo que torne sua chave pública conhecida de maneira certificada e autenticada pode usar criptografia RSA. Isso permite que as comunicações entre sistemas sejam criptografadas.

Um certificado de chave pública é usado para certificar a identidade do proprietário da chave pública. Dois exemplos comuns de certificados de chave pública são Secure Socket Layer e Transport Layer Certificates (SSL / TLS). As chaves públicas podem ser transmitidas entre pessoas que desejam se comunicar ou podem ser recuperadas de servidores de chaves, como o servidor de chaves OpenPGP.

Secure Shell (SSH), OpenPGP, S / MIME e SSL / TSL usam criptografia RSA e todos os navegadores a usam. Algumas criptomoedas usam. Praticamente todo o mundo do comércio eletrônico depende da RSA de uma forma ou de outra. Qualquer coisa que ameace a integridade do criptossistema RSA deve ser analisada com atenção.

RELACIONADO: Como usar criptografia OpenPGP para e-mails no Thunderbird

Ameaças à criptografia RSA

Um elemento central dos algoritmos de criptografia é a irreversibilidade. As transformações matemáticas realizadas nos dados devem ser irreversíveis para todos os fins práticos.

O esquema RSA usa números muito grandes que são o produto da multiplicação de dois grandes números primos. Pegar dois números primos e multiplicá-los é trivial e barato do ponto de vista computacional. Não é preciso muito poder de processamento ou tempo para realizar essa ação. Mas receber o produto resultante e sem nenhum conhecimento prévio tentar calcular — por meio da fatoração — quais dois números primos foram usados ​​é computacionalmente caro.

A fatoração fica muito mais difícil rapidamente à medida que os números se tornam maiores. Levaria um tempo tão proibitivo — algumas estimativas chegam a trilhões de anos — para quebrar esse tipo de criptografia. Isso fornece uma pseudo-irreversibilidade segura. Não é realmente irreversível, mas demoraria tanto para fazê-lo, que poderia muito bem ser genuinamente irreversível.

O advento da computação quântica traz uma ameaça a esse tipo de criptografia. Os computadores quânticos prometem ser capazes de fazer a fatoração de inteiros necessária para determinar os dois números primos em um tempo extremamente curto. Prevê-se que um computador quântico executando uma derivada do Algoritmo de Shor seria capaz de encontrar os números primos dentro de períodos de tempo aceitavelmente curtos — talvez até dentro de horas.

Espera-se que leve 25 anos ou mais antes que exista um computador quântico capaz de fazer isso. Isso pode ser bom para algumas informações que estão criptografadas agora — a utilidade das informações pode ter expirado nessa altura. Mas parte do que está sendo criptografado agora ainda precisará ser protegido e privado em 25 (ou até mais) anos a partir de agora. Por exemplo, algumas comunicações governamentais e de segurança ainda serão confidenciais mesmo assim.

Erros na implementação do RSA já causaram problemas no passado. O RSA teórico deve ser processado em uma implementação de software funcional antes que possa ser útil — e software complexo geralmente contém bugs. Houve ajustes e substituições nos algoritmos usados ​​no criptossistema RSA, pois foram encontradas falhas nas implementações. As versões antigas foram descontinuadas e substituídas por novas versões.

Houve alegações de que portas traseiras foram introduzidas nos algoritmos RSA devido à coerção ou cooperação com agências de segurança nacional. Essas acusações nunca foram provadas, mas falhas que efetivamente forneciam portas dos fundos foram encontradas e posteriormente corrigidas.

Qual é a nova ameaça?

O professor Claus Peter Schnorr é um matemático aposentado e criptógrafo. Ele foi professor do Departamento de Matemática e Ciência da Computação da Universidade Johann Wolfgang Goethe em Frankfurt am Main.

A pré-impressão de um artigo de Schnorr (pré-impressão significa que está em desenvolvimento tardio, mas ainda não revisado por pares) propõe um novo método de fatoração de números inteiros primos nas plataformas de computação de hoje em uma taxa bastante acelerada. O artigo é intitulado “ Fast Factoring Integers by SVP Algorithms. ” SVP significa problema de menor vetor. O resumo termina com a frase provocativa “ Isso destrói o criptosistema RSA. ”

Ao condensar um trabalho muito complicado em uma declaração simples, o que isso sugere é uma melhoria em uma ordem de magnitude na velocidade da fatoração. O ganho de velocidade seria alcançado usando um refinamento de alguns dos trabalhos anteriores de Schnorr. Obviamente, uma redução revolucionária na fatoração de números inteiros teria um impacto significativo no criptossistema RSA. Ou seja, se o artigo teórico estiver factualmente correto e se uma implementação prática puder sustentar a hipótese.

O artigo promove um método de fatoração usando estruturas matemáticas chamadas reticulados. O Professor Schnorr é um especialista amplamente reconhecido neste campo e em sua aplicação à criptografia. O artigo afirma que a nova técnica é dramaticamente mais rápida do que o algoritmo General Number Field Sieve (GNFS), que é considerado a técnica atual mais rápida para fatorar grandes números.

Uma análise da ameaça

O artigo de Schorr é teórico por natureza. Não há tempos ou resultados de implementações. Os ganhos de velocidade teórica em relação ao GNFS parecem impressionantes no papel, mas a teoria e a matemática resistem ao escrutínio por aqueles que realmente entendem isso no nível necessário para comentar de forma significativa?

Dr. Léo Ducas é pesquisador do grupo de criptografia do Centrum Wiskunde & Informatica (CWI). O CWI é o instituto nacional de pesquisa para matemática e ciência da computação na Holanda. Ducas completou seu Ph.D. em 2013 em “ Assinaturas Baseadas em Lattice: Ataques, Análise e Otimização. ” Ele trabalhou com treliças ao longo de sua carreira. Ele também é um criptógrafo, portanto é eminentemente capaz de revisar o artigo de Schnorr.

Melhor ainda para os nossos propósitos, o Dr. Léo Ducas é um programador. Se você gosta de jogar Cryptris, seu jogo de criptografia assimétrica, vá em frente. Seu código-fonte acadêmico está espalhado pelo GitHub. Parte dele fica em seu próprio repositório, enquanto muito mais reside nos repositórios de outros projetos de vários autores nos quais ele trabalhou.

Ele revisou e analisou o artigo de Schnorr. Ele também criou uma implementação dos algoritmos de Schnorr &’ s como um script SageMath. Ele o chamou de SchnorrGate. Ducas também aponta para uma discussão sobre a criptografia StackExchange. Isso examina um erro em uma das fórmulas do papel que, se usado como impresso, produz resultados altamente imprecisos. Com esta fórmula corrigida, o método de fatoração de Schnorr funciona, mas a uma taxa muito mais lenta do que ele prevê.

Ducas &’ as descobertas de seus testes SageMath corroboram isso. Eles ilustram que os algoritmos de fatoração de Schnorr funcionam, mas muito mais lentamente do que os melhores métodos já disponíveis hoje.

Todos podemos respirar novamente

O RSA vive para criptografar outro dia. Mas o que teria acontecido se as afirmações no jornal tivessem se revelado verdadeiras? Bem, caos, inicialmente, e depois, a adoção de um novo criptossistema.

Talvez a era da criptografia de curva elíptica (ECC) tivesse chegado.