Criptografia de curvas elípticas

Neste artigo vamos descrever como funciona a criptografia de curvas elípticas. Para isso é preciso saber como funciona aritmética modular. O artigo Introdução ao RSA, do @c4v0k, tem tudo que precisamos saber, então dá um pulo lá se não entender muito sobre a operação mod. Ao invés de estudar como implementar um esquema de curvas elípticas de forma segura e sua matemática por trás, vamos entender neste artigo a essência do assunto. 🙂

Curvas Elípticas

Uma curva elíptica é definida por uma equação cúbica. Exemplos de curvas incluem Weierstrass, Montgomery e Edwards. Essas três têm uma relação chamada equivalência birracional, então existe uma forma de transformar uma curva e todas as suas propriedades de um tipo para outro. Vamos usar a curva de Weierstrass na forma curta como exemplo pois é a mais simples de entender. A equação da curva é definida como:

y² = x³ + ax + b

Ao plotar a curva no plano cartesiano com a = -2 e b = 4, temos esse gráfico:

Curva definida pela equação y² = x³ - 2x + 4

Um grupo, em matemática, é uma estrutura algébrica que tem uma operação binária (no sentido de dois operadores). Nossa curva vai ser um grupo, então precisamos definir uma operação nela: a operação de soma. Peguemos dois pontos A e B da curva, totalmente aleatórios. Se traçarmos uma reta entre esses dois pontos, teremos um terceiro ponto que a reta vai cruzar. Esse terceiro ponto vai ser o espelho (no eixo x) do ponto que representa A + B. Veja a imagem para entender melhor:

Soma dos pontos A e B

Se repetirmos essa operação de soma com pontos da curva várias vezes, sempre teremos um ponto diferente como resultado. Mas, e se acontecer de aleatoriamente termos os pontos A e B iguais, como fica a soma de A + A? Para resolver essa soma, traçamos a reta tangente ao ponto A e o segundo ponto que a reta tocar na curva será o espelho de A + A:

Duplicação de um ponto A

Achou complicado esse negócio de tangente? Na verdade, é só imaginar que o ponto B está muito pertinho do ponto A, então a operação de soma acaba sendo a mesma essencialmente, só o cálculo dela que muda. Para terminar a definição do grupo na nossa curva, precisamos também de um inverso da soma. Vamos chamar de "menos" com o sinal "-", então o ponto -A será o inverso do ponto A. O inverso é mais tranquilo: só espelhar o ponto na coordenada x, logo se o ponto A é (x, y) o ponto -A é (x, -y).

Para facilitar a notação, quando somarmos dois pontos iguais, vamos chamar de 2A. Assim, se somarmos mais um A, teremos 3A e assim sucessivamente. Imagine agora que somemos A "n" vezes. Cada vez que a gente soma A, o resultado é um ponto diferente na nossa curva, logo seria complicado sabermos quantas vezes somamos A. Nosso "n" pode ser então um segredo, já que é difícil descobri-lo. Olhe a imagem abaixo e tente descobrir o "n":

Tente descobrir o valor de "n" na imagem

Só de olhar a imagem é difícil saber né? Eu sei que "n" é 17 porque fui eu que escolhi esse número. Mas quem vê de fora não descobre sem eu contar. Logo, "n" vai será a chave privada da nossa criptografia e "nA" será a chave pública. Mas tem um problema aí: se usarmos ponto flutuante, vai acabar acumulando erros na hora de somar todas essas vezes. Por isso, vamos tirar o mod de um primo p grandão, aí nossa equação da curva vai ficar assim:

y² = x³ + ax + b mod p

Com esse mod p grandão, teremos muitos pontos possíveis para somar! Eu garanto que a operação de soma e inverso funcionam muito bem nessa equação também. Além disso, será melhor para armazenar nossas chaves, pois todos os números são inteiros e conseguimos representá-los sem precisar de bits extras de precisão.

Um outro problema...

Imagina que eu escolha o número 17 para minha chave privada. Seria muito fácil qualquer um encontrá-la... Só tentar 1, 2, 3… até 17. Então, como p é um número grande, também podemos escolher nossa chave privada como um número grande, deixando-a mais difícil de ser descoberta! Vamos supor que o número tenha 256 bits, isso dá 78 dígitos. Para calcular nossa chave privada vamos precisar somar A o mesmo número de vezes que alguém que quer descobrir nossa chave precisa. Então, precisamos pensar numa forma de somar A "n" vezes rápido.

Lembra quando eu falei de grupo na matemática? Então, além da definição de soma, também temos as seguintes leis neste grupo:

• Quando somamos qualquer dois pontos A + B = C, então C sempre vai estar no grupo também.
• O grupo tem associatividade, ou seja, a soma (A + B) + C para quaisquer pontos vai ser igual a A + (B + C).
• Existe um elemento neutro O, de forma que A - A = O.

Provar que isso é verdade para curvas elípticas é um pouco complicado, no entanto. Se quiser saber mais sobre, veja no livro "Introdução à Criptografia com Curvas Elípticas", na seção 4.1.2, escrito por Sally Andria, Rodrigo Gondim e Rodrigo Salomão e publicado pelo IMPA.

Tá bom, mas o que isso tem a ver com somar A "n" vezes rápido? Bom, por causa dessa associatividade, A + 3A é igual a 2A + 2A. Então dá para representar nosso "n" em binário e aí duplicamos o ponto A várias vezes. Isso vai trocar a complexidade do problema para quantos bits o "n" tem e não para quanto ele vale em decimal. Vamos ver um exemplo com "n" sendo 315. A representação desse número em binário é 100111011, nessa tabela abaixo podemos ver as potências de 2 referente a cada posição:

Então podemos somar A 315 vezes como se fosse dessa forma:

2⁸A + 2⁵A + 2⁴A + 2³A + 2¹A + 2⁰A

Com isso, vamos usar bem menos operações que 315.

Já sobre o elemento neutro O, imagine o que acontece quando somamos um ponto com o inverso dele, ou seja A + (-A). Ao traçar a reta entre esses dois pontos, teremos uma reta vertical, ou seja, paralela ao eixo y e que não corta a curva em nenhum outro ponto. Existe uma outra lei da geometria projetiva, aliás essa é a geometria que a gente tá vendo aqui, que diz que duas retas paralelas se encontram no infinito. Dito isso, vamos chamar esse ponto O de ponto no infinito e ele sempre será o elemento neutro, como o 0 (zero) na soma ou o 1 (um) na multiplicação.

A representado na nossa curva definida anteriormente

Troca de chaves

Um dos principais usos da criptografia de curvas elípticas é na troca de chaves. No protocolo TLS, a primeira coisa que acontece, criptograficamente falando (na maioria das vezes) é uma troca de chaves antes de o protocolo prosseguir com um esquema de criptografia simétrica para troca de dados segura entre o servidor e o cliente. Veremos agora como funciona um esquema de troca de chaves aplicável a qualquer grupo matemático. O esquema se chama Diffie-Hellman.

Vamos pensar em duas pessoas que querem ter uma chave secreta em comum. Chamaremo-os de Aline e Bernardo. Aline vai criar uma chave privada "n" e Bernardo vai criar uma chave privada "m", então os dois vão estabelecer um ponto de partida, que é o ponto A que vimos anteriormente. Já que os dois têm um mesmo ponto de partida, eles podem enviar a chave pública um para o outro, então Aline vai enviar "nA" para Bernardo e Bernardo envia "mA" para Aline. Já que os dois possuem as chaves públicas, então eles podem chegar em um acordo de chave multiplicando a chave privada na chave recebida.

Aline recebe "mA" e soma esse ponto "n" vezes, então ela vai ter "nmA". Já Bernardo recebe "nA" e soma esse ponto "m" vezes, então ele vai ter "nmA". A chave compartilhada vai ser "nmA" e eles podem seguir um canal secreto de comunicação. Veja a imagem para tentar entender melhor, nela eu usei "n" igual a 5 e "m" igual a 3.

Esquema Diffie-Hellman de troca de chaves, usando ECC

Criptografia

O mais comum de se ver no dia a dia, entre duas entidades, é primeiro um esquema de troca de chaves e depois a troca de dados por meio de um esquema simétrico de criptografia, como por exemplo o AES. Mesmo assim, veremos na prática um esquema um pouco diferente que não depende da troca de chaves. Esse esquema chama-se El Gamal. Aline e Bernardo serão os protagonistas de novo. 🙂

Aline será a pessoa que receberá a mensagem de Bernardo. Então ela precisa enviar a chave pública para Bernardo encriptar a mensagem que ele quer enviar, logo, Aline cria uma chave privada "n" e uma chave pública "P = nA". Ela envia a chave pública e o ponto de partida A para Bernardo. Bernardo tem uma mensagem "M" que quer enviar para Aline, então precisará gerar um número aleatório "k" e criar a sua própria chave "K = kA". Não só isso, Bernardo também vai enviar "C = kP + M" para Aline. Quando Alice receber esses dois pontos (C, K), basta que ela compute "C - nK" para recuperar a mensagem. Veja a imagem com a prova para tentar entender melhor:

Esquema Elgamal de criptografia usando ECC

Se gostou desse assunto você pode ver meu writeup de um desafio de CTF que envolve curvas elípticas. O CryptoHack também é um ótimo site para aprender sobre criptografia de curva elíptica (ECC, no acrônimo em inglês). Bons estudos!