33
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

Embed Size (px)

Citation preview

Page 1: 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

Page 2: 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

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

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

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

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.

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

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

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

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

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

Curvas elípticas

Exemplo:

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

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

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

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.

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

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.

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

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:

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

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.

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

Exemplo

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

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.

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

Exemplo

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

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:

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

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

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

Campos finitos

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

Exemplo de curva sobre GF(23)

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

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.

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

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

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

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

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

O criptossistema elíptico

O problema do logaritmo discreto e os protocolos criptográficos

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

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)

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

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

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

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

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

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.

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

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.

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

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)

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

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

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

Criptografia com curvas elípticas na prática

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

ECC versus RSA

Tamanhos de chave

Maturidade do sistema Reconhecimento comercial

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

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)

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

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