Nos últimos anos, uma grande parte da investigação feita em criptografia de chave pública tem-se desviado dos grupos definidos sobre os números inteiros mod m, i.e.
$$\mathbb{Z}/m\mathbb{Z}$$
, para os grupos definidos por curvas elípticas sobre um corpo finito K, este geralmente
$$\mathbb{F}_p$$
ou
$$\mathbb{F}_{2^m}$$
— E/K. Não só a investigação, mas também a própria indústria tem-se virado para as curvas elípticas em detrimento dos algoritmos mais clássicos - o NIST definiu em 1999 uma série de curvas e corpos standard e em 2006 anunciou a Suite B, um conjunto de algoritmos aprovados para proteger dados até ao nível ‘Top Secret’.
A que é que se deve esta mudança?
Tem a ver com a estrutura, ou falta dela, existente nas curvas elípticas. No caso do Diffie-Hellman ou RSA clássico, estamos a trabalhar nos números inteiros mod N, e o problema fundamental a resolver é a factorização de um produto de dois primos ou o logaritmo discreto. Ambos estes problemas podem ser resolvidos com essencialmente o mesmo algoritmo — NFS. A complexidade deste é:
$$O(e^{\frac{64}{9}^{1/3} (\log n)^{1/3} (\log \log n)^{2/3}})$$
A razão pela qual este algoritmo funciona em tempo sub-exponencial relativamente a n está relacionada com a estrutura de
$$\mathbb{Z}$$
— todos os inteiros podem ser representados como um produto de factores primos. Associando esta propriedade às propriedades dos logaritmos e exponenciações e à distribuição dos números primos, conseguimos resolver logaritmos discretos em menos tempo do que os métodos genéricos, como o Pollard’s Rho. Nos grupos das curvas elípticas sobre um corpo, para parâmetros razoavelmente bem escolhidos, não são conhecidos algoritmos sub-exponenciais ou polinomiais para resolver o problema onde reside a segurança do algoritmo.
Antes de mais, vamos definir uma curva elíptica. Na prática, uma curva elíptica é definida pela equação de Weierstrass num corpo finito arbitrário:
$$y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6$$
Os coeficientes
$$a_1 \ldots a_6$$
definem, portanto, a curva. Tipicamente, quando a curva é definida sobre o corpo finito dos inteiros mod p, p primo, apenas
$$a_4$$
e
$$a_6$$
são diferentes de 0 (uma excepção sendo a Curve25519 do djb).
Naturalmente, os elementos deste grupo serão as soluções da equação acima — dado que existem duas soluções para cada x, os elementos são definidos como pontos P = (x, y) na curva. Ainda nos falta, no entanto, a operação de grupo - a adição. Esta é ligeiramente diferente para o caso em que P != Q e P = Q, quando queremos obter P+Q = (x3, y3), P=(x1, y1), Q=(x2, y2):
Adição
$$x3 = \frac{y2-y1}{x2-x1}^2 - x1 - x2 \\ y3 = \frac{y2-y1}{x2-x1}(x1-x3)-y1$$
Duplicação
$$x3 = \frac{3x1 + a_4}{2y1}^2 - 2x1 \\ y3 = \frac{3x1 + a_4}{2y1}(x1-x3)-y1$$
Existe ainda um ponto especial,
$$\infty$$
, que representa a identidade relativamente à adição, i.e.
$$P+\infty = \infty+P = P$$
.
Tendo o grupo definido, surge a operação relevante para fins criptográficos: a multiplicação. Esta é definida como:
$$nP = P+P+\ldots +P$$
i.e. n vezes o ponto P.
Outro conceito importante é a ordem de uma curva — o número total de pontos que nela existem — #E. Este valor deve ser sempre ou primo ou bastante próximo de um primo, de forma a evitar ataques conhecidos.
Uma propriedade importante da multiplicação em curvas elípticas é que é bastante fácil calcular
$$n P$$
, mas dado
$$P$$
e
$$n P$$
é extremamente difícil obter
$$n$$
. Este é o designado problema do logaritmo discreto em curvas elípticas. O melhor algoritmo conhecido para calcular este logaritmo é o Pollard’s Rho, que tem uma complexidade de
$$O({\#E}^{1/2})$$
A diferença entre o logaritmo discreto nas curvas elípticas e nos inteiros mod n é esta - não existe conceito de divisibilidade entre pontos, i.e. não existem pontos ‘primos’ nos quais seja possível decompor um ponto arbitrário. Esta (falta de) estrutura provê uma grande vantagem a nivel de segurança relativamente aos grupos mais clássicos.
Para fazer uma comparação directa entre os tamanhos dos corpos finitos necessários para uma segurança de 80 bits, podemos aplicar directamente as complexidades acima. Com curvas elípticas, precisamos de um corpo finito de tamanho
$${2^{80}}^2 = 2^{160}$$
, i.e. 160 bits. Com e.g. Diffie-Hellman, precisamos de pelo menos 896 bits de chave —
$$e^{\frac{64}{9}^{1/3} (\log 2^{896})^{1/3} (\log \log 2^{896})^{2/3}} \approx 2^{81.85}$$
. Note-se que isto são apenas complexidades assimptóticas; o custo real é muito diferente e geralmente muito, muito maior que o apresentado nestas fórmulas simplificadas.
Portanto, podemos ver como as curvas elípticas podem ser apelativas para quem implementa sistemas criptográficos — maior segurança por tamanho de chave, maior rapidez (derivado das chaves menores), menor estrutura dentro do grupo, minimizando as vias de ataque. Até agora parece ser em quase todos os sentidos uma opção superior ao RSA, ElGamal, DH tradicionais.
PS. Este post foi essencialmente elaborado para testar o
$$\LaTeX$$
no blol.
