Criptografía de
Curva Elíptica

“Curso de Introducción a la Criptografía” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

$n=24$

Curva Elíptica: longitud de clave

la dificultad de ejecutar el logaritmo de una clave pública $n$ es
$O(\sqrt{2^{\text{longitud}_n}})$, por tanto el nivel de seguridad en bits es la mitad

el NIST recomienda $\|n\| \geq 224$ bit hasta el 2030

ECDH $n$ / ECDSA $n$	DSA $p$; $q$	DH $n$ / RSA $n$		(bits de seguridad)
$224$	$2048$; $224$	$2048$	$\leftrightarrow$	$112$
$256$	$3072$; $256$	$3072$	$\leftrightarrow$	$128$
$512$	n/d	$15360$	$\leftrightarrow$	$256$

ECDSA y ECDH sustituye DSA y DH respectivamente ya que son más eficientes y aguantarán mejor el paso del tiempo (hay implementaciones con $\|n\| = 512$ pero nadie está usando DSA, DH o RSA con longitudes de clave equivalentes (según el NIST) de $15360$ b)

Cripto de Curva Elíptica

se busca un primo $p$ de tamaño apropiado: $\mathbb{F}_p$ (similar a $\mathbb{Z}_p^*$)
se seleccionan los “puntos” que cumplen con la ecuación de una curva elíptica $E(\mathbb{F}_p)$
se "cuentan" los puntos de la curva ($|E(\mathbb{F}_p)|$) y se verifica que (también) es un número primo
sobre estos "puntos bidimensionales" se definen dos operaciones:
$\begin{aligned} "+" &\rightarrow P+Q \\ "+ \text{repetida}" &\rightarrow P+P+P+\cdots+P \color{gray}{= i P} \end{aligned}$

ECDLP: EC Discrete Logarithm Problem

encontrar $i$ a partir de

$R=i A$

conociendo $R$ y $A$

es un problema de complejidad exponencial

por ejemplo ECDH

$i(\color{red}{jA}) = j(\color{red}{iA}) = ijA \leftarrow$ (secreto acordado)

es equivalente a DH

${(\color{red}{\alpha^{i}})}^j = {(\color{red}{\alpha^{j}})}^i = \alpha^{ij}\leftarrow$ (secreto acordado)

utilizaremos mayúsculas para definir puntos y distingirlos de los enteros
$A$ es $\alpha$ mayúscula, el punto generador

4. Suma de puntos (y suma-repetida)

enfoque geométrico; ojo: $P\in E(\mathbb{R})$ no $E(\mathbb{F}_p)$

(fuente: Jan R. Sandbakken / GeoGebra)

2. Cripto de Curva elíptica

una curva elíptica $E$ es:

$y^2 = x^3+ax+b$

una curva elíptica $E(\mathbb{F}_p)$ es:

$y^2 \equiv x^3+ax+b \pmod p$

y para que no tinga singularidades hace falta escoger $a,b \in \mathbb{F}_p$ para que $4a^3+27b^2 \not\equiv 0 \pmod p$

las curvas elípticas tienen las propiedades necesarias para que la operación $+$ esté bien definida $\forall P = (x,y) \in E(\mathbb{F}_p)$

4. Suma: $R=P+Q$

$\begin{aligned} x_R &= \left(\frac{y_Q-y_P}{x_Q-x_P}\right)^2 - x_P - x_Q \\ y_R &= \left(\frac{y_Q-y_P}{x_Q-x_P}\right)(x_P-x_R) - y_P \\ \end{aligned}$

4. Suma repetida: $R = 2P$

$\begin{aligned} x_R &= \left(\frac{3 x_P^2+a}{2 y_p}\right)^2 - 2x_P \\ y_R &= \left(\frac{3 x_P^2+a}{2 y_p}\right)(x_P-x_R)- y_P \\ \end{aligned}$

4.$\rightarrow$1. Suma de puntos (algunos detalles)

entonces: para hacer la suma (y suma repetida) de puntos sobre $E(\mathbb{F}_p)$...
necesitamos suma, resta, multiplicación y división sobre $\mathbb{F}_p$
$\mathbb{F}_p = \{0,1,2,\dotsc,p-1\}$

no hay bastante con el $\mathbb{Z}_p^*$ ya que la resta sobre $\mathbb{F}_p$ puede generar valores $P=(0,-)$

$P-P = \mathcal{O}$: si nos fijamos en el gráfico, sumar $P$ a $-P$ tiende a $(-,\infty)$ $\Rightarrow$
$\mathcal{O}$ es la identidad (o desde el punto de vista gráfico es el “punto en el inifinito”)

...

1. Cuerpo finito $\mathbb{F}_p$

…este tipo de conjuntos con estas operaciones definidas
se denominan cuerpos finitos

en resumen, sobre $\mathbb{F}_p$ tenemos que:

las dos funciones $+$ y $\times$ definidas
tiene el elemento nulo (sobre $+$)
tiene el elemento identidad (sobre $\times$)
así como la inversa definida (y única) para todos los elementos no nulos

recordemos que para DH o DSA usábamos un grupo (finito) sobre la multiplicación ($\mathbb{Z}_p^*$)

3. $|E(\mathbb{F}_p)|$

Hace falta que la cantidad de elementos de $E(\mathbb{F}_p)$ ($|E(\mathbb{F}_p)|$) tenga un factor (primo) grande

el teorema de Hasse dice que $|E(\mathbb{F}_p)|$ tiene como factor
$n=p+1\pm 2\sqrt{p}$, por tanto

entonces $E(\mathbb{F}_p)$ es o bien cíclico o bien tiene algún generador con un orden^* grande ($n$)

escogemos uno de estos puntos como generador $A$:

$n = \text{ord}(A) \; \Rightarrow \; nA=\mathcal{O}$

Nota: en DH (no EC) sería equivalente a:
$\alpha^n \equiv 1 \pmod p$

Ejemplo

con parámetros reducidos

(ejemplo de [Johnson, Menezes, Vanstone])

Ejemplo con parámetros reducidos

usaremos $p=23 \Rightarrow \mathbb{F}_{23} = \{0,1,2,\dotsc,21,22\}$

y $a=1$ y $b=4 \Rightarrow y^2 \equiv x^3+x+4 \pmod{23}$

entonces $E(\mathbb{F}_{23})$:

$\begin{matrix} \mathcal{O} & (0, 2) & (0,21) & (1, 11) & (1,12) & (4, 7) \\ (4,16) & (7, 3) & (7,20) & (8,8) & (8,15) & (9,11) \\ (9,12) & (10, 5) & (10,18) & (11,9) & (11,14) & (13,11) \\ (13,12) & (14,5) & (14,18) & (15,6) & (15,17) & (17,9) \\ (17,14) & (18,9) & (18,14) & (22,5) & (22,18) \end{matrix}$

y el tamaño es $|E(\mathbb{F}_{23})| = 29$ (el tamaño de $|E(\mathbb{F}_{p})| \approx p$)

$E(\mathbb{F}_{23}); y^2=x^3+x+4$

$E(\mathbb{F}_{23});\; y^2=x^3+x+4$

$\begin{matrix} \mathcal{O} & (0,2) & (0,21) & (1, 11) & (1,12) & (4,7) \\ (4,16) & (7, 3) & (7,20) & (8,8) & (8,15) & (9,11) \\ (9,12) & (10, 5) & (10,18) & (11,9) & (11,14) & (13,11) \\ (13,12) & (14,5) & (14,18) & (15,6) & (15,17) & (17,9) \\ (17,14) & (18,9) & (18,14) & (22,5) & (22,18) \end{matrix}$

$E(\mathbb{F}_{23});\; y^2=x^3+x+4;\;$ generador $A = (0,2);\; 29A=\mathcal{O}$

$\begin{matrix} 1A=(0,2) & 2A=(13,12) & 3A=(11,9) & 4A=(1,12) \\ 5A=(7,20) & 6A=(9,11) & 7A=(15,6) & 8A=(14,5) \\ 9A=(4,7) & \dotsc & & \\ 25A=(1,11) & 26A=(11,14) & 27A=(13,11) & 28A=(0,21) \\ 29A=\mathcal{O} \end{matrix}$

Curvas estándar

NIST P-256

$y^3 \equiv x^2 + ax + b \pmod p$

$\begin{aligned} p =& 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 = \\ & 115792089210356248762697446949407573530086143415290314195533631308867097853951\\ a =& -3 \\ b =& 41058363725152142129326129780047268409114441015993725554835256314039467401291 \\ A =& (\\ & \mathtt{0x6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296}\\ & , \\ & \mathtt{0x4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5}\\ & ) \\ \text{ord}(A) =& n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 \end{aligned}$

(font: NIST)

Prestaciones en Thales nShield Connect 6000+

Algoritmo	Generación (TPS)	Firma (TPS)
RSA-2048	—	3000
NIST P-256	840	2400
NIST P-521	480	1300

DSA $\rightarrow $ ECDSA:

\[\begin{eqnarray} &&\color{red}{q | (p-1)} \\ \text{random }k &\rightarrow& 0 < k < \color{red}{q} \\ r &=& (\alpha^k \bmod p) \color{red}{\bmod q} \qquad\\ s &=& \dfrac{h(m)+a_\text{u}r}{k} \color{red}{\bmod{q}}\quad \end{eqnarray}\]

$\downarrow$

\[\begin{eqnarray} \text{random }k &\rightarrow& 0 < k < \text{ord}(A) \\ r &=& kA \bmod \text{ord}(A) \\ s &=& \dfrac{h(m)-a_\text{u}r}{k} \bmod \text{ord}(A) \\ \end{eqnarray}\]