Análisis de frecuencia , criptoanálisis de frecuencia : uno de los métodos de criptoanálisis , basado en el supuesto de la existencia de una distribución estadística no trivial de caracteres individuales y sus secuencias, tanto en texto sin formato como en texto cifrado, que, hasta el reemplazo de caracteres , se conservará en el proceso de cifrado y descifrado.
De manera simplista, el análisis de frecuencia asume que la frecuencia de ocurrencia de una letra dada del alfabeto en textos suficientemente largos es la misma para diferentes textos del mismo idioma. Al mismo tiempo, en el caso del cifrado monoalfabético , si existe un carácter en el texto cifrado con una probabilidad de ocurrencia similar, entonces podemos asumir que es la letra cifrada indicada. Se aplica un razonamiento similar a los bigramas (secuencias de dos letras), trigramas, etc. en el caso de los cifrados polialfabéticos .
El método de criptoanálisis de frecuencia se conoce desde el siglo IX (obra de Al-Kindi ), aunque el caso más famoso de su aplicación en la vida real, quizás, sea el desciframiento de los jeroglíficos egipcios por J.-F. Champollion en 1822. En la ficción, las referencias más famosas son los cuentos "The Gold-Bug " de Edgar Allan Poe , "The Dancing Men " de Conan Doyle y la novela " Captain Grant's Children " de Jules Verne .
Desde mediados del siglo XX, la mayoría de los algoritmos de cifrado utilizados se han desarrollado resistentes al criptoanálisis de frecuencia, por lo que se utiliza principalmente en el proceso de formación de futuros criptógrafos.
Utiliza el hecho de que la probabilidad de aparición de letras individuales, así como su orden en palabras y frases de un lenguaje natural, está sujeta a patrones estadísticos: por ejemplo, un par de letras “sya” una al lado de la otra en El ruso es más probable que "tsy", y " o " en el idioma ruso no aparece en absoluto (pero se encuentra a menudo, por ejemplo, en checheno ). Al analizar un texto suficientemente largo cifrado por el método de reemplazo, es posible realizar un reemplazo inverso en función de las frecuencias de aparición de los caracteres y restaurar el texto original.
Como se mencionó anteriormente, las características importantes del texto son la repetición de letras (el número de letras diferentes en cada idioma es limitado), los pares de letras, es decir, m (m-gramos), la compatibilidad de las letras entre sí . , la alternancia de vocales y consonantes, y algunas otras características. Es de destacar que estas características son bastante estables.
La idea es contar el número de ocurrencias de cada n m posibles m-gramas en textos claros suficientemente largos T=t 1 t 2 …t l , compuestos por letras del alfabeto {a 1 , a 2 , …, a n } . Al mismo tiempo, se visualizan m-gramas consecutivos del texto:
t 1 t 2 … t m , t 2 t 3 … t m+1 , …, t i-m+1 t l-m+2 … t l .
Si L (a i1 a i2 … a im ) es el número de ocurrencias del m-gram a i1 a i2 … a im en el texto T , y L es el número total de m-grams contados, entonces para L suficientemente grande las frecuencias L (a i1 a i2 … a im )/ L , para un m-grama dado, difieren poco entre sí.
Debido a esto, la frecuencia relativa se considera una aproximación de la probabilidad P (a i1 a i2 …a im ) de la aparición de un m-grama dado en un lugar seleccionado al azar en el texto (este enfoque se adopta en la definición estadística de probabilidad).
En el caso general, la frecuencia de letras en términos porcentuales se puede determinar de la siguiente manera: se cuenta cuántas veces ocurre en el texto cifrado, luego el número resultante se divide por el número total de caracteres en el texto cifrado; para un porcentaje, el resultado se multiplica por 100.
Sin embargo, la frecuencia depende esencialmente no solo de la longitud del texto, sino también de su naturaleza. Por ejemplo, en el texto técnico, la letra F normalmente rara puede aparecer con mucha más frecuencia. Por lo tanto, para determinar de manera confiable la frecuencia promedio de las letras, es deseable tener un conjunto de textos diferentes.