Criptografia de corba el·líptica

La Criptografia de Corba El·líptica (CCE) és una variant de la criptografia asimètrica o de clau pública basada en les matemàtiques de les corbes el·líptiques. Els seus autors argumenten que la CCE pot ser més ràpida i usar claus més curtes que els mètodes antics - com RSA - al mateix temps que proporcionen un nivell de seguretat equivalent. La utilització de corbes el·líptiques al xifratge va ser proposada de forma independent per Neal Koblitz i Victor Miller el 1985.

Introducció

Els sistemes de criptografia asimètrica o de clau pública utilitzen dues claus diferents: una d'elles pot ser pública, l'altra és privada. La possessió de la clau pública no proporciona prou informació per determinar quina és la clau privada. Aquest tipus de sistemes es basen en la dificultat de trobar la solució a certs problemes matemàtics. Un d'aquests problemes és l'anomenat logaritme 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 finits de grans dimensions, mentre que el problema invers, l'exponenciació discreta pot ser avaluat eficientment usant per exemple exponenciació binària

Una corba el·líptica és una corba plana definida per una equació de la forma

$y^{2}=x^{3}+ax+b\,$.

Amb el conjunt de punts G que formen la corba (és a dir, totes les solucions de l'equació més un punt O, anomenat punt a l'infinit) més una operació additiva +, es forma un grup abelià. Si les coordenades x i y s'escullen des d'un cos finit, aleshores estem en presència d'un grup abelià finit. El problema del logaritme discret sobre aquest conjunt de punts (PLDCE) es creu que és més difícil de resoldre que el corresponent als cossos finits (PLD). D'aquesta manera, les longituds de claus en criptografia de corba el·líptica poden ser més curtes amb un nivell de seguretat comparable.

Introducció matemàtica

Sigui $p>3$ primer. La corba el·líptica E $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}$ a la congruència

$y^{2}=x^{3}+ax+b{\pmod {p}}\,$,

on $a,b\in \mathbb {Z} _{p}$ són constants tal que $4a^{3}+27b^{2}\neq 0{\pmod {p}}$

Es defineix una operació additiva de la manera següent: Atès que

$P=(x_{1},y_{1})$

i

$Q=(x_{2},y_{2})$

són punts en E i ${\mathcal {O}}$ és un punt a l'infinit. Si $x_{2}=x_{1}$ i $y_{2}=-y_{1}$, llavors $P+Q={\mathcal {O}}$; en cas contrari $P+Q=(x_{3},y_{3})$, on

$x_{3}=\lambda ^{2}-x_{1}-x_{2}$,

$y_{3}=\lambda (x_{1}-x_{3})-y_{1}$,

i

$\lambda ={\begin{cases}{\cfrac {y_{2}-y_{1}}{x_{2}-x_{1}}},&{\mbox{si}}P\neq Q\\{\cfrac {3x_{1}^{2}+a}{2y_{1}}},&{\mbox{si}}P=Q\end{cases}}$.

Finalment, definim

$P+{\mathcal {O}}={\mathcal {O}}+P=P\ \forall P\in E$.

Amb això es pot mostrar que L és un grup abelià amb element identitat ${\mathcal {O}}$. Cal notar que la inversa de (x, y) (que s'escriu com - (x, y), ja que l'operació és additiva) és (x,-y), per a tot $(x,y)\in E$

D'acord amb el teorema de Hasse, el nombre de punts #E que conté L és proper a p . Més precisament se satisfà la següent desigualtat

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

Com que se sap que qualsevol grup d'ordre primer és cíclic, el que cal és trobar un subgrup de L d'ordre q (q primer) per tenir un isomorfisme amb $\mathbb {Z} _{q}$ on el problema del logaritme discret sigui intractable. En aquest cas, sent $\alpha$ un generador del grup cíclic (el qual pot ser qualsevol element del grup diferent de ${\mathcal {O}}$, la identitat), es poden calcular les "potències" de $\alpha$ (les quals s'escriuen com múltiples de $\alpha$, pel fet que l'operació del grup és additiva).

Exemple

Sigui E la corba el·líptica $y^{2}=x^{3}+x+6$ sobre $\mathbb {Z} _{11}$. Es calculen els punts sobre E verificant els possibles valors de $x\in \mathbb {Z} _{11}$, i després verificant si $z=x^{3}+x+6{\pmod {11}}$ és un residu quadràtic. Els valors es tabulen en la següent Taula,

$x$	$x^{3}+x+6{\pmod {11}}$	$y$	punts $(x,y)$
0	6
1	8
2	5	4,7	$(2,4)(2,7)$
3	3	5,6	$(3,5)(3,6)$
4	8
5	4	2,9	$(5,2)(5,9)$
6	8
7	4	2,9	$(7,2)(7,9)$
8	9	3,8	$(8,3)(8,8)$
9	7
10	4	2,9	$(10,2)(10,9)$

Com que E té 12 punts $+{\mathcal {O}}$, se segueix que és cíclic i isomorf a $\mathbb {Z} _{13}$. Atès el generador $\alpha =(2,7)$, aleshores: $2\alpha =(2,7)+(2,7)$

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

Aleshores tenim

$x_{3}=8^{2}-2-2{\pmod {11}}=5$

i

$y_{3}=8(2-5)-7{\pmod {11}}=2$

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

L'ordre del subgrup amb generador $G$ és el menor nombre n que fa $nG={\mathcal {O}}$, i normalment és primer. En el nostre exemple és $13$

$+$	${\mathcal {O}}$	$(2,4)$	$(2,7)$	$(3,5)$	$(3,6)$	$(5,2)$	$(5,9)$	$(7,2)$	$(7,9)$	$(8,3)$	$(8,8)$	$(10,2)$	$(10,9)$
${\mathcal {O}}$	${\mathcal {O}}$	(2,4)	(2,7)	(3,5)	(3,6)	(5,2)	(5,9)	(7,2)	(7,9)	(8,3)	(8,8)	(10,2)	(10,9)
$(2,4)$	(2,4)	(5,9)	${\mathcal {O}}$	(7,2)	(10,2)	(2,7)	(8,8)	(7,9)	(3,6)	(5,2)	(10,9)	(8,3)	(3,5)
$(2,7)$	(2,7)	${\mathcal {O}}$	(5,2)	(10,9)	(7,9)	(8,3)	(2,4)	(3,5)	(7,2)	(10,2)	(5,9)	(3,6)	(8,8)
$(3,5)$	(3,5)	(7,2)	(10,9)	(8,3)	${\mathcal {O}}$	(8,8)	(7,9)	(5,2)	(2,7)	(5,9)	(3,6)	(2,4)	(10,2)
$(3,6)$	(3,6)	(10,2)	(7,9)	${\mathcal {O}}$	(8,8)	(7,2)	(8,3)	(2,4)	(5,9)	(3,5)	(5,2)	(10,9)	(2,7)
$(5,2)$	(5,2)	(2,7)	(8,3)	(8,8)	(7,2)	(10,2)	${\mathcal {O}}$	(10,9)	(3,5)	(3,6)	(2,4)	(7,9)	(5,9)
$(5,9)$	(5,9)	(8,8)	(2,4)	(7,9)	(8,3)	${\mathcal {O}}$	(10,9)	(3,6)	(10,2)	(2,7)	(3,5)	(5,2)	(7,2)
$(7,2)$	(7,2)	(7,9)	(3,5)	(5,2)	(2,4)	(10,9)	(3,6)	(2,7)	${\mathcal {O}}$	(8,8)	(10,2)	(5,9)	(8,3)
$(7,9)$	(7,9)	(3,6)	(7,2)	(2,7)	(5,9)	(3,5)	(10,2)	${\mathcal {O}}$	(2,4)	(10,9)	(8,3)	(8,8)	(5,2)
$(8,3)$	(8,3)	(5,2)	(10,2)	(5,9)	(3,5)	(3,6)	(2,7)	(8,8)	(10,9)	(7,9)	${\mathcal {O}}$	(7,2)	(2,4)
$(8,8)$	(8,8)	(10,9)	(5,9)	(3,6)	(5,2)	(2,4)	(3,5)	(10,2)	(8,3)	${\mathcal {O}}$	(7,2)	(2,7)	(7,9)
$(10,2)$	(10,2)	(8,3)	(3,6)	(2,4)	(10,9)	(7,9)	(5,2)	(5,9)	(8,8)	(7,2)	(2,7)	(3,5)	${\mathcal {O}}$
$(10,9)$	(10,9)	(3,5)	(8,8)	(10,2)	(2,7)	(5,9)	(7,2)	(8,3)	(5,2)	(2,4)	(7,9)	${\mathcal {O}}$	(3,6)

Ús en criptografia

En l'ús criptogràfic, es tria un punt base G específic i publicat per utilitzar amb la corba L ( q ). Es tria un nombre enter aleatori k com a clau privada, i llavors el valor P = k * G es dona a conèixer com a clau pública (noteu que la suposada dificultat del PLDCE implica que k és difícil de deduir a partir de P ). Si Alícia i Bernat tenen les claus privades k _A i k _B , i les claus públiques P _A i P _B , llavors Alícia podria calcular k _A * P _B = ( k _A * k _B ) * G ; i Bernat pot obtenir el mateix valor, ja que k _B * P _A = ( k _B * k _A ) * G .

Això permet establir un valor "secret" que tant Alícia com Bernat poden calcular fàcilment, però que és molt complicat de derivar per a una tercera persona. A més, Bernat no aconsegueix esbrinar res de nou sobre k _A durant aquesta transacció, de manera que la clau d'Alícia continua sent privada.

Els mètodes utilitzats en la pràctica per a xifrar missatges basant-se en aquest valor secret consisteixen en adaptacions d'antics criptosistemes de logaritmes discrets originalment dissenyats per ser usats en altres grups. Entre ells es podrien incloure Diffie-Hellman, ElGamal i DSA.

La realització de les operacions necessàries per executar aquest sistema és més lenta que per a un sistema de factorització o de logaritme discret mòdul sencer de la mateixa mida. De tota manera, els autors de sistemes de CCE creuen que el PLDCE és significativament més complicat que els problemes de factorització o del PLD, i així es pot obtenir la mateixa seguretat mitjançant mides de les claus molt més curtes utilitzant CCE, fins al punt que pot resultar més ràpid que, per exemple, RSA. Els resultats publicats fins ara tendeixen a confirmar això, encara que alguns experts es mantenen escèptics.

La CCE ha estat àmpliament reconeguda com l'algorisme més fort per a una determinada longitud de clau, de manera que podria ser útil sobre enllaços que tinguin requisits molt limitats d'amplada de banda.

NIST i ANSI X9 han establert uns requisits mínims de mida de la clau de 1024 bits per a RSA i DSA i de 160 bits per ECC, corresponents a un bloc simètric de clau de 80 bits. NIST ha publicat una llista de corbes el·líptiques recomanades de 5 mides diferents de claus (80, 112, 128, 192, 256). En general, la CCE sobre un grup binari requereix una clau asimètrica del doble de mida que el corresponent a una clau simètrica.

Certicom és la principal empresa comercial de CCE. Aquesta organització té 130 patents, i ha atorgat llicències sobre tecnologia a la National Security Agency (NSA) per 25 milions de dòlars. Certicom també ha patrocinat diversos desafiaments a l'algorisme CCE. El més complex resolt fins ara és una clau de 109 bits, que va ser trencat per un equip d'investigadors a principis de 2003. L'equip que va trencar la clau va utilitzar un atac massiu en paral·lel basat en el 'birthday attack', mitjançant més de 10.000 PC de tipus Pentium funcionant contínuament durant 540 dies. S'estima que la longitud de clau mínima recomanada per CCE (163 bits) requeriria 10 ⁸ vegades els recursos utilitzats per resoldre el problema amb 109 bits.

Referències

• 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

Enllaços externs

• Recommended Elliptic Curves for Government Use, NIST document (PDF file)
• press_archive & view = 121 Certicom press release regarding 109 bit ACC challenge
• home Certicom Online ACC Tutorial