Uma introdução à criptografia com curvas elípticas Afonso Comba de Araujo Neto

Uma introdução à criptografia com curvas elípticas

Afonso Comba de Araujo Neto

Sumário da apresentação

IntroduçãoDefinição de curvas elípticasÁlgebra e geometria de curvas elípticasProduto escalar Problema do logaritmo discreto elípticoProtocolos criptográficosUso da criptografia com curvas elípticas

na prática

Introdução

A criptografia com curvas elípticas, ou Elliptic Curve Cryptography (ECC), é um sistema de criptografia assimétrica

Esse sistema é interessante pois é mais eficiente que o RSA, o sistema assimétrico mais utilizado nos dias de hoje

O principal objetivo deste trabalho é mostrar como funciona a criptografia com curvas elípticas

Curvas elípticas

Curvas elípticas são equações que definem um conjunto de pontos em um plano bidimensional

Elas têm a seguinte forma geral

Com coeficientes pertencentes ao conjunto sobre o qual a curva está definida.

Corpos

Todas as curvas elípticas são definidas sobre algum corpo

Um corpo é um conjunto, mais duas operações com características especiais

O corpo dos reais é composto pelo conjunto dos reais mais as operações de adição e multiplicação

Essas operações definem como os símbolos + e x são interpretados nas equações

Os corpos utilizados na prática são os chamados “corpos finitos”, mas exemplificaremos com o corpo dos reais

Curvas elípticas

Utilizando o conjunto dos reais, a equação pode ser simplificada da seguinte forma

Com

É necessário que a curva possua tangente à todos os seus pontos

Curvas elípticas

Exemplo:

Lei de grupo

Devido às características destas curvas, podemos tomar o conjunto de pontos de uma curva elíptica e definir uma operação fechada sobre ele. É o que chamamos lei de grupo

A lei de grupo deve possuir as seguintes propriedades

1. Comutatividade

2. Existência da identidade

3. Existência do inverso

4. Associatividade

Definição da operação

Ao conjunto de pontos da curva, é adicionado um ponto extra chamado ponto no infinito, normalmente denotado por

Para satisfazer as propriedades antes mencionadas, algumas definições se fazem necessárias

definimos o ponto no infinito como sendo a identidade;

dado um ponto P = (x, y), definimos o inverso de P como P = (x, -y). Devido à natureza simétrica das curvas elípticas, o inverso sempre existe, e o inverso da identidade é a própria identidade.

Soma de pontos

Para definirmos a operação, que chamaremos de soma de pontos, entre os elementos do conjunto, existem quatro casos a serem considerados. Consideremos dois pontos quaisquer do conjunto, P e Q.

Caso 1: é trivialmente dedutível da definição de identidade. Se um dos pontos é a identidade, então o resultado é igual ao outro ponto.

Soma de pontos

Caso 2: Dedutível da definição de inverso. Se um dos pontos é o inverso do outro, a operação entre eles resulta na identidade. Exemplo:

Soma de pontos

Caso 3: É o caso mais comum. Se P é diferente de Q, então traçamos uma reta que passe por P e Q. Essa reta interceptará a curva em um terceiro ponto R. O resultado da operação é o inverso do ponto R, ou seja, R.

Podemos ver que o caso 2 é um caso particular do caso 3 onde a reta intercepta, por definição, o ponto no infinito.

Exemplo

Soma de pontos

Caso 4: Caso P e Q sejam iguais, e diferentes da identidade, traça-se uma reta tangente à curva no ponto P. Da mesma forma que no caso anterior, a reta intercepta um terceiro ponto R. O resultado é o inverso desse ponto.

É importante notar que esse caso é o mesmo que calcularmos P + P = 2P.

Exemplo

Equações algébricas

Naturalmente, a implementação prática desse sistema se dá através de um sistema de equações algébricas.

R = P + Q é calculado da seguinte forma:

Campos finitos

Entendido o funcionamento da operação de soma de pontos de uma curva elíptica, podemos começar a adaptar o sistema para seu uso em criptografia

Na prática, os criptossistemas elípticos são definidos sobre corpos finitos, ou seja, corpos cujo conjunto base tem um número finito de elementos

Dois conjuntos são normalmente utilizados GF(p) - número primo de elementos GF(2m) – número de elementos igual a uma potência de 2

Nesses corpos, as operações são tomadas em módulo

Campos finitos

Desta forma, deixamos de ter curvas e passamos a ter um conjunto discreto de pontos.

Exemplo de curva sobre GF(23)

Produto escalar

Ao somar um ponto P com ele mesmo, estamos multiplicando o ponto por 2

Se somarmos novamente o ponto ao resultado, obteremos 3P

Podemos definir o produto escalar no sistema elíptico, que seria o produto de um ponto por um valor escalar k.

Otimização do produto escalar

A associatividade da soma de pontos permite que façamos otimizações no produto escalar. Por exemplo, podemos calcular 50P da seguinte forma

O objetivo disto é minimizar o número de somas elípticas. No exemplo, são necessárias apenas 12 somas ao invés de 50.

A fim de generalizar o procedimento, Neal Koblitz, um dos inventores da criptografia com curvas elípticas, desenvolveu um algoritmo conhecido como expansão binária balanceada, que faz com que o número de somas elípticas seja proporcional ao número de bits do valor escalar multiplicado.

Essa otimização é fundamental para a criptografia

Ponto gerador

O produto escalar permite que pensemos em uma seqüência de pontos

Dado um ponto P, podemos nos referir aos outros pontos da curva como 2P, 3P, 4P, etc.

Isso significa que podemos pegar um ponto qualquer e utilizá-lo como referência para identificação de todos os outros pontos. Esse ponto é o que chamamos de ponto gerador, ou G

Isso agiliza a aritmética, na medida em que podemos somar os coeficientes dos pontos ao invés dos pontos diretamente. Ex.: 7G + 10G = 17G

O criptossistema elíptico

O problema do logaritmo discreto e os protocolos criptográficos

Problema do logaritmo discreto elíptico

Todas as técnicas de criptografia com chave pública são baseadas em problemas matemáticos intratáveis. RSA: fatoração em componentes primos

Dado um número inteiro, descobrir dois números primos que multiplicados resultem neste número

El Gamal e Diffie-Hellman: logaritmo discreto Dado o resultado de uma potenciação em módulo e a

base da potência, descobrir o expoente Da mesma forma, a criptografia com curvas elípticas é

baseada no chamado problema do logaritmo discreto elíptico, ou Elliptic Curve Discrete Logarithm Problem (ECDLP)

ECDLP

O problema do logaritmo discreto elíptico pode ser enunciado da seguinte forma:

Dados os pontos P e G na equação P = k x G,

descobrir o valor escalar k.

Os métodos existentes para resolução deste problema não são muito melhores que a simples força bruta

Esse é, atualmente, o problema matemático mais difícil empregado na prática para fins criptográficos

Protocolos criptográficos

Os protocolos criptográficos são os procedimentos através dos quais podemos nos utilizar o ECDLP como base para criptografia assimétrica

Como o próprio nome sugere, os protocolos que se utilizam do logaritmo discreto convencional (como El Gamal e Diffie-Hellman) são facilmente transpostos para o modelo elíptico

Protocolos criptográficos

Todos os protocolos se utilizam de parâmetros públicos e parâmetros privados

Em todos os casos, é necessário que as partes concordem nos parâmetros públicos, sendo eles:

1. O corpo utilizado, GF(p) ou GF(2m)2. A curva utilizada3. Um ponto gerador sobre esta curva, que chamaremos

de G.

Elliptic Curve Diffie-Hellman

Protocolo para troca de um segredo através de um canal público.

Funcionamento: Alice deseja trocar um segredo Qs com Bob. Alice escolhe um valor escalar ka qualquer e calcula o ponto

Qa = ka x G, e envia Qa para Bob Bob calcula Qb = kb x G, da mesma forma, e envia Qb para

Alice Cada um deles pega o ponto recebido e multiplica pelo seu

próprio valor escalar, obtendo:

Qs = ka x Qb = kb x Qa = ka x kb x G

O ECDLP garante que ka não é dedutível de Qa e G, assim como kb não é dedutível de Qb e G.

Elliptic Curve AES

Protocolo de chave pública baseado no El Gamal A idéia é criar e cifrar um ponto da curva e utilizá-lo

como chave para o algoritmo simétrico AES Funcionamento:

Alice deseja mandar um documento secreto m para Bob Bob escolhe um valor escalar k e calcula Y = k x G. Y é a sua

chave pública, e k a sua chave privada. Alice, de posse de Y, escolhe um valor descartável qualquer

s e calcula os pontos N = s x G e C = s x Y. Alice então utiliza o ponto C de alguma forma como chave simétrica para o AES e calcula a mensagem cifrada M = E(C, m). Alice envia M e N para Bob.

Bob então calcula C = k x N. Em posse de C, ele utiliza o AES novamente para recuperar m, m = D(C, M)

Elliptic Curve DSA

Protocolo para assinatura digital de um hash de documento

Dado o hash m, a chave pública Y e a chave privada k, a assinatura é obtida da seguinte forma: Escolhe-se um valor descartável s e calcula-se N = s x G. Sendo r a abscissa do ponto N, calcula-se w = s(m + rk)-1. A

assinatura é o par <r, w>. Para verificarmos a assinatura, calculamos

V = wm x G + wr x Y. A abscissa de V deve ser igual a r, pois V e N devem ser o mesmo

ponto. A demonstração da igualdade V = N está no trabalho escrito

Criptografia com curvas elípticas na prática

ECC versus RSA

Tamanhos de chave

Maturidade do sistema Reconhecimento comercial

ECC versus RSA

Um estudo da Sun, através do SSL, mostrou que a criptografia elíptica realmente é tão mais eficiente que a criptografia com RSA quanto maior for a segurança necessária

Tempos (ms) de execução das operações criptográficas básicas, para RSA 1024 bits e ECC 163 bits (acima) e RSA 2048 bits e ECC 193 bits (abaixo)

Conclusões

A criptografia com curvas elípticas é uma técnica ainda muito nova

É importante existir uma tecnologia de criptografia assimétrica confiável alternativa ao RSA

O RSA está bem estabelecido e não deve ser substituído, a não ser nos casos em que a eficiência da criptografia elíptica se mostre muito importante, como nos sistemas wireless e smart cards

Desafio ECC