Las matemáticas detrás del protocolo Bitcoin

Una razón por la que Bitcoin puede resultar confuso para los principiantes es que la Tecnología que hay detrás redefine el concepto de propiedad.

Ser propietario de algo en el sentido tradicional, ya sea una casa o una suma de dinero, significa tener la custodia personal de la cosa o conceder la custodia a una entidad confiable, como un banco.

Protocolo Bitcoin

Con Bitcoin, el caso es diferente. Los bitcoins en sí no se almacenan ni de forma central ni local, por lo que ONE entidad es su custodio. Existen como registros en un libro de contabilidad distribuido llamado cadena de bloques, cuyas copias son compartidas por una red voluntaria de computadoras conectadas. Ser propietario de un Bitcoin simplemente significa tener la capacidad de transferir su control a otra persona mediante la creación de un registro de la transferencia en la cadena de bloques. ¿Qué otorga esta capacidad? El acceso a... ECDSA Par de claves privada y pública. ¿Qué significa esto y cómo protege Bitcoin?

Echemos un vistazo debajo del capó.

ECDSAes la abreviatura de Algoritmo de Firma Digital de Curva Elíptica. Es un proceso que utiliza uncurva elípticay uncampo finito Firmar datos de forma que terceros puedan verificar la autenticidad de la firma, manteniendo al firmante la capacidad exclusiva de crearla. Con Bitcoin, los datos firmados constituyen la transacción que transfiere la propiedad.

ECDSA cuenta con procedimientos separados para la firma y la verificación. Cada procedimiento es un algoritmo compuesto por unas pocas operaciones aritméticas. El algoritmo de firma utiliza la clave privada, mientras que el proceso de verificación utiliza la clave pública. Mostraremos un ejemplo más adelante.

Pero primero, un curso intensivo sobre curvas elípticas y campos finitos.

curvas elípticas

Una curva elíptica se representa algebraicamente como una ecuación de la forma:

y2 = x3 + ax + b

Para a = 0 y b = 7 (la versión utilizada por Bitcoin), LOOKS así:

Las curvas elípticas tienen propiedades útiles. Por ejemplo, una línea no vertical que interseca dos puntos no tangentes de la curva siempre interseca un tercer punto de la curva. Otra propiedad es que una línea no vertical tangente a la curva en un punto interseca precisamente ONE punto de la curva.

Podemos utilizar estas propiedades para definir dos operaciones: suma de puntos y duplicación de puntos.

Adición de puntos,P + Q = R,se define como la reflexión a través del eje x del tercer punto de intersecciónR’en una línea que incluyePAG y QEs más fácil entenderlo usando un diagrama:

Similarmente,duplicación de puntos,P + P = Rse define encontrando la recta tangente al punto que se va a duplicar,PAG, y tomando la reflexión a través del eje x del punto de intersecciónR’En la curva para llegarRAquí hay un ejemplo de cómo se vería:

Juntas, estas dos operaciones se utilizan paramultiplicación escalar,R = una P,definido añadiendo el puntoPAGa sí mismoaveces. Por ejemplo:

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

El proceso de multiplicación escalar se simplifica normalmente mediante una combinación de operaciones de suma y duplicación de puntos. Por ejemplo:

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

Aquí, 7PSe ha dividido en dos pasos de duplicación de puntos y dos pasos de adición de puntos.

campos finitos

Un campo finito, en el contexto de ECDSA, puede considerarse como un rango predefinido de números positivos dentro del cual debe estar todo cálculo. Cualquier número fuera de este rango se ajusta para quedar dentro del mismo.

La forma más sencilla de entender esto es calcular los residuos, representados por el operador módulo (mod). Por ejemplo, 9/7 da 1 con un residuo de 2:

9 módulo 7 = 2

Aquí nuestro campo finito es módulo 7, y todas las operaciones mod sobre este campo producen un resultado que cae dentro de un rango de 0 a 6.

Poniéndolo todo junto

El ECDSA utiliza curvas elípticas en el contexto de un campo finito, lo que altera considerablemente su apariencia, pero no sus ecuaciones subyacentes ni sus propiedades especiales. La misma ecuación, representada anteriormente, en un campo finito de módulo 67, LOOKS así:

Ahora es un conjunto de puntos, en los que todos losincógnita y yLos valores son números enteros entre 0 y 66. Tenga en cuenta que la “curva” aún conserva su simetría horizontal.

La suma y duplicación de puntos ahora tienen una ligera diferencia visual. Las líneas dibujadas en este gráfico se ajustarán horizontal y verticalmente, como en un juego de Asteroids, manteniendo la misma pendiente. Por lo tanto, la suma de los puntos (2, 22) y (6, 25) LOOKS así:

El tercer punto de intersección es (47, 39) y su punto de reflexión es (47, 28).

Regreso a ECDSA y Bitcoin

Un protocolo como Bitcoin selecciona un conjunto de parámetros para la curva elíptica y su representación de campo finito, que es fijo para todos los usuarios del protocolo. Los parámetros incluyen: ecuaciónusado, elmódulo PRIMEdel campo, y unapunto baseque cae sobre la curva. Elorden El punto base, que no se selecciona independientemente, sino que es función de los demás parámetros, puede representarse gráficamente como el número de veces que el punto puede sumarse a sí mismo hasta que su pendiente sea infinita o una línea vertical. El punto base se selecciona de tal manera que el orden sea un número PRIME grande.

Bitcoin utiliza números muy grandes como punto base, módulo PRIME y orden. De hecho, todas las aplicaciones prácticas de ECDSA utilizan valores enormes. La seguridad del algoritmo depende de que estos valores sean grandes y, por lo tanto, imprácticos para aplicar fuerza bruta o ingeniería inversa.

En el caso de Bitcoin:

Ecuación de curva elíptica: y2 = x3 + 7

Módulo PRIME = 2256 – 232 – 29 – 28 – 27 – 26 – 24 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Punto base = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Pedido = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

¿Quién eligió estos números y por qué? Una gran cantidad deinvestigación, y una buena cantidad deintriga, rodea la selección de parámetros apropiados. Después de todo, un número grande, aparentemente aleatorio, podría ocultar un método de puerta trasera para reconstruir la clave privada. En resumen, esta implementación en particular se conoce como secp256k1 y forma parte de una familia de soluciones de curva elíptica sobre campos finitos, propuestas para su uso en criptografía.

Claves privadas y claves públicas

Una vez superadas estas formalidades, ahora podemos comprender las claves privadas y públicas y su relación. En resumen: en ECDSA, la clave privada es un número impredecible entre 1 y el orden. La clave pública se deriva de la clave privada mediante la multiplicación escalar del punto base un número de veces igual al valor de la clave privada. Expresado como una ecuación:

clave pública = clave privada * punto base

Esto demuestra que el número máximo posible de claves privadas (y por tanto de direcciones de Bitcoin ) es igual al orden.

En un campo continuo podríamos trazar la línea tangente y localizar la clave pública en The Graph, pero hay algunas ecuacionesque logran lo mismo en el contexto de campos finitos. Adición de puntos dep + qPara encontraroSe define componente por componente de la siguiente manera:

c = (qy - py) / (qx - px)

rx = c2 - px - qx

ry = c (px - rx) - py

Y el punto de duplicación para encontraroes como sigue:

c = (3px2 + a) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

En la práctica, el cálculo de la clave pública se divide en una serie de operaciones de duplicación y adición de puntos a partir del punto base.

Ejecutemos un ejemplo aproximado con números pequeños para comprender cómo se construyen y utilizan las claves para firmar y verificar. Los parámetros que utilizaremos son:

Ecuación: y2 = x3 + 7 (es decir, a = 0 y b = 7)

Módulo PRIME : 67

Punto base: (2, 22)

Orden: 79

Clave privada: 2

Primero, encontremos la clave pública. Dado que hemos seleccionado la clave privada más simple posible con valor = 2, solo se requerirá una única operación de duplicación de punto desde el punto base. El cálculo LOOKS así:

c = (3 * 22 + 0) / (2 * 22) mod 67

c = (3 * 4) / (44) módulo 67

c = 12 / 44 módulo 67

Aquí tenemos que hacer una pausa para un BIT truco: ¿cómo realizamos la división en el contexto de un cuerpo finito, donde el resultado siempre debe ser un entero? Tenemos que multiplicar por la inversa, cuyo espacio no nos permite definir aquí (le remitimos a aquí y aquíSi le interesa). En este caso, deberá confiar en nosotros por el momento:

44-1 = 32

Continuando adelante:

c = 12 * 32 módulo 67

c = 384 módulo 67

c = 49

rx = (492 - 2 * 2) mod 67

rx = (2401 - 4) mod 67

rx = 2397 mod 67

rx = 52

ry = (49 * (2 - 52) - 22) mod 67

ry = (49 * (-50) - 22) mod 67

ry = (-2450 - 22) mod 67

ry = -2472 mod 67

ry = 7

Nuestra clave pública corresponde, por tanto, al punto (52, 7). ¡Todo ese trabajo para una clave privada de 2!

Esta operación (pasar de la clave privada a la clave pública) es computacionalmente fácil en comparación con intentar trabajar al revés para deducir la clave privada de la clave pública, lo que si bien es teóricamente posible es computacionalmente inviable debido a los grandes parámetros utilizados en la criptografía elíptica real.

Por lo tanto, pasar de la clave privada a la clave pública es, por diseño, un viaje de ida.

Al igual que con la clave privada, la clave pública se representa normalmente mediante una cadena hexadecimal. Pero espere, ¿cómo pasamos de un punto en un plano, descrito por dos números, a un solo número? En una clave pública sin comprimir, los dos números de 256 BIT que representan... incógnita y yLas coordenadas simplemente se unen en una cadena larga. También podemos aprovechar la simetría de la curva elíptica para producir una clave pública comprimida, manteniendo solo las xValor y anotando en qué mitad de la curva se encuentra el punto. A partir de esta información parcial, podemos recuperar ambas coordenadas.

Firmar datos con la clave privada

Ahora que tenemos un par de claves privadas y públicas, ¡firmemos algunos datos!

Los datos pueden tener cualquier longitud. El primer paso habitual es aplicar un hash a los datos para generar un número con la misma cantidad de bits (256) que el orden de la curva. Para simplificar, omitiremos el hash y simplemente firmaremos los datos sin procesar.zTe llamaremosGRAMOel punto base, el orden ydLa clave privada. La receta para firmar es la siguiente:

• Elija un número entero k entre 1 y n - 1.
• Calcula el punto (x, y) = k * G, usando la multiplicación escalar.
• Encuentra r = x mod n. Si r = 0, regresa al paso 1.
• Encuentra s = (z + r * d) / k mod n. Si s = 0, regresa al paso 1.
• La firma es el par (r, s)

Como recordatorio, en el paso 4, si los números resultan en una fracción (lo cual casi siempre ocurre en la vida real), el numerador debe multiplicarse por el inverso del denominador. En el paso 1, es importante quekNo debe repetirse en diferentes firmas y no debe ser adivinado por un tercero. Es decir,k Debe ser aleatoria o generada por medios deterministas que se mantengan en Secret . De lo contrario, sería posible extraer la clave privada del paso 4, ya que... z,o,ky son todos conocidos. Puedes leer sobre una hazaña pasada de este tipo.aquí.

Elijamos el número 17 como nuestro dato y Síguenos la receta. Nuestras variables:

z = 17 (datos)

n = 79 (orden)

G = (2, 22) (punto base)

d = 2 (clave privada)

• Elige un número al azar:

k = rand(1, n - 1)

k = rand(1, 79 - 1)

k = 3 (¿esto es realmente aleatorio? ¡Está bien, nos atrapaste, pero esto hará que nuestro ejemplo sea más sencillo!)

1. Calcular el punto. Esto se hace de la misma manera que determinar la clave pública, pero para abreviar, omitiremos la suma y duplicación de puntos.

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

y = 63

1. Encontrar o:

r = x módulo n

r = 62 módulo 79

r = 62

1. Encontrar :

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 módulo 79

s = 47

Tenga en cuenta que arriba pudimos dividir entre 3 ya que el resultado fue un entero. En casos reales, usaríamos el inverso dek(como antes, hemos ocultado algunos detalles sangrientos al calcularlos en otra parte):

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 141 * 3-1 módulo 79

s = 141 * 53 módulo 79

s = 7473 módulo 79

s = 47

1. Nuestra firma es el par (o, ) = (62, 47).

Al igual que con las claves privadas y públicas, esta firma normalmente está representada por una cadena hexadecimal.

Verificar la firma con la clave pública

Ahora tenemos datos y una firma para esos datos. Un tercero con nuestra clave pública puede recibirlos y verificar que somos los remitentes. Veamos cómo funciona.

Con Qsiendo la clave pública y las demás variables definidas como anteriormente, los pasos para verificar una firma son los siguientes:

• Verifique que r y s estén entre 1 y n - 1.
• Calcular w = s-1 mod n
• Calcular u = z * w mod n
• Calcular v = r * w mod n
• Calcular el punto (x, y) = uG + vQ
• Verifique que r = x mod n. La firma no es válida si no lo es.

¿Por qué funcionan estos pasos? Omitimos la prueba, pero puedes leer los detalles.aquíSíguenos la receta y veamos cómo funciona. Nuestras variables, una vez más:

z = 17 (datos)

(r, s) = (62, 47) (firma)

n = 79 (orden)

G = (2, 22) (punto base)

Q = (52, 7) (clave pública)

• Verificar queoy están entre 1 y - 1. Comprobar y comprobar.

r: 1 <= 62 < 79

s: 1 <= 47 < 79

1. Calcularo:

w = s-1 módulo n

w = 47-1 módulo 79

w = 37

1. Calculartú:

u = zw módulo n

u = 17 * 37 módulo 79

u = 629 módulo 79

u = 76

1. Calcularv:

v = rw módulo n

v = 62 * 37 módulo 79

v = 2294 módulo 79

v = 3

1. Calcular el punto (incógnita,y):

(x, y) = uG + vQ

Analicemos la duplicación y la suma de puntos enuG y vQpor separado.

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

Relájense un momento para apreciar que, al usar el truco de agrupación, reducimos 75 operaciones de suma sucesivas a solo seis operaciones de duplicación de punto y dos operaciones de suma de punto. Estos trucos serán útiles cuando los números sean muy grandes.

Trabajando desde adentro hacia afuera:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

Y ahora paravQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

Juntándolos:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

Claramente, el paso 5 representa la mayor parte del trabajo. Para el paso final,

1. Verifique que r = x mod n

r = x módulo n

62 = 62 módulo 79

62 = 62

¡Nuestra firma es válida!

Conclusión

Para aquellos de ustedes que vieron todas las ecuaciones y saltaron al final, ¿qué acabamos de aprender?

Hemos desarrollado cierta intuición sobre la profunda relación matemática que existe entre las claves públicas y privadas. Hemos visto cómo, incluso en los ejemplos más sencillos, las matemáticas que sustentan las firmas y la verificación se complican rápidamente, y podemos apreciar la enorme complejidad que implica cuando los parámetros involucrados son números de 256 BIT . Hemos visto cómo la aplicación inteligente de los procedimientos matemáticos más sencillos puede crear las funciones de "trampa" unidireccionales necesarias para preservar la asimetría de información que define la propiedad de un Bitcoin. Y hemos renovado nuestra confianza en la robustez del sistema, siempre que protejamos cuidadosamente el conocimiento de nuestras claves privadas.

En otras palabras, es por esto que comúnmente se dice que Bitcoin está “respaldado por las matemáticas”.

Si aguantó las partes complicadas, esperamos que le haya dado la confianza para dar el siguiente paso y probar las matemáticas por su cuenta (unCalculadora aritmética modularFacilita enormemente las matemáticas de campos finitos. Descubrimos que firmar y verificar datos manualmente proporciona una comprensión más profunda de la criptografía que habilita la forma única de propiedad de bitcoin.

Este artículo se ha republicado aquí con la autorización del autor. Publicado originalmente enCadena.comEl autor agradece especialmente a Steven Phelps por su ayuda con este artículo.

Eric Rykwalder es ingeniero de software y ONE de Cadena.comLos fundadores de.