Protocolo de Ko-Lee-Cheon-Hang-Park

El protocolo basa su funcionamiento y fiabilidad en el uso del grupo de trenzas.

El protocolo Ko-Lee-Hang-Park es un protocolo de clave pública que usa grupos no abelianos. Fue propuesto por Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang y Choonsik Park. Utiliza el fundamento de que los grupos trenza pueden servir como una buena fuente de enriquecimiento para la criptografía, lo cual incluye lo siguiente:

• El problema de la palabra es solucionado por medio de un algoritmo rápido que computa la forma canónica que puede ser manejada de manera eficiente por computadores.
• Las operaciones de grupo pueden ser ejecutadas de manera eficiente.
• Los grupos de trenzas tienen algunos problemas matemáticos difíciles que pueden ser utilizados para diseñar primitivos criptográficos.

También tiene como fin proponer e implementar un protocolo de acuerdo de llave y sistema criptográfico de llave pública que puede ser utilizado para diseñar primitivas criptográficas. La seguridad de este sistema está basada en problemas topológicos, combinatorios y teóricos de grupos que son intractibles de acuerdo al actual conocimiento matemático. La fundamentación de este sistema es diferente a la mayoría de criptosistemas usados en teoría de números, pero existen algunas similitudes en el diseño.

Antecedentes

Desde que Diffie y Hellman presentaron por primera vez un criptosistema de llave pública usando funciones de una sola vía, algunos sistemas de cifrado de llave pública han sido vulnerados. Muchos de los sistemas de cifrado de llave pública requieren una gran cantidad de números primos. La dificultad de factorización de enteros con una gran cantidad de factores primos forma la base del sistema RSA y sus variantes como la de Rabin-Williams, el esquema de LUC o el cifrado de curva elíptica. También la dificultad del problema de algoritmo discreto forma la base de los cifrados tipo Diffie-Hellman como ElGamal.

Ha habido bastantes esfuerzos para desarrollar cifrados de llave pública alternativos que no están basados en la teoría de números. El primer intento fue usar los problemas de dificultad NP en combinatoria como el cifrado Merkle-Hellman y sus modificaciones. Algunos criptógrafos han sido pesimistas acerca de la criptografía combinatoria después del desciframiento del cifrado de clave pública tipo Knapsack realizado por Shamir, Brickell, Lagarias, Odlyzko, Vaudenay y otros. La mayoría de los criptosistemas derivados de la teoría de grupos combinatorios son principalmente teóricos o tienen ciertas limitaciones en la práctica amplia y general.

Descripción de funcionamiento

Para este protocolo de encriptación se utiliza una función unidireccional basada en el problema de conjugación en grupos trenzados, y de esta función se derivara un protocolo de establecimiento de clave y un protocolo de clave pública.

Función unidireccional

Si consideramos dos subgrupos $L{B}_l$ y $R{B}_r$ que pertenecen a $B_{l+r}$, tales que $L{B}_l$ son las trenzas formadas al trenzar las trenzas izquierdas entre $l+r$ , es decir, que las trenzas $1,2,...,l$ son las únicas que están trenzadas, y las trenzas $l+1,l+2,...,r$ no lo están. De forma similar el subgrupo $R{B}_r$ son las trenzas formadas por las trenzas trenzadas de la derecha, es decir que las trenzas $l+1,l+2,...,r$ están trenzadas, pero las trenzas $1,2,...,l$ no están trenzadas. De esta forma, cada subgrupo se genera así:

$L{B}_l$ se genera por σ${}_1$, σ${}_2$,..., σ${}_{l-1}$, y el subgrupo $R{B}_r$ se genera por σ${}_{l+1}$, σ${}_{l+2}$,..., σ${}_{r-1}$.

En la función también debe considerarse la propiedad conmutativa de los grupos trenza que dice que σ${}_i$σ${}_j=$ σ${}_j$σ${}_i$ para $|i-j|$ ≥ $2$. Así, se puede decir que para cualquier $a$ Є $L{B}_l$ y $b$ Є $R{B}_r$, entonces $ab=ba$. Así, se tiene que la función es:

$f:L{B}_l$ × $B_{l+r}$ → $B_{l+r}$ × $B_{l+r}$, $f(a,x)=(ax{a}^{-1})$

Esta función es unidireccional debido a que dados $(a,x)$ es fácil calcular $ax{a}^{-1}$, pero requiere un tiempo exponencial para calcular $a$ conociendo $(ax{a}^{-1},x)$, y en esto se basa la seguridad de este protocolo criptográfico. En este aspecto es similar al protocolo de Diffie-Hellman, ya que el rol de $x$ es similar al de $g$ en el protocolo Diffie-Hellman.

Establecimiento de clave

• Paso de preparación: Se eligen dos enteros $l$ y $r$ tales que la trenza $x$ de orden $l+r$ es suficientemente complicada, y luego esta se publica.

• Paso de establecimiento de clave:
  • Alice escoge un $a$ Є $L{B}_l$ aleatoriamente y le envía $y_1=ax{a}^{-1}$ a Bob
  • Bob escoge un $b$ Є $R{B}_r$ aleatoriamente y le envía $y_2=bx{b}^{-1}$ a Alice
  • Alice recibe $y_2$ y calcula la clave compartida $K=a{y}_2{a}^{-1}$
  • Bob recibe $y_1$ y calcula la clave compartida $K=b{y}_1{b}^{-1}$

Como se sabe que $ab=ba$, entonces:

$K=a{y}_2{a}^{-1}=a(bx{b}^{-1})a^{-1}=b(ax{a}^{-1})b^{-1}=b{y}_1{b}^{-1}$

Obteniendo Alice y Bob la misma trenza.

Protocolo de clave pública

Usando el establecimiento de clave anterior, ahora se toma una función hash $H:B_{l+r}$ → {$0,1$}$k^{}$ que se adapte del grupo de trenzas al mensaje que se quiere encriptar.

• Generación de clave:
  • Se escoge un $x$ Є $B_{l+r}$ suficientemente complicado
  • Se escoge una $a$ Є $L{B}_l$
  • Se define la clave pública como $(x,y)$, donde $y=ax{a}^{-1}$, y la clave privada sería $a$

• Encriptación: Tomando el mensaje $m$ Є {$0,1$}$k^{}$ y la clave pública definida
  • Se escoge una trenza cualquiera $b$ Є $R{B}_r$
  • Obteniendo así el texto cifrado $(c,d)$, donde $c=bx{b}^{-1}$ y $d=H(bx{b}^{-1})*m$

• Descifrado:
  • Con el texto cifrado y la clave privada se calcula $m=H(ac{a}^{-1})*d$

Como $a$ y $b$ conmutan, entonces $ac{a}^{-1}=abx{b}^{-1}{a}^{-1}=bax{a}^{-1}{b}^{-1}=by{b}^{-1}$. Así que $H(ax{a}^{-1})*d=H(bx{b}^{-1})*H(ax{a}^{-1})*m$ recuperando así el mensaje original. Para este protocolo debe elegirse un $x$ lo suficientemente complicado para evitar la “factorización” de $x$ en $x_1{x}_{2}z$, donde $x_1$ Є $L{B}_l$, $x_2$ Є $R{B}_r$ y $z$ es una trenza de orden $l+r$ conmutable con $L{B}_l$ y $R{B}_r$. Esto es así ya que si es posible descomponer fácilmente $x$, entonces:

$by{b}^{-1}=(a{x}_1{a}^{-1})(b{x}_2{b}^{-1})z$ sería fácil de calcular usando $y_1=(a{x}_1{a}^{-1})x_{2}z$ y $y_2=x_1(b{x}_2{b}^{-1})z$ sin conocer $a$ o $b$.

Operación del protocolo

Se discuten las características operativas teóricas del protocolo propuesto y los parámetros de seguridad / longitud del mensaje para futuras implementaciones, esto debido a que en el protocolo Ko-Lee-Cheon-Hang-Park no es posible comparar su desempeño con el de otros cifrados de clave pública. Recordemos que el protocolo usa tres hebras: $x\in B_{\ell +r},a\in L{B}_{\ell }$ y $b\in R{B}_r$, y el texto cifrado es $(bx{b}^{-1},H(abx{a}^{-1}{b}^{-1}\oplus m))$. Cuando se trabaja con hebras, debemos considerar dos parámetros, el índice de la hebra y la longitud canónica. Por simplicidad, asumimos que los índices de las hebras en nuestro protocolo son $l=r=\frac{n}{2}$ y las longitudes canónicas son $len(x)=len(a)=len(b)=p$. Las siguientes son las discusiones acerca de las características de operación del protocolo:

• Una $n-$permutación puede ser representada por un entero $0\le N<N!$. Mientras $n!exp(nlogn)$, una hebra con $p$cantidad de factores canónicos puede ser representada por una cadena de bits de tamaño $pnlogn$.
• Para trenza $y_1,y_2\in B_n,len(y_1,y_2)\le len(y_1)+len(y_2)$ y para $y_1\in L{B}_{\ell },y_2\in R{B}_r,len(y_1,y_2)=max(len(y_1),len(y_2))$. Entonces $len(bx{b}^{-1})$ y $len(abx{a}^{-1}{b}^{-1})$ son a lo sumo $3p$. Para selecciones genéricas de $a,b$ y $x$, estos son no menores que $2p$. Además, asumimos que $len(bx{b}^{-1})$ y $len(abxb{a}^{-1}{b}^{-1})$ están entre $2p$ y $3p$.
• El tamaño de la llave privada $a$ es $p\ell log\ell p\frac{n}{2}log\frac{n}{2}\frac{1}{2}pnlogn$.
• El tamaño de la llave pública $bx{b}^{-1}$ es a lo sumo $3pnlogn$.
• La dificultad de un ataque de fuerza bruta para computar de $a$ a $ax{a}^{-1}$, o de manera equivalente, calcular $b$ de $bx{b}^{-1}$, es proporcional a $(\ell !{)}^p=(\frac{n}{2}!{)}^{p}exp(\frac{1}{2}pnlogn)$

Estadísticas de operación del protocolo

Bloque de texto plano	bits de $pnlogn$
Bloque de texto cifrado	bits de $4pnlogn$
Velocidad de encriptado	$O(p^{2}nlogn)$
Velocidad de desencriptado	$O(p^{2}nlogn)$
Expansión de mensajes	$4-1$
Longitud de llave privada	bits de$\frac{1}{2}pnlognbits$
Longitud de llave pública	bits de $3pnlogn$
Dificultad de un ataque de fuerza bruta	$(\frac{n}{2}!{)}^{p}exp(\frac{1}{2}pnlogn)$

Análisis de seguridad

Similitudes con el esquema de ElGamal

El protocolo es similar al protocolo de ElGamal en diseño y tiene las siguientes propiedades:

• El problema de romper el protocolo Ko-Lee-Cheon-Hang-Park es equivalente a resolver el problema base, al igual que en el rompimiento del protocolo de ElGamal es equivalente a resolver el problema de Diffie-Hellman. En el esquema propuesto, el texto cifrado es:

$(c,d)=(bx{b}^{-1},H(abx{a}^{-1}{b}^{-1})\oplus m)$

Y desencriptar el texto cifrado $m$ en un texto plano $m$ es equivalente a conocer $abx{a}^{-1}{b}^{-1}$

• Como cualquier otro sistema de cifrado de llave pública, es crítico usar una llave $b$ diferente para cada sesión: Si la misma llave de sesión $b$ es usada para encriptar $m_1$ y $m_2$ cuyos textos cifrados correspondientes son $(c_1,d_1)$ y $(c_2,d_2)$, luego $m_2$ puede ser fácilmente computado de $(m_1,d_1,d_2)$ porque $H(by{b}^{-1})=m_1\oplus d_1=m_2\oplus d_2$.

Ataque de fuerza bruta

Un posible ataque de fuerza bruta es computar $a$ de $ax{a}^{-1}$ o $b$ de $bx{b}^{-1}$,lo cual es justamente un ataque al problema generalizado de búsqueda conjugada. Asuma que le ha sido dada una pareja $(x,y)$ de trenzas en $B_{\ell +r}$, tal que $y=ax{a}^{-1}$ para algún $a\in L{B}_{\ell }$. La trenza $a$ puede ser elegida de un grupo infinito $L{B}_{\ell }$ en teoría. Pero en un sistema práctico, el adversario puede generar todas las trenzas $a={\mathrm{\Delta }}^u{A}_1\dots A_p$ en la forma canónica con algún límite razonable para $p$ y revisar el punto en el que $y=ax{a}^{-1}$ corresponde.

El número necesario es como mínimo $(\frac{\ell -1}{2}!{)}^p$. Si el $\ell =45$ y $p=2$, luego $(\frac{\ell -1}{2}!{)}^p>2^{139}$, lo cual muestra que el ataque de fuerza bruta es inútil.

Bibliografía

• I. Anshel and M. Anshel, From the Post-Markov theorem through decision problems to public-key cryptography, Amer. Math. Monthly 100 (1993), no. 9, 835–844.
• I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography, Mathematical Research Letters 6 (1999) 287–291
• E. Artin, Theory of braids, Annals of Math. 48 (1947), 101–126