Criptografía de curva elíptica
Autor: Graytrain, 29 junio de 2018
Artículo original: Elliptic-Curve Cryptography
Este no es un tema fácil, pero tiene una amplia gama de aplicaciones y, por lo tanto, vale la pena esforzarse para entenderlo. Ha permitido una reducción en el tiempo de generación de claves y el peso de claves sobre los sistemas de claves públicas de primera generación, como la criptografía prime factorization, así como un aumento de 10 veces en la seguridad y sirve como base a gran parte de la criptografía de clave pública en el ecosistema de criptomonedas actual . Así que vamos a desglosarlo para que podamos confiar en él.
Hola Alice, pásame la llave.
Primero, retrocedamos. Supongamos que deseas enviar un mensaje a alguien y no deseas que nadie lo lea excepto esa persona. Así que lo “encriptas” de alguna manera para que alguien no pueda leerlo a menos que sepa cómo “desencriptarlo”. Esto se puede hacer con un simple revoltijo o desplazamiento de las letras de una manera conocida. Una de las encriptaciones más antiguas conocidas es el Cifrado de César, hace exactamente eso. Al cambiar las letras un número de lugares X, las palabras en el mensaje se vuelven ilegibles [Fig.1]. Una vez que se comunica X, la mezcla de letras se puede cambiar para descifrar el mensaje.
Hay dos problemas importantes con este método. Primero, debes decirle de alguna manera a la persona con la que deseas comunicarte, la clave secreta para descifrar el código y confiar en que lo mantendrá a salvo. Y segundo, en esta era de las computadoras, esto no es muy difícil de romper.
Podríamos idear otro esquema para encriptar los datos, como usar una página específica en un libro como cifrado, pero en cada caso que se me ocurra, necesitamos una forma segura de comunicarle la clave a otra persona. ¿Cómo se haría esto si estuviéramos lejos? ¿Comunicarse a través de un formato digital o confiar en un tercero para compartir el secreto? Tenemos que encontrar otra manera.
Criptografía de clave pública
Llega la criptografía de clave pública (o asimétrica). Iniciada por Whit Diffie y Martin Hellman a fines de la década de 1970, la criptografía de clave pública utiliza pares de claves; una pública, que puede ser conocida por todos, y una privada, que se mantiene en secreto. Este sistema permite a cualquiera encriptar un mensaje usando la clave pública del receptor y ese mensaje sólo puede ser descifrado con la clave privada del receptor.
Una llave pública es una llave que puede cerrar la puerta pero no puede abrirla.
Este paso revolucionario resolvió el problema de tener que compartir un secreto para descifrar el mensaje y también permitió la autenticación de mensajes cifrados por el propietario de una clave pública.
Estos pares de claves se basan en “Trapdoor Functions”, que son fáciles de calcular en una dirección pero mucho más difíciles de revertir. Basado en las matemáticas, la fuerza de estos pares de claves se basa en el esfuerzo computacional que tendría que gastarse para derivar la clave privada de la clave pública.
RSA
En uno de los primeros sistemas criptográficos de clave pública ampliamente utilizados, RSA (Rivest — Shamir — Adleman), confía en el hecho de que multiplicar grandes números juntos es fácil y factorizarlos es difícil.
Para crear un par de claves RSA (sin entrar en demasiados detalles), seleccionamos dos números primos grandes, los multiplicamos para obtener un valor máximo (max o MOD, que significa el número donde el reloj se restablece a 0), y seleccionamos uno de los primos para ser la clave pública, pub, y usar el otro número primo para derivar su clave privada, priv. Con estos tres números, alguien puede multiplicar su mensaje por pub, envolver cualquier número que supere el máximo, y el desorden de números correspondiente se puede multiplicar por priv para obtener los datos originales. Sé que suena abstracto pero así es como funciona (y si quieres verlo simplemente, echa un vistazo a los enlaces al final de este artículo). Es como si escondiera la manecilla de la hora en el reloj y girara la manecilla de los minutos varias veces para luego mostrártelo. Puedes ver que la manecilla indica 45 minutos, pero no sabes cuántas veces giró antes de terminar allí. Sólo yo lo sabría.
La conclusión es que usando estas matemáticas, puedes encontrar 2 números de tal manera que cuando multipliques un número por sí mismo varias veces y obtengas un número de aspecto aleatorio, podrás multiplicarlo nuevamente por sí mismo un número secreto de veces para obtener El número original de vuelta.
El único problema con esto es que el factoring es un problema muy popular y que no es tan difícil de hacer poco a poco. Con el avance de la velocidad computacional y la mayor eficiencia en los algoritmos de factorización, los números primos en la generación de pares de claves RSA tienen que crecer continuamente para superar la tecnología y mantener la seguridad. Por lo tanto, este sistema se ha vuelto insostenible y no aplicable para móviles o aparatos de baja potencia. Se tenía que encontrar otra función Trapdoor más robusta.
Curvas Elípticas
Este caso de uso de las matemáticas en el mundo real revitalizó la investigación en matemáticas más marginales en el esfuerzo por encontrar algo que revolucionara aún más la criptografía.
En 1985, Neal Koblitz y Victor Miller propusieron independientemente la criptografía basada en curvas elípticas.
Las curvas elípticas tienen algunas características curiosas que las hacen útiles. Se definen como una curva que es completamente suave (no singular) y una línea entre dos puntos en esta curva siempre se cruza con un tercer punto (proyectivo) [Fig. 2] Esto le permite saltar rápidamente alrededor de esta curva fácilmente (computacionalmente) y proponer un procedimiento que aparentemente no tiene relación con el punto de partida y es muy difícil revertir el camino que lo condujo allí.
En el uso criptográfico, se aplican las mismas ideas de encontrar dos números únicos (puntos en una curva bidimensional) que están relacionados y un techo máximo para envolver.
¿Cómo hacemos para obtener dos números que estén relacionados pero que nadie pueda decir? Bueno, usamos la propiedad proyectiva de la curva y dibujamos una línea tangente al punto de partida P, encontrando dónde interseca la curva en un segundo punto Pʹ. Luego voltee el eje y dibuje una línea desde ese nuevo punto (2•P) a través del punto inicial y encuentre el nuevo punto de intersección Pʹʹ. Luego voltee el eje y dibuje una línea desde ese nuevo punto (3 • P) a través del punto inicial y encuentre el nuevo punto de intersección Pʹʹʹ, etc. (esta operación matemática se llama multiplicación de puntos) [Fig. 3]
Hacemos esto n veces y terminamos con un punto en la curva, Q, que no tiene una relación obvia con el punto de partida y puede definirse como Q = n•P donde n es el número de iteraciones de multiplicación de puntos realizadas. Matemáticamente, esto funciona así: Q = P + P + P … n veces.
Entonces, si supieras la curva que usamos, el punto de partida P y el punto final Q, ¿podrías determinar n? Resulta que no hay un algoritmo conocido para hacer esto. No hay atajos para determinar cuántas veces se “punteó” P para llegar a Q. Básicamente, hay que seguir agregando P a sí mismo y contar cuántas veces tiene que hacerlo para llegar a Q (o al revés). Esto es bastante fácil con un n pequeño, pero ¿qué sucede cuando n crece? y quiero decir realmente grande …
Curvas Elípticas en Aplicación
La curva elíptica utilizada por Bitcoin, Ethereum y muchas otras es la curva secp256k1, con una ecuación de y² = x³ + 7 y se ve así:
Y tiene un punto de partida definido utilizado por toda generación de claves, P (x, y), con coordenadas x e y:
Coordenada x: 55066263022277343669578718895168534326250603453777594175500187360389116729240
Coordenada y:
32670510020758816978083085130507043184471273380659243275938904335757337482424
Como se puede ver con un punto de partida TAN grande, es muy posible tener un punto final más grande que el tamaño de clave permitido de 512 bits. Por lo tanto, debemos establecer un valor máximo que ajustemos para establecer un campo de puntos permitidos que se ajuste a nuestro tamaño de clave.
Para esta curva específica, el valor máximo (mod) está definido por un número primo (para producir un campo primo) de:
O
115792089237316195423570985008687907853269984665640564039457584007908834671663
O
115 quattuorvigintillion …
O
.12% de todos los átomos en el universo conocido.
aka muy grande
Como los valores negativos o no enteros son difíciles de usar en el cálculo, solo queremos usar los puntos enteros en la curva con valores negativos invertidos y usar el valor máximo definido para ajustar los valores de nuevo a 0 para evitar que los valores sean demasiado grandes. Terminamos con algo que se parece menos a una curva, pero más a un puñado aleatorio de puntos, aunque se pueda ver cierta simetría [Fig. 5]
Entonces, ahora con esta “curva” recién definida, hacemos la multiplicación de puntos desde nuestro nuevo punto de partida, envolvemos nuestro módulo de manera muy parecida a la manecilla de minutos que gira alrededor de un reloj, y después de n veces terminamos en el punto Q [o A•B = C como se muestra en la Fig. 6].
Dado que el número de puntos disponibles está relacionado linealmente con el tamaño del campo (número de puntos = Fᵖ+1), y dado que no hay una manera fácil de encontrar n dado P y Q, sólo hay que recorrer toda la lista, con 115792089237316195423570985008687907853269984665640564039457584007908834671663 –1 posibilidades de encontrarlo (siendo cada una tan posible como la otra). Por lo tanto, tiene sentido hacer que Q sea la clave pública y n la clave privada y todos usando la misma curva y punto de partida, P.
Entonces, al final, tu clave privada es solo un número entero grande y tu clave pública es un punto en la curva correspondiente a su punto de clave privada multiplicado por el punto de partida.
¿Cómo de “Seguro” es Seguro?
Tratemos de visualizar cómo de seguro es esto. Si la selección de n fuera realmente aleatoria, ¿cuánto tiempo le tomaría encontrar un n específico, o simplemente en general, cualquier “colisión” con otra clave privada en uso? Digamos que pudiera probar 250 mil millones de posibilidades por segundo, 5 veces la tasa actual del hash de la red de Bitcoin, todavía tomaría 1⁰¹⁰ veces la edad del universo para encontrar una coincidencia. Básicamente, cualquier otra cosa que ocurra es más probable que encontrar una coincidencia.
Se han realizado algunas investigaciones para establecer formas de medir la seguridad de estos tipos de cifrado. En estas escalas, el ECC en la curva y el campo definido arriba se considera “Globalmente Seguro”, lo que significa que la energía que una computadora, o grupo de computadoras, tendría que usar para encontrar un n específico sería suficiente energía para hervir 1,400,000,000 km³ de agua, que es casi toda el agua en la superficie de la tierra. Eso es probablemente lo suficientemente seguro.
¿Cómo se aplica esto a las direcciones que vemos hoy en día?
Obviamente, las formas en que estamos acostumbrados a ver direcciones, ya que son cadenas grandes de números y letras, son diferentes de un número y puntos en una curva. Esto se debe a que se hace el hash de tal forma que se reduce el tamaño de la cadena de caracteres para facilitar su uso. En Bitcoin, las coordenadas de Q se combinan y pasan por una cascada de algoritmos de hash diseñados para comprimir la clave y añadir una suma de verificación de validez para la verificación de direcciones [Fig. 7].
Entonces, con suerte, después de todo eso, ahora comprendes un poco mejor las ideas detrás de la criptografía de curva elíptica y puedes confiar en la seguridad de tus criptomonedas y comunicaciones privadas a las estadísticas de números cósmicamente grandes.
Si deseas ver esta explicación con más detalle con algunos ejemplos de cifrado, consulta los enlaces a continuación que sirvieron de inspiración para este artículo.
