Teoría de la información > Entropía y Criptografía

Veamos:
Fig1 - Idea intuitiva de la entropía

La entropía es una medida de aleatoriedad en la información, esto es importante en los procesos criptográficos. En seguridad de la información, requerimos algoritmos de seguridad para producir una alta aleatoriedad en el mensaje cifrado, de modo que haya menos o ninguna dependencia entre la clave y el texto cifrado. Con una alta aleatoriedad, la relación entre la clave y el texto cifrado se vuelve compleja.
Esta propiedad también se llama confusión. Se desea que un alto grado de confusión sea difícil de adivinar para un atacante. La entropía refleja el rendimiento del algoritmo criptográfico. [1, 3]

Calculemos la entropía en la información usando la fórmula de Shannon. 
Consideremos un mensaje $X$(variable aleatoria) la entropía de $X$, denotado por $H(X)$, es el valor medio ponderado de la cantidad de información de los diversos estados del mensaje $x_i$.
$$H(X) = - \sum_{i=1}^{n}p_i \log_2(p_i)$$
Donde $p_i = p(x_i)=p(X=x_i)$ es la probabilidad que ocurra el estado $x_i$.
Para alcanzar la entropía máxima de un mensaje $X$, cada uno de sus estado debe tener la misma probabilidad de ocurrencia(se deja de ejercicio al lector). Por ejemplo en el evento de lanzar un moneda no truncada al aire, la entropía es máxima, debido que la probabilidad es la misma para ambos resultados (cara o sello), sin embargo esto no sucede en una moneda truncada.
Los fundamentos de la teoría de la entropía está ligado a la teoría de probabilidad, esto se ve más claro en la entropía conjunta y la entropía condicional. [2,3]

Entropía conjunta 
Sí X e Y dos variables aleatorias, entonces la entropía conjunta se define como 
$$H(X,Y) = - \sum_{i=1}^{n}\sum_{j=1}^{m}p_{ij}.\log_2(p_{ij})$$
Donde $p_{ij}=p(x_i,x_j)=p(X=x_i, Y=y_j)$ es la probabilidad conjunta que ocurra el estado $x_i$ y $y_i$. 
Se debe entender que $H(X,Y)$ como el total de la cantidad de información contenida en una observación en particular $(x,y) \in X \times Y$, por otro lado se tiene un resultado interesante, siempre que $X$ e $Y$ sean independientes  $$H(X,Y) \leq H(X) + H(Y)$$
Entropía condicional  
Es la principal herramienta para entender algunos métodos de cifrados no perfectos, más adelante. 
Sean $X$ e $Y$ dos variables aleatorias, la entropía de $X$ habiendo observado un estado de $Y=y$ (entropía condicional de $X$ dado un estado de $Y$) se define como
$$H(X | Y = y) = -\sum_{i=1}^{n}p_{i|y}.\log_2(p_{i|y})$$
Donde $p_{i|y} = p(x_i|y)=p(X=x_i|Y=y)$ es la probabilidad que ocurra $x_i$ sabiendo que ya ocurrió  $y$.
Luego, para calcular la entropía condicional de $X$ dado $Y$, usamos 
$$H(X|Y) = \sum_{j=1}^{m}p_{j}. H(X | Y=y_j)$$
Donde $p_{j} = p(y_j)=p(Y=y_j)$ 

La entropía condicional y conjunta están relacionado por la siguiente igualdad $$H(X,Y) = H(Y) + H(X|Y)$$ Y se obtiene la siguiente desigualdad $H(X|Y) \leq H(X)$ con la igualdad si y solo si $X$ e $Y$ son independientes. [2]

En Criptografia : 

Siendo las siguientes variables aleatorias $P = texto~plano$, $C=texto~cifrado$ y $K=clave$, generalmente un algoritmo criptográfico debe cumplir las siguientes proposiciones 
  1. $H(P|K,C) = 0$ Si se conoce el texto cifrado y la clave, entonces se conoce el texto plano
  2. $H(C|K,P) = 0$ Si se conoce el texto cifrado y la clave, entonces se conoce el texto cifrado, esto vale para todo los cifrados de bloque, sin embargo algunos esquemas modernos no satisfacen esta última proposición. 
Usando estas dos proposiciones obtenemos $H(K,P,C) = H(K) + H(P)$ y  $H(K,P,C) = H(K,C) $, por lo tanto $$H(K,C) = H(K) + H(P)$$ Esta última igualdad es muy importante puesto que está relacionada con la entropía condicional $H(K|C)$,es llamada key equivocation, la cual es la cantidad de incertidumbre que queda sobre la clave después que se revela un texto cifrado.
Dicha relación se manifiesta así $$\mathbf{H(K|C) = H(K,C) -  H(C) = H(K) + H(P) - H(C)} $$ En otras palabras, la incertidumbre sobre la clave despues de mostrar el texto cifrado es igual a la incertidumbre en el texto plano y la llave, menos la incertidumbre del texto cifrado. [2, 4]

La entropía en algoritmos criptográficos se mide en bits por byte de información.

Ejemplo 1
Consideremos los siguientes espacios de probabilidad $\mathbb{P} = \{a,b,c,d\}$, $\mathbb{K}=\{k_1,k_2,k_3\}$ y $\mathbb{C} = \{1,2,3,4\}$ con las siguientes probabilidades asociadas : 
    • $p(P=a) = 0,25$, $p(P=b)=p(P=d)=0.3$ y $p(P=c)=0.15$
    • $p(K=k_1) = p(K=k_3) = 0.25$ y $p(K=k_2)=0.5$
    • $p(C=1)=p(C=2)=p(C=3)=0.2625$ y $p(C=4)=0.2125$
Calculando el valor de las entropías tenemos $H(P) \approx 1.9527$, $H(K) \approx 1.5$ y $H(C) \approx 1.9944$, por lo tanto $$\mathbf{H(K|C) = H(K) + H(P) - H(C) \approx 1.4583}$$
La interpretación es que luego de mostrar el texto cifrado se sabe aproximadamente un bit y medio por byte de la clave, esto índica que el sistema no es totalmente seguro, aunque esto implique un alcance asintótico en este contexto. 

Ejemplo 2
Consideramos un byte, y los 256 valores permitidos son equiprobables, entonces el byte contiene 8 bits por byte de entropía(máxima) o, de manera equivalente, 8 bits de información real. Si algunos patrones de bits son más probables que otros, por ejemplo, el patrón de bits para la letra 'a', ​​entonces el byte contendrá menos de 8 bits de entropía o información. 
$$ \log_{2}(256-1) = 7.994353436858858 $$
Se tendría 7.99 bits por byte de entropía. 

Así que en este contexto, si se quiere más entropía se debe tener más bits aleatorios. Esto significa que la fuente de aleatoriedad debe ser cuasi aleatoria.
Por ejemplo 
  • Ruido atmosférico 
  • Clics de un contador Geiger
  • Movimientos del ratón 
  • Velocidad del viento
  • Precios de los combustibles
  • Entre otros. 

Bibliografía. 
[1]    Priyadarshini Patil, Prashant Narayankar, Narayan D G, Meena S M. A Comprehensive Evaluation of Cryptographic Algorithms: DES, 3DES, AES, RSA and Blowfish. International Conference on Information Security & Privacy (ICISP2015), 2016. 
[2]    Nigel P. Smart. Cryptography Made Simple. Universiy of Bristol. Springer. 2016.
[3] Thomas W. Edgar, David O. Manz, Science and Cyber Security, https://www.sciencedirect.com/topics/computer-science/entropy [en línea] in Research Methods for Cyber Security, 2017
[4]    Lawrence Stewart. Quora. What is entropy in terms of cryptography? https://www.quora.com/What-is-entropy-in-terms-of-cryptography [en línea]


Comentarios

Publicar un comentario

Entradas populares de este blog

Linear Q-Learning - Doble Péndulo Invertido

Imagen
Fig1: Doble péndulo invertido sobre un móvil. Se ha implementado los algoritmos de aprendizaje por refuerzo Linear Q-Learning y Deep Q-Learning para lograr la convergencia del movimiento de un doble péndulo invertido a su estado de equilibrio. Los resultados indican que para una perturbación uniformemente aleatoria de la posición de equilibrio en un pequeño intervalo, los algoritmos realizan entre 100 y 300 iteraciones de promedio para lograr la convergencia. Esta aplicación del Aprendizaje Automático al control de sistemas complejos y caóticos refuerzan el enfoque de los algoritmos de aprendizaje en muchas campos donde se requiere lograr la autonomía del agente o sistema, frente a los controladores clásicos usados usualmente. Artículo completo aquí.
Leer más

Esquema de cifrado compartido de Shamir

El Esquema de Cifrado Compartido de Shamir( Shamir's Secret Sharing ) es un algoritmo criptográfico creado por Adi Shamir , uno de los creadores del popular algoritmo RSA. El algoritmo es del tipo secreto compartido, donde cada participante es dueño de una única parte que se obtiene al dividir el secreto.  Lo interesante está en la reconstrucción, puesto que se requiere un número mínimo $k$ de participantes, también llamado umbral, para obtener el secreto.  Modelo matemático Se requiere dividir el secreto $S$ (e.g una clave compartida para acceder a una caja fuerte) en $n$ partes $S_1, S_2, ... , S_n$ de tal manera que $S$ puede ser reconstruida por cualquier combinación de $\textbf{k}\leq n$ o más partes, sin embargo si tenemos menos de $k$ partes, $S$ es completamente indeterminado.  Este esquema es llamado un $(k,n)$ esquema de umbral , además si $k=n$ requerimos todas las partes para la reconstrucción del secreto.  La idea esencial de  Adi Shamir  se ba...
Leer más