Generador de reducción

En criptografía , el generador decreciente es una forma de generador de números pseudoaleatorios diseñado para usarse en un cifrado de flujo . Fue publicado en Crypto 1993 por Don Coppersmith , Hugo Krawczyk y Yishay Mansour . ^{[ 1 ]}

El generador de contracción utiliza dos registros de desplazamiento con retroalimentación lineal . Uno, denominado secuencia A , genera bits de salida, mientras que el otro, denominado secuencia S , controla su salida. Tanto A como S están sincronizados; si el bit S es 1, se emite el bit A ; si el bit S es 0, se descarta el bit A , no se emite nada y los registros se sincronizan de nuevo. Esto tiene la desventaja de que la tasa de salida del generador varía de forma irregular, y de una manera que sugiere el estado de S ; este problema puede superarse almacenando en búfer la salida. La secuencia aleatoria generada por el LFSR no puede garantizar la imprevisibilidad en un sistema seguro y se han propuesto varios métodos para mejorar su aleatoriedad ^[²^].

A pesar de esta simplicidad, actualmente no se conocen ataques mejores que la búsqueda exhaustiva cuando los polinomios de retroalimentación son secretos. Sin embargo, si los polinomios de retroalimentación son conocidos, el mejor ataque conocido requiere menos de A • S bits de salida. ^{[ 3 ]}

Una variante es el generador autoencogible .

Una implementación en Python

Este ejemplo utiliza dos secuencias de bits aleatorias de Galois para generar la secuencia de bits pseudoaleatoria de salida. El código Python se puede usar para cifrar y descifrar un archivo o cualquier secuencia de bytes.

#!/usr/bin/env python3importar sys# ---------------------------------------------------------------------------- # Las funciones de Crypto4o comienzan aquí # ----------------------------------------------------------------------------Clase GLFSR : """Registro de desplazamiento con retroalimentación lineal de Galois."""def __init__ ( self , polynom , initial_value ): print "Usando el polinomio 0x %X , valor inicial: 0x %X ." % ( polynom , initial_value )self.polynom = polynom | 1 self.data = initial_value tmp = polynom self.mask = 1mientras tmp ! = 0 : si tmp & self.mask ! = 0 : tmp ^ = self.maskSi tmp == 0 : salirmáscara propia << = 1def next_state ( self ): self . data <<= 1valor de retorno = 0Si self.data y self.mask no son iguales a 0 : retval = 1 self.data ^ = self.polynomvalor de retornoclase SPRNG : def __init __ ( self , polynom_d , init_value_d , polynom_c , init_value_c ): print " GLFSR D0: " , self.glfsr_d = GLFSR ( polynom_d , init_value_d ) print " GLFSR C0: " , self.glfsr_c = GLFSR ( polynom_c , init_value_c )def next_byte ( self ): byte = 0 bitpos = 7Mientras sea verdadero : bit_d = self.glfsr_d.next_state ( ) bit_c = self.glfsr_c.next_state ( )Si bit_c != 0 : bit_r = bit_d byte |= bit_r << bitposbitpos -= 1Si bitpos < 0 : salirbyte de retorno# ---------------------------------------------------------------------------- # Las funciones de Crypto4o terminan aquí # ----------------------------------------------------------------------------def main ( ): prng = SPRNG ( int ( sys.argv [ 3 ], 16 ) , int ( sys.argv [ 4 ] , 16 ) , int ( sys.argv [ 5 ] , 16 ) , int ( sys.argv [ 6 ] , 16 ) , )con open ( sys.argv [ 1 ] , " rb " ) as f , open ( sys.argv [ 2 ] , " wb " ) as g : while True : input_ch = f.read ( 1 )if input_ch == "" : breakrandom_ch = prng.next_byte ( ) & 0xFF g.write ( chr ( ord ( input_ch ) ^ random_ch ) )if __name__ == "__main__" : main ()

Véase también

FISH , un cifrado de flujo (inseguro) basado en el principio del generador decreciente.
Generador de pasos alternos , un cifrado de flujo similar

Referencias

↑ D. Coppersmith, H. Krawczyk y Y. Mansour, “ El generador encogimiento ”, en CRYPTO '93: Actas de la 13.ª conferencia internacional anual de criptología sobre avances en criptología, (Nueva York, NY, EE. UU.), págs. 22-39, Springer-Verlag New York, Inc., 1994
↑ Poorghanad, A. et al. Generación de números pseudoaleatorios de alta calidad mediante métodos evolutivos IEEE , DOI: 10.1109/CIS.2008.220.
↑ Caballero-Gil, P. et al. Nueva estrategia de ataque para el generador de contracción Journal of Research and Practice in Information Technology , Vol. 1, páginas 331–335, diciembre de 2008.

[1] D. Coppersmith, H. Krawczyk y Y. Mansour, “ El generador encogimiento ”, en CRYPTO '93: Actas de la 13.ª conferencia internacional anual de criptología sobre avances en criptología, (Nueva York, NY, EE. UU.), págs. 22-39, Springer-Verlag New York, Inc., 1994

[2] Poorghanad, A. et al. Generación de números pseudoaleatorios de alta calidad mediante métodos evolutivos IEEE , DOI: 10.1109/CIS.2008.220.

[3] Caballero-Gil, P. et al. Nueva estrategia de ataque para el generador de contracción Journal of Research and Practice in Information Technology , Vol. 1, páginas 331–335, diciembre de 2008.

[ 1 ]

[

[ 3 ]