Poco a poco la criptografía como la conocemos está desapareciendo, he hablado con
Tanja Lange un par de veces en los congresos que hace la sociedad matemática holandesa y ella parece insistir mucho que estamos ya muy cerca presenciar la existencia de una computadora cuántica, ella afirma que entre el 2024-2030 ya existirá alguna.
Lo relevante es que toda la criptografía actual implementada en los ámbitos económicos, militares y gubernamentales, cuenta con seguridad extrema ante computo clásico como lo conocemos (modelos Von Neumann, Turing...) . El problema es que el modelo de cómputo cuántico rompe todos los algoritmos implementados hoy en día. Esto es debido a la existencia de un algoritmo por
Peter Shor que factoriza y calcula logaritmos discretos, es decir, rompe RSA y criptografía basada en el problema de logaritmo discreto (Curvas elípticas) en tiempo polinomial. Esto significará que todos seríamos vulnerables ante el individuo/organización que construya computadora cuántica (IBM, DWave, Google por ejemplo).
Por lo que, las curvas elípticas e hiperelípticas como las implementamos hoy en día, comienzan a ser obsoletas en criptografía, aunque siguen siendo muy útiles para computación en teoría de números algebraica que sirve para hacer nuevos algoritmos, es decir, no estoy diciendo que ya no sirvan las curvas, sino que la criptografía que usa el problema de logaritmo discreto con curvas o variedades abelianas está vulnerado ante la presencia de una computadora cuántica.
En este post les voy a mostrar un análogo de Diffie Hellman que no es vulnerable ante la presencia de un atacante con recursos cuánticos. El post es autocontenido, sólo requieres saber la teoría básica de curvas elípticas la cual la puedes leer en mi blog, recomiendo (aunque no es obligatorio ya que trato de hacerlo autocontenido leer estos artículos aquí en mi blog antes)
Teorema de Hasse en curvas elípticas
Álgebras de endomorfismos en curvas elípticas
j-Invariante en curvas elípticas
El método de Diffie Hellman que funciona bajo cómputo cuántico que describiremos aquí necesita conocimiento de morfismos entre curvas elípticas (isogenias u homomorfismos de los grupos abelianos inducidos por las curvas).
El contenido de este post es el siguiente:
* Background en isogenias y kérneles de éstas antes de irse a lo cuántico.
* Grado de una isogenia
* p-Torsión, j-invariante y características de curvas elípticas súpersingulares
* Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.
* Algoritmo explítico Diffie Hellman con isogenias entre curvas elípticas supersingulares.
* ¿Pero por qué nos enfocamos en súpersingulares?
* ¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis?
Todo esto que escribo fue gracias a la emoción que me causaron las pláticas de Dimitar Jetchev (EPFL, Lausanne, Suiza), Frederik Vercauteren (KU Leuven, Bélgica), Benjamin Smith (INRIA, Francia) y René Schoof (Università di Roma, Italia) en el workshop "Mathematical structures for cryptography" el cual tuve la suerte de poder trabajar con grandes matemáticos del 22-26 de Agosto en Leiden, Países Bajos cuyo objetivo era juntar investigadores en matemáticas y criptografía para resolver problemas abiertos en esta teoría así como la basada en retículas para cómputo cuántico (Lattice Based Cryptography), todos los participantes aportamos algo interesante, y fue una de las más grandes experiencias profesionales que he tenido, aquí hay más información de la gente involucrada
http://www.lorentzcenter.nl/lc/web/2016/834/participants.php3?wsid=834&venue=Oort
Comenzamos.
Background en isogenias y kérneles de éstas antes de irse a lo cuántico.
Sea $latex E$ una curva elíptica en forma de Weierstrass sobre un campo finito $latex \mathbb{F}_q$ , es decir $latex E:=\lbrace (x,y)\in \mathbb{F}_q\times\mathbb{F}_q : y^2 = x^3 + ax + b \rbrace$.
Como he explicado en
posts anteriores, las curvas elípticas forman un grupo abeliano, es decir, $latex \langle E,\oplus\rangle$ es una estructura donde los puntos se pueden "sumar y restar" , es conmutativa, todos tienen inverso aditivo, es asociativa, cerrada y con elemento neutro $latex \infty$.
Hay fórmulas explícitas para calcular la suma de puntos como en el post anterior mencionado en el párrafo anterior, y también están muy bien explicadas en
wikipedia, así que supondré que ya sabemos como funciona la adición elíptica que geométricamente la intuición es con la siguiente imagen:
Isogenias entre curvas
(mapeos de curvas elípticas, homomorfismos de grupos abelianos inducidos)
Tenemos que si $latex \langle E_1, \oplus\rangle ,\langle E_2,\boxplus \rangle$ son dos curvas elípticas y existe un morfismo $latex \psi:E_1\to E_2$ que respeta la estructura de grupo de cada una, es decir $latex \psi(P\oplus Q)= \phi(P)\boxplus \phi(Q)$ y que mapea el $latex 0$ de una al $latex 0$ de la otra, entonces decimos que ambas son
isógenas.
Ahora vamos a ver qué son esos ceros en la curva, ya que no es trivial desde el punto de vista afín.
Kérnel de isogenias
En curvas elípticas tenemos que una isogenia entre dos curvas se ve como $latex \psi(x,y) := (\frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} )$ donde más técnicamente es porque $latex \frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} \in \mathbb{F}_q(E_2)$ es decir son funciones bien definidas en los puntos de la curva en el codominio, son funciones de su campo de funciones (campo de fracciones de la gavilla de funciones del la curva vista como esquema).
Para entender el kérnel de un mapeo como el anterior, necesitamos ver la curva de manera proyectiva, ya que el 0 (cero) en $latex E_1$ y $latex E_2$ no es un punto afín.
Si $latex \psi:E_1\to E_2$ es una isogenia entre curvas elípticas, el kérnel está definido como:
$latex ker\psi := \lbrace P\in E_1 : \psi(P) = \infty_{E_2}\rbrace$
Es decir, todos los puntos que nos mandan al infinito.
Recuerden que las curvas son proyectivas, entonces lo que esto significa exactamente es que si la isogenia está definida por $latex (\frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)})$ entonces podemos proyectivizar estas ecuaciones con una nueva variable $latex z$ (cerradura proyectiva), los puntos que el mapeo manda al infinito veremos a continuación que son justamente donde no están definidas esas funciones racionales sin proyectivizar.
Informalmente pero no incorrectamente, definir la imagen de estos puntos "no definidos bajo $latex \phi$" como $latex \infty_{E_2}$ se hace, deshaciéndose de los denominadores en la isogenia y homogeneizando, eso será la isogenia vista en la cerradura proyectiva de la curva que es $latex zy^2 = x^3 + az^2x + bz^3$ .
Entonces tendremos que los puntos afines de la cerradura proyectiva de la curva están dados por los puntos $latex (x:y:1)$ , es decir, la imagen afín de $latex \psi$ es $latex (\frac{a_1(x)}{a_2(x)}:y\frac{b_1(x)}{b_2(x)}:1)$ , por lo que entonces la ecuación proyectiva es: $latex (a_1(x)b_2(x):yb_1(x)a_2(x):a_2(x)b_2(x))$ , y todos los puntos $latex (x:y:1)$ donde no está definida la curva afín, justamente estarán bien definidos aquí proyectivamente y esos puntos, son los que tienen imagen al infinito , es decir, que tienen como imagen el punto $latex \infty := (0:1:0)$, y son los puntos en el $latex ker\psi$ incluyendo al $latex \infty_{E_1}$ ya que es requisito de una isogenia mapear infinitos.
Pueden ustedes demostrar de hecho que $latex ker\psi := \lbrace (x,y)\in E_1 : a_2(x)=0\rbrace$ con el hint de que $latex a_2^3 \mid b_2^2$ siempre, y así como que $latex b_2^2\mid f_1a_1^3$ donde $latex f_1$ es la ecuación que define a $latex E_1$ en $latex y^2 = x^3 + a_1x + b_1$, recuerden que esto lo demuestran en el campo de funciones de la curva, es decir tienen que tomar en cuenta la ecuación de la curva al momento de demostrar esto.
Teorema: Si
dos curvas elípticas son isógenas sobre un campo finito, entonces tienen el mismo número de puntos.
Grado de una isogenia
Antes de demostrar el teorema, necesitamos entender qué es el grado de una isogenia.
Sea $latex \psi:E_1\to E_2$ una isogenia definida sobre un campo finito $latex \mathbb{F}_q$.
Decimos que el mapeo $latex \psi$ es separable si la extensión de los campos inducida por $latex \mathbb{\psi}$ es separable.
Es decir si $latex \mathbb{F}(E_1)/\psi^{*}\mathbb{F}_q(E_1)$ es separable, y su dimensión como espacio vectorial la usamos para definir:
$latex \text{grad}\psi := dim_{\mathbb{F}_q}(\mathbb{F}_q(E_1)/\psi^{*}\mathbb{F}_q(E_1))=[\mathbb{F}(E_1):\psi^{*}\mathbb{F}_q(E_1)]$
Si esta extensión de campos inducida por $latex \psi$ es separable, decimos que es $latex \psi$ es separable, y una propiedad de isogenias separables es que $latex \text{grad}\psi :=$#$latex ker\psi$.
Pero
que no cunda el pánico, vamos a ver cómo encontrar este grado sin meternos en la teoría dura, esto sólo es para definir algo (grado) y luego ver que su cálculo se puede hacer sin tener que calcular bases de espacios vectoriales.
Es fácil demostrar que el grado de la extensión de campos se mide siempre de una manera inocente contando el número de elementos en la imagen inversa de cualquier punto (sin ramificación) en el codominio.
O sea si el grado de $latex \psi$ fuera 1, significa que los espacios vectoriales inducidos por $latex \psi$ son los mismos, por lo que la imagen inversa de cualquier punto tiene sólo 1 punto ya que en este caso $latex \psi$ sería un isomorfismo.
El grado mide qué tan "complejo" es $latex \psi$ , por lo que de hecho el grado de una isogenia está definido también por la cantidad de elementos en la imágen inversa de $latex \psi$ para un punto ordinario general, es decir de $latex \psi^{-1}(Q_{E_2})$ donde $latex Q_{E_2}\in E_2$ es un punto ordinario, es decir no presenta ramificación (Por ejemplo un punto $latex (x,y)$ cuya coordenada $latex x$ no sea raíz de $latex x^3 + ax + b$ , ya que estos puntos son de ramificación, pero no entraremos en eso por ahora).
Como $latex \psi$ es un homomorfismos, tenemos que #$latex \psi^{-1}(Q_{E_2}) =$#$latex ker\psi$, por lo que tenemos otra igualdad más.
De tarea ustedes entonces dicho lo anterior pueden probar que $latex \text{grad}\psi$ es fácilmente calculable ya que si $latex P\in E_1$ y $latex Q:=\psi(P)$ es un punto con coordenadas $latex (s,t)$ en $latex E_2$ entonces #$latex \psi^{-1}(Q)$ es exactamente el número de ceros diferentes del polinomio $latex a_1(x)-sa_2(x)$ pero como $latex \psi$ es separable entonces este polinomio no tendrá raíces repetidas, por lo que #$latex \text{grad}\psi = \text{Deg}(a_1(x)-sa_2(x))=$#$latex ker\psi$.
Demostración de teorema
Dicho todo esto, considera el mapeo $latex \phi_1\in End_{\mathbb{F}_q}(E_1)$ y $latex \phi_2\in End_{\mathbb{F}_q}(E_2)$ tal que si $latex (x_i,y_i) \in E_i$ entonces $latex \phi_i(x_i,y_i) = (x_i^q, y_i^q)$ .
Es decir son los endomorfismos de Frobenius de cada una de las curvas.
Recuerden que queremos demostrar que dos curvas $latex E_1,E_2$ isógenas sobre $latex \mathbb{F}_q$ tienen el mismo números de puntos, y tenemos que la isogenia es $latex \psi:E_1\to E_2$.
Es fácil ver que $latex \psi\circ \phi_1 = \phi_2\circ \psi$, ya que si $latex P:=(x_1,y_1)\in E_1$ y $latex (x_2,y_2):=\phi(P)$ entonces $latex \psi(\phi_1(P)) = \psi(x_1^q,y_1^q)$ y en el otro lado $latex \phi_2(\psi(P)) = \phi_2(x_2,y_2)=(x_2^q,y_2^q)$.
Es decir, en el párrafo anterior afirmo que $latex (x_2^q,y_2^q) = \psi(x_1^q,y_1^q)$, ya que recuerden que $latex \psi$ está formada por funciones racionales en $latex x$ y en $latex y$, entonces es un ejercicio de álgebra básica demostrar que si $latex r(x)$ es un polinomio sobre un campo finito entonces $latex r^q(x)=r(x^q)$, es decir se cumple el sueño de todo niño de secundaria, que por ejemplo si $latex x+y\in \mathbb{F}_q(x,y)$ entonces $latex \phi(x+y)=(x+y)^q = x^q + y^q$.
Entonces con toda mi informalidad que me caracteriza, tenemos ya que $latex \psi\circ \phi_1 = \phi_2\circ \psi$
Por lo que como la operación $latex \circ$ de composición en $latex End_{\mathbb{F}_q}(E_i)$ es distributiva, podemos inferir que:
$latex \psi\circ (\mathbbm{1}_{E_1} - \phi_1) = (\mathbbm{1}_{E_2}- \phi_2)\circ \psi$
(*)
Tal que $latex \mathbbm{1}_{E_i}$ es el mapeo de identidad en $latex End_{\mathbb{F}_q}(E_i)$ .
Calculemos el grado de
(*) .
Sabemos que el $latex \text{grad}\psi_1\circ \psi_2 = \text{grad}\psi_1\cdot \text{grad}\psi_2$ , esto lo pueden demostrar usando mi demostración anterior de que el grado de una isogenia está directamente relacionado con el grado de un polinomio dado por el mapeo, y pues al componerlos, el grado incrementa multiplicativamente.
También tenemos que el grado de $latex \mathbbm{1}_{E_i}-\phi_i$, como es un mapeo separable, es el número de elementos en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$... Pregunta ¿quién está en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$?
Recordemos que el endomorfismo de Frobenius tiene una propiedad interesante, es decir, si tenemos que $latex \mathbb{F}_{p^n}$ es un campo finito, y definimos para todo $latex x\in \mathbb{F}_{p^n}$ el mapeo $latex \phi_m(x) := x^{p^m}$ entonces $latex \phi_m(x)=x$ sí y sólo sí $latex x\in \mathbb{F}_{q^m}$ por lo que $latex x\in \overline{\mathbb{F}_p}$ es $latex \mathbb{F}_{p^m}$-racional si $latex \phi_m(x)=x$ , es decir, donde el endomorfismo de Frobenius se comporta como la identidad, nos caracteriza a los puntos racionales.
Entonces el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$ son los puntos $latex (x_i,y_i)\in E_i$ que son iguales ante Frobenius y ante la identidad... es decir, puntos racionales $latex \mathbb{F}_q$-racionales.
Con lo anterior tenemos que $latex \text{grad} (\mathbbm{1}_{E_i}-\phi_i)=$#$latex E_i$ .
Con esto tenemos tenemos que el grado de
(*) es:
$latex \text{grad}\psi\cdot$#$latex E_1 = \text{grad}\psi\cdot$#$latex E_2$ por lo que #$latex E_1=$#$latex E_2$. q.e.d. $latex \blacksquare$.
p-Torsión, j-invariante y características de curvas elípticas súpersingulares
Definición: $latex E/\mathbb{F}_{p^n}$ una curva elíptica, entonces definimos la n-torsión de la curva como:
$latex E[n] := \lbrace P\in E : nP=\infty \rbrace$
Es decir, los puntos que al sumarse $latex n$ veces, se anulan.
Definición: Sea $latex E/\mathbb{F}_{p^n}$ entonces decimos que $latex E$ es
ordinaria si $latex E[p]\cong \mathbb{Z}/(p)$ y es
supersingular si $latex E[p]\cong\lbrace\infty\rbrace$.
Es decir, si no tiene p-torsión más que la trivial, le llamamos
supersingular.
La palabra "supersingular" no tiene nada que ver con "singular", ya que una curva es singular si tiene singularidades, pero una curva elíptica por definición no es singular, es decir, no tiene puntos raros (discriminante de la curva es distinto de cero), ni tampoco raices repetidas.
La palabra supersingular es porque realmente son excepcionales, y de hecho una cosa interesante de estas curvas es que
SIEMPRE están bien definidas sobre $latex \mathbb{F}_{p^2}$ para cualquier $latex p$ , es decir, al reducir una ecuación de una curva a $latex \mathbb{F}_{p^2}$ nunca presentará singularidades.
Ahora vamos a ver otra definición importante que justamente será usada por el protocolo Diffie-Hellman.
Definición: Definimos el
j-invariante de una curva elíptica $latex E/k$ donde $latex k$ es cualquier campo de caracteristica mayor que 3 y la forma de Weierstrass de $latex E$ es $latex y^2=x^3 + ax+b$ lo definimos como:
$latex j(E):=1728 \frac{4a^3}{4a^3+27b^2}$
Esta función loquita es muy importante en análisis complejo, y se preguntarán de donde sale ese 1728. Primero necesitamos saber para qué es esto.
El j-invariante tiene la propiedad de que si dos curvas tienen el mismo j-invariante, es decir $latex j(E_1)=j(E_2)$ entonces tenemos que $latex E_1\cong E_2$ sobre su campo de definición $latex k$.
Noten que el denominador del j-invariante nunca es 0, ya que es justamente el discriminante de $latex x^3 + ax+b$ y este no es cero porque sino la curva tendría singularidades y por definición una curva elíptica no es singular.
Otro teorema importante es que para todo $latex j_0\in k$ existe una curva elíptica $latex E_{j_0}$ tal que $latex j(E_{j_0})$ por lo que automáticamente podemos inferir que sobre cualquier campo... el moduli de TODAS las curvas elípticas sobre cualquier campo finito o infinito... es unidimensional... es decir, todas las curvas elípticas forman una línea.
Otros teoremas importantes es que los endomorfismos extendidos a $latex \mathbb{Q}$ definido como $latex End_0(E):= End_k(E)\otimes_{k}\mathbb{Q}$ cuando $latex E$ es supersingular, forman una álgebra de cuaternios, es decir no es conmutativa.
En el caso ordinario donde $latex E$ no sea supersingular , tenemos que $latex End_0(E)$ siempre es una extensión cuadrática de $latex Q$ compleja, es decir $latex End_0(E)\cong \mathbb{Q}(\sqrt{d})$ con $latex d$ negativo y libre de cuadrados.
Corolario: Sea $latex E/\mathbb{F}_q$ una curva elíptica supersingular, entonces #$latexE(\mathbb{F}_q)=p+1$.
Demostración:
No lo haré, pero usen el teorema de Hasse, deduzcan que si la curva es supersingular, entonces la traza del endomorfismo de frobenius es 0, todo esto se puede demostrar con lo anterior.
Teorema: Sea $latex \psi:E_1\to E_2$ una isogenia tal que $latex E_1$ es súpersingular, entonces $latex E_2$ también es supersingular.
Lo mismo aplica para curvas ordinarias, es decir, los dos tipos de curvas, súpersingulares y ordinarias sólo "se llevan" entre sus respectivas categorías, esto es importante, porque el protocolo que describiré pronto asegura que todas las isogenias serán entre curvas súpersingulares.
Pero antes veamos cómo construir isogenias cuyo kernel sea el subgrupo del dominio de la isogenia, es decir, dado un $latex H_P\subset E$ un subgrupo de una curva elíptica sobre un campo finito, en este caso $latex H_P$ es el generado por $latex P$ , construiremos explícitamente $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P=H_P$ y la ecuación explícita de $latex E_P$.
Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.
Recuerden que #$latex E(\mathbb{F}_q)=N$ es finito, ya que el campo de definición es finito.
Entonces por el teorema de lagrange, sabemos que la información de sus subgrupos está escondida en la factorización de $latex N$.
Sea $latex P\in E$, definimos el subgrupo $latex H_P\subsetneq E$ como:
$latex H_P:=\lbrace nP : n \in \mathbb{Z}\rbrace$
Este es el grupo de "todos los múltiplos de $latex P$:" en la curva, es trivial que es un subgrupo de $latex E$.
Vamos ahora a construir una isogenia asociada a $latex P\in E$ que denotamos por $latex \psi_P$ cuyo kernel sea $latex H_P$ hacia otra curva que denotaremos como $latex E_P$.
Es decir vamos a construir $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P = H_P$
Todos sabemos que el kérnel de un morfismo de grupos es un subgrupo normal del grupo, así que esto no debe causarles conflicto.
La notación de las coordenadas para los puntos en $latex \langle E,\oplus\rangle$ será $latex P:=(x_P,y_P), Q:=(x_Q,y_Q), P\oplus Q:=(x_{P+Q},y_{P+Q})$.
Definición-Teorema-Vélu: Sea $latex \langle E/\mathbb{F}_q,\oplus\rangle$ una curva elíptica y $latex P_0\in E$, tal que $latex y^2 = x^3 + ax + b$ construyamos como vimos anteriormente el grupo generado por los "múltiplos de $latex P_0$" , $latex H_{P_0}$.
Entonces tenemos que para todo $latex P\notin H_{P_0}$:
$latex \psi_{P_0}:E\to E_{P_0}$
$latex P\mapsto \Big( x_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(x_{P+Q}-x_Q), y_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(y_{P+Q}-y_Q)\Big)$
Y si $latex P\in H_{P_0}$ definimos $latex \psi_{P_0}(P)=\infty$.
Es fácil mostrar que $latex ker\psi_{P_0}:=H_{P_0}$ , de hecho, ústedes háganlo y verán como todo se reduce a hacer matemáticas lindas, no es tan difícil.
Pero bueno, esta función $latex \psi_{P_0}$ no está dada por la forma que mostrarmos al principio, es decir por la isogenia definida con los polinomios $latex \big( \frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)} \big)$.
Pero Dustim Moody y Daniel Shumow ya lo hicieron en la sección 2.3 de un paper,
aquí dejo su páper , así que ya tenemos la isogenia explícita, y de hecho en ese mismo paper se describe la ecuación de la curva $latex E_{P_0}$ la cual es $latex y^2 = x^3 + (a-5v)x + (b-7w)$ donde $latex v,w$ son constantes que dependen de $latex H_{P_0}$ y son explícitamente calculables.
Ahora sí, el algoritmo
Algoritmo explícito Diffie Hellman con isogenias entre curvas elípticas supersingulares.
Considera una curva elíptica supersingular $latex E$ definida sobre $latex \mathbb{F}_{p^2}$ tal que $latex p=w_A^{e_A}\cdot w_B^{e_B}\cdot f \pm 1$, es decir es un número primo especial, donde $latex w_A,w_B$ son números primos chicos y $latex f$ es cualquier entero, así como $latex e_A,e_B$ los cuales se escogerán de tamaños parecidos y tal que $latex p$ cumpla el nivel de seguridad requerido en bits para este esquema, que está probado que es aproximadamente de 3000 bits (
referencia aquí). Entonces con todo lo que dijimos en la sección de curvas súpersingulares es fácil inferir que el tamaño de la curva está dado por #$latex E(\mathbb{F}_{p^2})=(p\pm 1)^2$.
Sean A=Artemisa y B=Boris , dos personas que desean intercambiar una llave en un canal no seguro intervenido por un atacante con recursos cuánticos.
Entonces ellos harán lo siguiente:
Algoritmo SIDH (Supersingular Isogeny Diffie-Hellman)
Públicamente harán lo siguiente:
Se ponen de acuerdo en los siguiente: $latex p=w_A^{e_A}\cdot \w_B^{e_B}\cdot f \pm 1,\langle E/\mathbb{F}_{p^2},\oplus\rangle,P_A,Q_A,P_B,Q_B\in E$ tal que $latex E$ es súpersingular.
donde intercambiar una curva $latex E/\mathbb{F}_{p^2}$ equivale a mandar $latex \lbrace a,b\rbrace$ tal que $latex y^2 = x^3 + ax+b$.
Tenemos que $latex P_A,Q_A$ y $latex P_B,Q_B$ fueron escogidos tal que tienen orden $latex w_A^{e_A}$ y $latex w_B^{e_B}$ respectivamente, lo cual es fácil por el número primo que construimos.
Vamos a denotar por nA, nB, el paso $latex n$ que tiene que hacer Artemisa o Boris respectivamente,.
Protocolo:
1A: A genera dos números aleatorios $latex m_A,n_A$ < $latex w_A^{e_A}$
2A: A genera $latex R_A := m_A\cdot P_A \oplus n_A\cdot Q_A$
(secreto)
3A: A usa el punto $latex R_A$ para crear el subgrupo $latex H_{R_A}$ que funcionará como kernel del mapeo $latex \psi_{A}:E\to E_A$, por lo que ya tiene $latex R_A,\psi_{A},E_A$ donde los últimos dos son gracias a las fórmulas de Vélu mostradas en la sección anterior.
4A: A forma los puntos $latex \psi_{A}(P_B)$ y $latex \psi_{A}(Q_B)$ con su isogenia creada en el paso anterior.
5A: A le manda a B $latex \lbrace E_A,\psi_A(P_B),\psi_A(Q_B)\rbrace$
Pero
NO le manda la isogenia, sino la imagen de los puntos bajo la isogenia secreta $latex \psi_A$
1B-4B: Ahora Boris hace los mismos primeros 4 que Artemisa, sólo intercambiamos las letras de los subscripts A por B
5B: B manda a A $latex \lbrace E_B,\psi_B(P_A),\psi_B(Q_A)\rbrace$
6A: A tiene $latex m_A,n_A,\psi_B(P_A),\psi_B(Q_A)$ y forma el punto $latex S_{BA}:=m_A\cdot\psi_B(P_A)\oplus n_A\cdot\psi_B(Q_A)$.
7A: A usa el punto para generar la isogenia $latex \psi_{BA}$ usando fórmula de Vélu, así como la imagen de la isogenia que será la nueva curva $latex E_{BA}$ que es isógena a $latex E$ gracias a $latex \psi_{BA}$.
8A. A calcula el
j-invariante de la curva $latex E_{BA}$ que será $latex \kappa:=j(E_{BA})$.
6B: Similarmente al paso 6A, Boris tiene $latex m_B,n_B,\psi_A(P_B),\psi_A(Q_B)$ por lo que forma el punto $latex S_{AB}:=m_B\cdot\psi_A(P_B)\oplus n_B\cdot\psi_A(Q_B)$.
7B: Boris usa el punto $latex S_{AB}$ para generar la isogenia con las fórmulas de Velú asociada al subgrupo generado por $latex S_{AB}$ , esta isogenia es $latex \psi_{AB}$ y genera también el codominio de esta isogenia que es la curva $latex E_{AB}$ que es isógena a $latex E$ gracias a $latex \psi_{AB}$.
8B: B calcula el
j-invariante de la curva $latex E_{AB}$ que será $latex \kappa:=j(E_{AB})$.
Las curvas $latex E_{AB}$ y $latex E_{BA}$ son isomorfas, ustedes lo pueden demostrar si hacen todo el diagrama, por lo que el j-invariante será el mismo, y ya ambos pueden usar como password $latex \text{Hash}(\kappa)$ o cualquier función en Kappa.
¿Pero por qué nos enfocamos en súpersingulares?
La verdad nunca usamos nada de las características supersingulares... Pero recuerden que el álgebra de endomorfismos de una curva elíptica supersingular NO es conmutativa, ya que es isomorfa a un álgebra de cuaternios.
Existe un ataque, que resuelve el problema "difícil" en el que está basado este protocolo en tiempo subexponencial cuántico. El algoritmo está descrito en
este paper por Andrew M. Childs, David Jao y Vladimir Soukharev. El cuál hace uso extenso de la CONMUTATIVIDAD del anillo de endomorfismos de la curva elíptica para resolver subexponencialmente el "Abelian Hidden Shift Problem" que es el nombre del problema que hace seguro al algoritmo descrito en la sección anterior.
Por lo que debemos enfocarnos a curvas cuyo anillo de endomorismos no sea conmutativo... es decir... súpersingulares.
¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis a este algoritmo?
Lo que hay que romper es el
"Abelian Hidden Shift Problem". Algo así en español como "Problema oculto de desplazamiento oculto", ya que lo que estamos haciendo en el algoritmo anterior, es desplazar grupos, y adquireir nuevas curvas "desplazando" con puntos nuevos.
Este problema en general consta de lo siguiente.
-Sea $latex A$ un grupo abeliano finito.
-Sea $latex S$ un conjunto finito.
-Sea $latex f:A\to S$ y $latex g:A\to S$ dos funciones inyectivas.
-Existe una $latex b\in A$ tal que para todo $latex x\in A$ tenemos que $latex f(x)=g(xb)$
-El valor que un atacante quisiera saber es $latex b$.
Vamos a reformular esto en términos de curvas elípticas de manera básica.
-Tenemos dos curvas isógenas $latex E,\hat{E}$
-Decimos que $latex f_0(a)=a*E$ y $latex f_1(a)=a*\hat{E}$.
-Entonces $latex b*E=\hat{E}$
-También $latex f_1(a)=a*\hat{E}=a*b*E=f_0(ab)$
Resolver el
Abelian Hidden Shift Problem en $latex f_0$ y $latex f_1$ es descubrir $latex b$.
Esto realmente significa calcular la acción en las curvas elípticas
Dicho esto, SIDH con curvas elípticas súpersingulares, la seguridad se obtiene es con llaves de 3000 bits para obtener seguridad cuántica exponencial de 128 bits, la cual es más que suficiente.
Esto es todo por hoy, ahora saben cómo implementar un algoritmo que tenga seguridad cuántica.
Espero les haya gustado.
Más información, pueden ver el paper original de Luca De Feo, David Jao y Jerome Plut.
https://eprint.iacr.org/2011/506.pdf
Eduardo Ruíz Duarte (beck)
Twitter: @toorandom
