Sustitución homofónica

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de marzo de 2022; las comprobaciones requieren 2 ediciones .

El cifrado de sustitución homofónico es un  cifrado de sustitución en el que cada carácter del texto sin formato se reemplaza por uno de varios caracteres del cifrado del alfabeto, y el número de caracteres de reemplazo para una letra es proporcional a la frecuencia de esta letra. Esto le permite ocultar la frecuencia real de aparición de una letra determinada en el texto cifrado [1] .

Historia

El cifrado por el método de sustitución homofónica se conoce desde el siglo XV [2] .

Simeone de Crema en 1401 utilizó por primera vez tablas de homófonos para la frecuencia uniforme de las vocales con la ayuda de la sustitución multivaluada [3] .

Leon Battista Alberti , en su Tratado sobre cifrados , publicado en 1466, describió un cifrado por sustitución en el que se asignan varios elementos a una letra [3] .

Los cifrados de sustitución monoalfabéticos tradicionales todavía eran relevantes en el siglo XVII para tareas triviales, como cifrar la correspondencia personal para ocultar información a los sirvientes o proteger el diario de una esposa o esposo. La sustitución monoalfabética produce una protección simple y rápida de la información de personas ignorantes del criptoanálisis . Sin embargo, para propósitos más serios, dicho cifrado ya no era seguro, por lo que se hizo necesario buscar un cifrado que fuera más difícil de descifrar que un cifrado de sustitución monoalfabético , pero que fuera más fácil de usar que un cifrado de sustitución polialfabético . Se presentaron varias variantes de tales cifrados, la solución más efectiva a este problema fue un cifrado de sustitución homofónica o sustitución homofónica [1] .

Cifrado

Sea  un carácter del alfabeto que se utiliza en el texto plano. Para cada uno , componemos el conjunto de símbolos , de modo que para diferentes símbolos y los conjuntos y no se intersecan. Normalmente, los elementos de un conjunto son números. En el cifrado homofónico, el número de sustituciones de cada carácter se toma en proporción a la probabilidad de que ese carácter aparezca en el texto sin formato. En el cifrado, se elige al azar (generador de números aleatorios) o de una manera específica (por ejemplo, en orden) un reemplazo para un carácter de texto sin formato. Para memorizar las letras que se encuentran con mayor frecuencia en los textos, utilizan combinaciones de las letras "senovaliter" y "tetrishonda" para ruso e inglés, respectivamente. Estas combinaciones son similares a las palabras y, por lo tanto, son fáciles de recordar [4] .

La probabilidad de aparición de letras del alfabeto ruso.
Carta Probabilidad
PERO 0.069
B 0.013
A 0.038
GRAMO 0.014
D 0.024
SU 0.071
Y 0.007
Z 0.016
Carta Probabilidad
Y 0.064
Y 0.010
A 0.029
L 0.039
METRO 0.027
H 0.057
O 0.094
PAGS 0.026
Carta Probabilidad
R 0.042
DE 0.046
T 0.054
A 0.023
F 0.003
X 0.008
C 0.005
H 0.012
Carta Probabilidad
W 0.006
SCH 0.004
Kommersant 0.001
S 0.015
b 0.013
mi 0.002
YU 0.005
yo 0.017

(*) (La tabla muestra los resultados de un análisis de frecuencia de textos literarios y científicos con un volumen total de más de 1 millón de caracteres. Bajo las mismas condiciones, la probabilidad de una "brecha" es 0.146.)

Dado que la probabilidad de encontrar la letra más rara es aproximadamente una milésima, el cifrado mediante el método de sustitución de texto plano homofónico se puede llevar a cabo mediante una tabla de sustitución de cifrado, donde cada sustitución de cifrado consta de 3 dígitos y su número total es 1000. En este caso, para el elemento más raro, exactamente un carácter [ 4] .

A continuación se muestra un ejemplo de una tabla de este tipo.

No. PERO B A … mi … O PAGS R … mi YU yo
una 012 128 325 … 037 … 064 058 265 … 501 064 106
2 659 556 026 … 700 … 149 073 333 … 248 749 098
… … … … … … … … … … … … …
17 111 061 … 144 … 903 656 476 … 453
… … … … … … … … … …
38 366 804 … … … 123 865 …
… … … … … … … …
69 095 … 010
… … …
71 541 268
… …
94 479

Algunos campos de la tabla están vacíos, ya que el número de reemplazos para cada carácter del alfabeto fuente es diferente. Por ejemplo, este fragmento se puede utilizar para cifrar la palabra "VERA". Cada letra del mensaje original, en este caso una palabra, debe ser reemplazada por uno de los reemplazos de cifrado en la columna de esa letra. Si las letras se reemplazan por tales sustituciones de cifrado: "B" - , "E" - , "P" - , "A" - , entonces la palabra cifrada tiene la forma de una secuencia numérica " " [4] .

Criptoanálisis

El cifrado por sustitución homofónica es la defensa más sencilla contra los criptoataques de análisis de frecuencia, ya que una de sus sustituciones se selecciona aleatoriamente al cifrar una letra del texto de origen. Con este método de encriptación, los elementos del texto cifrado aparecen con igual probabilidad, por lo que el cálculo habitual de la frecuencia de las letras es inútil para un criptoanalista . Sin embargo, el criptoanálisis de frecuencia basado en el conteo de pares, tripletes de letras o palabras tendrá más éxito. Por ejemplo, el artículo the es el más común en texto sin formato en inglés. Además, después de la letra q, solo hay una letra: u. Por lo tanto, al notar algunas combinaciones de caracteres, puede descifrar parte del texto y luego, de acuerdo con la información recibida, restaurar el resto [5] [4] .

Actualmente, las computadoras modernas descifran textos cifrados con sustitución homofónica en cuestión de segundos [6] .

Características del cifrado

La peculiaridad de este método es que los reemplazos de cifrado no se repiten. Esto significa que si la letra "Ф" tiene 3 sustituciones de cifrado, por ejemplo, y , entonces las sustituciones de cifrado y denotan solo la letra "Ф" [7] .

Un cifrado homofónico puede parecer un cifrado polialfabético ( polialfabético ), ya que cada letra del alfabeto se puede cifrar de muchas maneras, pero, de hecho, un cifrado de sustitución homofónico es un tipo de cifrado monoalfabético ( monoalfabético ). La razón principal por la que un cifrado homofónico es monoalfabético es que el alfabeto cifrado no cambia a lo largo del proceso de cifrado [7] .

Características del cifrado

El cifrado de sustitución homofónico se caracteriza por dos parámetros: la longitud del texto cifrado y la complejidad , donde  es el número de caracteres diferentes del alfabeto cifrado utilizado en este texto cifrado. Obviamente la complejidad es limitada . Cuando la complejidad de un cifrado es lo suficientemente cercana a 0, el cifrado es un cifrado de sustitución simple. En un cierto valor , la distribución de los caracteres del alfabeto cifrado se vuelve uniforme (alrededor de 0,3 para un texto cifrado de 200 caracteres), sin embargo, si continúa aumentando la complejidad, puede alcanzar el valor límite en el que ya no es posible descifrar sin ambigüedades el texto. Las sustituciones homofónicas de órdenes superiores tienen el mismo texto cifrado para diferentes textos sin formato, por lo tanto, en los casos en que la longitud del texto cifrado es menor que la distancia de unicidad , es imposible entender qué versión del texto sin formato será la correcta [8] .

Sustitución homofónica de segundo orden

Una sustitución homofónica de segundo orden es una sustitución homofónica tal que el texto cifrado se puede descifrar de dos maneras. Por ejemplo, " " con la ayuda de una clave (clave 1) se puede descifrar como "MAMA SOAPED THE FRAME", y con la ayuda de la segunda clave (clave 2) como "AMUR WASHED URAL". Ambos textos sin formato no tienen mucho significado, pero ilustran bien que se pueden ocultar mensajes completamente diferentes detrás del mismo texto cifrado [9] .

Clave 1
METRO 13, 2
PERO 9, 32, 10
S 19
L 27
R ocho
A 3
Clave 2
METRO 9, 19
PERO 13
S 27
L diez
R 32
A 8.2

Generación de claves y cifrado

Para entender cómo se puede obtener tal cifrado, escribamos nuestros textos sin formato de igual longitud uno debajo del otro.

METRO PERO METRO PERO METRO S L PERO R PERO METRO A
PERO METRO A R A METRO S L A R PERO L

Ahora tenga en cuenta que si leemos el registro resultante no en filas, sino en columnas, obtendremos 9 digramas diferentes (pares de letras): "MA", "AM", "MU", "AP", "YM", " LY", "AL", "RU", "UL". Todos los digramas excepto "MA", "MU" y "AR" se repiten una vez. A continuación, llene aleatoriamente la matriz (6 es el número de letras en los alfabetos de texto sin formato; si se usa todo el alfabeto en el texto, tendremos una matriz o para los alfabetos ruso e inglés, respectivamente) con números, por ejemplo, del 1 al 36 [10] .

PERO L METRO R A S
PERO 21 diez 9 32 26 34
L dieciséis 6 7 catorce treinta 27
METRO 13 Dieciocho 23 28 2 5
R cuatro quince 36 22 ocho 35
A 25 3 17 29 veinte 33
S una 31 19 24 12 once

Cada fila y cada columna se asigna a uno de los caracteres alfabéticos del primer y segundo texto sin formato, respectivamente. Ahora, cada digrama corresponde a un número determinado (en la intersección de las filas y columnas correspondientes), por lo tanto, reemplazando el digrama con el número correspondiente, podemos encriptar los textos. Una matriz con números correspondientes a digramas juega el papel de una clave en este caso. Para mantener en secreto la matriz completa, se divide en dos matrices: una se obtiene ordenando los elementos de las filas, la otra ordenando las columnas y transponiendo . A la salida, tendremos dos matrices, en cada una de las cuales los elementos de las filas están ordenados de forma ascendente (descendente), y una matriz se puede usar para obtener solo un texto sin formato. Por ejemplo, se toman textos con los mismos alfabetos, ya que se supone que en el caso general se utilizará todo el alfabeto para crear un cifrado y que el cifrado debe cubrir todos los digramas posibles [11] .

Clave para el primer destinatario
PERO 9 diez 21 26 32 34
L 6 7 catorce dieciséis 27 treinta
METRO 2 5 13 Dieciocho 23 28
R cuatro ocho quince 22 22 36
A 3 17 veinte 26 29 33
S una once 12 19 24 31
Clave para el segundo destinatario
PERO una cuatro 13 dieciséis 22 25
L 3 6 diez quince Dieciocho 31
METRO 7 9 17 19 23 36
R catorce 22 24 28 29 32
A 2 ocho 12 veinte 26 treinta
S 5 once 27 33 34 35

Sustitución homofónica con mínima redundancia

Para mejorar el método, se puede lograr la redundancia mínima del alfabeto cifrado. Algoritmo

  1. Usaremos cada número una sola vez. Si el digrama se repite, tome un nuevo número para él, que será mayor que el máximo disponible en el alfabeto. En nuestro caso, obtenemos el texto cifrado " "
  2. Una vez que se completa el cifrado, elimine todos los elementos no utilizados de la matriz
  3. Se puede obtener una página de libro de cifrado con redundancia mínima reemplazando todos los números con diferentes números aleatorios. Obviamente, en este caso, podemos obtener el texto cifrado " ". La tabla de claves del digrama y las claves para cada uno de los destinatarios de dicho conjunto de mensajes se reducirán al mínimo posible [11] .
PERO L METRO R A S
PERO ocho 2 4, 10
L 7
METRO 1, 11 3, 5
R 9
A 12
S 6
Clave 1
PERO 2, 4, 8, 10
L 7
METRO 1, 3, 5, 11
R 9
A 12
S 6
Clave 2
PERO 1, 11
L 8, 12
METRO 2, 6
R 4, 10
A 3, 5, 9
S 7

Si lee las letras en el orden indicado por los números correspondientes a cada letra, obtiene el texto sin formato. Debido a esto, el uso de dicho cifrado se vuelve imposible, ya que para obtener el texto plano, será suficiente que un atacante tenga una clave, sin siquiera tener un texto privado. Esto hace que no tenga sentido reducir la redundancia de texto. Por otro lado, la forma matricial utilizada anteriormente de la sustitución homofónica de segundo orden tiene una solidez criptográfica bastante buena si se utiliza el alfabeto completo. Dos textos darán ( ) posibles digramas que no se repetirán mucho a menos que el texto sea demasiado largo. Como resultado, la redundancia de los mensajes cifrados será baja, mientras que el mensaje utilizará una gran cantidad de caracteres diferentes, lo que constituye un serio obstáculo para el criptoanálisis [12] .

Ejemplos notables

Los criptogramas del famoso asesino en serie de Zodiac están encriptados con un cifrado de sustitución homofónica. Uno de los dos criptogramas aún no ha sido descifrado [13] .

Se considera que los criptogramas de Bale están encriptados con un cifrado por sustitución homofónica de primer orden, y la probabilidad de descifrar el segundo criptograma (el único de los tres que podría descifrarse) de manera que se obtenga otro texto significativo es la más pequeña [ 14] [15] .

Sustitución homofónica en la naturaleza

El código genético es una sustitución homofónica, en la que los aminoácidos desempeñan el papel de símbolos de texto plano y los codones  son triples de nucleótidos  : símbolos de texto cifrado [16] .

Notas

  1. ↑ 1 2 Singh, 2007 , pág. 70.
  2. ↑ Kahn, 2000 , pág. 7.
  3. ↑ 1 2 Anisimov .
  4. ↑ 1 2 3 4 Singh, 2007 , pág. 71-72.
  5. ↑ Dolgov, 2008 , pág. 33.
  6. ↑ Schneier, 2002 , pág. 35.
  7. ↑ 1 2 Singh, 2007 , pág. 72.
  8. ↑ John C. King y Dennis R. Bahler. Una solución algorítmica de cifrados homofónicos secuenciales  (inglés)  = Una solución algorítmica de cifrados homofónicos secuenciales // Cryptologia: revista científica. — Taylor & Francis, 1993. — Vol. 17. - Pág. 149. - ISSN 0161-1194 . -doi : 10.1080/ 0161-119391867827 . Archivado desde el original el 12 de diciembre de 2020.
  9. ↑ Martillo, 1988 , pág. 12-13.
  10. ↑ Martillo, 1988 , pág. 13
  11. ↑ 1 2 Hammer, 1988 , p. catorce.
  12. ↑ Martillo, 1988 , pág. 14-15.
  13. ↑ John C. King y Dennis R. Bahler. Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos  (inglés)  = Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - Pág. 46. - ISSN 0161-1194 . -doi : 10.1080/ 0161-118891862747 . Archivado desde el original el 15 de febrero de 2019.
  14. ↑ John C. King y Dennis R. Bahler. Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos  (inglés)  = Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - Pág. 47. - ISSN 0161-1194 . -doi : 10.1080/ 0161-119391867755 . Archivado desde el original el 15 de febrero de 2019.
  15. ↑ Carl Hammer. Cifrados homofónicos de segundo orden  (inglés)  = Cifrados homofónicos de segundo orden // Cryptologia: Journal. - Taylor y Francis, 1988. - vol. 12. - Pág. 15-19. — ISSN 0161-1194 . -doi : 10.1080/ 0161-118891862747 . Archivado el 8 de mayo de 2020.
  16. ↑ John C. King y Dennis R. Bahler. Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos  (inglés)  = Un marco para el estudio de cifrados homofónicos en sistemas genéticos y de cifrado clásicos // Cryptologia: Journal. — Taylor & Francis, 1993. — Vol. 17. - Pág. 48-50. — ISSN 0161-1194 . -doi : 10.1080/ 0161-119391867755 . Archivado desde el original el 15 de febrero de 2019.

Literatura

Enlaces