Chinchila

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: 28A + 25A + 24A + 23A + 21A + 20A 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!

O que é criptografia? É uma área de estudo que tem foco em transferir dados entre um grupo sem que alguém de fora desse grupo consiga recuperar os dados. Para isso é necessário alguma convenção do grupo, todos eles devem usar um mesmo mecanismo que geralmente envolve algum passo a passo, o que chamamos de algoritmo, e uma chave que apenas as pessoas do grupo podem ter acesso. Criptografia clássica Desde muito tempo temos essa necessidade de trocar informações de forma secreta, então antes mesmo de existir computadores já existia a criptografia. Antigamente eram bem comuns esquemas de cifra de substituição, ou seja, um grupo criava um mapa de representação de caracteres, por exemplo o “A” vira “C”, “B” vira “K”, e por aí vai. Um bom exemplo é a cifra de césar, também conhecida como ROT13, é uma cifra de substituição bem simples que cada caractere é mapeado para uma posição, por exemplo “A” vira “0”, “B” vira “1”, etc. Depois disso era escolhida uma chave, no caso o césar escolheu 13, e todas as posições eram somadas 13, então onde tinha “A” vira a letra na posição 13 que é a letra “N”, “B” vira a da posição 14 ou seja a letra “O”, etc. Figura 1 - Uma ilustração do mapa e a palavra CESAR ambas com a chave 13 Além da cifra de César, outra bem comum, porém menos antiga, é a cifra de Vigenère que na verdade é uma generalização da cifra de César. Basicamente invés de somar uma chave fixa vamos somar o deslocamento da chave mais do texto simples. Por exemplo, vamos ter uma chave “ACB” e um texto simples “DFG”, então o “D” vira a posição 4 do alfabeto que começa com a letra “A”, o “F” vira a posição 6 do alfabeto que começa com C e por aí vai. Criptografia moderna Com a popularização dos computadores a criptografia clássica foi ficando obsoleta porque a capacidade de cálculo do computador é muito alta. Logo, por exemplo, se uma pessoa interceptar uma cifra feita com o esquema de César fica muito fácil para ela recuperar a informação sem saber a chave, apenas testando todas as chaves possíveis. A partir dessa fraqueza dos esquemas clássicos surgiu a criptografia moderna que engloba esquemas de chave simétrica, assimétrica e funções hash. A criptografia de chave simétrica funciona com o princípio de que existe uma chave secreta e alguns exemplos de primitivas são AES e Salsa20. Em geral, essas primitivas se baseiam em uma matemática pesada, extensa e difícil que acaba se reduzindo a operações de bit a bit, como XOR e AND. Embora as primitivas já tragam bastante segurança, não é recomendado usar apenas a primitiva e sim uma implementação dela, como por exemplo AES-256 que usa a primitiva do AES porém com uma chave de 256 bits. Além disso, no caso de cifras em blocos, também é interessante utilizar algum modo de operação, que é essencialmente como cada bloco vai ser processado a cada passo da encriptação. Figura 2 - Criptografia com chave simétrica Além da criptografia de chave simétrica, também existe a de chave assimétrica que se baseia em uma chave pública, que pode ser conhecida por qualquer um, e uma privada, que é secreta. As primitivas desse tipo são baseadas em uma função armadilha, que é uma função na qual é muito fácil realizar uma operação de transformação mas é muito difícil realizar o inverso. Um bom exemplo para esse tipo é o RSA, as funções armadilhas do RSA são a de logaritmo discreto e a fatoração de um número. Figura 3 - Criptografia com chave assimétrica Além desses esquemas também vieram as funções hash, que são funções que transformam um dado em um conjunto de bits de forma que aquele dado seja único, para garantir unicidade na verdade se parte do princípio de que com uma probabilidade muito baixa dois dados vão ter o mesmo conjunto de bits, então sempre pode acontecer de ter a chamada colisão que é quando dois dados geram a mesma hash. Exemplos de funções hash são MD5 e SHA1, que estão depreciadas pois já foram encontradas formas de gerar colisão, e SHA2 que até agora está bem. Criptografia pós quântica Na década de 90, mais precisamente entre 1995 e 1996, surgiram dois algoritmos, um deles, o algoritmo de Shor, diz que é possível inverter uma função armadilha na qual grande parte dos esquemas assimétricos são estruturados e o outro, algoritmo de Grover, descreve uma forma de diminuir o tempo da busca pela chave secreta de esquemas simétricos. Porém ambos algoritmos precisam de um computador quântico que ainda não foi desenvolvido, com a chegada desses algoritmos a comunidade científica que pesquisa criptografia viu que era necessário criar esquemas baseados em problemas que nem computadores quânticos conseguissem quebrar, e aí surgiu a criptografia pós quântica. Só para sabermos a proporção, ter esses algoritmos significa que qualquer um com acesso a um computador quântico forte o suficiente vai conseguir ver qualquer dado que uma pessoa troca com a maioria dos sites, seja cartão de crédito, endereço, senhas, isso porque a maioria dos sites usa um esquema junto do protocolo TLS que é “quebrável” com o algoritmo de Shor. Embora os algoritmos existam há bastante tempo, somente em 2016 começaram a planejar uma padronização assim como fizeram com AES e RSA. O National Institute of Standards and Technology ou NIST organizou alguns rounds em que pesquisadores pudessem compartilhar esquemas que pudessem ser usados como primitivas para uma troca segura de informações. Os esquemas nesses rounds são divididos em algumas funções de armadilha que possuem muitos casos de borda e acabam sendo bem fáceis de resolver nesses casos, então para criar um esquema bom é preciso bastante conhecimento no problema matemático que ele é baseado, além de conhecimento de ataques. Como transferir/armazenar dados de forma segura? Transferir dados de forma segura parece uma tarefa difícil depois de ler um pouco sobre criptografia pós quântica, porém ainda não sabemos quando um computador quântico bom o suficiente vai ser criado. Para transferir dados encriptados em um protocolo de texto usamos algum tipo de encoding. Encoding é só uma tradução do dado de uma convenção para outra, os mais comuns que consigo lembrar são codificação base64 e hexadecimal. Lembrando que encoding não é considerado criptografia pois não envolve nenhuma chave e nem funções de uma via, como nos hashes. Seguem algumas boas práticas para troca e armazenamento de dados: Nunca implemente um esquema criptográfico. Sempre use bibliotecas de preferência com código aberto, a não ser que você saiba realmente o que está fazendo. Nunca armazene senhas em texto simples. É recomendado armazenar hashes de senhas. Sempre verifique a integridade do arquivo que foi transferido, seja pela hash ou verificando alguma assinatura. Sempre troque chaves secretas com algum mecanismo seguro de troca de chaves. Para se manter atualizado sobre o estado da arte da criptografia é interessante ver blogs de pesquisadores e publicações científicas. Muitos pesquisadores publicam no ePrint da iacr onde também tem várias palestras gratuitas. Outras apresentações muito boas são da conferência Chaos Computer Club, onde grandes pesquisadores montam palestras com conteúdo muito bom e didático. Se você curte uns desafios, também tem o site CryptoHack, que tem vários desafios bem interessantes de RSA, criptografia de curvas elípticas, AES, desafios matemáticos e até alguns de hashing.