ECDLP

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de enero de 2015; las comprobaciones requieren 13 ediciones .

ECDLP (Elliptic Curve Discrete Logarithm Problem) es un problema de logaritmo discreto en un grupo de puntos de una curva elíptica .

Sean dados una curva elíptica E, un campo finito F p , y puntos P, Q ∈ E(F p ). La tarea de ECDLP es encontrar tal k, si existe, que Q = [k]P.

Definiciones

Una curva elíptica E sobre un campo finito F p es una curva de la forma (forma de Weierstrass):

E:Y^{2}=X^{3}+aX+b

, donde a, b ∈ F pag .

El conjunto de puntos en una curva elíptica en el campo F p , incluido el punto "infinito" (denotado como Ο), forma un grupo abeliano finito y se denota como E(F p ) .

Un punto Q ∈E (F p ) se llama punto inverso a P ∈ E(F p ) si P + Q = Ο y se denota como Q = -P .

Para un número natural n y P ∈ E(F p ) asumimos:

{\displaystyle [n]P=\soporte {P+P+...+P} _{n))

Las notaciones [n]P y nP son equivalentes. La definición se puede extender a cualquier número entero n usando -P.

El orden de un grupo de puntos es el número N igual a la cardinalidad del conjunto E(F p ) y se denota como |E(F p )| =N . Por lo general, en la criptografía elíptica, las curvas se toman de manera que N = h * l, donde h = 1, 2 o 4, y l es un número primo grande.

El orden de un punto P ∈ E(Fp) es el número mínimo s tal que [s]P = Ο. En este caso, se forma un subgrupo y el punto P se llama generador . $\langle P\rangle =\{[k]P:k={\overline {1,s}}\}$ $\langle P\rangle$

Algoritmos de solución

Enumeración completa

Es el ataque más simple de implementar. Solo es necesario poder realizar la operación R = [k]P.

Algoritmo

${\ estilo de visualización k: = 1}$
${\ estilo de visualización R: = [k] P}$
si , entonces - solución ${\ estilo de visualización R = Q}$ $k$
más ; ir a [2]. $k:=k+1$

Complejidad del algoritmo: Ο(N).

Algoritmo de Polig-Hellman

Descripción

Sea G un subgrupo de E(F p ), (es decir, se supone que el número N se puede factorizar), y . $N=|G|=\prod _{i=1}^{t}{p_{i}}^{e^{i}}$ ${\ estilo de visualización P, Q \ en G}$ $\existe k:Q=[k]P$

Resolveremos el problema de encontrar k módulo , luego, usando el teorema chino del resto , encontraremos la solución k módulo N. ${p_{i}}^{e_{i}}$

Se sabe por la teoría de grupos que existe un isomorfismo de grupo:

\phi :G\rightarrow C_{{p_{1}}^{e_{1}}}\otimes ...\otimes C_{{p_{t}}^{e_{t}}}

donde es un subgrupo cíclico de G, $C_{{p_{i}}^{e_{i}}}$ $|C_{{p_{i}}^{e_{i}}}|={p_{i}}^{e_{i}}$

Entonces la proyección sobre : $\fi$ $C_{p^{e))$

\phi _{p}={\begin{cases}G\rightarrow C_{p^{e}}\\R\longmapsto [{\frac {N}{p^{e}}}]R\ fin {casos}}

Por lo tanto, en . ${\phi _{p}}(Q)=[k]{\phi _{p}}(P)$ $C_{p^{e))$

Mostremos cómo resolver el problema en , reduciéndolo a resolver ECDLP en . $C_{p^{e))$ $C_p$

Sea y . $P,Q\en C_{p^{e}}$ $\existe k:Q=[k]P$

El número se define módulo . Entonces k se puede escribir de la siguiente forma: $k$ $p^{e}$

k=k_{0}+{k_{1}}p+...+{k_{e-1}}p^{e-1}

Encontremos los valores por inducción. Supongamos que sabemos - el valor , es decir $k_{0},k_{1},...$ $k'$ ${\ Displaystyle k\ mod\ p^{t))$

{\displaystyle k'=k_{0}+...+k_{t-1}p^{t-1))

Ahora queremos determinar y así calcular : $k_t$ $k\ mod\ p^{t+1}$

k=k'+p^{t}k''

entonces _ $Q=[k']P+[k'']([p^{t}]P)$

Deja y luego $Q'=Q-[k']P$ $P'=[p^{t}]P$ $Q'=[k'']P'$

Ahora - el elemento de orden , para obtener el elemento de orden y, por tanto, reducir a él el problema es necesario multiplicar la expresión anterior por . Que. $PAGS'$ ${\displaystyle p^{et))$ $pags$ $C_p$ ${\displaystyle s=p^{et-1))$

Q''=[s]Q'

P''=[s]P'

Recibió ECDLP en el campo como . $C_p$ $Q''=[k_{t}]P''$

Suponiendo que este problema se puede resolver en , encontramos la solución en . Usando el teorema del resto chino, obtenemos la solución ECDLP en . $C_p$ $k$ $C_{p^{e))$ $E(F_p)$

Como se mencionó anteriormente, en la práctica, las curvas elípticas se toman de manera que , donde es un número primo muy grande, lo que hace que este método sea ineficaz. ${\ estilo de visualización N = hl}$ $yo$

Ejemplo

${\ estilo de visualización Q = [k] P \ (mod \ 1009)}$

$E:y^{2}\equiv x^{3}+71x+602\ (mod\ 1009)$

${\ estilo de visualización P = (1237), Q = (190271)}$

${\ estilo de visualización N = 1060 = 2 ^ {2} * 5 * 53}$

$|\langle P\rangle |=530=2*5*53$

Paso 1. Encuentra ${\ Displaystyle k\ mod\ 2}$

Encontramos las proyecciones de los puntos sobre : $C_{2}$

P_{2}=265P=(50,0)

Q_{2}=265Q=(50,0)

Nosotros decidimos ${\displaystyle Q_{2}=[k]P_{2))$

k\equiv 1\ (mod\ 2)

Paso 2. Encuentra ${\ Displaystyle k\ mod\ 5}$

Encontramos las proyecciones de los puntos sobre : ${\ estilo de visualización C_ {5}}$

P_{5}=106P=(639,160)

Q_{5}=106Q=(639,849)

Nosotros decidimos $Q_{5}=[k]P_{5}$

Tenga en cuenta que entonces

Q_{5}=-P_{5}

k\equiv 4\ (mod\ 5)

Paso 3. Encuentra ${\ Displaystyle k\ mod\ 53}$

Encontramos las proyecciones de los puntos sobre : ${\ estilo de visualización C_ {53}}$

P_{53}=10P=(32,737)

Q_{53}=10Q=(592,97)

Nosotros decidimos $Q_{53}=[k]P_{53}$

k\equiv 48\ (mod\ 53)

Paso 4. Encuentra ${\ Displaystyle k\ mod\ 530}$

Del teorema chino del resto para los valores obtenidos en los pasos anteriores 1-3, tenemos que

k\equiv 419\ (mod\ 530)

Algoritmo de Shanks (método Baby-Step/Giant-Step)

Descripción

Sea un subgrupo cíclico de . $G=\langle P\rangle$ $E(F_{p});|\langle P\rangle |=l;Q\in G$

Pongámoslo en la forma: $k$

k=k_{0}+k_{1}\lceil {\sqrt {l))\rceil

Desde entonces . ${\ Displaystyle k \ leq l}$ $0\leq k_{0},k_{1}<\lceil {\sqrt {l))\rceil$

Calculamos la lista de "pequeños pasos" y guardamos los pares . $P_{i}=[i]P$ $0\leq i<\lceil {\sqrt {l))\rceil$ ${\ estilo de visualización (P_ {i}, i)}$

Complejidad de los cálculos: . ${\ Displaystyle O (\ lceil {\ sqrt {l)) \ rceil)}$

Ahora calculamos los "grandes pasos". Vamos a encontrar . $P'=[\lceil {\sqrt {l}}\rceil ]P$ $Q_{j}=Q-[j]P'$ $0\leq j<\lceil {\sqrt {l))\rceil$

Durante la búsqueda, tratamos de encontrar entre los pares guardados tales que . Si fuera posible encontrar tal par, entonces . $Q_{j}$ ${\ estilo de visualización (P_ {i}, i)}$ ${\displaystyle P_{i}=Q_{j))$ $k_{0}=i,k_{1}=j$

O lo que es lo mismo:

[i]P=Q-[j\lceil {\sqrt {l))\rceil]P,

[i+j\lceil {\sqrt {l}}\rceil]P=Q

Complejidad de los cálculos de "grandes pasos": . ${\ Displaystyle O (\ lceil {\ sqrt {l)) \ rceil)}$

En este caso, la complejidad general del método , pero también requiere memoria para el almacenamiento, lo cual es una desventaja significativa del algoritmo. ${\ estilo de visualización O ({\ sqrt {l)))}$ ${\ estilo de visualización S ({\ sqrt {l)))}$

Algoritmo

$m:=\lceil {\sqrt {l))\rceil$
$\mathbf {para} \ i:=1\ \mathbf {para} \ m\ \mathbf {hacer}$ ${\ estilo de visualización R: = [i] P}$ ahorrar ${\ estilo de visualización (R, yo)}$
$\mathbf {para} \ j:=1\ \mathbf {para} \ m\ \mathbf {hacer}$ $T:=Q-[j\lceil {\sqrt {l))\rceil]P$ comprobar en la lista [2] $T$
$\mathbf {si} \ T=R\ \mathbf {entonces}$ $k:=i+j\lceil {\sqrt {l))\rceil \ (mod\ l)$ $\mathbf {retorno} \k$

Método ρ de Pollard

Descripción

Sea un subgrupo cíclico de . $G=\langle P\rangle$ $E(F_{p});|G|=r;Q\in G$

La idea principal del método es encontrar pares distintos y módulos tales que . ${\ estilo de visualización (c', d')}$ ${\ estilo de visualización (c'', d'')}$ $r$ $[c']P+[d']Q=[c'']P+[d'']Q$

Entonces o . Por lo tanto, . $[c'-c'']P=[d''-d']Q$ $Q={\frac {c'-c''}{d''-d'}}P\ (mod\ r)$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$

Para implementar esta idea, elegimos una función aleatoria para iteraciones y un punto aleatorio para iniciar el recorrido. El siguiente punto se calcula como . ${\ estilo de visualización f: G \ flecha derecha G}$ $P_0$ $P_{i+1}=f(P_{i})$

Como es finito, existen índices tales que . $GRAMO$ $yo<j$ ${\displaystyle P_{i}=P_{j))$

entonces _ $P_{i+1}=f(P_{i})=f(P_{j})=P_{j+1}$

En realidad , para . ${\displaystyle P_{i+l}=P_{j+l))$ ${\ estilo de visualización \ forall l \ geq 0}$

Entonces la secuencia es periódica con un período (ver figura). ${\ estilo de visualización \ {P_ {i} \}}$ ${\ estilo de visualización ji}$

Dado que f es una función aleatoria, de acuerdo con la paradoja del cumpleaños , la coincidencia ocurrirá después de aproximadamente iteraciones. Para acelerar la búsqueda de colisiones, se utiliza un método inventado por Floyd para encontrar la duración del ciclo: se calcula un par de valores para a la vez hasta que se encuentra una coincidencia. ${\ estilo de visualización {\ sqrt {\ frac {\ pi r} {2}}}}$ ${\ estilo de visualización (P_{i},P_{2i})}$ ${\ estilo de visualización i = 1,2,...}$

Algoritmo

Inicialización. Elija el número de ramas L (normalmente se toman 16) Seleccionar función $H:\langle P\rangle \rightarrow {1,2,...,L}$
calculo _ $[a_{i}]P+[b_{i}]Q$ $\mathbf {para} \ i:=1\ \mathbf {para} \ L\ \mathbf {hacer}$ tomar al azar ${\ estilo de visualización a_ {i}, b_ {i} \ en [0, r-1]}$ $R_{i}:=[a_{i}]P+[b_{i}]Q$
calculo _ $[c']P+[d']Q$ tomar al azar ${\ estilo de visualización c', d' \ en [0, r-1]}$ $X':=[c']P+[d']Q$
Preparando un ciclo. ${\ estilo de visualización X'':=X',c'':=c',d'':=d'}$
Ciclo. $\mathbf {repetir}$ ${\ estilo de visualización j: = H (X')}$ ${\ Displaystyle X':=X'+R_{j))$ $c':=c'+a_{j}\ (mod\ r)$ $d':=d'+b_{j}\ (mod\ r)$ $\mathbf {para} \ i:=1\ \mathbf {para} \ 2\ \mathbf {hacer}$ ${\ estilo de visualización j: = H (X'')}$ ${\ estilo de visualización X'':=X''+R_{j))$ $c'':=c''+a_{j}\ (mod\r)$ $d'':=d''+b_{j}\ (mod\ r)$ $\mathbf {hasta} \ X'=X''$
Salida. $\mathbf {si} d'\neq d''\ \mathbf {entonces}$ $k\equiv {\frac {c'-c''}{d''-d'}}\ (mod\ r)$ $\mathbf {otro}$ ERROR o vuelva a ejecutar el algoritmo.

Complejidad del algoritmo: . $O({\sqrt {r)))$

Ejemplo

${\ estilo de visualización Q = [k] P \ (mod \ 229)}$

$E:y^{2}\equiv x^{3}+x+44\ (mod\ 229)$

${\ estilo de visualización P = (5116), Q = (155166)}$

$|\langle P\rangle |=239$

Paso 1. Defina la función.

$H:\langle P\rangle \rightarrow {1,2,3,4}$
$H(x,y)=(x\ mod\ 4)+1$
${\ estilo de visualización (a_ {1}, b_ {1}, R_ {1}) = (79,163, (135,117))}$
${\ estilo de visualización (a_ {2}, b_ {2}, R_ {2}) = (206,19, (96,97))}$
${\ estilo de visualización (a_ {3}, b_ {3}, R_ {3}) = (87,109, (84,62))}$
${\ estilo de visualización (a_ {4}, b_ {4}, R_ {4}) = (219,68, (72,134))}$

Paso 2. Iteraciones.

${\begin{array}{c|ccc|ccc}Iteración&c'&d'&[c']P+[d']Q&c''&d''&[c'']P+[d'']Q\ \\hlínea 0&54&175&(39,159)&54&175&(39,159)\\1&34&4&(160,9)&113&167&(130,182)\\2&113&167&(130,182)&180&105&(36,97)\\3&200&37&\0410,17 (36,97) & 46 & 40 & (223,153) \\ 5 & 20 & 29 & (119,180) & 232 & 127 & (167,57) \\ 6 & 0 & 97 & (108,89) & 192 & 24 & (57,105) \\ 7 & 79 & 21 & (81,168) y 139 y 111 y 111 y 245. (197.92) \\ 9 & 26 & 108 & (9.18) & 140 & 87 & (194.145) \\ 10 & 232 & 127 & (167.57) & 67 & 120 & (223.153) \\ 11 & 212 & 195 & (75.136) & 14 & 204 & (161.B2) \ Matemáticas (167.57) \ 57 y 195 y 21 \ 55) )} \\\end{matriz}}$

Paso 3 Detección de colisión

en : ${\ estilo de visualización i = 12}$ $[192]P+[24]Q=[213]P+[104]Q=(57,105)$
eso lo conseguimos $k\equiv {\frac {192-213}{104-24}}\equiv 176\ (mod\ 229)$

Literatura

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Una introducción elemental a la criptografía elíptica: fundamentos algebraicos y algorítmicos. - M.: KomKniga, 2006. - S. 328. - ISBN 5-484-00443-8 .

Bolotov, A. A., Gashkov, S. B., Frolov, A. B., Chasovskikh, A. A. Una introducción elemental a la criptografía elíptica: protocolos de criptografía de curva elíptica. - M.: KomKniga, 2006. - S. 280. - ISBN 5-484-00444-6 .

Galbraith, SD, Smart, NP INFORME DE EVALUACIÓN DE CRYPTREC: NIVEL DE SEGURIDAD DE LA CRIPTOGRAFÍA - PROBLEMA MATEMÁTICO ECDLP.

Song Y. Yan Quantum Attacks en criptosistemas basados en ECDLP. - Springer EE. UU., 2013 - ISBN 978-1-4419-7721-2