ESTRUCTURAS GENERADORAS 

DE SECUENCIAS CIFRANTES

Generador de congruencia lineal.

Un generador de congruencia lineal ( LCG ) es un algoritmo que produce una secuencia de números pseudo-aleatorios calculados con una discontinua ecuación lineal por tramos . El método representa una de las más antiguas y más conocidas número de generadores pseudoaleatorios algoritmos. La teoría detrás de ellos es relativamente fácil de entender, y se implementa fácilmente y rápido, sobre todo en el hardware que puede proporcionar la aritmética módulo de almacenamiento de bits truncamiento.

El generador se define por la relación de recurrencia:

son enteros constantes que especifican el generador. Si c = 0, el generador es a menudo llamado un generador de congruencia multiplicativo (MCG), o Lehmer RNG . Si c ≠ 0, el método se llama un generador de congruencia mixta.

NLFSR (No-Lineal Feedback Shift Register).

Un  es un componente común en los modernos sistemas de cifrado de flujo , especialmente en RFIDy tarjetas inteligentes aplicaciones. NLFSRs son conocidos por ser más resistente a los ataques que criptoanalíticos Registros Feedback Shift lineales ( LFSRs ). Se sabe cómo generar un n -bit NLFSR longitud máxima de 2 ⁿ , generando una secuencia de Brujin, mediante la extensión de un LFSR de longitud máxima con n etapas; , pero la construcción de otros NLFSRs grandes con largos períodos garantizados sigue siendo una problema abierto. El uso de métodos de fuerza bruta, una lista de máximo período de n -bit NLFSRs para n <25 se ha hecho , así como para n = 25 y n = 27.

LFSR (linear feedback shift register).

Que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior.
El valor inicial se denomina semilla y, como la forma de operar el registro es determinista, la secuencia de valores producidos está completamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico.

Como trabaja:

La secuencia tap de un LFSR se puede representar como un polinomio mod 2. Esto significa que los coeficientes del polinomio deben ser 1's o 0's. Esto se llama polinomio de realimentación o característica polinomial.

Las salidas que influyen en la entrada, se denominan taps. Son las que aparecen en el polinomio. Y se indican en azul en el esquema inferior

·         Si el polinomio es primitivo, sí y solo sí, el LFSR es máximo, o lo que es lo mismo, tiene periodo máximo.

·         El LFSR sólo será máximo si el número de taps es par.

·         Los valores de tap en un LFSR máximo son coprimos.

·         Puede haber más de una secuencia tap que haga máximo al LFSR para esa longitud determinada.

Una vez encontrada una secuencia tap máxima, automáticamente sigue otra. Si la secuencia tap, en un LFSR n-bit, es [n,A,B,C], entonces la secuencia mirrorcorrespondiente es [n,n-A,n-B,n-C]. Por ejemplo, la secuencia tap [32,3,2,1], tiene su homólogo [32,29,30,31]. Ambos dan como resultado periodo máximo.