Cifrado y compresión

No hay contradicción aquí, siempre y cuando consideres el problema en términos de probabilistic . Por ejemplo:

  

La razón por la que estoy confundido es que pensé que todo lo que se suponía que tenía que hacer el cifrado era hacerlo tan difícil como que la fuerza bruta obligara a la clave a pasar del texto cifrado al texto plano. Me parece que podría haber una clave AES que produciría un texto cifrado con todos los 0 dados un texto sin formato determinado.

Sí, es ciertamente posible que una combinación de clave y texto simple pueda producir texto cifrado con todo cero. Pero dado que las claves deben seleccionarse al azar, si existe tal combinación, la probabilidad de que ocurra en la práctica es astronómicamente improbable.

Una de las nociones de seguridad clave para los cifrados es indistinguishability en chosen-plaintext attack ("IND-CPA"), que dice (aproximadamente) que un adversario no puede diferenciar los textos cifrados de manera eficaz, aparte de los bits aleatorios uniformes , incluso si eligen los plaintexts para ser encriptados. Más precisamente, cualquier algoritmo que tenga éxito en distinguir el cifrado debe ser prohibitivamente caro (por ejemplo, forzar una clave de 128 bits).

Esto significa que podemos sacar buenas conclusiones sobre la compresibilidad de los textos cifrados simplemente razonando sobre la compresibilidad de cadenas de bits aleatorias uniformes. Y todo se reduce a esto: para un algoritmo de compresión fijo, si selecciona aleatoriamente una cadena de bits n , existe la posibilidad de que el algoritmo comprima la cadena seleccionada con una longitud de m los bits ( m < n ) disminuyen exponencialmente con m . Si pudiera escribir un algoritmo eficiente (fuerza no bruta) que lograra un mejor éxito que este al comprimir los textos cifrados, entonces la seguridad del cifrado sería sospechosa.

La compresión y el cifrado producen resultados de alta entropía, pero por diferentes medios y por diferentes motivos.

La compresión elimina la redundancia (baja entropía), lo que aumenta la entropía promedio. Considere una secuencia como 111111111 ; Poca entropía ya que cada byte es el mismo. Ahora, pseudo-RLE a 1x9; ; ahora es la mitad de la longitud, y cada byte almacenado es diferente. Al eliminar lo mismo, te quedas con más diferencias; tiene sentido.

El cifrado no suele cambiar el tamaño de salida; aumentándolo en todo caso. Es por eso que quiere comprimir antes que encripta: texto plano con mayor entropía (generalmente menos adivinable) y menos bytes para cifrar. Para aumentar la entropía de salida, el cifrado mezcla la entropía en la clave con la entropía en el texto plano. El objetivo es maximizar la distribución de salida para que las entradas estrechamente relacionadas aún tengan una distribución de salida variada y uniforme.

Se debe a que "abc" produce salidas muy diferentes a "abd" que los atacantes no pueden decir qué tan cerca es una suposición en particular: deben clavar la llave exactamente o no funcionará en absoluto. Contrasta esto con un cerrojo de tambor en el que el atacante sabe que está a "1 pin de distancia" y vale un poco más de esfuerzo. Sin retroalimentación, los atacantes deben recurrir a la fuerza bruta, y debido a que esa fuerza bruta actualmente es dura / costosa / lenta, el atacante está desincentivado y está impedido matemáticamente.