ECDSA

14 febrero 201726 mayo 2017

Jaime Núñez Miller, socio fundador de Bankabit y de Zentank, veterano de la comunidad Bitcoin y responsable del capítulo 9 del libro (“Criptografía y consenso aplicado a la blockchain”), firma el presente anexo donde incide en otras cuestiones importantes que sirven para ampliar nuestros conocimientos sobre las claves y los secretos de la criptografía y su aplicación en la tecnología blockchain.

***

ECDSA (Elliptic Curve Digital Secure Algorithm)

Como citamos ya en el libro, el ECDSA se trata de un algoritmo que nos permitirá calcular un número (clave pública) a partir de otro número aleatorio (clave privada). La clave pública la debemos poder compartir con la garantía de que nadie podrá obtener nuestra clave privada a partir de la pública.

Nuestro sistema de curva elíptica calculará las coordenadas de un punto en una curva. Ese punto será nuestra clave privada k y se obtiene como resultado de una operación de multiplicación de curva elíptica entre un punto base (G) y nuestra clave privada (k).

G * k = K

 

Operaciones de curva elíptica

Las curvas elípticas tienen ciertas características que las hacen especiales en el mundo de la criptografía. Una de estas características consiste en la posibilidad de poder generar un punto en una curva partiendo de dos puntos dados (o incluso de uno). Este concepto es muy fácil de entender con la figura siguiente.

curvas elípticas

Suma puntos en la curva.

 

Partiendo de dos puntos (los llamaremos P y Q) trazamos una recta que se cruzará (no siempre) con la curva en un punto al que llamaremos -R. Para obtener la suma de P+Q bastará con reflejar el punto -R sobre el eje X y así llegar el punto R que será la suma geométrica de P+Q.

P+Q=R

En el caso de que la recta no cortara la curva en ningún otro punto y se perdiera en el infinito  diremos que corta la curva en el infinito, al que llamaremos punto del infinito O.  En este caso la suma sería

P+Q=O

Recordemos que trabajamos con coordenadas. Veamos un ejemplo utilizando solo una curva elíptica ya pintada en un papel, sin recurrir a fórmulas aritméticas. Si nos dan dos puntos cualesquiera en la curva, P y Q, por ejemplo (-2.0, 1.4) y (0.2, 1.7) nos bastaría una regla para trazar una recta y obtener el punto -R. Luego reflejamos -R sobre el eje X y sacamos las coordenadas de R tal y como vemos en la siguiente ilustración.

El resultado R es en este caso (1.7, -2.0)

El resultado R es en este caso (1.7, -2.0)

pero antes hay que resolver un par de situaciones conflictivas.

En primer lugar ¿qué pasaría en el caso de que P y Q fueran el mismo punto?. En ese supuesto no podríamos trazar una recta para obtener R. La solución es utilizar la tangente del punto P para obtener la recta que necesitamos. Veamos una ilustración.

ilustracion

 

Si utilizamos por ejemplo el punto P (-1.1, 2.4) que sería en este caso el mismo que el punto Q, solo tendríamos que trazar la tangente de P para obtener -R y luego llegar a R. Hasta ahora todo muy sencillo. Miramos el gráfico y deducimos que R está en (2.4, -3.3).

Hasta ahora sólo hemos utilizado la geometría (una curva, un lápiz y una regla) para hacer la suma.  Ahora vamos a ver cuál es la fórmula aritmética para obtener R a partir de P y Q.

Dados (x1, y1), (x2, y2) debemos hallar (x3,y3) = (x1, y1), (x2, y2)

formulas

 

Multiplicar puntos. Doblar y sumar.

Este sería el cálculo de R con la suma de P y Q cuando P y Q son distintos, y cuando ambos son mismo punto:

P + Q = R

P + P = 2P = R

y este sería si utilizáramos más de dos puntos iguales para obtener R, por ejemplo, n puntos:

P + P + P + P + P + … + P = nP

Veamos un ejemplo con n = 5. Una forma de hacerlo sería esta:

2  * P = 2P

2P + P = 3P

3P + P = 4P

4P + P = 5P

Si usamos 2 como multiplicador podríamos hacerlo en solo tres pasos:

2  *  P = 2P

2  * 2P = 4P

4P +  P = 5P

A este algoritmo que acelera la multiplicación le llamaremos “doblar y sumar” o multiplicación escalar y nos permite llegar al resultado final 5P con menos pasos. Si el número n fuera mucho mayor podríamos incrementar el multiplicador y el cálculo se realizaría exponencialmente más rápido. Bitcoin utiliza números de 1077 cifras o 256 bits que pueden requerir cerca de 250 pasos. Este sistema es una de las bases para muchos algoritmos de clave pública, no solo ECDSA.

Campos finitos

Ahora que sabemos sumar y multiplicar puntos en una curva elíptica vamos a ver otro problema que debemos resolver. Las fórmulas aritméticas nos dan resultados con decimales. Algunos decimales son irracionales y no terminan nunca, por ejemplo 3,14159265358… etc.  y nuestros ordenadores no disponen de espacio infinito para almacenar este tipo de números. Por supuesto que nuestras computadoras pueden hacer aproximaciones, pero si les preguntáramos si es cierto que 1,9999 = 2 no sabrían qué responder. Para solucionar esto usaremos sólo los puntos de la curva que se puedan representar con números enteros, sin decimales.

Acabamos de establecer qué tipo de elementos forman parte de nuestro campo. Si nuestro campo fuera una mesa de billar, sería como definir qué características deben de tener las bolas con las que queremos jugar. En este ejemplo, nuestras bolas de billar se llaman números enteros. Sin duda es algo que van a agradecer mucho nuestros ordenadores.

Ahora ya sólo nos quedaría definir el tamaño de nuestra particular mesa de billar y los bordes de la mesa en donde rebotan las bolas de forma que aunque peguen fuerte, la bola siempre quede dentro de la mesa. Os podéis imaginar que a nuestro ordenador tampoco le gusta jugar en mesas de billar infinitas así que nos valdremos de un concepto matemático llamado aritmética modular.

Si eres capaz de leer las horas de un reloj digital ya entiendes algo de aritmética modular. Si fueran las 11 de la noche (23:00 h) y te tuvieras que despertar en 8 horas, pondrías la alarma de tu despertador a las 07:00 h y no a las 31:00 h. Cuando la hora llega a las 24:00 se reinicia el contador y se empieza a contar a partir de 00:00. Ese reloj estaría contando en módulo 24 o  (mod 24). El 24 es el número máximo.

El cálculo en nuestro despertador es el siguiente

23h + 8h = 31h

31 7 mod 24

lo que se lee de la siguiente forma: “31 es congruente con 7, cuando estamos en módulo 24”

En el caso del estándar de curva elíptica secp256k1 utilizado por Bitcoin el cuerpo finito son todos los números enteros en donde el límite de elementos es un número primo enorme, concretamente

p=115792089210356248762697446949407573530086143415290314195533631308867097853951

La razón de elegir este número es que es primo, su longitud es de 256 bits y su expresión binaria tiene 127 ceros y 129 unos, lo que facilita los cómputos.

Anteriormente vimos que a curva elíptica usada por Bitcoin era del tipo  y2 = x3 + 7. Ahora ya podemos avanzar un poco más y definir la curva elíptica en un campo finito (F) de números enteros, módulo p. En donde p es el número primo de enormes dimensiones que hemos visto.

y2 = x3 + 7 sobre (Fp)

Las curvas elípticas definidas sobre cuerpos finitos en donde el límite p es un número primo grande, como es nuestro caso, son de gran interés criptográfico debido a la dificultad que tiene el problema del logaritmo discreto cuando se plantea sobre este tipo de cuerpos.

Las multiplicaciones escalares necesarias para obtener el punto que representa la clave pública siguen siendo fáciles, mientras que el logaritmo discreto se convierte en un problema difícil, que es la propiedad que se busca en una función de clave pública unidireccional.

 

Calcular la clave pública

Al representar nuestras curvas elípticas en cuerpos finitos, el gráfico de la curva no queda tan elegante. Recordemos que en el cuerpo finito Fp ya no contamos con decimales, por lo que el gráfico se parece ahora más a una ensalada de puntos inconexos que a una curva, sin embargo esa ensalada conserva las mismas propiedades aritméticas que la curva.  

Si queremos enumerar los puntos de la curva debemos proponer un punto inicial. A ese punto le llamamos “punto base” que representamos aquí con la letra G. Los puntos de la curva se irán añadiendo a la gráfica a medida que multiplicamos G por cada número entero hasta llegar al límite máximo de nuestro campo finito. Por ejemplo, los puntos en una curva elíptica módulo 29 (cuyo límite es 29) se muestran en la siguiente ilustración que contiene cada uno de sus 29 puntos.

1*G = (0,2)
2*G = (6,17)
3*G = (22,1)
………                                            puntos

28*G = (22,28)
29*G = (6,12)
30*G = (0,27)
Aquí podemos ver todos los puntos de la curva porque el módulo es muy pequeño, pero sería imposible visualizarlos al completo cuando usamos límites mucho mayores como en el caso de Bitcoin.

La clave privada k será un número entero elegido al azar entre los que forman parte del grupo o cuerpo finito que hemos definido, en nuestro caso un número entre 1 y p-1 en donde p es el número primo visto anteriormente. La clave pública es el punto K que se obtiene al multiplicar la clave privada k por el punto base G.

k * G = K

Clave privada * Punto base = Clave pública

Recordemos que el punto base G (también llamado generator point) es siempre el mismo punto para todas las claves y viene dado por la especificación secp256k1 usada en el protocolo Bitcoin. Así pues se trata de multiplicar un punto en la curva elíptica, o sumar k veces el punto base G en la curva aplicando el procedimiento de suma de puntos visto al inicio. El punto base sería el punto P en esa primera curva elegante, la que usaba números reales en vez de números enteros. El proceso sería el siguiente:

  1. Trazamos la tangente de G (que es el punto P).
  2. El punto donde corta la curva es en punto -2G que reflejamos sobre el eje X para llegar al punto 2G.
  3. Trazamos la tangente de 2G
  4. El punto donde corta la curva es en punto -4G que reflejamos sobre el eje X para llegar al punto 4G.
  5. Trazamos la tangente de 4G
  6. El punto donde corta la curva es en punto -8G que reflejamos sobre el eje X para llegar al punto 8G.

Repetimos el proceso hasta llegar a kG y obtener las coordenadas de K (kG = K). Lo visualizamos en una curva de números reales en vez de enteros, para verlo mejor.

numeros enteros

 

De este sistema se puede remarcar lo siguiente:

  • Si la clave privada es muy larga será fácil calcular su clave pública usando el sistema de multiplicación que vimos más arriba, pero muy difícil de revertir mediante fuerza bruta.
  • A diferencia de la clave pública, la clave privada es sólo un número sobre el que podemos realizar cálculos matemáticos normales.
  • La clave pública en cambio es un punto en una curva elíptica sobre el que sólo se pueden realizar operaciones de suma y multiplicación como hemos visto. Los puntos no se pueden dividir.