Criptografia de curva elíptica

Criptografia de curva elíptica (ECC) é uma abordagem para criptografia de chave pública baseada na estrutura algébrica de curvas elípticas sobre campos finitos. O ECC permite chaves menores em comparação com a criptografia não-EC (baseada em campos simples de Galois) para fornecer segurança equivalente.

Curvas elípticas são aplicáveis para acordo de chaves, assinaturas digitais, geradores pseudo-aleatórios e outras tarefas. Indiretamente, eles podem ser usados para criptografia combinando o acordo de chave com um esquema de criptografia simétrica. As curvas elípticas também são usadas em vários algoritmos de fatoração inteira baseados em curvas elípticas que têm aplicações em criptografia, como a fatoração de curva elíptica Lenstra.

Justificativa

A criptografia de chave pública é baseada na intratabilidade de certos problemas matemáticos. Os primeiros sistemas de chave pública baseavam sua segurança na suposição de que é difícil fatorar um inteiro grande composto de dois ou mais fatores primos grandes. Para protocolos baseados em curvas elípticas posteriores, a suposição básica é que encontrar o logaritmo discreto de um elemento de curva elíptica aleatória em relação a um ponto base conhecido publicamente é inviável: este é o "problema do logaritmo discreto da curva elíptica" (ECDLP). A segurança da criptografia de curva elíptica depende da capacidade de calcular uma multiplicação de pontos e da incapacidade de calcular o multiplicando dados os pontos originais e de produto. O tamanho da curva elíptica, medido pelo número total de pares inteiros discretos que satisfazem a equação da curva, determina a dificuldade do problema.

O Instituto Nacional de Padrões e Tecnologia (NIST) dos EUA endossou a criptografia de curva elíptica em seu conjunto Suite B de algoritmos recomendados, especificamente curva elíptica Diffie–Hellman (ECDH) para troca de chaves e algoritmo de assinatura digital de curva elíptica (ECDSA) para assinatura digital. A Agência de Segurança Nacional dos EUA (NSA) permite seu uso para proteção de informações classificadas como ultrassecretas com chaves de 384 bits. No entanto, em agosto de 2015, a NSA anunciou que planeja substituir o Suite B por um novo conjunto de cifras devido a preocupações com ataques de computação quântica em ECC.

Embora a patente RSA tenha expirado em 2000, pode haver patentes em vigor cobrindo certos aspectos da tecnologia ECC. No entanto, alguns argumentam que o padrão de assinatura digital de curva elíptica do governo dos EUA (ECDSA; NIST FIPS 186-3) e certos esquemas práticos de troca de chaves baseados em ECC (incluindo ECDH) podem ser implementados sem infringi-los, incluindo RSA Laboratories e Daniel J. Bernstein.

O principal benefício prometido pela criptografia de curva elíptica é um tamanho de chave menor, reduzindo os requisitos de armazenamento e transmissão, ou seja, que um grupo de curvas elípticas pode fornecer o mesmo nível de segurança oferecido por um sistema baseado em RSA com um grande módulo e correspondentemente maior chave: por exemplo, uma chave pública de curva elíptica de 256 bits deve fornecer segurança comparável a uma chave pública RSA de 3072 bits.

História

O uso de curvas elípticas na criptografia foi sugerido independentemente por Neal Koblitz e Victor S. Miller em 1985. Algoritmos de criptografia de curva elíptica entraram em uso em 2004 a 2005.

Teoria

Para fins criptográficos atuais, uma curva elíptica é uma curva plana sobre um campo finito (em vez de números reais) que consiste nos pontos que satisfazem a equação:

$Não. y^{2}=x^{3}+ax+b,,}$

junto com um ponto distinto no infinito, denotado ∞. As coordenadas aqui devem ser escolhidas a partir de um campo finito fixo de característica não igual a 2 ou 3, ou a equação da curva será um pouco mais complicada.

Este conjunto junto com a operação de grupo de curvas elípticas é um grupo abeliano, com o ponto no infinito como elemento de identidade. A estrutura do grupo é herdada do grupo divisor da variedade algébrica subjacente:

${displaystyle mathrm {Div} ^{0}(E)to mathrm {Pic} ^{0}(E)simeq E,,}$

Esquemas criptográficos

Vários protocolos baseados em logaritmos discretos foram adaptados para curvas elípticas, substituindo o grupo $(mathbb {Z} _{p})^{times }}$ com uma curva elíptica:

• O esquema de acordo-chave Diffie-Hellman (ECDH) baseado no esquema Diffie-Hellman,
• O Esquema de Criptografia Integrada de Curva Elíptica (ECIES), também conhecido como Esquema de Criptografia Aumentada de Curva Elíptica ou simplesmente o Esquema de Criptografia de Curva Elíptica,
• O algoritmo de assinatura digital de curva elíptica (ECDSA) é baseado no algoritmo de assinatura digital,
• O esquema de deformação usando a métrica p-adic Manhattan de Harrison,
• O algoritmo de assinatura digital da Edwards-curve (EdDSA) é baseado na assinatura Schnorr e usa curvas da Edwards torcidas,
• O esquema de acordo-chave ECMQV baseia-se no esquema de acordo-chave MQV,
• O sistema de certificados implícitos ECQV.

Na RSA Conference 2005, a National Security Agency (NSA) anunciou a Suite B, que usa exclusivamente ECC para geração de assinatura digital e troca de chaves. A suíte destina-se a proteger sistemas e informações de segurança nacional classificadas e não classificadas.

Recentemente, um grande número de primitivas criptográficas baseadas em mapeamentos bilineares em vários grupos de curvas elípticas, como os pares de Weil e Tate, foram introduzidos. Esquemas baseados nessas primitivas fornecem criptografia eficiente baseada em identidade, bem como assinaturas baseadas em pareamento, criptografia de assinatura, acordo de chave e recriptografia de proxy.

Implementação

Algumas considerações de implementação comuns incluem:

Parâmetros de domínio

Para usar o ECC, todas as partes devem concordar em todos os elementos que definem a curva elíptica, ou seja, a parâmetros de domínio do esquema. O tamanho do campo usado é tipicamente ou primo (e denotado como p) ou é um poder de dois (${displaystyle 2^{m}}$); o último caso é chamado o caso binário, e também requer a escolha de uma curva auxiliar denotada por f. Assim, o campo é definido por p no caso principal e o par de m e f no caso binário. A curva elíptica é definida pelas constantes um e b) usado em sua equação de definição. Finalmente, o subgrupo cíclico é definido pelo seu gerador de energia (a.k.a. ponto de base) G. Para aplicação criptográfica a ordem de G, esse é o menor número positivo n tal que $- Sim. Não.$ (o ponto no infinito da curva, e o elemento de identidade), é normalmente primo. Desde então n é o tamanho de um subgrupo de $E(mathbb {F} _{p})}$ segue do teorema de Lagrange que o número $- Sim. {1}{n}}|E(mathbb {F} _{p})|}$ é um inteiro. Em aplicações criptográficas este número h, chamado de co-fator, deve ser pequeno (${displaystyle hleq 4$) e, de preferência, $Não.$. Para resumir: no caso principal, os parâmetros de domínio são $(p,a,b,G,n,h)}$; no caso binário, eles são $(m,f,a,b,G,n,h)}$.

A menos que haja uma garantia de que os parâmetros de domínio foram gerados por uma parte confiável em relação ao seu uso, os parâmetros de domínio devem ser validados antes do uso.

A geração de parâmetros de domínio geralmente não é feita por cada participante porque envolve o cálculo do número de pontos em uma curva que é demorado e difícil de implementar. Como resultado, vários órgãos de padronização publicaram parâmetros de domínio de curvas elípticas para vários tamanhos de campo comuns. Esses parâmetros de domínio são comumente conhecidos como "curvas padrão" ou "curvas nomeadas"; uma curva nomeada pode ser referenciada pelo nome ou pelo identificador de objeto único definido nos documentos padrão:

• NIST, curvas elípticas recomendadas para uso do governo
• SECG, SEC 2: Parâmetros de domínio de curva elíptica recomendados
• ECC Brainpool (RFC 5639), ECC Brainpool Standard Curves and Curve Generation Arquivado em 2018-04-17 na Wayback Machine

Os vetores de teste SECG também estão disponíveis. O NIST aprovou muitas curvas SECG, portanto, há uma sobreposição significativa entre as especificações publicadas pelo NIST e SECG. Os parâmetros do domínio EC podem ser especificados por valor ou por nome.

Se alguém (apesar do acima) quiser construir seus próprios parâmetros de domínio, deve selecionar o campo subjacente e, em seguida, usar uma das seguintes estratégias para encontrar uma curva com número apropriado (ou seja, quase primo) de pontos usando um dos seguintes métodos:

• Selecione uma curva aleatória e use um algoritmo geral de contagem de pontos, por exemplo, o algoritmo de Schoof ou o algoritmo de Schoof-Elkies-Atkin,
• Selecione uma curva aleatória de uma família que permita fácil cálculo do número de pontos (por exemplo, curvas Koblitz), ou
• Selecione o número de pontos e gerar uma curva com este número de pontos usando o multiplicação complexa técnica.

Várias classes de curvas são fracas e devem ser evitadas:

• Curvas sobre ${displaystyle mathbb {F} _{2^{m}}}$ com não prima m são vulneráveis a ataques de descendência Weil.
• Curves tal que n divide $Não. P^{B}-1$ (onde) p é a característica do campo: q para um campo principal, ou $Não. 2$ para um campo binário) para suficientemente pequeno B são vulneráveis ao ataque Menezes-Okamoto-Vanstone (MOV) que aplica problema de logaritmo discreto usual (DLP) em um campo de extensão de pequeno grau de ${displaystyle mathbb {F} _{p}}$ para resolver ECDLP. O limite B deve ser escolhido para que logaritmos discretos no campo ${displaystyle mathbb {F} _{p^{B}}}$ são pelo menos tão difíceis de calcular como logs discretos na curva elíptica $E(mathbb {F} _{q})}$.
• Curves tal que $|E(mathbb {F} _{q})|=q}$ são vulneráveis ao ataque que mapeia os pontos na curva para o grupo aditivo de ${displaystyle mathbb {F} _{q}}$.

Tamanhos de chave

Porque todos os algoritmos mais conhecidos que permitem resolver o ECDLP (passo gigante de bebê, Rho de Pollard, etc), precisam ${displaystyle O({sqrt {n}})}$ passos, segue-se que o tamanho do campo subjacente deve ser aproximadamente o dobro do parâmetro de segurança. Por exemplo, para segurança de 128 bits um precisa de uma curva sobre ${displaystyle mathbb {F} _{q}}$, onde ${displaystyle qapprox 2^{256}}$. Isso pode ser contrastado com criptografia de campo finito (por exemplo, DSA) que requer chaves públicas de 3072 bits e chaves privadas de 256 bits e criptografia de fatoração de inteiro (por exemplo, RSA) que requer um valor de 3072 bits de n, onde a chave privada deve ser tão grande. No entanto, a chave pública pode ser menor para acomodar criptografia eficiente, especialmente quando o poder de processamento é limitado.

O esquema ECC mais difícil (publicamente) quebrado até hoje tinha uma chave de 112 bits para o caso do campo principal e uma chave de 109 bits para o caso do campo binário. Para o caso de campo principal, isso foi quebrado em julho de 2009 usando um cluster de mais de 200 consoles de jogos PlayStation 3 e poderia ter sido concluído em 3,5 meses usando esse cluster em execução contínua. O caso do campo binário foi quebrado em abril de 2004 usando 2.600 computadores em 17 meses.

Um projeto atual visa quebrar o desafio ECC2K-130 da Certicom, usando uma ampla gama de diferentes hardwares: CPUs, GPUs, FPGA.

Coordenadas projetivas

Um exame próximo das regras de adição mostra que, a fim de adicionar dois pontos, um precisa não apenas várias adições e multiplicações em ${displaystyle mathbb {F} _{q}}$ mas também uma operação de inversão. A inversão (para dados ${displaystyle xin mathbb {F} _{q}}$ encontrar ${displaystyle yin mathbb {F} _{q}}$ tal que $- Sim.$) é uma a duas ordens de magnitude mais lentas do que a multiplicação. No entanto, pontos em uma curva podem ser representados em diferentes sistemas de coordenadas que não exigem uma operação de inversão para adicionar dois pontos. Vários desses sistemas foram propostos: projeto sistema cada ponto é representado por três coordenadas $(X,Y,Z)}$ usando a seguinte relação: ${displaystyle x={frac {X}{Z}}}}}}$, $- Sim. Não.$; no Sistema Jacobiano um ponto também é representado com três coordenadas $(X,Y,Z)}$, mas uma relação diferente é usada: ${displaystyle x={frac {X}{Z^{2}}}}}}}}$, $- Sim. (Y}{Z^{3}}$; no Sistema López-Dahab a relação é ${displaystyle x={frac {X}{Z}}}}}}$, $- Sim. (Y}{Z^{2}}$; no modificado Jacobian sistema as mesmas relações são usadas, mas quatro coordenadas são armazenadas e usadas para cálculos $(X,Y,Z,aZ^{4})}$; e Chudnovsky Jacobian sistema cinco coordenadas são usadas $(X,Y,Z,Z^{2},Z^{3})}$. Note que pode haver diferentes convenções de nomeação, por exemplo, o padrão IEEE P1363-2000 usa "coordenadas projetivas" para se referir ao que é comumente chamado de coordenadas jacobinas. Uma aceleração adicional é possível se forem utilizadas coordenadas mistas.

Redução rápida (curvas NIST)

Modulo de redução p (que é necessário para adição e multiplicação) pode ser executado muito mais rápido se o primo p é um primo pseudo-Mersenne, que é ${displaystyle papprox 2^{d}}$; por exemplo, $Não. P=2^{521}-1}$ ou $Não. p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1.}$ Em comparação com a redução de Barrett, pode haver uma ordem de velocidade de magnitude. A aceleração aqui é prática, em vez de teórica, e deriva do fato de que o moduli de números contra números perto de poderes de dois pode ser executado de forma eficiente por computadores que operam em números binários com operações bits.

As curvas sobre ${displaystyle mathbb {F} _{p}}$ com pseudo-Mersenne p são recomendados por NIST. No entanto, outra vantagem das curvas NIST é que eles usam um= −3, que melhora a adição nas coordenadas jacobinas.

De acordo com Bernstein e Lange, muitas das decisões relacionadas à eficiência no NIST FIPS 186-2 são abaixo do ideal. Outras curvas são mais seguras e correm com a mesma rapidez.

Aplicativos

Curvas elípticas são aplicáveis para criptografia, assinaturas digitais, geradores pseudo-aleatórios e outras tarefas. Eles também são usados em vários algoritmos de fatoração inteira que têm aplicações em criptografia, como a fatoração de curva elíptica Lenstra.

Em 1999, o NIST recomendou quinze curvas elípticas. Especificamente, o FIPS 186-4 tem dez campos finitos recomendados:

• Cinco campos principais ${displaystyle mathbb {F} _{p}}$ para certos primos p de tamanhos 192, 224, 256, 384, e 521 bits. Para cada um dos campos primos, recomenda-se uma curva elíptica.
• Cinco campos binários ${displaystyle mathbb {F} _{2^{m}}}$ para m igual 163, 233, 283, 409 e 571. Para cada um dos campos binários, uma curva elíptica e uma curva Koblitz foi selecionada.

Assim, a recomendação do NIST contém um total de cinco curvas primárias e dez curvas binárias. As curvas foram ostensivamente escolhidas para segurança ideal e eficiência de implementação.

Em 2013, The New York Times afirmou que a Geração de Bits Aleatórios Determinísticos de Curva Elíptica Dupla (ou Dual_EC_DRBG) foi incluída como um padrão nacional do NIST devido à influência da NSA, que incluiu uma deliberada fraqueza no algoritmo e na curva elíptica recomendada. A RSA Security emitiu em setembro de 2013 um comunicado recomendando que seus clientes descontinuassem o uso de qualquer software baseado em Dual_EC_DRBG. Após a exposição do Dual_EC_DRBG como "uma operação secreta da NSA", especialistas em criptografia também expressaram preocupação com a segurança das curvas elípticas recomendadas pelo NIST, sugerindo um retorno à criptografia baseada em grupos de curvas não elípticas.

A criptografia de curva elíptica é usada pela criptomoeda Bitcoin. A versão 2.0 do Ethereum faz uso extensivo de pares de curvas elípticas usando assinaturas BLS - conforme especificado no rascunho da especificação BLS da IETF - para garantir criptograficamente que um validador Eth2 específico realmente verificou uma transação específica.

Segurança

Ataques de canal lateral

Ao contrário da maioria dos outros sistemas DLP (onde é possível usar o mesmo procedimento para elevar ao quadrado e multiplicar), a adição EC é significativamente diferente para duplicar (P = Q) e adição geral (P ≠ Q) dependendo do sistema de coordenadas utilizado. Consequentemente, é importante neutralizar ataques de canal lateral (por exemplo, ataques de temporização ou análise de potência simples/diferencial) usando, por exemplo, métodos de janela de padrão fixo (também conhecido como pente) (observe que isso não aumenta o tempo de computação). Alternativamente, pode-se usar uma curva de Edwards; esta é uma família especial de curvas elípticas para as quais a duplicação e a adição podem ser feitas com a mesma operação. Outra preocupação para os sistemas ECC é o perigo de ataques de falha, especialmente quando executados em cartões inteligentes.

Backdoors

Especialistas em criptografia expressaram preocupação de que a Agência de Segurança Nacional tenha inserido um backdoor cleptográfico em pelo menos um gerador pseudo-aleatório baseado em curva elíptica. Memorandos internos vazados pelo ex-contratado da NSA, Edward Snowden, sugerem que a NSA colocou um backdoor no padrão Dual EC DRBG. Uma análise do possível backdoor concluiu que um adversário em posse da chave secreta do algoritmo poderia obter chaves de criptografia com apenas 32 bytes de saída PRNG.

O projeto SafeCurves foi lançado para catalogar curvas que são fáceis de implementar com segurança e são projetadas de forma totalmente verificável publicamente para minimizar a chance de um backdoor.

Ataques de computação quântica

O algoritmo de Shor pode ser usado para quebrar a criptografia de curva elíptica computando logaritmos discretos em um computador quântico hipotético. As últimas estimativas de recursos quânticos para quebrar uma curva com um módulo de 256 bits (nível de segurança de 128 bits) são 2330 qubits e 126 bilhões de portões Toffoli. Para o caso da curva elíptica binária, são necessários 906 qubits (para quebrar 128 bits de segurança). Em comparação, usar o algoritmo de Shor para quebrar o algoritmo RSA requer 4.098 qubits e 5,2 trilhões de portas Toffoli para uma chave RSA de 2.048 bits, sugerindo que o ECC é um alvo mais fácil para computadores quânticos do que o RSA. Todos esses números excedem em muito qualquer computador quântico já construído, e as estimativas colocam a criação de tais computadores em uma década ou mais.

Isogenia Supersingular Diffie-Hellman Key Exchange alegou fornecer uma forma pós-quântica segura de criptografia de curva elíptica usando isogenias para implementar trocas de chaves Diffie-Hellman. Essa troca de chaves usa muito da mesma aritmética de campo que a criptografia de curva elíptica existente e requer sobrecarga computacional e de transmissão semelhante a muitos sistemas de chave pública usados atualmente. No entanto, novos ataques clássicos minaram a segurança deste protocolo.

Em agosto de 2015, a NSA anunciou que planejava fazer a transição "em um futuro não distante" a um novo conjunto de cifras resistente a ataques quânticos. "Infelizmente, o crescimento do uso da curva elíptica esbarrou no fato do progresso contínuo na pesquisa em computação quântica, exigindo uma reavaliação de nossa estratégia criptográfica."

Ataque de curva inválido

Quando o ECC é usado em máquinas virtuais, um invasor pode usar uma curva inválida para obter uma chave privada PDH completa.

Patentes

Pelo menos um esquema ECC (ECMQV) e algumas técnicas de implementação são cobertos por patentes.

Representações alternativas

Representações alternativas de curvas elípticas incluem:

• Curvas hessianas
• Curvas de Edwards
• Curvas torcidas
• Curvas hessianas torcidas
• Curva de Edwards torcida
• Doche orientado para duplicação– curva de carretel-Kohel
• Curva Doche–Icart–Kohel orientada a triplos
• Curva Jacobiana
• Curvas de Montgomery