Logaritmo discreto en una curva elíptica

Logaritmo discreto sobre una curva elíptica es la solución de la ecuación para conocidas y , donde son los puntos que pertenecen a la curva elíptica y que son el mensaje encriptado y el punto de partida, respectivamente [1] . En otras palabras, es un método para piratear un sistema de seguridad basado en una curva elíptica dada (por ejemplo, el estándar ruso EP GOST R 34.10-2012 [2] ) y encontrar una clave secreta . $S=nT \pmod{m}$ $norte$ $S$ $T$ $S T$

Historia

La criptografía elíptica se refiere a la categoría de asimétrica , es decir, el cifrado se produce mediante una clave pública. Este algoritmo fue propuesto por primera vez de forma independiente por Neil Koblitz y Victor Miller en 1985 [3] . Esto se justificó por el hecho de que el logaritmo discreto sobre una curva elíptica resultó ser más complicado que el logaritmo discreto clásico sobre un campo finito . Hasta ahora, no existen algoritmos rápidos para descifrar un mensaje cifrado utilizando una curva elíptica en el caso general. Básicamente , las vulnerabilidades de tales cifrados están asociadas con una serie de deficiencias en la selección de datos iniciales [4] .

Introducción

Este método se basa en la reducción del logaritmo discreto sobre una curva elíptica al logaritmo discreto sobre un campo finito con alguna extensión del campo sobre el que se dio la curva elíptica. Esto simplifica mucho la tarea, ya que actualmente existen algoritmos subexponenciales suficientemente rápidos para resolver el logaritmo discreto, que tienen complejidad , o el algoritmo de Pollard con complejidad , desarrollado para campos finitos [5] . $O \left( \exp \left( c \left( \ln p \right )^k \left( \ln \ln p \right)^{k-1} \right ) \right )$ $\rho$ $O(\raíz cuadrada{\pi p/2})$

Teoría

Sea una curva elíptica dada en la forma de Weierstrass sobre un campo de orden finito : $mi$ $F_q$ $q$

y^2 + a_1xy + a_3y = x^3 + a_2x^2+ a_4x + a_6

Supongamos que los coeficientes son tales que la curva no tiene singularidades . Los puntos de la curva , junto con el punto en el infinito , que es el elemento cero, forman un grupo conmutativo escrito de forma aditiva , es decir, para . También se sabe que si es un campo finito, entonces el orden de tal grupo , según el teorema de Hasse , satisfará la ecuación . $a_i\en F_q$ $mi$ $P_\infty$ $\para todo A,B \en E(F_q), A + B = B + A = C \en E(F_q)$ $F_q$ $N_q$ $|N_q-q-1| \le 2 \sqrt{q}$

Sea un subgrupo de puntos definidos sobre . Por lo tanto, es un grupo conmutativo finito . Tome un punto generando un grupo cíclico de orden . Eso es [1] . $E(F_{q'})$ $mi$ $F_{q'}\supseteq F_q$ $E(F_{q'})$ $P \in E(F_q)$ $metro$ $|\ángulo P\rángulo| = metro$

La tarea de calcular logaritmos discretos es la siguiente. Para un punto dado , encuentre tal que . $\langle P\rangle$ $Q\in\langle P\rangle$ $n\pmod{m}$ $nP = Q$

El problema de calcular logaritmos discretos en un campo finito es el siguiente. Sea un elemento primitivo del campo . Para un determinado distinto de cero , encuentre tal que [6] . $F_q$ $\alfa$ $F_q$ $\beta$ $n \pmod {(q-1)}$ $\alpha^n = \beta$

Sea LCM y una extensión de campo tal que contenga un subgrupo de torsión isomorfo a , es decir, . Se sabe que tal extensión existe [7] . De esto se deduce que para algunos . En este caso, se cumplirá el siguiente teorema, que permite pasar a un logaritmo discreto en un campo finito extendido [6] : $(m,q)=1$ $F_{q'} \supseteq F_q$ $E(F_{q'})$ $E[m]$ $\Z/m \times \Z/m$ $E[m] = \{P, T \in E(F_{q'}): mP=0, mT=0 \}$ $q' = q^k$ $k\geqslant 1$

Teorema

Sea un punto tal que . Entonces, la complejidad de calcular logaritmos discretos en el grupo no es mayor que la complejidad de calcular logaritmos discretos en . $T \in E(F_{q'})$ $\langle P,T\rangle = E[m]$ $\langle P\rangle$ $F_{q'}$

Para utilizar este teorema, es necesario conocer el grado de extensión del campo $k$ sobre y el punto por el cual [6] . $F_{q'}$ $F_q$ $T$ $\langle P,T\rangle = E[m]$

El caso de una curva elíptica supersingular

Para una curva supersingular , y se encuentran fácilmente, mientras que . Esto fue establecido por Alfred Menezes , Okamoto Tatsuaki y Scott Vanstone en 1993. En su artículo, describieron un algoritmo probabilístico para calcular un punto auxiliar , cuyo tiempo de ejecución promedio está limitado por un polinomio en [4] . $mi$ $k$ $T$ $k\le 6$ $T$ $\log{q'}$

Caso general

Sea el subgrupo máximo cuyo orden de elementos es el producto de factores primos . Así, y , donde divide y . En este caso (en el caso , se puede adaptar el método de curvas supersingulares [6] para encontrar el punto ). Sea el mínimo número natural para el cual . $GRAMO$ $E(F_{q'})$ $metro$ $E[m]\subconjunto G$ $G= \Z/m_1 \times \Z/m_2$ $metro$ $m_1$ $m_2$ $m_1 \ neq m_2$ $m_1 = m_2$ $T$ $yo$ $q^l \equiv 1 \pmod m$

Teorema

Deje NOK . Entonces y si se conoce la descomposición en factores primos, entonces existe un algoritmo probabilístico para calcular el punto para el cual . El tiempo promedio de ejecución del algoritmo es igual a las operaciones en el campo para alguna constante y . $(m, q-1) = 1$ $k = l$ $metro$ $T \in E(F_{q'})$ $\langle P,T\rangle = E[m]$ $O(registro^c{q'})$ $F_{q'}$ $C$ $m\rightarrow\infty$

En los casos en que LCM , el algoritmo funciona demasiado lento o no funciona en absoluto [6] . $(m, q-1) \neq 1$

Véase también

Notas

↑ 1 2 Semaev I. A. Sobre el cálculo de logaritmos en curvas elípticas . — Discreto. Mat., 1996. - V. 8 , núm. 1 . — S. 65–71 .
↑ EP GOST R 34.10-2012 http://www.altell.ru/legislation/standards/gost-34.10-2012.pdf Copia de archivo fechada el 5 de marzo de 2016 en Wayback Machine
↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Introducción a la criptografía matemática . — Springer. — 530 págs.
↑ 1 2 Menezes A., Okamoto T., Vanstone S.,. Reducción de logaritmos de curvas elípticas a logaritmos en un campo finito. IEEE. — Trans. informar. Teoría, 1993. - S. 1639-1646 .
↑ Don Johnson, Alfred Menezes, Scott Vanstone. El algoritmo de firma digital de curva elíptica (ECDSA) . — Investigación de Certicom, Canadá. Archivado desde el original el 4 de marzo de 2016.
↑ 1 2 3 4 5 Semaev IA Sobre la cuestión de reducir el cálculo de logaritmos discretos en una curva elíptica al cálculo de logaritmos discretos en un campo finito . — Discreto. Mat., 1999. - V. 11 , n. 3 . — P. 24–28 .
↑ Silverman JH La aritmética de las curvas elípticas. . - Springer, Berlín, 1986. - 522 p.

Literatura

Teoría

Semaev IA Sobre el cálculo de logaritmos en curvas elípticas . — Discreto. Mat., 1996. - V. 8 , núm. 1 . — S. 65–71 .
- Suplemento: Semaev I. A. Sobre la cuestión de reducir el cálculo de logaritmos discretos en una curva elíptica al cálculo de logaritmos discretos en un campo finito . — Discreto. Mat., 1999. - V. 11 , n. 3 . — P. 24–28 .
Don Johnson, Alfred Menezes, Scott Vanstone. El algoritmo de firma digital de curva elíptica (ECDSA) . — Investigación de Certicom, Canadá. Archivado desde el original el 4 de marzo de 2016.

Historia

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Introducción a la criptografía matemática . — Springer. — 530 págs.