Distancia de unicidad

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 30 de marzo de 2018; la verificación requiere 1 edición .

La distancia de unicidad (en criptología) es el número de caracteres de texto cifrado en el que la entropía de información condicional de la clave (y, en consecuencia, del texto sin formato ) es igual a cero, y la clave en sí misma se determina de forma única.

Alcanzar la distancia de unicidad aún no significa que la clave (o el texto sin formato) se pueda encontrar en la práctica, ya que la definición no tiene en cuenta la computabilidad práctica de la clave, sino que solo postula que se puede encontrar, por ejemplo, utilizando métodos exhaustivos . buscar _

Definición

Definamos la función de confiabilidad de la clave a través de la entropía de información condicional de la clave y los símbolos de texto cifrado que son interceptados por el criptoanalista : $Z$ ${\displaystyle y_{1},y_{2},\puntos,y_{n))$

f_{0}=H\izquierda(Z\derecha)

f_{1}=H\izquierda(Z|y_{1}\derecha)

f_{2}=H\izquierda(Z|y_{1}y_{2}\derecha)

\puntos

f_{n}=H\left(Z|y_{1}y_{2}\dots y_{n}\right)

{\displaystyle f_{n}\leq f_{n-1}\leq \dots \leq f_{1}\leq f_{0))

Tal número de caracteres interceptados , en el que y se denomina distancia de unicidad. $tu$ ${\ estilo de visualización f_ {u} = 0}$

Fórmula aproximada

La derivación de la fórmula de distancia de unicidad es posible para algunos criptosistemas "buenos", en los que la entropía de la información del texto cifrado tiene ciertas propiedades de "linealidad":

H\left(Y\right)=N\log L

donde es el número total de caracteres en el texto cifrado del mensaje, es el alfabeto del texto cifrado, por simplicidad, igual al texto sin formato y la clave de cifrado

norte

L

H\left(y_{1}\dots y_{n}\right)\approx n\log L

H\left(y_{1}\dots y_{n}|Z\right)\approx {n \over N}H\left(X\right)

la última expresión es una "linealización" de la expresión

H\izquierda(Y|Z\derecha)=H\izquierda(X\derecha)

Luego, a partir de las expresiones para la entropía de información conjunta:

H\left(y_{1}\dots y_{n};Z\right)=H\left(y_{1}\dots y_{n}\right)+H\left(Z|y_{1 }\puntos y_{n}\right)\approx n\log L+f_{n}

H\left(y_{1}\dots y_{n};Z\right)=H\left(Z\right)+H\left(y_{1}\dots y_{n}|Z\right )\approx H\left(Z\right)+{n \over N}H\left(X\right)

n\log L+f_{n}\approx H\left(Z\right)+{n \over N}H\left(X\right)

n\approx {{H\left(Z\right)-f_{n}} \over {\log LH\left(X\right)/N}}={{H\left(Z\right) -f_{n}} \over {\log L\cdot \left({1-{{H\left(X\right)} \over {N\log L}}}\right)))

Entonces, de acuerdo con la definición de la distancia de unicidad como : ${\ estilo de visualización u: f_ {u} = 0}$

u\approx {H\left(Z\right) \over {\log LH\left(X\right)/N))={H\left(Z\right) \over {\log L\cdot \left({1-{{H\left(X\right)} \over {N\log L}}}\right)}}

La expresión se denomina redundancia de fuente . Si la redundancia de la fuente es cero, es decir, es imposible determinar a partir del texto sin formato si es correcto o no (no hay sumas de verificación ni firmas en él), entonces la distancia de unicidad se vuelve igual a infinito y el criptosistema se vuelve absolutamente seguro. $\rho =1-{{H\left(X\right)} \over {N\log L))$

Ejemplo

Para el idioma ruso, la redundancia es de 3,5 bits por carácter. Si se usa un cifrado monoalfabético , entonces el número de claves posibles en él es igual a , y la entropía de la clave (con una elección equiprobable) de un bit . ${\displaystyle 33!\aprox. 8,68\cdot 10^{36))$ $H\left(Z\right)=\log _{2}33!\aproximadamente 122,7$

Entonces, la distancia de unicidad para un texto ruso encriptado con un cifrado de sustitución simple es:

u={{H\left(Z\right)} \over {\rho }}\approx 35.1

Es decir, si un criptoanalista intercepta más de 35 caracteres del texto cifrado, lo más probable es que esto le permita (por ejemplo, mediante una búsqueda exhaustiva) restaurar el texto sin formato original. Si se interceptan menos caracteres, la recuperación del texto será ambigua (puede haber varias versiones diferentes del texto sin formato).

Literatura

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Distancia de unicidad // Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
G. V. Basalova Distancia de unicidad // Fundamentos de criptografía (ruso)

Enlaces

Bruce Schneier : Cómo reconocer texto sin formato (boletín informativo de Crypto-Gram, 15 de diciembre de 1998 )
Unicity Distancia calculada para cifrados comunes