Curva Elíptica

Uma curva elíptica é usada como base de alguns sistemas criptográficos.

A estrutura da curva elíptica permite realizar uma função matemática ("multiplicar") para se mover pelos pontos da curva em uma direção, sem conseguir percorrer o caminho inverso. Isso é conhecido como "função de alçapão" (trapdoor function), e é a característica-chave que torna as curvas elípticas ideais para a criptografia de chave pública.

Em resumo, as curvas elípticas têm propriedades matemáticas úteis para a criptografia, e fazem parte do sistema de assinaturas digitais do Bitcoin (ECDSA).

Parâmetros (Secp256k1)

Satoshi escolheu a curva secp256k1 para usar com ECDSA, que tem os seguintes parâmetros:

# y² = x³ + ax + b
$a = 0
$b = 7

# corpo primo (prime field)
$p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 #=> 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1

# número de pontos na curva que podemos alcançar ("ordem")
$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

# ponto gerador (ponto inicial na curva usado para todos os cálculos)
$G = {
  x: 55066263022277343669578718895168534326250603453777594175500187360389116729240,
  y: 32670510020758816978083085130507043184471273380659243275938904335757337482424,
}

• a, b — Uma curva elíptica é um conjunto de pontos descritos pela equação y² = x³ + ax + b, então é daí que vêm as variáveis a e b. Curvas diferentes têm valores diferentes para estes coeficientes, e a=0 e b=7 são os específicos da secp256k1.
• p — Este é o módulo primo. É um número que mantém todos os números dentro de um intervalo específico ao realizar cálculos matemáticos (novamente, específico da secp256k1). O fato de ser um número primo é um ingrediente chave para a criptografia funcionar.
• n — Esta é a ordem. É a quantidade de pontos na curva que podemos alcançar. É menor que p, e é influenciada pelo ponto gerador escolhido (veja abaixo).
• G — Este é o ponto gerador. Este é o ponto de partida na curva usado ao realizar a maioria das operações matemáticas. A origem exata da escolha deste ponto é desconhecida, mas geralmente é porque ele fornece uma ordem alta (veja acima) e mostrou não ter fraquezas criptográficas inerentes.
  

Corpo Finito

Os diagramas que estou usando neste tutorial mostram uma curva elíptica suave como esta:

No entanto, a curva real usada no Bitcoin parece mais com um gráfico de dispersão de pontos como este:

Isto se deve ao fato de que a curva usada no Bitcoin está sobre um corpo finito de números inteiros (ou seja, usando mod p para restringir números a um determinado intervalo), e isso quebra a curva contínua que você obtém ao usar números reais.

No entanto, mesmo que estes gráficos pareçam radicalmente diferentes, as operações matemáticas que você pode realizar em ambas as curvas ainda funcionam da mesma forma.

É claro que a curva secp256k1 tem um valor muito grande para p, então ela se assemelha mais ao gráfico abaixo, exceto que imagine que há tantos pontos quanto átomos no universo:

sudo apt install sagemath

sage: C = EllipticCurve([0,7]) # y^2 = x^3 + 7, onde a=0, b=7
sage: plot(C)
sage: C.lift_x(1.123) # obter coordenada y de exemplo
sage: C.lift_x(-1.834) # obter coordenada y de exemplo

sage: F = FiniteField(47)
sage: C = EllipticCurve(F, [0, 7]) # y^2 = x^3 + 7, onde a=0, b=7
sage: plot(C)
sage: C.lift_x(17) # obter coordenada y de exemplo

sage: F = FiniteField(115792089237316195423570985008687907853269984665640564039457584007908834671663)
sage: C = EllipticCurve(F, [0, 7])

Por que usar um corpo finito?

Porque ao implementar criptografia em computadores, é mais fácil trabalhar com números inteiros em um campo finito (ex.: 1, 2, 3, 4, ..., p) do que trabalhar com uma quantidade infinita de números reais (ex.: 0.911722707844879, 2.90107701845366, ...).

Você corre o risco de perder precisão ao trabalhar com números decimais em um computador, então a precisão que você obtém com um conjunto finito de números inteiros é mais adequada para criptografia.

Para fins ilustrativos, usarei a curva suave para o restante deste tutorial.

Matemática de Curva Elíptica

Existem algumas operações matemáticas que você pode realizar em pontos na curva elíptica. As duas operações principais são double() e add(), e estas podem ser combinadas para realizar multiply().

Estas operações são os blocos de construção da criptografia de curva elíptica, e são usadas para gerar chaves públicas e assinaturas no ECDSA.

• Inverso Modular
• Duplicação
• Adição
• Multiplicação

Inverso Modular

Inverso Modular

Inverso Modular

Encontre o inverso de um número com um módulo específico.

Exemplo Simples Número

0d

Inverso

0d

Módulo

0d

n p

n = número de pontos na curva secp256k1 (usado com escalares, ex.: chaves privadas)

p = tamanho do corpo da curva secp256k1 (usado com pontos, ex.: coordenadas)

Antes de podermos realizar as operações de double() e add() em pontos na curva, primeiro precisamos ser capazes de encontrar o inverso modular de um número em um corpo finito.

Isto porque as equações de double() e add() incluem a operação de divisão /.

No entanto, não existe uma operação direta de divisão dentro de um corpo finito de números. Em vez disso, você pode multiplicar pelo inverso de um número para alcançar o mesmo resultado que a divisão:

Em outras palavras, se você começa em um número específico em um corpo finito e multiplica por outro número, você pode "voltar" ao número inicial multiplicando novamente pelo inverso do número que você usou para a multiplicação.

Obviamente este é um primeiro passo confuso na matemática de curvas elípticas, mas apenas pense em "multiplicar pelo inverso" como uma substituição para divisão na aritmética modular.

Isto sempre funciona se você tiver um número primo de elementos no corpo finito. Um número primo não pode ser dividido por nenhum outro número, então ele distribuirá os resultados da multiplicação modular uniformemente por cada um dos números no corpo (sem repetir ou perder alguns números). Então, ao usar um número primo como módulo, você pode garantir que cada número no corpo finito terá um inverso multiplicativo (ou uma operação de "divisão").

Então o primeiro passo na matemática de curvas elípticas é ser capaz de encontrar o inverso de um número em um corpo finito:

def inverse(a, m = $p)

  # armazenar módulo original
  m_orig = m

  # garantir que a seja positivo
  if a < 0
    a = a % m
  end

  # definir valores iniciais antes do loop
  y_prev = 0
  y = 1

  while a > 1
    q = m / a

    y_before = y # armazenar valor atual de y
    y = y_prev - q * y # calcular novo valor de y
    y_prev = y_before # definir y anterior para o valor antigo de y

    a_before = a # armazenar valor atual de a
    a = m % a # calcular novo valor de a
    m = a_before # definir m para o valor antigo de a
  end

  return y % m_orig
end

Notação de inverso modular

O inverso modular de um número é tipicamente denotado por ⁻¹ em equações matemáticas.

Nas próximas operações, o inverso de um número às vezes é encontrado mod p (módulo o número primo), e às vezes mod n (módulo o número de pontos na curva).

Duplicação

Duplicação de Ponto

Duplicação de Ponto (EC Double)

Duplique um ponto na curva elíptica secp256k1.

Ponto Gerador Ponto Aleatório

Ponto 1

x:

0d

y:

0d

Ponto 1 + Ponto 1

x:

0d

y:

0d

"Duplicar" um ponto é o mesmo que "somar" um ponto a ele mesmo.

De uma perspectiva visual, para "duplicar" um ponto você traça uma tangente à curva no ponto dado, então encontra o ponto na curva que esta linha intersecta (haverá apenas um), e então reflete este ponto através do eixo x.

def double(point)
  # slope = (3x₁² + a) / 2y₁
  slope = ((3 * point[:x] ** 2 + $a) * inverse((2 * point[:y]), $p)) % $p # usando inverse para ajudar com a divisão

  # x = slope² - 2x₁
  x = (slope ** 2 - (2 * point[:x])) % $p

  # y = slope * (x₁ - x) - y₁
  y = (slope * (point[:x] - x) - point[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

Adição

Soma de Pontos

Soma de Pontos (EC Add)

Some dois pontos na curva elíptica secp256k1.

Pontos Aleatórios

Ponto 1

x:

0d

y:

0d

Ponto 2

x:

0d

y:

0d

Ponto 1 + Ponto 2

x:

0d

y:

0d

Como esperado, a "adição" de dois pontos na matemática de curvas elípticas não é o mesmo que a adição simples de inteiros, mas é chamada de "adição" mesmo assim.

De uma perspectiva visual, para "somar" dois pontos você traça uma linha entre eles, então encontra o ponto na curva que esta linha intersecta (haverá apenas um), e então reflete este ponto através do eixo x.

def add(point1, point2)
  # duplicar se ambos os pontos forem iguais
  if point1 == point2
    return double(point1)
  end

  # slope = (y₁ - y₂) / (x₁ - x₂)
  slope = ((point1[:y] - point2[:y]) * inverse(point1[:x] - point2[:x], $p)) % $p

  # x = slope² - x₁ - x₂
  x = (slope ** 2 - point1[:x] - point2[:x]) % $p

  # y = slope * (x₁ - x) - y₁
  y = ((slope * (point1[:x] - x)) - point1[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

Multiplicação

Esta operação é o coração da criptografia de curva elíptica.

Multiplicação na Curva

Multiplicação de Ponto (EC Multiply)

Multiplique um ponto na curva elíptica secp256k1.

Ponto Gerador Ponto Aleatório

Ponto 1

x:

0d

y:

0d

Multiplicador

0d

+1 Aleatório

Ponto 1 × Multiplicador

x:

0d

y:

0d

Steps [mostrar]

A maioria das operações de multiplicação no ECDSA começa no ponto gerador G.

Agora que podemos double() e add() pontos na curva, podemos pegar qualquer ponto na curva e multiply() por um inteiro para chegar a um ponto completamente novo.

O método mais simples para multiplicação em curvas elípticas seria add() repetidamente um ponto a si mesmo até alcançar o número pelo qual você quer multiplicar, o que funcionaria, mas estas operações incrementais de add() tornariam esta abordagem impossivelmente lenta ao multiplicar por números grandes (como os usados no Bitcoin).

Felizmente, existe uma maneira mais rápida de realizar multiplicação em curvas elípticas...

Algoritmo double-and-add

Uma abordagem mais rápida para multiplicação é usar o algoritmo double-and-add.

Este algoritmo usa tanto duplicação quanto adição para alcançar o múltiplo desejado em tão poucas operações quanto possível.

Por exemplo, se você começa em 2 e quer chegar a 128, é mais rápido realizar seis operações de double() do que realizar sessenta e quatro operações de add().

Mas como você sabe quantas operações de double e add são necessárias para alcançar seu múltiplo alvo?

Bem, incrivelmente, se você converter qualquer inteiro para sua representação binária, os 1s e 0s fornecerão um mapa para a sequência de operações double() e add() que você precisa realizar para alcançar aquele múltiplo.

Por exemplo:

ex.: 1 * 21

21 = 10101 (binário)
      │││└ double e add = 21
      ││└─ double        = 10
      │└── double e add = 5
      └─── double        = 2
                            1  <- comece aqui

De qualquer forma, aqui está a aparência da multiplicação em curva elíptica usando o algoritmo double-and-add em código Ruby:

def multiply(k, point = $G)
  # criar uma cópia do ponto inicial (para uso na adição depois)
  current = point

  # converter inteiro para representação binária
  binary = k.to_s(2)

  # algoritmo double-and-add para multiplicação rápida
  binary.split("").drop(1).each do |char| # da esquerda para a direita, ignorando o primeiro caractere binário
    # 0 = double
    current = double(current)

    # 1 = double e add
    current = add(current, point) if char == "1"
  end

  # retornar o ponto final
  current
end

Resumo

Este artigo cobre apenas as operações matemáticas básicas usadas em curvas elípticas.

• Encontrar o inverso modular é um requisito básico para poder realizar as operações double() e add().
• As operações double() e add() são apenas blocos de construção para a operação multiply().
• A operação multiply() é a operação central usada em sistemas criptográficos.

É importante lembrar que a "multiplicação" na curva elíptica não é nada como a multiplicação cotidiana. É melhor pensar na "multiplicação de curva elíptica" como um tipo completamente único de operação, mas nós a chamamos de "multiplicação" apenas para ter um nome próprio. É apenas uma pena que seja tão confuso.

De qualquer forma, esta operação multiply() permite que você se mova por pontos na curva em uma direção, mas não há operação matemática que permita "desfazer" este movimento, e esta propriedade é o que torna as curvas elípticas tão úteis para criptografia.

Toda esta matemática de curvas elípticas é usada como base para os sistemas de assinatura digital usados no Bitcoin: ECDSA e Schnorr (adicionado em 2021 como parte da atualização Taproot).

Recursos

Referências:

• sec2-v2.pdf — Lista de curvas recomendadas para uso em criptografia de curva elíptica do SECG. Contém parâmetros para a curva secp256k1 usada no Bitcoin.

Explicações:

• Elliptic Curve Cryptography: A Gentle Introduction — Uma excelente introdução em quatro partes à Criptografia de Curva Elíptica por Andrea Corbellini. Um bom lugar para começar.
• Introducing Elliptic Curves — Introdução a curvas elípticas por alguém que tem um entendimento profundo de por que elas são usadas em criptografia.
• An Introduction to Elliptic Curve Cryptography — Outra introdução à ECC. Mais curta que os dois guias acima, mas achei útil.

Ferramentas:

• Elliptic Curve Plotter — Um programa pequeno mas legal que permite brincar com operações simples de curva elíptica. Foi o que usei para ajudar a criar os diagramas nesta página.
• Sage Math — Uma grande biblioteca matemática que vem com funções de plotagem de curvas elípticas. Usei para mostrar os gráficos de curvas elípticas sobre números reais e sobre corpos finitos.
• Interactive Elliptic Curve Operations — Uma ferramenta web legal criada por Andrea Corbellini que permite visualizar operações de adição e duplicação em curvas elípticas tanto sobre números reais quanto sobre um corpo finito.