elikaski/ecc_attacksAtaques conhecidos em Criptografia de Curva Elíptica
Nos últimos anos, a abordagem da Criptografia de Curvas Elípticas tornou-se popular devido à sua alta eficiência e forte segurança. O objetivo deste artigo é apresentar este tema de uma forma relativamente mais clara do que a que existe hoje na internet.
Neste artigo apresentarei o que são curvas elípticas, as operações básicas que podem ser realizadas nelas e como podem ser utilizadas em contexto criptográfico. A maior parte deste artigo consiste em exemplos de ataques conhecidos a implementações incorretas ou utilizações erradas das mesmas. Ao longo do artigo, tento separar a explicação numa parte intuitiva e de alto nível, e numa parte matemática que entra em mais detalhes. O leitor é convidado a focar-se na parte que lhe interessar naquele ponto e a saltar as partes que lhe interessam menos.
Boa leitura!
Em geral, uma curva elíptica é algum tipo de linha curva. Um exemplo disso é a parábola, cuja equação é da forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ e tem este aspeto:
No contexto da criptografia, é habitual utilizar curvas elípticas cuja equação é da forma
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Por exemplo, uma curva elíptica correspondente à equação $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ tem este aspeto:
A equação da curva define a relação entre a coordenada 𝑥 de um ponto na curva e a sua coordenada 𝑦. Num contexto criptográfico, restringimos 𝑥, 𝑦, 𝑎, 𝑏 a números inteiros e restringimos os cálculos a serem feitos módulo algum número primo grande. Portanto, a equação da curva elíptica é:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Isto significa que temos um número finito de pontos na curva. Em linguagem matemática, a curva é definida sobre um corpo finito de ordem 𝑝. Como resultado, agora nem todos os valores de 𝑥 terão necessariamente um ponto correspondente na curva, porque pode acontecer que a coordenada 𝑦 correspondente não seja um número inteiro.
O conjunto de pontos na curva consiste em pares de números inteiros (𝑥, 𝑦) que satisfazem a equação da curva. Além destes pontos, é definido outro ponto especial chamado "Infinito", e é denotado por 𝒪. Em linguagem matemática, este ponto é o elemento neutro do conjunto de pontos na curva em relação à operação de adição, que definiremos na próxima secção. O número de pontos na curva (incluindo o ponto 𝒪) é chamado de "ordem da curva".
Outra observação é que as curvas elípticas são simétricas em relação ao eixo X. Isso significa que se o ponto 𝑃 = (𝑥, 𝑦) está na curva, então o ponto −𝑃 = (𝑥, −𝑦) também está na curva. Na verdade, esses pontos são considerados "inversos" um do outro (daí a marcação −𝑃 para o segundo ponto), e o resultado da operação de adição entre eles é definido como o elemento neutro 𝒪.
Um teorema chamado Teorema de Hasse fornece uma estimativa de #𝐸, a ordem da curva, e é da ordem de grandeza de Θ(𝑝). Mais precisamente:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Dados dois pontos na curva, é possível definir uma operação de adição entre eles, resultando num terceiro ponto que também está na curva. Para encontrar este ponto geometricamente, traçamos uma linha entre os dois pontos dados e continuamo-la até que intersete a curva num terceiro ponto. Este ponto é refletido em relação ao eixo 𝑋, e o ponto resultante é definido como o resultado da adição.
Aqui está um diagrama que mostra como, dados os pontos 𝑃 e 𝑄, o ponto 𝑃 + 𝑄 pode ser encontrado:
Uma questão que pode surgir desta descrição é: o que acontece se a linha traçada entre os dois pontos não intersetar a curva novamente? Neste caso, diz-se que a linha interseta a curva no "infinito", e o resultado da adição é o ponto 𝒪. Repare que este caso acontece se a linha traçada for vertical, ou seja, se estivermos a tentar adicionar um ponto 𝑃 ao seu ponto inverso, −𝑃:
Duas identidades básicas derivam daqui. Para todo o ponto 𝑃, vale que:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Outra questão que surge da descrição geométrica é: como adicionamos um ponto a si próprio? Vimos que, para adicionar dois pontos diferentes 𝑃 e 𝑄, traçamos uma linha entre eles e observamos o ponto de interseção da sua continuação com a curva. Intuitivamente, deixaremos 𝑃 constante e observaremos a linha que é criada à medida que movemos 𝑄 "cada vez mais perto" de 𝑃, até 𝑄 se fundir com 𝑃. O que obteremos é uma linha cada vez mais "tangente" à curva no ponto 𝑃, e é exatamente essa a linha que observaremos quando quisermos adicionar 𝑃 a si próprio:
Para adicionar um ponto 𝑃 a si próprio, traçamos uma tangente à curva no ponto 𝑃 e continuamo-la até que intersete a curva num segundo ponto. Este ponto é refletido em relação ao eixo 𝑋, e o ponto resultante é definido como o resultado da adição. É habitual marcar o resultado da adição como 𝑃 + 𝑃 = 2𝑃. Novamente, se a tangente não intersetar a curva num segundo ponto, então diz-se que interseta a curva no "infinito", e o resultado da adição neste caso é o ponto 𝒪.
Estas descrições geométricas visuais ilustram bem e ajudam-nos a compreender como funciona a adição de pontos. Mas como é que realmente a calculamos? Equações matemáticas, claro!
Dados os pontos $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ e $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, o resultado da sua adição é o ponto $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ tal que:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
