 |
Home | Login / Cadastro | Contato |
|
|||||||||||||||||||||||
Criptografia com Curvas Elípticas
 Curvas
Elípticas sobre Números Reais |
|
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: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) é: Como exemplo, vamos representar o gráfico da curva para a4 = -7, a6 = 5 com x e y no conjunto dos números reais: 
Figura 1 - Gráfico da curva elíptica y2=x3-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.
|
|
(1)
(2)
|
Curvas
Elípticas sobre Corpos Finitos Primos |
|
| 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 a4, a 6 Î Zp e 4a 43 + 27a62 ¹ 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: y2 = x3 + x + 1, definida sobre Z23. Note que 4a43 + 27a62 = 4 + 4 = 8 ¹ 0, então E é uma curva elíptica. Os pontos em E(Z23) são O e os seguintes: (0, 1) (0, 22) (1, 7) (1, 16) (3, 10) (3, 13) (4, 0) (5, 4) (5, 19)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 = (x1,y1) Î E(Zp) e Q = (x2,y2) Î E(Zp), onde P ¹ -Q. Então P + Q = (x3,y3), onde: e
(8) Vamos ver um exemplo de adição de
curva elíptica. Considere a curva elíptica definida no exemplo
anterior. Portanto, P + Q = (17,20). 2. Seja P = (3,10). Então 2P = P + P = (x3, y3) é calculado como segue: Portanto, 2P = (7,12).
|
|
(5) 
(6)
|
Curvas
Elípticas sobre Corpos Finitos de Característica Dois |
|
| Os
corpos finitos de característica dois,
GF(2m),
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: 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, a6 precisa ser diferente de 0. Contudo, a2 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(2n),
segundo Schroeppel et al.[4]:
|
|
(9) 
(10)
(11)
(14)
|
Multiplicação
sobre Curvas Elípticas |
|
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: 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
|
|
|
Ordem
da Curva |
|
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:
Ou, de outra forma: Então, o número de pontos de uma curva é, aproximadamente, o tamanho do corpo.
|
|
(18)
(19)Fonte: http://www.redes.unb.br/security/criptografia/curvaselipticas/curvas.html
Tópicos Relacionados:
| Home | Missão | Serviços | Tecnologia | Contato | Produtos | Fórum | Loja Virtual |
| Copyright © 2006 SmartSEC. Todos os direitos Reservados |