Cifrado de Feistel

Empezando a buscar en que entretenerme un rato, comence a buscar algun tipo de cifrado, despues de un rato logre concluir que debía empezar desde los metodos utilizados antes o los metodos en los cuales estan "basados" los actuales métodos de cifrados, asi que encontre el Algoritmo de Feistel el cual hoy les presentaré.

Es un método de cifrado en bloque diseñado por Horst Feistel, también se le conoce como Red Feistel o Cadena de Feistel, una gran cantidad de cifrado por bloques lo utilizan, siendo el mas conocido el algoritmo Data Encryption Standard (DES) que mas adelante probablemente estaré publicando algo al respecto, recordemos que los tipos de cifrado según sus algoritmos puede ser: cifrado en bloque, donde el cifrado se realiza bloque a bloque y el cifrado en flujo, donde el cifrado se realiza bit a bit.

El algoritmo

Este algoritmo se denomina simétrico por rondas, es decir, realiza siempre las mismas operaciones un número determinado de veces (denominadas rondas). Los pasos de la red de Feistel son entre algunos más:

1. Se selecciona una cadena, N, normalmente de 64 o 128 bits (para mi ejemplo 64 bits), y se la divide en dos subcadenas, L y R, de igual longitud (N/2)
2. Se toma una función, F, y una clave K_i
3. Se realizan una serie de operaciones complejas con F y K_i y con L o R (solo uno de ellas)
4. La cadena obtenida se cambia por la cadena con la que no se han realizado operaciones, y se siguen haciendo las rondas.

Construcción del algoritmo

Las operaciones básicas de una red de Feistel son las siguientes: se descompone el texto plano en dos piezas iguales, (Lo, Ro). Para realizar el cifrado en cada ronda i= 0,1,2...n-1 , se calcula:

 

donde f es una función y Ki son cada una de las subclaves aplicadas a cada iteración (para mi ejemplo utilizo cada carácter de una clave de 8 bytes, es decir: K[i] ). Luego a Li-1 se le aplica un XOR (vease aqui) con el resultado de aplicar la función f (Ri-1, Ki). El texto cifrado viene dado por la concatenación de Ln y Rn.

Para el descifrado las operaciones que hay que realizar son:

Otra forma de ver el algoritmo es con esta imagen, la cual utilicé para guiarme al hacer código.

Código (Hecho en C)

Para este ejemplo utilicé una cadena de 8 caracteres como primer parametro (argv[1]) y una cadena de 8 caracteres como segundo parametro (argv[2]). La funcion F es el dato pasado como parametro (dato[i]) mas el Ascii del residuo de la division de pwd entre 17 (pwd%17).
Para compilacion ejecutar en terminal:

$gcc nombre_archivo.c -o ejecutable

$./ejecutable micadena miclave1

Donde "micadena" es la cadena a encriptar y "miclave1" es la clave que se utilizará para el cifrado.

Pueden ver el código desde aqui.

El código:

/**
 Autor: PaoloRamirez
 Tema: Cifrado de Feistel
 Link: https://www.facebook.com/PaoloProgrammer/
**/

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


void fun_aplicada(char dato[],char pwd);
void fun_xor(char dato1[], char dato2[]);

int main(int argc, char **argv)
{
 if(argc!=3)
 {
  perror("Insertar 2 parametros (p1:texto, p2:clave)");
  exit(0);
 }

 int len_texto,len_clave;
 len_texto=strlen(argv[1]);
 len_clave=strlen(argv[2]);

 /**
  Texto inicial
  Clave de cifrado
 **/
 //Tamaño de cadena = len+fincadena \0
 char texto[len_texto+1]; //L+R
 char clave[len_clave+1]; //Ki

 //Format
 memset(texto,0,sizeof(texto));
 memset(clave,0,sizeof(clave));

 //Copiar a variables
 strcpy(texto,argv[1]);
 strcpy(clave,argv[2]);


 printf("Texto: %s\n", texto);
 printf("Clave: %s\n\n\n", clave);

 /**
  CIFRADO
 **/
 char izquierda[(len_texto/2)+1]; //L
 char derecha[(len_texto/2)+1]; //R

 //Format
 memset(izquierda,0,sizeof(izquierda));
 memset(derecha,0,sizeof(derecha));

 strncpy(izquierda,texto,len_texto/2);
 strcpy(derecha,texto+len_texto/2);

 //Valores iniciales
 printf("Texto[0]---> L(0) = %s\tR(0) = %s\n", izquierda, derecha);

 //Ciclo iterativo de L0-N y R0-N)
 int i;
 char temp_fun[(len_texto/2)+1];
 char temp_xor[(len_texto/2) +1];
 memset(temp_fun,0,sizeof(temp_fun));
 memset(temp_xor,0,sizeof(temp_xor));


 for (i = 0; i < len_texto; i++)
 {
  //Asignar a Li+1 <- Ri
  strcpy(temp_xor,izquierda); //Obtengo en temp_xor: Li
  strcpy(izquierda,derecha); //Obtengo en izquierda: Li+1

  //Aplicar f(Ri, Ki) ; donde Ri: derecha , Ki: clave
  strcpy(temp_fun,derecha);
  fun_aplicada(temp_fun,clave[i]); //Obtengo en temp_fun: f(Ri, Ki)

  //Aplicar XOR: Li XOR f(Ri,Ki)
  fun_xor(temp_xor,temp_fun); //Obtengo en temp_xor: Li XOR f(Ri,Ki)

  //Asignar a Ri+1 <- Resultado de Li XOR f(Ri,Ki)
  strcpy(derecha,temp_xor); //Obtengo en derecha: Ri+1

  //Mostrar valores i+1
  printf("Texto[%i]---> L(%i) = %s\tR(%i) = %s\n", i+1, i+1, izquierda, i+1, derecha);
 }

 printf("Cifrado: L() = %s\tR() = %s\n", izquierda, derecha);
 printf("%s\n", "--------------------------------------");

 /**
  DESCRIFRADO
 **/
 for (i = len_texto-1; i >= 0; i--)
 {
  //Asignar a Ri-1 <- Li
  strcpy(temp_xor,derecha); //Obtengo en temp_xor: Ri
  strcpy(derecha,izquierda); //Obtengo en derecha: Ri-1

  //Aplicar f(Li, Ki) ; donde Li: izquierda , Ki: clave
  strcpy(temp_fun,izquierda);
  fun_aplicada(temp_fun,clave[i]); //Obtengo en temp_fun: f(Li, Ki)

  //Aplicar XOR: Ri XOR f(Li,Ki)
  fun_xor(temp_xor,temp_fun); //Obtengo en temp_xor: Ri XOR f(Li,Ki)

  //Asignar a Li-1 <- Resultado de Ri XOR f(Li,Ki)
  strcpy(izquierda,temp_xor); //Obtengo en izquierda: Li-1

  //Mostrar valores i+1
  printf("Texto[%i]---> L(%i) = %s\tR(%i) = %s\n", i, i, izquierda, i, derecha);
 }

 printf("Descrifrado: L() = %s\tR() = %s\n", izquierda, derecha);
 printf("%s\n", "--------------------------------------");
}


//Ascii dato[i] + Ascii residuo pwd/17
void fun_aplicada(char dato[],char pwd)
{
 int len_dato;
 len_dato = strlen(dato);
 int pwd_ki;
 pwd_ki= pwd%17;

 int i;
 for (i = 0; i < len_dato; i++)
 {
  dato[i] = dato[i] + pwd_ki;
 }
}


void fun_xor(char dato1[], char dato2[])
{
 int tam;
 tam = strlen(dato1);

 int i;
 for (i = 0; i < tam; i++)
 {
  dato1[i] = dato1[i]^dato2[i];
 }
}

Una ventaja de este modelo es que la función F usada no tiene por que se reversible, pudiendo ser todo lo complicada que se desee, esta cualidad permite a los criptografos concentrarse en la seguridad de dicha funcion sabiendo que el proceso de descifrado esta garantizado ya que la propia estructura de la red de Feistel es reversible. Para ello unicamente requiere que se invierta el orden de las subclaves utilizadas.

Enlaces

https://github.com/phaoliop/Programming_C-Cplus/blob/master/C/Cifrado/feistel.c

Referencias

https://es.wikipedia.org/wiki/Cifrado_de_Feistel