Anshel Anshel Goldfeld

El protocolo de Anshel-Anshel-Goldfeld, también conocido como AAG^[1] propuesto por Iris Anshel, Michael Anshel y Dorian Goldfeld, es un protocolo de establecimiento de claves, en el cual la llave va compartida entre dos partes, por medio de un canal público. A diferencia de otros protocolos basados en grupos, este protocolo no emplea ninguna propiedad de los grupos abelianos, ya que su dificultad radica en resolver ecuaciones sobre estructuras algebraicas para estos grupos particulares, al aplicarlo se consigue ampliar el número de permutaciones posibles para conjugar la clave y el costo computacional del cálculo de la llave se reduce.^[2]

Este protocolo requiere que cada parte realice un cálculo algebraico (varias multiplicaciones seguidas de la reescritura de un monoide), luego los resultados de los cálculos, las llaves se intercambian entre las partes a través de un canal público y cada parte obtiene una clave secreta compartida, después de realizar un segundo cálculo; el segundo cálculo implica un algoritmo para resolver el problema de la palabra en el monoide.

Versión general del protocolo

El protocolo consiste en una tupla de la forma $\mathbf {U} ,\mathbf {V} ,\beta ,\gamma _{1},\gamma _{2}$ donde $\mathbf {U}$ y $\mathbf {V}$ son monoides fácilmente computables, y:

$\beta :\mathbf {U} \times \mathbf {U} \longrightarrow \mathbf {V}$ ,

$\gamma _{i}:\mathbf {U} \times \mathbf {V} \longrightarrow \mathbf {V}$ para $i\in \{1,2\}$ .

Donde $\beta ,\gamma _{1}$ y $\gamma _{2}$ funciones computables que satisfacen las siguientes propiedades:

Para todo elemento $x,y_{1},y_{2}\in \mathbf {U}$ , se tiene que: $\beta (x,y_{1}\cdot {y_{2}})=\beta (x,y_{1})\cdot \beta (x,y_{2})$
Para todo elemento $x$ , $y$ se tiene que: $\gamma _{1}(x,\beta (x,y))=\gamma _{2}(y,\beta (y,x))$
Supongamos que: $y_{1},y_{2},...y_{k}\in \mathbf {U}$ y $\beta (x,y_{1}),\beta (x,y_{2}),...,\beta (x,y_{k})$ son públicamente conocidos por algún elemento secreto $x\in \mathbf {U}$ . Entonces, en general, es inviable determinar el elemento secreto $x$ .

A los usuarios $A$ y $B$ se le asignan submonoides tales que $S_{A}$ , $T_{B}\subseteq U$ . Supongamos que $S_{A}$ es generado por los elementos:

${s_{1},s_{2},...,s_{n}}\quad {\text{donde}}\quad n\in \mathbb {N}$

y $T_{B}$ es generado por los elementos:

${t_{1},t_{2},...,t_{m}}$ donde $m\in \mathbb {N}$ .

El protocolo inicia cuando el usuario $A$ elige un elemento $a$ en $S_{A}$ y transmitiendo elementos de la forma:

$\beta (a,s_{i})\qquad i=1,...,m$ .

Y el usuario $B$ elige un elemento $b$ en $T_{B}$ transmitiendo elementos de la forma:

$\beta (b,t_{i})\qquad i=1,...,m$ .

$A$ puede calcular $\beta (a,b)$ eligiendo $b=y_{1}y_{2}$ ya que $\beta (a,y_{1})\beta (a,y_{2})=\beta (a,y_{1}y_{2})$ por la propiedad (i). De modo que $\beta (a,y_{1}y_{2})=\beta (a,b)$ . De la misma manera $B$ puede calcular $\beta (b,a)$ eligiendo $a=y_{1}y_{2}$ .

Luego la llave $k$ estaría dada por:

$k=\gamma _{1}(a,\beta (b,a))=\gamma _{2}(b,\beta (a,b))$ Dado por la propiedad iii).

Ejemplo detallado

Supongamos los monoides $\mathbf {U} =\mathbf {V}$ grupos, denotados como $\mathbf {G}$ , y los usuarios $A$ y $B$ son subgrupos asignados públicamente como $S_{A}$ y $S_{B}$ donde:

$S_{A}=\langle s_{1},s_{2},...,s_{m}\rangle \quad {\text{y}}\quad T_{B}=\langle t_{1},...,t_{n}\rangle$

Se elige la función $\beta :\mathbf {G} \times \mathbf {G} \longrightarrow \mathbf {G}$ como:

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

y las funciones $\gamma _{1}$ , $\gamma _{2}$ como:

$\gamma _{1}(u,v)=u^{-1}v,\qquad \gamma _{2}(u,v)=v^{-1}u$

Los usuarios $A$ y $B$ eligen los elementos secretos $a\in S_{A}$ y $b\in S_{B}$ respectivamente, el usuario $A$ comienza el protocolo calculando, reescribiendo y transmitiendo la colección. de elementos

$a^{-1}t_{1}a,a^{-1}t_{2}a,....,a^{-1}t_{n}a.$

De manera similar, el usuario $B$ calcula, reescribe y transmite

$b^{-1}s_{1}b,b^{-1}s_{2}b,....,b^{-1}s_{m}b.$

Un adversario que observa estas transmisiones no puede determinar $a$ ó $b$ a menos que pueda resolver un conjunto de ecuaciones de conjugación simultáneas sobre el grupo base.

Recordando que el conjugado del producto de dos elementos es el producto de Los conjugados de esos elementos (es decir, la propiedad i) de $\beta$ ), los usuarios $A$ y $B$ están ahora en posición de computar respectivamente los elementos:

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

Para obtener una clave común, el usuario A calcula

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

y el usuario por B calcula

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

Seguridad

La dureza computacional de AAG depende de la estructura de los subgrupos elegidos por lo tanto la elección adecuada de estos subgrupos produce un esquema de intercambio de claves que es resistente a todos los ataques actualmente conocidos en AAG.^[3]

Ataques

Ataques pasivos

Ataques basados en la longitud para ciertos grupos

Es un ataque probabilístico en criptosistemas de clave pública basado que interviene directamente en el problema de la palabra ya que esta tiene un tiempo polinomial solución, mientras que el problema de la conjugación no tiene solución polinomial conocida.

El método se basa en tener una forma canónica de longitud mínima para palabras en un grupo dado finamente presentado , el ataque consiste en tener un representante canónico de cada cadena en relación con la cual se puede calcular una función de longitud. De ahí el término longitud del ataque. Se sabe que tales representantes canónicos existen para el grupo de trenzas. Un ejemplo clave es el grupo de trenzas propuesto por Anshel, Anshel y Goldfel. Se indicará un posible ataque probabilístico en tal sistema, utilizando la función de longitud en el conjunto de conjugados que definen la clave pública.

Se tiene en cuenta que, ya que cada palabra tiene un canónico representativo, la función de longitud está bien definida y para el grupo de trenzas se puede calcular en tiempo polinomial en la longitud de la palabra según los resultados.^[4] La conclusión es que el ataque de longitud obliga a tomar generadores de longitud canónica no demasiados largos. Dorian Goldfeld informó que la evidencia experimental sugiere que si cada uno de los generadores S₁, ... , S_n es de < 10 en los generadores de Artin, entonces esto puede frustrar el ataque. Este ataque fue probado bajo ciertas condiciones que confirmaron su veracidad con claves débiles^[5]

Finalmente, es importante tener en cuenta que este ataque no resuelve el problema general de conjugación para el grupo de trenzas. De hecho, en este caso los factores son conocidos y limitados. En el problema general de la conjugación, el número de posibles factores es infinito. En consecuencia, el problema de la conjugación parece ser mucho más difícil y no es susceptible a esta técnica. El intercambio de claves del tipo propuesto en por Anshel,Anshel y Goldfeld^[6] requiere que se conozcan los factores y la comunicación, y proporcionar al atacante mucha más información de la que se conoce en el problema general de la conjugación.

Subgrupo de ataque

Se transforma el par de tuplas conjugadas $(a_{1},a_{2},...a_{k}),({\hat {a_{1}}},{\hat {a_{2}}},...,{\hat {a_{k}}})$ a otro par de tuplas conjugadas $(c_{1},c_{2},...c_{k}),({\hat {c_{1}}},{\hat {c_{2}}},...,{\hat {c_{k}}})$ tal que para todo :

$X\epsilon B_{n}$

tenemos que :

$X^{-1}a_{1}X={\hat {a_{i}}}(i=1,...,k)\Leftrightarrow X^{-1}c_{1}X={\hat {c_{i}}}(i=1,...,k)$

Y considerando que los elementos son más cortos:

$(c_{1},c_{2},...c_{k})\;\;es\;mas\;simple\;que\;\;(a_{1},a_{2},...a_{k})$

Para el experimento se generaron 100 pares aleatorios de tuplas $(a_{1},a_{2},...a_{k}),({\hat {a_{1}}},{\hat {a_{2}}},...,{\hat {a_{k}}})$ donde $(k=20,\;\;\;a_{i}\;\epsilon \;B_{80},\;\;\;5\leq \left|a_{i}\right|\leq 8);$

Para cada par se utilizó una secuencia de transformaciones para obtener pares de tuplas como las anteriores $(c_{1},c_{2},...c_{k}),({\hat {c_{1}}},{\hat {c_{2}}},...,{\hat {c_{k}}})$ de modo que $(c_{1},c_{2},...c_{k})$ obtiene los siguientes resultados^[7]

En el 99 % de los casos se compone de palabras cortas y positivas
En el 100 % el conjunto que se encuentra en la cima es pequeño $(c_{1},c_{2},...c_{k})$
En el 100 % el centralizador puntual $(c_{1},c_{2},...c_{k})$ coincide con el centro de $B_{n}(\;\;\;generado\;\;\;por\;\;\;\Delta ^{2})$

Los resultados obtenidos en el experimento dieron como resultado pares equivalentes de tuplas que:

$(x_{1},...,x_{79})\;\;\;en\;\;\;63\;\;\;casos$

$(x_{1},...,x_{i-1},x_{i}^{2},x_{i+1},...,x_{79})\;\;\;en\;\;\;25\;\;\;casos$

$(x_{1},...,x_{i-1},x_{i}^{2},x_{i+1},...,x_{j-1},x_{j}^{2},x_{j+1},...,x_{79})\;\;\;en\;\;\;5\;\;\;casos$

$(x_{1},...,x_{i-1},x_{i}^{2},x_{i}x_{i+1}^{2}x_{i},x_{i+2},...,x_{79})\;\;\;en\;\;\;5\;\;\;casos$

$(x_{1},...,x_{i-1},x_{i}^{2},x_{i}x_{i+1}^{2}x_{i},x_{i+1}...,x_{j-1},x_{j}^{3},x_{j+1},...,x_{79})\;\;\;en\;\;\;1\;\;\;caso$

$(x_{1},...,x_{i-1},x_{i}^{-1}x_{i+1}x_{i},x_{i+2},...,x_{79})\;\;\;en\;\;\;1\;\;\;caso$

Referencias

↑ Fernández Martínez, Isabel (2014). Introducción a la teoría combinatoria de grupos. p. 85. Consultado el 5 de junio de 2019.
↑ Hughes, James; R. Tannenbaum, Allen (2003). «Length-Based Attacks for Certain Group Based Encryption Rewriting Systems». IACR Cryptology ePrint Archive.
↑ D.Myasnikov, Alex; Ushakov, Alexander (2009). «Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol». Groups Complexity Cryptology. 1 issn=1869-6104.
↑ Birman, Joan; Ko, Ki Hyoung; Lee, Sang Jin Hyoung (1998). «A new approach to the word and conjugacy problems in the braid groups.». Advances in Math ePrint Archive.
↑ D.Myasnikov, Alex; Ushakov, Alexander. «Length Based Attack and Braid Groups». Public Key Cryptography – PKC 2007. PKC 2007.
↑ Anshel, Iris; Anshel, Michael; Goldfeld, Dorian (1999). «AN ALGEBRAIC METHOD FOR PUBLIC-KEY CRYPTOGRAPHY». Mathematical Research Letters, LNCS 1880. ISBN 978-3-540-44598-2. Archivado desde el original el 14 de junio de 2010. Consultado el 17 de julio de 2019.
↑ Shpilrain, Vladimir; Myasnikov, Alexei; Ushakov, Alexander. «Random subgroups of braid groups: cryptanalysis of a braid group based cryptographic protocoll». Public Key Cryptography – PKC 2006. PKC 2006.

Bibliografía

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

Datos: Q4770671

[1] Fernández Martínez, Isabel (2014). Introducción a la teoría combinatoria de grupos. p. 85. Consultado el 5 de junio de 2019.

[2] Hughes, James; R. Tannenbaum, Allen (2003). «Length-Based Attacks for Certain Group Based Encryption Rewriting Systems». IACR Cryptology ePrint Archive.

[3] D.Myasnikov, Alex; Ushakov, Alexander (2009). «Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol». Groups Complexity Cryptology. 1 issn=1869-6104.

[4] Birman, Joan; Ko, Ki Hyoung; Lee, Sang Jin Hyoung (1998). «A new approach to the word and conjugacy problems in the braid groups.». Advances in Math ePrint Archive.

[5] D.Myasnikov, Alex; Ushakov, Alexander. «Length Based Attack and Braid Groups». Public Key Cryptography – PKC 2007. PKC 2007.

[6] Anshel, Iris; Anshel, Michael; Goldfeld, Dorian (1999). «AN ALGEBRAIC METHOD FOR PUBLIC-KEY CRYPTOGRAPHY». Mathematical Research Letters, LNCS 1880. ISBN 978-3-540-44598-2. Archivado desde el original el 14 de junio de 2010. Consultado el 17 de julio de 2019.

[7] Shpilrain, Vladimir; Myasnikov, Alexei; Ushakov, Alexander. «Random subgroups of braid groups: cryptanalysis of a braid group based cryptographic protocoll». Public Key Cryptography – PKC 2006. PKC 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]