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 trenzados para desarrollar protocolos criptográficos. Posteriormente , se identificaron otras estructuras no conmutativas como grupos de Thompson , grupos policíclicos , grupos de Grigorchuk y grupos de matrices como candidatos potenciales para aplicaciones criptográficas. A diferencia de la criptografía no conmutativa, los criptosistemas de clave pública actualmente 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 tanto, dependen de estructuras algebraicas conmutativas.

Se han desarrollado protocolos criptográficos no conmutativos para resolver diversos problemas criptográficos como el intercambio de claves , el cifrado -descifrado y la 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 asumiría que G es un grupo no abeliano . Si w y a son elementos de G, la notación w ^a indicaría el elemento a ⁻¹ wa .

Protocolos para el intercambio de claves

Protocolo debido a Ko, Lee, et al.

El siguiente protocolo debido a Ko, Lee y otros, establece una clave secreta común K para Alice y Bob .

1. Se publica un elemento w de G.
2. Se publican dos subgrupos A y B de G tales que ab = ba para todo a en A y b en B.
3. Alice elige un elemento a de A y envía w ^a a Bob. Alice mantiene un privado.
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

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

1. Elementos a ₁ , a ₂ , . . . , a _k , b ₁ , b ₂ , . . . , b _m de G son seleccionados y publicados.
2. Alice elige una x privada en G como palabra en a ₁ , a ₂ ,. . . , a _k ; es decir, x = x ( a ₁ , a ₂ , . . . , a _k ).
3. Alice envía b ₁ ^x , b ₂ ^x , . . . , bmx _a ^Bob .
4. Bob elige una y privada en G como 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 ( a ₁ ^y , a ₂ ^y , . . . , a _k ^y ) = y ⁻¹ xy . Al multiplicarlo previamente por x ⁻¹ , Alice obtiene K.
8. Bob calcula y ( b ₁ ^x , b ₂ ^x , . . . , b _m ^x ) = x ⁻¹ yx . Multiplicándolo previamente por y ⁻¹ 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 . Sean los órdenes de a y b 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 mediante K = a ^m vb ⁿ .
7. Bob calcula la clave mediante K = ar ^ub s ^.

Protocolos de cifrado y descifrado

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

1. Sea G un grupo no conmutativo. Sean A y B subgrupos públicos de G tales que ab = ba para todo a 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 plano 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. Sea G un grupo no conmutativo y sean A y B subgrupos de G tales que ab = ba para todo a en A y b en B.
2. Se selecciona y publica un elemento w de G.
3. Alice elige una s privada 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.

Bases de seguridad de los protocolos.

La base de la seguridad y solidez de los distintos 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 para resolver el problema de búsqueda de conjugación, entonces la función x → u ^x puede considerarse como una función unidireccional .

Grupos de plataformas

Un grupo no conmutativo que se utiliza en un protocolo criptográfico particular se denomina grupo de plataforma de ese protocolo. Sólo se pueden utilizar grupos que tengan determinadas propiedades 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 bien conocido y estudiado.
2. El problema verbal en G debería tener una solución rápida mediante un algoritmo determinista. Debería haber una "forma normal" eficientemente computable para los elementos de G .
3. Debería ser imposible recuperar los factores xey 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

Sea n un número entero positivo. El grupo trenzado B _n es un grupo generado por x ₁ , x ₂ , . . . , x _{n -1} teniendo 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

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 }$

El grupo de Grigorchuk.

Sea T el árbol binario de raíz infinita . El conjunto V de vértices es el conjunto de todas las secuencias binarias finitas. Sea A ( T ) 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 artín

Un grupo Artin 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 matrices

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

Productos semidirectos

^[1]

Ver también

• Criptografía basada en grupos

Referencias

1. Habeeb, M.; Kahrobaei, D.; Koupparis, C.; Shpilrain, V. (2013). "Intercambio de claves públicas utilizando productos semidirectos de (semi) grupos". Criptografía Aplicada y Seguridad de Redes. ACNS 2013 . Apuntes de conferencias sobre informática. vol. 7954. Saltador. págs. 475–486. arXiv : 1304.6572 . CiteSeerX  10.1.1.769.1289 . doi :10.1007/978-3-642-38980-1_30. ISBN 978-3-642-38980-1.

Otras lecturas

1. Myasnikov, Alexei; Shpilrain, Vladimir; Ushakov, Alejandro (2008). Criptografía basada en grupos. Birkhäuser Verlag. ISBN 9783764388270.
2. Cao, Zhenfu (2012). Nuevas direcciones de la criptografía moderna . Prensa CRC. ISBN 978-1-4665-0140-9.
3. Benjamín bien; et al. (2011). "Aspectos de la criptografía basada en grupos nobelianos: una encuesta y problemas abiertos". arXiv : 1103.4093 [cs.CR].
4. Myasnikov, Alexei G.; Shpilrain, Vladimir; Ushakov, Alejandro (2011). Criptografía no conmutativa y complejidad de problemas de teoría de grupos . Sociedad Matemática Estadounidense. ISBN 9780821853603.