Resumen de Criptoanálisis de generadores no lineales de números pseudoaleatorios.
En esta tesis se realiza un estudio de varios algoritmos para generación de números pseudoaleatorios definidos por ciertos generadores no lineales, Las secuencias de números pseudoaleatorios son utilizadas en diferentes campos como: la simulación, la toma de decisiones aleatorias y los algoritmos criptográficos. En estos casos se recurre a los PRNG, generadores de números pseudoaleatorios que constituyen, en definitiva, una forma de expandir unos pocos bits obtenidos por mediciones en algún experimento. Son conocidos en la literatura diferentes estudios de algunos generadores, como por ejemplo, el generador de Lehmer (lineal), el generador de Blum Blum Shub, el generador inverso. El esquema más empleado consiste en fijar un cuerpo finito y una transformación sobre él. Aplicando recursivamente esta función obtenemos una secuencia aparentemente casual de enteros en un rango acotado. En las aplicaciones a la criptografía, la semilla y las constantes que definen el generador son parte de la clave secreta. Se quiere usar la salida del generador como un cifrado en flujo. Por supuesto, si varios valores cosecutivos son revelados, entonces es sencillo descubrir la semilla y las constantes.
De esta forma, solamente se exportan los bits más significativos de cada valor con la esperanza de que sea difícil predecir la suceción.
En esta tesis se ha demostrado que los generadores inverso modular, el cuadratico y, más generalmente el definido por un polinomio son predecibles, si se revela un número suficientemente grande de los bits más significativos de varios elementos consecutivos. Para ello se utliza la denominada técnica del LLL-algoritmo, introducida en el célebre trabajo de Lenstra.Lenstra.Lovász.
También se presentan argumentos heurísticos para cuando se posee información adicional, es decir, cuando uno más aproximaciones.
Este método es utilizado también en el problema de la factorización de números enteros conoci
