Llevar registro de cambio de retroalimentación

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 13 de marzo de 2013; las comprobaciones requieren 23 ediciones .

El registro de desplazamiento con registro de desplazamiento de acarreo ( FCSR ) es un registro de desplazamiento de palabras de bits, un análogo aritmético de un registro de desplazamiento de retroalimentación lineal , se diferencia de él por la presencia de un registro de acarreo. Se utiliza para generar secuencias de bits pseudoaleatorias y también se utilizó para crear el cifrado de flujo F-FCSR .

Historia

En 1994 , Goresky y Klapper inventaron el registro de desplazamiento con retroalimentación de acarreo , ) inglésenCouture(Couture,ZamanyMarsagliaindependienteformadecomoasí L'Ecuyer en inglés ). Además, Clapper y Goresky querían usarlo para el criptoanálisis del generador sumador. Por otro lado, Marsaglia, Zaman, Couture, L'Ecuer tenían como objetivo encontrar un buen generador de números aleatorios para resolver problemas como el método cuasi-Monte Carlo . [una]

Descripción

El FCSR tiene un registro de desplazamiento, una función de retroalimentación y un registro de acarreo. La longitud del registro de desplazamiento es el número de bits. Cuando es necesario extraer un bit, todos los bits del registro de desplazamiento se desplazan una posición hacia la derecha. [2]

En lugar de aplicar XOR a todos los bits en la secuencia de toque, estos bits se agregan entre sí y al contenido del registro de acarreo. El resultado se convierte en un nuevo ritmo. El resultado dividido por se convierte en el nuevo contenido del registro de acarreo. [3] $modificación$ $2$ $2$

$metro$ — valor del registro de acarreo

\sigma ={q_{1}}{a_{k-1}}+\cdots +{q_{k}}{a_{0}}+m

{a_{k}}={\sigma}{mod}{2}

{m^{\principal}}=[{\sigma}/2]

$({a_{k}},\cdots,{a_{1}})$ — nuevo estado del registro

$m^{\principal}$ — nuevo valor del registro de acarreo

Ejemplo

Considere un ejemplo de un registro de 3 bits con derivaciones en la primera y segunda posición. Sea su valor inicial y el contenido inicial del registro de acarreo sea igual a . La salida será el bit más a la derecha del registro de desplazamiento . Otros estados del registro se muestran en la siguiente tabla: $\izquierda[0,\;0,\;1\derecha]$ $[0]$

Número de paso	registro de turnos	Llevar registro
0	$\izquierda[0,\;0,\;1\derecha]$	0
una	$\izquierda[1,\;0,\;0\derecha]$	0
2	$\izquierda[0,\;1,\;0\derecha]$	0
3	$\izquierda[1,\;0,\;1\derecha]$	0
cuatro	$\izquierda[1,\;1,\;0\derecha]$	0
5	$\izquierda[1,\;1,\;1\derecha]$	0
6	$\izquierda[0,\;1,\;1\derecha]$	una
7	$\izquierda[1,\;0,\;1\derecha]$	una
ocho	$\izquierda[0,\;1,\;0\derecha]$	una
9	$\izquierda[0,\;0,\;1\derecha]$	una
diez	$\izquierda[0,\;0,\;0\derecha]$	una
once	$\izquierda[1,\;0,\;0\derecha]$	0

El estado interno final (incluido el contenido del registro de acarreo) es el mismo que el segundo estado interno. A partir de este momento, la secuencia se repite cíclicamente con un periodo igual a . También vale la pena mencionar que el registro de acarreo no es un bit , sino un número. Su tamaño debe ser como mínimo , de donde es el número de ramas. En el ejemplo, solo hay tres ramas, por lo que el registro de acarreo es de un bit. Si hubiera cuatro ramas, entonces el registro de acarreo constaría de dos bits y podría tomar los valores o . [3] $diez$ ${\ estilo de visualización \ log _ {2} t}$ $t$ $0.1.2$ $3$

Propiedades

A diferencia de LFSR , hay un retraso para FCSR antes de que ingrese al modo cíclico, es decir, comienza a generar una secuencia repetitiva cíclica. Dependiendo del estado inicial elegido, son posibles 4 casos diferentes: [3]

El estado inicial puede ser parte del período máximo.
El estado inicial puede pasar a la secuencia de período máximo después de un retraso inicial.
El estado inicial puede, después de un retraso inicial, generar una secuencia de ceros.
El estado inicial puede, después de un retraso inicial, producir una secuencia de unos.

Empíricamente, puede verificar cómo termina un estado inicial particular. Necesito ejecutar FCSR por un tiempo. (Si es la cantidad inicial de memoria y es el número de bifurcaciones, entonces los ciclos son suficientes). Si el flujo de salida degenera en una secuencia infinita de ceros y unos por bit, ¿dónde está la longitud de FCSR, entonces este estado inicial no debería ser usado. [3] $metro$ $t$ ${~\log_{2}t}+{~\log_{2}m}+1$ $norte$ $norte$

Además, vale la pena señalar que un conjunto de claves generadoras basadas en FCSR será débil, ya que el estado inicial de FCSR corresponde a la clave del cifrado de flujo. [3]

El período máximo de FCSR es, donde es un número entero de la conexión. Este número define ramas y se define como: $q-1$ $q$

$q={2q_{1}}+{{2^{2}}q_{2}}+{{2^{3}}q_{3}}+\cdots +{{2^{n}}q_{ n}}-1$

$q$ - debe ser un número primo para el cual 2 es una raíz primitiva . [3] [1]

Conexión con el LFSR

Así como el análisis LFSR se basa en la suma de polinomios mod 2 primitivos , el análisis FCSR se basa en la suma de números, llamados 2-ádicos . En el mundo de los números 2-ádicos, hay análogos para todo. De la misma manera que se define la complejidad lineal , también se puede definir la complejidad biádica. También hay un análogo 2-ádico para el algoritmo de Berlekamp-Massey . Esto significa que el número de posibles cifrados de flujo se ha duplicado al menos. Cualquier cosa que se pueda hacer con LFSR se puede hacer con FCSR. [3]

Opciones de implementación

Configuración de Galois

La configuración de Galois consta de:

Registro principal de n bits , con algunos toques fijos $M=(m_{0},\cdots,{m_{{n-1}}})$ $d_{0},\cdots,d_{{n-1}}$
n-1 - registro de acarreo de bit $C=(c_{0},\cdots,c_{{n-2}})$

En el tiempo t, el estado cambia de la siguiente manera: $(M,C)$

1. , para todos , con y y donde representa el bit de realimentación. $x_{i}=m_{{i+1}}+{c_{i}}{d_{i}}+{m_{0}}{d_{i}}$ $0\leq i<n$ $m_{{n}}=0$ $c_{{n-1}}=0$ $m_{0}$

2. Se actualiza el estado: , para todos y , para todos . [4] [5] $m_{i}\flecha izquierda {x_{i}}mod2$ $yo\en [0\puntos n-1]$ $c_{i}\flecha izquierda {x_{i}}div2$ $yo\en [0\puntos n-2]$

Configuración de Fibonacci

La configuración de Fibonacci consta de:

n - registro principal de bits $M=(m_{0},\cdots,{m_{{n-1}}})$
Los grifos están asociados con un registro de acarreo que consta de bits, donde el peso de Hamming para $(d_{0},\cdots,d_{{n-1}})$ $C$ $w_{H}(d)$ $w_{H}(d)$ $d=(1+|q|)/2$

El estado cambia de la siguiente manera: $(M,c)$

1 .; $x=c+\sum_{{i=0}}^{{n-1}}{{m_{i}}{d_{{n-1-i}}}}$

2. estado de actualización: , . [4] [5] $M\flecha izquierda (m_{1},\puntos,m_{{n-1}},xmod2)$ $c\flecha izquierda xdiv2$

Posibles casos de uso en generadores

Generadores intermitentes intercalados

Artículo principal: generador Stop-Go

Utiliza tres registros de desplazamiento de diferentes longitudes. Aquí, el Registro 1 controla la frecuencia de reloj de los registros 2 y 3, es decir, el Registro 2 cambia su estado cuando la salida del Registro 1 es igual a uno, y el Registro 3, cuando la salida del Registro 1 es igual a uno. igual a cero. [3]

Estos registros usan FCSR en lugar de algunos LFSR, y la operación XOR se puede reemplazar con un acarreo adicional.

Generador Stop-Go FCSR: Registro-1, Registro-2, Registro-3 es FCSR. La función unificadora es XOR.
Generador stop-go FCSR/LFSR: Registro-1 - FCSR; Registro-2, Registro-3 - LFSR. La función unificadora es la suma con acarreo.
Generador stop-go FCSR/LFSR: Registro-1 - LFSR; Registro-2, Registro-3 - FCSR. La función unificadora es XOR. [3]

Generadores en cascada

Artículo principal: Cascada Gollmann

Este circuito es una versión mejorada del generador stop-go. Consiste en una secuencia de registros, el reloj de cada uno de los cuales está controlado por el registro anterior. Si la salida del Registro-1 en ese momento es 1, entonces el Registro-2 está cronometrado. Si la salida del Registro-2 en el momento es 1, entonces se cronometra el Registro-3, y así sucesivamente. La salida del último registro es la salida del generador. [3]

Hay dos formas de usar FCSR en osciladores en cascada:

Cascada FCSR. Cascada Gollmann con FCSR en lugar de LFSR.
Cascada FCSR/LFSR. Cascada de Gollmann con osciladores que cambian LFSR a FCSR y viceversa. [3]

Generadores combinados

Estos generadores utilizan un número variable de FCSR y/o LFSR y una variedad de funciones que combinan registros. La operación XOR destruye las propiedades algebraicas de la FCSR, por lo que tiene sentido usar esta operación para combinarlas. [3]

Generador de paridad FCSR. Todos los registros son FCSR y la función de unión es XOR.
Generador de paridad LFSR/FCSR. Se usa una mezcla de LFSR y FCSR, y la función de combinación es XOR.
Generador de umbral FCSR. Todos los registros son FCSR, y la función unificadora es la mayorización.
Generador de umbral LFSR/FCSR. Se usa una mezcla de LFSR y FCSR, y la función unificadora es la de mayorización.
Generador sumador FCSR. Todos los registros son FCSR y la función de combinación es suma con acarreo.
Generador sumador LFSR/FCSR. Se usa una mezcla de LFSR y FCSR, y la función de unión es carry-add. [3]

Aplicación

Los registros de desplazamiento con retroalimentación de acarreo pueden servir como base para crear varios generadores (algunos de los cuales se describen anteriormente), así como varios cifrados de flujo.

F-FCSR

Artículo principal: F-FCSR .

F-FCSR es una familia de cifrados de flujo basada en el uso de un registro de desplazamiento de retroalimentación de acarreo (FCSR) con un filtro de salida lineal. La idea del cifrado fue propuesta por Terry Berger, François Arnault y Cédric Larade. F-FCSR se presentó a la competencia eSTREAM , se incluyó en la lista de ganadores de la competencia en abril de 2008, pero luego se reveló una debilidad criptográfica y en septiembre de 2008 F-FCSR se eliminó de eSTREAM.

Véase también

Notas

↑ 1 2 A. Klapper Una encuesta de retroalimentación con registros de desplazamiento de acarreo (enlace descendente)
↑ A. Klapper y M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, en Journal of Cryptology vol. 10, págs. 111-147 , 1997, [1] (enlace inaccesible)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
↑ 1 2 A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers , 2004, [2] Archivado el 23 de septiembre de 2015 en Wayback Machine .
↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier y Benjamin Pousse, A new approach for FCSRs , [3] Archivado el 2 de junio de 2018 en Wayback Machine .

Literatura

Schneier B. Criptografía aplicada. Protocolos, algoritmos, textos fuente en lenguaje C. - Triunfo, 2013. - 816 p. - ISBN 978-5-89392-527-2 .