Para un cifrador la distancia de unicidad, también llamada punto de unicidad, es el valor mínimo de caracteres del texto cifrado que se necesitan para reducir a una el número de claves posibles y, por tanto, romper el cifrado. Es decir, después de intentar todas las posibles claves (fuerza bruta del espacio de claves) sólo hay una que puede hacer que el descifrado tenga sentido. La distancia de unicidad es posible a causa de la redundacia de los idiomas humanos (puesta de manifiesto cuando se estudia su ratio de entropía).
El concepto de distancia de unicidad fue introducido por C. E. Shannon.C. E. Shannon, "Communication Theory of Secrecy Systems"
La distancia de unicidad permite medir el secreto de un cifrador a partir de la cantidad de incertidumbre (entropía) de la clave condicionada por el conocimiento del texto cifrado (). Si entonces no hay incertidumbre y el cifrador es teóricamente rompible teniendo los suficientes recursos. La distancia de unicidad es la longitud mínima del texto cifrado que se necesita para determinar de forma única la clave.Dorothy Elizabeth Robling Denning,"Cryptography and Data Security",Addison-Wesley 1982
Un cifrador se dice que es incondicionalmente seguro si nunca se aproxima a 0 incluso para longitudes largas de texto cifrado. De la propia definición de secreto perfecto se puede concluir que un cifrador que tiene secreto perfecto no tiene distancia de unicidad y por tanto es incondicionalmente seguro. Shannon usaba el término secreto ideal para describir sistemas que no logran el secreto perfecto pero sin embargo no se pueden romper porque no dan suficiente información para determinar la clave.
Formalización teórica
Entropías condicionales interesantes en un sistema de cifrado Para un sistema de cifrado hay una serie de entropías condicionales interesantes:"Applied cryptology, cryptographic protocols and computer security models", Richard A. DeMillo et all. American Mathematical Society 1983"Basic methods of cryptography", J. C. A. Lubbe, Cambridge University Press 1998
Supongamos Un mensaje M1 es sometido a un proceso de cifrado usando la clave K1 obteniendo E(K1,M1)=C1. representan la probabilidad condicional de la clave K dado el criptograma recibido C. A veces también se denota por representan la probabilidad condicional del mensaje M dado el criptograma recibido C. A veces también se denota por 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), , también denotada por , mediante la fórmula:
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 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), , también denotada por , mediante la fórmula:
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), , también denotada por , mediante la fórmula:
Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado y la clave, denotado por o por . Dada una clave la relación entre texto cifrado y texto en claro es uno-a-uno y por tanto
Se ha demostrado que se cumple la siguiente relación entre las distintas entropías:
Esta relación nos pone de manifiesto un hecho bastante curioso: En general el objetivo de cualquiera que use un cifrador es tener un valor de 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 sea pequeño. Sin embargo, tener un valor pequeño de 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
Considerando la longitud del criptograma Podemos calcular y para aquellos criptogramas de una cierta longitud N (en el sumatorio sólo se consideran esos criptogramas).A estos valores son denotados por y . Otra notación alternativa equivalente es y .
La distancia de unicidad de un sistema de cifrado, si existe, nos da el valor mínimo valor de N para el cual . 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 , esto no garantiza que la clave pueda ser encontrada para cada situación concebible.J.C.A. Lubbe "Basic Methods of Cryptography". Cambridge University Press 1998 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á demostradoC. E. Shannon, "Communication Theory of Secrecy Systems" que se cumplen las siguientes propiedades: i) si (La equivocación de la clave es una función no creciente de N) ii)) si (La equivocación de los A primeros caracteres del mensaje es una función no creciente del número N de caracteres interceptados). iii) (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 el siguiente teorema:
donde representa la redundancia del texto en claro de longitud N, la cual es la diferencia entre la ratio absoluta y la ratio del idioma (). 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
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 , , 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.
Cálculo El método tradicional para el cálculo, normalmente aproximado, de la distancia de unicidad fue el propuesto por Shannon.C. E. Shannon, "Communication Theory of Secrecy Systems" Posteriormente Hellman extiende las conclusiones de Shannon y propone nuevas técnicas para estimar la distancia de unicidad.
La mayor parte de los cifradores son demasiado complejos para determinar las probabilidades requeridas para obtener la distancia de unicidad. Sin embargo Shannon mostróC. E. Shannon, "Communication Theory of Secrecy Systems" que es posible aproximarse al valor para cierto tipo de cifradores usando un modelo de cifrador al que llama cifrador aleatorio. En este cifrador modelo demuestra que el valor aproximado de la distancia de unicidad es . Aprovechándose de este resultado Shannon estima el valor de la distancia de unicidad para otros cifradores.
Martin Edward HellmanHellman, M. E., "An extension of the Shannon Theroy Approach to Cryptography". IEEE Trans. on Info. Theory. Vol IT-23 pp. 289-994 May 1977 derivó los mismos resultados que Shannon para la distancia de unicidad del cifrador aleatorio pero siguiendo un enfoque un poco diferente. Hellman usó un argumento de conteo, para dada una secuencia de símbolos de texto cifrado, encontrar el número de claves que podían haber generado esa secuencia particular. Hellman además muestra que el cifrador aleatorio tiene, entre la clase de los cifradores con el mismo tamaño de clave y tamaño de texto plano, la mínima distancia de unicidad y por tanto es el caso peor.A. Kh Al Jabri, "The unicity distance: An upper bound on the proability of an eavesdropper successfully estimating the secret key", King Saud University, Arabia Saudí 1996 Beauchemin and BrassardP. Beauchemin and G. Brassard, "A Generalization of Hellman's Extension to Shannon´s Approach to Cryptography". Journal of Cryptology 1988. generalizaron los resultados para incluir cifradores con claves y mensajes en claro que siguen distribuciones de probabilidad uniformes (aleatorias).
Cálculo para un cifrador aleatorio Veamos el cálculo de la distancia de unicidad para el cifrador aleatorioM. Davio, J., M. Goethals, "Elements of cryptology", Philips Research Laboratory, Brussels
Cifrador aleatorio Shannon definió un cifrador aleatorio como un sistema de cifrado que satisface las siguientes tres condiciones: i)El número de posibles mensajes de longitud N es
con la ratio absoluta con valor donde A es el cardinal del alfabeto que usa tanto el texto plano como el texto cifrado. ii) Los posibles mensajes de longitud N pueden ser divididos en dos grupos: Un grupo de los que tienen a priori una probabilidad alta y casi uniforme (los mensajes con significado). Otro grupo con una insignificante probabilidad total. El grupo con alta probabilidad contiene mensajes, con es la entropía por letra de mensajes de N letras. iii) El proceso de descifrado puede formalizarse como una serie de líneas que relacionan cada criptograma con una serie de textos en claro. Vamos a asumir que hay k claves equiprobables. Por tanto habrá k líneas hacia cada criptograma que proceden de una selección aleatoria de los posibles mensajes.
Cálculo Para el cifrador aleatorio, dado un criptograma, la probabilidad de obtener un mensaje con significado al descifrar usando una clave dada es:
donde D es la redundancia del idioma, para mensajes de N caracteres, medida en bits/carácter. Vamos a suponer que podemos aproximar el valor de redundancia del idioma para mensajes de N caracteres, por la redundancia del idioma. La redundancia del idioma es la diferencia entre la ratio absoluta y la ratio del idioma y por tanto se puede expresar con la ecuación:
Para el cifrador aleatorio, como hay k claves equiprobables entonces el valor de su entropía es y por tanto . Entonces, el valor esperado de criptogramas descifrados con significado es:
Por tanto: Si H(K)>>ND, entonces hay una gran probabilidad de obtener un criptograma descifrado con significado y entonces una baja probabilidad de determinar la clave y el mensaje correctos. Si H(K)<<ND, entonces tan pronto como se obtenga un criptograma descifrado con significado, entonces tiene casi toda probabilidad de ser el único correcto. La frontera entre estas dos situaciones está determinada por la cantidad
a la cual se le llama distancia de unicidad.
Cuando la información de la fuente es baja, sólo se requieren un pequeño número de símbolos (N) para llegar a la distancia de unicidad. En la práctica esto puede paliar asegurando una mínima información para los mensajes, por ejemplo usando un sistema de codificación.
Cálculo para un cifrador por sustitución monoalfabética aplicado al idioma inglés