Cifrado afín

El cifrado afín 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){\bmod {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\leq \ b\leq \ n$ , 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\neq \ 0$ . Además podemos acotar a que $a\geq \ 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 coprimos (o primos relativos). 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\geq \ 1$ y sea $f:{\mathcal {N}}_{m}->{\mathcal {N}}_{m}$ , definida con $f(x)=(ax+b){\bmod {m}}$ , con $a$ y $b$ enteros, $f$ es una biyección, si, y solo si $mcd(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){\bmod {n}}

En este cifrado, la clave viene definida por los valores enteros $a$ y $b$ , y por el orden usado en el alfabeto de cifrado 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)){\bmod {m}}$

donde $a^{-1}$ representa al inverso multiplicativo en aritmética modular (el menor número que $(a*a^{-1}){\bmod {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

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){\bmod {n}}$ . Por tanto para descifrar tenemos que realizar la operación $m_{i}=(c_{i}-b){\bmod {n}}$ donde $-b$ es el inverso de la adición en el conjunto de los enteros ${\bmod {n}}$ . Por ejemplo si $b=15$ y $n=27$ entonces $-b=12$ ya que se tiene que cumplir $b+-b{\bmod {n}}=0$ .

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}){\bmod {n}}$ . Por tanto para descifrar tenemos que realizar la operación $m_{i}=(a^{-1}*c_{i}){\bmod {n}}$ donde $a^{-1}$ es el inverso de la multiplicación en el conjunto de los enteros ${\bmod {n}}$ .

Si $a\neq \ 1$ y $b\neq \ 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){\bmod {n}}$ al despejar para poder descifrar obtenemos: $m_{i}=(a^{-1}*(c_{i}-b)){\bmod {n}}=(a^{-1}*(c_{i}+n-b)){\bmod {n}}$ la última igualdad aplicando propiedad elemental de aritmética modular.

Ejemplo

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){\bmod {2}}7=20$ , 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({\bmod {m}}=27)$ el inverso multiplicativo en aritmética modular es $a^{-1}=11$ . Por tanto para $s=20$ tenemos $(11*(20-15)){\bmod {\ }}27=1$ . El carácter que ocupa la posición 1 del alfabeto es la ' $a$ '.

Criptoanálisis

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

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

Ejemplo

Por ejemplo, supongamos que observando un texto cifrado podemos inferir que usa un alfabeto de cifrado con m=26 símbolos, lo que nos lleva a suponer que ha usado el alfabeto del inglés. 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

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 27(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.

Implementaciones en C

Cifrado

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/*Este código (creado por Arget) compilado tal cual está se convierte en un
  cifrador afín usado de la siguiente manera:
  affine-cipher a b plaintext
  Siendo 'a' y 'b' las claves y 'plaintext' el texto a cifrar.
  De manera predeterminada considera este alfabeto
  ABCDEFGHIJKLMNOPQRSTUVWXYZ
  Con A=1; B=2... sin embargo se puede modificar siguiendo las intrsucciones,
  Para usar la 'Ñ' el valor de 'm' se debe modificar por 27 así como
  descomentar/modificar las líneas indicadas. También se puede configurar
  fácilmente para usar A=0;B=1...
  Si se obtiene una '@' es debido a que el valor cifrado es 0, y al realizar
  la conversión para el ASCII se debe sumar 64: 0 + 64 = 64, valor de '@'*/

int main(int argc, char** argv)
{    
    int a = atoi(argv[1]),
        b = atoi(argv[2]),
        i = 0,
        m = 26, //m = 27 para usar Ñ
        len = strlen(argv[3]);
    char* plaintext;
    plaintext = (char*) malloc(len);
    strcpy(plaintext, argv[3]);

    char ciphertext, x;

    i = 0;
    while(i < len)
    {
        x = toupper(plaintext[i]) - 64;//A=1; Cambiar 64 por 65 para A=0.
        //if(x > 14) x++;//Para usar 'Ñ''
        ciphertext = ((a * x + b) % m) + 64; //Quitar "+ 64" si se usa 'Ñ' / Cambiar 64 por 65 para A=0
        printf("%c", ciphertext); //Cambiar "%c" por "%i\n" cuando se usa 'Ñ'
        i++;
    }

    free(plaintext);
    return 0;
}

Descifrado

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h> //toupper()

/*
Descifrador de cifrado afín por Arget.
Uso:
affine-decipher a b ciphertext
Usa el siguiente alfabeto
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Con A=1, B=2...
*/

int cim(int a, int m);

int main(int argc, char** argv)
{
    if(argc == 1) exit(-1);

    int a = atoi(argv[1]),
        b = atoi(argv[2]),
        m = 26,
        i,
        len = strlen(argv[3]),
        x,
        ai = cim(a, m);
    char* ciphertext;
    ciphertext = (char*) malloc(len);
    strcpy(ciphertext, argv[3]);

    if(!ai){printf("Error!");exit(-2);}

    for(i = 0; i < len; i++)
    {
        x = ciphertext[i] - 64;
        x = ((ai * abs((x - b))) % m) + 64;
        printf("%c", x);
    }

    return 0;
}

int cim(int a, int m)
{
    int b, //Almacena el valor de b en (a * b)(mod m)
        x; //Almacena el resultado de la op.

    for(b = 0; b < m; b++)
    {
        x = (a * b) % m;
        if(x == 1)
            return b;
    }
    return 0;
}

Referencias

Jorge Ramió Aguirre, Aplicaciones criptográficas. Libro guía de la asignatura de Seguridad Informática. Universidad Politécnica de Madrid. Enero 1998.

↑ James L. Hein,Discrete Structures, Logic and computability.pp. 109-110. Jones and Bartlett Publishers 2010.
↑ David Bishop, Introduction to Cryptography with Java Applets. Jones and Bartlett Publishers. 2003

Datos: Q382486

[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

[1]

[2]