¿Cuál es la matemática detrás de la criptografía de curva elíptica?

Introducción

Cuando alguien le envía bitcoins, lo envían a su dirección. Si desea gastar parte de los bitcoins que se envían a su dirección, cree una transacción y especifique dónde debe ir su bitcoin. Tal transacción puede verse como:

Transfiera 5 bitcoins de 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa (su dirección) a 12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX (la dirección del destinatario).

Por supuesto, cualquiera puede crear una transacción que se parezca a la anterior, por lo que si se agregara a la cadena de bloques tal como está y sin problemas, perdería $ 30,000 o más, le guste o no. Afortunadamente, dicha transacción no pertenece a la cadena de bloques, porque le falta una firma digital válida. Al agregar una firma digital, puede demostrar que conoce la clave privada que corresponde a la dirección 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfN. Si no conoce la clave privada correspondiente, entonces probablemente no debería haber estado diciéndole a la gente que le envíe bitcoins a través de esa dirección, ¡ya que no puede gastar nada de los bitcoins enviados allí!

Cuando crea una dirección de bitcoin para usted (o una dirección/cuenta para cualquier otra criptomoneda), primero genera la clave privada. A partir de la clave privada, calcula la clave pública correspondiente y, al codificar esa clave pública, obtiene su dirección. Con suerte, no puede elegir una dirección primero y luego determinar la clave privada a partir de ella; de lo contrario, podría determinar la clave privada para cualquier dirección utilizando el mismo método. ¿Cuál es la dirección de Satoshi de nuevo?

Criptografía de clave pública

Las claves públicas, las claves privadas y las firmas digitales forman los componentes básicos de la criptografía de clave pública. No importa qué base matemática se utilice para implementar un sistema criptográfico de clave pública, debe satisfacer lo siguiente, al menos para nuestros propósitos:

1. Es computacionalmente inviable derivar la clave privada correspondiente a una clave pública dada.
2. Es posible demostrar que se conoce la clave privada correspondiente a una clave pública sin revelar ninguna información útil sobre la clave privada en el proceso. Además, dicha prueba se puede construir de manera que requiera que se verifique un mensaje específico. De esta forma, la prueba forma una firma digital para ese mensaje.

Una forma de hacer criptografía de clave pública es con curvas elípticas. Otra forma es con RSA, que gira en torno a los números primos. La mayoría de las criptomonedas, incluidas Bitcoin y Ethereum, utilizan curvas elípticas, porque una clave privada de curva elíptica de 256 bits es tan segura como una clave privada RSA de 3072 bits. Las teclas más pequeñas son más fáciles de administrar y trabajar.

Criptografía de curva elíptica

¿Qué es una curva elíptica? Una curva elíptica consta de todos los puntos que satisfacen una ecuación de la siguiente forma:

y² = x³+ax+b

donde 4a³+27b² ≠ 0 (esto es necesario para evitar puntos singulares ).

Aquí hay algunos ejemplos de curvas elípticas:

Observe que todas las curvas elípticas anteriores son simétricas con respecto al eje x. Esto es cierto para cada curva elíptica porque la ecuación para una curva elíptica es:

y² = x³+ax+b

Y si sacas la raíz cuadrada de ambos lados obtienes:

y = ± √x³+ax+b

Así que si a=27 yb=2 y reemplazas x=2, obtendrás y=±8, resultando en los puntos (2, -8) y (2, 8).

La curva elíptica utilizada por Bitcoin, Ethereum y muchas otras criptomonedas se llama secp256k1. La ecuación para la curva secp256k1 es y² = x³+7. Esta curva se parece a:

Satoshi eligió secp256k1 sin ninguna razón en particular .

Adición de puntos

¿Sabes cómo puedes sumar dos números para obtener un tercer número? Puede sumar dos puntos en una curva elíptica para obtener un tercer punto en la curva.

Para sumar dos puntos en una curva elíptica, primero encuentra la línea que pasa por esos dos puntos. Luego determina dónde esa línea se cruza con la curva en un tercer punto. Luego, reflejas ese tercer punto a lo largo del eje x (es decir, multiplicas la coordenada y por -1) y cualquier punto que obtengas es el resultado de sumar los dos primeros puntos.

Echemos un vistazo a un ejemplo de esto. Supongamos que desea sumar los dos puntos siguientes:

Primero, encuentra la línea que pasa por los dos puntos:

Luego encuentra el tercer punto en la curva que la línea intersecta:

Luego reflejas ese punto a través del eje x:

Por lo tanto, P+Q=R.

Para hacer la criptografía de curva elíptica correctamente, en lugar de agregar dos puntos arbitrarios, especificamos un punto base en la curva y solo agregamos ese punto a sí mismo.

Por ejemplo, digamos que tenemos la siguiente curva con punto base P:

Inicialmente, tenemos P, o 1•P.

Ahora agreguemos P a sí mismo. Primero, tenemos que encontrar la ecuación de la línea que pasa por P y P. ¡Hay infinitas líneas de este tipo! En este caso especial, optamos por la recta tangente.

Ahora encontramos el "tercer" punto que esta línea interseca y lo reflejamos a lo largo del eje x.

Así P sumado a sí mismo, o P+P, es igual a 2•P.

Si volvemos a sumar P a sí mismo, estaremos calculando P sumado a sí mismo sumado a sí mismo, o P+P+P. El resultado será 3•P. Para calcular 3•P, podemos simplemente sumar P y 2•P juntos.

Podemos continuar sumando P a sí mismo para calcular 4•P y 5•P y así sucesivamente.

El punto base utilizado por la curva secp256k1 tiene las siguientes coordenadas x e y:

coordenada x: 550662630222773436695787188951685343262506034537775941755500187360389116729240

coordenada y:32670510020758816978083085130507043184471273380659243275938904335757337482424

En los ejemplos anteriores, se usa un punto base diferente para que todas las operaciones de suma de puntos quepan en una pequeña ventana.

Acelerando la suma de puntos

¿Cuántos pasos se necesitarían para calcular 10•P? Parecería tomar nueve pasos, porque 10•P es

P+P+P+P+P+P+P+P+P+P

que requiere operaciones de suma de nueve puntos.

Resulta que puedes calcular 10•P en solo cuatro pasos. Esto se debe a que la siguiente propiedad se cumple para la suma de puntos:

n•P+r•P = (n+r)•P

Por ejemplo:

4•P+6•P = (4+6)•P = 10•P

Por lo tanto, la forma rápida de calcular 10•P es la siguiente:

P+P = 2•P

2•P+2•P = 4•P

4•P+4•P = 8•P

2•P+8•P=10•P

que solo requiere operaciones de suma de cuatro puntos.

¿Cuántos pasos se necesitarían para calcular x•P, donde x es un número entero aleatorio de 256 bits? En este caso, x puede oscilar entre 0 y 1,1579209e+77.

Resulta que calcular x•P nunca requeriría más de 510 operaciones de suma de puntos. Este es el por qué. Primero, calcule la siguiente serie:

2⁰•P, 2¹•P, 2²•P, 2³•P, 2⁴•P, 2⁵•P, 2⁶•P, … , 2²⁵⁵•P.

Puede calcular la serie anterior con operaciones de suma de 255 puntos, porque hay 256 puntos, y puede pasar de un punto al siguiente sumando el punto actual a sí mismo. Esto se debe a que 2^n•P+2^n•P = 2^(n+1)•P. Se da el primer punto, 2⁰•P. 2⁰•P=1•P=P.

El siguiente paso es encontrar la expansión binaria de x. Por ejemplo, si x es 246, la expansión binaria será 2⁷ + 2⁶ + 2⁵ + 2⁴ +2² + 2¹ = 246. Luego multiplicamos la expansión binaria de x por P: 2⁷•P + 2⁶•P + 2⁵•P + 2⁴•P + 2²•P + 2¹•P. Luego simplemente sumamos todos estos puntos para obtener 246•P. No tenemos que calcular los puntos individuales 2¹•P, 2²•P, … , 2⁷•P ya que los calculamos antes.

Como mucho, la expansión binaria de x contendrá 256 elementos (2⁰ hasta 2²⁵⁵), por lo que nunca tendremos que sumar más de 256 puntos juntos y, por lo tanto, el segundo paso requerirá como máximo 255 operaciones de suma de puntos. Por lo tanto, calcular x•P requerirá como máximo 255+255=510 operaciones de suma de puntos.

Claves públicas y privadas en criptografía de curva elíptica

Digamos que calculo x•P, donde x es un entero aleatorio de 256 bits. El resultado será algún punto de la curva. Llamemos a ese punto X.

Si te doy X, ¿podrías determinar x? En otras palabras, ¿podría determinar cuántas veces sumé P a sí mismo para obtener el punto X en la curva? Supongamos que sabe qué es P y qué curva estaba usando.

Resulta que no es factible para ti averiguar x, incluso si tuvieras una supercomputadora. No existe un algoritmo conocido para determinar x, por lo que su única opción es seguir sumando P a sí mismo hasta obtener X o seguir restando P de X hasta obtener P. En promedio, x estará entre 0 y 2²⁵⁶-1, aproximadamente 2¹²⁸. Por lo tanto, le llevará en promedio 2¹²⁸ operaciones de suma de puntos para determinar x sin importar su enfoque. Incluso si tu computadora pudiera hacer un billón de operaciones de suma de puntos por segundo y hubieras estado usando tu computadora desde el comienzo del universo, hasta ahora solo habrías hecho 2⁹⁸ operaciones de suma de puntos. 2⁹⁸/2¹²⁸ =1/1073741824.

¿Qué pasa si empiezas en el medio? Después de todo, puedes calcular 2¹²⁸•P en 510 pasos o menos. Bueno, en promedio, x no está más cerca de 2¹²⁸ que de 0 o 2²⁵⁶-1, porque x es aleatoria, por lo que no importa por dónde empieces, tendrás que hacer sumas de 2¹²⁸ en promedio.

Claves públicas y privadas

Entonces, debido a que alguien no puede averiguar x dado X, donde X=x•P, podría ser conveniente hacer de x su clave privada y de X su clave pública. Entonces, su clave privada sería un número entero aleatorio de 256 bits y su clave pública serían las coordenadas x e y de un punto en una curva elíptica. Esto cumpliría la siguiente propiedad de las claves públicas y privadas:

"Es computacionalmente inviable derivar la clave privada correspondiente a una clave pública dada".

Además, aunque todavía no hemos discutido esto, es posible probarle a alguien que conoces x, sin revelar ninguna información útil sobre x. Es decir, puede mostrarle a alguien que sabe cuántas veces tendría que sumar P a sí mismo para obtener X sin decirle directamente qué es x.

El modelo de curva elíptica actualizado

Antes de probarle a alguien que conoces x, debemos actualizar nuestro modelo de curva elíptica.

Uno de los problemas con nuestro modelo actual es que x•P puede resultar en un punto cuyas coordenadas x e y no se pueden almacenar en una clave pública estándar de 512 bits. La coordenada x o y podría ser demasiado larga.

La solución es definir nuestra curva elíptica sobre un campo finito. Básicamente, nos aseguraremos de que solo haya puntos enteros y que haya un límite para el tamaño de las coordenadas de un punto.

Para ello transformamos

y² = x³+ax+b

a

y² mod p = (x³ + ax + b) mod p.

Donde p es un número primo (p es primo para asegurar que las operaciones de suma y multiplicación siempre se puedan deshacer).

En secp256k1, p es el primo más grande que es menor que 2²⁵⁶.

Nuestra curva elíptica ahora se parece a:

Observe que todavía hay una línea de simetría horizontal.

Entonces, ¿qué sucede cuando sumas dos puntos y la línea que va entre esos dos puntos sale de los límites antes de cruzar un tercer punto? ¡Envuelves la línea alrededor de los confines!

En la imagen de arriba, puede ver cómo sumar P y Q requiere envolver la línea "entre" P y Q alrededor de los límites varias veces.

A pesar de estos cambios en nuestro modelo, todo lo que hemos discutido hasta ahora aún se aplica.

Cómo demostrar que sabes x

Entonces, si calcula X=x•P, donde x es un número entero aleatorio de 256 bits, ¿cómo puede demostrarle a alguien que conoce la x que corresponde a X sin revelar ninguna información útil sobre x?

Puede usar la propiedad de suma de puntos de antes:

n•P+r•P = (n+r)•P

Lo modificaremos ligeramente:

hash(m, r•P)•n•P+r•P = (hash(m, r•P)*n+r)•P

Si expande el lado derecho de la ecuación anterior, obtendrá el lado izquierdo, por lo que la ecuación anterior es válida para cualquier m, r y n.

Entonces, ¿qué sucede si establecemos n•P=X? Tendremos:

hash(m, r•P)•X+r•P = (hash(m, r•P)*n+r)•P

Si n•P=X, entonces n=x, entonces tenemos:

hash(m, r•P)•X+r•P = (hash(m, r•P)*x+r)•P

Ahora vamos a hacer las siguientes sustituciones: R=r•P y s=hash(m,R)*x+r.

Así que ahora tenemos:

hash(m, R)•X+R = s•P

Bien, esta es la afirmación: si puedes proporcionar una m, una R y una s que satisfagan la ecuación anterior, entonces esto prueba que conoces la x correspondiente a la X en la ecuación, donde x•P=X.

Para que esto sea así, se deben cumplir las dos condiciones siguientes:

1. Si conoce x, entonces debería poder proporcionar valores de trabajo para m, R y s.
2. Si no conoce x, entonces no debería poder proporcionar valores de trabajo para m, R y s.

Si conoce x, claramente puede encontrar valores de trabajo para m, R y s. Elija valores aleatorios para m y r, luego calcule R=r•P y s=hash(m)*x+r. Si conecta estos valores en hash(m,R)•X+R=s•P, entonces obtiene:

hash(m, r•P)•x•P+r•P = (hash(m, r•P)*x+r)•P

que es la ecuación que dijimos que se cumpliría antes para cualquier m, r y n (x es n en este caso).

¿Qué pasa si no sabes x? ¿Podría encontrar valores de trabajo para m, R y s? El problema es que tendrías que resolver hash(m,R)•X+R=s•P. Básicamente, tendría que encontrar una entrada para un hash que tenga un valor hash específico, lo cual no es posible, o al menos no es computacionalmente factible, debido a la propiedad de resistencia a la preimagen de las funciones hash criptográficas.

Por lo tanto, la única forma de proporcionar valores de trabajo para m, R y s es calcularlos usando x. Por lo tanto, puede probar que conoce la clave privada, x, que va con la clave pública, X, proporcionando valores para m, R y s que satisfagan hash(m,R)•X+R=s•P.

¿Revelas alguna información útil sobre x demostrando que conoces x?

Si proporciona valores de trabajo para m, R y s, ¿se puede obtener algo útil sobre x de esos valores?

m y R no tienen nada que ver con x, por lo que esos valores no pueden revelar nada útil sobre x.

Sabemos que s=hash(m,R)*x+r. ¿Alguien podría calcular x a partir de s?

Para hacerlo, tendrían que resolver x=(sr)/hash(m, R).

Como no conocen r, no pueden calcular x a partir de s. No pueden obtener r del hecho de que R=r•P (se les da R), porque eso es lo mismo que determinar cuántas veces P tendría que sumarse a sí mismo para obtener R, que es el mismo problema computacionalmente inviable que impide que alguien determine x a partir de X.

s tampoco revela ninguna información sobre x, como "x debe ser menor que yadda yadda". Si r se genera aleatoriamente y permitimos que hash(m, R)*x+r se desborde para que r pueda ser cualquier número entero de 256 bits, entonces el valor de s es completamente aleatorio, lo que significa que s podría ser cualquier número entero de 256 bits. Un entero aleatorio de 256 bits te dice tanto como el PIB de Nueva Zelanda.

Firmas digitales

m, R y s se pueden usar para demostrar que se conoce la x que corresponde a X, donde X=x•P. Verificar la prueba requiere insertar m, R y s en hash(m,R)•X+R=s•P. ¿Podemos hacer que se requiera un mensaje específico para que la verificación sea exitosa, de modo que la prueba (m, R y s) forme una firma digital para ese mensaje? ¡Sí!

Sea m ese mensaje específico y R y s sean la firma digital de ese mensaje. Entonces, el proceso de verificación solo tendría éxito si el mensaje específico, m, se conecta a la ecuación de verificación. Si se introduce un valor diferente para m, entonces el lado izquierdo de hash(m,R)•X+R=s•P no sería igual al lado derecho, porque s se calculó usando un mensaje diferente.

Así, uno puede demostrar que conoce la clave privada, x, que corresponde a una clave pública, X, para un mensaje específico, m, proporcionando una firma digital R y s para m.

Para las criptomonedas, el mensaje sería la parte sin firmar de una transacción. Si alguna vez mira una firma digital para una transacción, generalmente es la coordenada x de R (R es un punto en la curva) concatenada con s (s es un número entero aparentemente aleatorio de 256 bits), después de que se haya codificado y convertido a hexadecimal.

Conclusión

Si desea obtener una dirección de Bitcoin o una cuenta de Ethereum, genera un número entero x aleatorio de 256 bits. x es entonces su clave privada. Luego calcula X= x•P usando los parámetros para la curva secp256k1. X será tu clave pública. Es seguro dar su clave pública y no se puede usar para determinar su clave privada. Si hash tu clave pública, obtendrás tu dirección.

Cuando desea enviar bitcoin o ether desde su dirección a otra dirección, crea una transacción. Establece m en la parte sin firmar de esa transacción y calcula R y s a partir de esa m. Luego adjuntas R y s a la transacción. Después de transmitir su transacción, cualquier nodo podrá verificar que m (la parte sin firmar de la transacción), R y s satisfacen hash(m,R)•X+R=s•P. Por supuesto, esto supone que también incluye X en su transacción, ya que su clave pública no se puede determinar a partir de su dirección. Para Ethereum, en lugar de proporcionar X, proporciona v, lo que permite determinar X a partir de R y s.

El fin

¡Bueno, ese es el final! Si llegaste hasta aquí y entendiste casi todo, ¡felicidades! Si desea una explicación de nivel superior de la criptografía de curva elíptica (más matemática), consulte este enlace . Este es mi primer artículo, así que avísenme si hay algún error y dejen sus comentarios.

¡Gracias por leer!