Criptografía basada en Isogenias

Criptografía basada en Isogenias Dr. Carlos Vela Cabello Criptografía basada en Isogenias Dr. Carlos Vela Cabello Memoria presentada como parte de los requisitos para la obtención del título de Máster Universitario en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Dra. Sara Arias de Reyna Índice general English Abstract 1 1. Curvas Elípticas 3 2. Isogenias y sus grafos 13 2.1. Isogenias.................................. 13 2.2. grafodeisogenias............................. 22 3. Criptografía basada en Isogenias 27 3.1. Protocolo de intercambio de clave . . . . . . . . . . . . . . . . . . . . 27 3.2. ¿Por qué es tan seguro? . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.1. Otros protocolos . . . . . . . . . . . . . . . . . . . . . . . . . 38 4. Programación SAGE 39 English Abstract In this project we will make an introduction to the Diffie-Hellman key exchange protocol based on iogenies of supersingular elliptic curves. Firstly, we will study some bibliography about elliptic curves and define the supersingular elliptic curves. Secondly, we will review the concept of isogeny and construct the base for our key exchange protocol, the 𝓁-isogeny graphs. Later, a detailed explanation of this protocol will be given together with an exhaustive example of it. Finally, a SAGEMath programm will be developed to make instances of the protocol according to this project. 1 Curvas Elípticas En este capítulo haremos una introducción de todos los conceptos previos necesarios para cumplir con el objetivo de este trabajo de fin de máster, comprender la criptografía basada en isogenias. Para ello, comenzaremos definiendo qué son las curvas elíticas y veremos algunos aspectos y resultados sobre ellas. Acabaremos estudiando las aplicaciones entre curvas elípticas, como son los isomorfismos. Para este capítulo supondremos que 𝐾es un cuerpo y  𝐾es su clausura algebraica. Empezaremos con la definición de curvas elípticas para continuar describiendo muchas de sus propiedades las cuales nos servirán para poder construir un protocolo criptográfico basado en aplicaciones entre curvas elípticas, las isogenias. Definición 1.1. El espacio proyectivo de dimensión 𝑛, es el conjunto de clases ℙ𝑛(𝐾)=(𝐾𝑛+1 ⧵{𝟎})∕ ∼ donde dos vectores 𝑢y𝑣están relacionados: 𝑢∼𝑣⇐⇒ existe un 𝜆≠0tal que 𝑢=𝜆𝑣. Nótese que los puntos en el plano proyectivo tienen tres coordenadas [𝑥0∶𝑥1∶ 𝑥2], no simultaneamente nulas que verifican que: [𝑥0∶𝑥1∶𝑥2]=[𝑥′ 0∶𝑥′ 1∶𝑥′ 2]⇐⇒ 𝑟𝑎𝑛𝑔𝑜 ([𝑥0𝑥1𝑥2 𝑥′ 0𝑥′ 1𝑥′ 2])= 1 Con respecto al plano proyectivo, nos queda recordar que contiene al plano afín habitual (recordemos que el espacio afín es el conjunto 𝔸𝑛(𝐾) = 𝐾𝑛), con la aplica- 10 criptografía basada en isogenias sobre este cuerpo finito: 𝐸1∶𝑦2−𝑥3− 39𝑥− 1 𝐸2∶𝑦2−𝑥3− 102𝑥− 63 Es sencillo comprobar que son curvas elípticas verificando que Δ1= 4220 y que Δ2= 898. Ahora podemos calcular sus respectivos 𝑗-invariantes 𝑗(𝐸1) = 𝑗(𝐸2) = 72. Esto nos indica que estas curvas son isomorfas sobre 𝔽107, la clausura algebraica de 𝔽107. Ahora no sólo podemos identificar si una fórmula de Weiestra𝛽es elíptica, o no, si no que las podemos clasificar por su 𝑗-invariante. Teorema 1.3. Sea 𝑗0∈ 𝐾. Existe una curva elíptica definida sobre  𝐾cuyo 𝑗invariante es 𝑗0. Este último teorema nos dice que todas las clases de equivalencia de las curvas elípticas sobre un cuerpo son no vacías. Debemos introducir el punto =[0∶1∶0]como el punto del infinito. Éste es el único punto en las curvas elípticas que se encuentra en en la recta 𝑍= 0. Definición 1.10. Sea 𝐸=𝐶𝑓∕𝐾una curva elíptica donde 𝑓∶𝑦2=𝑥3+𝑎𝑥 +𝑏. Sean 𝑃1= (𝑥1, 𝑦1)y𝑃2= (𝑥2, 𝑦2)dos puntos de 𝐸diferentes del punto del infinito. Definimos la operación ⊕en 𝐸como sigue: 𝑃 ⊕ =⊕ 𝑃 =𝑃para todo 𝑃∈𝐸 Si 𝑥1=𝑥2y𝑦1= −𝑦2entonces 𝑃1⊕ 𝑃2=. En otro caso tenemos que 𝑃1⊕ 𝑃2= (𝑥3, 𝑦3)tales que: •𝑥3=𝜆2−𝑥1−𝑥2 •𝑦3= −𝜆𝑥3−𝑦1+𝜆𝑥1 •𝜆=⎧ ⎪ ⎨ ⎪ ⎩ 𝑦2−𝑦1 𝑥2−𝑥1 if 𝑃≠𝑄 3𝑥2 1+𝑎 2𝑦2 if 𝑃=𝑄 Proposición 1.2.El par (𝐸(𝐾), ⊕)es un grupo abeliano conmutativo, cuyo elemento neutro es , el punto del infinito. Esta operación, lejos de ser aleatoria, tiene una explicación geométrica gracias al teorema de Bezout el cual nos explica que dada una curva elíptica y una recta, su intersección son 3 puntos (contando multiplicidades). 1. curvas elípticas 11 Si consideramos las curvas elípticas sobre un cuerpo finito 𝔽𝑞tenemos una cota en el cardinal del grupo: Teorema 1.4. [7, V, Th.1.1] Sea 𝑞∈ℤuna potencia de primo, 𝐸(𝔽𝑞)una curva elíptica definida sobre un cuerpo finito, entonces #𝐸(𝔽𝑞) = 𝑞+ 1 − 𝑡donde 𝑡cumple que |𝑡|≤2√𝑞 En este aspecto de las curvas elípticas vistas como un grupo podemos ir un poquito mas allá. El siguiente resultado nos da una herramienta para saber cuando una curva elíptica existe y además qué estructura tiene: Teorema 1.5 ([12]). Sea 𝔽𝑞el cuerpo de 𝑞elemento. Dado un |𝑡|≤2√𝑞entero entonces existe una curva elíptica sobre 𝔽𝑞con 𝑞+ 1 − 𝑡puntos racionales si y solo si, tomando 𝑞=𝑝𝑟, se satisfacen alguna de las siguientes condiciones: i)𝑚𝑐𝑑(𝑡, 𝑞)=1, ii)𝑡= 0,𝑟impar, o 𝑝≢1 m od 4, iii)𝑡= ±√𝑞,𝑟par, o 𝑝≢1 m od 3, iv)𝑡= ±2√𝑞,𝑟par, v)𝑡= ±√2𝑞,𝑟impar y 𝑝= 2, vi)𝑡= ±√3𝑞,𝑟impar y 𝑝= 3. Además, la estructura de grupo en los casos 𝐼𝐼) − 𝑉 𝐼)son los siguientes: ii)ℤ∕2ℤ⊕ℤ∕(𝑞+1 2)ℤo cíclico si 𝑞≡3 m od 4, iii) grupo cíclico, iv)(ℤ∕(√𝑞± 1)ℤ)2, v) grupo cíclico, vi) grupo cíclico. Definición 1.11. Sea 𝐸∕𝔽𝑞una curva elíptica con 𝑞+1−𝑡puntos. Entonces: Si 𝑝∤𝑡entonces 𝐸es una curva ordinaria. Si 𝑝|𝑡entonces 𝐸es una curva supersingular. En cuanto al término “supersingular” no tiene nada que ver con que tenga puntos singulares. De hecho en [7, V.3,Remark3.2.2] se cuenta el origen de esta terminología. Desde el punto de vista histórico, a las curvas elípticas definidas sobre ℂcuyo anillo 12 criptografía basada en isogenias de endomorfismos era más grande que ℤse les llamaba singulares en el sentido de “raro o “no usual”. De todas formas, en este sentido (como ya veremos), las curvas elípticas definidas sobre cuerpos finitos 𝔽𝑝son todas singulares. De hecho, el anillo de endomorfismos de la mayoría de curvas elípticas sobre 𝔽𝑝son órdenes en un cuerpo cuadrático imaginario. Es en el excepcional caso en el que el anillo de endomorfismos de la curva es un orden de un álgebra de cuaternión en el que usaremos el término “supersingular”. 2 Isogenias y sus grafos En este capítulo veremos cómo se define una isogenia y algunas características que tienen. Además también veremos cómo se definen los grafos de isogenias y cómo construirlos. Estos grafos serán el andamio sobre el que, en el siguiente capítulo, construyamos nuestro protocolos criptográficos. 2.1 Isogenias Comenzaremos esta sección dando la definición de isogenia y dos propiedades básicas que nos serán de gran utilidad a la hora de construir los mencionados grafos. Definición 2.1. Sean 𝐸1y𝐸2dos curvas elípticas. Una isogenia de 𝐸1a𝐸2es un morfismo 𝜙∶𝐸1→𝐸2de tal forma que 𝜙() = . Diremos que dos curvas, 𝐸1y𝐸2son isógenas si existe una isogenia 𝜙entre ellas de tal forma que 𝜙(𝐸1)≠{}. También diremos que la isogenia 𝜙está definida sobre 𝐾si sus coeficientes pertenecen a 𝐾. Más adelante podremos ver que la relación “ser isógenas” es una relación de equivalencia. Teorema 2.1. [7, III.4] Sea 𝜙∶𝐸1→𝐸2una isogenia. Entonces 𝜙o es constante o sobreyectiva. Teorema 2.2. [7, III.4, Corollary 4.9] Sea 𝜙∶𝐸1→𝐸2una isogenia. Entonces, 𝑘𝑒𝑟(𝜙)es un grupo finito. Teorema 2.3. [4, 9.7, Theorem 9.7.4](Tate) Dos curvas elípticas, 𝐸y𝐸′definidas sobre un cuerpo 𝐾son isógenas sobre 𝐾si y solo si #𝐸(𝐾)=#𝐸′(𝐾). Un dato sobre las isogenias muy importante para nuestro fin, la criptografía, es el grado de estas. Para poder determinarlo debemos recordar brevemente qué es el 14 criptografía basada en isogenias cuerpo de funciones de una curva 𝐸. Sea 𝐸=𝐶𝑓(𝐾)una curva elíptica, definimos el conjunto: 𝐾(𝐸) = {ℎ(𝑥, 𝑦) 𝑔(𝑥, 𝑦)∶con ℎ, 𝑔 ∈𝐾[𝐸], 𝑔 ≠0};𝐾[𝐸] = 𝐾[𝑋, 𝑌 ]∕⟨𝑓⟩(2.1) Por las propiedades que hemos visto hasta ahora, una isogenia, 𝜙∶𝐸1→𝐸2 puede verse como una aplicación racional no constante, a excepción de [0]. Entonces, la composición con 𝜙induce una inyección de los cuerpos de funciones que fijan 𝐾 [7, II.2]: 𝜙∗∶𝐾(𝐸2)→𝐾(𝐸1)𝜙∗𝑓=𝑓◦𝜙. De hecho, en [7, II.2,Theorem 2.4] se demuestra que esta inyección es una extensión finita, i.e., que 𝐾(𝐸1)es una extensión finita de 𝜙∗(𝐾(𝐶2). El grado de una isogenia no nula se define como el grado del morfismo, pero tambiñen puede definirse como a continuación: Definición 2.2. Sean 𝐸1∕𝐾y𝐸2∕𝐾dos curvas elípticas y 𝜙∶𝐸1→𝐸2una isogenia no constante definida sobre 𝐾. Entonces, el grado de 𝜙se define como 𝑑𝑒𝑔𝜙 = [𝑘(𝐸) ∶ 𝜙∗(𝐾(𝐸2))], donde 𝜙∗es el pullback1de 𝜙. Si 𝜙es constante, entonces 𝑑𝑒𝑔(𝜙) = 0. De una manera menos formal, según [4], una isogenia de grado 𝑑es una correspondencia “𝑑-to-1on most points”. Esto lo podremos comprobar en el ejemplo 2.1. Definición 2.4. A una isogenia se le dice separable cuando la extensión de cuerpos 𝑘(𝐸)∕𝜙∗(𝐾(𝐸2)) lo es. Teorema 2.4. Sea 𝜙∶𝐸1→𝐸2una isogenia. Si 𝜙es separable, entonces 𝑑𝑒𝑔(𝜙)=#𝑘𝑒𝑟(𝜙) Las isogenias también pueden ser inseparables y puramente inseparables si la ex- 1En caso de que alguien necesite recordarlo: Definición 2.3. [4, 5.5, Definition 5.5.21] Sean 𝑋e𝑌variedades sobre 𝐾y sea 𝜙∶𝑋→𝑌una aplicación racional dominante sobre 𝐾. Definimos el pullback 𝜙∗∶𝐾(𝑌)→𝐾(𝑋)como 𝜙∗(𝑓) = 𝜙◦𝑓. 2. isogenias y sus grafos 15 tensión de cuerpos correspondiente lo es. No indagaremos más en la diferencia entre estos tipos de isogenias. Aquellos que deseen saber más sobre las diferencias entre los tipos de isogenias pueden dirigirse a [4], [7]. A continuación, veremos dos isogenias entre una curva y ella misma, es decir, isogenias que son endomorfismos. Son una simple muestra de cómo funcionan, además de introducirnos en los elementos del anillo de endomorfismos de una curva. Profundizaremos en este último concepto y su relación con las isogenias más adelante. Definición 2.5. Sea 𝑚∈ℤdefinimos la multiplicación por escalar [𝑚] ∶ 𝐸→𝐸 como: [𝑚](𝑃) = 𝑚 ⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞ 𝑃+𝑃+⋯+𝑃 El punto 𝑃se suma 𝑚veces. En caso de que 𝑚 < 0fijamos la operación como: [𝑚](𝑃) = [−𝑚](−𝑃) Por último, si 𝑚= 0 fijamos [0](𝑃) = . Teorema 2.5. [4, 9.6, Corollary 9.6.28] Sea 𝑚∈ℤ, la multiplicación por escalar [𝑚] es una isogenia y tiene grado 𝑚2. Definición 2.6. Sea 𝑚∈ℤtal que 𝑚≥1. El subgrupo 𝑚-torsión de 𝐸, denotado como 𝐸[𝑚], es el conjunto de puntos de 𝐸cuyo orden divide a 𝑚: 𝐸[𝑚] = {𝑃∈𝐸()  𝐾∶ [𝑚]𝑃=} Teorema 2.6. [12] Sea 𝑚∈ℤy𝐸una curva elíptica definida sobre el cuerpo 𝐾de tal forma que 𝑐ℎ𝑎𝑟(𝐾) ∤ 𝑚, entonces 𝐸[𝑚] ≅ ℤ∕𝑚ℤ×ℤ∕𝑚ℤ. Observación 2.1.Puede apreciarse, por definición, que el subgrupo de 𝑚-torsión es el núcleo de la multiplicación por escalar [𝑚]. Es decir, 𝑘𝑒𝑟([𝑚]) ≅ 𝐸[𝑚] ≅ ℤ∕𝑚ℤ×ℤ∕𝑚ℤ. Ejemplo 2.1.Consideremos la curva elíptica 𝐸=𝐶𝑓(𝔽11)dada por la fórmula 𝑓∶ 𝑦2=𝑥3+ 3𝑥+ 3 definida sobre el cuerpo finito 𝔽𝟙𝟙 de 11 elementos. Esta curva tiene 16 criptografía basada en isogenias 8puntos, vamos a ver como se comporta la isogenia [2]: [2] ∶ 𝐸𝑓←→ 𝐸𝑓 𝜙(0 ∶ 1 ∶ 0) = (0 ∶ 1 ∶ 0) 𝜙(0 ∶ 5 ∶ 1) = (9 ∶ 0 ∶ 1) 𝜙(0 ∶ 6 ∶ 1) = (9 ∶ 0 ∶ 1) 𝜙(5 ∶ 0 ∶ 1) = (0 ∶ 1 ∶ 0) 𝜙(7 ∶ 2 ∶ 1) = (9 ∶ 0 ∶ 1) 𝜙(7 ∶ 9 ∶ 1) = (9 ∶ 0 ∶ 1) 𝜙(8 ∶ 0 ∶ 1) = (0 ∶ 1 ∶ 0) 𝜙(9 ∶ 0 ∶ 1) = (0 ∶ 1 ∶ 0) Por ende el subgrupo de 2-torsión es 𝐸[2] = {(0 ∶ 1 ∶ 0),(5 ∶ 0 ∶ 1),(8 ∶ 0 ∶ 1),(9 ∶ 0 ∶ 1)} ⊂ 𝐸(𝔽11). Nótese que, por lo general, no sabíamos a priori si 𝐸[2] ⊆ 𝐸(𝔽11). Además, el núcleo de esta isogenia está formado por el mismo subgrupo 𝑘𝑒𝑟([2]) = {(0 ∶ 1 ∶ 0),(5 ∶ 0 ∶ 1),(8 ∶ 0 ∶ 1),(9 ∶ 0 ∶ 1)} cuyos elementos tienen todos orden 2. Por ello, se ve que: 𝑘𝑒𝑟([2]) ≡ℤ∕2ℤ×ℤ∕2ℤ. La aplicación de Frobenius es el segundo ejemplo de isogenia que es un endomorfismo que vamos a presentar: Definición 2.7. Sea 𝐾=𝔽𝑞un cuerpo finito con 𝑞elementos. La aplicación de Frobenius se define como: 𝜋∶𝐸→𝐸 (𝑋, 𝑌 )→ (𝑋𝑞, 𝑌 𝑞) Teorema 2.7. [4, 9.6] La aplicación de Frobenius es una isogenia y además fija los puntos 𝐾-racionales de la curva elíptica: 𝑥𝑞=𝑥para todo 𝑥∈𝔽𝑞 𝑦𝑞=𝑦para todo 𝑦∈𝔽𝑞 Observación 2.2.Dada una curva elíptica 𝐸∕𝔽𝑞con #𝐸∕𝔽𝑞=𝑞+1−𝑡, sabemos que el endomorfismo de Frobenius satisface que: 𝜋2−𝑡𝜋 +𝑞= 0. A este 𝑡=𝑡𝑟𝜋 le llamamos la traza de Frobenius. Del teorema 1.4 sabemos que 2. isogenias y sus grafos 17 |𝑡|≤2√𝑞o equivalentemente 𝑡2− 4𝑞≤0. Teorema 2.8. [4, 9.6, Teorema 9.6.21](Isogenia dual) Sea 𝜙∶𝐸←→ 𝐸′una isogenia de grado 𝑚. Existe una única isogenia  𝜙∶𝐸′←→ 𝐸tal que:  𝜙◦𝜙= [𝑚]𝐸,and 𝜙◦ 𝜙= [𝑚]𝐸. Esta  𝜙se llama isogenia dual de 𝜙. Además cumple las siguientes propiedades:  𝜙está definido sobre un cuerpo 𝐾si y solo si 𝜙está definido sobre 𝐾,  (𝜑◦𝜙) =  𝜙◦𝜑 para cualquier isogenia 𝜑∶𝐸′→𝐸′′  (𝜑+𝜙) =  𝜙+𝜑 para cualquier isogenia 𝜑∶𝐸′→𝐸′′, 𝑑𝑒𝑔 𝜙 =𝑑𝑒𝑔  𝜙   𝜙=𝜙 La isogenia dual funciona “casi” como una inversa, lo que hace que éstas se comporten “bien”. Lo más destacable, y más adelante veremos porqué, es que todas las isogenias tienen su correspondiente dual. En este contexto vale la pena mencionar que los isomorfismos de curvas elípticas son un caso concreto de isogenias, concretamente aquellas que tienen grado 1 (por eso al comoponerlas tenemos 𝑖𝑑 = [1]). Gracias a la existencia de esta “dualidad”, la relación “ser isogénicas” es relación de equivalencia. Del anterior teorema 2.2 hemos aprendido que dada una isogenia, su núcleo es un subgrupo finito de la curva dominio. Otro resultado relacionado con este nos dice lo siguiente: Proposición 2.1.[7, III.4] Sea 𝐸una curva elíptica y 𝐺 ⊆ 𝐸 un subgrupo de esta. Existe una única curva elíptica 𝐸′y una única isogenia separable 𝜙𝐺∶𝐸→𝐸′de tal manera que 𝑘𝑒𝑟(𝜙𝐺) = 𝐺. Observación 2.3.Es decir que por cada subgrupo 𝐺de una curva elíptica 𝐸tendremos una única isogenia 𝜙𝐺y una única curva elíptica 𝐸′como codominio de 𝜙𝐺. Además, por el teorema 2.4 si conocemos el orden del grupo 𝐺también sabremos el grado de la isogenia. De esta forma podemos saber las isogenias que hay entre los diferentes 𝑗-invariantes. Nótese que hemos hablado de existencia de isogenias, no de construcción. Para resolverlo, en [8] se nos facilita un algoritmo para poder construir las isogenias que en el resultado anterior sabemos que existen. El desarrollo de esta fórmula se escapa del propósito de este trabajo por lo que aquellos interesados en profundizar sobre ello pueden consultar [8]. 18 criptografía basada en isogenias Ejemplo 2.2.Sea 𝐸=𝐶𝑓(𝔽17), la curva elíptica sobre el cuerpo finito 𝔽17 definida por la ecuación 𝑓∶𝑦2=𝑥3+ 3𝑥+ 3 (usamos la misma ecuación que en el anterior ejemplo pero sobre un cuerpo diferente). En este caso la curva contiene 12 puntos entre los cuales (2 ∶ 0 ∶ 1) tiene orden 2. Si tomamos este punto como generador del subgrupo 𝐺, usando la fórmula de Velù encontramos la isogenia 𝜑de tal forma que 𝑘𝑒𝑟(𝜑) = 𝐺como sigue: 𝜑∶𝐸←→ 𝐸𝐺 (𝑥, 𝑦)←→ (𝑥2− 2𝑥− 2 𝑥− 2 ,𝑥2𝑦− 4𝑥𝑦 + 6𝑦 (𝑥2− 4𝑥+ 4) ) Como es de esperar, al ser el núcleo un subgrupo de orden 2,𝜑es una isogenia de orden 2. Su dual 𝜑 viene definida por: 𝜑 ∶𝐸𝐺←→ 𝐸 (𝑥, 𝑦)←→ (−4𝑥2+𝑥− 6 𝑥+ 4 ,−2𝑥2𝑦+𝑥𝑦 + 5𝑦 (𝑥2+ 8𝑥− 1) ) Vamos a comprobar la propiedad que nos dice que 𝜑◦𝜑 = [2] usando el punto 𝑃= (6 ∶ 4 ∶ 1) ∈ 𝐸. Es sencillo ver que 𝜑(𝑃) = (14 ∶ 13 ∶ 1), y además que 𝜑(𝜑(𝑃)) = (6 ∶ 13 ∶ 1). Ahora nos falta conocer [2](𝑃), que tomando la operación de grupo presentada en el anterior capítulo tenemos que es [2]𝑃= (6 ∶ 13 ∶ 1). Ejemplo 2.3.Vamos a considerar ecuación 𝑓∶𝑦2=𝑥3+ 3𝑥+ 3 sobre el cuerpo finito 𝔽𝟟. Los puntos de la curva son : 𝐶𝑓(𝔽7) = {(0 ∶ 1 ∶ 0),(1 ∶ 0 ∶ 1),(3 ∶ 2 ∶ 1),(3 ∶ 5 ∶ 1),(4 ∶ 3 ∶ 1),(4 ∶ 4 ∶ 1)} Es fácil ver que es una curva elíptica ya que Δ=5≠0. Si calculamos el orden de los puntos de la curva vemos que son {1,2,3,3,6,6}, respectivamente. Vamos a tomar el subgrupo generado por el punto de orden 2,𝐺= {(1 ∶ 0 ∶ 1),(0 ∶ 1 ∶ 0)} como núcleo para definir la siguiente isogenia de orden 2: 𝜙∶𝐸←→ 𝐸1 (𝑥, 𝑦)←→ (𝑥2−𝑥− 1 𝑥− 1 ,𝑥2𝑦− 2𝑥𝑦 + 2𝑦 𝑥2− 2𝑥+ 1 ), donde la curva 𝐸1=𝐶𝑔(𝔽7)con 𝑔∶𝑦2=𝑥3+𝑥+ 3. Como estas curvas son isogenias entonces tienen la misma cantidad de puntos: 𝐸1={(0 ∶ 1 ∶ 0),(4 ∶ 1 ∶ 1),(4 ∶ 6 ∶ 1),(5 ∶ 0 ∶ 1),(6 ∶ 1 ∶ 1),(6 ∶ 6 ∶ 1)}, 2. isogenias y sus grafos 19 cuyos órdenes son {1,6,6,2,3,3} respectivamente. Recordando del comentario anterior que habíamos citado de [4, 8.1] que nos describía que el grado 𝑑de una isogenia nos indicaba que era una correspondencia "d-to-1 on most points", vemos cómo funciona 𝜙: 𝜙(0 ∶ 1 ∶ 0) = (0 ∶ 1 ∶ 0) 𝜙(1 ∶ 0 ∶ 1) = (0 ∶ 1 ∶ 0) 𝜙(3 ∶ 2 ∶ 1) = (6 ∶ 6 ∶ 1) 𝜙(4 ∶ 4 ∶ 1) = (6 ∶ 6 ∶ 1) 𝜙(3 ∶ 5 ∶ 1) = (6 ∶ 1 ∶ 1) 𝜙(4 ∶ 3 ∶ 1) = (6 ∶ 1 ∶ 1) En este caso, esa correspondencia se cumple en todos los puntos donde además confirmamos que los dos primeros elementos están en el núcleo de la isogenia. En un primer momento podríamos pensar que, al tener la misma cantidad de puntos y además los mismos órdenes, estas curvas podrían ser isomorfas. Pero un rápido vistazo a sus 𝑗-invariantes nos despeja cualquier atisbo de duda, ya que 𝑗(𝐸) = 4 y 𝑗(𝐸1)=5. Algunos de los ejemplos de isogenias que hemos considerado hasta ahora coinciden en dominio y codomino, i.e., son endomorfismos. El conjunto de endomorfismos juega un importante papel a la hora de definir las isogenias. Un endomorfismo de una curva elíptica 𝐸o bien es la aplicación nula (aquella que lleva todos los elementos al punto del infinito, i.e., [0]) o bien es una isogenia. El conjunto de todos los endomorfismos de una curva 𝐸se denota 𝐸𝑛𝑑(𝐸). Este conjunto, 𝐸𝑛𝑑(𝐸), junto con las operaciones suma y composición forma un anillo, i.e., que para todos 𝜙, 𝜑 ∈𝐸𝑛𝑑(𝐸) y𝑃∈𝐸(𝐾)las operaciones son: (𝜙+𝜑)(𝑃) = 𝜙(𝑃) + 𝜑(𝑃), (𝜙𝜑)(𝑃) = 𝜙(𝜑(𝑃)). De las isogenias que hemos visto a la largo del capítulo podemos deducir qué elementos se encuentran dentro del anillo de endomorfismos. Para empezar, para todo 𝑛∈ℤ,[𝑛] ∈ 𝐸𝑛𝑑(𝐸)así que podemos decir que ℤ⊆ 𝐸𝑛𝑑(𝐸). Si seguimos en esta línea, la aplicación de frobenius, 𝜋, al ser un endomorfismo también está en 𝐸𝑛𝑑(𝐸) siempre y cuando la característica del cuerpo 𝑝 > 0. Por lo tanto, sabemos que ℤ[𝜋]⊆ 𝐸𝑛𝑑(𝐸). 26 criptografía basada en isogenias 094 72 68𝛼+ 37 16 47 81𝛼+ 19 26𝛼+ 22 39𝛼+ 95 81 Figura 2.2: El grafo de 3-isogenias de la componente de curvas supersingulares. poner un protocolo de intercambio de clave tipo Diffie-Hellman y porqué es computacionalmente seguro. 3 Criptografía basada en Isogenias En esta sección vamos a presentar el protocolo de intercambio de clave de Diffie- Hellman basado en isogenias. Para ello comenzaremos eligiendo los parámetros del protocolo, para a continuación, precisar los cambios de información. Acabaremos por ver la razón por la que, hasta este mismo año, ha sido un candidato en el Proceso de estandarización de criptografía post-cuántica del Instituto Nacional de estándares y tecnología (NIST por sus siglas en inglés). 3.1 Protocolo de intercambio de clave Dentro de la biliografía disponible, tanto a nivel teórico como a nivel computacional, la elección del primo 𝑝sobre el que construiremos el protocolo es, por lo general, de la forma siguiente: 𝑝= 2𝑒𝐴3𝑒𝐵− 1, donde 𝑒𝐴, 𝑒𝐵∈ℕde tal forma que 2𝑒𝑎≈ 3𝑒𝐵. Algunas referencias incluso dan un poco más de flexibilidad permitiendo un "factor", 𝑓de tal forma que 𝑝=𝑓2𝑒𝐴3𝑒𝐵− 1. Una razón de peso la tenemos en el teorema 1.5, ya que nos permite saber que existe una curva 𝐸(𝔽𝑝2)que, 𝐸(𝔽𝑝2) ≅ ℤ∕(𝑝+ 1)ℤ×ℤ∕(𝑝+ 1)ℤ=ℤ∕(2𝑒𝑎3𝑒𝐵)ℤ×ℤ∕(2𝑒𝑎3𝑒𝐵)ℤ. Por ello, sabemos que podemos encontrar dos puntos 𝑃y𝑄de la curva, ambos de orden 2𝑒𝑎3𝑒𝐵que pueden generar el grupo, i.e., son una base para este. Recordando la relación de los subgrupos de una curva elíptica con las isogenias y teniendo presente el teorema de Lagrange, la elección de estos primos nos permite restringirnos a los grafos de 2y3-isogenias. 28 criptografía basada en isogenias Primero, fijamos todos parámetros públicos: una curva elíptica supersingular 𝐸0y dos bases de puntos {𝑃𝐴, 𝑄𝐴}y{𝑃𝐵, 𝑄𝐵}. La curva 𝐸0definida sobre 𝔽𝑝2y las bases de puntos han de generar 𝐸[2𝑒𝐴]y𝐸[3𝑒𝐵]respectivamente, i.e., ⟨𝑃𝐴, 𝑄𝐴⟩=𝐸[2𝑒𝐴] ≅ ℤ∕2𝑒𝐴ℤ×ℤ∕2𝑒𝐴ℤ;⟨𝑃𝐵, 𝑄𝐵⟩=𝐸[3𝑒𝐵] ≅ ℤ∕3𝑒𝐵ℤ×ℤ∕3𝑒𝐵ℤ. De esta manera, los pares de puntos públicos {𝑃𝐴, 𝑄𝐴}y{𝑃𝐵, 𝑄𝐵}tienen, necesariamente, orden 2𝑒𝐴y3𝑒𝐵respectivamente. Con esta información pública ya podemos empezar a escoger las claves privadas y calcular las claves públicas de los usuarios que, como no podía ser de otra manera, son Alicia y Bernardo. Cuando un elemento tenga el subíndice 𝐴querrá decir que es de Alicia, mientras que si tiene el subíndice 𝐵querrá decir que es de Bernardo. Comenzaremos por pedirle a nuestros usuarios que escojan una clave privada 𝑘𝐴∈ [0,2𝑒𝐴)y𝑘𝐵∈ [0,3𝑒𝐵), para, a continuación empezar a calcular su clave pública: 𝑆𝐴=𝑃𝐴+ [𝑘𝐴]𝑃𝐴y𝑆𝐵=𝑃𝐵+ [𝑘𝐵]𝑃𝐵 Una vez tenemos los puntos 𝑆𝐴y𝑆𝐵han de calcular sus isogenias secretas, haciendo uso del algoritmo de Velú [8]: 𝜙𝐴∶𝐸0←→ 𝐸𝐴=𝐸∕⟨𝑆𝐴⟩ 𝜙𝐵∶𝐸0←→ 𝐸𝐵=𝐸∕⟨𝑆𝐵⟩ Esta, 𝜙𝐴será el resultado de componer 𝑒𝐴isogenias de orden 2, i.e., dar 𝑒𝐴pasos en el grafo de 2-isogenias. Esta secuencia de isogenias está determinada por 𝑆𝐴. Análogamente, 𝜙𝐵es el resultado de componer 𝑒𝐵isogenias de grado 3, i.e., de dar 𝑒𝐵pasos por el grafo de 3-isogenias. Las claves públicas de Alicia y Bernardo son, 𝑃 𝐾𝐴= (𝐸𝐴, 𝑃 ′ 𝐵, 𝑄′ 𝐵)=(𝜙𝐴(𝐸), 𝜙𝐴(𝑃𝐵), 𝜙𝐴(𝑄𝐵)), 𝑃 𝐾𝐵= (𝐸𝐵, 𝑃 ′ 𝐴, 𝑄′ 𝐴)=(𝜙𝐵(𝐸), 𝜙𝐵(𝑃𝐴), 𝜙𝐵(𝑄𝐴)). Ahora, Alicia, usando su clave secreta 𝑘𝐴y la clave pública de Bob calcula el subgrupo secreto generado por el punto 𝑆′ 𝐴=𝑃′ 𝐴+ [𝑘𝐴]𝑄′ 𝐴de la curva 𝐸𝐵. Después, calcula la isogenia secreta 𝜙′ 𝐴∶𝐸𝐵→𝐸𝐴,𝐵 donde 𝐸𝐴,𝐵 =𝐸𝐵∕⟨𝑆′ 𝐴⟩. Finalmente la clave intercambiada será 𝑗𝐴,𝐵 =𝑗(𝐸𝐴,𝐵)que es el 𝑗-invariante de la curva 𝐸𝐴,𝐵. Por su parte Bernardo hace los cálculos análogamente, i.e., con su clave privada 𝑘𝐵y la clave pública de Alicia calcula el punto 𝑆′ 𝐵=𝑃′ 𝐵+ [𝑘𝐵]𝑄′ 𝐵de la curva 𝐸𝐴. Posteriormente, obtiene la isogenia secreta 𝜙′ 𝐵∶𝐸𝐴→𝐸𝐵,𝐴 donde 𝐸𝐵,𝐴 =𝐸𝐴∕⟨𝑆′ 𝐵⟩. Finalmente la clave intercambiada será 𝑗𝐴,𝐵 =𝑗(𝐸𝐴,𝐵) = 𝑗(𝐸𝐵,𝐴) = 𝑗𝐵,𝐴. En el Cuadro 3.1 puede 3. criptografía basada en isogenias 29 verse resumido el protocolo de una forma muy esquemática. Parámetros públicos Primos 𝓁𝐴,𝓁𝐵y𝑝=𝓁𝑒𝐴 𝐴𝓁𝑒𝐵 𝐵± 1 Curva elíptica supersingular 𝐸∕𝔽𝑝2de orden (𝑝± 1)2 Una base ⟨𝑃𝐴, 𝑄𝐴⟩de 𝐸[𝓁𝑒𝐴 𝐴] Una base ⟨𝑃𝐵, 𝑄𝐵⟩de 𝐸[𝓁𝑒𝐵 𝐵] Alicia Bernardo Elegir la clave secreta 𝑆𝐴=𝑃𝐴+ [𝑘𝐴]𝑄𝐴𝑆𝐵=𝑃𝐵+ [𝑘𝐵]𝑄𝐵 Calcula la isogenia secreta 𝜙𝐴∶𝐸→𝐸𝐴=𝐸∕⟨𝑆𝐴⟩𝜙𝐵∶𝐸→𝐸𝐵=𝐸∕⟨𝑆𝐵⟩ Cambiar datos 𝐸𝐴, 𝜙𝐴(𝑃𝐵), 𝜙𝐴(𝑄𝐵)→ ← 𝐸𝐵, 𝜙𝐵(𝑃𝐴), 𝜙𝐵(𝑄𝐴) Calcular el secreto común 𝐸∕⟨𝑆𝐴, 𝑆𝐵⟩=𝐸𝐵∕⟨𝜙𝐵(𝑆𝐴)⟩𝐸∕⟨𝑆𝐵, 𝑆𝐴⟩=𝐸𝐴∕⟨𝜙𝐴(𝑆𝐵)⟩ Cuadro 3.1: Esquema del protocolo SIDH Para ver que ambos 𝑗-invariantes son el mismo se puede argumentar que ambos corresponden a la misma clase de isomorfía 𝐸∕⟨𝑆𝐴, 𝑆𝐵⟩usando la identidad 𝐸∕⟨𝑆𝐴, 𝑆𝐵⟩≅ (𝐸∕⟨𝑆𝐴⟩)∕⟨𝜙(𝑆𝐵)⟩con 𝜙∶𝐸→𝐸∕⟨𝑆𝐴⟩[1]. Este protocolo, y otros basados en isogenias que veremos al final del capítulo, se apoyan en el siguiente diagrama conmutativo: 𝐸𝐸∕⟨𝑆𝐴⟩ 𝐸∕⟨𝑆𝐵⟩𝐸∕⟨𝑆𝐴, 𝑆𝐵⟩ 𝜙𝐴 𝜙𝐵 Ahora vamos a construir un ejemplo de protocolo de intercambio de clave entre Alicia y Bernardo: Parámetros públicos Vamos a retomar los grafos que construimos en la sección anterior con 𝑝= 107 = 2233− 1, y tomamos la curva elíptica pública 𝐸0∶𝑦2=𝑥3+ (24𝑗+ 33)𝑥+ (59𝑗+ 42),con 𝑗(𝐸0) = 81𝛼+ 19 30 criptografía basada en isogenias También vamos a tomar cuatro cualesquiera puntos de 𝐸0de tal forma que 𝐸[22] = ⟨𝑃𝐴, 𝑄𝐴⟩y𝐸[33] = ⟨𝑃𝐵, 𝑄𝐵⟩. Vamos a fijar los puntos: 𝑃𝐴∶= (69𝛼+ 52 ∶ 20𝛼+ 3 ∶ 1) 𝑄𝐴∶= (51𝛼+ 28 ∶ 77𝛼+ 65 ∶ 1) 𝑃𝐵∶= (48𝛼+ 8 ∶ 55𝛼+ 85 ∶ 1) 𝑄𝐵∶= (26𝛼+ 89 ∶ 98𝛼+ 77 ∶ 1) Alicia: Supongamos que escoge la clave secreta 𝑘𝐴= 1, su primer paso será calcular el punto secreto: 𝑆𝐴=𝑃𝐴+ [𝑘𝐴]𝑄𝐴 = (69𝛼+ 52 ∶ 20𝛼+ 3 ∶ 1) + (51𝛼+ 28 ∶ 77𝛼+ 65 ∶ 1) = (84𝛼+ 7 ∶ 35𝛼+ 106 ∶ 1). Este último punto es de orden 4en la curva 𝐸0. Ahora Alicia, ha de calcular su clave pública, para ello necesita calcular (usando la fórmula de Velú [8]) la isogenia: 𝜙𝐴∶𝐸0←→ 𝐸𝐴=𝐸∕⟨𝑆𝐴⟩ Esta isogenia tiene las siguiente representación racional: 𝜙𝐴(𝑥, 𝑦) = (𝑥4+ (−38𝛼− 9)𝑥3+ (−53𝛼− 51)𝑥2+ (15𝛼− 18)𝑥+ (31𝛼+ 24) 𝑥3+ (48𝛼− 43) , 𝑥5𝑦+ (8𝛼− 11)𝑥4𝑦+ (27𝛼+ 41)𝑥3𝑦+ (15𝛼+ 11)𝑥2𝑦+ (32𝛼− 16)𝑥𝑦 + (−𝛼− 21)𝑦 𝑥5+ (8𝛼− 11)𝑥4+ (32𝛼− 25)𝑥3+ (−28𝛼+ 43)𝑥2+ (−44𝛼+ 45)𝑥+ (22𝛼+ 5) ) y la curva 𝐸𝐴que es codominio de 𝜙𝐴es: 𝐸𝐴∶𝑦2=𝑥3+ (106𝛼+ 42)𝑥+ (13𝛼+ 51) con 𝑗(𝐸𝐴) = 72. Nos falta encontrar la imagen, a través de la isogenia, de los puntos 𝑃𝐵y𝑄𝐵. 𝑃′ 𝐵=𝜙𝐴(𝑃𝐵) = (16𝛼+ 38 ∶ 20𝛼+ 54 ∶ 1) 𝑄′ 𝐵=𝜙𝐴(𝑄𝐵) = (8𝛼+ 73 ∶ 43𝛼+ 54 ∶ 1) Por lo tanto la clave pública de Alicia es: 𝑃 𝐾𝐴= ((106𝛼+42),(13𝛼+51), 𝑃 ′ 𝐵= (8𝛼+1 ∶ 83𝛼+45 ∶ 1), 𝑄′ 𝐵= (8𝛼+1 ∶ 24𝛼+62 ∶ 1)). Para identificar la curva basta dar el coeficiente de 𝑥y el coeficiente libre ya que el resto son iguales. 3. criptografía basada en isogenias 31 Bernardo: Supongamos que escoge la clave secreta 𝑘𝐵= 1, este, hace los cálculos de forma análoga a los de Alicia: 𝑆𝐵=𝑃𝐵+ [𝑘𝐵]𝑄𝐵 = (48𝛼+ 8 ∶ 55𝛼+ 85 ∶ 1) + (26𝛼+ 89 ∶ 98𝛼+ 77 ∶ 1) = (103𝛼+ 43 ∶ 22𝛼+ 9 ∶ 1). Este último punto es de orden 27 en la curva 𝐸0. Ahora calcula su clave pública: 𝜙𝐵∶𝐸0←→ 𝐸𝐵=𝐸∕⟨𝑆𝐵⟩ En este caso las ecuaciones racionales de la isogenia son demasiado voluminosas como para escribirla en una sola página, por ello, nos limitaremos a ver el codominio, 𝐸𝐵, de 𝜙𝐵que es la curva: 𝐸𝐵∶𝑦2=𝑥3+ (5𝛼+ 57)𝑥con 𝑗(𝐸𝐵) = 16. Nos falta encontrar la imagen, a través de 𝜙𝐵, de los puntos 𝑃𝐴y𝑄𝐴. 𝑃′ 𝐴=𝜙𝐵(𝑃𝐴) = (56𝛼+ 103 ∶ 32𝛼+ 30 ∶ 1) 𝑄′ 𝐴=𝜙𝐵(𝑄𝐴) = (45𝛼+ 10 ∶ 94𝛼+ 18 ∶ 1) Por lo tanto la clave pública de Bernardo es: 𝑃 𝐾𝐵= ((5𝛼+57),0, 𝑃 ′ 𝐴= (56𝛼+103 ∶ 32𝛼+30 ∶ 1), 𝑄′ 𝐴= (45𝛼+10 ∶ 94𝛼+18 ∶ 1)) Ya tenemos la elección de ambas claves secretas y la publicación de ambas claves públicas. Para el cálculo de estas últimas hemos obtenido dos isogenias de grado 4 y 27 para Alicia y Bernardo, respectivamente, partiendo ambas de la curva 𝐸0. Ya podemos comenzar con el cálculo de la clave compartida, pero antes vamos a conocer un poco más de estas isogénias. Como bien hemos visto tenemos dos isogenias de grado 4 y 27 respectivamente, pero no sabemos cual es el camino aleatorio dentro de los grafos de isogenias. Vamos a descomponer 𝜙𝐴y𝜙𝐵en isogenias de grado 2 y 3 respectivamente para saber cual ha sido el camino que han tomado dentro del grafo correspondiente. Conociendo las claves privadas podemos describir estos caminos. En el caso de Alicia el camino será a través del grafo de 2-isogenias y en el caso de Bernardo a través del grafo de 3- isogenias. Alicia: al ser 𝑆𝐴un punto de orden 22, la isogenia 𝜙𝐴tiene grado 4lo que quiere 32 criptografía basada en isogenias 094 72 68𝛼+ 37 16 47 81𝛼+ 19 26𝛼+ 22 39𝛼+ 95 81 Figura 3.1: El nodo amarillo es el inicial, los nodos azules son los correspondientes a las curvas 𝐸𝐴y𝐸𝐵. decir que es una composición de dos isogenias de grado 2. Para obtener, esas dos isogenias debemos tomas el punto 𝑆𝐴, calcular 𝑅𝐴= [2]𝑆𝐴y usamos el algoritmo de Velú para obtener: 𝜙0∶𝐸0←→ 𝐸1,donde 𝐸1=𝐸0∕⟨𝑅𝐴⟩, 𝜙(𝑥, 𝑦) = (𝑥2+ (23𝛼+ 5)𝑥+ 37 𝑥+ (23𝛼+ 5) ,𝑥2𝑦+ (46𝛼+ 10)𝑥𝑦 + (−8𝛼)𝑦 𝑥2+ (46𝛼+ 10)𝑥+ (−8𝛼+ 37)) Esta 𝜙0es una isogenia de orden 2, cuyo codominio es la curva 𝐸1que tiene como 𝑗-invariante 𝑗(𝐸1) = 47. Debemos observar que el punto 𝑆′ 𝐴=𝜙0(𝑆𝐴)es un punto de orden 2en la curva 𝐸1. Una vez ya tenemos 𝜙0, podemos calcular 𝜙1de forma similar: 𝜙1∶𝐸1←→ 𝐸𝐴donde 𝐸𝐴=𝐸1∕⟨𝑆′ 𝐴⟩ 𝜙(𝑥, 𝑦) = (𝑥2+ (23𝛼− 19)𝑥+ (5𝛼+ 4) 𝑥+ (23𝛼− 19) ,𝑥2𝑦+ (46𝛼− 38)𝑥𝑦 + (−47𝛼+ 48)𝑦 𝑥2+ (46𝛼− 38)𝑥+ (−42𝛼+ 52) ) Así ya sabemos que el camino aleatório 𝜙𝐴que ha tomado Alicia consiste en la composición de las isogenias 𝜙0y𝜙1, i.e., 𝜙𝐴=𝜙0◦𝜙1. En la figura 3.4 podemos ver cual es el correspondiente camino en el grafo. Bernardo: los cálculos en este caso son algo más complejos, no porque a nivel teórico conlleve más tarea si no porque las isogenias son algo más aparatosas de manejar, como ya hicimos notar en la generación de la clave pública. Bernardo hará lo 3. criptografía basada en isogenias 33 094 72 68𝛼+ 37 16 47 81𝛼+ 19 26𝛼+ 22 39𝛼+ 95 81 𝜙𝐴 1 𝜙𝐴 0 Figura 3.2: El camino aleatorio de Alice a través del grafo de 2-isogenias. mismo que ha hecho Alicia, tomar su punto secreto 𝑆𝐵e ir tomando múltiplos de este y sus imágenes para crear el camino hasta el nodo anteriormente indicado. El camino de Bernardo será: 𝜙𝐵 0∶𝐸0→𝐸′ 1con 𝐸′ 1∶𝑦2=𝑥3+ (9𝛼+ 4)𝑥+ (62𝛼+ 2) y𝑗(𝐸′ 1) = 68𝛼+ 37 𝜙𝐵 1∶𝐸′ 1→𝐸′ 2con 𝐸′ 2∶𝑦2=𝑥3+ (79𝛼+ 66)𝑥+ (94𝛼+ 4) y𝑗(𝐸′ 2) = 72 𝜙𝐵 2∶𝐸′ 2→𝐸′ 3con 𝐸𝐵∶𝑦2=𝑥3+ (5𝛼+ 57)𝑥y𝑗(𝐸′ 3) = 16 Entonces tenemos que 𝜙𝐵=𝜙0◦𝜙1◦𝜙2, lo cual nos define el camino dentro del grafos de 3-isogenias que se muestra en la figura 3.5. Intercambio de clave Alicia: Va a hacer el mismo camino que ha hecho en el paso anterior, pero con unas variaciones. Comenzando en la curva de la clave pública de Bernardo y usaremos los puntos de la misma clave para crear, con su clave privada un generador de la isogenia. Es decir, debemos tomar como curva inicial 𝐸𝐵cuyo 𝑗-invariante es 16 y proceder como antes. Primero calculamos el punto secreto: 𝑆𝐴𝐵 =𝑃′ 𝐴+ [𝑘𝐴]𝑄′ 𝐴 = (56𝛼+ 103 ∶ 32𝛼+ 30 ∶ 1) + (45𝛼+ 10 ∶ 94𝛼+ 18 ∶ 1) = (62𝛼+ 97 ∶ 17𝛼+ 48 ∶ 1). 34 criptografía basada en isogenias 094 72 68𝛼+ 37 16 47 81𝛼+ 19 26𝛼+ 22 39𝛼+ 95 81 𝜙𝐵 2 𝜙𝐵 1𝜙𝐵 0 Figura 3.3: El camino aleatorio de Bernardo a través del grafo de 3-isogenias. Y luego la isogenia correspondiente: 𝜙𝐴𝐵 ∶𝐸𝐵←→ 𝐸𝐵𝐴 donde𝐸𝐵𝐴 =𝐸𝐵∕⟨𝑆𝐴𝐵⟩ donde: 𝐸𝐵𝐴 ∶𝑦2+ (73𝛼+ 1)𝑥+ (73𝛼+ 99) 𝑗(𝐸𝐵𝐴) = 68𝛼+ 37. Por lo tanto la clave compartida es 𝑗(𝐸𝐵𝐴) = 68𝛼+ 37. El camino, a través del grafo, que ha seguido en el grafo de 2-isogenias (dibujado en la Figura 3.2) es el siguiente: 𝜙𝐵𝐴 0∶𝐸𝐵→𝐸𝐵,1con 𝐸𝐵,1∶𝑦2=𝑥3+ (55𝛼+ 92)𝑥+ (45𝛼+ 52) y𝑗(𝐸𝐵,1) = 94 𝜙𝐵𝐴 1∶𝐸𝐵,1→𝐸𝐵𝐴 con 𝐸𝐵𝐴 ∶𝑦2=𝑥3+ (73𝛼+ 1)𝑥+ (73𝛼+ 99) y𝑗(𝐸𝐵𝐴) = 68𝛼+ 37 Bernardo: Vamos a repetir lo que ha hecho Alicia pero con sus claves públicas. Es decir, debemos tomar como curva inicial 𝐸𝐴cuyo 𝑗-invariante es 72 y proceder como antes. Primero calculamos el punto secreto: 𝑆𝐵𝐴 =𝑃′ 𝐵+ [𝑘𝐵]𝑄′ 𝐵 = (16𝛼+ 38 ∶ 20𝛼+ 54 ∶ 1) + (8𝛼+ 73 ∶ 43𝛼+ 54 ∶ 1) = (51𝛼+ 79 ∶ 85𝛼+ 51 ∶ 1). 3. criptografía basada en isogenias 35 094 72 68𝛼+ 37 16 47 81𝛼+ 19 26𝛼+ 22 39𝛼+ 95 81 𝜙𝐵𝐴 1 𝜙𝐵𝐴 0 Figura 3.4: El camino aleatorio de Alice a través del grafo de 2-isogenias. Y luego la isogenia correspondiente: 𝜙𝐴𝐵 ∶𝐸𝐵←→ 𝐸𝐴𝐵 donde𝐸𝐴𝐵 =𝐸𝐴∕⟨𝑆𝐵𝐴⟩ donde: 𝐸𝐴𝐵 ∶𝑦2=𝑥3+ (73𝛼+ 1)𝑥+ (73𝛼+ 99) 𝑗(𝐸𝐴𝐵) = 68𝛼+ 37. Por lo tanto la clave compartida es 𝑗(𝐸𝐵𝐴) = 68𝛼+ 37 también. El camino, a través del grafo, que ha seguido en el grafo de 3-isogenias (dibujado en la Figura 3.3) es el siguiente: 𝜙𝐵𝐴 0∶𝐸𝐴→𝐸𝐴,1con 𝐸𝐴,1∶𝑦2=𝑥3+ (98𝛼+ 57)𝑥+ (77𝛼+ 14) y𝑗(𝐸𝐴,1) = 72 𝜙𝐵𝐴 1∶𝐸𝐴,1→𝐸𝐴,2con 𝐸𝐴,2∶𝑦2=𝑥3+ (85𝛼+ 19)𝑥+ (89𝛼+ 34) y𝑗(𝐸𝐴,2) = 39𝛼+ 95 𝜙𝐵𝐴 1∶𝐸𝐴,2→𝐸𝐴𝐵 con 𝐸𝐴𝐵 ∶𝑦2=𝑥3+ (73𝛼+ 1)𝑥+ (73𝛼+ 99) y𝑗(𝐸𝐵𝐴) = 68𝛼+ 37 Con este protocolo, Alicia y Bernardo han podido compartir una clave, 68𝛼+ 37, sin que un tercero pueda obtenerla a pesar de la información pública. 42 criptografía basada en isogenias return L ###### # # A partir de quí ya podemos escoger el p de la lista que más nos interese. # ##### N=200 p=primer_prime2(pA,pB,N)[11][0] print(’ --- La elección del primo ha sido: ’"{}".format(p)) print(’ ’) ############# # # El siguiente procedimiento nos sirve para encontrar los j-invariantes # de curvas supersingulares en Fp^2. # ############## from sage.schemes.elliptic_curves.ell_finite_field import is_j_supersingular, supersingular_j_polynomials S=[j for j in GF(p^2,’j’) if is_j_supersingular(j)] print(’ --- Los j-invariantes de curvas supersingulares --- ’) print(’ ’) print(S) print(’ ’) ############ # # A continuación definimos los polinomios l-modulares. Cuyas # raíces (j1,j2) nos indican las aristas entre j-invariantes # (isomorfas en ext(K)) que son isogenas entre si, es # decir, que existe una isogenia entre una curva con 4. programación sage 43 # j-invariante j1 y otra con j-invariante j2. # ############# R.<x,y>=PolynomialRing(GF(p^2,’j’)); x, y = R.gens() Phi2=x^3-x^2*y^2 + 1488*x^2*y- 162000*x^2 + 1488*x*y^2+ 40773375*x*y + 8748000000*x + y^3- 162000*y^2 + 8748000000*y- 157464000000000; Phi3=x^4+36864000*x^3+452984832000000*x^2+1855425871872000000000*x+ y^4+36864000*y^3+452984832000000*y^2+1855425871872000000000*y -x^3*y^3+2587918086*x^2*y^2-770845966336000000*x*y+2232*x^3*y^2 -1069956*x^3*y+8900222976000*x^2*y+2232*y^3*x^2-1069956*y^3*x +8900222976000*y^2*x ############### # # Usamos los polinomios modulares para obtener las aristas de los # grafos de 2-isogenias y 3-isogenias. # ############### Graph_edges2=[] s=len(S) for i in range(s): for k in range(i,s): if Phi2(S[i],S[k])==0: Graph_edges2.append((S[i],S[k])) print(’ --- Aristas de 2-isogenias ---’) print(Graph_edges2) print(’ ’) Graph_edges3=[] s=len(S) for i in range(s): 44 criptografía basada en isogenias for k in range(i,s): if Phi3(S[i],S[k])==0: Graph_edges3.append((S[i],S[k])) print(’--- Aristas de 3-isogenias ---’) print(Graph_edges3) print(’ ’) ################ # # Construímos el grafo que vamos a usar para hacer el protocolo # de intercambio de clave. # ############ print(’--- Dibujamos los grafos:’) g2 = Graph({}, loops=True, sparse=True) g2.add_edges(Graph_edges2) g2.name("Grafo de 2-isogenias") g2.show() g3 = Graph({}, loops=True, sparse=True) g3.add_edges(Graph_edges3) g3.name("Grafo de 2-isogenias") g3.show() Graph_edgesL2=[i for i in Graph_edges2 if not i[0]==i[1]] Graph_edgesL3=[i for i in Graph_edges3 if not i[0]==i[1]] ############## # # Escojemos uno de los j-invariantes y encontramos una curva de # la clase de isomorfismo. Esta curva será la curva común # para Alice y Bob. Vamos a tomar un j-invariante que # tenga el máximo grado en ambos grafos. Con el fin de el # ejercicio sea más visual. # 4. programación sage 45 ############## ##### # # Calculamos el grado de los j-invariantes en cada grafo. # ##### Grade_List2=[] s=len(S) t=len(Graph_edgesL2) for i in range(s): count=0 for j in range(t): if (S[i]==Graph_edgesL2[j][0] or S[i]==Graph_edgesL2[j][1]): count=count+1 Grade_List2.append([S[i],count]) Grade_List3=[] s=len(S) t=len(Graph_edgesL3) for i in range(s): count=0 for j in range(t): if (S[i]==Graph_edgesL3[j][0] or S[i]==Graph_edgesL3[j][1]): count=count+1 Grade_List3.append([S[i],count]) ##### # # Calculamos aquellos que tengan grado máximo en ambos grafos. # ##### Max_Grade=[S[i] for i in range(len(S)) if (Grade_List2[i][1]==3 and Grade_List3[i][1]==4)] ##### 46 criptografía basada en isogenias # # Tomamos un j-invariante aleatoriamente y generamos una curva con # ese j-invariante. # ##### j0=Set(Max_Grade).random_element() E_0=EllipticCurve(j=j0) print(’ ’) print(’--- La curva pública es: ’"{}".format(E_0)) print(’--- --- su j-invariante es: ’"{}".format(j0)) print(’ ’) ## # Veamos qué estructura tiene como grupo. ## A = E_0.abelian_group() print(’La estructura de grupo de la curva es: ’"{}".format(A)) ########## # # Buscamos P_A, Q_A puntos que generan E[pA^eA]. Para ello, # encontramos el grupo de torsión y luego escogemos dos # puntos distintos que generen el cjto. # ########## Ta=E_0.torsion_polynomial(pA^eA).roots(multiplicities=0) ######################################################## # # La diferencia entre E_torsion_A_red y E_torsion_A es que en el # segundo solo hay un elemento con primera coordenada igual. # De esta manera nos aseguramos que al escoger dos puntos 4. programación sage 47 # sean distintos y que te generen todo el grupo de torsión. # La siguiente lista E_torsion_A_red_red se encarga de tomar # los puntos de máximo orden para encontrar más fácilmente # los generadores. # ######################################################## E_torsion_A=[E_0.lift_x(a, all=True) for a in Ta ] E_torsion_A_red=[E_0.lift_x(a) for a in Ta ] E_torsion_A_red_red=[i for i in E_torsion_A_red if i.order() == pA^eA ] Comp2=[] tc_a= len(E_torsion_A_red_red) while (is_sublist(Comp2,flatten(E_torsion_A)) & is_sublist(flatten(E_torsion_A),Comp2))== False: rtc_a=random_select_dif_pair(tc_a,True) (P_A, Q_A)= (E_torsion_A_red_red[rtc_a[0]],E_torsion_A_red_red[rtc_a[1]]) Comp2=[n*P_A+m*Q_A for n in range(pA^eA) for m in range(pA^eA)] Comp2.pop(0) # Quitamos el primer elemento que es el (0:1:0) Tr2=is_sublist(Comp2,flatten(E_torsion_A)) & is_sublist(flatten(E_torsion_A),Comp2) print(’ ’) print(’ --- Los puntos que generan E[pA^eA] son:’) print(’ --- --- P_A=’"{}".format(P_A)) print(’ --- --- Q_A=’"{}".format(Q_A)) print(’ --- --- ¿Generan E[pA^eA]? ’"{}".format(Tr2)) ###### # # Repetimos el proceso para obtener los puntos P_B y Q_B que generen E[pB^eB]. # ###### E_0.torsion_polynomial(pB^eB) Tb=E_0.torsion_polynomial(pB^eB).roots(multiplicities=0) 48 criptografía basada en isogenias E_torsion_B=[E_0.lift_x(b, all=True) for b in Tb ] E_torsion_B_red=[E_0.lift_x(b) for b in Tb ] E_torsion_B_red_red=[i for i in E_torsion_B_red if i.order() == pB^eB ] Comp3=[] tc_b= len(E_torsion_B_red_red) while (is_sublist(Comp3,flatten(E_torsion_B)) & is_sublist(flatten(E_torsion_B),Comp3))== False: rtc_b=random_select_dif_pair(tc_b,True) (P_B, Q_B)= (E_torsion_B_red_red[rtc_b[0]],E_torsion_B_red_red[rtc_b[1]]) Comp3=[n*P_B+m*Q_B for n in range(pB^eB) for m in range(pB^eB)] Comp3.pop(0) # Quitamos el primer elemento que es el (0:1:0) Tr3=is_sublist(Comp3,flatten(E_torsion_B)) & is_sublist(flatten(E_torsion_B),Comp3) print(’ ’) print(’ --- Los puntos que generan E[pB^eB] son:’) print(’ --- --- P_B=’"{}".format(P_B)) print(’ --- --- Q_B=’"{}".format(Q_B)) print(’ --- --- ¿Generan E[pB^eB]? ’"{}".format(Tr3)) ###### # # Ahora llega el momento de que Alicia escoja una clave privada y calcule # su clave pública. # ###### ######################################### # # # Ahora Alice debe escoger kA en # # Z/ZpA^eA SECRETA de tal manera # # que no sea divisible por pA # kA= 1 # # # ######################################### Sa=P_A+kA*Q_A 4. programación sage 49 print(’ ’) print(’ --- La clave secreta de Alicia es:’) print(’ --- --- kA=’"{}".format(kA)) print(’ --- --- Sa=’"{}".format(Sa)) print(’ ’) ###### # # Vamos a calcular la Isogenia cuyo kernel lo genere Sa. # ###### PhiA = E_0.isogeny([Sa]); E_A=PhiA.codomain() j_A=E_A.j_invariant() print(’ --- La isogenia secreta de Alicia es:’) print(’ --- --- ’"{}".format(PhiA)) print(’ --- --- El codominio es ’"{}".format(E_A)) print(’ --- --- j(E_A)=’"{}".format(j_A)) P_Bp=PhiA(P_B) Q_Bp=PhiA(Q_B) print(’ --- El camino que sigue en el grafo es:’) L2=camino_isogenias(E_0,Sa) print(table(L2,header_row=["Curva","j-invariante"])) ######################################### # # # Ahora Bernardo debe escoger kB # # en Z/ZpB^eB SECRETO de tal manera # # que no sea divisible por pB # kB= 1 # # # ######################################### 50 criptografía basada en isogenias Sb=P_B+kB*Q_B print(’ ’) print(’ --- La clave secreta de Bernardo es:’) print(’ --- --- kB=’"{}".format(kB)) print(’ --- --- Sb=’"{}".format(Sb)) print(’ ’) ###### # # Vamos a calcular la Isogenia cuyo kernel lo genere Sa. # ###### PhiB = E_0.isogeny([Sb]); E_B=PhiB.codomain() j_B=E_B.j_invariant() print(’ --- La isogenia secreta de Bernardo es:’) print(’ --- --- ’"{}".format(PhiB)) print(’ --- --- El codominio es ’"{}".format(E_B)) print(’ --- --- j(E_B)=’"{}".format(j_B)) print(’ ’) P_Ap=PhiB(P_A) Q_Ap=PhiB(Q_A) print(’ --- El camino que sigue en el grafo es:’) L3=camino_isogenias(E_0,Sb) print(table(L3,header_row=["Curva","j-invariante"])) ######### # # Las claves de cada uno son: print(’ --- Alicia PKa:’) print(’ --- E_A:’"{}".format(E_A)) 4. programación sage 51 print(’ --- P_Bp:’"{}".format(P_Bp)) print(’ --- Q_Bp:’"{}".format(Q_Bp)) print(’ ’) print(’ --- Bernardo PKb:’) print(’ --- E_B:’"{}".format(E_B)) print(’ --- P_Ap:’"{}".format(P_Ap)) print(’ --- Q_Ap:’"{}".format(Q_Ap)) # ######### ############### # # Ahora vamos a calcular el intercambio de clave. # ############### ############### # # Vamos a empezar por Alicia. Primero calculamos el punto Sap y # luego calculamos la isogenia que tiene como núcleo el # espacio que genera Sap. # ############### Sap=P_Ap+kA*Q_Ap PhiAB=E_B.isogeny(Sap) E_AB=PhiAB.codomain() j_AB=E_AB.j_invariant() print(’ ’) print(’ --- El j-invariante al que llega Alicia es ’"{}".format(j_AB)) ############### # # Continuamos con Bernardo. Primero calculamos el punto Sbp y # luego calculamos la isogenia que tiene como núcleo el # espacio que genera Sbp.