Comparando ECDSA vs RSA

Introdução

Ultimamente, tem havido inúmeras discussões sobre os prós e contras de RSA[01]
e ECDSA[02], na comunidade de criptografia. Para os não iniciados, eles são dois dos
os algoritmos de assinatura digital mais usados, mas mesmo para os mais técnicos
esclarecido, pode ser bastante difícil acompanhar os fatos. Este artigo é um
tentativa de comparação simplificadora dos dois algoritmos. Embora isso não seja
um ensaio profundamente técnico, o leitor mais impaciente pode verificar o final do
artigo para uma rápida tabela TL; DR com o resumo da discussão.

ECDSA x RSA

ECDSA e RSA são algoritmos usados ​​por criptografia de chave pública[03] sistemas
fornecer um mecanismo para autenticação. A criptografia de chave pública é a
ciência do design de sistemas criptográficos que empregam pares de chaves: público
chave (daí o nome) que pode ser distribuído livremente a qualquer pessoa, junto com um
correspondente chave privada, que é conhecido apenas por seu proprietário. Autenticação
refere-se ao processo de verificar se uma mensagem, assinada com uma chave privada, foi
criado pelo titular de uma chave privada específica. Algoritmos usados ​​para
autenticação são coletivamente conhecidas como algoritmos de assinatura digital [04].

Tais algoritmos dependem de problemas matemáticos complexos que são relativamente simples
calcular de uma maneira, embora seja bastante impraticável reverter. Isso significa que para
um invasor forjar uma assinatura digital, sem nenhum conhecimento do privado
chave, eles devem resolver problemas matemáticos intratáveis, como números inteiros
fatoração, para a qual não existem soluções eficientes conhecidas [05].

Por esse motivo, como não existem soluções eficientes disponíveis para o
problemas matemáticos subjacentes, a avaliação de algoritmos criptográficos pode
somente ocorrem com relação aos detalhes de implementação em conjunto com o
nível de segurança que eles fornecem. Para esse fim, esta seção apresenta um
comparação de RSA e ECDSA usando cinco (ou seis) métricas quantificadoras. Cada métrica
é introduzido em sua própria seção, juntamente com seu significado para qualquer pessoa
tentando decidir entre os dois algoritmos.

Adoção

A RSA é o padrão da indústria para criptografia de chave pública há muitos anos
agora. Mais SSL /TLS certificados estavam (e ainda estão) sendo assinados com chaves RSA.
Embora a maioria das CAs já tenha implementado o suporte a sistemas baseados em ECDSA
certificados, essa adoção duradoura levou a muitos sistemas legados
suporte RSA. Portanto, se um fornecedor exigir compatibilidade com versões anteriores
software cliente, eles são forçados a usar certificados assinados com o RSA. Hoje em dia,
entretanto, a maioria dos clientes modernos implementou suporte ao ECDSA, que
provavelmente remova essa restrição de compatibilidade em um futuro próximo.

Maturidade padrão

RSA foi padronizado primeiro para SSL /TLS em 1994 [06], enquanto a ECDSA foi introduzida
na especificação de TLS v1.2 em 2008 [07]. Essa diferença de idade indica uma
disparidade na maturidade dos padrões que descrevem as melhores práticas para
cada algoritmo. Embora os padrões RSA tenham sido extensivamente pesquisados ​​e
auditada, a ECDSA não recebeu tanta atenção. Recentemente, a defesa deste
algoritmo pelas principais CAs e sua adoção na maioria dos SSL / modernosTLS clientes tem
resultou na publicação de uma pesquisa mais extensa, mas ainda permanece
esquema relativamente novo. Isso deixa espaço para falhas desconhecidas de design ou
implementações incorretas sendo divulgadas no futuro.

Proporção de tamanho de chave e nível de segurança

Nível de segurança [08] é uma métrica em criptografia, referindo-se à força
de uma função ou primitiva criptográfica. É comumente medido em "bits" que
denota o número de operações que um invasor precisa executar para comprometer sua
segurança. Essa métrica pode fornecer um método de quantificação para comparar a eficácia
de vários sistemas de criptografia. Deve-se enfatizar que o tamanho da chave pública também é
medido em bits, mas é um conceito totalmente diferente, referente à
tamanho físico da chave.

Nesse sentido, uma chave pública comum RSA de 2048 bits fornece um nível de segurança de
112 bits. No entanto, o ECDSA requer apenas chaves públicas de tamanho 224 bits para fornecer o
mesmo nível de segurança de 112 bits. Essa diferença marcante no tamanho da chave tem dois
implicações significativas. Tamanhos de chave menores requerem menos largura de banda para configurar um
SSL /TLS stream, o que significa que os certificados ECDSA são ideais para dispositivos móveis
formulários. Além disso, esses certificados podem ser armazenados em dispositivos com muito
restrições de memória mais limitantes, fato que permite que m /TLS pilhas para ser
implementado em dispositivos IoT sem alocar muitos recursos. Publicados
pesquisa, até mostra que o ECDSA é mais eficiente [09] para implementar em
dispositivos.

Desempenho e complexidade de tempo

Algoritmos são receitas abstratas que descrevem um método para atingir um determinado objetivo.
Na ciência da computação, seu desempenho é medido contando o número de
operações elementares necessárias para atingir esse final predeterminado
doença. Essa métrica é chamada complexidade do tempo. Desde entrada diferente
tamanhos requerem um número diferente de operações, a complexidade do tempo é geralmente
expresso em função do tamanho da entrada.

Ambos os algoritmos em questão têm o mesmo desempenho demorado
operações matemáticas, como divisões e multiplicações. Assim, o tamanho da entrada
(que nesse caso é o tamanho de suas chaves) continua sendo o mais significativo
fator que afeta seu desempenho. Comparando os dois algoritmos, é necessário
distingue entre assinar uma mensagem e verificar uma assinatura. Na maioria
implementações práticas, o RSA parece ser significativamente mais rápido que o ECDSA em
verificação de assinaturas, embora seja mais lenta durante a assinatura.

As coisas ficam complicadas para níveis mais altos de segurança. Por exemplo, nos mais
configuração comum de um nível de segurança de 112 bits, o RSA requer 2048 bits
versus ECDSA que precisa de chaves de 224 bits. No próximo nível comum de 128 bits, o RSA
requer uma chave de 3072 bits, enquanto ECDSA apenas 256 bits. Isso resulta em RSA's
drasticamente o desempenho, enquanto o ECDSA é apenas ligeiramente afetado. Como
uma conseqüência desse problema de escala, embora a RSA pareça ter melhor desempenho no
momento, o aumento contínuo dos requisitos de segurança poderia muito bem tornar
ECDSA, a solução de fato no futuro.

Resistência pós-quântica

o algoritmo de Shor [10] é um algoritmo bem conhecido para quebrar chaves RSA usando
computadores quânticos. Como não há implementações práticas (públicas) de um
Em uma máquina desse tipo, a seguir é uma conjectura sobre o futuro da chave pública
criptografia. No momento em que este artigo foi escrito, a melhor implementação do Shor's
O algoritmo pode anular uma criptografia RSA de chave de 15 bits. Embora isso não pareça
quanto à medida que mais e mais pesquisas são direcionadas à computação quântica, o RSA
pode estar com sérios problemas a qualquer momento.

Os advogados da ECDSA não devem ser rápidos em comemorar, porque os elípticos
criptografia de curva também é vulnerável [11] para uma versão modificada de Shor's
algoritmo. Conseqüentemente, se ambas as cifras puderem ser quebradas por um computador quântico,
a única métrica objetiva é a complexidade necessária para implementar tal
ataque. De acordo com pesquisas públicas, as chaves RSA de 2048 bits requerem 4098 qubits
(e 5.2 trilhões de portas Tofolli) a serem derrotadas, enquanto as chaves ECDSA de 256 bits
requerem apenas 2330 qubits (e 126 bilhões de portões Tofolli). Portanto, a RSA é mais
caro quebrar, usando uma máquina quântica teórica.

Conclusão

Embora essa comparação não seja de forma alguma abrangente, é evidente que
A RSA ganhou legitimamente sua posição como a principal assinatura digital
algoritmo para a maioria dos aplicativos de certificado. No entanto, como a tecnologia é sempre
avançando de maneiras mais imprevisíveis, a conscientização e as necessidades de segurança também são
aumentando. Há pouco mais de dez anos, a segurança do dispositivo incorporado era
ficção e hoje em dia as comunicações seguras são essenciais para qualquer mundo real
inscrição. Como resultado, mesmo que ECDSA seja relativamente jovem, é de qualquer
adivinhe se substituirá RSA como o padrão para autenticação em SSL /TLS
implementações.

Se você, leitor, ainda não pode decidir qual algoritmo escolher, existem
soluções para apoiar o ECDSA e o RSA (como mecanismo de fallback), até que o
comunidade criptografada escolhe um vencedor. Verifique esta seção do artigo para um futuro
guia de instruções.

Tabela TL; DR

Referências

• [01] Algoritmo RSA
• [02] Algoritmo ECDSA
• [03] Criptografia de chave pública
• [04] Algoritmos de assinatura digital
• [05] Complexidade NP
• [06] SSL v.0.0 RFC
• [07] TLS v.1.2 RFC
• [08] Nível de segurança
• [09] RSA vs ECC para sistemas incorporados
• [10] Algoritmo de Shor
• [11] Estimativas de recursos quânticos para ECDL