Adição de curvas elípticas

_{Isenção de responsabilidade: isso não faz justiça ao rico tópico das curvas elípticas. É muito simplificado. Como as curvas elípticas recentemente receberam muita atenção da mídia no contexto da criptografia, eu queria fornecer uma pequena visão de como "calcular" uma curva elíptica realmente funciona.}

Introdução

As curvas elípticas são conjuntos de pontos (x,y)no plano do formulário y^2 = x^3+Ax+B. (Além disso, 4A^3+27B^2 ≠ 0para evitar singularidades desagradáveis.) Você pode considerar essas curvas em qualquer campo. Se você usar o campo de números reais, as curvas poderão ser visualizadas e ficarão assim:

_Fonte

O aspecto especial dessas curvas é que elas possuem uma operação aritmética integrada , que é o análogo da adição. Você pode adicionar e subtrair pontos, e esta operação é associativa e comutativa (um grupo abeliano).

Como funciona a adição?

Nota: a adição de pontos nas curvas elípticas não é intuitiva. Esse tipo de adição é definido da maneira que é porque possui certas propriedades agradáveis. É estranho, mas funciona.

Como as curvas elípticas formam um grupo, existe uma identidade aditiva equivalente a 0. Ou seja, adicionar 0a qualquer ponto não altera o resultado. Essa identidade aditiva é o "ponto" no infinito. Todas as linhas no plano incluem esse ponto no infinito, portanto, adicioná-lo não faz diferença.

Digamos que qualquer linha cruze a curva em três pontos, o que pode ser 0, e que a soma desses três pontos é 0. Mantendo isso em mente, dê uma olhada nesta imagem.

_Fonte

Agora, a questão natural é: o que é P+Q? Bem, se P+Q+R = 0, então P+Q = -R(alternativamente escrito como R'). Onde está -R? É onde R + (-R) = 0, que está no outro lado do eixo x de Rmodo que a linha através deles é vertical, que intersecta única R, -R, e 0. Você pode ver isso na primeira parte desta imagem:

_Fonte

Outra coisa que você pode ver nessas imagens é que a soma de um ponto significa que a linha é tangente à curva.

Como encontrar interseções de linhas e curvas elípticas

No caso de dois pontos distintos

Geralmente, há exatamente uma linha através de dois pontos P=(x0,y0), Q=(x1,y1). Assumindo que não é vertical e os dois pontos são distintos, podemos escrevê-lo como y = m*x+q. Quando queremos encontrar os pontos de interseção com a curva elíptica, podemos simplesmente escrever

0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2

que é um polinômio de terceiro grau. Geralmente não é tão fácil de resolver, mas já sabemos dois zeros desse polinômio: Os dois x-coordenadosx0, x1 dos dois pontos que queremos adicionar!

Dessa forma, fatoramos os fatores lineares (x-x0)e ficamos (x-x1)com um terceiro fator linear cuja raiz é a xcoordenada do ponto R. ( -R. Também por causa da simetria Observe que, se R = (x2,y2), em seguida, -R = (x2,-y2)O. -É do grupo, não é um sinal de menos vectorial.)

No caso de adicionar um ponto Pa si mesmo

Nesse caso, temos que calcular a tangente da curva em P=(x0,y0). Podemos escrever diretamente me qem termos de A,B,x0,y0:

     3*x0^2 + A
m = ------------
        2*y0

     -x0^3 + A*x0 + 2*B
q = --------------------
          2*y0

Obtemos a equação y = m*x+qe podemos proceder da mesma maneira que no parágrafo acima.

Uma árvore de casos completa

Esta é uma lista completa de como lidar com todos esses casos:

Let P,QSer pontos na curva elíptica (incluindo o ponto "infinito" 0)

• Se P = 0ou Q = 0, então P+Q = Qou P+Q = P, respectivamente
• Senão P ≠ 0e Q ≠ 0, então vamos P = (x0,y0)e Q = (x1,y1):
  • Se P = -Q(isso significa x0 = x1e y0 = -y1) entãoP+Q = 0
  • Outro P ≠ -Q
    • Se x0 = x1então temos P=Qe calculamos a tangente (consulte a seção acima) para obter R. EntãoP+Q = P+P = 2P = -R
    • Senão: podemos construir uma linha do formulário y = m*x+yatravés desses dois pontos (veja a seção acima) para calcular R. EntãoP+Q=-R

Campos finitos

Para esse desafio, consideraremos apenas os campos de tamanho ponde pé primo (e por causa de alguns detalhes p ≠ 2, p ≠ 3). Isso tem a vantagem que você pode simplesmente calcular mod p. A aritmética em outros campos é muito mais complicada.

Neste exemplo, definimos p = 5e todas as igualidades aqui são congruências mod 5.

2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4

Desafio

Dados os parâmetros A,Bde uma curva elíptica, uma característica de campo principal pe dois pontos P,Qna curva elíptica retornam sua soma.

• Você pode assumir que os parâmetros A,Brealmente descrevem uma curva elíptica, o que significa que4A^3+27B^2 ≠ 0 .
• Você pode assumir que P,Qna verdade são pontos na curva elíptica ou no 0ponto-.
• Você pode assumir que p ≠ 2,3é primo.

Casos de teste

Fiz uma implementação (não muito elegante) no MATLAB / Octave, que você pode usar para seus próprios casos de teste: ideone.com Espero que esteja correto. Pelo menos reproduziu alguns cálculos que fiz manualmente.

Observe os casos de teste triviais que funcionam para todas as curvas que consideramos aqui:

Adicionando zero: P+0 = P Adicionando o inverso:(x,y) + (x,-y) = 0

Para p = 7, A = 0, B = 5os dois pontos P = (3,2)e Q = (6,2)estão na curva elíptica. Em seguida, o seguinte é válido:

2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q

Todas as pontas da curva elíptica são (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0

Pois p = 13, A = 3, B = 8temos

(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0

Por p = 17, A = 2, B = 2e P=(5,1) temos

2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)

Se você é realmente ambicioso, tome

p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117

e tente encontrar um número natural ntal que n*(x0,y0) = (x1,y1). Mais informações aqui.

Apêndice

Antes de tudo, um grande OBRIGADO a @ El'endiaStarman por revisar e editar meu rascunho!

Por que curvas elípticas?

Bem, pode parecer algum tipo de equação arbitrária, mas não é, é bastante geral: geralmente consideramos essas "formas" geométricas no plano projetivo (é daí que vem o "infinito". Lá, consideramos tudo isso é uma curva elíptica na forma longa de Weierstrass.Essas são basicamente as mesmas curvas que consideramos, mas apenas um pouco distorcidas.Com uma transformação de coordenadas lineares, você pode facilmente fazer uma equação de Weierstras curta a partir desse exemplo , que ainda mantém todas as propriedades interessantes. homogêneas polinômios de terceiro grau. (Aqueles de grau mais baixo ou mais alto seriam muito difíceis ou triviais para serem examinados.) Depois de aplicar algumas restrições para obter as boas propriedades que desejamos e depois de desmogeneizar esses polinômios (projetando-se em um dos três planos afins) ) acabamos com equações comoy^2+a*x*y+b*y = x^3+c*x^2+d*x+e

Por que nós excluímos p=2,3?

Isso tem a ver com o fato de que, para a forma curta de Weierstrass, precisamos da restrição 4A^3+27B^2 ≠ 0para evitar singularidades (mais sobre isso abaixo). Em um campo da característica 2 que temos 4 = 0e em um campo da característica 3 que temos 27 = 0, isso torna impossível a existência de curvas em forma curta de faixa de Weiers para esses tipos de campos.

O que são singularidades?

Se a equação se 4A^3+27B^2=0mantém, temos singularidades como a seguir: Como você vê nesses pontos, não é possível encontrar uma derivada e, portanto, nenhuma tangente, o que "mata" a operação. Você pode olhar para as equações y^2 = x^3ouy^2 = x^3-3*x+2

Por que eles são chamados de curvas elípticas ?

A razão é que as equações dessa forma aparecem em integrais elípticas, por exemplo, quais são as suas vantagens quando você deseja calcular o, por exemplo, o comprimento do arco de uma elipse. Uma pequena apresentação de slides sobre a origem do nome.

O que eles têm a ver com criptografia?

Existem maneiras de calcular com nP = P+P+...+Pmuita eficiência. Isso pode ser usado, por exemplo, na troca de chaves Diffie Hellman . A aritmética modular pode ser substituída pela adição em subgrupos de torção, esses são apenas os pontos na curva que têm ordem finita. (Isso significa que, mP = 0para alguns m, o que é basicamente apenas um cálculo mod m).

Pitão, 105 100 bytes

A,@Q3eQ?qGZH?qHZG?&=YqhHhGqeG%_eHhQZ_m%dhQ,-*J?Y*+*3^hG2@Q1^*2eG-hQ2*-eGeH^-hGhH-hQ2-hGK--^J2hGhHeGK

A entrada é esperada como (p, A, P, Q), onde Pe Qsão os dois pontos do formulário (x, y)ou, se eles são o 0ponto especial , apenas como 0. Você pode experimentá-lo online aqui . Os dois últimos exemplos mostram como o especial 0funciona.

Para economizar alguns bytes, eu uso apenas mod pna resposta final. Isso significa que ele faz as coisas x0^palgumas vezes sem fazer exponenciação modular, por isso pode ser muito lento.

Funciona seguindo aproximadamente a mesma lógica que esta função Python:

def add_ellip(p, A, P, Q): # points are in format (x, y)
    z = 0 # representing special 0 point

    if (P == z):
        return Q
    if (Q == z):
        return P

    if P[0] == Q[0]:
        if (P == (Q[0], -Q[1] % p)):
            return z
        else:
            m = ((3*pow(P[0], 2, p) + A)*pow(2*P[1], p-2, p)) % p
    else:
        m = (P[1] - Q[1])*pow(P[0] - Q[0], p-2, p) % p

    x = (pow(m, 2, p) - P[0] - Q[0]) % p
    y = (m*(P[0] - x) - P[1]) % p
    return (x, y)

Isso depende muito do fato de que o inverso multiplicativo modular de xé igual a x^(p-2) mod pse pé primo. Assim, somos capazes de calcular ma inclinação da linha, encontrando o inverso multiplicativo modular do denominador e multiplicando-o pelo numerador. Muito útil. A função Python deve calcular problemas maiores um pouco mais eficientemente devido ao uso de pow.

Eu também usei os atalhos mostrados na página da Wikipedia sobre este assunto . É bastante interessante que eu só acabo usando Auma vez, e Bnem um pouco.

Também apenas por diversão:

def pow2floor(x):
    p = 1
    x >>= 1
    while (x > 0):
        x >>= 1
        p <<= 1
    return p

def multi_nP(p, A, n, P):
    d = {}

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half
            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP

    return rec_helper(n, P)

A multi_nPfunção calcula n*Pum determinado número inteiro ne ponto P. Ele usa uma estratégia recursiva dividindo-se nem duas partes p2fe de remaindertal forma p2f + remainder = nquep2f = 2^k . Em seguida, chamamos a função novamente nessas partes, adicionando o resultado com add_ellip. Também usei a abordagem básica de programação dinâmica salvando os valores já calculados no dict d.

A próxima função teoricamente resolveria a questão do bônus usando a mesma estratégia:

def find_nPQ(p, A, P, Q): # P is input point, Q is what we're looking for
    d = {}
    found_Q = False

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half

            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP


    for x in range(p):
        xP = rec_helper(x, P)
        if (xP == Q):
            return x

Infelizmente, ele não chega nem perto o suficiente para computá-lo. Suponho que possa haver maneiras muito mais eficientes de fazer isso, especialmente se não precisarmos iterar todos os valores possíveis n.

Python 3, 193 191 bytes

Uma solução baseada na resposta Pyth do Rhyzomatic e sua lógica Python. Em particular. Eu gostei de como eles descobriram a terceira raiz de um polinômio cúbico monic x^3 + bx^2 + cx + dquando você tem duas raízes x_1e x_2observando que b == x_1 + x_2 + x_3e subtraindo conformidade. Pretendo acrescentar uma explicação, dar um tapa nisso e talvez transpilar para Ruby, se Ruby for mais curto.

def e(p,A,B,P,Q):
 if P==0:return Q
 if Q==0:return P
 f,g=P;j,k=Q
 if f==j:
  if g==-k%p:return 0
  m=(3*f*f+A)*pow(2*j,p-2)
 else:m=(g-k)*pow(f-j,p-2)
 x=m*m-f-j;y=m*(f-x)-g;return(x%p,y%p)

Ungolfing:

def elliptic_curve_addition(p, A, B, P, Q):
    if P == 0:
        return Q
    if Q == 0:
        return P
    f,q = P
    j,k = Q
    if f==j:
        if g == (-k) % p:
            return 0
        m = (3 * f**2 + A) * pow(2*j, p-2)
    else:
        m = (g-k) * pow(f-j, p-2)
    x = m**2 - f - j
    y = m * (f-x) - g
    return (x%p, y%p)