3-1) LFSR

Escrito por: Ciro Gamboa

Objetivos:

• Aprender sobre los LFSRs y sus usos.

• Usar el concepto de LFSR para hacer cifrado de datos en software y hardware.

Requisitos:

• Python IDLE

• Audacity

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 n 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 encriptar los datos. Un ejemplo de ello, es la encriptació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 la encriptación, 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 de programación 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). 

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.

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.

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, 

.

.