Criptografía no conmutativa

La criptografía no conmutativa es el área de la criptología donde las primitivas , métodos y sistemas criptográficos se basan en estructuras algebraicas como semigrupos , grupos y anillos que no son conmutativos . Una de las primeras aplicaciones de una estructura algebraica no conmutativa con fines criptográficos fue el uso de grupos de trenzas para desarrollar protocolos criptográficos. Más tarde, varias otras estructuras no conmutativas como grupos de Thompson , grupos policíclicos , grupos de Grigorchuk y grupos de matriz.han sido identificados como candidatos potenciales para aplicaciones criptográficas. A diferencia de la criptografía no conmutativa, los criptosistemas de clave pública ampliamente utilizados como el criptosistema RSA , el intercambio de claves Diffie-Hellman y la criptografía de curva elíptica se basan en la teoría de números y, por lo tanto, dependen de estructuras algebraicas conmutativas.

Se han desarrollado protocolos criptográficos no conmutativos para resolver varios problemas criptográficos como el intercambio de claves , cifrado- descifrado y autenticación . Estos protocolos son muy similares a los protocolos correspondientes en el caso conmutativo.

Algunos protocolos criptográficos no conmutativos

En estos protocolos se supondría que G es un grupo no abeliano . Si w y una son elementos de G La notación w ^un indicaría el elemento de un ^-1 wa .

Protocolos para el intercambio de claves

Protocolo debido a Ko, Lee, et al.

El siguiente protocolo de Ko, Lee, et al., Establece una clave secreta común K para Alice y Bob .

1. Se publica un elemento w de G.
2. Dos subgrupos A y B de G tal que ab = ba para todos una en A y B en B se publican.
3. Alice elige un elemento a de A y envía w ^a a Bob. Alice mantiene una privacidad.
4. Bob elige un elemento b de B y envía w ^b a Alice. Bob mantiene b en privado.
5. Alice calcula K = ( w ^b ) ^a = w ^ba .
6. Bob calcula K ' = ( w ^a ) ^b = w ^ab .
7. Dado que ab = ba , K = K ' . Alice y Bob comparten la clave secreta común K .

Protocolo Anshel-Anshel-Goldfeld

Artículo principal: Intercambio de claves Anshel-Anshel-Goldfeld

Este es un protocolo de intercambio de claves que utiliza un grupo G no abeliano . Es significativo porque no requiere dos subgrupos de conmutación A y B de G como en el caso del protocolo debido a Ko, Lee, et al.

1. Elementos a ₁ , a ₂ ,. . . , Una _k , b ₁ , b ₂ ,. . . , b _m de G se seleccionan y publican.
2. Alice elige una x privada en G como una palabra en un ₁ , un ₂ ,. . . , a _k ; es decir, x = x ( a ₁ , a ₂ ,..., a _k ).
3. Alice envía b ₁ ^x , b ₂ ^x ,. . . , b _m ^x a Bob.
4. Bob elige un privado y en G como una palabra en b ₁ , b ₂ ,. . . , b _m ; es decir y = y ( b ₁ , b ₂ ,..., b _m ).
5. Bob envía un ₁ ^y , un ₂ ^y ,. . . , Un _k ^y a Alice.
6. Alice y Bob comparten la clave secreta común K = x ⁻¹ y ⁻¹ xy .
7. Alice Calcula x ( un ₁ ^y , un ₂ ^y ,..., Un _k ^y ) = y ^-1 xy . Pre-multiplicándola con x ^-1 , Alice recibe K .
8. Bob calcula y ( b ₁ ^x , b ₂ ^x ,..., B _m ^x ) = x ⁻¹ yx . Pre-multiplicándola con y ^-1 y luego tomando la inversa, Bob obtiene K .

Protocolo de intercambio de claves de Stickel

En la formulación original de este protocolo, el grupo utilizado fue el grupo de matrices invertibles sobre un campo finito .

1. Sea G un grupo finito público no abeliano .
2. Sean a , b elementos públicos de G tales que ab ≠ ba . Deje que las órdenes de un y b ser N y M , respectivamente.
3. Alice elige dos números aleatorios n < N y m < M y envía u = a ^m b ⁿ a Bob.
4. Bob elige dos números aleatorios r < N y s < M y envía v = a ^r b ^s a Alice.
5. La clave común compartida por Alice y Bob es K = a ^{m + r} b ^{n + s} .
6. Alice calcula la clave por K = a ^m vb ⁿ .
7. Bob calcula la clave por K = a ^r ub ^s .

Protocolos de cifrado y descifrado

Este protocolo describe cómo cifrar un mensaje secreto y luego descifrarlo utilizando un grupo no conmutativo. Deja que Alice quiera enviar un mensaje secreto m a Bob.

1. Sea G un grupo no conmutativo. Deje que A y B sean subgrupos públicas de G tal que ab = ba para todos una en A y B en B .
2. Se elige y publica un elemento x de G.
3. Bob elige una clave secreta b de A y publica z = x ^b como su clave pública.
4. Alice elige un r aleatorio de B y calcula t = z ^r .
5. El mensaje cifrado es C = ( x ^r , H ( t ) m ), donde H es alguna función hash y denota la operación XOR . Alice envía C a Bob.${\displaystyle \oplus }$ ${\displaystyle \oplus }$
6. Para descifrar C , Bob recupera t de la siguiente manera: ( x ^r ) ^b = x ^rb = x ^br = ( x ^b ) ^r = z ^r = t . El mensaje de texto sin formato enviado por Alice es P = ( H ( t ) m ) H ( t ) = m .${\displaystyle \oplus }$ ${\displaystyle \oplus }$

Protocolos de autenticación

Deje que Bob quiera comprobar si el remitente de un mensaje es realmente Alice.

1. Deje que G sea un grupo no conmutativo y dejar que A y B sean subgrupos de G tal que ab = ba para todos una en A y B en B .
2. Se selecciona y publica un elemento w de G.
3. Alice elige un privado s de A y publica el par ( w , t ) donde t = w ^s .
4. Bob elige una r de B y envía un desafío w '= w ^r a Alice.
5. Alice envía la respuesta w '' = ( w ') ^s a Bob.
6. Bob comprueba si w '' = t ^r . Si esto es cierto, entonces se establece la identidad de Alice.

Base de seguridad de los protocolos

La base de la seguridad y la fuerza de los diversos protocolos presentados anteriormente es la dificultad de los dos problemas siguientes:

• El problema de decisión de conjugación (también llamado problema de conjugación ): Dados dos elementos u y v en un grupo G, determine si existe un elemento x en G tal que v = u ^x , es decir, tal que v = x ⁻¹ ux .
• El problema de búsqueda de conjugación : Dados dos elementos u y v en un grupo G, encuentre un elemento x en G tal que v = u ^x , es decir, tal que v = x ⁻¹ ux .

Si no se conoce ningún algoritmo que resuelva el problema de búsqueda de conjugación, entonces la función x → u ^x puede considerarse una función unidireccional .

Grupos de plataforma

Un grupo no conmutativo que se utiliza en un protocolo criptográfico particular se denomina grupo de plataforma de ese protocolo. Solo los grupos que tienen ciertas propiedades pueden usarse como grupos de plataforma para la implementación de protocolos criptográficos no conmutativos. Sea G un grupo sugerido como grupo de plataforma para un determinado sistema criptográfico no conmutativo. La siguiente es una lista de las propiedades esperadas de G .

1. El grupo G debe ser conocido y estudiado.
2. El problema verbal en G debería tener una solución rápida mediante un algoritmo determinista. No debe haber una "forma normal" de manera eficiente computable para los elementos de G .
3. Debe ser imposible recuperar los factores de x y y a partir del producto xy en G .
4. El número de elementos de longitud n en G debería crecer más rápido que cualquier polinomio en n . (Aquí, "longitud n " es la longitud de una palabra que representa un elemento de grupo).

Ejemplos de grupos de plataformas

Grupos de trenzas

Artículo principal: grupo de trenzas

Sea n un número entero positivo. El grupo trenza B _n es un grupo generado por x ₁ , x ₂ ,. . . , x _{n -1 que} tenga la siguiente presentación:

${\displaystyle B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big |}x_{i}x_{j}=x_{j}x_{i}{\text{ if }}|i-j|>1{\text{ and }}x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}{\text{ if }}|i-j|=1\right\rangle }$

Grupo de Thompson

Artículo principal: grupos de Thompson

El grupo de Thompson es un grupo infinito F que tiene la siguiente presentación infinita:

${\displaystyle F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle }$

Grupo de Grigorchuk

Artículo principal: grupo de Grigorchuk

Sea T el árbol binario con raíces infinitas . El conjunto V de vértices es el conjunto de todas las secuencias binarias finitas. Deje A ( t ) denota el conjunto de todos los automorfismos de T . (Un automorfismo de T permuta los vértices preservando la conectividad.) El grupo Γ de Grigorchuk es el subgrupo de A ( T ) generado por los automorfismos a , b , c , d definidos de la siguiente manera:

• ${\displaystyle a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})}$
• ${\displaystyle b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$

Grupo Artin

Artículo principal: grupo Artin

Un Artin group A (Γ) es un grupo con la siguiente presentación:

${\displaystyle A(\Gamma )=\left\langle a_{1},a_{2},\ldots ,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i<j\leq n\right\rangle }$

donde ( factores) y .${\displaystyle \mu _{ij}=a_{i}a_{j}a_{i}\ldots }$${\displaystyle m_{ij}}$${\displaystyle m_{ij}=m_{ji}}$

Grupos de matriz

Artículo principal: grupo Matrix

Sea F un campo finito. Se han utilizado grupos de matrices sobre F como grupos de plataforma de ciertos protocolos criptográficos no conmutativos.

Productos semidirectos

Artículo principal: Producto semidirecto

^[1]

Ver también

• Criptografía basada en grupos

Lectura adicional

1. Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2008). Criptografía basada en grupos . Berlín: Birkhäuser Verlag.
2. Zhenfu Cao (2012). Nuevas direcciones de la criptografía moderna . Boca Ratón: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9.
3. Benjamin Fine; et al. (2011). "Aspectos de la criptografía basada en grupos no belianos: una encuesta y problemas abiertos". arXiv : 1103.4093 [ cs.CR ].
4. Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2011). Criptografía no conmutativa y complejidad de problemas teóricos de grupos . Sociedad Matemática Estadounidense. ISBN 9780821853603.

Referencias

1. M. Habeeb, D. Kahrobaei, C. Koupparis, V. Shpilrain, Intercambio de claves públicas mediante el producto semidirecto de (semi) grupos, en: ACNS 2013, Lecture Notes Comp. Carolina del Sur. 7954 (2013), 475--486.