La criptografía de curva hiperelíptica es similar a la criptografía de curva elíptica (CEC) en la medida en que el jacobiano de una curva hiperelíptica es un grupo abeliano en el que hacer aritmética, al igual que usamos el grupo de puntos en una curva elíptica en CEC.
Definición
Una curva hiperelíptica (imaginaria) del género sobre un campo viene dado por la ecuación dónde es un polinomio de grado no mayor que y es un polinomio monico de grado . De esta definición se deduce que las curvas elípticas son curvas hiperelípticas del género 1. En criptografía de curvas hiperelípticases a menudo un campo 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 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 los criptosistemas basados en curvas elípticas o factorización ( RSA ). La eficiencia de implementar 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 características impares. [2]
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 número entero dados dos elementos de , a saber y . El primer tipo de grupo utilizado fue el grupo multiplicativo de un campo finito, posteriormente 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 la DLP. Esto significa que, si el jacobiano ha elementos, que 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 tanto, estas curvas hiperelípticas deben evitarse. Teniendo en cuenta varios ataques a DLP, es posible enumerar las características de las curvas hiperelípticas que deben evitarse.
Ataques contra el DLP
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, pueden usarse para atacar el DLP en el jacobiano de curvas hiperelípticas. El ataque Pohlig-Hellman reduce la dificultad del DLP al observar el orden del grupo con el que estamos trabajando. Supongamos que el grupo que se usa tiene elementos, donde es la factorización prima de . Pohlig-Hellman reduce el DLP en a los DLP en subgrupos de orden por . Así que para el divisor principal más grande de , el DLP en es tan difícil de resolver como el DLP en el subgrupo de orden . Por eso nos gustaría elegir tal que el divisor principal más grande de es casi igual a sí mismo. Requerir generalmente es suficiente.
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 índice 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 deno puede garantizar la seguridad. [5] Por lo tanto, nos quedamos con curvas elípticas y curvas hiperelípticas del género 2.
Otra restricción en las curvas hiperelípticas que podemos utilizar proviene del ataque Menezes-Okamoto-Vanstone / Frey-Rück-attack. El primero, a menudo llamado MOV para abreviar, se desarrolló en 1993, el segundo surgió en 1994. Considere una curva (hiper) elíptica sobre un campo finito dónde es la potencia de un número primo. Suponga que el jacobiano de la curva tiene elementos y es el divisor principal 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 mediante el uso del ataque de cálculo índice en . Para curvas arbitrarias es muy grande (alrededor del tamaño de ); así que aunque el ataque de cálculo de índices es bastante rápido para grupos multiplicativos de campos 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 las utilizan. En tales aplicaciones, es importante equilibrar la dureza del DLP en y ; dependiendo de los valores del nivel de seguridad deentre 6 y 12 son útiles. El subgrupo dees un toro . Existe un uso independiente en la criptografía basada en toro .
También tenemos un problema, si , el divisor primo más grande del orden del jacobiano, es igual a la característica de Mediante un mapa inyectivo diferente, podríamos considerar el DLP en el grupo aditivo en lugar de DLP en el jacobiano. Sin embargo, DLP en este grupo de aditivos es trivial de resolver, como se puede ver fácilmente. Por lo tanto, estas curvas, llamadas curvas anómalas, no deben usarse en DLP.
Orden de los jacobianos
Por tanto, para elegir una buena curva y un buen campo finito subyacente, es importante conocer el orden del jacobiano. Considere una curva hiperelíptica de género sobre el campo dónde es la potencia de un número primo y define como pero ahora sobre el campo . Puede demostrarse [6] que el orden del jacobiano de yace en el intervalo , llamado intervalo de Hasse-Weil. Pero hay más, podemos calcular el orden usando la función zeta en curvas hiperelípticas. Dejar ser el número de puntos en . Entonces definimos la función zeta de como . Para esta función zeta se puede mostrar [7] que dónde es un polinomio de grado con coeficientes en . además factores como dónde para todos . Aquídenota el complejo conjugado de. Finalmente tenemos que el orden de es igual a . Por lo tanto, se pueden encontrar órdenes de jacobianos calculando las raíces de.
Referencias
- ^ Déchène, Isabelle (2007). "El Grupo Picard, o cómo construir un grupo a partir de un conjunto" (PDF) . Tutorial sobre criptografía de curvas elípticas e hiperelípticas 2007 .
- ^ Gaudry, P .; Lubicz, D. (2009). "La aritmética de las características 2 superficies de Kummer y de las líneas elípticas de Kummer". Campos finitos y sus aplicaciones . 15 (2): 246–260. doi : 10.1016 / j.ffa.2008.12.006 .
- ^ Th'eriault, N. (2003). "Ataque de cálculo índice para curvas hiperelípticas de género pequeño". Avances en Criptología - ASIACRYPT 2003 . Nueva York: Springer. ISBN 978-3540406747.
- ^ Enge, Andreas (2002). "Cálculo de logaritmos discretos en jacobianos hiperelípticos de alto género en tiempo probablemente subexponencial" . Matemáticas de la Computación . 71 (238): 729–742. doi : 10.1090 / S0025-5718-01-01363-1 .
- ^ Jasper Scholten y Frederik Vercauteren, Introducción a la criptografía de curvas elípticas e hiperelípticas y el criptosistema NTRU , sección 4
- ^ Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, Una introducción elemental a las curvas hiperelípticas , página 30
- ^ Alfred J. Menezes, Yi-Hong Wu, Robert J. Zuccherato, Una introducción elemental a las curvas hiperelípticas , página 29
enlaces externos
- Colm Ó hÉigeartaigh Implementación de algunos algoritmos de curvas hiperelípticas utilizando MIRACL