¿Es todo cifrado una función biyectiva?

Question

¿Existe algún algoritmo de encriptación que no sea una función biyectiva?

¿Debe un cifrado dar siempre el mismo resultado dada la misma clave?

Answer 1

Formalmente una función de encriptación (simétrica) es una función $E$ de $\mathcal{M} \times \mathcal{K}$ a $\mathcal{M}$ , donde $\mathcal{M}$ es un espacio de mensajes (aquí utilizamos, por comodidad, el mismo para el texto cifrado y el texto plano) y $\mathcal{K}$ un espacio clave. Para un $k \in \mathcal{K}$ queremos $E(.,k)$ sea una biyección de $\mathcal{M}$ a $\mathcal{M}$ Esto significa que cada mensaje tiene una encriptación única bajo la clave $k$ y cada mensaje puede ser desencriptado también. (También hay nociones de cifrado aleatorio, etc., pero este es el modelo más sencillo).

Para algoritmos como RSA, o modos de cifrado como CBC, es cierto que un mensaje, bajo una misma clave, tiene múltiples cifrados, pero el descifrado debe poder hacerse siempre de forma única (podemos filtrar, por así decirlo, la aleatoriedad que hemos añadido como ingrediente extra en el cifrado). Es necesario en la criptografía asimétrica (como RSA) para tener un sistema seguro, y muy probablemente también en los sistemas simétricos. Evita algunos ataques que existirían de otro modo.

Para dar un ejemplo, para RSA usamos una clave grande (digamos un módulo de 1024 bits $n$ con algún exponente de encriptación $e$ ), por lo que podemos cifrar cosas que tengan un tamaño en torno a los 128 bytes (un poco menos, porque consideramos los números $x < n$ como mensajes, que pueden ser encriptados como $x^e \mod n$ ). Ahora, si tenemos un mensaje (como, digamos "Hola", o alguna clave de 16 bytes que queramos usar para comunicaciones posteriores, como se suele usar RSA, pero digamos que usamos "Hola", en su codificación ASCII (hex) 48 65 6c 6c 6f y queremos enviar eso como un mensaje, podríamos usar la cadena, como un número grande 0x48656c6c6f que es menor que $n$ (No daré un ejemplo, pero recuerda que lo elegimos de tamaño 128 bytes), así que podríamos simplemente encriptarlo, y desencriptarlo de forma única. Sin embargo, esto deja a un atacante (que también sabe $n$ y $e$ , por lo que podría hacer el mismo cifrado) con la opción de probar el cifrado (bajo esta clave) de todas las palabras de un diccionario y así encontrar el mensaje, sin romper realmente el RSA. Así que en la práctica (este es un estándar de uso común; existen otros pero son más difíciles de explicar), generamos un número $x$ del mensaje formando un número de 128 bytes como sigue: primero un byte 0x00 , entonces un byte 0x01 , luego 120 bytes aleatorios distintos de cero, luego de nuevo un byte 0x00 y luego el mensaje 0x48 65 6c 6c 6f (5 bytes), en total un número de 128 bytes, que empieza por 0x00 para asegurar que es menor que cualquier $n$ de ese tamaño 128 bytes y este es el $x$ que utilizamos para calcular $x^e \mod n$ . Después de la desencriptación (de forma única, haciendo otra exponenciación) quitamos los bytes aleatorios (todos distintos de cero, por lo que sabemos que el mensaje original empieza después del primer 0x00 después de la inicial. De este modo, el atacante no puede precalcular todos los posibles textos cifrados para un texto plano dado. Esto se denomina "rellenar el mensaje", y la norma exige al menos bytes aleatorios distintos de cero.

Así que, en cierto modo, el descifrado sigue siendo único, pero nos aseguramos de que los posibles textos cifrados (como número menor que $n$ ) no son todos los posibles números de este tipo, sólo los que obtenemos después de un relleno válido. El mensaje "real", previsto, es más corto. Así que RSA como función es una biyección, pero como mapeo de "mensaje real" a "texto cifrado" no es una función real. Lo será si añadimos la aleatoriedad como factor: dado un mensaje, un número aleatorio (para el relleno) y una clave, el resultado sigue siendo únicamente descifrable, y podemos, dada una clave, separar el mensaje y la aleatoriedad. Pero hay que tener en cuenta que hemos cambiado un poco la función de cifrado: el espacio del mensaje y el del texto cifrado son ahora diferentes, y esto tiene un valor añadido de seguridad. La desventaja es que ya no podemos cifrar directamente cualquier cadena. Pero en la práctica, sólo se encriptan valores pequeños con RSA, que luego se utilizan como una nueva clave para un algoritmo más rápido.

Para ver un ejemplo de esto en la criptografía simétrica, mire los modos de cifrado como CBC enlace de wikipedia que también amplían el texto cifrado con un bloque IV adicional para obtener más de un posible texto cifrado para un único texto plano.

Answer 2

Los algoritmos de encriptación no serán subjetivos si quieres tener una función de suma de comprobación. (Una suma de comprobación puede detectar errores de envío. Por ejemplo, puede añadir un dígito que haga que el número sea divisible por 9. Si recibe un número que no es divisible por 9, sabrá que ha habido un error de transmisión).

No estoy seguro de su segunda pregunta. Por supuesto, el cifrado puede variar en función del tiempo, pero tal vez no sea ésta su pregunta. (Si el cifrado varía según las circunstancias, también puede considerarse un cambio de clave, pero observo que hay sistemas de "cifrado" muy sencillos que no son inyectivos. Por ejemplo, la palabra "plomo" codifica significados muy diferentes que hay que reconstruir a partir del contexto. Este problema también está muy presente en los alfabetos sin vocales).

Está claro que si construyes algoritmos de encriptación modernos querrás tener una función inyectiva, pero hay situaciones (como algunas funciones hash) en las que la gente se conforma con que la función sea casi siempre inyectiva en la práctica.

Answer 3

Un algoritmo de cifrado que no garantice el mismo resultado para las mismas entradas (es decir, la clave de cifrado y el mensaje) es ciertamente posible. De hecho, el vector de inicialización de los cifradores de bloques encadenados suele ser aleatorio, pero solemos considerarlo como una de las entradas porque para una clave de cifrado y un vector de inicialización fijos, el algoritmo será determinista.

Como tal, un algoritmo de cifrado no es necesariamente una función bien definida, en el sentido matemático. Sin embargo, es esencial que bajo ninguna circunstancia el algoritmo asigne dos entradas diferentes a la misma salida - de lo contrario el descifrado es imposible. Por lo tanto, si el algoritmo de cifrado es determinista, es al menos un mapa inyectivo. Además, si el algoritmo de descifrado puede aceptar cualquier cadena como texto cifrado, entonces el algoritmo de cifrado también debe ser sobreyectivo, y en esta situación es biyectivo.

Answer 4

"¿Debe un cifrado dar siempre el mismo resultado dada la misma clave?"

No. Si el mensaje cifrado es siempre el mismo, el sistema es vulnerable a los ataques de repetición.

Probablemente ya conoces varios algoritmos de cifrado que, si cifran el mismo texto plano con la misma clave, siempre producen de forma determinista el mismo texto cifrado.

Hay muchos algoritmos de cifrado (algunos de ellos se enumeran a continuación) que, si se cifra el mismo texto plano con la misma clave cien veces, producirá (casi con seguridad) cien textos cifrados diferentes.

Si descifras esos 100 textos cifrados con la clave correcta y el algoritmo de descifrado apropiado, todos ellos producirán una copia perfecta del texto plano original.

Estos criptosistemas generalmente hacen que el transmisor saque números de un generador de números aleatorios y de alguna manera transmiten esos números aleatorios al receptor dentro del mensaje de texto cifrado. Dado exactamente las mismas entradas - es decir, el generador de números aleatorios se rompe y produce exactamente los mismos bytes de nuevo, un error en el software permite seguir utilizando la misma clave incluso después de que el contador de mensajes se ponga a cero, y utilizamos la misma clave y el mismo mensaje de texto plano - estos criptosistemas producirían el mismo mensaje de texto cifrado.

cifrados simétricos con un IV

Todo cifrado que utilice un vector de inicialización cifrarán el mismo texto plano de muchas maneras diferentes. (No son biyectivas).

Normalmente, el texto cifrado se compone de un vector de inicialización aleatorio (enviado sin cifrar) concatenado con los datos cifrados (generalmente de la misma longitud que el texto plano, o redondeado a un bloque completo). El vector de inicialización se genera de nuevo para cada mensaje. (Con TKIP y CCMP, el IV es un simple contador -- el TSC; con algunos otros algoritmos de encriptación, el IV se extrae de un generador de números aleatorios). El vector de inicialización es 10 bytes para CipherSaber, 3 bytes para Wired Equivalent Privacy, 6 bytes para TKIP, 6 bytes para CCMP, etc.

cifrados de clave pública

Los criptosistemas híbridos encriptan el mismo texto plano de muchas maneras diferentes. (No son biyectivos).

PGP, GPG, SSL, TLS, SSH, etc. utilizan criptosistemas híbridos.

El mensaje de texto cifrado se compone de una clave temporal cifrada concatenada con los datos encriptados (generalmente de la misma longitud que el texto plano, o redondeado a un bloque completo).

La clave temporal se extrae de un generador de números aleatorios para cada mensaje. Así que el mismo mensaje de texto plano, enviado en otro momento casi seguramente será encriptado con una clave temporal diferente y, por tanto, es casi seguro que generará un mensaje de texto cifrado diferente.

El mensaje en texto plano se encripta con un cifrado simétrico utilizando la clave temporal. La clave temporal se cifra con un cifrado de clave pública utilizando la clave pública del destinatario.

Answer 5

He aquí una solución, teniendo en cuenta muchos casos.

Cifrado de clave simétrica

Sólo encriptación

No, al menos no encriptando bajo la misma clave. Si E(k1,u) = E(k2,u) entonces no tendría un receptor se confundiría en cuál.

Pero con llaves diferentes esto sería imposible. Si M es el espacio de mensajes y K es el espacio de claves, E: M x K -> M. Pero el espacio de todos los posibles (M,K) es mayor que M, así que esto es imposible.

Cifrado con un IV

Ahora, tenemos un argumento similar: EM : (M,K,I) -> M, pero el conjunto de todos los (M,K,I) es mayor que M. No pueden existir funciones biyectivas que utilicen modos como CBC y otros modos que utilicen IV (casi todos).

Pero con la misma clave, el cifrado sigue estando influenciado por el IV, lo que hace que siga siendo no bijetivo. Lo mismo con el mismo IV pero diferente clave. Pero si tenemos la misma clave y el mismo IV, a diferencia del cifrado solo, este es no biyectivo.

Cifras de clave no simétrica

Ver los argumentos de "encriptación con IV", porque hay tres argumentos: Mensaje, Clave privada, Clave pública.