Sistemas Criptográficos baseados em Curvas Elípticas



Sistemas Criptográficos baseados em Curvas Elípticas

Curvas Elípticas

Curvas Elípticas sobre Números Reais
Curvas Elípticas sobre Corpos Finitos Primos
Curvas Elípticas sobre Corpos Finitos de Característica Dois
Multiplicação sobre Curvas Elípticas
Ordem da Curva

Curvas Elípticas sobre Números Reais	Início da Página

Para melhor entendimento do conceito matemático das curvas elípticas, iniciemos nosso estudo no campo dos reais. A equação abaixo mostra a forma de “Weierstrass” de uma curva elíptica: (1) As variáveis x e y situam-se no plano. Na verdade, x e y podem ser complexos, reais, inteiros, base polinomial, base canônica ou qualquer outro tipo de elemento de corpo. Mas, consideremos números reais sobre o plano dos reais, que nos é mais familiar. Uma forma simples da equação (1) é: (2) Como exemplo, vamos representar o gráfico da curva para a₄ = -7, a₆ = 5 com x e y no conjunto dos números reais: Figura 1 - Gráfico da curva elíptica y²=x³-7x+5 Nossa intenção é definir uma álgebra para curvas elípticas. Assim, devemos encontrar uma maneira de definir “adição” de dois pontos da curva, cuja soma seja outro ponto da curva. Além disso, devemos definir o elemento identidade da soma O, ponto que somado com qualquer outro da curva, resulte no próprio ponto: P + O = P (3) Este ponto também é chamado de ponto no infinito. Para a álgebra funcionar, o negativo do ponto de interseção é definido como a “soma elíptica” (veja figura 2). Matematicamente: R = P + Q(4) Figura 2 – Adição de pontos de uma curva elíptica sobre números reais Adicionar um ponto a ele mesmo é um caso especial. A linha usada é a tangente à curva no ponto considerado.
Início da Página

Curvas Elípticas sobre Corpos Finitos Primos	Início da Página

Para utilização em criptografia interessa-nos estudar a matemática de curvas elípticas aplicadas a corpos finitos. Analisaremos, inicialmente, corpos finitos gerados por grandes primos. Ou seja, analisaremos curvas elípticas sobre Zp, p primo maior que 3. Uma curva elíptica E sobre Zp pode ser definida pela mesma equação (2) estudada no item anterior: onde a₄, a ₆ Î Zp e 4a ₄³ + 27a₆²¹ 0. O conjunto E(Zp) é composto, então, por todos os pontos (x,y), xÎZp, yÎZp, que satisfazem a equação de definição, juntamente com o ponto no infinito O. Por exemplo: seja p = 23 e considere a curva elíptica E: y² = x³ + x + 1, definida sobre Z₂₃. Note que 4a₄³ + 27a₆² = 4 + 4 = 8 ¹ 0, então E é uma curva elíptica. Os pontos em E(Z₂₃) são O e os seguintes: (0, 1) (0, 22) (1, 7) (1, 16) (3, 10) (3, 13) (4, 0) (5, 4) (5, 19) (6, 4) (6, 19) (7, 11) (7, 12) (9, 7) (9, 16) (11, 3) (11, 20) (12, 4) (12, 19) (13, 7) (13, 16) (17, 3) (17, 20) (18, 3) (18, 20) (19, 5) (19, 18) Vejamos a regra para adicionar dois pontos em uma curva elíptica E(Zp) para resultar em um terceiro ponto da curva. Junto com esta operação de adição, o conjunto de pontos E(Zp) forma um grupo, com O servindo como sua identidade. É este grupo que é utilizado na construção de sistemas de criptografia baseados em curvas elípticas. A regra de adição é apresentada abaixo como uma seqüência de fórmulas algébricas: 1. P + O = O + P = P para todo P Î E(Zp) 2. Se P = (x, y) Î E(Zp), então (x, y) + (x, -y) =O. (O ponto (x, -y) é representado por –P e é chamado negativo de P. Observe que –P é, também, um ponto na curva.) 3. Seja P = (x₁,y₁) Î E(Zp) e Q = (x₂,y₂) Î E(Zp), onde P ¹ -Q. Então P + Q = (x₃,y₃), onde: (5) (6) e (7) (8) Vamos ver um exemplo de adição de curva elíptica. Considere a curva elíptica definida no exemplo anterior. 1. Seja P = (3, 10) e Q = (9, 7). Então P + Q = (x₃, y₃) é calculado como segue: x₃ = 112 - 3 - 9 = 6 - 3 - 9 = -6 Î 17 (mod 23), e y₃ = 11(3 - (-6)) -10 = 11(9) -10 = 89 Î 20 (mod 23). Portanto, P + Q = (17,20). 2. Seja P = (3,10). Então 2P = P + P = (x₃, y₃) é calculado como segue: x₃ = 62 - 6 = 30 Î 7 (mod 23), e y₃ = 6 (3 -7) -10 = -24 -10 = -11 Î 12 (mod 23). Portanto, 2P = (7,12).
Início da Página

Curvas Elípticas sobre Corpos Finitos de Característica Dois	Início da Página

Os corpos finitos de característica dois, GF(2^m), interessam especialmente, pois permitem implementações eficientes da aritmética de curvas elípticas. Neste caso, as constantes são números de base polinomial ou canônica. Não podemos, neste caso, utilizar a versão simplificada da equação (1). Menezes [3] afirma que é necessário uma das duas versões abaixo: (9) (10) A equação (9) é da forma “supersingular” e, embora possa ser computada rapidamente, suas propriedades não a tornam indicadas para o uso em criptografia. As curvas da equação (10) são chamadas “nonsupersingular”. Não existe nenhum método de ataque conhecido de complexidade menor que exponencial para estas curvas. Certamente, a escolha dos coeficientes é fundamental, a fim de que se obtenha a máxima vantagem da segurança. Para que a equação (10) seja válida, a₆ precisa ser diferente de 0. Contudo, a₂ pode ser 0. Valem aqui as mesmas regras de adição vistas para corpos primos. As fórmulas, contudo, são um pouco diferentes para adição de dois pontos sobre GF(2ⁿ), segundo Schroeppel et al.[4]: Se P ¹ Q: (11) (12) (13) Se P = Q: (14) (15) (16)
Início da Página

Multiplicação sobre Curvas Elípticas	Início da Página

A multiplicação sobre curvas elípticas se refere, ao contrário da idéia intuitiva de se multiplicar dois pontos da curva, ao produto de um escalar por um ponto da curva: Q = kP (17) Onde Q e P são pontos sobre uma curva elíptica e k é um inteiro. O que a multiplicação realmente significa é a soma de Pa ele mesmo k vezes. Como a própria curva elíptica – isto é, os pontos sobre ela – forma um corpo, o inteiro k não deve ser maior que a ordem do ponto P. Caso não se saiba a ordem do ponto, o cálculo não será tão eficiente quanto poderia ser. Exemplo: suponha que desejamos calcular Q = 15P. Podemos expandir como: Q = 15P = P + 2(P + 2(P + 2P)) Observe que este é o mesmo algoritmo utilizado para exponenciação modular. Outro método para o cálculo da multiplicação é a expansão balanceada, proposta por Koblitz [5]. O algoritmo converte uma string de bits “1” em uma string de bits “0” seguido de “–1”. Por exemplo, calculemos Q = 15P: 15P = (16-1)P 11112P = (1000-1)2P Q = (2P)2 2 * 2 - P* Temos, assim cinco operações, ao invés de seis, como no caso anterior. Outro exemplo: Q = 10045P = 100111001111012P. O último bit na cadeia de “1” é substituído por “–1”, todos os outros bits são substituídos por “0” e o primeiro “0” é substituído por “1”. Assim, a representação balanceada fica: 10100-101000-101 Q = (((((2P 2 + P)2 * 2 * 2 – P)2 * 2 + P)2 * 2 * 2 2 – P)2 2 + P*
Início da Página

Ordem da Curva	Início da Página

O número de pontos de uma curva elíptica sobre um corpo finito deve satisfazer o teorema de Hasse. Dado um campo, GF(q), a ordem da curva N deverá satisfazer esta equação: (18) Ou, de outra forma: (19) Então, o número de pontos de uma curva é, aproximadamente, o tamanho do corpo.
Início da Página

Por favor mande comentários para:

Eduardo Wolski
Departamento de Engenharia Elétrica
Universidade de Brasília
eduardo@ene.unb.br

UnB - Departamento de Engenharia Elétrica
Mestrado em Engenharia de Redes e Tecnologias da Informação
Prof. Dr. Rafael T. de Sousa Jr. e Prof. MSc. Ricardo S. Puttini

@Webmaster: Michello Viana de Almeida, Paulo Ovídio I. Guimarães e Flávio Elias