CRIPTOGRAFIA DE CHAVE PÚBLICA BASEADA EM CURVAS ELÍPTICAS

Por Paulo Guilherme Nascimento | 11/01/2010 | Tecnologia

CRIPTOGRAFIA DE CHAVE PÚBLICA BASEADA EM CURVAS ELÍPTICAS

Paulo Guilherme dos Santos Nascimento

Graduado em Ciência da Computação – UFPA – PA

Pós-Graduado em Criptografia e Segurança de Redes – UFF - RJ

E-mail: pgsnascimento@hotmail.com



Resumo

O objetivo deste artigo é apresentar de uma forma introdutória alguns conceitos relacionados aos sistemas criptográficos baseados em curvas elípticas e explanar como as curvas elípticas podem ser usadas para esquemas de criptografia, destacando os de chaves públicas.

Palavra-chave: Chave Pública. Sistemas Criptográficos. Curvas Elípticas


Introdução

Os estudos sobre a aplicação de curvas elípticas em sistemas criptográficos através de algoritmos que utilizam idéias matemáticas, no caso, os conceitos de elipses, já contabilizam já algum tempo, em torno de vinte três anos. Quando essa técnica foi proposta em 1985 por Victor Miller [1] e Neal Koblitz [2] como uma atraente forma de implementação de um sistema de chave pública em algumas das aplicações existentes, despertou então o interesse dentro do contexto de criptografia. A ciência matemática correlacionadas às curvas elípticas é bastante antiga, há quase um século os estudos no campo da teoria dos números e geometria vem proporcionado uma aplicabilidade no mundo real e essa oportunidade surgiu recentemente com o advento da globalização e o tráfego intenso de dados através da grande malha de computadores interconectados - a Internet. Isso tudo gerou um grande interesse por parte de pessoas e instituições, visando comodidade e visão de negócio através desse mundo virtual.

E, para garantir que os critérios de confidencialidade e autenticidade, correspondam aos anseios de todos, surgiram vários métodos de criptografia. Sendo que o foco deste artigo será a Criptografia de curvas elípticas, ou ECC, das iniciais de Eliptic Curve Cryptography, que é uma variante da criptografia assimétrica, que tem como base os conceitos matemáticos relacionados as curvas elípticas sobre os corpos finitos. A principal idéia para implementar estes sistemas criptográficos é converter os dados em pontos dentro de uma curva, mas especificamente em curva elíptica.

Neste artigo pretende-se abordar, no primeiro momento, a motivação para o estudo dessa técnica, onde serão incluídos alguns argumentos, bem como uma comparação com o outro sistema criptográfico, no caso o RSA. Dessa forma, pretende-se começar chamando a atenção para o potencial associado ao uso dessa técnica. Em um segundo momento, serão introduzidas noções de álgebra baseada em curvas elípticas sobre números reais, sobre corpos finitos primos, sobre corpos finitos de características dois, multiplicação sobre curvas elípticas e ordem da curva, incluindo representações gráficas para cada uma dessas operações. Numa tentativa de convergir a teoria de curvas elípticas para uma técnica de criptografia, os itens seguintes abordarão aplicações dessas curvas e como essa técnica irá se transformar em um sistema de criptografia com chave pública. E, ao final serão observados os projetos de sistemas criptográficos de chave pública que devem possuir um compromisso entre o nível de segurança e o tempo de resposta que se deseja obter. Nesse aspecto, quanto mais desenvolvidos forem as ferramentas e algoritmos utilizados para a violação dos sistemas criptográficos existentes, maiores tamanhos têm que ser as chaves e, em conseqüência, maior o esforço computacional para a quebra da criptografia utilizada. Então, pode-se se avaliar e comparar as técnicas entre si.


Criptografia com Curvas Elípticas (ECC)

Segundo William Stallings [5] é importante frisar que curvas elípticas não são elipse. Essa afirmação pode provocar espanto para alguns leitores e gerar dúvidas para alguns ao lê-la. Porém, Stallings esclarece que esse nome foi estabelecido para definí-las como um objeto matemático, mais precisamente como curva, descrito por uma equação cúbica, as mesmas utilizadas para cálculo do comprimento de arco de uma elipse. Essa curvas podem assumir diversas formas que possuem propriedades interessantes. E, é exatamente essas propriedades que motivaram o interesse na aplicação das mesmas no contexto criptográfico.

Através da forma simplificada da equação cúbica y2 = x3 + a4x + a5 pode-se definir uma propriedade de que uma soma de dois pontos pertencentes a uma curva elíptica resulta num outro ponto na curva. Outra propriedade interessante é a do elemento identidade que seria a soma de qualquer ponto da curva com o ponto no infinito, conhecido como ponto O, resulta no próprio ponto.

Portanto, o conjunto de ponto (x,y) dessa curva poderiam ser valores inteiros, complexos, base canônicas ou qualquer outro tipo de elemento do corpo. Ao aplicar essas propriedades de formar restrita a um corpo finito, denominado de Fq. As operações necessárias para executar este sistema são mais lentas do que aquelas de um sistema de fatoração de inteiro ou de sistema de logaritmo discreto módulo um inteiro do mesmo tamanho. Acredita-se que o problema do logaritmo discreto de uma curva elíptica (PLDCE) é significativamente mais complicado que os problemas de fatoração ou de problema de logaritmo discreto (PLD). Assim pode-se obter a mesma segurança usando chaves muito menores com o ECC, tornando-se o algoritmo ECC mais rápido do que o RSA por exemplo.

Curvas Elípticas sobre os Números Reais (R)

Uma curva elíptica em R pode ser definida como o conjunto de pontos (x,y) que satisfaça a seguinte equação:

y² = x³ + ax + b, onde a e b são constantes reais, assim como as variáveis x e y.

Se o polinômio x³ + ax + b não contém fatores repetidos ou de forma equivalente se 4a³ + 27b² é diferente de zero, então a curva elíptica y² = x³ + ax + b pode ser usado para formar um grupo. O grupo é formado pelos pontos definidos pela curva elíptica juntamente com um ponto O, chamado de ponto no infinito.

A propriedade de Adição: Uma Abordagem Geométrica

Curvas elípticas formam um grupo, cuja operação básica é adição. A adição de dois pontos em uma curva elíptica é definida geometricamente.

Seja um ponto P = (xP,yP) pertencente à curva, é definido o negativo de P, a sua reflexão em relação ao eixo x, ou seja, -P = (xP,-yP).

Note que para todo ponto P, o ponto -P também pertence à curva (curvas elípticas são simétricas em relação ao eixo-x). Agora, será definida a soma de dois pontos distintos P e Q pertencentes à curva, tal que P ≠ -Q. Os pontos P e Q definem uma reta, que interceptará o gráfico da curva em exatamente mais um ponto, chamado -R. A soma em curvas elípticas é definida de maneira que P + Q = R.

Considerando o caso em que Q = -P, a linha definida por estes pontos é vertical e não corta o gráfico da curva em um terceiro ponto. É por esta razão que o grupo inclui o ponto no infinito O. Por definição P + (-P) = O. Como resultado desta equação, P + O = P. O ponto O é a identidade da operação de adição.

Considerando o caso em que Q = P, isto é, somar P a ele mesmo; se yP ≠ 0, a tangente a curva no ponto P interceptará o gráfico em outro ponto exatamente, chamado de -R. A operação de dobrar um ponto é definida de maneira que P + P = 2P = R.

Finalmente dobrando o ponto P, no caso em que yP = 0, a reta tangente sempre será vertical e não interceptará o gráfico da curva em outro ponto. Neste caso, por definição, 2P = O e como conseqüência disso 3P = P, 4P = O, 5P = P, 6P = O etc


A propriedade de Adição: Uma Abordagem Algébrica

Embora a descrição geométrica da adição ser um excelente método para ilustrar esta operação sobre curvas elípticas, ela não é um modo prático para implementação de computação aritmética. Fórmulas algébricas são derivadas da definição geométrica para permitir uma implementação eficiente.

Sejam dois pontos pertencentes à curva elíptica P = (xP,yP) e Q = (xQ,yQ), tal que Q ≠ -P. A fórmula algébrica que define o ponto R, tal que R = P + Q, é obtida pela resolução sistema abaixo, derivado da definição geométrica:

yP² = xP² + axP + b

yQ² = xQ² + axQ + b

(yQ - yP)x + (xP- xQ)y + xQyP - xPyQ = 0 ( reta que passa por P e Q )

y² = x³ + ax + b

Resolvendo o sistema acima é obtido as coordenadas do ponto R.

xR = s2 - xP - xQ e yR = -yP + s(xP – xR), onde s = (yP - yQ) / (xP - xQ)

(coeficiente angular da reta que passa por P e Q).

Seja um ponto P = (xP,yP), tal que yP ≠ 0. A fórmula algébrica que define o ponto R, tal que R = 2P, é obtida pela resolução sistema abaixo, derivado da definição geométrica.

yP² = xP² + axP + b

y = (3xP² + a)x/2yP + (2yP² - (3xP² + a))/2yP(reta que passa por P com inclinação da derivada da curva neste ponto)

y² = x³ + ax + b

Resolvendo o sistema acima , as coordenadas do ponto R são obtidas.

xR = s2 - 2xP e yR = -yP + s(xP – xR), onde s = (3xP2 + a) / (2yP ) (derivada da curva no ponto P)

Curvas Elípticas sobre Corpos Finitos Primos

Cálculos realizados sobre números reais são lentos e imprecisos, devido ao erro de arredondamento. Aplicações de criptografia requerem cálculos rápidos e precisos. Além disso, uma propriedade essencial para a criptografia é a finitude do conjunto de pontos, assim curvas elípticas sobre corpos inteiros finitos são utilizadas na prática. Nesta seção será abordado o uso de curvas elípticas sobre corpos finitos primos (FP) e na seção seguinte curvas elípticas sobre corpos de característica dois (F2m).

O campo FP é definido pelos números inteiros de 0 a p - 1, e todas operações são finalizadas calculando-se o resto da divisão por p. Uma curva elíptica sobre o campo

Fp é definida é definida pelo conjunto de pontos (x,y) que satisfaz equação a seguir:

y2 mod p = (x3 + ax + b) mod p, onde a e b são constantes que pertencem ao FP, assim como as variáveis x e y. Se o polinômio x³ + ax + b não contém fatores repetidos ou de forma equivalente se (4a³ + 27b²) mod p é diferente de zero, então a curva elíptica y² = x³ + ax + b pode ser usado para formar um grupo. O grupo é formado pelos pontos definidos pela curva elíptica juntamente com o ponto no infinito, O. A seguir, segue um exemplo de curva elíptica sobre o campo F23. Considerando a = 1 e b = 0, a seguinte equação é estabelecida: y2 mod p = (x3 + x) mod p

Os 23 pontos que satisfazem a esta equação são: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)

Repare que há dois pontos para valor de x, existindo uma simetria em torno de y = 11,5 aproximadamente. Curvas elípticas sobre os números reais apresentam um ponto negativo (reflexão em torno do eixo-x para todo ponto da curva). Sobre o campo F23, as componentes negativas dos valores de y são tomadas módulo 23, resultando em um número positivo. Sendo assim, o negativo de P = (xP, yP) é definido como -P = (xP, (-yP mod 23)).

A propriedade de Adição: Curvas Elípticas sobre Corpos Finitos Primos

Existem várias diferenças entre grupos de curvas elípticas sobre o FP e sobre os números reais. Grupos de curvas elípticas sobre o FP apresentam um número finito de pontos, desta forma fica difícil aplicar relações geométricas como no caso grupos de curvas elípticas sobre os números reais. No entanto, as relações algébricas para a operação de adição podem ser adaptadas. Ao contrário de curvas sobre os números reais, os cálculos sobre FP não apresentam erros de arredondamento, uma propriedade fundamental para sistemas criptográficos.

Sejam dois pontos pertencentes à curva elíptica P = (xP,yP) e Q = (xQ,yQ), tal que Q ≠ -P. A seguir é definida a fórmula algébrica que define o ponto R, tal que R = P + Q:

xR = (s2 - xP - xQ) mod p e yR = (-yP + s(xP - xR)) mod p, onde s = (yP - yQ) / (xP - xQ) mod p

A seguir, considere o ponto P, tal que yP ≠ 0. Segue a fórmula algébrica que define o ponto R, tal que R = 2P:

xR = (s2 - 2xP) mod p e yR = (-yP + s(xP - xR)) mod p, onde s = (3xP2 + a) / (2yP ) mod p


Curvas Elípticas sobre Corpos Finitos de Característica 2

Os elementos do campo F2m são vetores de m bits e possui dois tipos de apresentação: representação polinomial e base normal ótima. Como F2m opera em vetores de m bits, computadores podem realizar operações aritméticas de forma eficiente. Neste trabalho será apresentado somente a representação polinomial.

Uma curva elíptica sobre o campo F2m é definida é definida pelo conjunto de pontos (x,y) que satisfaz equação a seguir: y2 + xy = x3 + ax2 + b, onde a e b são constantes que pertencem ao F2m, assim como as variáveis x e y. A constante b deve ser diferente de zero. Como o campo é de característica dois, a equação que define a curva é um pouco diferente das equações apresentadas anteriormente. O grupo é formado pelos pontos definidos pela curva elíptica juntamente com o ponto no infinito, O.

Representação Polinomial

Os elementos de F2m são polinômios de grau menor que m com coeficientes binários.

{am-1xm-1 + am-2xm-2 + ... + a2x2 + a1x + a0 | ai = 0 ou 1}.

O polinômio pode ser representado em um vetor como (am-1 ... a1 a0). F2m possui 2m elementos. As principais operações em F2m são adição e multiplicação. Algumas operações envolvem um polinômio f(x) = xm + fm-1xm-1 + fm-2xm-2 + ... + f2x2 + f1x + f0, onde fi é um coeficiente binário. O polinômio f(x) (de grau m) precisa ser irredutível, isto é, não pode ser fatorado em outros dois polinômios. Este polinômio garante estas operações retornem polinômios pertencentes ao F2m. A adição de dois polinômios é definida como a operação de OU- Exclusivo bit a bit. A multiplicação é módulo f(x), ou seja, (am-1 ... a1 a0) (bm- 1 ... b1 b0) = (rm-1 ... r1 r0), onde rm- 1xm-1 + ... + r1x + r0 é o resto da divisão de (am-1xm-1 + ... + a1x + a0) (bm-1xm-1 + ... + b1x + b0) pelo polinômio f(x). Todos os coeficientes são calculados módulo 2. A operação de subtração é equivalente à adição e a operação de exponenciação é derivada de forma direta da multiplicação, ou seja, (am-1 ... a1 a0)k é realizada multiplicando k vezes (am-1 ... a1 a0).

Existe pelo menos um elemento g em F2m, tal que todos elementos em F2m, à exceção do polinômio identicamente nulo, podem ser expressados como uma potência de g. Este elemento é denominado o gerador de F2m.

A seguir, segue um exemplo, considerando o campo F24, utilizando a representação polinomial. O polinômio irredutível é f(x) = x4 + x + 1. O elemento g = (0010) é um gerador deste campo. As potencies de g são:


g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011)

g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g9 = (1010)

g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001)

g15 = (0001)

Em uma aplicação de criptografia, o parâmetro m deve ser grande o suficiente para permitir a criação de uma tabela imune a quebras. Atualmente, o uso de m = 160 é uma escolha confiável.

A tabela permite a utilização da notação que utiliza potência do gerador (gk), ao em vez de utilizar a notação de vetor de bits. Continuando utilizando o campo F24 com o polinômio irredutível f(x) = x4 + x + 1, considere a curva elíptica y2 + xy = x3 + g4x2 + 1, onde a = g4 e b = g0 =1.

Os quinze pontos que satisfazem esta equação são:

(1, g13) (g3, g13) (g5, g11) (g6, g14) (g9, g13) (g10, g8) (g12, g12) (1, g6) (g3, g8) (g5, g3) (g6, g8) (g9, g10) (g10, g) (g12, 0) (0, 1)


A propriedade de Adição: Curvas Elípticas sobre Corpos Finitos de Característica 2

O negativo de um ponto P = (xP, yP) é o ponto - P = (xP, xP + yP). Assim como nos outros grupos de curvas elípticas, tem-se que P + (-P) = O e P + O = P.

Sejam dois pontos P = (xP, yP) e Q = (xQ, yQ), pertencentes à curva e distintos, tal que P ≠ -Q. As coordenadas (xR, yR) do ponto R = P + Q é definida a seguir:

xR = s2 + s + xP + xQ + a e yR = s(xP + xR) + xR + yP, onde s = (yP - yQ) / (xP + xQ)

A seguir, considere o ponto P, tal que xP ≠ 0. Segue a fórmula algébrica que define o ponto R, tal que R = 2P:

xR = s2+ s + a e yR = yP 2 + (s + 1) * xR, onde s = xP + yP / xP

No caso em que xP = 0, 2P = O

O Problema do Logaritmo Discreto em Curvas Elípticas(PLDCE)

Todo sistema criptográfico é baseado em um problema matemático que é intratável computacionalmente. Sistemas criptográficos em curvas elípticas são baseados na dificuldade do problema do logaritmo discreto em curvas elípticas (ECDLP - Elliptic Curve Discrete Logarithm Problem).

Nas seções anteriores foi definida a operação de adição sobre elementos de um grupo de curvas elípticas. Considerando o caso em que um ponto é somado a ele mesmo, isto é, a partir de um ponto P pertencente à curva elíptica, o ponto 2P é obtido dobrando o ponto P. Neste momento, o ponto P pode ser adicionado ao ponto 2P, resultando o ponto 3P. A determinação de um ponto nP é conhecida como Multiplicação por Escalar do ponto. O problema do logaritmo discreto é baseado na intratabilidade do produto da multiplicação por escalar.

Apesar da operação utilizada ser uma seqüência de somas, a operação de multiplicação por escalar também é representada por uma notação de multiplicação (nP = PxPxPx...xP n vezes), explicando a utilização da palavra logaritmo para definir o problema.

O problema do logaritmo discreto é definido da seguinte maneira: dados os elementos R e Q pertencentes ao grupo, e um primo P, achar um número k tal que R = Qk mod P. O número k é chamado de logaritmo discreto de R na base Q.


Criptografia Assimétrica ou de Chave Pública

Na criptografia assimétrica, cada parte da comunicação possui um par de chaves. Uma chave é utilizada para encriptar e a outra para decriptar uma mensagem. A chave utilizada para encriptar a mensagem é publica, isto é, ela é divulgada para o transmissor; enquanto a chave para decriptar a mensagem é privada, isto é, ela é um segredo pertencente ao receptor. Sendo assim, não existe o problema de manutenção e transmissão do segredo que existe na criptografia simétrica.

Ao implementar um sistema criptográfico baseado em curvas elípticas é necessário definir alguns parâmetros genéricos do sistema, e em um momento posterior, os parâmetros pessoais, isto é, as chaves, são definidas pelos usuários do sistema. Entre os parâmetros gerais se destacam os parâmetros que definem a curva elíptica e um ponto gerador G que pertence à curva, todos estes parâmetros são públicos para permitir a utilização deste sistema por duas pessoas. O ponto G é obtido a partir da escolha de um valor n primo grande tal que nG = O. Todos os pontos Pi que pertencem a curva têm uma ordem ni tal que niPi = O, dessa forma n é denominado ordem de G. Além disso, n deve ser grande o suficiente para inviabilizara obtenção de todos os múltiplos de G: G, 2G, 3G, ..., (n - 1)G. Uma tabela que mapeia a mensagem original em pontos na curva elíptica também precisa der definida, por exemplo cada caractere pode ser mapeado em um ponto na curva.

Uma vez estabelecidos todos parâmetros genéricos do sistema criptográfico, neste momento cada usuário determina seus parâmetros individuais, um par de chaves, onde uma é a chave pública e a outra a chave privada. Cada usuário define um valor ni < n (ordem do ponto gerador G) como sua chave privada. A chave pública correspondente é calculada a partir da chave privada; Pi = niG. Note que Pi pertence à curva. A mensagem M (mensagem de comprimento de 1 caractere) é mapeada no ponto PM.

A seguir será descrito os cálculos efetuados quando um transmissor envia uma mensagem M a um receptor, cuja chave privada é nR e a chave pública é PR = nRG.


Transmissor: Escolhe, aleatoriamente, um inteiro k

Transmissor: Calcula, a partir de k, G, PR e PM (obtido da tabela de mapeamento), um par de pontos PC1 e PC2:

PC1 = (kG)

PC2 = (PM + kPR)

Transmissor: Transmite para o receptor o par de pontos cifrados PC:

PC = [PC1, PC2]

Do outro lado, quando o receptor recebe a mensagem cifrada (par de pontos PC), recupera PM, a partir do segundo ponto (PC2), da seguinte forma:

Receptor: Embora o receptor não conheça k, ele sabe que kPR = knRG e obtém kPR de PC1 da seguinte maneira:

PC1nR = (kG)nR = kPR

Receptor: Para extrair PM de PC2, basta calcular PC2 - kPR, assim:

PC2 - PC1nR = (PM + kPR) - kPR = = (PM + [(kG)nR]) - [(kG)nR]) = PM

Receptor: Obtém M a partir da tabela de mapeamento.

Considerações Finais

Atualmente, existem basicamente três tipos de sistemas de criptografia que se baseiam em três problemas matemáticos diferentes: problema de fatoração de inteiros (IFP - Integer Factorization Problem), problema do logaritmo discreto (DLP - Discrete Logarithm Problem) e o problema aqui apresentado; problema do logaritmo discreto em curvas elípticas (ECDLP - Elliptic Curve Discrete Logarithm Problem). Analisando em termos de segurança cada um desses problemas, há algoritmos de complexidade sub- exponencial que conseguem resolver os dois primeiros problemas, enquanto que o último problema é puramente exponencial. Sendo assim, pode-se observar que o problema de logaritmos discretos em curvas elípticas é considerado mais difícil de resolver que os demais.

Em termos de eficiência, estudos mostram que as melhores implementações de cada um dos sistemas indicam que o sistema de criptografia em curvas elípticas executa, aproximadamente, 10 vezes mais rápido que os demais sistemas. Outro fator importante para medir avaliar a eficiência, enquanto que o RSA, algoritmo baseado no problema de fatoração de inteiros, necessita de uma chave privada de 2048 bits para “assegurar” a segurança, o sistema ECC (Elliptic Curve Cryptography) necessita de uma chave privada de 160 bits para “assegurar” o mesmo nível de segurança.

Pode-se concluir que a utilização da criptografia com chave pública baseada em curvas elípticas é uma excelente escolha em termos de segurança e eficiência [3][4].

Dadas suas características, essa técnica pode ser utilizada, principalmente, em sistemas "embutidos" ou sistemas com restrições físicas de espaço e/ou capacidade de processamento. Estudos recentes [6] apontam para o uso dessa técnica na implementação de cartões inteligentes ("smart cards"), entre outros tipos de aplicação.


Referências

[1] KOBLITZ, N. Elliptic Curve Cryptosystems. Mathematics of Computation (1987).
[2] MILLER, V. S. Use of Elliptic Curves in Cryptography em CRYPTO’85. (New York: Springer-Verlag,1986).

[3] www.certicom.com - Current Public-Key Cryptographic Systems - A Certicom Whitepaper - April, 1997
[4] www.certicom.com - Remarks on the Security of the Elliptic Curve Cryptosystem - A Certicom Whitepaper - September, 1997

[5] STALLINGS, Williams. Criptografia e Segurança de Redes: Princípios e práticas (2007).

[6] Elsayed Mohammed, A. E. Emarah and Kh. El-Shennawy. Elliptic Curve Cryptosystems on Smart Cards. 2001 IEEE 35th International Carnahan Conference on , Oct 2001 pp 213 -222