Escrito por: Ciro Gamboa

Revisado por: Holguer A. Becerra

 
 
 
Objetivos:
  • Aprender sobre los LFSRs y sus usos.
  • Usar el concepto de LFSR para hacer cifrado de datos en software y hardware.
Requisitos:

 

Conceptos 
 
¿Qué es un LFSR?
 
Linear Feedback Shift Registers (LFSR), hace referencia a circuitos digitales, conformados por registros de corrimiento con realimentación. Las diferentes salidas de los registros de corrimiento, sirven como entrada para la realimentación. Esta realimentación, se hace comúnmente con compuertas XOR, tal y como muestra la siguiente imagen:
 
 
Estos sistemas, son usados para la generación de secuencias pseudo-aleatorias de bits, esto quiere decir, que las secuencias producidas, no tienen un patrón lógico definido, pero después de llegar al 'tope' de la capacidad del sistema, vuelve a iniciar la secuencia 'aleatoria'. 
 
Para generar una secuencia pseudo-aleatoria, es necesario escoger cuidadosamente la salida de los registros que se van a usar para la realimentación, a estás salidas se les denomina taps. Con los taps adecuados, se puede llegar a generar una secuencia de (2^n)-1 combinaciones sin repetir, donde corresponde al número de registros del sistema o variar el 'orden' de la secuencia de bits de salida. Veamos una comparación de las salidas de un LFSR pequeño, con diferentes taps como entrada de realimentación:
 
 
 
Como se detalla en la imagen anterior, el '0' es el único valor que no está dentro de la secuencia. De allí se atribuye el '-1' , en la expresión correspondiente a las combinaciones que puede producir el LFSR. La secuencia de máxima longitud o MLS, por sus siglas en inglés (Maximal-Lenght Secuence), se produce, como se dijo antes, con la combinación correcta de taps. Por términos prácticos, no es conveniente hallar la MLS manualmente, por lo que se recurre a una tabla, que ha sido desarrollado por estudiosos del tema, que relaciona los taps a escoger, de acuerdo al número de registros que se tenga en nuestro LFSR:
 
La realimentación de los LFSR, no se hace exclusivamente con compuertas XOR que reciben los taps y luego van al registro inicial, también exiten otras configuraciones más especificas, que se pueden implementar dependiendo de la necesidad, aquí hay un ejemplo de ello:
 
 
Sea cual sea la configuración que se escoja para el LFSR, todas estas convergen en que pretenden generar secuencias lo más aleatorias posibles, tienen realimentación y necesitan un valor inicial. El valor de inicialización de los registros del LFSR, no puede ser cero, ya que la secuencia se quedaría en cero siempre (por lo menos en las configuraciones mas comunes). Por lo que es necesario darles un valor inicial, diferente de cero. A este valor se le conoce como KEY. En términos de circuitos digitales, la implementación del KEY, luce de la siguiente forma:
 
 
¿Para qué se usan los LFSR?
 
En aplicaciones prácticas, la secuencia pseudo-aleatoria, que producen los LFSR, recibe el nombre de PRBS (Pseudo Random Bit Sequence) o PN (Pseudo Noise). El PN, tiene múltiples aplicaciones, entre las cuales, destacan las siguientes:
 
Generación de números aleatorios
Las funciones generados de números aleatorios en software, son en realidad LFSR con muchos registros, por ello no se nota la aleatoriedad de los números.
 
CRC (Cyclic Redundancy Check)
En un flujo de datos digitales, de cualquier sistema, se puede usar un LFSR, para comprobar si hay datos repetidos dentro dentro de un rango determinado de información; esto se ve de la siguiente manera:
 
 
Criptología
Al mezclar información digital con las secuencias propias de un LFSR, se pueden decifrar los datos. Un ejemplo de ello, es la codificación de una señal digital transmitida con la ayuda del PN, producido por un LFSR. Una vez recibida la señal, se hace la operación XOR, con el orden adecuado para despejar la ecuación booleana que representa el cifrado, y se obtiene la señal original de nuevo. Esto se explica mejor de manera gráfica, con la siguiente imagen:
 
 
Uso en software de un LFSR
 
En esta sección, se implementara la metodología del LFSR, para cifrar una canción, por medio de un sencillo script en el lenguaje Python. 
 
Primero, se usarán algunas operaciones entre bits, para probar que se esté generando una secuencia. Se usará para el script, un LFSR de 32 bits.
Definimos una variable llamada lfsr y le damos el valor inicial de 3123123123. Este valor, es la llave, o KEY, del LFSR, es el valor de inicialización. Cabe resaltar que se escogió éste número por que en binario, su bit más significativo está en 1, esto es útil, para poder ver todos los bits, ya que si hay un cero a la izquierda, la consola de python no los muestra. Claramente el número no debe superar los 32 bits, es decir, no debe ser mayor de 4.294.967.296. El número seleccionado es 10111010001001110001001110110011 en binario. Se puede visualizar en la consola de Python, con el comando print bin(lfsr). 
lfsr=3123123123;#inicializo el LFSR KEY
print bin(lfsr);
 
El siguiente paso, es crear una variable, que en ésta ocasión se recibe el nombre de count, la cual servirá de parámetro para un ciclo while, cuya condición es que la variable count, sea menor que 10. Con esto se pretende ver en 10 ciclos, la secuencia producida por el LFSR.
 
count=0;
while(count<10):
Dentro del ciclo while, se declaran algunas variables que corresponden a los bits de realimentación que se usarán. Para 32 bits, según la tabla mostrada con anterioridad, los taps deben ser el bit 1, el 5, el 6 y el 31.
 
 
lfsr=3123123123;#inicializo el LFSR KEY
print bin(lfsr);
count=0;

while(count<10):
    #SHIFT LFSR
    bit1=(lfsr>>0) & 1;
    bit2=(lfsr>>5) & 1;
    bit3=(lfsr>>6) & 1;
    bit4=(lfsr>>31) & 1;
 
Para adquirir el bit específico, en el primer ciclo del loop, para cada caso (bit1, bit5, bit6, bit31), se usa el comando '>>', el cual se encarga de correr los bits hacia la derecha, para llegar a una posición específica en la cadena de bits. Por ejemplo, si se tiene la siguiente secuencia de bits: s = 101101, s>>2, da como resultado 001011; los 2 últimos bits desaparecen. Así mismo, está el corrimiento hacía la izquierda, en donde se aumenta el valor en potencias de dos. Por ejemplo, s<<2, da como resultado 10110100. Para nuestro caso, en el primer ciclo del programa, 
while(count<10):
    #SHIFT LFSR
    bit1=(lfsr>>0) & 1;
    bit2=(lfsr>>5) & 1;
    bit3=(lfsr>>6) & 1;
    bit4=(lfsr>>31) & 1;

    bitnuevo=bit1^ bit2 ^ bit3 ^ bit4;
    lfsr=lfsr>>1;
    lfsr=(lfsr & 0x7fffffff) | (bitnuevo<<31);

    print bin(lfsr);
    count= count + 1;
 
 
 
 
Ejemplo - Cifrando una canción usando LFSR 32 bits.
 
Una vez se ha entendido como funciona un LFRS, este se pondra a prueba para ver sus aplicativos en criptologia y de esta forma entender completamente porque pueden ser muy utiles, en este caso se cifrara una cancion(Descargar) que estan muestreada a 44100 hz, y contiene muestras de 8 bits. Para escuchar la cancion, procederemos a abrir Audacity y vamos a Archivo->Importar->Datos en bruto.
 
 
 
 
Una vez importada la canción el sistema nos pedira el formato en el cual queremos importarla, para esto escogemos "Unsigned 8 bit PCM, Little-endian, 1 Canal(mono), 44100hz"
 
 
 
 
Una vez la canción ha sido importada se procede a reproducir el contenido, para esto podemos oprimir en play y escuchar el resultado que vamos a cifrar. 
 
 
 
Una vez se sabe lo que se va a cifrar  procederemos a cifrarcar el archivo usando el script python que fue explicado anteriormente, pero adicionando algunas lineas adicionales para poder leer el archivo ".bin" como cualquier otro archivo.
 
 
import os

pFile1=open("UNEncrypted_song.bin","rb");#abro el archivo song.bin lectura binario
pFile2=open("Encrypted_song.bin","wb");#abro el archivo para escritura

#tamano del archivo
old_file_position = pFile1.tell();
pFile1.seek ( 0 , os.SEEK_END );
sizepFile1 = pFile1.tell();
pFile1.seek(old_file_position, os.SEEK_SET)

lfsr=3123123123;#inicializo el LFSR KEY
byte=0;

while(sizepFile1>0):
    #SHIFT LFSR
    bit1=(lfsr>>0) & 1;
    bit2=(lfsr>>5) & 1;
    bit3=(lfsr>>6) & 1;
    bit4=(lfsr>>31) & 1;
    bitnuevo=bit1^ bit2 ^ bit3 ^ bit4;
    lfsr=lfsr>>1;
    lfsr=(lfsr & 0x7fffffff) | (bitnuevo<<31);

    #read LFRS bit
    bitlfsr=lfsr &1;
    #print bin(lfsr)
    #read byte from file
    byte=pFile1.read(1);
    if(bitlfsr==1):
        pFile2.write(chr(ord(byte) ^ 255));
    else:
        pFile2.write(byte);
    sizepFile1=sizepFile1-1;

print "accion completada"  


pFile1.close();
pFile2.close();

 
 
Una vez tenemos el script python, procedemos a poner la cancion no cifrarcada en la misma carpeta donde esta el script
 
 
 
El nombre del archivo que se va a cifrar puede ser cambiando en el script en las siguientes lineas, para este ejemplo procedemos a poner el archivo pFile1 como la entrada del archivo que se quiere cifrar, y la salida pFile2 como el resultado cifrado.
 
 
Una vez se han modificado las lineas anteriores, se procede a ejecutar el script the python 
python lfsr_32bits.py​
 
 
se podra ver que en la carpeta donde esta el script y la canción se habra creado nuevo archivo llamando "Encrypted_song.bin".
 
 
Ahora se procede abrir la cancion cifrada usando Audacity para escuchar lo que sucede una vez encriptada, se debe importar de la misma manera que se importo la canción no cifrada(Unsigned 8 bit PCM, Little-endian, 1 Canal(mono), 44100hz).

 
 
Se procede a esuchar la canción, y se dara cuenta que la canción es irreconocible y no se puede determinar el tipo de sonido, felicitaciones! has cifrado tu primer archivo usando la tecnica LFSRs en 32 bits.
 
Ahora si se quiere decifrar la canción se puede usar el mismo script de python, cambiando el nombre de archivo de entrada y salida.
En esta caso la entrada sera la canción "Encrypted_song.bin" y la salida sera un nuevo archivo llamado "UnEncrypted_song2.bin".
 
Ahora se ejecuta nuevamente el script de python y se podra ver que se ha creado el nuevo archivo con la cancion decifrada.
 
 
Se procede a comprobar que los datos se recuperaran usando Audacity, se importa la canción nuevamente usando el formato de importación hemos usado.
 
 
 
Se reproduce y nos daremos cuenta que la canción ha vuelto ha ser la original! felicitaciones has decifrarcado tu primera canción usando LFSRs de 32 bits!
 
 
Ahora puedes hacer lo mismo no solo para cifrarcar canciones pero cualquier tipo de archivo, ya depende de ti que tipo de combinación de LFSR usas para hacer tus cifrarcaciones, y lo bueno es que tienes muchas combinaciones para hacer. Puedes doble cifrado, o triple o penta cifrado de tus archivos usando multiples semillas y tipos de estructuras, ya depende de ti y lo que tengas en mente. Podria ser una buena forma de proteger tus archivos personales donde contienes contraseñas, o información que alguien no quieras ver. Generalmente las personas usan sistemas de codificacion conocidos como Base64, pero este tipo de codificaciones son estandar, y conocidas, lo que las hace vulnerables, por eso en el mundo de criptologia siempre que se tiene una forma de cifrarcar y decodiifcar que no sean conocidas o no sean estandar, es mas seguro para cifrar tus archivos. 
 
 
Enjoy!
 
 
La segunda parte sera de como implementar este tipo de LFSRs y este ejemplo en una FPGA, para decifrado en tiempo real.