Criptografia com curvas elítipticas

Introdução

O problema da escolha de um método para criptografia na comunicação entre duas entidades tem duas restrições fundamentais:

Possuir características técnicas que minimizem o consumo de espaço (informação armazenada ou transmitida) e o esforço de processamento na cifragem e decifragem;

Garantir que o esforço para a decifragem, sem que se possua a chave, exija um tempo absurdo, mesmo que se possua um poder computacional igualmente absurdo. Esta robustez do sistema criptográfico está baseada na complexidade computacional do cálculo da função inversa àquela utilizada na criptografia;

A criptografia mais conhecida e utilizada até final da década de 90 é a já conhecida criptografia simétrica, onde deve haver um algoritmo e uma chave de conhecimento de ambas as partes de um processo de comunicação. Apesar de ser um método bastante eficiente, em termos computacionais, um problema que sempre esteve sob estudo é como garantir a integridade e confidencialidade da chave, garantindo assim a segurança da comunicação.

Tradicionalmente o que fazemos é criar diversos artifícios para garantir que a chave seja transferida com segurança ao alvo da comunicação: utilizamos uma outra chave para cifrar a chave a ser transferida, utilizamos um processo de geração compartilhada (cada parte gera uma parte da chave e estas partes são transferidas fisicamente através de um processo seguro e auditável) e outros processos. Ainda assim, temos que garantir que cada parte guardará esta chave apropriadamente. Normalmente as chaves realmente importantes e de uso recorrente são armazenadas em equipamentos próprios para este fim (os HSMs).

Buscando contornar essa dificuldade surgiram as pesquisas das chamadas funções criptográficas de chave pública, cujo propósito é transferir informações cifradas por uma chave conhecida (chave de cifragem, pública) de tal forma que mesmo se a informação e estas chave forem interceptados a confidencialidade será garantida, pois falta uma chave de decifragem (desconhecida, de uso privado da entidade-destino). Por isso mesmo este tipo de criptografia é também chamada de "criptografia assimétrica".

Vamos abordar um pouco da história da criptografia assimétrica, dos algoritmos que surgiram e o por quê da importância da criptografia com curvas elípticas.

Criptografia assimétrica

Há bastante tempo o homem pesquisa alternativas para garantir a criptografia de informações sem que um segredo (a chave) precise ser trocado entre as partes.

O registro mais antigo deste tipo de estudo remonta ao ano de 1874 [1], quando Willian Stanley Jevons, pesquisador inglês dos temas de economia e lógica, descreveu as relação entre funções sem função inversa (funções de sentido único) e a criptografia e, mais especificamente, o problema da fatoração (representação de uma função através da família da função e seus parâmetros) que foi a base para os primeiros algoritmos da criptografia assimétrica.

Um sistema de criptografia assimétrico foi publicado em 1976 por Whitfield Diffie e Martin Hellman e por isso mesmo é chamado de algoritmo de Diffie-Hellman.

Da esquerda para a direita: Ralph Merkle, Martin Hellman e Whitfield Diffie [2]

O Algoritmo de Diffie-Hellman

Este algoritmo baseado na função G^X mod N, apresentado aqui de forma bastante simples, é particularmente interessante para entendermos a criptografia com chaves assimétricas. Para fins práticos N deveria ser um número primo muito grande (muito mesmo!) que determina o tamanho do campo finito gerado.

Consideremos que dois individuos, Alice e Bob, desejam se comunicar de forma segura, de tal forma que Alice irá transferir uma informação a Bob.

Para isto Alice e Bob concordam em valores para G e N (estes são os parâmetros do algoritmo, que podem ser de conhecimento público). Estes valores devem ser primos, com G < g =" 11" n =" 23.

Alice e Bob escolhem suas chaves privadas, digamos 2 e 9 respectivamente. Esta chave não é comunicada a ninguém.

Alice calcula 11² mod 23, cujo resultado é 6, e envia esta informação a Bob. Esta é a chave pública de Alice.

Bob calcula 11⁹ mod 23, cujo resultado é 19, e envia esta informação a Alice. Esta é a chave pública de Bob.

Alice pega o valor enviado por Bob, 19, e calcula 19² mod 23 (chave pública de Bob elevada à chave privada de Alice mod N), que resulta em 16. Bob faz o mesmo, pegando o valor enviado por Alice, 6, e calcula 6⁹ mod 23 (chave pública de Alice elevada à chave privada de Bob mod N), que resulta também em 19. O valor 19 é a chave comum para a comunicação entre Alice e Bob.

O que percebemos é que para Alice e Bob conversarem eles apenas precisaram entrar em acordo sobre um algoritmo e seus parâmetros e a informação trocada entre eles, para a determinação da chave comum, não contém nenhum teor de confidencialidade. O único requisito é que as chaves privadas continuem secretas.

Temos portanto uma exponencial e encontrar as chaves requer o cálculo de um logaritmo sobre um campo numérico discreto baseado em números primos muito grandes, o que é computacionalmente imprático (o que, hoje, significa "impossível"). Fica clara a relação recorrente que envolve a dificuldade do cálculo da inversa e o tamanho da chave para garantir a segurança da estratégia de criptografia.

Logicamente a descrição aqui simplifica bastante o modelo - que exige números primos bastante grantes e uma boa qualidade no algoritmo de geração de números aleatórios - mas é o suficiente para que possamos entender a simplicidade brilhante do método.

O algoritmo RSA

Ainda em 1977 Ron Rivest, Adi Shamir e Len Adleman criaram o algoritmo RSA (formado pelas iniciais de seus nomes).

Ron Rivest, Adi Shamir e Len Adleman [3]

O algoritmo implementou o conceito de assinatura digital e foi elegantemente baseado no produto de dois números primos. A inversa dependeria de, dado o produto, achar estes primos, o que é imprático computacionalmente.

O RSA é utilizado no protocolo SSL na maioria dos browsers [4].

Os algoritmos baseados nas curvas elípticas

Como mencionei ao início do artigo, espaço (memória) e velocidade são dois fatores importantes na escolha de um algoritmo de criptografia. E é aí que surge o especial interesse nas curva elípticas: elas oferecem mais segurança para um mesmo tamanho de chave. Por outra óptica, elas oferecem mais segurança para uma chave menor, o que significa mais velocidade (menos ciclos, menos energia, menos calor produzido).

A matemática das curvas elípticas

Enquanto o algoritmo de Diffie-Hellman baseia-se no problema do logaritmo discreto sobre um campo finito formado por números primos, as curvas elípticas baseiam sua técnica num campo finito formado por pontos - pares (x,y) - de números primos que estão sobre a curva elíptica definida por uma determinada equação.

Em geral os pontos (x,y) são definidos pela equação a seguir

que está representada na figura abaixo (de [5])

onde temos as curvas para b = 0, 1/10, 2/10, 3/10, 4/10. Mas existem outras equações possíveis para as curvas elípticas. Para ter uma idéia de outras equações e no formato destas curvas, dê uma olhada aqui.

Agora imagine que tenhamos um quadrado de lado p definindo uma região onde está a curva, sendo p um número primo muito grande. O campo em que estamos interessados é formado por pontos (x,y), onde tanto x quanto y são números primos dentro do campo Fp, que são os inteiros módulo p na faixa [0, p-1], e definem pontos sobre a curva elíptica escolhida.

É possível determinar aproximadamente quantos pontos tem-se sobre a curva através da equação p + 1 - 2*sqrt(p) <= #E <= p + 1 + 2*sqrt(p). Por exemplo, para a equação y² = x³ +4x +20 com F29 temos 37 pontos (incluindo o ponto no infinito).

Ainda, a matemática das curvas elípticas define um conjunto de operações aritméticas que produzem resultados dentro do campo discreto de primos sobre a curva. A imagem abaixo ilustra a soma dos pontos P e Q, resultando em R [5].

A mais importante operação refere-se à multiplicação por escalar, onde temos o ponto P sobre a curva e k é um inteiro. Então Q = kP = P + P + P + ... + P (a soma é feita k vezes).

Chave pública e chave privada

Na criptografia com curvas elípticas, a equação base é a multiplicação por escalar Q = kP, onde P é um ponto de referência na curva (parâmetro da curva), Q é a chave pública e k é a chave privada. O problema do logaritmo discreto nas curvas elípiticas é justamente termos P e Q e tentarmos encontrar o k correspondente.

De fato, os parâmetros da curva são definidos pela tupla T = (p, a, b, P, n, h), onde:

- p define o tamanho do campo;

- a e b são os parâmetros da equação, que vimos há pouco;

- P é o ponto-base da curva;

- n é um primo grande, da ordem de P;

- h é um inteiro tal que h = #E(Fp)/n (também falamos de #E logo acima);

Digamos então que Alice (A) e Bob (B) desejam se comunicar utilizando uma criptografia suportada pelas curvas elípticas. De forma bem simplista, eles terão que acordar sobre uma curva e seus parâmetros de domínio definidos pela tupla T.

Alice determina Qa = Ka*P, sendo Qa sua chave pública e Ka sua chave privada.

Bob determina Qb = Kb*P, sendo Qb sua chave pública e Kb sua chave privada.

Assim, Alice pode calcular Kab = Ka*Qb = Ka*(Kb*P). Da mesma forma, Bob pode calcular Kab = Kb*Qa = Kb*(Ka*P). Sendo Ka e Kb escalares, temos que Alice e Bob conseguem definir uma chave exclusiva para se comunicarem sem que para isso precisem divulgar sua chave privada.

Obviamente esta é uma demonstração muito simples e a própria definição dos parâmetros requer um conjunto de validações. Não basta escolher quaisquer parâmetros de curva.

Uma descrição detalhada de todos os passos para a escolha dos parâmetros e suas validações pode ser encontrada em [6].

Quebrando a criptografia

Para o caso de P192, teríamos 3x10⁵⁷ adições a serem feitas para achar o k pelo método da força-bruta. A tabela abaixo ([6]) nos mostra que a criptografia com curvas elípticas entrega muito mais segurança com uma chave muito menor que aquela utilizada no RSA (as colunas ECC e DSA/RSA indicam o tamanho da chave).

Entretanto em 2009 um conjunto de pesquisadores suíços utilizou um cluster de 200 Playstation 3 para quebrar com sucesso a criptografia com chave de 112 bits (Fp-112) e, por isso, recomenda-se atualmente o uso de chaves de 256 bits. Veja aqui e aqui mais detalhes sobre esta façanha.

Conclusão

Apesar da matemática significativamente mais complexa, a criptografia com curvas elípticas provê um processo cuja criptografia é simples e de implementação relativamente fácil em hardware, provendo criptografia eficiente com chave muito menor.

No entanto ficamos com o sentimento que à medida que o poder computacional for crescendo, e vem crescendo de forma consistente com a Lei de Moore, novos algoritmos precisarão ser criados para que não tenhamos que usar chaves absurdamente grandes. Já estão aí os computadores quânticos, com um poder de processamento nunca visto anteriormente. Talvez as próximas pesquisas de criptografia tenham todas que se basear na criptografia quântica para garantir a segurança frente ao crescente poder computacional.

Referências

[1] Public-key criptography, em http://en.wikipedia.org/wiki/Public-key_cryptography, acessado em 20/04/2010.

[2] Public Key Criptography, em http://www.livinginternet.com/i/is_crypt_pkc.htm, acessado em 20/04/2010.

[3] Public Key Criptography (PKC) History, em http://www.livinginternet.com/i/is_crypt_pkc_inv.htm, acessado em 20/04/2010.

[4] Anderson, R. "Security Engineering: A Guide to Building Dependable Distributed Systems", Wiley, 1a ed, 20o1.

[5] http://www-math.uni-paderborn.de/mca/elliptic.html, acessado em 07/05/2010.

[6] SECG, "SEC 1: Elliptic Curve Cryptography", Standards for Efficient Cryptography Group - www.secg.org, 2009.

[7] An Intro do Elliptical Curve Cryptography, em http://www.deviceforge.com/articles/AT4234154468.html, acessado em 22/04/2010.