Criptografía con curvas elípticas

Lección 1. Criptosistemas basados en el problema del logaritmo discreto
Lección 2. Curvas elípticas en seguridad web
Lección 3. Criptografía con emparejamientos
Lección 4. Protocolos criptográficos con curvas elípticas

---

Lección 3: Criptografía con emparejamientos. Fecha de publicación: 05/12/2017
Josep M. Miret, Jordi Pujolàs & Javier Valera - Grupo de Investigación Cryptography & Graphs: www.cig.udl.cat, Universitat de Lleida.

Twittear

Temario

Apartado 3.1. Emparejamientos
Apartado 3.2. Intercambio de claves a tres partes
Apartado 3.3. Criptografía basada en la identidad
Apartado 3.4. Firmas digitales cortas
Apartado 3.5. Los emparejamientos de Tate y de Weil
Apartado 3.6. Curvas pairing-friendly
Apartado 3.7. Ejercicios
Apartado 3.8. Referencias bibliográficas

La criptografía basada en la identidad, ideada hace más de 20 años por A. Shamir [Sha] a partir de emparejamientos entre curvas, continúa despertando hoy en día un gran interés. Permite evitar los certificados de clave pública y, por tanto, aumentar la simplicidad de los protocolos criptográficos en las comunicaciones seguras. Es por tanto especialmente adecuada para claves públicas efímeras, ya que de esta manera se evita tener que hacer uso de las listas de revocación de certificados.

En esta tercera lección de este curso mostraremos, usando emparejamientos, un intercambio de claves a tres partes, una firma digital corta y el esquema basado en la identidad propuesto por Boneh y Franklin. También veremos cómo obtener curvas buenas para estos criptosistemas, las denominadas pairing-friendly curves, donde debe conseguirse un equilibrio entre la resistencia del logaritmo discreto y la eficiencia para el cómputo del emparejamiento.

El material de esta lección se basa principalmente en [BSS] y [Gal]. Para ilustrar los algoritmos y los protocolos criptográficos, se usará como en las lecciones anteriores el software matemático SAGE. Aún así existe la librería jPBC para Java que nos permite trabajar fácilmente con pairings y es de licencia LGPL [jPBC].

---

APARTADO 3.1. EMPAREJAMIENTOS

Dados dos grupos aditivos $ ( G_1 , + ) $ y $ ( G'_1 , + ) $ con neutro $ 0 $ y un grupo multiplicativo $ ( G_2 , \cdot ) $ con neutro $ 1 $, un emparejamiento o pairing es una aplicación $$ e : G_1 \times G'_1 \to G_2 $$ que satisface las siguientes propiedades:

• Bilineal: $$ \begin{array}{c} e( P + P' , Q ) = e( P , Q ) \cdot e( P' , Q ) , \quad \forall P , P' \in G_1 , \quad \forall Q \in G'_1 \\ e( P , Q + Q' ) = e( P , Q ) \cdot e( P , Q' ) , \quad \forall P \in G_1 , \quad \forall Q , Q' \in G'_1 \end{array} $$
• No degenerado: $$ \begin{array}{c} \forall P \in G_1 , \; P \neq 0 , \; \exists Q \in G'_1 \mbox{ tal que } e( P , Q ) \neq 1 \\ \forall Q \in G'_1 , \; Q \neq 0 , \; \exists P \in G_1 \mbox{ tal que } e( P , Q ) \neq 1 \end{array} $$

Si $ G_1 = G'_1 $, el emparejamiento $ e $ se dice que es simétrico.

Los emparejamientos computables en la práctica son fundamentalmente los emparejamientos de Tate y de Weil, que se detallan en el apartado 3.5. No obstante en la mayoría de protocolos criptográficos que usan emparejamientos, éstos aparecen a modo de caja negra omitiendo la necesidad de conocer su funcionamiento interno. Éste es precisamente el enfoque que tomamos en los siguientes apartados, donde el cálculo queda escondido en una función llamada Pairing. En dicha función, la curva elíptica $ E $ tiene por ecuación $ y^2 = x^3 + x $. Además, $ E $ es supersingular. Los puntos $ P $ y $ Q $, siendo $ Q $ un múltiplo de $ P $, tienen orden $ n $. Tal y como podemos observar, la función Pairing llama a la función RTP, la cual, tal y como veremos en el apartado 3.5, es la implementación del emparejamiento de Tate reducido. Sin entrar en muchos detalles, si $ E $ está definida sobre un cuerpo finito $ \mathbb F_p $, la función Pairing devuelve un elemento de $ \mathbb F_{p^2} = \mathbb F_p[ x ] / ( x^2 + 1 ) $.

Problemas computacionales asociados a un emparejamiento

La seguridad de los protocolos criptográficos que detallaremos en esta lección recae en última instancia en si un ordenador puede o no puede resolver un problema determinado de un modo eficiente. En nuestro caso, los problemas que sustentan la criptografía con emparejamientos están relacionados con el problema del logaritmo discreto (DLP) en un grupo cíclico $ G $ de orden $ n $. Así, los protocolos que presentaremos no tienen sentido sin un grupo $ G $ donde el DLP sea computacionalmente irresoluble, ya que de otro modo el cálculo de emparejamientos se convierte en una tarea trivial.

Sobre un DLP "robusto" en $ ( G , \cdot ) $, los problemas originales involucrados en algunos protocolos criptográficos son el problema computacional de Diffie-Hellman (CDHP) y el problema decisional de Diffie-Hellman (DDHP).

El problema que permite sacarle partido a los emparejamientos es el problema bilineal de Diffie-Hellman (BDHP), en cuyo enunciado, en su versión simétrica, aparece implícito que $ P $ es un generador (conocido) de un grupo cíclico $ ( G_1 , + ) $ de orden $ n $, $ e : G_1 \times G_1 \to G_2 $ es un emparejamiento tal que $ e( P , P ) \neq 1 $, y donde se supone que el DLP es inatacable en $ G_1 $ y $ G_2 $:

En la versión asimétrica, este problema consiste en: dados $ P $ (generador de $ G_1 $), $ aP $, $ bP $ en $ G_1 $ tales que $ 1 < a , b < n $ son escogidos aleatoriamente, y $ Q $ en $ G_1'$, calcular $ e( P , Q )^{ab} $.

Lo importante para la criptografía basada en emparejamientos es que existe una reducción entre los problemas BDHP < DLP en el sentido de que si se puede resolver un problema $ B $ entonces $ A < B $ indica que también se puede resolver $ A $.

Así la criptografía con emparejamientos cobra su sentido cuando se cumple:

1. DLP es intratable en $ ( G_1 , + ) $ y $ ( G_2 , \cdot ) $.
2. Las operaciones en $ G_1 $ y $ G_2 $ son eficientes.
3. Existe un emparejamiento $ e : G_1 \times G_1 \to G_2 $ cuyos valores son eficientemente computables.
4. BDHP es intratable para el emparejamiento $ e : G_1 \times G_1 \to G_2 $.

Los grupos de puntos de las llamadas curvas pairing-friendly satisfacen todos estos requisitos (ver apartado 3.6).

En esta situación, los DLP en los grupos $ G_1$ y $ G_2 $ quedan vinculados computacionalmente mediante el emparejamiento, ya que sus propiedades hacen que la resolución del DLP en $ G_2 $ permita la resolución del DLP en $ G_1 $. Este tipo de "transfer" se describe en [MOV], [FR].

---

APARTADO 3.2. INTERCAMBIO DE CLAVES A TRES PARTES

Uno de los inconvenientes de los criptosistemas simétricos es la distribución de claves, en el sentido que dos usuarios que quieren comunicarse de forma cifrada deben previamente pactar su clave secreta o enviársela por un canal seguro. W. Diffie y M.E. Hellman propusieron en 1976 un protocolo de intercambio de claves seguro [DH]. Su primera patente la firmaron junto con R.C. Merkle, si bien el protocolo es conocido actualmente como Diffie-Hellman key exchange.

La idea fundamental en la que se basa es la que originó que poco después surgieran los criptosistemas de clave pública, en los que no es necesario compartir ninguna información secreta. La seguridad radica en la intratabilidad computacional del problema del logaritmo discreto.

Intercambio de claves de Diffie-Hellman

Para el intercambio de claves de Diffie-Hellman entre dos usuarios $ A $ y $ B $ basta considerar un grupo $ ( G , \cdot ) $ de orden $ n $ y un generador $ g $. Si $ A $ y $ B $ quieren tener una clave en común, pueden escoger dos enteros $ a $ y $ b $, respectivamente, tales que $ 1 < a , b < n $. Entonces $ A $ hace público $ g^a $ y $ B $ hace público $ g^b $. Pero ahora $ A $ puede calcular $ (g^b)^a $ y $ B $ puede calcular $ (g^a)^b $. De este modo, los dos comparten la clave $$ g^{ab} = (g^a)^b = (g^b)^a . $$

Notemos que obtener $ g^{ab} $ conociendo $ g $, $ g^a $ y $ g^b $ es difícil en un grupo $ G $ en el que el problema del logaritmo discreto es computacionalmente difícil. Esto significa que no podemos obtener $ a $ y $ b $ a partir de $ g $, $ g^a $ y $ g^b $. No obstante, lo estrictamente necesario para impedir obtener $ g^{ab} $ es considerar un grupo en el que sea computacionalmente difícil el problema computacional de Diffie-Hellman (CDHP), es decir, dados $ g $, $ g^a $ y $ g^b $, es difícil determinar $ g^{ab} $.

Intercambio de claves con emparejamientos

Los emparejamientos permiten diseñar un protocolo de intercambio de claves entre tres usuarios. A. Joux propuso en 2004 un intercambio a tres bandas en el que solo es necesario una ronda para establecer la clave compartida [Jou].

Si $ A $, $ B $ y $ C $ quieren tener una clave en común, pueden escoger tres enteros $ a $, $ b $ y $ c $, respectivamente, tales que $ 1 < a , b , c < n $. Entonces, $ A $ hace público $ aP $, $ B $ hace público $ bP $ y $ C $ hace público $ cP $. Pero ahora $ A $ puede calcular $ e( bP , cP )^a $, $ B $ puede calcular $ e( aP , cP )^b $ y $ C $ puede calcular $ e( aP , bP )^c $. Así los tres comparten la clave $$ e( P , P )^{abc} = e( bP , cP )^a = e( aP , cP )^b = e( aP , bP )^c . $$ En este caso, para garantizar la seguridad del protocolo tenemos que suponer que el problema bilineal de Diffie-Hellman (BDHP) para el emparejamiento simétrico $ e $ con $ e( P , P)\ne 1 $ es computacionalmente difícil, es decir, dados $ P $, $ aP $, $ bP $ y $ cP $, es difícil determinar $ e( P , P )^{abc} $.

A continuación mostramos un ejemplo en SAGE de intercambio de claves con emparejamientos.

---

APARTADO 3.3. CRIPTOGRAFÍA BASADA EN LA IDENTIDAD

Para evitar los inconvenientes de la verificación de las claves públicas, Shamir propuso en 1984 [Sha] un nuevo paradigma: la criptografía basada en la Identidad, en la cual la clave pública de un usuario es su propio nombre o cualquier otro atributo ligado a su identidad. Este nuevo esquema es ideal para grupos de usuarios de una misma empresa o institución, en la que su oficina central puede actuar como generador de claves en la que todos confían.

Antes de introducir este paradigma, veamos los certificados de claves públicas que son necesarios verificar en una infraestructura de clave pública. Supongamos que $ A $ y $ B $ son dos usuarios o entidades que tienen sendos certificados de sus claves públicas facilitados por una autoridad certificadora (CA). Supongamos además que $ A $ quiere enviar un mensaje a $ B $. Entonces:

• El emisor $ A $ debe:
  • Verificar 1 firma digital (del certificado de $ B $)
  • Calcular 1 cifrado (usando la clave pública de $ B $)
  • Firmar el mensaje (usando su propia clave privada)
• El receptor $ B $ debe:
  • Verificar 1 firma digital (del certificado de $ A $)
  • Verificar 1 firma digital (del mensaje de $ A $)
  • Calcular 1 descifrado (usando su propia clave privada)

En criptografía basada en la Identidad, el emisor puede usar la Identidad del receptor como su clave pública y no es necesario obtener y verificar su certificado. El atributo ligado a la identidad de cada usuario se suele transformar (mediante una función hash) en un elemento propio del sistema.

Presentamos a continuación un esquema de encriptación basado en la Identidad propuesto en 2001 por Boneh-Franklin [BF], que requiere el uso de emparejamientos. Para la configuración del criptosistema necesitamos un grupo aditivo $ G_1 $ de orden $ q $ con generador $ P $ y un grupo multiplicativo $ G_2 $ tales que en ambos grupos el DLP sea intratable. Además de la función hash que transforma el atributo ligado a la identidad de cada usuario en un elemento de $ G_1 $ necesitamos otra función hash $ h : G_2 \to \{ 0 , 1 \}^n $ y un emparejamiento simétrico $ e : G_1 \times G_1 \to G_2 $ eficientemente computable tal que $ e( P , P ) \neq 1 $.

La autoridad certificadora (CA) elige una clave secreta global $ s $. La clave pública global será $ sP $. Asimismo, cada usuario tiene su clave pública $ Q_A \in G_1 $, así como su clave privada $ D_A = sQ_A $. Si un usuario $ B $ quiere enviar un mensaje cifrado a un usuario $ A $, los procesos de cifrado y descifrado son los siguientes:

La seguridad del sistema se basa en la dificultad del BDHP: dados $ P $, $ sP $, $ U = rP $, $ Q_A = tP $, es difícil calcular $ e( D_A , U ) = e( P , P )^{rst} $.

---

APARTADO 3.4. FIRMAS DIGITALES CORTAS

Presentamos en este apartado el esquema de firma digital creado por Boneh, Lynn y Shacham en 2004 [BLS], que utiliza emparejamientos. Para los procesos de generación y verificación necesitamos un grupo aditivo $ G_1 $ con generador $ P $, un grupo multiplicativo $ G_2 $, ambos con un DLP intratable, un emparejamiento simétrico $ e : G_1 \times G_1 \to G_2 $ tal que $ e( P , P ) \neq 1 $ y una función hash $ h : \{ 0 , 1 \}^n \to G_1 $.

Este esquema de firma digital utiliza claves de longitud 170 bits versus los 320 bits para el esquema de firma DSA.

La seguridad de la generación de la firma se basa en la dificultad del DLP en $ G_1 $ y $ G_2$. La verificación de la firma es factible debido a la efectividad de cómputo del emparejamiento y a sus propiedades de bilinealidad (ver [BLS] para más detalles).

---

APARTADO 3.5. LOS EMPAREJAMIENTOS DE TATE Y DE WEIL

Antes de introducir los emparejamientos de Tate y de Weil, unos de los más usados actualmente, repasaremos aquellos conceptos sobre divisores que son necesarios para definirlos.

Divisores

Sea $ E $ una curva elíptica sobre un cuerpo finito $ \mathbb F_q $. Un divisor de $ E $ es una combinación lineal de puntos $ P \in E( \overline{\mathbb F_q} ) $ con coeficientes enteros que expresamos en la forma $$ D = \sum_{P \in E( \overline{\mathbb F_q} )} m_P( P ) , $$ con un número finito de $ m_P \in \mathbb Z $ no nulos. Para que el divisor esté definido sobre $ \mathbb F_q $ tiene que ser invariante por la acción del grupo de Galois $ G = Gal( \overline{\mathbb F_q} / \mathbb F_q ) $.

El conjunto de divisores $ Div( E ) $ sobre la curva $ E $ con la operación $ + $ definida de forma natural tiene estructura de grupo abeliano $ ( Div( E ) , + ) $. El soporte de un divisor $ D = \sum_P m_P( P ) $ que denotamos $ sup( D ) $ es el conjunto de los puntos $ P $ tales que $ m_P \neq 0 $. El grado de un divisor $ D = \sum_P m_P( P ) $ es el entero $$ \deg( D ) = \sum_P m_P . $$ El conjunto de los divisores de grado $ 0 $ forman un subgrupo $ Div^0( E ) $ de $ ( Div( E ) , + ) $. Una clase distinguida de divisores de grado $ 0 $ son los divisores asociados a una función racional definida sobre la curva, denominados divisores principales. Si $ f $ es una función racional de $ E $, denotaremos por $ div( f ) $ el divisor de ceros y polos de $ f $. Éstos forman un subgrupo $ Prin( E ) $ de $ Div^0( E ) $. Los divisores $ D , D' \in Div( E ) $ tales que $ D - D' \in Prin( E ) $ decimos que son equivalentes. Notemos también que existe un morfismo de grupos que a cada divisor de grado $ 0 $ le asigna un punto de la curva sobre $ \overline{\mathbb F_q} $: $$ \begin{array}{ccc} Div^0( E ) & \to & E( \overline{\mathbb F_q} ) \\ \sum_{P \in E( \overline{\mathbb F_q} )} m_P( P ) & \mapsto & \sum_{P \in E( \overline{\mathbb F_q} )} m_P P \end{array} $$ El núcleo está formado por los divisores de $ Prin( E ) $ y, por tanto, $ Div^0( E ) / Prin( E ) $ y $ E( \overline{\mathbb F_q} ) $ son grupos isomorfos.

Si $ f $ es una función sobre la curva $ E $ y $ D = \sum_P m_P( P ) $ es un divisor de grado $ 0 $ tal que el soporte de $ D $ es disjunto con el soporte de $ div( f ) $, se define $$ f( D ) = \prod_P f( P )^{m_P} . $$ Notemos que si $ g = cf $, siendo $ c $ una constante no nula, y $ D $ es un divisor de grado $ 0 $, entonces $ g( D ) = f( D ) $.

El algoritmo de Miller

Dada una curva elíptica $ E $ sobre un cuerpo finito $ \mathbb F_q $, los emparejamientos de Tate y de Weil se definen a partir de ciertas funciones racionales $ f_{n, P} $ sobre $ E $, siendo $ n $ un número coprimo con $ q $ y $ P $ un punto de $ E( \mathbb F_q ) $ de orden $ n $. Estas funciones se eligen de manera que su divisor de ceros y polos sea $$ div( f_{n, P} ) = n( P ) - n( \mathcal O ) . $$ Más en general, cuando $ n $ no es el orden de $ P $, la función $ f_{n, P} $ se puede definir de forma que $$ div( f_{n, P} ) = n( P ) - ( nP ) - ( n - 1 )( \mathcal O ) . $$ El algoritmo de Miller [Mil] calcula las funciones $ f_{n, P} $ de forma recursiva a partir de las igualdades $$ f_{0, P} = f_{1, P} = 1 , \quad f_{r + s, P} = f_{r, P} f_{s, P} g_{rP, sP} , $$ siendo $ g_{R, S} = \frac{l}{v}$, donde $ l = 0 $ es la ecuación de la recta que pasa por $ R $ y por $ S $, si $ R \neq S $, o la recta tangente a la curva en $ R $ si $ R = S $, y $ v = 0 $ es la ecuación de la recta que pasa por $ R + S $ y por $ - ( R + S ) $. Damos a continuación el algoritmo que calcula $ f_{n, P}( D ) $, siendo $ D $ el divisor $ ( Q + R ) - ( R ) $ de manera que $$ sup( D ) \cap sup( div( f_{n, P} ) ) = \emptyset . $$

El emparejamiento de Tate

Sea $ E $ una curva elíptica definida sobre $ \mathbb F_q $ y sea $ n $ un divisor de su cardinal coprimo con $ q $. Sea $ E( \mathbb F_q )[ n ] $ el subgrupo de puntos de $ n $-torsión de $ E( \mathbb F_q ) $, es decir, $$ E( \mathbb F_q )[ n ] = \{ P \in E( \mathbb F_q ) \mid n P = \mathcal O \} , $$ y sea $ n E( \mathbb F_q ) = \{ n Q \mid Q \in E( \mathbb F_q ) \} $. Entonces $ n E( \mathbb F_q ) $ es un subgrupo de $ E( \mathbb F_q ) $ y se puede formar el cociente $ E( \mathbb F_q ) / n E( \mathbb F_q ) $.

Dados $ P \in E( \mathbb F_q )[ n ] $ y $ Q \in E( \mathbb F_q ) $, para definir su emparejamiento de Tate se consideran los divisores $$ div( f_{n, P} ) = n( P ) - n( \mathcal O ) , \quad D = ( Q + R ) - ( R ) , $$ para $ R \in E( \overline{\mathbb F_q} ) $ tal que los soportes de $ div( f_{n, P} ) $ y $ D $ sean dijuntos. Entonces se define el emparejamiento de Tate, denominado también de Tate-Lichtenbaum, como $$ \begin{array}{cccc} t_n : & E( \mathbb F_q )[ n ] \times E( \mathbb F_q ) / n E( \mathbb F_q ) & \to & \mathbb F_q^* / ( \mathbb F_q^* )^n \\ & ( P , Q ) & \mapsto & f_{n, P}( D ) . \end{array} $$ Esta definición es independiente del representante $ Q $ de su clase. El cálculo del valor $ f_{n, P}( D ) $ se lleva a cabo mediante el Algoritmo de Miller. Nótese también que el valor del emparejamiento es una clase módulo potencias $ n $-ésimas de $ \mathbb F_q^* $. Para eliminar esta ambigüedad se trabaja con una versión simplificada $ \hat t_n $.

El emparejamiento de Tate reducido

Este emparejamiento $ \hat t_n $ no es más que una modificación del emparejamiento $ t_n $ que resuelve la ambigüedad del valor $ t_n( P , Q ) $ como clase módulo potencias $ n $-ésimas.

El exponente de la mínima extensión de $ \mathbb F_q $ que contiene el subgrupo de las raíces $ n $-ésimas de $ 1 $ es el llamado grado de inmersión respecto a $ n $, es decir, el menor natural $ k $ tal que $ n \mid ( q^k - 1 ) $. De este modo, si denotamos por $ \mu_n $ el subgrupo de $ \mathbb F_{q^k}^* $ de raíces $ n $-ésimas de $ 1 $ resulta que $$ t_n( P , Q )^{ ( q^k - 1 ) / n } \in \mu_n . $$

Habitualmente aún se simplifica un poco más $ t_n $ considerando curvas $ E $ sobre $ \mathbb F_q $ y un primo $ \ell $, coprimo con $ q $, que divida el cardinal $ \# E( \mathbb F_q ) $ y de modo que $ \ell^2 $ divida $ \# E( \mathbb F_{q^k} ) $. Así se consigue que se pueda tomar $ E( \mathbb F_{q^k} )[ \ell ] $ en lugar de $ E( \mathbb F_{q^k} ) / \ell E( \mathbb F_{q^k} ) $. En la práctica se necesita un punto $ Q \in E( \mathbb F_{q^k} ) - E( \mathbb F_q )$ de modo que $ P $ y $ Q $ sean una base de toda la $ \ell $-torsión $ E( \overline{\mathbb F_q} )[ \ell ] $. Con todas estas modificaciones el emparejamiento de Tate reducido se puede definir como $$ \begin{array}{cccc} \hat t_\ell : & E( \mathbb F_q )[ \ell ] \times E( \mathbb F_{q^k} )[ \ell ] & \rightarrow & \mu_\ell \\ & ( P , Q ) & \mapsto & t_\ell( P , Q )^{ ( q^k - 1 ) / \ell } . \end{array} $$

Consideremos la curva elíptica $ E \ : \ y^2 = x^3 + 96x + 14 $ definida sobre $ \mathbb F_{103} $. Entonces $ \# E( \mathbb F_{103} ) = 3^2 \cdot 13 $. Para $ \ell = 13 $ tenemos que $ k = 2 $. Escribamos $ \mathbb F_{103^2} = \mathbb F_{103}( w ) $ con $ w^2 + 95w + 20 = 0 $. Sean $ P = ( 54 , 5 ) $, $ Q = ( 51w + 81 , 23w + 55 ) $ y $ R = ( 85w + 17 , 75w + 94 ) $. Si $ D = ( Q + R ) - ( R ) $, entonces con el Algoritmo de Miller obtenemos los siguientes valores:

$ i $	$ f_{i , P}( D ) $
$ 1 $	$ 1 $
$ 2 $	$ 35w + 51 $
$ 3 $	$ 83w + 99 $
$ 6 $	$ 45w + 54 $
$ 12 $	$ 4w + 28 $
$ 13 $	$ 3w + 48 $

Elevando $ f_{\ell , P}( D ) $ a $ ( 103^k - 1 ) / \ell = 816 $ obtenemos $ 39w + 18 \in \mu_{13} $.

En los ejemplos que mostramos en esta lección usamos una versión simétrica $ \hat t_\ell^{\varphi} $ de $\hat t_\ell $. Esta versión consiste en usar una aplicación de distorsión $ \varphi: G_1 \rightarrow G'_1 $ de modo que $$\hat t_\ell^{\varphi}( P , Q )= \hat t_\ell ( P , \varphi( Q ) ) \neq 1 , $$ donde $ P , Q \in G_1 $.

A continuación damos un ejemplo de $ \hat t_\ell^{\varphi} $. En el ejemplo, $$ P = ( 1342232817382886117148 , 2527154567086762169220 ) , $$ de orden $ q = 10000000207 $, pertenece a la curva elíptica $ E $ definida sobre $ \mathbb F_p $, $ p = 2800000115920001199773 $, de ecuación $$ y^2 = x^3 + 577777801697778025348x + 2251851945078519483414 . $$ La función DM (Distortion Map) implementa $ \varphi $ mientras que la función NP (New Pairing) implementa $ \hat t_\ell^{\varphi} $.

El emparejamiento de Weil

Sea $ E $ una curva elíptica sobre un cuerpo finito $ \mathbb F_q $, un entero $ n $ coprimo con $ q $, y dos puntos $ P , Q \in E( \overline{\mathbb F_q} )[ n ] $, que habitualmente se abrevia $ P , Q \in E[ n ] $. Bajo nuestra hipótesis se cumple $ \# E[ n ] = n^2 $.

El emparejamiento de Weil se puede definir a partir del de Tate tal como sigue $$ \begin{array}{cccc} e_n : & E[ n ] \times E[ n ] & \to & \mu_n \subseteq \overline{\mathbb F_q} \\ & ( P , Q ) & \mapsto & \dfrac{t_n( P , Q )}{t_n( Q , P )} . \end{array} $$

El valor $ e_n( P , Q ) $ está definido salvo potencias $ n $-ésimas en $ \overline{\mathbb F_q} $. Para evitar esta ambigüedad, escribiremos $$ e_n( P , Q ) = \left ( \dfrac{t_n( P , Q )}{t_n( Q , P )} \right )^{ ( q^k - 1 ) / n } , $$ donde $ k $ es el grado de inmersión de la curva.

El emparejamiento de Weil $ e_n $, además de bilineal y no degenerado, es alternado, es decir, $ e_n( P , P ) = 1 $.

---

APARTADO 3.6. CURVAS PAIRING-FRIENDLY

Las curvas elípticas cuyo cardinal tiene en su factorización un primo grande, para las que los problemas del logaritmo discreto tanto en el grupo de puntos de la curva como en el cuerpo extensión definido por su grado de inmersión tienen la misma dificultad computacional, son adecuadas para ser usadas en criptografía basada en emparejamientos. Son las denominadas curvas pairing-friendly. En este apartado revisaremos las propiedades que satisfacen y veremos algunas construcciones que permiten obtener familias de ellas.

Vamos a recordar en primer lugar la definición de grado de inmersión de una curva. Sea $ E $ una curva elíptica sobre $ \mathbb F_q $ cuyo cardinal es de la forma $ \ell h $, siendo $ \ell $ un primo grande y $ h $ el cofactor. El grado de inmersión de $ E / \mathbb F_q $ es el menor entero $ k $ que satisface las propiedades equivalentes siguientes:

• $ \ell \mid ( q^k - 1 ) $;
• $ \mathbb F^*_{q^k} $ contiene un subgrupo cíclico de orden $ \ell $.

Si $ k $ es el grado de inmersión de $ E / \mathbb F_q $, el emparejamiento de Weil y el reducido de Tate permiten transformar puntos de la curva en elementos del cuerpo extensión $ \mathbb F_{q^k} $. Así pues, si $ k $ es muy pequeño, el ataque de Menezes-Okamoto-Vanstone [MOV], apoyándose en la transformación inducida por el emparejamiento de Weil, podría resolver un logaritmo discreto en $ E( \mathbb F_q ) $ a partir de un logaritmo discreto sobre el grupo $ \mathbb F^*_{q^k} $. De la misma manera, Frey y Rück [FR] dan una prueba similar usando el emparejamiento de Tate.

Para evitar este ataque y poder usar una curva $ E / \mathbb F_q $ en protocolos basados en emparejamientos, necesitamos que $ k $ no sea muy grande para hacer el cálculo del emparejamiento, pero tampoco sea muy pequeño para que el problema del logaritmo discreto en $ \mathbb F^*_{q^k} $ sea computacionalmente difícil.

Teniendo en cuenta que uno de los mejores algoritmos para resolver el ECDLP en un subgrupo cíclico de orden $ \ell $ de $ E( \mathbb F_q ) $ es el algoritmo de rho de Pollard de complejidad $ O( \sqrt{1/4} \ell ) $, mientras que para el problema DLP en el grupo $ \mathbb F^*_{q^k} $ el index-calculus tiene complejidad subexponencial, se deduce que $ k \geq \log_2( \ell ) / 8 $.

Así pues, decimos que una curva es pairing-friendly si satisface las propiedades:

• El cardinal de $ E( \mathbb F_q ) $ tiene un factor $ \ell \geq \sqrt{q} $;
• El grado de inmersión de $ E / \mathbb F_q $ es tal que $ k \geq \log_2( \ell ) / 8 $.

Freeman, Scott y Teske dan en [FST] la siguiente tabla comparativa con distintos tamaños de $ \ell $, $ q $ y $ q^k $. En ella se considera también el parámetro $ \rho = \log q / \log \ell $ que mide el tamaño del cuerpo base respecto al tamaño del subgrupo de orden el primo $ \ell $.

Nivel seg. (bits)	$ r $ (bits)	$ q^k $ (bits)	$ k $ ($ \rho \equiv 1 $)	$ k $ ($ \rho \equiv 2 $)
$80$	$160$	$960$ - $1280$	$6$ - $8$	$2^*$, $3$ - $4$
$112$	$224$	$2200$ - $3600$	$10$ - $16$	$5$ - $8$
$128$	$256$	$3000$ - $5000$	$12$ - $20$	$6$ - $10$
$192$	$384$	$8000$ - $10000$	$20$ - $26$	$10$ - $13$
$256$	$512$	$14000$ - $18000$	$28$ - $36$	$14$ - $18$

Equivalencias para parámetros curva y grado de inmersión según nivel de seguridad.

El grado de inmersión de las curvas supersingulares ha sido estudiado en distintintos artículos. Para ellas, $ k \leq 6 $, y si están definidas sobre un cuerpo finito primo, $ k = 2 $ (véase por ejemplo [MOV]). En cambio, no es fácil construir curvas ordinarias con grado de inmersión pequeño. Uno de los métodos generales que se pueden usar para ello es el de multiplicación compleja, propuesto por Atkin y Morain [AM], que construye una curva sobre un cuerpo finito dado y con un número de puntos prefijado.

Más recientemente han surgido nuevas estrategias que permiten obtener familias de curvas ordinarias pairing-friendly, para las cuales los parámetros de la curva $ E / \mathbb F_q $ de traza $ t $ y con un subgrupo de orden primo $ r $ vienen determinados por tres polinomios $ q(x) $, $ t(x) $ y $ r(x) $ en términos de un nuevo parámetro $ x $.

Así, las curvas MNT propuestas por Miyaji, Nakabayashi y Takano [MNT] tienen cardinal primo y posibles grados de inmersión 3, 4 o 5. Más concretamente, son curvas definidas sobre un cuerpo primo $ \mathbb F_q $ con $ r = q + 1 - t $ y cuyo grado de inmersión es:

• $ k = 3 $ si y sólo si existe $ x \in \mathbb Z $ tal que $ q = 12 x^2 - 1 $ y $ t = - 1 \pm 6 x $;
• $ k = 4 $ si y sólo si existe $ x \in \mathbb Z $ tal que $ q = x^2 + x + 1 $ y $ t = - x $ o $ t = x + 1 $;
• $ k = 6 $ si y sólo si existe $ x \in \mathbb Z $ tal que $ q = 4 x^2 + 1 $ y $ t = 1 \pm 2 x $.

Otras de estas familias llamadas ciclotómicas se basan en las propiedades:

• $ r $ divide $ q + 1 - t $ implica $ q \equiv t - 1 \pmod{r} $;
• $ r $ divide $ q^k - 1 $, $ k $ grado de inmmersión, implica $ r $ divide $ \Phi_k(q) $, siendo $ \Phi_k(x) $ el $ k $-ésimo polinomio ciclotómico.

Una de estas familias ciclotómicas es la construida por Barreto y Naehrig [BN]. Son curvas con grado de inmersión $ k = 12 $ y $ \rho = 1 $, que vienen dadas por: $$ q(x) = 36x^4 + 36x^3 + 24x^2 + 6x + 1 , \quad t(x) = 6x^2 + 1, \quad r(x) = 36x^4 + 36x^3 + 18x^2 + 6x + 1 . $$ Cabe señalar, también, que en [MST] se estudian las curvas con $ j $-invariante $ 0 $ y $ 1728 $, por tanto de ecuaciones $ y^2 = x^3 + b $ e $ y^2 = x^3 + ax $, respectivamente, que tienen grado de inmersión pequeño.

---

APARTADO 3.7. EJERCICIOS

Solución   Mostrar   Ocultar



Solución   Mostrar   Ocultar



Solución   Mostrar   Ocultar



Solución   Mostrar   Ocultar



Solución   Mostrar   Ocultar

---

APARTADO 3.8. REFERENCIAS BIBLIOGRÁFICAS

[AM] A.O.L. Atkin and F. Morain. Elliptic curves and primality proving. Math. Comp. 61, 29-68, 1993.

[BF] D. Boneh & M. Franklin. Identity based encryption from the Weil pairing. CRYPTO 2001, LNCS 2139, 213-229, 2001.

[BLS] D. Boneh, B. Lynn, H. Shacham. Short signatures from the Weil pairing. Journal of Cryptology 17, no. 4, 297-319, 2004.

[BN] P. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. SAC 2005, LNCS 3897, 319-331, 2006.

[BSS] I. Blake, G. Seroussi, and N. Smart. Advances in Elliptic Curve Cryptography. London Mathematical Society, LNS 317, Cambridge University Press, 2005.

[DH] W. Diffie & M.E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22, no. 6, 644-654, 1976.

[FR] G. Frey & H.G. Rück. A remark concerning $ m $-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp. 62, no. 206, 865-874, 1994.

[FST] D. Freeman, M. Scott, and E. Teske. A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology 23, no. 2, 224-280, 2010.

[Gal] S. Galbraith. Mathematics of Public Key Crypotography. Cambridge University Press, 2012.

[Jou] A. Joux. A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology 17, no. 4, 263-276, 2004

[jPBC] A. De Caro and V. Iovino. jPBC: Java pairing based cryptography. ISCC 2011, 850-855, IEEE, 2011. http://gas.dia.unisa.it/projects/jpbc/

[Mil] V. Miller. Short programs for functions on curves. 1986.

[MNT] A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundamentals E84-A (5), 2001.

[MOV] A. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transaction on Information Theory 39, 1639-1646, 1993.

[MST] J. Miret, D. Sadornil, and J. Tena. Computing elliptic curves with $ j = 0 , 1728 $ and low embedding degree. Int. J. Computer Mathematics, 2016.

[Sha] A. Shamir. Identity based cryptosystem and signature schemes. CRYPTO 84, LNCS 196, 47-53, 1985.