Criptografia de curva elíptica

La criptografia de curva elíptica (de l'anglés: elliptic curve cryptography, ECC) és una variant de la criptografia asimètrica o de clau pública basada en les matemàtiques de les curves elíptiques. Els seus autors argumenten que la CCE pot ser més ràpida i usar claus més curtes que els métodos antics —com RSA— a l'hora que proporcionen un nivell de seguritat equivalent. L'utilisació de curves elíptiques en criptografia va ser proposta de forma independent per Neal Koblitz i Victor Miller en 1985.

Introducció

Els sistemes de criptografia asimètrica o de clau pública utilisen dos claus distintes: una d'elles pot ser pública, l'atra és privada. La possessió de la clau pública no proporciona suficient informació per a determinar quin és la clau privada. Este tipo de sistemes es basa en la dificultat de trobar la solució a certs problemes matemàtics. Un d'estos problemes és el cridat logaritmo discret. Trobar el valor de b donada l'equació $a^b=c$, quan a i c són valors coneguts, pot ser un problema de complexitat exponencial per a certs grups finitos de gran tamany; mentres el problema invers, la exponenciación discreta pot ser evaluat eficientemente usant per eixemple l'exponenciación binaria.

Una curva elíptica és una curva plana definida per una equació de la forma

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

En el conjunt de punts G que formen la curva (i.i., totes les solucions de l'equació més un punt O, cridat punt en l'infinit) més una operació aditiva +, es forma un grup abeliano. Si les coordenades x i i es trien des d'un cos finito, llavors estem en presència d'un grup abeliano finito. El problema del logaritmo discret sobre este conjunt de punts (PLDCE) es creu que és més difícil de resoldre que el corresponent als cossos finitos (PLD). D'esta manera, les llongituts de claus en criptografia de curva elíptica poden ser més curtes en un nivell de seguritat comparable.

Teoria

Siga $p>3$ cosí. La curva elíptica I: $y^2=x^3+ax+b$ sobre ${\mathbb{Z}}_p$ és el conjunt de solucions $(x,y)\in {\mathbb{Z}}_p\times {\mathbb{Z}}_p$ en la congruència

$y^2=x^3+ax+b(\mathrm{mod}p)$,

a on $a,b\in {\mathbb{Z}}_p$ són constants tal que $4a^3+27b^2\ne 0(\mathrm{mod}p)$

Es definix una operació aditiva com seguix: Considerant que

$P=(x_1,y_1)$

i

$Q=(x_2,y_2)$

són punts en I i $𝒪$ és un punt en l'infinit. Si $x_2=x_1$ i $y_2=-y_1$, llavors $P+Q=𝒪$; de lo contrari $P+Q=(x_3,y_3)$, a on

$x_3={\lambda }^2-x_1-x_2$,

$y_3=\lambda (x_1-x_3)-y_1$,

i

$\lambda =\{\begin{array}{cc}\frac{y_2-y_1}{x_2-x_1},& \text{si }P\ne Q\\ \frac{3x_1^2+a}{2y_1},& \text{si }P=Q\end{array}$.

Finalment, definim

$P+𝒪=𝒪+P=P\mathrm{\forall }P\in E$.

En açò es pot mostrar que I és un grup abeliano en element identitat $𝒪$. cal notar que l'inversa de (x, i) (que s'escriu com -(x, i) ya que l'operació és aditiva) és (x, -i), per a tot $(x,y)\in E$.

D'acort a la teorema de Hasse, el número de punts #I que conté I és propenc a p. Més precisament se satisfà la següent desigualtat

$p+1-2\sqrt{p}\le \mathrm{\#}E\le p+1+2\sqrt{p}$.

Com se sap que qualsevol grup d'orde primer és cíclico, lo que es requerix és trobar un subgrup de I d'orde q (q primer) per a tindre un isomorfisme en ${\mathbb{Z}}_q$ a on el problema del logaritmo discret siga intractable. En este cas, sent $\alpha$ un generador del grup cíclico (el qual pot ser qualsevol element del grup distint de $𝒪$, l'identitat), es poden calcular les «potències» de $\alpha$ (les que s'escriuen com a múltiples de $\alpha$, degut a que l'operació del grup és aditiva).

Eixemple

Siga I la curva elíptica $y^2=x^3+x+6$ sobre ${\mathbb{Z}}_{11}$. Es calculen els punts sobre I verificant els possibles valors de $x\in {\mathbb{Z}}_{11}$, i després verificant si $z=x^3+x+6(\mathrm{mod}11)$ és un residu quadràtic. Els valors es tabulan en la següent Taula:

$x^3+x+6(\mathrm{mod}11)$

x	i
0	NO EXISTE
1	NO EXISTE
2	4, 7
3	5, 6
4	NO EXISTE
5	2, 9
6	NO EXISTE
7	2, 9
8	3, 8
9	NO EXISTE
10	2, 9

Com I té 12 punts + $O$, seguix que és cíclico i isomorfo a ${\mathbb{Z}}_{13}$. Considerant el generador $\alpha =(2,7)$, llavors:$2\alpha =(2,7)+(2,7)$

$\lambda$	$=(3\times 2^2+1)(2\times 7{)}^{-1}(\mathrm{mod}11)$
	$=2\times 3^{-1}(\mathrm{mod}11)$
	$=2\times 4(\mathrm{mod}11)$
	$=8$

Llavors tenim

$x_3=8^2-2-2(\mathrm{mod}11)=5$

i

$y_3=8(2-5)-7(\mathrm{mod}11)=-31(\mathrm{mod}11)=-9(\mathrm{mod}11)=2$

Per lo tant $2\alpha =(5,2)$

Vore també

• Curve25519
• Criptografia asimètrica
• Curva448
• Diffie-Hellman
• Elliptic-curve Diffie-Hellman

Bibliografia

• Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp203–209.
• V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
• Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999.
• Hankerson, Menezes, Vanstone: "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004.