Protocolo de Ko-Lee-Cheon-Hang-Park

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.

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

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.^[1]

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 ${\displaystyle LB_{l}}$ y ${\displaystyle RB_{r}}$ que pertenecen a ${\displaystyle B_{l+r}}$, tales que ${\displaystyle LB_{l}}$ son las trenzas formadas al trenzar las trenzas izquierdas entre ${\displaystyle l+r}$ , es decir, que las trenzas ${\displaystyle 1,2,...,l}$ son las únicas que están trenzadas, y las trenzas ${\displaystyle l+1,l+2,...,r}$ no lo están. De forma similar el subgrupo ${\displaystyle RB_{r}}$ son las trenzas formadas por las trenzas trenzadas de la derecha, es decir que las trenzas ${\displaystyle l+1,l+2,...,r}$ están trenzadas, pero las trenzas ${\displaystyle 1,2,...,l}$ no están trenzadas. De esta forma, cada subgrupo se genera así:

${\displaystyle LB_{l}}$ se genera por σ${\displaystyle _{1}}$, σ${\displaystyle _{2}}$,..., σ${\displaystyle _{l-1}}$, y el subgrupo ${\displaystyle RB_{r}}$ se genera por σ${\displaystyle _{l+1}}$, σ${\displaystyle _{l+2}}$,..., σ${\displaystyle _{r-1}}$.

En la función también debe considerarse la propiedad conmutativa de los grupos trenza que dice que σ${\displaystyle _{i}}$σ${\displaystyle _{j}=}$ σ${\displaystyle _{j}}$σ${\displaystyle _{i}}$ para ${\displaystyle |i-j|}$ ≥ ${\displaystyle 2}$. Así, se puede decir que para cualquier ${\displaystyle a}$ Є ${\displaystyle LB_{l}}$ y ${\displaystyle b}$ Є ${\displaystyle RB_{r}}$, entonces ${\displaystyle ab=ba}$. Así, se tiene que la función es:

${\displaystyle f:LB_{l}}$ × ${\displaystyle B_{l+r}}$ → ${\displaystyle B_{l+r}}$ × ${\displaystyle B_{l+r}}$, ${\displaystyle f(a,x)=(axa^{-1})}$

Esta función es unidireccional debido a que dados ${\displaystyle (a,x)}$ es fácil calcular ${\displaystyle axa^{-1}}$, pero requiere un tiempo exponencial para calcular ${\displaystyle a}$ conociendo ${\displaystyle (axa^{-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 ${\displaystyle x}$ es similar al de ${\displaystyle g}$ en el protocolo Diffie-Hellman.

Establecimiento de clave

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

• Paso de establecimiento de clave:
  • Alice escoge un ${\displaystyle a}$ Є ${\displaystyle LB_{l}}$ aleatoriamente y le envía ${\displaystyle y_{1}=axa^{-1}}$ a Bob
  • Bob escoge un ${\displaystyle b}$ Є ${\displaystyle RB_{r}}$ aleatoriamente y le envía ${\displaystyle y_{2}=bxb^{-1}}$ a Alice
  • Alice recibe ${\displaystyle y_{2}}$ y calcula la clave compartida ${\displaystyle K=ay_{2}a^{-1}}$
  • Bob recibe ${\displaystyle y_{1}}$ y calcula la clave compartida ${\displaystyle K=by_{1}b^{-1}}$

Como se sabe que ${\displaystyle ab=ba}$, entonces:

${\displaystyle K=ay_{2}a^{-1}=a(bxb^{-1})a^{-1}=b(axa^{-1})b^{-1}=by_{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 ${\displaystyle H:B_{l+r}}$ → {${\displaystyle 0,1}$}${\displaystyle ^{k}}$ que se adapte del grupo de trenzas al mensaje que se quiere encriptar.

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

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

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

Como ${\displaystyle a}$ y ${\displaystyle b}$ conmutan, entonces ${\displaystyle aca^{-1}=abxb^{-1}a^{-1}=baxa^{-1}b^{-1}=byb^{-1}}$. Así que ${\displaystyle H(axa^{-1})*d=H(bxb^{-1})*H(axa^{-1})*m}$ recuperando así el mensaje original. Para este protocolo debe elegirse un ${\displaystyle x}$ lo suficientemente complicado para evitar la “factorización” de ${\displaystyle x}$ en ${\displaystyle x_{1}x_{2}z}$, donde ${\displaystyle x_{1}}$ Є ${\displaystyle LB_{l}}$, ${\displaystyle x_{2}}$ Є ${\displaystyle RB_{r}}$ y ${\displaystyle z}$ es una trenza de orden ${\displaystyle l+r}$ conmutable con ${\displaystyle LB_{l}}$ y ${\displaystyle RB_{r}}$. Esto es así ya que si es posible descomponer fácilmente ${\displaystyle x}$, entonces:

${\displaystyle byb^{-1}=(ax_{1}a^{-1})(bx_{2}b^{-1})z}$ sería fácil de calcular usando ${\displaystyle y_{1}=(ax_{1}a^{-1})x_{2}z}$ y ${\displaystyle y_{2}=x_{1}(bx_{2}b^{-1})z}$ sin conocer ${\displaystyle a}$ o ${\displaystyle b}$.^[2]

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: ${\displaystyle x\in B_{\ell +r},a\in LB_{\ell }}$ y ${\displaystyle b\in RB_{r}}$, y el texto cifrado es ${\displaystyle (bxb^{-1},H(abxa^{-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 ${\displaystyle l=r={\frac {n}{2}}}$ y las longitudes canónicas son ${\displaystyle len(x)=len(a)=len(b)=p}$. Las siguientes son las discusiones acerca de las características de operación del protocolo:

• Una ${\displaystyle n-}$permutación puede ser representada por un entero ${\displaystyle 0\leq N<N!}$. Mientras ${\displaystyle n!~exp(nlogn)}$, una hebra con ${\displaystyle p}$cantidad de factores canónicos puede ser representada por una cadena de bits de tamaño ${\displaystyle pn\;log\;n}$.
• Para trenza ${\displaystyle y_{1},y_{2}\in B_{n},len(y_{1},y_{2})\leq len(y_{1})+len(y_{2})}$ y para ${\displaystyle y_{1}\in LB_{\ell },y_{2}\;\in \;RB_{r},len(y_{1},y_{2})=max(len(y_{1}),len(y_{2}))}$. Entonces ${\displaystyle len(bxb^{-1})}$ y ${\displaystyle len(abxa^{-1}b^{-1})}$ son a lo sumo ${\displaystyle 3p}$. Para selecciones genéricas de ${\displaystyle a,b}$ y ${\displaystyle x}$, estos son no menores que ${\displaystyle 2p}$. Además, asumimos que ${\displaystyle len(bxb^{-1})}$ y ${\displaystyle len(abxba^{-1}b^{-1})}$ están entre ${\displaystyle 2p}$ y ${\displaystyle 3p}$.
• El tamaño de la llave privada ${\displaystyle a}$ es ${\displaystyle p\ell \;log\;\ell \;~p{\frac {n}{2}}log{\frac {n}{2}}~{\frac {1}{2}}pn\;log\;n}$.
• El tamaño de la llave pública ${\displaystyle bxb^{-1}}$ es a lo sumo ${\displaystyle 3pn\;log\;n}$.
• La dificultad de un ataque de fuerza bruta para computar de ${\displaystyle a}$ a ${\displaystyle axa^{-1}}$, o de manera equivalente, calcular ${\displaystyle b}$ de ${\displaystyle bxb^{-1}}$, es proporcional a ${\displaystyle (\ell$ !)^{p}=({\frac {n}{2}}!)^{p}\;~\;exp({\frac {1}{2}}pn\;log\;n)}

Estadísticas de operación del protocolo

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

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:

${\displaystyle (c,d)=(bxb^{-1},H(abxa^{-1}b^{-1})\;\oplus \;m)}$

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

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

Ataque de fuerza bruta

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

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

Referencias

1. Ko, Ki (21 de julio de 2016). «New Public-key Cryptosystem Using Braid Groups». 22 de julio de 2016. PMID 110861. Consultado el https://www.iacr.org/archive/crypto2000/18800166/18800166.pdf.
2. Zhaohui, Cheng (11 de enero de 2011). «Pairing-Based One-Round Tripartite Key Agreement Protocols». Pairing-Based One-Round Tripartite Key Agreement Protocols. Archivado desde el original el 15 de julio de 2019. Consultado el 13 de julio de 2019.
3. Lee, Ko (25 de junio de 2000). «An Authenticated Group Key Agreement Protocol on Braid groups». 25 de junio de 2002. PMID 110861. Consultado el 23 de julio de 2019.

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

• Datos: Q97369184