Cifrado afín

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El cifrado afín también se le llama cifrado de transformación afín o cifrado monoalfabético genérico. Es un tipo de cifrado por sustitución en el que cada símbolo del alfabeto en claro (el alfabeto del texto en claro) es sustituido por un símbolo del alfabeto cifrado (el alfabeto del texto cifrado) siendo el número de símbolos del alfabeto en claro igual que el número de símbolos del alfabeto cifrado. Para hallar el símbolo del alfabeto cifrado que sustituye a un determinado símbolo del alfabeto en claro, se usa una función matemática afín en aritmética modular. Para poder aplicar la función matemática lo primero que hay que hacer es asignar un orden que a cada símbolo de cada uno de los alfabeto le asocie un número de orden. Una vez establecido esto, la fórmula matemática tiene la siguiente forma:

c_i=(a*m_i+b) \mod\ n

Donde:

c_i: Identifica el símbolo i del texto cifrado
a: Se la llama constante de decimación
m_i: Identifica el símbolo i del texto en claro
b: Se la llama constante de desplazamiento
n: Es el número de símbolos del alfabeto de cifrado (el orden)

Los valores numéricos de c_i y m_i para traducirlos a símbolos de alfabetos, se interpretan como la posición del símbolo en el orden elegido de cada alfabeto.

Sobre los valores de las constantes podemos decir:

  • 0 \le\ b \le\ 1 ya que para la sustitución definida para cualquier otro valor de a se puede encontrar un b cuya sustitución es equivalente.
  • Para que se defina una sustitución utilizable es necesario que a \ne\ 0. Además podemos acotar a que a \ge\ 1, ya que la sustitución definida con valores de a negativos se pueden obtener con el mismo valor de a pero sin el signo.
  • Por las propiedades de la aritmética modular, para que este tipo de cifrado sea operativo es necesario que a y n sean primos entre sí, también llamados coprimos o primos relativos ( \gcd\ (a,n) = 1). Esta condición es necesaria para que a tenga inverso de la multiplicación (a^{-1}) lo cual es necesario para poder descifrar. Además se puede demostrar[1] que sea m \ge\ 1 y sea f:\mathcal{N}_m->\mathcal{N}_m definida con f(x)=(ax+b) \mod\ m con a y b enteros, f es una biyección sí y sólo sí  \gcd\ (a,m)=1 .

Por ejemplo, podemos modelizar el cifrado César, suponiendo el orden natural del alfabeto de n símbolos, por la siguiente ecuación:

c_i=(m_i+3) \mod\ n

En este cifrado la clave viene definida por los valores enteros a y b, y por el orden usado en el alfabeto de claro y en el alfabeto en claro, ambos alfabetos son el mismo número de símbolos, m. Por tanto es un cifrado de clave simétrica.

Para descifrar habrá que realizar el proceso inverso que se puede describir con la función matemática D(x)=(a^{-1} (x-b)) \mod\ m donde a^{-1} representa al inverso multiplicativo en aritmética modular (el menor número que (a*a^{-1}) \mod\ m = 1).

Este tipo de cifrado se ha generalizado para su uso como cifrador de bloque en los llamados cifradores afínes por bloques.

Clasificación[editar]

Podemos clasificar los cifradores afines según los valores de a y b:

  • Si a=1 se dice que el cifrado es por desplazamiento puro. Con ello la función matemática queda c_i=(m_i+b) \mod\ n. Por tanto para descifrar tenemos que realizar la operación m_i=(c_i-b) \mod\ n donde -b es el inverso de la adición en el conjunto de los enteros módulo n. Por ejemplo si b=15 y n=27 entonces -b=12 ya que se tiene que cumplir b+-b \mod\ n = 1 .
Observar que si a=1 y b=0 y el alfabeto en claro y el alfabeto cifrado son iguales y con el mismo orden definido, entonces cada símbolo se sustituirá por sí mismo y por tanto no habrá cifrado.
  • Si b=0 se dice que el cifrado es por decimación pura. Con ello la función matemática queda c_i=(a*m_i) \mod\ n. Por tanto para descifrar tenemos que realizar la operación m_i=(a^{-1}*c_i) \mod\ n donde a^{-1} es el inverso de la multiplicación en el conjunto de los enteros módulo n.
  • Si  a \ne\ 1 y  b \ne\ 0 se dice que el cifrado es por sustitución afín. Por tanto en la función matemática c_i=(a*m_i+b) \mod\ n al despejar para poder descifrar obtenemos m_i=(a^{-1}*(c_i-b)) \mod\ n=(a^{-1}*(c_i+n-b)) \mod\ n, la última igualdad aplicando propiedad elemental de aritmética modular.

Ejemplo[editar]

Supongamos que a=5 y b=15 y usamos el alfabeto castellano con m=27 en el orden habitual como alfabeto en claro y como alfabeto cifrado. Usando el cifrado afín definido de esa forma el símbolo 'a' se convertirá en (5*1+15) \mod\ 27=20 y, por tanto, el carácter asociado será el que ocupa la posición 20 empezando desde 0, la 's'. Aplicando el mismo algoritmo podemos obtener que el texto cifrado de 'plantanuclear' es 'ntsdlspctmsb'.

Para descifrar aplicamos la fórmula de descifrado. Para a=5 el inverso multiplicativo es 135 (aprovecho que a=5 y m=27 son primos relativos y las propiedades de los inversos multiplicativos en aritmética modular). Por tanto para s=20 tenemos (135*(20-15)) \mod\ 27=0. El carácter que ocupa la posición 0 del alfabeto es la 'a'.

Criptoanálisis[editar]

El cifrado afín es vulnerable a ataques criptoanalíticos, los más habituales son:[2]

  • El análisis de frecuencias
  • La búsqueda en el espacio de claves

Análisis de frecuencias[editar]

El cifrado afín, como cualquier otro cifrado por sustitución, es vulnerable a ataques por análisis de frecuencias.

Ejemplo[editar]

Por ejemplo supongamos que observando un texto cifrado podemos inferir que usa un alfabeto de cifrado con m=26 símbolos. Si suponemos que el texto en claro que ha sido cifrado está escrito en idioma inglés con un alfabeto de m=26 símbolos. En el inglés los caracteres más frecuentes son la E y después la T. Si suponemos el orden habitual entonces E=4 y T=19. Analizando una cantidad suficiente de mensaje cifrado obtenemos que, por ejemplo, las más frecuentes son la V y después la E. Si suponemos el orden habitual V=21 y E=4. Del resultado anterior podemos ver que probablemente la E esté siendo sustutida por la V y la T por la E. Por tanto podemos obtener las siguientes congruencias:

21=(4a+b) \mod\ 26
4=(19a+b) \mod\ 26

Si restamos de la primera ecuación la segunda, obtenemos lo siguiente:

-17=15a \mod\ 26

resolviendo obtenemos:

a=11 \mod\ 26

Sustituyendo a en la primera ecuación original obtenemos:

21=((4*11)+b) \mod\ 26

despejando

b=(21-44) \mod\ 26=-23 \mod\ 26=3 \mod\ 26

A partir de estos valores puedo hallar el inverso multiplicativo, por ejemplo usando el algoritmo de Euclides extendido, a^{-1}=19. Ahora toca verificar nuestras suposiciones, si aplicando los valores obtenidos obtenemos un texto inteligible entonces habíamos acertado en nuestras suposiciones, en otro caso habremos fallado y será necesario hacer otras suposiciones.

Búsqueda en el espacio de claves[editar]

La función de Euler nos da el número de enteros de \mathcal{Z}_n que tienen inverso para la multiplicación. Aplicando dicha fórmula a n=27 el valor de la función de Euler es 27*(1-1/3)=18. De este resultado podemos concluir que el número de posibles cifradores definidos con n=27 es 26(posibles valores de b)*18(posibles valores de a)=486. Este valor es realmente pequeño y un ordenador podría probar todas las posibles combinaciones muy rápidamente.

Para hacer crecer este valor podemos usar una clave para que nos sirva como un desplazamiento adicional para cada símbolo. En esta situación, el cifrador se convierte en un cifrador de sustitución monoalfabético general en el que cada símbolo del alfabeto en claro es susituido por un símbolo del alfabeto cifrado. En este tipo de cifradores las posibles sustituciones son n!=27! (el número de las posibles permutaciones). Por ejemplo, si la clave es "HOLA" al primer símbolo de texto cifrado obtenido por la función, se le aplicará un desplazamiento de 8 (la H ocupa la octava posición), y así se sigue sucesivamente y cuando se acabe la clave volvemos a empezar.

Referencias[editar]

  • Jorge Ramió Aguirre, Aplicaciones criptográficas. Libro guía de la asignatura de Seguridad Informática. Universidad Politécnica de Madrid. Enero 1998.
  1. James L. Hein,Discrete Structures, Logic and computability.pp. 109-110. Jones and Bartlett Publishers 2010.
  2. David Bishop, Introduction to Cryptography with Java Applets. Jones and Bartlett Publishers. 2003