Cifrado de Vernam

El cifrado de Vernam es un sistema de cifrado simétrico inventado en 1917 por Gilbert Vernam [1] .

Un cifrado es un tipo de sistema criptográfico de un solo uso. Utiliza la función booleana exclusiva-o . El cifrado de Vernam es un ejemplo de un sistema con fuerza criptográfica absoluta [2] . Al mismo tiempo, se considera uno de los criptosistemas más simples [3] .

Historia

Descrito por primera vez por Frank Miller en 1882. [4] [5] [6]

El cifrado lleva el nombre del telegrafista Gilbert Vernam , quien en 1917 inventó y en 1919 patentó un sistema para cifrar automáticamente los mensajes telegráficos.

Vernam no usó el concepto XOR en la patente, pero implementó exactamente esta operación en lógica de escalera. Cada carácter en el mensaje fue XOR bit a bit (o exclusivo) con la tecla de cinta de papel [7] . Joseph Mauborgne (entonces capitán del ejército de los EE. UU. y luego jefe del cuerpo de señales) modificó este sistema para que la secuencia de caracteres en la cinta clave fuera completamente aleatoria, ya que en este caso el criptoanálisis sería más difícil.

Vernam creó un dispositivo que realiza estas operaciones automáticamente, sin la participación de un criptógrafo. Así, se inició el llamado “cifrado lineal”, cuando los procesos de cifrado y transmisión de un mensaje ocurren simultáneamente. Hasta entonces, el cifrado era preliminar, por lo que el cifrado de línea aumentó significativamente la velocidad de la comunicación.

Sin embargo, al no ser un criptógrafo, Vernam notó correctamente una propiedad importante de su cifrado: cada cinta debe usarse solo una vez y luego destruirse. Esto es difícil de aplicar en la práctica; por lo tanto, el aparato se convirtió en varias cintas en bucle con períodos coprimos [8] .

Descripción

El criptosistema se propuso para cifrar mensajes telegráficos, que eran textos binarios en los que el texto sin formato se representa en el código Baudot (en forma de "combinaciones de pulsos" de cinco dígitos). En este código, por ejemplo, la letra "A" se veía como (1 1 0 0 0). En la cinta de papel, el número "1" correspondía al agujero y el número "0" a su ausencia. Se suponía que la clave secreta era un conjunto caótico de letras del mismo alfabeto [8] .

Para obtener el texto cifrado, el texto plano se combina con una operación XOR con la clave secreta . Así, por ejemplo, al aplicar la clave (1 1 1 0 1) a la letra "A" (1 1 0 0 0), obtenemos un mensaje encriptado (0 0 1 0 1): Sabiendo que para el mensaje recibido tiene la clave (1 1 1 0 1), es fácil obtener el mensaje original mediante la misma operación: para una fuerza criptográfica absoluta, la clave debe tener tres propiedades críticas [2] : $(11000)\oplus (11101)=(00101)$ ${\ estilo de visualización (00101) \ o más (11101) = (11000)}$

Tener una distribución uniforme aleatoria discreta : , donde k es la clave y N es el número de caracteres binarios en la clave; $P_{k}(k)=1/2^{N}$
Ser del mismo tamaño que el texto sin formato especificado;
Aplicar solo una vez.

También es conocido el denominado módulo m de cifrado de Vernam , en el que los signos del texto plano, texto cifrado y clave toman valores del anillo de residuos Z m . El cifrado es una generalización del cifrado de Vernam original, donde m = 2 [2] .

Por ejemplo, módulo de cifrado de Vernam m = 26 (A=0,B=1,…, Z=25):

Clave: EVTIQWXQVVOPMCXREPYZ Texto sin formato: ALLSWELLTHATENDSWELL (Bien está lo que bien acaba) Texto cifrado: EGEAMAIBOCOIQPAJATJK

Al cifrar, la transformación se realiza de acuerdo con la tabla de Vigenère (la adición de índices de caracteres módulo la longitud del alfabeto da esta tabla).

La letra clave es la columna, la letra del texto sin formato es la fila y el texto cifrado es la letra en la intersección.

Sin el conocimiento de la clave, dicho mensaje no se puede analizar. Incluso si fuera posible probar todas las claves, el resultado serían todos los mensajes posibles de una longitud determinada, más una cantidad colosal de desciframientos sin sentido que parecen un revoltijo de letras. Pero incluso entre desciframientos significativos, no habría forma de elegir el deseado. Cuando una secuencia aleatoria (la clave) se combina con una no aleatoria (el texto sin formato), el resultado (el texto cifrado ) es completamente aleatorio y, por lo tanto, carece de las características estadísticas que podrían usarse para analizar el cifrado. [9] .

Fuerza criptográfica

En 1945, Claude Shannon escribió "La teoría matemática de la criptografía" (desclasificada solo después de la Segunda Guerra Mundial en 1949 como " La teoría de la comunicación en sistemas secretos "), en la que demostró la fuerza criptográfica absoluta del cifrado de Vernam. Es decir, la interceptación del texto cifrado sin clave no proporciona ninguna información sobre el mensaje. Desde el punto de vista de la criptografía, es imposible pensar en un sistema que sea más seguro que el cifrado de Vernam [2] . Los requisitos para la implementación de dicho esquema no son triviales, ya que es necesario garantizar la imposición de una gamma única igual a la longitud del mensaje, con su posterior destrucción garantizada. En este sentido, el uso comercial del cifrado Vernam no es tan común como los esquemas de clave pública, y se utiliza principalmente para la transmisión de mensajes de particular importancia por parte de las agencias gubernamentales [8] .

Presentamos una prueba de seguridad criptográfica absoluta. Sea el mensaje representado por una secuencia binaria de longitud . La distribución de probabilidad del mensaje puede ser cualquier cosa. La clave también está representada por una secuencia binaria de la misma longitud, pero con una distribución uniforme para todas las claves. $N:m=m_{1},m_{2},\ldots,m_{n}$ $P_{m}(m)$ $k=k_{1},k_{2},\ldots,k_{n}$ $P_{k}(k)=1/2^{N}$

De acuerdo con el esquema de cifrado, produciremos un texto cifrado componente por componente sumando secuencias de módulo 2 del texto sin formato y la clave:

C=M\oplus K=(m_{1}\oplus k_{1},m_{2}\oplus k_{2},\ldots,m_{N}\oplus k_{N})

El usuario legal conoce la clave y realiza el descifrado:

M=C\oplus K=(c_{1}\oplus k_{1},c_{2}\oplus k_{2},\ldots,c_{N}\oplus k_{N})

Encontremos la distribución de probabilidad de N-bloques de textos cifrados usando la fórmula:

P(c=a)=P(m\oplus k=a)=\sum _{m}{P(m)}P(m\oplus k=a|m)=\sum _{m} {P(m)1/2^{N}}=1/2^{N}

El resultado confirma el hecho bien conocido de que la suma de dos variables aleatorias, una de las cuales tiene una distribución uniforme discreta en un grupo finito , es una variable aleatoria distribuida uniformemente. Así, en nuestro caso, la distribución de los textos cifrados es uniforme.

Escribimos la distribución conjunta de textos planos y cifrados:

P(m=a,c=b)=P(m=a)P(c=b|m=a)

Encontremos la distribución condicional

P(c=b|m=a)=P(m\oplus k=b|m=a)=P(k=b\oplus a|m=a)=P(k=b\oplus a)=1 /2^{N},

ya que la clave y el texto plano son variables aleatorias independientes. Total:

P(c=b|m=a)=1/2^{N}

Sustituyendo el lado derecho de esta fórmula en la fórmula de distribución conjunta da

P(m=a,c=b)=P(m=a)1/2^{N}

Lo que prueba la independencia de los textos cifrados y los textos sin formato en este sistema. Esto significa fortaleza criptográfica absoluta [10] .

Alcance

Actualmente, el cifrado de Vernam rara vez se usa. En gran medida, esto se debe al importante tamaño de la clave, cuya longitud debe coincidir con la longitud del mensaje. Es decir, el uso de dichos cifrados requiere enormes costos de producción, almacenamiento y destrucción de materiales clave. Sin embargo, los cifrados completamente fuertes como Vernam todavía encontraron un uso práctico para proteger las líneas de comunicación críticas con una cantidad de información relativamente pequeña. Por ejemplo, los británicos y los estadounidenses utilizaron cifrados de tipo Vernam durante la Segunda Guerra Mundial. El cifrado Vernam módulo 2 se utilizó en una línea directa del gobierno entre Washington y Moscú, donde los materiales clave eran cintas de papel en las que se perforaban los caracteres de la secuencia clave [2] .

En la práctica, es posible transferir físicamente el portador de información con una clave larga y verdaderamente aleatoria una vez, y luego reenviar los mensajes según sea necesario. La idea de las libretas de cifrado se basa en esto : el empleado de cifrado recibe un cuaderno por correo diplomático o en persona, cada página del cual contiene claves. La parte receptora tiene el mismo bloc de notas. Las páginas usadas se destruyen [11] .

Desventajas

Se necesita una secuencia verdaderamente aleatoria ( clave ) para que funcione el cifrado de Vernam . Por definición, una secuencia obtenida utilizando cualquier algoritmo no es realmente aleatoria, sino pseudoaleatoria. Es decir, debe obtener una secuencia aleatoria no algorítmicamente, sino, por ejemplo, utilizando la descomposición radiactiva creada por un generador electrónico de ruido blanco u otros eventos bastante aleatorios. Para que la distribución sea lo más uniforme posible , se suele pasar una secuencia aleatoria a través de una función hash como MD5 [12] .

La desventaja de usar el cifrado Vernam es la falta de confirmación de la autenticidad e integridad del mensaje. El destinatario no puede verificar la ausencia de daño o la autenticidad del remitente. Si un tercero de alguna manera reconoce el mensaje, recuperará fácilmente la clave y podrá reemplazar el mensaje por otro de la misma longitud. La solución al problema es usar una función hash. Una función hash se calcula a partir del texto sin formato y su valor se cifra junto con el mensaje. Cualquier cambio en el mensaje cambiará el valor hash. Por lo tanto, incluso si un atacante se apodera de un bloque de cifrado sin conocer el algoritmo para calcular la función hash, no podrá utilizarlo para transmitir información [11] .

Siempre es necesario tener a mano una cantidad suficiente de claves, que pueden ser necesarias en el futuro para cifrar grandes cantidades de texto sin formato. El volumen real del texto suele ser difícil de estimar de antemano, especialmente en las esferas diplomática y militar, donde la situación puede cambiar de forma rápida e impredecible. Esto puede conducir a la falta de claves, lo que puede hacer que el criptógrafo reutilice las claves o rompa por completo la comunicación cifrada.

El problema es la transmisión segura de la secuencia y mantenerla en secreto. Si hay un canal de transmisión de mensajes que está protegido de manera confiable contra la intercepción, no se necesitan cifrados en absoluto: los mensajes secretos se pueden transmitir a través de este canal. Sin embargo, si la clave del sistema Vernam se transmite utilizando otro cifrado (por ejemplo, DES ), el cifrado resultante estará protegido exactamente tanto como DES. Al mismo tiempo, dado que la longitud de la clave es la misma que la del mensaje, no es más fácil transmitirla que el mensaje. Un bloque de cifrado en un medio físico puede ser robado o copiado [11] .

El cifrado de Vernam es sensible a cualquier incumplimiento del procedimiento de cifrado. Hubo casos en que la misma página del bloc de notas se usó dos veces por varias razones. Por ejemplo, entre todo el volumen de correspondencia encriptada soviética interceptada por la inteligencia estadounidense en los años 40 del siglo pasado, se encontraron mensajes que estaban cerrados con una gamma de doble uso. Este período no duró mucho, porque ya después de los primeros éxitos de los criptoanalistas estadounidenses a fines de la década de 1940, los servicios secretos de la URSS se enteraron de serios problemas con la confiabilidad de su correspondencia cifrada. Dichos mensajes fueron descifrados durante los siguientes 40 años como parte del proyecto secreto Venona , cuyos documentos fueron posteriormente desclasificados y publicados en el sitio web de la NSA [13] .

Notas

↑ Algoritmos simétricos .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Mao, 2005 .
↑ Molinero, Frank. Código telegráfico para asegurar la privacidad y el secreto en la transmisión de telegramas. — CM Cornwell, 1882.
↑ Bellovin, Steven M. (2011). Frank Miller: inventor del bloc de notas de un solo uso . criptología _ 35 (3): 203-222. DOI : 10.1080/01611194.2011.583711 . ISSN 0161-1194 . S2CID 35541360 .
↑ John Markoff . El libro de códigos muestra un formulario de cifrado que se remonta a Telegraphs (25 de julio de 2011). Consultado el 26 de julio de 2011.
↑ Patente de EE. UU. 1310719A
↑ 1 2 3 Babash, et al., 2003 .
↑ Criptografía (enlace inaccesible) . Fecha de acceso: 8 de febrero de 2014. Archivado desde el original el 2 de noviembre de 2013. (indefinido)
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 41-43.
↑ 1 2 3 Bloc de notas de una sola vez .
↑ Preguntas frecuentes .
↑ Kiwi, 2005 .

Literatura

Fomichev V. M. Matemáticas discretas y criptología : curso de conferencias / ed. N. D. Podufalov - M. : Dialog-MEPhI , 2013. - S. 239-246. — 397 pág. — ISBN 978-5-86404-185-7
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Mao V. Criptografía moderna : Teoría y práctica / trad. D. A. Klyushina - M. : Williams , 2005. - S. 255. - 768 p. — ISBN 978-5-8459-0847-6
Roberto L. Benson. The Venona Story (inglés) // Centro de Historia Criptológica Agencia de Seguridad Nacional. Archivado desde el original el 27 de mayo de 2010.
Babash A. V. , Goliev Yu. I. , Larin D. A. , Shankin G. P. Ideas criptográficas del siglo XIX // Seguridad de la información. Confidente - San Petersburgo. : 2004. - edición. 3.

Enlaces

Algoritmos simétricos (ruso) .
Dirk Rijmenants. Bloc de notas de un solo uso (inglés) .
Marcus J. Ranum. Preguntas frecuentes de One-Time-Pad (Cifrado de Vernam) .
Byrd Kiwi. Errores de precio . - 2005. Archivado el 24 de diciembre de 2013.