Fundamentos de la Teoría de Números aplicados a la Firma Criptográfica ECDSA usada por el Protocolo Bitcoin

La Criptografía Asimétrica es la base de la seguridad de muchos sistemas informáticos en la actualidad, el protocolo Bitcoin utiliza la Criptografía de Curva Elíptica (ECDSA) la cual se sustenta en un par de claves, clave privada y clave pública, que básicamente son números, la clave privada corresponde a un número que permite gastar los fondos mientras que la clave pública es un número en base al cual se genera la dirección a la que se envían los fondos. La clave pública puede ser generada a partir de la clave privada de forma fácil mientras que el proceso inverso es imposible de realizar con la potencia computacional existente en la actualidad.

El proceso mediante el cual se genera la clave pública a partir de la clave privada se conoce como multiplicación de curva elíptica. En un artículo anterior explique al detalle este proceso de generación de clave privada/clave pública, sin embargo, surge la interrogante ¿cómo se asegura el protocolo Bitcoin de que el usuario que firma una transacción es el propietario de la clave privada sin necesidad de que el propietario tenga que compartir su clave privada?

Para explicar este punto primero se hará un repaso de aritmética modular y del proceso de multiplicación de curva elíptica resumiendo lo abordado en un artículo anterior, estos conceptos servirán de base para entender el proceso de firma criptográfica.

Aritmética Modular o Aritmética de Reloj

La aritmética modular consiste en realizar la adición o multiplicación de dos o más números de forma similar a la adición y multiplicación en el conjunto de números enteros y luego calcular el residuo al dividir entre un número entero llamado módulo (denotado por p), por ejemplo:

6 + 10 = 3 (módulo 13) debido a que 6 + 10 = 16 16/13 es 1, y el residuo es 3
9 + 11 = 7 (módulo 13)
8 * 10 = 2 (módulo 13) debido a que 8 * 10 = 80 80/13 es 6 y el residuo es 2
5 * 5 = 4 (módulo 7)

El conjunto de los enteros módulo p también denotado por F_p consiste en todos los números enteros desde 0 hasta p−1 con las operaciones de adición y multiplicación basadas en la aritmética modular (módulo p) también conocida como “aritmética del reloj”.

Curvas elípticas en cuerpos de enteros módulo p

En general, una curva elíptica en F_p , es una función definida de la siguiente forma

y2 = x3+ax+b (módulo p) tal que x,y,a y b pertenecen a Fp

Cada punto de la curva elíptica satisface la ecuación anterior, en el caso de Bitcoin la curva elíptica usada se define específicamente en el estándar secp256k1 de la siguiente forma:

y2 = x3+7 (módulo p)

Donde p es igual a

p = 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴-1

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Con el objetivo de simplificar los cálculos en el presente artículo se mostrará un ejemplo del proceso de firma criptográfica ECDSA utilizando un valor de p menor (en este caso 23) para comprender los fundamentos matemáticos de esta criptografía.

Dados los punto de la curva elíptica

y2 = x3+7 (módulo 23)

Y un punto adicional llamado “punto al infinito” (0,0), el cual no satisface la ecuación de la curva se forma un grupo abeliano, la operación de adición de puntos se define de la siguiente manera:

Tres puntos en una curva elíptica están alineados si su suma da cero P₁ + P₂ + P₃ = (0,0), es decir, P₁ + P₂ = - P₃ donde - P₃ corresponde al punto simétrico a P₃, adicionalmente se puede decir que tres punto en F_p están alineados si existe una línea recta que los una, sin embargo, las líneas rectas en F_p no son iguales a las líneas rectas en los números reales.

Una línea recta en F_p es el conjunto de puntos (x,y) que satisfacen la ecuación

y = ax + b (módulo p)

Que es la misma ecuación para los números reales pero aplicando aritmética modular, por ejemplo en F₂₃ los puntos (1,10) y (6,4) están alineados en la recta

y = 8x+2 (módulo 23)

Probando con los otros puntos de F₂₃ se demuestra que el tercer punto alineado en dicha recta es (11,21), por lo tanto el resultado de la adición es el simétrico de (11,21), es decir, (11,2) en caso de que se sume un punto P₁ con el mismo, como no puede trazarse una línea recta entre ambos puntos, la línea recta se extiende para ser la tangente sobre la curva en P₁, esta tangente intersectará a la curva en un punto, el simétrico de dicho punto es el resultado de la adición.

Propiedades de la adición de puntos

P1 + 0 = 0 + P1 = P1
P1 + ( - P1) = 0 un punto más su simétrico es igual al punto al infinito

Las ecuaciones para calcular la suma de dos puntos son las siguientes, dados P₁ = (x₁, y₁) y P₂=(x₂,y₂) su suma es igual a P₃ =(x₃,y₃)

x3 = m2 - x1 - x2 (módulo p)
y3 = m * (x1 - x3 ) - y1 (módulo p)

Donde

m = (y2 - y1 ) * (x2 - x1)-1 (módulo p) si P1 ≠ P2
m = (3 * x12 ) * (2 * y1)-1 ( módulo p) si P1 = P2

La demostración del porque se usan estas formula escapa al alcance de este artículo. Ahora se define la multiplicación escalar dentro de la curva elíptica de la siguiente forma

n * P1 = (P1 + P1 + ⋯ + P1) n veces

Donde n es un número entero menor que p, por ejemplo en F₂₃ si se define la curva elíptica y² = x³+7 (módulo 23) se obtendría la siguiente representación gráfica

Luego si en la curva anterior se define el punto P₁ = (1,10) como punto de partida y se multiplica dicho punto por un escalar n se obtendrían los siguientes puntos dependiendo del valor de n

Como se puede observar al multiplicar por diferentes valores escalares tomando (1,10) como punto generador se obtiene un subgrupo cíclico compuesto por 24 elementos que se repiten continuamente.

En el caso de la curva elíptica de bitcoin el punto generador G es el siguiente

X=55066263022277343669578718895168534326250603453777594175500187360389116729240
Y=32670510020758816978083085130507043184471273380659243275938904335757337482424

El punto obtenido al multiplicar el punto generador G por la clave privada es la clave pública la cual se suele representar en dos formatos diferentes, comprimida y descomprimida.

A continuación se presenta un ejemplo de la firma criptográfica ECDSA para la curva mostrada anteriormente.

y2 = x3+7 (módulo 23)

La cual es la misma curva con la que trabaja el protocolo de Bitcoin pero cambiando el valor del módulo para simplificar los cálculos, en la curva anterior si se selecciona el número d=20 como clave privada se puede apreciar en la tabla N° 1 que la clave pública correspondiente sería el punto Q = (11,21).

Proceso de Firma Criptográfica ECDSA

1- Se selecciona el mensaje a firmar M en el caso de Bitcoin se corresponde al SHA-256 de cierta información de la transacción en formato hexadecimal, la Curva Elíptica E de orden n (el orden es el número de puntos) y el punto Generador G.

En este artículo se usará como ejemplo de mensaje el número 17, la curva elíptica

y2 = x3+7 (módulo 23)

El punto generador será G= (1,10) esta curva posee 24 puntos por lo tanto su orden es n=24

2- Se selecciona un número aleatorio k entre 1 y n, por ejemplo el número 13.

3- Se calcula k * G, obteniéndose el punto (x₁,y₁), en este caso sería

13 * (1,10) = (16,3) ver Tabla N°1

4- Se calcula R = x₁ mod n, si R = 0 se regresa al primer paso (x₁ es tratado como un entero en aritmética modular)

R = 16 mod 24 = 16

5- Se calcula k^-1 mod n (mediante el Algoritmo de Euclides Extendido) en este caso

13 mod 24 = 13 lo cual es cierto debido a que 13 * 13 = 1 (mod 24)

6- Se calcula S = k^-1 * ( M + d * R) mod n si S = 0 regresar al primer paso

S = 13 * (17 + 20 * 16) (mod 24)
S = 13 * 1 (mod 24)
S = 13

7- La firma del mensaje son los números (R, S).

(16,13)


Proceso de verificación de la Firma Criptográfica ECDSA

El proceso de verificación de la firma se realiza de la siguiente manera

1- Se verifica que R y S estén entre 1 y n-1

16 y 13 son menores que 24, por lo tanto el paso 1 se cumple

2- Se calcula W = S^-1 (mod n)

W = 13-1 (mod 24)
W = 13 lo cual es cierto debido a que 13 * 13 = 1 (mod 24)

3- Se calcula U₁ = M * W (mod n)

U1 = 17 * 13 (mod 24) = 5

4- Se calcula U₂= R * W (mod n)

U2 = 16 * 13 (mod 24) = 16

5- Se calcula el punto U₁ * G + U₂ * Q = (x0,y0)

5 * G + 16 * Q = (19,9) + 16 * (11,21)
(19,9) + (4,18)
(16,3)

6- Se calcula V = x₀ mod n

V = 16 mod 24 = 16

7- La firma verifica si y solo si V = R, lo cual se cumple debido a que

16 = 16


Por lo tanto la firma criptografica ECDSA del mensaje es válida, se puede apreciar que la firma pudo ser verificada sin necesidad de dar a conocer la clave privada, solamente con la clave pública.