Anshel Anshel Goldfeld

El protocol de Anshel-Anshel-Goldfeld, també conegut com AAG propost per Iris Anshel, Michael Anshel i Dorian Goldfeld, és un protocol d'establiment de claus, en el qual la clau va compartida entre dos parts, per mig d'un canal públic. A diferència d'atres protocols basats en grups, este protocol no ampra cap propietat dels grups abelianos, ya que la seua dificultat radica en resoldre equacions sobre estructures algebraiques per a estos grups particulars, en aplicar-ho es conseguix ampliar el número de permutació possibles per a conjugar la clau i el cost computacional del càlcul de la clau es reduïx.

Este protocol requerix que cada part realise un càlcul algebraic (vàries multiplicacions seguides de la reescritura d'un monoide), després els resultats dels càlculs, les claus s'intercanvien entre les parts a través d'un canal públic i cada part obté una clau secreta compartida, despuix de realisar un segon càlcul; el segon càlcul implica un algoritme per a resoldre el problema de la paraula en el monoide.

Versió general del protocol

El protocol consistix en una tupla de la forma $𝐔,𝐕,\beta ,{\gamma }_1,{\gamma }_2$ a on $𝐔$ i $𝐕$ són monoides fàcilment computables, i:

$\beta :𝐔\times 𝐔⟶𝐕$,

${\gamma }_i:𝐔\times 𝐕⟶𝐕$ per a $i\in \{1,2\}$..

A on $\beta ,{\gamma }_1$ i ${\gamma }_2$ funcions computables que satisfan les següents propietats:

1. Per a tot element $x,y_1,y_2\in 𝐔$, es té que: $\beta (x,y_1\cdot y_2)=\beta (x,y_1)\cdot \beta (x,y_2)$
2. Per a tot element $x$, $y$ es té que: ${\gamma }_1(x,\beta (x,y))={\gamma }_2(y,\beta (y,x))$
3. Supongam que: $y_1,y_2,\mathrm{...}{y}_k\in 𝐔$ i $\beta (x,y_1),\beta (x,y_2),\mathrm{...},\beta (x,y_k)$ són públicament coneguts per algun element secret $x\in 𝐔$. Llavors, en general, és inviable determinar l'element secret $x$.

Als usuaris $A$ i $B$ se li assignen submonoides tals que $S_A$, $T_B\subseteq U$. Supongam que $S_A$ és generat pels elements:

$s_1,s_2,\mathrm{...},s_n\text{donde}n\in \mathbb{N}$

i $T_B$ és generat pels elements:

$t_1,t_2,\mathrm{...},t_m$ a on $m\in \mathbb{N}$.

El protocol inicia quan l'usuari $A$ elegix un element $a$ en $S_A$ i transmetent elements de la forma:

$\beta (a,s_i)i=1,\mathrm{...},m$.

I l'usuari $B$ elegix un element $b$ en $T_B$ transmetent elements de la forma:

$\beta (b,t_i)i=1,\mathrm{...},m$.

$A$ pot calcular $\beta (a,b)$ elegint $b=y_1{y}_2$ ya que $\beta (a,y_1)\beta (a,y_2)=\beta (a,y_1{y}_2)$ per la propietat (i). De modo que $\beta (a,y_1{y}_2)=\beta (a,b)$ . De la mateixa manera $B$ pot calcular $\beta (b,a)$ elegint $a=y_1{y}_2$.

Després la clau $k$ estaria donada per:

$k={\gamma }_1(a,\beta (b,a))={\gamma }_2(b,\beta (a,b))$ Dau per la propietat iii).

Eixemple detallat

Supongam els monoides $𝐔=𝐕$ grups, denotats com $𝐆$ , i els usuaris $A$ i $B$ són subgrups assignats públicament com $S_A$ i $S_B$ a on:

$S_A=⟨s_1,s_2,\mathrm{...},s_m⟩\text{y}{T}_B=⟨t_1,\mathrm{...},t_n⟩$

S'elegix la funció $\beta :𝐆\times 𝐆⟶𝐆$ com:

$\beta (x,y)=x^{-1}yx,$

i les funcions ${\gamma }_1$ , ${\gamma }_2$ com:

${\gamma }_1(u,v)=u^{-1}v,{\gamma }_2(u,v)=v^{-1}u$

Els usuaris $A$ i $B$ elegixen els elements secrets $a\in S_A$ i $b\in S_B$ respectivament, l'usuari $A$ comença el protocol calculant, reescrivint i transmetent la colecció. d'elements

$a^{-1}{t}_{1}a,a^{-1}{t}_{2}a,\mathrm{....},a^{-1}{t}_{n}a.$

De manera similar, l'usuari $B$ calcula, reescriu i transmet

$b^{-1}{s}_{1}b,b^{-1}{s}_{2}b,\mathrm{....},b^{-1}{s}_{m}b.$

Un adversari que observa estes transmissions no pot determinar $a$ o $b$ a menos que puga resoldre un conjunt d'equacions de conjugació simultànees sobre el grup base.

Recordant que el conjugat del producte de dos elements és el producte dels conjugats d'eixos elements (és dir, la propietat i) de $\beta$ ), els usuaris $A$ i $B$ estan ara en posició de computar respectivament els elements:

$\beta (b,a)=b^{-1}ab,\beta (a,b)=a^{-1}ba$

Per a obtindre una clau comuna, l'usuari A calcula

$k={\gamma }_1(a,\beta (b,a))=a^{-1}{b}^{-1}ab$

i l'usuari per B calcula

$k={\gamma }_2(b,\beta (a,b))$

Seguritat

La durea computacional de AAG depén de l'estructura dels subgrups elegits per lo tant l'elecció adequada d'estos subgrups produïx un esquema d'intercanvi de claus que és resistent a tots els atacs actualment coneguts en AAG.

Bibliografia

• I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), pp. 287–291.