Criptografia de curva elíptica

A Criptografía de Curvas Elípticas, é uma aproximação para a criptografia de chave pública com base na estrutura algébrica de curvas elípticas sobre corpos finitos . A utilização de curvas elípticas em criptografia foi sugerida por Neal Koblitz e Victor S.Miller em 1985. Curvas Elípticas são também utilizadas em várias fatorações de algoritmos inteiros, que têm aplicações em criptografia.

Criptografia de chave pública é baseada na criação de enigmas matemáticos que são difíceis de resolver sem determinado conhecimento sobre como foram criados. O criador guarda aquele conhecimento secreto (a chave confidencial) e publicam o enigma (a chave pública). O enigma pode então ser usado para confundir uma mensagem de um jeito que somente o criador possa desconfundi-la. Antes, os sistemas de chaves públicas, tais como os algoritmos de RSA, usavam produtos de dois números primos como enigma: o usuário escolhe dois número primos como sua chave confidencial, e publica seu produto como sua chave pública. A dificuldade de fatoração assegura que ninguém mais possa desvendar a chave confidencial (isto é, os dois número primos) da chave pública. Entretanto, devido ao progresso recente em fatorar, chaves públicas de RSA devem agora ter milhares de bits de comprimento para fornecer a segurança adequada.

Uma outra classe do enigma envolve resolver a equação ab = c em b, quando sabemos quem são a e c. Tais equações que envolvem números reais ou complexos são resolvidas facilmente usando logaritmos. Entretanto, em um grande grupo finito, encontrar soluções a tais equações é completamente difícil e é conhecido como o problema de Logaritmo discreto. Uma curva elíptica é uma curva plana definida pela equação:${\displaystyle y^{2}=x^{3}+ax+b}$. Pode ser mostrado que o conjunto de pontos em uma curva forma um grupo abeliano (com o ponto infinito como a identidade do elemento).

Se as coordenadas x e y forem escolhidas de um grande campo finito, as soluções darão forma a um Grupo Abeliano finito. O problema com Logaritmo discreto é que em tais grupos de curvas elípticas ele é visto como mais difícil do que o problema correspondente no campo finito subjacente. Assim as chaves na criptografia de curvas elípticas podem ser escolhidas para serem muito mais curtas para um nível comparável da segurança.

Quanto a outros Sistemas Criptográficos de chaves públicas populares, nenhuma prova matemática de dificuldade foi publicada para a Criptografia de Curva Elíptica até à data de 2006. Entretanto, a agência da segurança nacional de Estados Unidos NSA endossou a tecnologia de Criptografia de Curva Elíptica incluindo em seu conjunto de Suite B os algoritmos recomendados. Embora a patente de RSA tenha expirado, há patentes que cobrem alguns aspectos de Criptografia de Curva Elíptica.

Introdução Matemática

As curvas elípticas usadas em Criptografia são definidas tipicamente em dois tipos de campos finitos: campos de característica impar p (${\displaystyle \mathbb {F} _{p}}$,, onde p > 3 é um número principal grande) e campos da característica par (${\displaystyle \mathbb {F} _{2^{m}}}$).Quando a distinção não é importante nós denotamos ambos eles como ${\displaystyle \mathbb {F} _{q}}$,onde q = p ou q = 2m. Em ${\displaystyle \mathbb {F} _{p}}$ os elementos são inteiros (${\displaystyle 0\leq x<p}$)que são combinados usando a aritmética modular. No caso ${\displaystyle \mathbb {F} _{2^{m}}}$ é um pouco mais complicado: um obtém representações diferentes dos elementos do campo como bitstrings para cada escolha do polinômio binário irretível f (x) do grau m.O conjunto de todos os pares das coordenadas (x, y) para ${\displaystyle (x,y)}$ para ${\displaystyle x,y\in \mathbb {F} _{q}}$ que forma o plano ${\displaystyle \mathbb {F} _{q}\times \mathbb {F} _{q}}$. Uma curva elíptica é o locus dos pontos do plano cujas coordenadas satisfazem a uma determinada equação cúbica junto com um ponto na infinidade O. No caso p>3 a equação definida de ${\displaystyle E(\mathbb {F} _{p})}$ pode ser escrita ${\displaystyle y^{2}=x^{3}+ax+b}$, onde ${\displaystyle a\in \mathbb {F} _{p}}$ e ${\displaystyle b\in \mathbb {F} _{p}}$ são constantes tanto que ${\displaystyle 4a^{3}+27b^{2}\neq 0}$. No outro caso a equação definida de ${\displaystyle E(\mathbb {F} _{2^{m}})}$ pode ser escrita: ${\displaystyle y^{2}+xy=x^{3}+ax^{2}+b}$ onde ${\displaystyle a\in \mathbb {F} _{2^{m}}}$ e ${\displaystyle b\in \mathbb {F} _{2^{m}}}$ são constantes e ${\displaystyle b\neq 0}$. Embora o ponto na infinidade O não tenha coordenadas, é conveniente representá-las , usando um par das coordenadas que não satisfazem à equação definida, por exemplo ${\displaystyle O=(0,0)}$ se ${\displaystyle b\neq 0}$ e ${\displaystyle O=(0,1)}$. De acordo com o teorema de Hasse em curvas elípticas o número dos pontos em uma curva é quase o do tamanho do campo subjacente; mais precisamente: ${\displaystyle ({\sqrt {q}}-1)^{2}\leq |E(\mathbb {F} _{q})|\leq ({\sqrt {q}}+1)^{2}}$. Os pontos em uma curva elíptica dão forma a um grupo abeliano ${\displaystyle (E(\mathbb {F} ),+)}$ com ${\displaystyle O}$ o ponto distinto na infinidade. Ou seja dado dois pontos ${\displaystyle P,Q\in E(\mathbb {F} _{q})}$, , há um terceiro ponto, denotado por ${\displaystyle P+Q}$ on ${\displaystyle E(\mathbb {F} _{q})}$, e as seguintes relações servem para todos ${\displaystyle P,Q,R\in E(\mathbb {F} _{q})}$ :

• ${\displaystyle P+Q=Q+P}$ (comutativo)
• ${\displaystyle (P+Q)+R=P+(Q+R)}$ (associativo)
• ${\displaystyle P+O=O+P=P}$ (existência de um elemento identidade)
• ${\displaystyle (-P)}$ ${\displaystyle -P+P=P+(-P)=O}$ (existência dos inversos)

Nós já especificamos como O é definido. Se nós definirmos o negativo de um ponto ${\displaystyle P=(x,y)}$ para ser ${\displaystyle -P=(x,-y)}$ para ${\displaystyle P\in E(\mathbb {F} _{p})}$ e ${\displaystyle -P=(x,x+y)}$ para ${\displaystyle P\in E(\mathbb {F} _{2^{m}})}$, nós podemos definir a operação da adição da seguinte forma:

• se ${\displaystyle Q=O}$ então ${\displaystyle P+Q=P}$
• se ${\displaystyle Q=-P}$ então ${\displaystyle P+Q=O}$
• se ${\displaystyle Q\neq P}$ então ${\displaystyle P+Q=R}$, onde
  • No primeiro caso: ${\displaystyle x_{R}=\lambda ^{2}-x_{P}-x_{Q}}$, ${\displaystyle y_{R}=\lambda (x_{P}-x_{R})-y_{P}}$, e ${\displaystyle \lambda ={\frac {y_{Q}-y_{P}}{x_{Q}-x_{P}}}}$, ou
  • No segundo caso: ${\displaystyle x_{R}=\lambda ^{2}+\lambda +x_{P}+x_{Q}+a}$, ${\displaystyle y_{R}=\lambda (x_{P}+x_{R})+x_{R}+y_{P}}$, e ${\displaystyle \lambda ={\frac {y_{P}+y_{Q}}{x_{P}+x_{Q}}}}$

• se ${\displaystyle Q=P}$ então ${\displaystyle P+Q=R}$, onde
  • no primeiro caso ${\displaystyle x_{R}=\lambda ^{2}-2x_{P}}$, ${\displaystyle y_{R}=\lambda (x_{P}-x_{R})-y_{P}}$, e ${\displaystyle \lambda ={\frac {3x_{P}^{2}+a}{2y_{P}}}}$, ou
  • no segundo caso ${\displaystyle x_{R}=\lambda ^{2}+\lambda +a}$, ${\displaystyle y_{R}=x_{P}^{2}+(\lambda +1)x_{R}}$, e ${\displaystyle \lambda =x_{P}+{\frac {y_{P}}{x_{P}}}}$

Esquemas Criptográficos

Desde que o grupo cíclico (aditivo) descrito acima pode ser considerado similar ao grupo (multiplicativo) de potências de um inteiro g de módulo primo p: ${\displaystyle (g^{0},g,g^{2},g^{3},g^{4},\ldots )}$, o problema de encontrar k dados os pontos kG e G é chamado o Problema Discreto do Logaritmo da Curva Elíptica (em Inglês - Elliptic Curve Discrete Logarithm Problem - ECDLP). A dificuldade suposta de diversos problemas relacionados ao logaritmo discreto no subgrupo de ${\displaystyle E(\mathbb {F} _{q})}$ permite o uso da Criptografia de Curva Elíptica (CCE). A maioria dos esquemas de curva elíptica criptográficos são relacionados aos esquemas discretos dos logarítmos que foram formulados originalmente para a aritmética modular usual: O esquema chave do acordo de Diffie-Hellman da curva elíptica é baseado no esquema de Diffie-Hellman.

• O algoritmo da assinatura digital da curva elíptica é baseado no algoritmo da assinatura de digital.
• O esquema chave do acordo de ECMQV é baseado no esquema chave do acordo de MQV.

Nem todos os esquemas do DLP devem ser movidos ao domínio curva elíptica. Por exemplo, o poço - o esquema conhecido como Criptografia de ElGamal nunca foi estandardizado por corpos oficiais e não deve diretamente ser usado sobre uma curva elíptica (o esquema padrão de criptografia para ECC é chamado esquema integrado de Curva de Criptografia Elíptica). A razão principal é que embora seja simples converter uma mensagem arbitrária (de comprimento limitado) a um modulo inteiro p, não é simples converter bitstring a um ponto de curva. Na conferência 2005 de RSA ,a agência da segurança nacional (NSA) anunciou o Suite B que usa exclusivamente ECC para a geração digital da assinatura e a troca da chave. O suite é pretende proteger sistemas classificados e não-classificados e informação da segurança nacional. Uma outra fonte principal de aplicações criptográficas de curvas elípticas é o operador bilinear (baseado em se Weil pairing ou Tate pairing) que permite fazer, por exemplo, eficiente criptografia de identidade-baseada.

Considerações de Execução

Mesmo que os detalhes de cada curva elíptica em particular sejam descritos em seus próprios artigos, aqui você encontrará algumas implementações sobre alguns assuntos.

Parâmetros do Domínio

Para usar ECC, todos os partidos devem concordar com todos os elementos que definem a curva elíptica, que é parâmetro do domínio do esquema. A curva elíptica é definida pelas constantes a e b usadas em sua equação definida. Finalmente, o subgrupo cíclico é definido por seu gerador (aka. ponto base) ${\displaystyle G}$. Para a aplicação criptográfica a ordem de G, aquele é o número não-negativo o menor n tais que o ${\displaystyle nG=O}$, devem ser os primeiros. Desde que n é o tamanho de um subgrupo de ${\displaystyle E(\mathbb {F} _{q})}$ segue do teorema de Lagrange que o número ${\displaystyle h={\frac {|E|}{n}}}$ é inteiro. Em aplicações criptográficas este número h, chamado cofator, pelo menos deve ser pequeno (${\displaystyle h\leq 4}$) e, preferivelmente, ${\displaystyle h=1}$. No caso principal os parâmetros do domínio são ${\displaystyle (p,a,b,G,n,h)}$ e no segundo caso eles são ${\displaystyle (m,f,a,b,G,n,h)}$. A menos que haja a garantia que os parâmetros do domínio foram gerados por um partido confiável com respeito a seu uso, os parâmetros do domínio devem ser validados antes de usar. A geração de parâmetros do domínio não é feita geralmente por cada participante desde que esta envolva contar o número dos pontos em uma curva que seja cansativa e incômoda para executar.

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

• selecionar uma curva aleatória e usar um algoritmo decontagem geral;
• selecionar uma curva aleatória de uma família que permita o cálculo fácil do número dos pontos ou;
• selecionar o número dos pontos e gerar uma curva com este número dos pontos usando a técnica complexa da multiplicação.

Tamanhos Chaves

Desde que os os algoritmos mais rápidos que permite solucionar o ECDLP, precisa ${\displaystyle O({\sqrt {n}})}$ etapas, isso indica que o tamanho do campo subjacente será aproximadamente duas vezes o parâmetro da segurança. Por exemplo, para segurança de 128 bits necessita de uma curva maior que ${\displaystyle \mathbb {F} _{q}}$, onde ${\displaystyle q\approx 2^{256}}$. Isto pode ser contrastado com a criptografia de campo-finito (por exemplo, DSA) que requer [10] 3072 bits de chaves públicas e 256 bits chaves confidenciais , e criptografia de fatoração de inteiros (por exemplo, RSA) que requer o 3072 bits de chave-pública de 3072 bits e chaves-confidenciais. O esquema o mais difícil de ECC (publicamente) teve 109 bits de chave (que é aproximadamente 55 bits de segurança).Como primeiro exemplo do campo, foi quebrado no começo de 2003 usando-se mais que 10.000 PCs da classe Pentium que funcionam continuamente por mais que 540 dias. Como segundo exemplo do campo, foi quebrado em abril 2004 usando 2600 computadores por 17 meses.

Coordenadas Projetáveis

Uma examinação mais próxima das réguas de adição mostra que a fim adicionar dois pontos necessita-se não somente de diversas adições e multiplicações em ${\displaystyle \mathbb {F} _{q}}$ mas também uma operação inversa.

A inversão (dado ${\displaystyle x\in \mathbb {F} _{q}}$ encontrar ${\displaystyle y\in \mathbb {F} _{q}}$ tanto que ${\displaystyle xy=1}$) é uma das duas ordens de valor mais lentas do que a multiplicação. Felizmente, os pontos em uma curva podem ser representados em sistemas coordenados diferentes que não requerem uma operação inversa para adicionar dois pontos. Diversos sistemas foram propostos:

• no sistema projetável cada ponto é representado por três coordenadas (X, Y, Z) usando a seguinte relação: ${\displaystyle x={\frac {X}{Z}}}$, ${\displaystyle y={\frac {Y}{Z}}}$;
• no sistema de Jacobian um o ponto é representado também com as três coordenadas (X, Y, Z), mas uma relação diferente é usada: ${\displaystyle x={\frac {X}{Z^{2}}}}$, ${\displaystyle y={\frac {Y}{Z^{3}}}}$;
• no sistema modificado de Jacobian as mesmas relações são usadas mas quatro coordenadas são armazenadas e usadas para cálculos ${\displaystyle (X,Y,Z,aZ^{4})}$.

Implementações de Fonte Aberta

• OpenSSL: Open source library written in C with ECC library
• NSS: Open source crypto libraries with ECC
• Crypto++: Open source Crypto Package written in C++ with ECC library
• MIRACL: Multiprecision Integer and Rational Arithmetic C/C++ Library
• LibTomCrypt: Public domain crypto library with ECC
• seccure: minimal footprint GPLed ECC tool with public key encryption and digital signatures
• SKS: very small open source tool for ECC (like a simplified PGP)
• eccGnuPG: An experimental patch to GnuPG
• Curve25519: A state-of-the-art Diffie-Hellman function by Dan Bernstein
• TinyECC: a software package providing ECC operations on TinyOS
• libecc: Open source ECC library
• Bouncy Castle: Open source crypto package for Java and C# that includes ECC

Referências

• N. Koblitz, Elliptic curve cryptosystems, in Mathematics of Computation 48, 1987, pp. 203–209
• V. Miller, Use of elliptic curves in cryptography, CRYPTO 85, 1985.
• G. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic Number Theory Symposium, 1994.
• S.D. Galbraith and N.P. Smart, A cryptographic application of the Weil descent, Cryptography and Coding, 1999.
• P. Gaudry, F. Hess, and N.P. Smart,Constructive and destructive facets of Weil descent on elliptic curves, Hewlett Packard Laboratories Technical Report, 2000.
• A. Menezes, T. Okamoto, and S.A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, Volume 39, 1993.
• I. Semaev, Evaluation of discrete logarithm in a group of P-torsion points of an elliptic curve in characteristic P, Mathematics of Computation, number 67, 1998.
• N. Smart, The discrete logarithm problem on elliptic curves of trace one, Journal of Cryptology, Volume 12, 1999.
• T. Satoh and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Mathematici Universitatis Sancti Pauli, Volume 47, 1998.
• NIST, Recommendation for Key Management — Part 1: general, Special Publication 800-57, August 2005.
• Y. Hitchcock, E. Dawson, A. Clark, and P. Montague, Implementing an efficient elliptic curve cryptosystem over GF(p) on a smart card, 2002.
• H. Cohen, A. Miyaji, T. Ono, Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, ASIACRYPT 1998.
• M. Brown, D. Hankerson, J. Lopez, and A. Menezes,Software Implementation of the NIST Elliptic Curves Over Prime Fields.
• M. Hedabou, P. Pinel, and L. Beneteau, A comb method to render ECC resistant against Side Channel Attacks, 2004.

Implementações

• Standards for Efficient Cryptography Group (SECG), SEC 1: Elliptic Curve Cryptography, Version 1.0, September 20, 2000.
• D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004.
• I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, London Mathematical Society 265, Cambridge University Press, 1999.
• I. Blake, G. Seroussi, and N. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society 317, Cambridge University Press, 2005.
• L. Washington, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall / CRC, 2003.
• The Case for Elliptic Curve Cryptography, National Security Agency

• Portal das tecnologias de informação