"Protocolos de criptosistemas": Diffie - Hellman, El-Gamal, MTI / A (0), STS

Al igual que los creadores de los protocolos de tres pasos de la sección anterior , los autores de los siguientes algoritmos los consideraron no solo construcciones matemáticas que proporcionan una operación elemental (por ejemplo, cifrado de clave pública), sino que intentaron construir un sistema completo de distribución de claves alrededor de una o dos fórmulas. Algunas de estas construcciones, que se han transformado, se utilizan hasta la fecha (por ejemplo, el protocolo Diffie-Hellman), algunas de ellas permanecen solo en la historia de la criptografía y la protección de la información.

Más adelante en la década de 1990, se separarán las primitivas asimétricas matemáticas (cifrado y firma electrónica) y los protocolos, se utilizarán estas primitivas, que se demostrarán en la sección sobre protocolos asimétricos.

Diffie - Protocolo Hellman

El primer algoritmo de clave pública fue propuesto por Diffie y Hellman en 1976, "Nuevas direcciones en criptografía" ( Bailey Whitfield Diffie, Martin Edward Hellman, "Nuevas direcciones en criptografía" , [Diffie, Hellman 1976] ). Este protocolo, que también se puede llamar el esquema Diffie-Hellman , fue el primero en reducir los requisitos para que el canal de comunicación establezca una conexión segura sin intercambiar primero las claves.

El protocolo permite a dos partes crear una clave de sesión común utilizando un canal de comunicación que un atacante puede escuchar, pero bajo el supuesto de que este último no puede cambiar el contenido de los mensajes.

Dejar $$$p$ - un número primo grande $$$g$ - un elemento primitivo del grupo $$$\ mathbb {Z} _p ^ *$ , $$$y = g ^ x \ bmod p$ y $$$p$ , $$$y$ y $$$g$ conocido de antemano. Función $$$y = g ^ {x} \ bmod p$ consideramos unidireccional, es decir, calcular una función con un valor conocido de un argumento es una tarea fácil, y su inversión (encontrar un argumento) con un valor conocido de una función es difícil. (Función inversa $$$x = \ log_g y \ bmod p$ llamado la función de logaritmo discreto. Actualmente no hay formas rápidas de calcular dicha función para grandes simples $$$p$ .)

El protocolo de intercambio consta de las siguientes acciones.

1. Alice elige un azar $$$2 \ leq a \ leq p - 1$
   $$$Alice \ to \ left \ {A = g ^ a \ bmod p \ right \} \ a Bob$
2. Bob elige al azar $$$2 \ leq b \ leq p-1$
   Bob calcula la clave de sesión $$$K = A ^ b \ bmod p$
   $$$Bob \ to \ left \ {B = g ^ b \ bmod p \ right \} \ para Alice$
3. Alice calcula $$$K = B ^ a \ bmod p$
   

De esta manera, se crea una clave de sesión secreta compartida $$$K$ . Debido a la selección aleatoria de valores $$$a$ y $$$b$ en una nueva sesión, se recibirá una nueva clave de sesión.

El protocolo proporciona solo la generación de nuevas claves de sesión (objetivo G10). En ausencia de un tercero de confianza, no proporciona autenticación de las partes (objetivo G1), debido a la falta de pasajes con confirmación de propiedad de la clave, no hay autenticación de clave (objetivo G8). Pero, dado que el protocolo no utiliza claves "maestras" largas, podemos decir que tiene la propiedad del secreto directo perfecto (objetivo G9).

El protocolo solo se puede usar con canales de comunicación en los que un criptoanalista activo no puede intervenir. De lo contrario, el protocolo se vuelve vulnerable a un simple "ataque medio".

1. Alice elige un azar $$$2 \ leq a \ leq p - 1$
   $$$Alice \ to \ left \ {A = g ^ a \ bmod p \ right \} \ to Mellory ~ (Bob)$
2. Mallory elige un azar $$$2 \ leq m \ leq p-1$
   Mallory calcula una clave de sesión para un canal con Alice
   

   $$

   $$K_ {AM} = A ^ m \ bmod p = g ^ {am} \ bmod p$$
   
   $$$Mellory ~ (Alice) \ a \ left \ {M = g ^ m \ bmod p \ right \} \ a Bob$
   $$$Mellory ~ (Bob) \ a \ left \ {M = g ^ m \ bmod p \ right \} \ a Alice$
3. Alice calcula la clave de sesión para el canal con Mallory (pensando que Mallory es Bob)
   

   $$

   $$K_ {AM} = M ^ a \ bmod p = g ^ {am} \ bmod p$$
4. Bob elige al azar $$$2 \ leq b \ leq p-1$
   Bob calcula la clave de sesión para el canal con Mallory (pensando que Mallory es Alice)
   

   $$

   $$K_ {BM} = M ^ b \ bmod p = g ^ {bm} \ bmod p$$
   
   $$$Bob \ to \ left \ {B = g ^ b \ bmod p \ right \} \ to Mellory ~ (Alice)$
5. Mallory calcula una clave de sesión para un canal con Bob
   

   $$

   $$K_ {BM} = B ^ m \ bmod p = g ^ {bm} \ bmod p$$
   
   

Como resultado, Alice y Bob recibieron nuevas claves de sesión, pero no establecieron un canal de comunicación "seguro" entre ellos, sino con un atacante que ahora tiene la capacidad de retransmitir o cambiar todos los mensajes transmitidos entre Alice y Bob.

El protocolo Diffie-Hellman difiere de la mayoría de los protocolos de distribución clave debido al hecho de que no utiliza otras primitivas criptográficas (cifrado, firma digital o funciones de hashing), pero en sí mismo es, en cierto sentido, una primitiva criptográfica para construir protocolos más complejos. Proporciona generación de números aleatorios en un sistema distribuido sin un centro confiable. Además, ninguno de los lados puede obligar al otro lado a usar la clave de sesión anterior, a diferencia, por ejemplo, del protocolo Yahalom.

El protocolo se puede cambiar para que, en lugar del grupo multiplicativo de multiplicación simple, use el grupo aditivo de adición de puntos de la curva elíptica. En este caso, las partes aún elegirán algunos enteros aleatorios, pero no elevan el número del generador a una potencia, sino que multiplican el punto del generador por el número deseado.

1. Las partes acordaron un grupo de puntos de la curva elíptica. $$$\ mathbb {E}$ su subgrupo cíclico $$$\ mathbb {G}$ poder $$$n = \ | \ mathbb {G} \ |$ y generador $$$G$ grupos $$$\ mathbb {G}$ (o al menos un subgrupo suficientemente grande del grupo $$$\ mathbb {G}$ )
2. Alice elige un azar $$$2 \ leq a \ leq n - 1$
   $$$Alice \ to \ left \ {A = a \ times G \ right \} \ to Bob$
3. Bob elige al azar $$$2 \ leq b \ leq n - 1$
   Bob calcula el punto $$$K = b \ veces A$
   $$$Bob \ to \ left \ {B = g \ times G \ right \} \ to Alice$
4. Alice calcula el punto $$$K = a \ veces B$

Como una nueva clave de sesión, las partes pueden elegir, por ejemplo, la primera coordenada del punto encontrado $$$K$ .

Protocolo de El Gamal

El protocolo El-Gamal ( [ElGamal, 1984] , [ElGamal, 1985] ), debido a la distribución preliminar de la clave pública de una de las partes, proporciona autenticación de la clave para este lado. Se puede garantizar que solo el propietario de la clave privada correspondiente puede calcular la clave de sesión. Sin embargo, la confirmación de la recepción de la clave (cumplimiento de los objetivos G1 y G8) no forma parte del protocolo.

1. Alice y Bob eligen opciones comunes $$$p$ y $$$g$ donde $$$p$ Es un número primo grande y $$$g$ - elemento de campo primitivo $$$\ mathbb {Z} _p ^ *$ .
   Bob crea un par de claves privadas y públicas $$$b$ y $$$K_B$ :
   

   $$

   $$\ begin {array} {l} b: 2 \ leq b \ leq p - 1, \\ K_B = g ^ b \ bmod p. \ end {array}$$
   
   Clave pública $$$K_B$ Es de acceso público abierto para todas las partes. Un criptoanalista no puede reemplazarlo; la sustitución será notable.
2. Alice escoge un secreto $$$x$ y calcula la clave de sesión $$$K$
   

   $$

   $$K = K_B ^ {x} = g ^ {bx} \ bmod p. $$$
   
   

   $$

   $$Alice \ to \ left \ {g ^ x \ bmod p \ right \} \ a Bob$$
3. Bob calcula la clave de sesión
   

   $$

   $$K = (g ^ x) ^ {b} = g ^ {bx} \ bmod p. $$$

El protocolo no garantiza la selección de una nueva clave de sesión en cada sesión de protocolo (G10), y el uso de una clave "maestra" $$$K_B$ transferir una clave de sesión permite a un atacante calcular todas las claves de sesión de sesiones pasadas cuando una clave privada se ve comprometida $$$b$ (objetivo G9).

Protocolo MTI / A (0)

En 1986, C. Matsumoto ( Tsutomu Matsumoto ), I. Takashima ( Youichi Takashima ) y H. Imai ( Hideki Imai ) propusieron varios algoritmos, más tarde llamados la familia del protocolo MTI ( [Matsumoto, Tsutomu, Imai 1986] ). Debido a la distribución preliminar de las claves públicas de ambas partes, proporcionaron autenticación de clave implícita (objetivo G7). Es decir, una clave de sesión solo podría ser garantizada para ser recibida por los propietarios de las claves públicas correspondientes. Consideraremos a uno de los representantes de esta familia: el protocolo MTI / A (0).

Anteriormente, las partes acordaron los parámetros generales del sistema. $$$p$ y $$$g$ donde $$$p$ Es un número primo grande y $$$g$ - elemento de campo primitivo $$$\ mathbb {Z} _p ^ *$ .


Cada una de las partes (Alice y Bob) generó un par de claves privadas y públicas:

$$

$$\ begin {array} {ll} Alice: & ~ a, ~~ K_A = g ^ a \ bmod p, \\ Bob: & ~ b, ~~ K_B = g ^ b \ bmod p. \\ \ end {array}$$

1. Alice generó un número aleatorio $$$R_A: ~ 2 \ leq R_A \ leq p-1$
   $$$Alice \ to \ left \ {g ^ {R_A} \ bmod p \ right \} \ a Bob$
2. Bob generó un número aleatorio $$$R_B: ~ 2 \ leq R_B \ leq p-1$
   Bob descubrió una clave de sesión $$$K = (g ^ {R_A}) ^ b \ cdot K_A ^ {R_B} \ bmod p$
   $$$Bob \ to \ left \ {g ^ {R_B} \ bmod p \ right \} \ para Alice$
3. Alice calculó la clave de sesión $$$K = (g ^ {R_B}) ^ a \ cdot K_B ^ {R_A} \ bmod p$

Si las claves públicas $$$K_A$ y $$$K_B$ coincide con tus claves privadas $$$a$ y $$$b$ , entonces las claves de sesión calculadas por los participantes coinciden:

$$

$$\ begin {array} {lll} (g ^ {R_A}) ^ b \ cdot K_A ^ {R_B} \ bmod p & = & g ^ {b R_A + a R_B} \ bmod p, \\ (g ^ { R_B}) ^ a \ cdot K_B ^ {R_A} \ bmod p & = & g ^ {a R_B + b R_A} \ bmod p. \ end {array}$$

Debido a la complejidad de la tarea de logaritmo discreto, un atacante no podrá obtener $$$a, R_A$ o $$$b, R_B$ de los mensajes transmitidos, y la publicación preliminar de claves públicas garantiza que solo los usuarios legítimos reciban la clave de sesión. Selección aleatoria $$$R_A$ y $$$R_B$ garantiza que ambas partes puedan estar seguras de crear una nueva clave de sesión en cada sesión de protocolo.

Al igual que otros representantes de los protocolos del sistema criptográfico, MTI no se desarrolló teniendo en cuenta la posibilidad de comprometer las claves "maestras" cerradas $$$a$ y $$$b$ (objetivo G9).

Protocolo de estación a estación

El protocolo STS ( estación a estación , [Diffie, Oorschot, Wiener 1992] ) está destinado a sistemas de comunicación móvil. Utiliza las ideas del protocolo Diffie-Hellman y el criptosistema RSA. Una característica del protocolo es el uso de un mecanismo de firma electrónica para la autenticación mutua de las partes.

Anteriormente, las partes acordaron los parámetros generales del sistema. $$$p$ y $$$g$ donde $$$p$ Es un número primo grande y $$$g$ - elemento de campo primitivo $$$\ mathbb {Z} _p ^ *$ .

Cada lado $$$A$ y $$$B$ posee un par de claves a largo plazo: una clave privada para descifrar y crear una firma electrónica $$$K _ {\ text {public}}$ y clave pública para cifrado y verificación de firma $$$K _ {\ text {public}}$ .

$$

$$\ begin {array} {ll} A: K_ {A, \ text {private}}, K_ {A, \ text {public}}: \ forall M: & \ text {Verify} _A (M, S_A (M )) = verdadero, \\ & D_A (E_A (M)) = M, \\ B: K_ {B, \ text {private}}, K_ {B, \ text {public}}: \ forall M: & \ texto {Verificar} _B (M, S_B (M)) = verdadero, \\ & D_B (E_B (M)) = M. \\ \ end {array}$$

Donde $$$\ text {Verificar} _A (\ dots)$ es una función de verificar la firma electrónica en una clave pública $$$K_ {A, \ text {public}}$ y $$$D_A$ - función de descifrado utilizando la clave privada $$$K_ {A, \ text {privado}}$ .

El protocolo consta de cuatro pases, tres de los cuales incluyen la transmisión de mensajes ( [Cheryomushkin 2009] ).

1. Alice elige un número aleatorio $$$R_A: 2 \ leq R_A \ leq p-1$ .
   $$$Alice \ to \ left \ {A, m_A = g ^ {R_A} \ bmod p \ right \} \ para Bob$
2. Bob elige un número aleatorio $$$R_B: 2 \ leq R_B \ leq p-1$ .
   Bob calcula la clave de sesión $$$K = m_A ^ {R_B} \ bmod p$ .
   $$$Bob \ to \ left \ {B, A, m_B = g ^ {R_B} \ bmod p, E_K (S_B (m_A, m_B)) \ right \} \ para Alice$
3. Alice calcula una clave de sesión $$$K = m_B ^ {R_A} \ bmod p$ .
   Alice verifica la firma en el mensaje $$$E_K (S_B (m_A, m_B))$ .
   $$$Alice \ to \ left \ {A, B, E_K (S_A (m_A, m_B)) \ right \} \ a Bob$
4. Bob verifica la firma en el mensaje $$$E_K (S_A (m_A, m_B))$ .

El protocolo proporciona una garantía de nueva generación de claves (G10), pero no un secreto directo perfecto (G9).

Como lo demostró el ataque Lowe de 1996 ( [Lowe 1996] ), un protocolo no puede garantizar la autenticación de los sujetos (objetivo G1), claves (G7) y prueba de propiedad de la clave de sesión (G8). Aunque el atacante no puede obtener acceso a la nueva clave de sesión si el protocolo se usa solo para autenticar a los sujetos, Alice puede confundir al atacante con Bob.

1. Alice elige un número aleatorio $$$R_A: 2 \ leq R_A \ leq p-1$ .
   $$$Alice \ to \ left \ {A, m_A = g ^ {R_A} \ bmod p \ right \} \ to Mellory ~ (Bob)$
   
2. $$$Mellory \ to \ left \ {M, m_A \ right \} \ a Bob$
   
3. Bob elige un número aleatorio $$$R_B: 2 \ leq R_B \ leq p-1$ .
   Bob calcula la clave de sesión $$$K = m_A ^ {R_B} \ bmod p$ .
   $$$Bob \ to \ left \ {B, M, m_B, E_K (S_B (m_A, m_B)) \ right \} \ to Mellory$
   
4. $$$Mellory ~ (Bob) \ a \ left \ {B, A, E_K (S_B (m_A, m_B)) \ right \} \ a Alice$
   
5. Alice calcula una clave de sesión $$$K = m_B ^ {R_A} \ bmod p$ .
   Alice verifica la firma en el mensaje $$$E_K (S_B (m_A, m_B))$ .
   $$$Alice \ to \ left \ {A, B, E_K (S_A (m_A, m_B)) \ right \} \ to Mellory ~ (Bob)$
   

Después de completar con éxito el protocolo, Alice confía en que se está comunicando con Bob.

Como todos los demás "protocolos de criptosistemas", el protocolo de estación a estación se basa en alguna fuente externa de información sobre las claves públicas de los participantes, sin cuestionar la exactitud y confiabilidad de esta fuente. Lo cual, en el caso general, es incorrecto. Si la información sobre las claves de los participantes debe recibirse externamente en cada sesión del protocolo (por ejemplo, si hay muchos participantes y no hay posibilidad de recordar las claves de todos), entonces el canal para obtener claves públicas será el objetivo principal de un criptoanalista activo para los protocolos considerados. Cómo protegerse de esto usando primitivas de criptografía asimétrica se encuentra en la siguiente sección.

Literatura

• [Diffie, Hellman 1976] Diffie W., Hellman ME Nuevas direcciones en criptografía // Teoría de la información, transacciones IEEE en. - 1976. - nov. - t. 22, núm. 6. - p. 644-654. - ISSN 0018-9448. - DOI: 10.1109 / TIT.1976.1055638.
• [ElGamal, 1984] El Gamal T. Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos // Procedimientos de CRYPTO 84 sobre avances en criptología. - Santa Bárbara, California, EE. UU .: Springer-Verlag New York, Inc., 1985 .-- p. 10-18. - ISBN 0-387-15658-5. - URL: dl.acm.org/citation.cfm?id=19478.19480 .
• [ElGamal, 1985] El Gamal T. Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos // IEEE Transactions on Information Theory. - 1985. - julio. - t. 31, núm. 4. - p. 469-472. - DOI: 10.1109 / TIT.1985.1057074.
• [Matsumoto, Tsutomu, Imai 1986] Matsumoto T., Takashima Y., Imai H. Sobre la búsqueda de sistemas inteligentes de distribución de clave pública // Trans. Inst. Electrón Commun. Ing. Jpn. Secta E. T. 69. problema 2. - 02.1986. - con 99-106.
• [Diffie, Oorschot, Wiener 1992] Diffie W., PC Van Oorschot, Autenticación Wiener MJ
  e intercambios de claves autenticados // Diseños, códigos y criptografía. - 1992. - junio. - t. 2, núm. 2. - p. 107-125. - ISSN 1573-7586. - DOI: 10.1007 / BF00124891.
• [Lowe 1996] Lowe G. Algunos nuevos ataques a los protocolos de seguridad // Actas CSFW '96 del noveno taller de IEEE sobre Fundamentos de seguridad informática. —Washington, DC, EE. UU .: IEEE Computer Society, 1996. - pág. 162
• [Cheremushkin 2009] Cheremushkin A. V. Protocolos criptográficos: propiedades básicas y vulnerabilidades // Matemática discreta aplicada. - 2009. - nov. - problema. 2. - p. 115-150. - URL: cyberleninka.ru/article/n/kriptograficheskieprotokoly-osnovnye-svoystva-i-uyazvimosti.pdf .