Criptografia de
Corba El·líptica

“Curs d'Introducció a la criptografia” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

$n=24$

Corba El·líptica: longitud de clau

la dificultat d'executar el logaritme d'una clau pública $n$ és $O(\sqrt{2^{\text{longitud}_n}})$, per tant el nivell de seguretat en bits és la meitat

el NIST recomana $\|n\| \geq 224$ bit fins el 2030

ECDSA i ECDH substitueix DSA i DH respectivament ja que són més eficients, i aguantaran millor el pas del temps (hi ha implementacions amb $\|n\| = 512$ però ningú està fent servir DSA, DH o RSA amb longituds de clau equivalents (segons el NIST) de $15360$)

Cripto de Corba El·líptica

1. és busca un primer $p$ de mida apropiada: $\mathbb{F}_p$ (similar a $\mathbb{Z}_p^*$)
2. es seleccionen els “punts” que compleixen amb l'equació d'una corba el·líptica $E(\mathbb{F}_p)$
3. es "compten" els punts de la corba ($|E(\mathbb{F}_p)|$) i es verifica que (també) és un nombre primer
4. sobre aquests "punts bidimensionals" es defineixen dues operacions:

   $\begin{aligned} "+" &\rightarrow P+Q \\ "+ \text{repetida}" &\rightarrow P+P+P+\cdots+P \color{gray}{= i P} \end{aligned}$

ECDLP: EC Discrete Logarithm Problem

trobar $i$ a partir d'

$R=i A$

coneixent $R$ i $A$

és un problema de complexitat exponencial

4. Suma de punts (i suma-repetida)

enfoc geomètric; compte: $P\in E(\mathbb{R})$ no $E(\mathbb{F}_p)$

2. Cripto de Corba el·líptica

una corba el·líptica $E$ és:

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

una corba el·líptica $E(\mathbb{F}_p)$ és:

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

i per a que no tingui singularitats cal escollir $a,b \in \mathbb{F}_p$ per a que $4a^3+27b^2 \not\equiv 0 \pmod p$

les corbes el·líptiques tenen les propietats necessàries per a que l'operació $+$ estigui ben 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 punts (alguns detalls)

llavors: per a fer la suma (i suma repetida) de punts sobre $E(\mathbb{F}_p)$...
ens calen suma, resta, multiplicació i divisió sobre $\mathbb{F}_p$
$\mathbb{F}_p = \{0,1,2,\dotsc,p-1\}$

no en tenim prou amb el $\mathbb{Z}_p^*$ ja que la resta sobre $\mathbb{F}_p$ pot generar valors $P=(0,-)$

$P-P = \mathcal{O}$: si ens fixem en el gràfic, sumar $P$ a $-P$ tendeix a $(-,\infty)$ $\Rightarrow$
$\mathcal{O}$ és la identitat (o des del punt de vista gràfic és el “punt a l'inifinit”)

...

1. Cos finit $\mathbb{F}_p$

...aquest tipus de conjunts amb aquestes operacions definides
s'anomenen cossos finits

en resum, sobre $\mathbb{F}_p$ tenim que:

• les dues funcions $+$ i $\times$ definides
• té l'element nul (sobre $+$)
• té l'element identitat (sobre $\times$)
• així com la inversa definida (í única) per a tots els elements no nuls

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

$N = |E(\mathbb{F}_p)|$: cal que l'ordre¹ ($N$) tingui un factor (primer) gran

el teorema de Hasse diu que $|E(\mathbb{F}_p)|$ té com a factor
$n=p+1\pm 2\sqrt{p}$, per tant

llavors $E(\mathbb{F}_p)$ és o bé cíclic o bé té algun generador amb un ordre² gran ($n$)

escollim un d'aquests punts com a generador $A$:

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

Nota: en DH (no EC) seria equivalent a:
$\alpha^n \equiv 1 \pmod p$

Exemple

amb paràmetres reduïts

(exemple de [Johnson, Menezes, Vanstone])

Exemple amb paràmetres reduïts

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

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

llavors $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}$

i la mida és $|E(\mathbb{F}_{23})| = 29$ (la mida 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}$

Corbes estàndard

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)

Rendiment en Thales nShield Connect 6000+

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}\]

(Complexitat) $\rightarrow$