Criptografía de curva hiperelíptica

La criptografía de curva hiperelíptica es similar a la criptografía de curva elíptica (ECC) en la medida en que el jacobiano de una curva hiperelíptica es un grupo abeliano en el que realizar operaciones aritméticas, de la misma manera que utilizamos el grupo de puntos en una curva elíptica en ECC.

Una curva hiperelíptica (imaginaria) de género sobre un cuerpo se da por la ecuación donde es un polinomio de grado no mayor que y es un polinomio mónico de grado . De esta definición se deduce que las curvas elípticas son curvas hiperelípticas de género 1. En la criptografía de curvas hiperelípticas, a menudo se trata de un cuerpo finito . El jacobiano de , denotado , es un grupo cociente , por lo que los elementos del jacobiano no son puntos, son clases de equivalencia de divisores de grado 0 bajo la relación de equivalencia lineal . Esto concuerda con el caso de la curva elíptica, porque se puede demostrar que el jacobiano de una curva elíptica es isomorfo con el grupo de puntos de la curva elíptica. ^[1] El uso de curvas hiperelípticas en criptografía surgió en 1989 de la mano de Neal Koblitz . Aunque se introdujeron solo 3 años después de ECC, no muchos criptosistemas implementan curvas hiperelípticas porque la implementación de la aritmética no es tan eficiente como con criptosistemas basados ​​en curvas elípticas o factorización ( RSA ). La eficiencia de la implementación de la aritmética depende del campo finito subyacente ; en la práctica, resulta que los campos finitos de característica 2 son una buena opción para implementaciones de hardware, mientras que el software suele ser más rápido en la característica impar. ^[2]${\displaystyle g}$${\displaystyle K}$${\displaystyle C:y^{2}+h(x)y=f(x)\in K[x,y]}$${\displaystyle h(x)\in K[x]}$${\displaystyle g}$${\displaystyle f(x)\in K[x]}$${\displaystyle 2g+1}$${\displaystyle K}$${\displaystyle C}$${\displaystyle J(C)}$${\displaystyle K}$

El jacobiano en una curva hiperelíptica es un grupo abeliano y como tal puede servir como grupo para el problema del logaritmo discreto (DLP). En resumen, supongamos que tenemos un grupo abeliano y un elemento de , el DLP en implica encontrar el entero dados dos elementos de , a saber y . El primer tipo de grupo utilizado fue el grupo multiplicativo de un cuerpo finito, más tarde también se utilizaron jacobianos de curvas (hiper)elípticas. Si la curva hiperelíptica se elige con cuidado, entonces el método rho de Pollard es la forma más eficiente de resolver el DLP. Esto significa que, si el jacobiano tiene elementos, el tiempo de ejecución es exponencial en . Esto hace posible utilizar jacobianos de un orden bastante pequeño , lo que hace que el sistema sea más eficiente. Pero si la curva hiperelíptica se elige mal, el DLP será bastante fácil de resolver. En este caso, existen ataques conocidos que son más eficientes que los solucionadores de logaritmos discretos genéricos ^[3] o incluso subexponenciales. ^[4] Por lo tanto, se deben evitar estas curvas hiperelípticas. Teniendo en cuenta los diversos ataques a DLP, es posible enumerar las características de las curvas hiperelípticas que se deben evitar. ${\displaystyle G}$${\displaystyle g}$${\displaystyle G}$${\displaystyle G}$${\displaystyle a}$${\displaystyle G}$${\displaystyle g}$${\displaystyle g^{a}}$${\displaystyle n}$${\displaystyle \log(n)}$

Todos los ataques genéricos al problema del logaritmo discreto en grupos abelianos finitos, como el algoritmo de Pohlig-Hellman y el método rho de Pollard, se pueden utilizar para atacar el DLP en el jacobiano de curvas hiperelípticas. El ataque de Pohlig-Hellman reduce la dificultad del DLP al observar el orden del grupo con el que estamos trabajando. Supongamos que el grupo que se utiliza tiene elementos, donde es la factorización prima de . Pohlig-Hellman reduce el DLP en a DLP en subgrupos de orden para . Entonces, para el divisor primo más grande de , el DLP en es tan difícil de resolver como el DLP en el subgrupo de orden . Por lo tanto, nos gustaría elegir tal que el divisor primo más grande de sea casi igual a sí mismo. Requerir generalmente es suficiente. ${\displaystyle G}$${\displaystyle n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}}$${\displaystyle p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}}$${\displaystyle n}$${\displaystyle G}$${\displaystyle p_{i}}$${\displaystyle i=1,...,k}$${\displaystyle p}$${\displaystyle n}$${\displaystyle G}$${\displaystyle p}$${\displaystyle G}$${\displaystyle p}$${\displaystyle \#G=n}$${\displaystyle n}$${\textstyle {\frac {n}{p}}\leq 4}$

El algoritmo de cálculo de índices es otro algoritmo que se puede utilizar para resolver DLP en algunas circunstancias. Para los jacobianos de curvas (hiper)elípticas existe un ataque de cálculo de índices en DLP. Si el género de la curva se vuelve demasiado alto, el ataque será más eficiente que el rho de Pollard. Hoy se sabe que incluso un género de no puede garantizar la seguridad. ^[5] Por lo tanto, nos quedamos con curvas elípticas y curvas hiperelípticas de género 2. ${\displaystyle g=3}$

Otra restricción sobre las curvas hiperelípticas que podemos usar proviene del ataque de Menezes-Okamoto-Vanstone / ataque de Frey-Rück. El primero, a menudo llamado MOV para abreviar, se desarrolló en 1993, el segundo apareció en 1994. Considere una curva (hiper)elíptica sobre un cuerpo finito donde es la potencia de un número primo. Suponga que el jacobiano de la curva tiene elementos y es el divisor primo más grande de . Para el entero positivo más pequeño tal que existe un homomorfismo de grupo inyectivo computable del subgrupo de de orden a . Si es pequeño, podemos resolver DLP en usando el ataque de cálculo de índices en . Para curvas arbitrarias es muy grande (alrededor del tamaño de ); por lo que, aunque el ataque de cálculo de índices es bastante rápido para grupos multiplicativos de cuerpos finitos, este ataque no es una amenaza para la mayoría de las curvas. La función inyectiva utilizada en este ataque es un emparejamiento y hay algunas aplicaciones en criptografía que hacen uso de ellas. En tales aplicaciones es importante equilibrar la dureza del DLP en y ; dependiendo del nivel de seguridad , son útiles valores de entre 6 y 12. El subgrupo de es un toro . Existe algún uso independiente en la criptografía basada en toros . ${\displaystyle C}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle k}$${\displaystyle p|q^{k}-1}$ ${\displaystyle J(C)}$${\displaystyle p}$${\displaystyle \mathbb {F} _{q^{k}}^{*}}$${\displaystyle k}$${\displaystyle J(C)}$${\textstyle \mathbb {F} _{q^{k}}^{*}}$${\displaystyle k}$${\displaystyle q^{g}}$${\displaystyle J(C)}$${\textstyle \mathbb {F} _{q^{k}}^{*}}$${\displaystyle k}$${\textstyle \mathbb {F} _{q^{k}}^{*}}$

También tenemos un problema, si , el mayor divisor primo del orden del jacobiano, es igual a la característica de Mediante una función inyectiva diferente podríamos entonces considerar el DLP en el grupo aditivo en lugar del DLP en el jacobiano. Sin embargo, el DLP en este grupo aditivo es trivial de resolver, como se puede ver fácilmente. Así también estas curvas, llamadas curvas anómalas, no se deben utilizar en el DLP. ${\displaystyle p}$${\displaystyle \mathbb {F} _{q}.}$${\displaystyle \mathbb {F} _{q}}$

Por lo tanto, para elegir una buena curva y un buen cuerpo finito subyacente, es importante conocer el orden del jacobiano. Consideremos una curva hiperelíptica de género sobre el cuerpo donde es la potencia de un número primo y definamos como pero ahora sobre el cuerpo . Se puede demostrar que el orden del jacobiano de se encuentra en el intervalo , llamado intervalo de Hasse-Weil. ^[6]${\textstyle C}$${\textstyle g}$${\textstyle \mathbb {F} _{q}}$${\textstyle q}$${\textstyle C_{k}}$${\textstyle C}$${\textstyle \mathbb {F} _{q^{k}}}$${\textstyle C_{k}}$${\textstyle [({\sqrt {q}}^{k}-1)^{2g},({\sqrt {q}}^{k}+1)^{2g}]}$

Pero hay más, podemos calcular el orden usando la función zeta en curvas hiperelípticas. Sea el número de puntos en . Luego definimos la función zeta de como . Para esta función zeta se puede demostrar que donde es un polinomio de grado con coeficientes en . ^[7] Además, se factoriza como donde para todo . Aquí denota el conjugado complejo de . Finalmente, tenemos que el orden de es igual a . Por lo tanto, los órdenes de los jacobianos se pueden encontrar calculando las raíces de . ${\textstyle A_{k}}$${\textstyle C_{k}}$${\textstyle C=C_{1}}$${\textstyle Z_{C}(t)=\exp(\sum _{i=1}^{\infty }{A_{i}{\frac {t^{i}}{i}}})}$${\textstyle Z_{C}(t)={\frac {P(t)}{(1-t)(1-qt)}}}$${\textstyle P(t)}$${\textstyle 2g}$${\textstyle \mathbb {Z} }$${\textstyle P(t)}$${\textstyle P(t)=\prod _{i=1}^{g}{(1-a_{i}t)(1-{\bar {a_{i}}}t)}}$${\textstyle a_{i}\in \mathbb {C} }$${\textstyle i=1,...,g}$${\textstyle {\bar {a}}}$${\displaystyle a}$${\textstyle J(C_{k})}$${\textstyle \prod _{i=1}^{g}{|1-a_{i}^{k}|^{2}}}$${\textstyle P(t)}$

• Colm Ó hÉigeartaigh Implementación de algunos algoritmos de curvas hiperelípticas usando MIRACL
• DJ Bernstein Surface1271: criptografía de curva hiperelíptica de género 2 de alta velocidad: trabajo incompleto de 2006 que pretendía producir una variante Diffie-Hellman, pero que se estancó debido a dificultades para elegir superficies (a su vez, porque no se dispone de conteo de puntos para superficies grandes). Contiene software para la multiplicación escalar de Pentium M en una superficie Kummer.