A Criptografía de Curvas Elípticas, ou ECC, das iniciais em inglës Eliptic Curve Cryptography, é uma variante da criptografia assimétrica ou de chave pública, baseada na matemática das curvas elípticas. Seus criadores argumentam que a ECC pode ser mais rápida e usar chaves mais curtas do que os métodos antigos—como RSA --, e proporcionar ao mesmo tempo um nível de segurança equivalente. A utilização de curvas elípticas em criptografia foi proposta de modo independente por Neal Koblitz e Victor Miller em 1985.

A criptografia assimétrica ou de chave pública usa duas chaves distintas: uma delas pode ser pública, a outra é privada. A posse da chave pública não proporciona informação suficiente para se determinar qual é a chave privada.

Existem várias versões de criptografia de curvas elípticas. Todas elas, com pequenas variações se baseiam na crença amplamente aceita da dificuldade de se resolver o problema de um logaritmo discreto para o grupo de uma curva elíptica sobre alguns corpos finitos. Os corpos finitos mais usados para isso são os inteiros módulo um número primo—ver aritmética modular, ou um grupo de Galois cujo tamanho seja potência de 2. Também foram propostos grupos de Galois cujo tamanho seja potência de algum número primo, mas eles geraram dúvidas entre os criptoanalistas.

Dada uma curva elíptica E, e um grupo GF(q), consideramos o grupo abeliano de pontos racionais E(q) na forma (x, y), onde x e y pertencem a GF(q), e onde a operação de grupo + se define nesta curva como descrito no artigo curva elíptica. Define-se então uma segunda operação "*" | Z×E(q) → E(q): se P é algum ponto em E(q), então definimos 2*P = P + P, 3*P = 2*P + P = P + P + P, e assim por diante. Note-se que dados os inteiros j e k, j*(k*P) = (j*k)*P = k*(j*P). O problema do logaritmo discreto de uma curva elíptica (PLDCE) é, pois, determinar o inteiro k, dados os pontos P e Q, quando k*P = Q.

É crença corrente que o problema típico do logaritmo discreto sobre o grupo muiltiplicativo (PLD) e o PLDCE não são problemas equivalentes; ao contrário, crê-se que o PLDCE é significativamente mais difícil do que o PLD.

Em criptografia, escolhe-se um ponto base G específico e público para se usar com a curva E(q). Escolhe-se um número inteiro aleatório k como chave privada. Então o valor P = k*G é divulgado como chave pública. Note que a suposta dificuldade da PLDCE implica que é difícil deduzir k a partir de P.

Se Maria e Pedro têm as chaves privadas k_A e k_B, então Maria poderia calcular k_A*P_B = (k_A*k_B)*G. E pedro pode obter o mesmo valor dado que k_B*P_A = (k_B*k_A)*G.

Isto permite estabelecer um valor "secreto" que tanto Maria quanto Pedro podem calcular facilmente, mas que é muito mais complicado de ser derivado por uma terceira pessoa. Além disso, Pedro não consegue averiguar nada novo sobre k_A, de modo que a chave de Maria continua a ser privada.

Os métodos utilizados na prática para se codificar mensagens a partir desse valor secreto são adaptações de antigos sistemas criptográficos de logaitmos discretos originalmente projetados para ser usados em outros grupos. Entre eles podem ser incluídos Diffie-Hellman, ElGamal e DSA.

As operações necessárias para se executar este sistema são mais lentas do que aquelas de um sistema de fatorização ou de logaritmo discreto módulo um inteiro do mesmo tamanho. De qualquer modo, os autores de sistemas de ECC acreditam que o PLDCE é significativamente mais complicado que os problemas de fatorização ou de PLD. Assim, pode-se obter a mesma segurança usando-se chaves muito menores usando-se ECC. Ao ponto de que este algoritmo torna-se mais rápido do que, por exemplo, o RSA. Os resultados publicados até aqui tendem a confirmar esta conjectura, mas alguns especialistas ainda se mostram céticos.

A ECC tem sido amplamente reconhecida como o algoritmo mais forte para um dado comprimento de chave, pelo que poderia se mostrar útil em conexões de rede que tenham requisitos muito limitados de largura de banda.

O NIST e o grupo X9 da ANSI estabeleceram requisitos mínimos de tamanho de chave: 1024 bits para RSA e DSA e 160 bits para ECC, correspondentes a um bloco simétrico de de 80 bits. O NIST publicou uma lista de curvas elípticas recomendadas de 5 tamanhos distintos de chave: 80, 112, 128, 192 e 256 bits. Em geral a ECC sobre um grupo binário requer uma chave assimétrica com o dobro de tamanho do que aquele correspondente a uma chave simétrica.

A principal empresa comercial ligada ao ECC é a Certicom, que possui 130 patentes e outorgou licenças sobre a tecnologia para NSA por 25 milhões de dólares. A Certicom também patrocinou vários desafios ao algoritmo ECC. O resultado mais complexo até aqui é uma chave de 109 bits que foi quebrada por uma equipe de investigadores no começo de 2003. A equipe que rompeu a chave utilizou um ataque massivo em paralelo baseado no birthday attack.

Para este ataque foram mobilizados mais de 10.000 PCs do tipo Pentium funcionando continuamente durante 540 dias. Estima-se que a chave de comprimento mínimo recomendado para ECC, de 163 bits, exigira recursos 10⁸ maiores do que aqueles usados para resolver o problema da chave de 109 bits.