Protocolo tres envíos

En criptografía, el protocolo de tres envíos para transmisión de mensajes es un sistema que permite a un emisor enviar un mensaje a un receptor sin la necesidad de intercambiar claves. Este protoco para envío de mensajes no ha de confundirse con otros algoritmos que utilizan tres pasos para llevar a cabo una autenticación.

Este protocolo se llama así porque el emisor y el receptor intercambian un total de tres mensajes encriptados. El primer protocolo de tres pasos fue desarrollado por Adi Shamir en torno a 1980. El concepto básico del protocolo de tres pasos es que cada parte - emisor, receptor- tiene dos claves privadas, una para encriptar y otra para desencriptar. Las dos partes utilizan sus claves independientemente, primero para encriptar su mensaje y luego para desencriptarlo.

El protocolo utiliza una función de encriptación E y una de desencriptación D. La función de encriptación utiliza una clave de encriptación e para cambiar un mensaje de texto simple m a un mensaje cifrado E(e,m). Correspondiendo a cada clave de encriptación e hay una clave de descriptación d que permite recuperar el mensaje utilizando el función de desencriptación D(d,E(e,m))=m. En algunos casos, la función de encriptación y de desencriptación son la misma.

Para que la función de encriptado y la función de desencriptado sean adecuadas para el protocolo de tres pasos, se ha de cumplir la propiedad de que para cualquier mensaje m, cualquier clave de encriptado con su correspondiente clave de desencriptado d y cualquier clave independiente k, D(d,E(e,E(k,m))) = E(k,m). Es decir, ha de ser posible prescindir de la primera clave de encriptado e aunque se realice una segunda encriptación con la clave k. Esto siempre será posible con un cifrado conmutativo. Un cifrado conmutativo es un cifrado que no depende del orden, es decir, que satisface E(a,E(b,m))=E(b,E(a,m)) para todas las claves de encriptado a, b y para todos los mensajes m. Los encriptados conmutativos satisfacen la igualdad D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).

El protocolo de tres pasos funciona de la siguiente manera:

El emisor escoge una clave de encriptado s y su correspondiente clave de desencriptado t. El emisor encripta el mensaje m con la clave s E(s,m). Envía E(s,m) al receptor.
El receptor escoge una clave de encriptación r y su correspondiente clave de desencriptado q y re-encripta el primer mensaje E(s,m) con la clave r, devolviendo al emisor E(r,E(s,m)).
El emisor desencripta el segundo mensaje con su clave de desencriptado t. Por la propiedad conmutativa anteriormente descrita, D(t,E(r,E(s,m))) = E(r,m), que es el mensaje cifrado con la clave del receptor. El emisor envía E(r,m) al receptor.

Ahora, el receptor puede desencriptar el mensaje usando la clave q: D(q,E(r,m)) = m, el mensaje original.

Tómese en consideración que todas las operaciones que dependen de las claves privadas del emisor se han realizado por parte del emisor, y que todas las operaciones que dependen de las claves del receptor se han realizado por parte del receptor, indicando esto que ninguna de las partes ha necesitado intercambiar claves.

El protocolo de tres pasos de Shamir

El primer protocolo de tres envíos fue el creado por Adi Shamir, desarrollado en torno a 1980. También es conocido como Protocolo sin clave de Shamir, dado que no es necesario el intercambio de claves entre el emisor y el receptor. Aun así, emisor y receptor generan cada uno dos claves privadas, una para encriptar y otra para desencriptar mensajes. El algoritmo de Shamir utiliza exponenciación módulo un primo grande en ambas funciones: encriptación y desencriptación. Esto es E(e,m) = m^e mod p y D(d,m) = m^d mod p donde p es un primo grande. Para cualquier exponente e en el rango 1..p-1 con m.c.d(e,p-1) = 1. El correspondiente exponente de desencriptación debe satisfacer de≡ 1 (mod p-1). Esto se debe al Pequeño teorema de Fermat: D(d,E(e,m)) = m^de mod p = m.

El protocolo de Shamir tiene la deseada propiedad conmutativa, ya que E(a,E(b,m)) = m^ab mod p = m^ba mod p = E(b,E(a,m)).

El criptosistema de Massey-Omura

El criptosistema de Massey-Omura fue propuesto por James Massey y Kim K. Omura en 1982 como una posible mejora del protocolo de Shamir. El método Massey-Omura utiliza exponenciación en campos de Galois GF(2ⁿ) para encriptar y desencriptar. Esto es E(e,m)=m^e y D(d,m)=m^d donde los cálculos son realizados en cuerpos finitos de característica dos. Para cualquier exponente e con 0<e<2ⁿ-1 y mcd(e,2ⁿ-1)=1, el correspondiente exponente de desencriptación es d tal que de ≡ 1 (mod 2ⁿ-1). Dado que el grupo multiplicativo del cuerpo GF(2ⁿ) tiene orden 2ⁿ-1, por el teorema de Lagrange se tiene que m^de=m para todo m en GF(2ⁿ)^*.

Cada elemento del cuerpo finito GF(2ⁿ) está representado como un vector binario sobre una base normal; se cumple que cada vector de la base es el cuadrado del vector precedente. Esto significa que los vectores de la base son v¹, v², v⁴, v⁸, ... donde v es un elemento del cuerpo de orden máximo, es decir $2^{n}-1$ . Utilizando esta representación, elevar m a una potencia de la forma $2^{k}$ se efectúa realizando desplazamientos cíclicos de las coordenadas de m en la base mencionada previamente. Esto significa que elevar m a una potencia arbitraria se efectúa haciendo, a lo sumo, n desplazamientos y n multiplicaciones en GF(2ⁿ). Además, varias multiplicaciones se pueden realizar en paralelo. Esto permite realizar estos cálculos mucho más rápido si existe la posibilidad de computación en paralelo.

Seguridad

Una condición necesaria para que el protocolo de tres envíos sea seguro es que el atacante sea incapaz de recabar información acerca del mensaje m mediante los envíos E(s,m), E(r,E(s,m)) y E(r,m) realizados.

Para las funciones utilizadas, tanto el en método de Shamir como en el de Massey-Omura, la seguridad se basa en la dificultad que supone calcular el logaritmo discreto en un cuerpo finito. Si un atacante pudiera calcular logaritmos discretos en GF(p) para el método de Shamir o en GF(2ⁿ) para el método de Massey-Omura, el protocolo quedaría vulnerado. La clave s podría ser calculada mediante los mensajes m^r y m^rs. Cuando s sea conocido, es fácil calcular el exponente de desencriptación t. Después, el atacante podría calcular m elevando el mensaje interceptado m^s a la potencia t. K. Sakurai y H. Shizuya mostraron que bajo ciertos supuestos romper el criptosistema de Massey-Omura sería equivalente a la suposición de Diffie-Hellman.

Autenticación

La descripción dada en este artículo sobre el protocolo de tres envíos no contempla ningún tipo de autenticación. Por lo tanto, este protocolo es susceptible a un ataque de tipo man-in-the-middle si un atacante fuera capaz de crear falsos mensajes, o de interceptar y sustituir los originales transmitidos.

Referencias

Patente USPTO n.º 4567600, patente Estadounidense para el criptosistema Massey-Omura
Alan G. Konheim (1981) Cryptography: A Primer 346-7.
A. Menezes, P. VanOorschot, S. Vanstone (1996) Handbook of Applied Cryptography 500, 642.
K. Sakurai and H. Shizuya (1998) "A Structural Comparison of the Computational Difficulty of Breaking Discrete Log Cryptosystems" Journal of Cryptology 11: 29-43.

Datos: Q1907602