🌔 👴🏻 💦 Tres protocolos de paso ⏩ 👩🏼 🛷

Este texto será uno de los capítulos reescritos del manual sobre protección de la información del Departamento de Ingeniería de Radio y Sistemas de Control, así como, a partir de este código de capacitación, el Departamento de Protección de Información del Instituto de Física y Tecnología de Moscú. El tutorial completo está disponible en github (ver también versiones preliminares ). En Habrir planeo diseñar nuevas piezas "grandes", en primer lugar, para recopilar comentarios y observaciones útiles, y en segundo lugar, para dar a la comunidad más material general sobre temas útiles e interesantes.

Temas anteriores:

Si hay un canal de comunicación entre Alice y Bob al que un atacante no puede modificar (es decir, cuando solo es aplicable el modelo de criptoanalista pasivo), incluso sin un intercambio preliminar de claves secretas u otra información, puede usar las ideas utilizadas previamente en la criptografía de clave pública. Después de describir el RSA en 1978, en 1980 Adi Shamir propuso el uso de criptosistemas basados en operaciones conmutativas para transmitir información sin intercambiar primero claves secretas. Si suponemos que la información transmitida es una clave de sesión secreta generada por una de las partes, en general obtenemos el siguiente protocolo de tres pasos.

Preliminar:

Alice y Bob están conectados por un canal de comunicación no seguro, abierto para escuchar (pero no para modificación) por un atacante.
Cada lado tiene un par de claves públicas y privadas. $K_A$ , $k_A$ , $K_B$ , $k_B$ en consecuencia
Las partes han elegido y utilizado la función de cifrado conmutativo:
$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$
$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$

El protocolo consta de tres pases con la transmisión de mensajes (de ahí el nombre) y uno final, en el que Bob recibe la clave.

Alice selecciona una nueva clave de sesión $K$

$Alice \ to \ left \ {E_A \ left (K \ right) \ right \} \ a Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) \ right \} \ para Alice$
Alice, usando la conmutatividad de la función de cifrado,
$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = D_{A} l e f t (E_{A} l e f t (E_{B} l e f t (K r i g h t) r i g h t) r i g h t) = E_{B} l e f t (K d e r e c h a) .$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = D_A \ left (E_A \ left (E_B \ left (K \ right) \ right) \ right) = E_B \ left (K \ derecha).$
$Alice \ to \ left \ {E_B \ left (K \ right) \ right \} \ a Bob$
Bob descifra $D_B \ left (E_B \ left (K \ right) \ right) = K$

Como resultado, las partes reciben una clave secreta compartida.

K

$K$ .

Un inconveniente común de todos estos protocolos es la falta de autenticación de las partes. Por supuesto, en el caso de un criptoanalista pasivo, esto no es obligatorio, pero en la vida real aún debe considerar todos los modelos posibles (incluido un criptoanalista activo) y utilizar protocolos que impliquen la autenticación mutua de las partes. Además, a diferencia del esquema Diffie - Hellman, el iniciador de la sesión selecciona la nueva clave, lo que le permite al iniciador, no con buenas intenciones, forzar al segundo participante a utilizar la clave de sesión desactualizada.

Hablando en términos de propiedades de seguridad , todos los representantes de esta clase de protocolos declaran solo la autenticación de clave (G7). A diferencia del esquema Diffie - Hellman, los protocolos de tres pasos no requieren la selección de nuevas claves "maestras" para cada sesión de protocolo, por lo que no se puede garantizar el secreto directo perfecto (G9) ni la formación de nuevas claves (G10).

Opción trivial

Pongamos un ejemplo de un protocolo basado en la función XOR (módulo de adición bit a bit 2). Aunque esta función se puede utilizar como base para construir sistemas de fuerza criptográfica perfecta, para un protocolo de tres pasos es una mala elección.

Antes de comenzar el protocolo, ambas partes tienen sus claves secretas.

K_{A}

$K_A$ y

K_{B}

$K_B$ representa secuencias binarias aleatorias con una distribución uniforme de caracteres. La función de cifrado se define como

E_{i} (X) = X o p l u s K_{i}

$E_i (X) = X \ oplus K_i$ donde

X

$X$ este mensaje también

K_{i}

$K_i$ - clave secreta. Obviamente:

f o r a l l i, j, X : E_{i} l e f t (E_{j} l e f t (X r i g h t) r i g h t) = X o p l u s K_{j} o p l u s K_{i} = X o p l u s K_{i} o p l u s K_{j} = E_{j} l e f t (E_{i} l e f t (X r i g h t) r i g h t)

$\ forall i, j, X: E_i \ left (E_j \ left (X \ right) \ right) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ left (E_i \ left (X \ right) \ right)$

Alice selecciona una nueva clave de sesión $K$

$Alice \ to \ left \ {E_A \ left (K \ right) = K \ oplus K_A \ right \} \ para Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K \ oplus K_A \ oplus K_B \ right \} \ to Alice$
Alice, usando la conmutatividad de la función de cifrado,
$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = K o p l u s K_{A} o p l u s K_{B} o p l u s K_{A} = K o p l u s K_{B} = E_{B} l e f t (K r i g h t) . $$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ left (K \ right). $$
$Alice \ to \ left \ {E_B \ left (K \ right) = K \ oplus K_B \ right \} \ para Bob$
Bob descifra $D_B \ left (E_B \ left (K \ right) \ right) = K \ oplus K_B \ oplus K_B = K$

Al final de la sesión de protocolo, Alice y Bob conocen la clave de sesión común.

K

$K$ .

La elección propuesta de la función de cifrado conmutativo de secreto perfecto no tiene éxito, ya que hay situaciones en las que un criptoanalista puede determinar la clave

K

$K$ . Supongamos que un criptoanalista intercepta los tres mensajes:

K o p l u s K_{A}, K o p l u s K_{A} o p l u s K_{B}, K o p l u s K_{B} . $

$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B. $$

La adición del módulo 2 de los tres mensajes da la clave

K

$K$ . Por lo tanto, dicho sistema de cifrado no se utiliza.

Ahora presentamos el protocolo para la transferencia confiable de la clave secreta, basado en la función de cifrado exponencial (conmutativa). La estabilidad de este protocolo está asociada con la dificultad de la tarea de calcular el logaritmo discreto: para valores conocidos

y, g, p

$y, g, p$ encontrar

x

$x$ de la ecuación

y = g^{x} b m o d p

$y = g ^ x \ bmod p$ .

Protocolo sin llave de Shamir

Las partes acuerdan tentativamente una prima importante

p s i m 2^{1024}

$p \ sim 2 ^ {1024}$ . Cada una de las partes elige una clave secreta.

a

$a$ y

b

$b$ . Estas teclas son más pequeñas y mutuamente simples.

p - 1

$p-1$ . Además, las partes se prepararon de acuerdo con un número especial

a^{'}

$a '$ y

b^{'}

$b '$ que les permiten descifrar un mensaje cifrado con su clave:

b e g i n a r r a y l a^{'} = a - 1 m o d (p - 1), a t i m e s a^{'} = 1 m o d (p - 1), f o r a l l X : (X^{a})^{a^{'}} = X . e n d a r r a y

$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ times a' = 1 \ mod (p-1), \\ \ forall X: (X ^ a) ^ {a '} = X. \\ \ end {array}$

La última expresión es verdadera por el corolario del pequeño teorema \ index {teorema de Fermat! La granja es pequeña}. Las operaciones de cifrado y descifrado se definen de la siguiente manera:

\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}

$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$

Alice selecciona una nueva clave de sesión $K <p$

$Alice \ to \ left \ {E_A \ left (K \ right) = K ^ a \ bmod p \ right \} \ para Bob$
$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K ^ {ab} \ bmod p \ right \} \ para Alice$
Alice, usando la conmutatividad de la función de cifrado,
$D_{A} l e f t (E_{B} l e f t (E_{A} l e f t (K r i g h t) r i g h t) r i g h t) = K^{a b a^{'}} = K^{b} = E_{B} l e f t (K r i g h t) m o d p . $$
$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = K ^ {aba '} = K ^ b = E_B \ left (K \ right) \ mod p. $$

$Alice \ to \ left \ {E_B \ left (K \ right) = K ^ b \ right \} \ para Bob$
Bob descifra $D_B \ left (E_B \ left (K \ right) \ right) = K ^ {bb '} \ bmod p = K$

Al final de la sesión de protocolo, Alice y Bob conocen la clave de sesión común.

K

$K$ .

Supongamos que un criptoanalista intercepta tres mensajes:

b e g i n a r r a y l y_{1} = K^{a} b m o d p, y_{2} = K^{a b} b m o d p, y_{3} = K^{b} b m o d p . e n d a r r a y

$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$

Para encontrar la llave

K

$K$ , un criptoanalista necesita resolver un sistema de estas tres ecuaciones, que tiene una complejidad computacional muy grande, inaceptable desde un punto de vista práctico, si los tres números

a, b, a b

$a, b, ab$ bastante grande Asume que

a

$a$ (o

b

$b$ ) no es suficiente. Luego, computando grados sucesivos

y_{3}

$y_3$ (o

y_{1}

$y_1$ ), se puede encontrar

a

$a$ (o

b

$b$ ), comparando el resultado con

y_{2}

$y_2$ . Sabiendo

a

$a$ fácil de encontrar

a^{- 1} b m o d (p - 1)

$a ^ {- 1} \ bmod (p-1)$ y

K = (y_{1})^{a^{- 1}} b m o d p

$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Criptosistema Massey-Omura

En 1982, James Massey y Jim Omura reclamaron una patente (James Massey, Jim K. Omura), mejorando (en su opinión) el protocolo sin llave de Shamir. Como una operación de cifrado en lugar de exponenciación en un grupo multiplicativo

m a t h b b Z_{p}^{*}

$\ mathbb {Z} _p ^ *$ sugirieron usar exponenciación en el campo de Galois

m a t h b b G F 2^{n}

$\ mathbb {GF} {2 ^ n}$ . Clave secreta de cada fiesta (para Alice -

a

$a$ ) debe cumplir las condiciones:

b e g i n a r r a y l a i n m a t h b b G F 2^{n}, g f d l e f t (a, x^{n - 1} + x^{n - 2} + . . . + x + 1 r i g h t) = 1. e n d a r r a y

$\ begin {array} {l} a \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ left (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ right) = 1. \\ \ end {array}$

De lo contrario, el protocolo se ve similar.

Epílogo

El autor estará agradecido por los hechos y otros comentarios sobre el texto.

Tres protocolos de paso

Opción trivial

Protocolo sin llave de Shamir

Criptosistema Massey-Omura

Epílogo

More articles: