Distancia de unicidad

Para un sistema de cifrado hay una serie de entropías condicionales interesantes:^[3][4]

Supongamos

• Un mensaje M₁ es sometido a un proceso de cifrado usando la clave K₁ obteniendo E(K₁,M₁)=C₁.
• ${\displaystyle P_{C}(K)}$ representan la probabilidad condicional de la clave K dado el criptograma recibido C. A veces también se denota por ${\displaystyle P(K|C)}$
• ${\displaystyle P_{C}(M)}$ representan la probabilidad condicional del mensaje M dado el criptograma recibido C. A veces también se denota por ${\displaystyle P(M|C)}$

Entonces:

• Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado, y por tanto medir la equivocación del mensaje (en inglés message equivocation), ${\displaystyle H_{C}(K)}$, también denotada por ${\displaystyle H(K|C)}$, mediante la fórmula:

${\displaystyle H_{C}(K)=-\sum _{E,K}P(E,K)\log _{P_{E}}(K)=-\sum _{E}P(E)\sum _{K}P_{E}(K)\log _{P_{E}}(K)}$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

Observar que si ${\displaystyle H_{C}(K)=0}$ significa que se podrá romper el cifrado pues ya no hay incertidumbre. Esta anulación nos introduce en el concepto de distancia de unicidad.

• Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado, y por tanto medir la equivocación de la clave (en inglés key equivocation), ${\displaystyle H_{C}(M)}$, también denotada por ${\displaystyle H(M|C)}$, mediante la fórmula:

${\displaystyle H_{C}(M)=-\sum _{E,M}P(E,M)\log _{P_{E}}(M)=-\sum _{E}P(E)\sum _{M}P_{E}(M)\log _{P_{E}}(M)}$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

• Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado y el mensaje en claro, y por tanto medir la equivocación del aspecto de la clave (en inglés key appearance equivocation), ${\displaystyle H_{C,M}(K)}$, también denotada por ${\displaystyle H(K|M,C)}$, mediante la fórmula:

${\displaystyle H_{C,M}(K)=-\sum _{E,M,C}P(E,K,M)\log _{P_{E,M}}(K)}$

• Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado y la clave, denotado por ${\displaystyle H_{C,K}(M)}$ o por ${\displaystyle H(M|K,C)}$. Dada una clave la relación entre texto cifrado y texto en claro es uno-a-uno y por tanto ${\displaystyle H_{C,K}(M)=0}$

Se ha demostrado^[4] que se cumple la siguiente relación entre las distintas entropías:

${\displaystyle H_{C,M}(K)=H_{C}(K)-H_{C}(M)}$

Esta relación nos pone de manifiesto un hecho bastante curioso:^[4]

En general el objetivo de cualquiera que use un cifrador es tener un valor de ${\displaystyle H_{C,M}(K)}$ alto para que el sistema tenga la máxima fortaleza posible para el caso de que el atacante disponga tanto del texto cifrado como del texto plano (ataque con texto plano conocido). Sin embargo, por la expresión de la ecuación, para ello es necesario que ${\displaystyle H_{C}(M)}$ sea pequeño. Sin embargo, tener un valor pequeño de ${\displaystyle H_{C}(M)}$ implica que haya poca incertidumbre respecto al texto plano una vez conocido el texto cifrado (ataque con sólo texto cifrado disponible), lo cual es contrario a los intereses de cualquiera que cifre un mensaje. Por tanto es necesario una solución de compromiso para que el sistema tenga una fortaleza aceptable para ambos tipos de ataque

Podemos calcular ${\displaystyle H_{C}(K)}$ y ${\displaystyle H_{C}(M)}$ para aquellos criptogramas de una cierta longitud N (en el sumatorio sólo se consideran esos criptogramas).A estos valores son denotados por ${\displaystyle H_{C}(K,N)}$ y ${\displaystyle H_{C}(M,N)}$. Otra notación alternativa equivalente es ${\displaystyle H(K/C^{N})}$ y ${\displaystyle H(M/C^{N})}$.

La distancia de unicidad de un sistema de cifrado, si existe, nos da el valor mínimo valor de N para el cual ${\displaystyle H_{C}(K,N)=0}$. Es decir, da el valor mínimo de la longitud del criptograma, N, para la que cierta clave K tiene probabilidad uno y el resto tiene probabilidad 0. Este valor es posible a causa de la redundacia de los idiomas humanos (puesta de manifiesto cuando se estudia su ratio de entropía).

Hay que remarcar que aunque la distancia de unicidad da un valor para el cual ${\displaystyle H_{C}(K,N)=0}$, esto no garantiza que la clave pueda ser encontrada para cada situación concebible.^[5] Esto sólo sucede en media. Esto es debido a los conceptos que se usan en la teoría de la información, como entropías, ratios, etc.. La distancia de unicidad representa valores medios de símbolos o letras requeridos.

Está demostrado^[1] que se cumplen las siguientes propiedades:

i)${\displaystyle H_{C}(K,S)\leq H_{C}(K,N)}$ si ${\displaystyle S\geq N}$ (La equivocación de la clave es una función no creciente de N)

ii))${\displaystyle H_{C}(M,S)\leq H_{C}(M,N)}$ si ${\displaystyle S\geq N}$ (La equivocación de los A primeros caracteres del mensaje es una función no creciente del número N de caracteres interceptados).

iii)${\displaystyle H_{C}(M,N)\leq H_{C}(K,N)}$ (Si N caracteres han sido interceptados, la equivocación de los primeros N caracteres del mensaje es menor o igual que la de la clave).

Además se cumple^[5] el siguiente teorema:

• ${\displaystyle H(K/C^{N})\geq H(K)-D_{N}}$

donde ${\displaystyle D_{N}}$ representa la redundancia del texto en claro de longitud N, la cual es la diferencia entre la ratio absoluta y la ratio del idioma (${\displaystyle D=R_{0}-R}$).

Por tanto acotando a la longitud N y suponiendo que ε es el número de símbolos diferentes del texto en claro y del texto cifrado, obtenemos

${\displaystyle D_{N}=N\log(\epsilon )-H(M^{N})}$

De la expresión podemos concluir que la si la redundancia incrementa, la equivocación media de la clave y por tanto la incertidumbre con respecto de la clave usada decrece. Por tanto la redundancia hace la tarea de encontrar la clave sea más fácil. Análogamente, métodos que reduzcan la redundancia mejoran la seguridad del criptosistema.

Otra conclusión que se puede obtener de la ecuación es que, al ser ${\displaystyle H(K/C^{N})\geq 0}$, ${\displaystyle H(K)\geq D_{N}}$, es decir, la equivocación de la clave, de forma general, no será cero y por tanto la clave no podrá determinarse de forma inequívoca.