Registro de desplazamiento de retroalimentación lineal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 5 de octubre de 2016; las comprobaciones requieren 44 ediciones .

El registro de desplazamiento de retroalimentación lineal ( LFSR ) es un registro de desplazamiento de de bits , en el que el valor del bit de entrada (deslizante) es igual a una función booleana lineal a partir de los valores de los bits restantes del registro antes del desplazamiento. Se puede organizar tanto por software como por hardware. Se utiliza para generar secuencias de bits pseudoaleatorias , lo que se utiliza, en particular, en criptografía [1] . Un registro de desplazamiento con retroalimentación de acarreo y un registro de desplazamiento con retroalimentación generalizada funcionan con un principio similar .

Descripción

En el registro de desplazamiento con retroalimentación lineal (RSLOS) hay dos partes (módulos):

el registro de desplazamiento real;
un circuito de retroalimentación (o subrutina) que calcula el valor del bit insertado.

El registro consta de celdas de memoria funcional (bits de una o más palabras de máquina), cada una de las cuales almacena el estado actual (valor) de un bit. El número de celdas se denomina longitud del registro. Los bits (celdas) generalmente se numeran con números , el contenido de la -ésima celda se indica con . El valor del nuevo bit se determina antes del cambio de bit en el registro y solo después de que el cambio se escribe en la celda , y el siguiente bit generado se extrae de la celda. $L$ $i = 0,\;1,\;\puntos,\;L-1$ $i$ $S_{(L-1)-i}$ $S_L$ ${\ estilo de visualización 0}$ $L-1$

La función de retroalimentación para LFSR es una función booleana lineal de los valores de todos o algunos bits del registro. La función multiplica los bits de registro por los coeficientes , donde . El número de coeficientes es el mismo que el número de bits de registro . Los coeficientes toman los valores , y el último coeficiente es igual a, ya que el LFSR viene dado por el polinomio característico de grado . La adición del Módulo 2 (la operación “XOR”, indicada en las fórmulas con el símbolo “ ”) o su inversión lógica “ XNOR ” son funciones booleanas lineales y se usan con mayor frecuencia en tales registros [2] . En este caso, los bits que son variables de la función de retroalimentación se denominan taps , y el registro en sí se denomina configuración de Fibonacci [3] . $c_{yo}$ $yo = 1, \; 2,\; \puntos,\; L$ $L$ $c_{yo}$ $\{0, \; una \}$ $c_L$ $c_L = 1$ $L$ $\oplus$

El control de registro en implementaciones de hardware se realiza aplicando un pulso de cambio (también llamado reloj o pulso de reloj ) a todas las celdas. La gestión de registros en implementaciones de software se realiza mediante la ejecución de un bucle . En cada iteración del ciclo, se calcula la función de retroalimentación y se realiza un cambio de bit en la palabra.

Cómo funciona

Durante cada ciclo de reloj , el registro de desplazamiento de retroalimentación lineal realiza las siguientes operaciones:

se lee el bit ubicado en la celda ; este bit es el siguiente bit en la secuencia de salida; $L-1$
la función de retroalimentación calcula un nuevo valor para la celda utilizando los valores actuales de las celdas; ${\ estilo de visualización 0}$
el contenido de cada celda se mueve a la celda siguiente , donde ; $i$ $yo+1$ $i = 0,\;1,\;\puntos,\;L-2$
la celda se escribe en el bit previamente calculado por la función de realimentación. ${\ estilo de visualización 0}$

Si la función de retroalimentación realiza la operación lógica " XOR " (OR exclusivo), los valores de los bits (celdas) se pueden calcular utilizando las siguientes fórmulas [4] :

$S_L=(c_1*S_{L-1})\oplus(c_2*S_{L-2})\oplus\dots\oplus(c_L*S_{0})$

$S_{L+1}=(c_1*S_{L})\oplus(c_2*S_{L-1})\oplus\dots\oplus(c_L*S_{1})$ $...$ $S_{L+j-1}=(c_1*S_{L+j-2})\oplus(c_2*S_{L+j-3})\oplus\dots\oplus(c_L*S_{j-1} )$

Propiedades

Periodicidad

El período del registro de desplazamiento es la longitud mínima de la secuencia resultante antes de que comience a repetirse. La longitud LFSR tiene estados iniciales que definen los valores de los bits en las celdas. De estos , los estados son distintos de cero, por lo que la secuencia generada tiene un período de . El periodo de la secuencia generada es máximo e igual a , si el polinomio de realimentación (o polinomio característico) sobre el campo es primitivo . Para ello, es necesario (pero no suficiente) que se cumplan las siguientes 2 condiciones: $L$ $2^{{I}}$ $2^{L}-1$ $T\leq2^{L}-1$ $2^{L}-1$ $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\puntos +c_{1}x+1$ ${\ matemáticas {GF}} (2)$

un número par de toques;
los números de grifo, tomados en conjunto, y no en pares, son coprimos .

El número de todos los polinomios primitivos posibles es , donde es la función de Euler [5] . El registro dado por dicho polinomio se denomina registro de desplazamiento de período máximo (o generador de secuencias pseudoaleatorias ), y las secuencias generadas se denominan secuencias de período máximo (o secuencias M ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\fi$

Complejidad lineal

La complejidad lineal de una secuencia binaria infinita es el número, que se define de la siguiente manera: $S=(S_0,\;S_1,\;S_2,\;\puntos)$ $L(S)$

si es una secuencia cero, entonces ; $S=(0,\;0,\;0,\;\puntos)$ $L(S)=0$
si no hay LFSR que genere , entonces ; $S$ $L(S) = \infty$
de lo contrario , igual a la longitud del LFSR más corto que genera . $L(S)$ $S$

La complejidad lineal de una secuencia binaria finita es un número igual a la longitud del LFSR más corto que genera esta secuencia. $S_n=(S_0,\;S_1,\;\puntos,\;S_n)$ $L(S_n)$

La complejidad lineal de un registro de desplazamiento de retroalimentación lineal indica qué tan cerca está la secuencia generada del azar . Un algoritmo eficiente para determinar la complejidad lineal de una secuencia binaria finita es el algoritmo de Berlekamp-Massey .

Independencia de la correlación

En un intento por obtener una alta complejidad lineal de la secuencia generada, los criptógrafos combinan de forma no lineal las salidas de varios registros de desplazamiento. En este caso, una o más secuencias de salida (o incluso salidas de LFSR individuales) se pueden conectar mediante un flujo común y un criptoanalista puede abrirlas . Un ataque basado en dicha vulnerabilidad se denomina ataque de correlación . La idea principal de tal truco es encontrar alguna correlación entre la salida del generador y las salidas de sus componentes. Luego, al observar la secuencia de salida, se puede obtener información sobre estas salidas intermedias y, por lo tanto, piratear el generador. Thomas Siegenthaler ha demostrado que es posible definir exactamente la independencia de la correlación y que existe un equilibrio entre la independencia de la correlación y la complejidad lineal [7] .

Implementación de software

Las implementaciones de software de RSLOS son bastante lentas y funcionan más rápido si están escritas en ensamblador . Una de las soluciones es el uso paralelo de 16 RSLOS (o 32, dependiendo de la longitud de palabra en la arquitectura de la computadora). En tal esquema, se usa una matriz de palabras, cuyo tamaño es igual a la longitud del registro de desplazamiento, y cada bit de la palabra se refiere a su propio LFSR. Dado que se utiliza el mismo número de secuencias de tomas, esto puede generar una ganancia notable en el rendimiento del generador [3] .

Configuración de Fibonacci

Considere un registro de desplazamiento de 32 bits. Hay una secuencia de escape para ello . Esto significa que para generar un nuevo bit, es necesario sumar los bits 31, 30, 29, 27, 25 y 0 utilizando la operación XOR . El LFSR resultante tiene un período máximo . El código para dicho registro en C es el siguiente: $\izquierda(32,\;31,\;30,\;28,\;26,\;1\derecha)$ $2^{32}-1$

int LFSR_Fibonacci ( vacío ) { estático sin firmar largo S = 0x00000001 ; S = (((( S >> 31 ) ^ ( S >> 30 ) ^ ( S >> 29 ) ^ ( S >> 27 ) ^ ( S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | ( S >> 1 ); devolver S & 0x00000001 ; }

Configuración de Galois

Como en la configuración de Fibonacci, el circuito de realimentación es un conjunto de operaciones XOR de los tap bits con la salida del generador, pero el orden de los bits en el registro se invierte: el -ésimo bit es la entrada y el -ésimo bit es la salida . El resultado de la suma se escribe en la siguiente celda y el nuevo bit de salida se escribe en -th. Por lo tanto, si el bit generado es igual a cero, todos los bits en las celdas se desplazan hacia la derecha sin cambios, si el bit generado es igual a uno, los bits de derivación cambian su valor al contrario y todos los bits se desplazan. A la derecha. Tanto la configuración de Fibonacci como la configuración de Galois de la misma longitud generan las mismas secuencias, pero desplazadas en el tiempo una de otra (en este caso, los estados internos de los registros pueden diferir) [8] . $L-1$ ${\ estilo de visualización 0}$ $L-1$

Este generador no tiene mayor fuerza criptográfica , pero da una ganancia de rendimiento: todas las operaciones XOR mediante paralelización se pueden realizar en una sola operación, y no secuencialmente una tras otra, como en la configuración de Fibonacci. Este esquema también dará una ganancia en la implementación del hardware.

El código para un registro de desplazamiento de 32 bits en C es el siguiente:

int LFSR_Galois ( vacío ) { // para el polinomio 0x80000057, invertido 0xea000001 static unsigned long S = 0x00000001 ; si ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; devolver 1 ;} más { S >>= 1 ; devuelve 0 ;} }

Vale la pena señalar que un ciclo de un número fijo de llamadas a funciones LFSR_Galoisen la configuración de Galois es aproximadamente 2 veces más rápido que una función LFSR_Fibonaccien la configuración de Fibonacci ( compilador MS VS 2010 en Intel Core i5 ).

Un ejemplo de una secuencia generada

Configuración de Fibonacci

Sea LFSR dado por el polinomio característico . Esto significa que los bits de derivación serán el segundo y el 0, y la unidad en la fórmula polinomial significa que el bit 0 es la entrada. La función de retroalimentación tiene la forma . Digamos que el estado inicial del registro de desplazamiento era la secuencia . Otros estados del registro se muestran en la siguiente tabla: $x^{3}+x+1$ $S_j=S_{j-1}\o más S_{j-3}$ $\izquierda[0,\;0,\;1\derecha]$

Número de paso	Estado	Bit generado
0	$\izquierda[0,\;0,\;1\derecha]$	una
una	$\izquierda[1,\;0,\;0\derecha]$	0
2	$\izquierda[1,\;1,\;0\derecha]$	0
3	$\izquierda[1,\;1,\;1\derecha]$	una
cuatro	$\izquierda[0,\;1,\;1\derecha]$	una
5	$\izquierda[1,\;0,\;1\derecha]$	una
6	$\izquierda[0,\;1,\;0\derecha]$	0
7	$\izquierda[0,\;0,\;1\derecha]$	una

Dado que el estado interno en el séptimo paso volvió a su estado original, entonces, a partir del siguiente paso, los bits se repetirán. Es decir, la secuencia generada es la siguiente: (el orden de los bits en la secuencia corresponde al orden en que fueron generados por el LFSR). Así, el período de la sucesión es 7, es decir, el valor máximo posible, lo que sucedió debido a la primitividad del polinomio dado. $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Configuración de Galois

Tomemos el mismo polinomio característico, es decir , . Solo el primer bit se agrega al bit de salida. El estado inicial es el mismo. Otros estados del registro: $c_3=c_1=1$ $c_2=0$

Número de paso	Estado	Bit generado
0	$\izquierda[0,\;0,\;1\derecha]$	una
una	$\izquierda[1,\;0,\;1\derecha]$	una
2	$\izquierda[1,\;1,\;1\derecha]$	una
3	$\izquierda[1,\;1,\;0\derecha]$	0
cuatro	$\izquierda[0,\;1,\;1\derecha]$	una
5	$\izquierda[1,\;0,\;0\derecha]$	0
6	$\izquierda[0,\;1,\;0\derecha]$	0
7	$\izquierda[0,\;0,\;1\derecha]$	una

El estado interno del registro en el séptimo paso volvió a su estado original, por lo tanto, su período también es igual a 7. A diferencia de la configuración de Fibonacci, los estados internos del registro resultaron ser diferentes, pero la secuencia generada es la misma. , solo desplazado por 4 ciclos : (el orden de los bits en la secuencia corresponde al orden de su generación de LFSR). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

Representación matricial de LFSR

sección del artículo en inglés

Generando polinomios primitivos

Calcular un polinomio primitivo sobre un campo es un problema matemático bastante complicado: para generar un polinomio de grado primitivo, necesitas conocer los factores del número . Es más fácil elegir al azar un polinomio y probar su primitivismo [3] . Otro método es usar tablas listas para usar que enumeren los números de secuencias de tomas que proporcionan el período máximo del generador. A continuación se muestra una tabla de polinomios primitivos sobre el campo para registros de desplazamiento con un período máximo de hasta 19 bits [5] . Vale la pena considerar que un generador de cualquier longitud dada puede tener más de un polinomio primitivo según sus propiedades . Puede encontrar una lista completa de registros de 4 a 32 bits de longitud aquí . ${\ matemáticas {GF}} (2)$ $k$ $2^{k}-1$ ${\ matemáticas {GF}} (2)$

pedacitos, $norte$	polinomio primitivo	Período, $2^{n}-1$	Número de polinomios primitivos
2	$x^{2}+x+1$	3	una
3	$x^3+x^2+1$	7	2
cuatro	$x^4+x^3+1$	quince	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{ 7 }+x^{ 6 }+1$	127	Dieciocho
ocho	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	dieciséis
9	$x^{9}+x^{5}+1$	511	48
diez	$x^{10}+x^{7}+1$	1023	60
once	$x^{11}+x^{9}+1$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	8191	630
catorce	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
quince	$x^{15}+x^{14}+1$	32767	1800
dieciséis	$x^{16}+x^{14}+x^{13}+x^{11}+1$	65535	2048
17	$x^{17}+x^{14}+1$	131071	7710
Dieciocho	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[una]
2 - 786, 1024, 2048, 4096	[2]

Ventajas y desventajas

Beneficios

alto rendimiento de algoritmos criptográficos creados sobre la base de LFSR (por ejemplo , cifrados de flujo );
el uso de solo las operaciones de suma y multiplicación de bits más simples , implementadas en hardware en casi todos los dispositivos informáticos;
buenas propiedades criptográficas (los LFSR pueden generar secuencias de período largo con buenas propiedades estadísticas);
debido a su estructura, los LFSR se analizan fácilmente mediante métodos algebraicos.

Desventajas

Uno de los principales problemas de LFSR es que su implementación de software es extremadamente ineficiente: se deben evitar los polinomios de retroalimentación dispersos, ya que conducen a una piratería más fácil mediante un ataque de correlación , y los polinomios densos son muy lentos de calcular. Por lo tanto, una implementación de software de dicho generador no es más rápida que una implementación DES .
La linealidad de la secuencia a la salida del registro permite determinar de forma única el polinomio de realimentación sobre los bits en serie utilizando el algoritmo de Berlekamp-Massey o el algoritmo de Euclid [3] [4] . $C(x)$ $2L$
La relativa facilidad de análisis por métodos algebraicos no solo facilita el desarrollo, sino que también aumenta las posibilidades de romper un generador basado en LFSR.

Formas de mejorar la fuerza criptográfica de las secuencias generadas

Generadores con múltiples registros de desplazamiento

Este tipo de generador consta de varios registros de desplazamiento de retroalimentación lineal que generan bits respectivamente. A continuación, los bits generados se convierten mediante alguna función booleana . Cabe señalar que para generadores de este tipo, las longitudes de registro , , son relativamente primos entre sí. $x_{1,i},\;x_{2,i},\;\puntos,\;x_{M,i}$ $f(x_{1,i},\;x_{2,i},\;\puntos,\;x_{M,i})$ $L_i$ $i=1,\;2,\;\puntos,\;M$

El período de este generador es , donde es el número total de celdas. Por lo tanto, el uso de varios LFSR aumenta el período de la secuencia generada en comparación con un solo registro, lo que aumenta la fuerza criptográfica del generador. También aumenta la complejidad lineal o la longitud del registro más corto correspondiente a un generador dado. Tal registro se encuentra usando el algoritmo de Berlekamp-Massey usando la secuencia generada. En el mejor de los casos, su longitud es proporcional al período de la secuencia generada [4] . $T=(2^{L_1}-1)\cdot(2^{L_2}-1)\cdots(2^{L_M}-1)\lesssim2^L$ $L=\sum\limits_{i=1}^M L_i$

Generadores con transformaciones no lineales

El diagrama de bloques de dicho generador no es diferente del diagrama del generador anterior. La principal diferencia es que el dispositivo de transformación viene dado por una función booleana no lineal . Como tal función, por ejemplo, se toma el polinomio de Zhegalkin (según el teorema de Zhegalkin , cualquier función booleana puede ser representada de manera única por el polinomio de Zhegalkin). $f(x_1, x_2, \puntos, x_M)$

También se puede implementar un generador no lineal en un registro de desplazamiento con retroalimentación no lineal . Puede dar variantes de secuencias del período máximo , que es mayor que el de LFSR [5] . $2^{2^{L-1}-L}$

La fuerza criptográfica de este generador aumenta debido a la no linealidad de la función utilizada. Determinar el estado de los registros a partir de la secuencia de bits generada es un problema matemático complejo, porque no se conoce ningún algoritmo que restaure los estados originales.

Este método se utiliza, por ejemplo, en el generador de Geff y en el generador de Geff generalizado; sin embargo, dichos generadores pueden piratearse mediante análisis de correlación [7] .

Osciladores con diferentes tiempos de registro de desplazamiento

Generador de paradas y arranques

El generador Stop-and-Go ( ing. Stop-and-Go , Both-Piper ) utiliza la salida de LFSR-1 para controlar la frecuencia de reloj de LFSR-2, de modo que LFSR-2 cambie su estado en algún momento. solo si la salida de LFSR-1 en ese momento era igual a uno. Este esquema no resistió la apertura de correlación [3] . $t_{yo}$ $t_{i-1}$

Para aumentar la fuerza criptográfica, se propuso un generador stop-go intercalado . Utiliza tres registros de desplazamiento de diferentes longitudes. Aquí LFOS-1 controla la frecuencia de reloj de los registros 2 y 3, es decir, LFSR-2 cambia su estado cuando la salida LFSR-1 es igual a uno, y LFSR-3, cuando la salida LFSR-1 es igual a cero. La salida del generador es la operación del módulo dos de las salidas de RLOS-2 y RLLS-3. Este generador tiene un gran período y una gran complejidad lineal. Existe un método de apertura de correlación de RLOS-1, pero esto no debilita mucho las propiedades criptográficas del generador.

Un esquema de sincronización más complicado se usa en un generador de parada y arranque de dos vías , que usa 2 registros de desplazamiento de la misma longitud. Si la salida de LFSR-1 en un determinado momento es igual a cero, y en un momento es igual a uno, entonces LFSR-2 no está cronometrado en ese momento . Si la salida de LFSR-2 en el momento del tiempo es igual a cero, y en el momento del tiempo es igual a uno, y si este registro está cronometrado en el momento del tiempo , entonces en el mismo momento LFSR-1 es no cronometrado. La complejidad lineal de este circuito es aproximadamente igual al período de la secuencia generada. $t_{i-1}$ $t_{i-2}$ $t_{yo}$ $t_{i-1}$ $t_{i-2}$ $t_{yo}$

Generador autodiezador

Los osciladores autodiezmados controlan su propia frecuencia . Hay dos tipos de tales generadores. El primero fue propuesto por Rainer Rüppel . Consiste en un registro de desplazamiento y un circuito de retroalimentación lineal que cronometra el registro en función de cómo sale el registro de desplazamiento. Si la salida del LFSR es igual a uno, entonces el registro se cronometra con una frecuencia, y si la salida es cero, entonces con otra. El segundo tipo fue propuesto por Bill Chambers y Dieter Kollman . El circuito de retroalimentación no recibe la señal de salida en sí, sino el resultado de la operación XOR de ciertos bits LFSR.

También existen generadores retractiles y autoretractiles._ _ _ _ _ _ Son bastante nuevos y no todas sus propiedades están bien estudiadas. El primero utiliza dos LFSR. Si se aplica un pulso de reloj al generador y la salida de RLOS-1 es uno, entonces la salida del generador será la salida de RLLS-2. De lo contrario, cuando se aplica un pulso de reloj, ambos bits se restablecen y el reloj comienza de nuevo. En el segundo generador, en lugar de verificar las salidas de dos registros para 0 o 1, se verifican 2 bits de un registro.

El generador diezmado se puede piratear si se diezman los polinomios de retroalimentación. Además, su tasa de generación no es constante. Un generador autodiezador necesita aproximadamente 2 veces menos memoria que el primero, pero funciona 2 veces más lento [7] .

Oscilador multifrecuencia con producto interno

Este generador utiliza dos registros de desplazamiento RSLOS-1 y RSLOS-2. La frecuencia de reloj de RSLOS-2 es varias veces mayor que la de RSLOS-1. Ciertos bits de estos registros se multiplican entre sí mediante la operación AND . Los resultados de las multiplicaciones se suman mediante la operación XOR y se obtiene la secuencia de salida. Este generador tiene una alta complejidad lineal y buenas propiedades estadísticas. Sin embargo, su estado se puede determinar a partir de la secuencia de salida de length , donde y son las longitudes de LFSR-1 y LFSR-2, respectivamente, y es la relación de sus frecuencias de reloj. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Cascada Gollmann

Este circuito es una versión mejorada del generador stop-go. Consiste en una secuencia de LFSR, la sincronización de cada uno de los cuales está controlada por el LFSR anterior. Si la salida de LFSR-1 en ese momento es 1, entonces LFSR-2 está cronometrado. Si la salida de LFSR-2 en el momento del tiempo es 1, entonces LFSR-3 está cronometrado, y así sucesivamente. La salida del último LFSR es la salida del generador. Si la longitud de todos los LFSR es la misma e igual a , entonces el período del sistema LFSR es y la complejidad lineal es [7] . $t_{yo}$ $t_{yo}$ $L$ $METRO$ $(2^L - 1)^M$ $L(S) = L(2^L - 1)^{M-1}$

Esta idea es simple y se puede utilizar para generar secuencias con grandes periodos, grandes complejidades lineales y buenas propiedades estadísticas. Pero, desafortunadamente, son susceptibles a un ataque llamado lock - in , cuando un criptoanalista , restaurando primero la secuencia de entrada del último registro en la cascada, rompe toda la cascada, registro por registro. A medida que aumenta el número de registros, la secuencia generada se acerca al azar , por lo que es mejor usar más LFSR de longitud pequeña que menos LFSR largos. $METRO$

Generadores mayoritarios

El generador de mayoría (o umbral ) consiste en una gran cantidad de registros de desplazamiento, cuyas salidas van al dispositivo especificado por la función de mayoría, por ejemplo, elemento mayoritario . La particularidad de este generador es que cada uno de los registros de desplazamiento tiene su propio bit de reloj , que son las variables de la función mayoritaria. Por ejemplo, para tres registros, dicha función tiene la forma . Solo se desplazan aquellos registros cuyos bits de reloj son iguales al valor , es decir, el desplazamiento de los registros se produce en la mayoría de los valores de dichos bits: 0 o 1. $ai}$ $i=1,\;2,\;\puntos,\;M$ $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ $segundo(t)$

Por lo tanto, obtenemos un generador con un número variable de LFSR. Su complejidad lineal es , donde es la longitud del registro -ésimo [7] . Las desventajas de dicho generador son la posibilidad de enumeración directa y apertura de correlación (cada bit de salida brinda información sobre el estado del registro de desplazamiento, para ser exactos, 0.189 bits). $L(S) = \sum\limits_{i,j=1}^M L_iL_j$ $L_i$ $i$

Se utilizan generadores similares en los algoritmos de cifrado A5 (A5/1, A5/2).

Aplicación

Los registros de desplazamiento de retroalimentación lineal se pueden implementar en hardware, lo que les permite usarse para la generación rápida de secuencias pseudoaleatorias , como el espectro ensanchado de secuencia directa o la generación de señales de ruido [9] .

Uso en criptografía

Los registros de desplazamiento de retroalimentación lineal se han utilizado durante mucho tiempo como generadores de secuencias pseudoaleatorias para cifrados de flujo (especialmente en criptografía militar ). Sin embargo, LFSR es un esquema lineal y, en algunos casos, puede piratearse fácilmente. Por ejemplo, un criptoanalista puede interceptar una parte del texto cifrado y utilizarlo, utilizando el algoritmo Berlekamp-Massey mencionado anteriormente , para reconstruir un LFSR de tamaño mínimo que imite el LFSR original. Luego, el texto interceptado puede introducirse en el registro recibido y descifrarse. Los métodos para aumentar la fuerza criptográfica de los cifrados de flujo basados en LFSR se dan arriba .

El registro de desplazamiento de retroalimentación lineal es la base para cifrados de flujo como A5/1 y A5/2 utilizados en el estándar GSM , y el cifrado E0 utilizado en Bluetooth . El cifrado A5/2 se rompió, y los cifrados A5/1 y E0 tienen fallas graves [10] [11] .

El registro de desplazamiento de retroalimentación lineal está estrechamente relacionado con el generador congruente lineal [12] .

Usar como contadores

La frecuencia de la secuencia LFSR generada le permite usarla como divisor de reloj o contador [13] . Un contador basado en un oscilador de este tipo tiene un circuito de retroalimentación simplificado, a diferencia de los contadores binarios o de código Gray convencionales , y por lo tanto puede operar a altas velocidades de reloj. Sin embargo, debe asegurarse de que dicho contador nunca ingrese al estado cero.

Probando dispositivos digitales

A diferencia de un contador convencional, el LFSR no pasa de un estado a otro en el orden del conteo binario, lo que permite usarlo para generar una señal de prueba cuando se detectan errores en los circuitos lógicos [6] .

Además, los registros de desplazamiento de retroalimentación lineal se utilizan en la autocomprobación integrada ( autocomprobación integrada , BIST ) para el análisis de firmas (detección de errores de bits) en circuitos lógicos. Dichos sistemas se utilizan debido al número limitado de salidas de microcircuitos (no todos los valores de bits intermedios se pueden aplicar a la salida). El sistema BIST consta de 3 bloques: un generador de secuencias de prueba y un analizador de firmas, que se construyen sobre la base de LFSR, y un controlador de prueba. El registro de desplazamiento en el analizador "comprime" el resultado del circuito para la secuencia de prueba en una firma y continúa trabajando hasta que todos sus bits, excepto el 0, se vuelven iguales a cero, es decir, al estado . Junto con LFSR, hay un contador binario que cuenta el número de ciclos desde el final de la compresión de la reacción de prueba. Si el estado inicial del registro correspondía a la firma de referencia (firma de un circuito sin errores), entonces la lectura del contador corresponde al número del bit erróneo [14] [15] . $\izquierda[1,\;0,\;0,\;...,\;0\derecha]$

Dado que LFSR realiza una compresión con pérdida, es probable que en un esquema con errores la firma resultante sea igual a la de referencia. Esto se puede evitar mediante el uso de un analizador de firmas con múltiples entradas.

Revoltijo

Los registros de desplazamiento de retroalimentación lineal se utilizan en la codificación para producir un flujo digital con propiedades de secuencia aleatoria . Una secuencia LFSR pseudoaleatoria de longitud máxima se agrega en módulo 2 al flujo de bits transmitido, y la secuencia se genera a la misma velocidad que la transmisión de datos. Algunos sistemas y tecnologías que utilizan codificación son:

ATSC [16] ;
lenguado ;
DVB-T ;
NICAM ;
CDMA ;
100BASE-T2 Fast Ethernet ;
Ethernet Gigabit 1000BASE-T ;
PCI Express 3.0 ;
sata ;
SCSI conectado en serie ;
USB 3.0 ;
IEEE802.11a ;
Bluetooth LE

Véase también

Notas

↑ B. Sklyar, 2007 .
↑ Registros de desplazamiento de retroalimentación lineal en dispositivos Virtex . Consultado el 19 de noviembre de 2014. Archivado desde el original el 2 de noviembre de 2013. (indefinido)
↑ 1 2 3 4 5 B. Schneier, 2013 .
↑ 1 2 3 4 Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ 1 2 3 Yu.B. Kobzarev, 2013 .
↑ 1 2 Larín, 2008 .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Beker, Piper, 1982 .
↑ A. Sizonenko, 2012 .
↑ E. Barklan, E. Biham, N. Keller, 2008 .
↑ Y. Lu, W. Meier, S. Vaudenay, 2005 .
↑ D. Eastlake, J. Schiller, S. Crocker, 2005 .
↑ Registros de desplazamiento eficientes, contadores LFSR y generadores de secuencias pseudoaleatorias largas . Consultado el 18 de noviembre de 2014. Archivado desde el original el 25 de enero de 2021. (indefinido)
↑ B. Harrington, 2008 .
↑ O. Dyachenko .
↑ V. Vargauzin, 1999 .

Literatura

Schneier B. Criptografía aplicada. Protocolos, algoritmos, textos fuente en lenguaje C. - Triunfo, 2013. - 816 p. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Larin A. L. Fundamentos de la electrónica digital - M .: MIPT , 2008. - 314 p. — ISBN 978-5-7417-0228-4
Sklyar B. Comunicación digital. Fundamentos teóricos y aplicación práctica. - Williams, 2007. - 1104 págs. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Radar moderno. - Ripol Clásico, 2013. - 708 p. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Matemáticas discretas y criptología : curso de conferencias / ed. N. D. Podufalov - M. : Dialog-MEPhI , 2013. - 397 p. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Sistemas de cifrado: la protección de las comunicaciones (inglés) - Londres : Northwood Books , 1982. - 427 p. — ISBN 978-0-7198-2611-5
Sizonenko AB Fuente de ruido digital multicanal basada en registro de desplazamiento recurrente . - Revista de equipos especiales y comunicaciones n.° 3, 2012. Copia de archivofechada el 29 de noviembre de 2014 enWayback Machine
Barklan E. , Biham E. , Keller N. Criptoanálisis instantáneo de solo texto cifrado de comunicación cifrada GSM . - Revista de criptología No. 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Criptoanálisis instantáneo de solo texto cifrado de comunicación cifrada GSM . - Crypto No. 3621, 2005. (enlace inaccesible)
Eastlake D. , Schiller J. , Crocker S. Requisitos de aleatoriedad para la seguridad . — 2005.
Harrington B. Obtenga su impulso de BIST . — 2008. (enlace inaccesible)
Dyachenko O. N. Análisis compacto sobre el campo GF(3).
Vargauzin V. Principios de la televisión digital del estándar ATSC. - Revista Tele-Sputnik No. 9 (47), 1999.

Enlaces

Referencia LFSR . Teoría e implementación de LFSR, Secuencias de longitud máxima y Tablas de secuencias de tomas completas para longitudes de 7 a 16 millones (3 a 24 bits) y tablas parciales para longitudes de hasta 4 mil millones (25 a 32 bits) (enlace no disponible) Archivado el 1 de octubre de 2018 .
Recomendación de la unión internacional de telecomunicaciones O.151 . agosto de 1992
Rutina de generación de números pseudoaleatorios Archivado el 25 de diciembre de 2008 en Wayback Machine .
[3 ]
Explicación simple de LFSR para ingenieros
Términos de comentarios
Una implementación de un generador de números pseudoaleatorios de reducción criptográficamente seguro
Métodos y tareas de protección de información criptográfica (enlace inaccesible)