Como estaba buscando una implementación de LFSR en Python, me encontré con este tema. Sin embargo he encontrado que la siguiente era un poco más precisa de acuerdo a mis necesidades:
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
El LFSR-generador anterior se basa en GF (2 k) módulo de cálculo (GF = Galois Field). Después de haber completado un curso de Algebra, voy a explicar esto de la manera matemática.inicio
de Let tomando, por ejemplo, GF (2), que es igual a {a x + un x + un x + a x + a x | un , un , ..., a ∈ Z } (para aclarar, Z n = {0,1, ..., n-1} y por lo tanto Z = {0,1}, es decir, un bit). Esto significa que este es el conjunto de todos los polinomios de cuarto grado con todos los factores presentes o no, pero sin múltiplos de estos factores (por ejemplo, no hay 2x k). x , x + x , 1 y x + x + x + x + 1, son ejemplos de miembros de este grupo.
Consideramos que este módulo de conjunto es un polinomio de cuarto grado (es decir, P (x) ∈ GF (2)), p. P (x) = x + x + x . Esta operación de módulo en un grupo también se denota como GF (2)/P (x). Para su referencia, P (x) describe los 'grifos' dentro del LFSR.
También tomamos un polinomio aleatorio de grado 3 o inferior (para que no se vea afectado por nuestro módulo, de lo contrario podríamos realizar la operación de módulo directamente en él), p. A (x) = x . Ahora, cada A siguiente (x) se calcula multiplicándolo por x: A i (x) = A i-1 (x) * x mod P (x).
Puesto que estamos en un campo limitado, la operación de módulo puede tener un efecto, pero sólo cuando la resultante A i (x) tiene al menos un factor de x (nuestro más alto factor de P (x)) Tenga en cuenta que, dado que estamos trabajando con números en Z , realizar la operación del módulo en sí no es más que determinar si cada i se convierte en 0 o 1 al agregar los dos valores de P (x) y A i (x) juntos (es decir, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0, o 'xoring' estos dos).
Cada polinomio se puede escribir como un conjunto de bits, por ejemplo x + x + x ~ 10011. El A (x) puede ser visto como la semilla. La operación 'times x' se puede ver como una operación de desplazamiento a la izquierda. La operación del módulo se puede ver como una operación de enmascaramiento de bits, siendo la máscara nuestra P (x).
El algoritmo representado anteriormente genera, por lo tanto, (una secuencia infinita de) patrones válidos de cuatro bits LFSR. Por ejemplo, para nuestra definido A (x) (x) y P (x) (x + x + x), podemos definir la siguiente primero dado resultados en GF (2) (nótese que a no se cede hasta que al final de la primera ronda - matemáticos generalmente empieza a contar en '1'):
i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
Nota que y nuestra máscara debe contener un '1' en la cuarta posición para asegurarse de que su LFSR genere resultados de cuatro bits. También tenga en cuenta que un '1' debe estar presente en la posición cero para asegurarse de que su flujo de bits no termine con un patrón de 0000 bits, o que el bit final quede sin utilizar (si todos los bits se desplazan hacia la izquierda, lo haría también terminan con un cero en la posición 0 después de un turno).
No todos los P (x) 's necesariamente son generadores de GF (2 k) (es decir, no todas las máscaras de k bits generar todos 2 k-1 -1 números). Por ejemplo, x + x + x + x + x genera 3 grupos de 5 polynomals distintos cada uno, o "3 ciclos de periodo de 5": 0001,0010,0100 , 1000,1111; 0011,0110,1100,0111,1110; y 0101,1010,1011,1001,1101. Tenga en cuenta que nunca se puede generar 0000 y no puede generar ningún otro número.
Normalmente, la salida de un LFSR es el bit que se 'desplaza', que es un '1' si se realiza la operación del módulo, y un '0' cuando no lo es. Los LFSR con un período de 2 k-1 -1, también llamados pseudo-ruido o PN-LFSR, se adhieren a los postulados de aleatoriedad de Golomb, que dice tanto que este bit de salida es "suficiente" al azar.
Por lo tanto, las secuencias de estos bits tienen su uso en criptografía, por ejemplo en los estándares de encriptación móvil A5/1 y A5/2, o en el estándar E0 Bluetooth. Sin embargo, no son tan seguros como cabría esperar: el Berlekamp-Massey algorithm se puede utilizar para realizar ingeniería inversa del polinomio característico (el P (x)) del LFSR. Por lo tanto, los estándares de cifrado fuertes usan Non-linear FSR o funciones no lineales similares. Un tema relacionado a esto es el S-Boxes utilizado en AES.
Tenga en cuenta que he utilizado el int.bit_length() operation. Esto no fue implementado hasta Python 2.7.
Si solo te gusta un patrón de bits finitos, puedes comprobar si la semilla es igual al resultado y luego romper el ciclo.
Puede utilizar mi método LFSR en for-loop (por ejemplo, for xor, pattern in lfsr(0b001,0b10011)) o puede llamar repetidamente a la operación .next() sobre el resultado del método, devolviendo un nuevo (xor, result) -pair cada vez.
Si busca LFSR en lo que se encuentra una gran cantidad ... –
Yo, no tanto lo que quería – MattiaG
Por qué el presente etiquetado como código de golf? – Landei