Diseño, implementación y optimización de algoritmos criptográficos de generación de aleatorios y factorización de enteros

Résumé

Estudio de la aritmética modular; de las propiedades de los enteros; de la distribución de los números primos y de los modos de qué disponemos para su identificación; de los sistemas criptográficos más extendidos: especialmente del criptosistema de clave pública RSA; de los generadores de secuencias de bits aleatorios y de los generadores de las secuencias de bits pseudoaleatorios; de los diferentes algoritmos de factorización, especialmente de los algoritmos basados en la estrategia de FERMAT de buscar dos cuadrados congruentes con el módulo el número a factorizar; y de las características de la arquitectura de los computadores, especialmente de aquellas que más directamente influyen en la velocidad de ejecución de instrucciones. Análisis de diferentes implementaciones disponibles para el uso y manejo de enteros de gran longitud; de los diferentes tests de primalidad, y selección del de MILLER–RABIN, que hemos considerado el mejor; de los diferentes generadores de secuencias de bits pseudoaleatorios, y selección del que hemos considerado criptográficamente más seguro: BBS; de las diferentes implementaciones y mejoras que paulatinamente han ido surgiendo para el algoritmo de factorización basado en la técnica de las fracciones continuas, de los valores de sus parámetros óptimos para su mejor rendimiento, y de las principales semejanzas entre ese algoritmo y los posteriores de Carl POMERANCE (QS) y Arjen K. LENSTRA (NFS); de las diferentes condiciones que se debe exigir al criptosistema RSA para lograr su uso alejado de ataques y trampas; y un largo proceso de análisis de la interacción entre nuestro código y nuestra máquina, buscando siempre el modo de reducir tiempos. Diseño de un nuevo modelo de entero largo, con su definición de dominio o rango de valores posibles codificables y de sus operadores; de algoritmos varios matemáticos, criptográficos; de un generador de secuencias de bits aleatorios por entrada de teclado; de un protocolo de actuación para desarrollar con orden y sistema una tarea de optimización de código. Implementación de todas las herramientas necesarias para que nuestro modelo de entero largo resulta operativo en todas las necesidades de cálculo (operadores a nivel de bit, relacionales, aritméticos, funciones matemáticas), del generador de secuencias de bits de aleatorios diseñado y del generador de secuencias de bits pseudoaleatorios BBS; de los algoritmos para los test de primalidad; de todos los procesos necesarios para lograr factorizar enteros largos producto de dos primos: bibliotecas de funciones que son requeridas por el algoritmo CFRAC y programas para factorizar innumerables enteros (varios millones hemos factorizado en diferentes máquinas); replica de todas las implementaciones en forma de macro para lograr programas más largos pero, sobre todo, más veloces; y también de todas las herramientas necesarias para lograr analizar la interacción entre software y hardware. Y optimización del código estudiado, analizado, diseñado e implementado para factorizar enteros compuestos producto de dos primos grandes. Buscar con un protocolo diseñado, las formas de reducir tiempos de ejecución, analizando los tiempos, número de instrucciones, fallos de caché, instrucciones de salto. Buscar la manera de lograr obtener los factores de un entero, no sólo procurando algoritmos de menor complejidad computacional, sino también procurando implementaciones que renten al máximo las posibilidades de nuestros ordenadores actuales. Y siempre, deslumbrados ante la esférica perfección de los números. El motor principal de nuestro estudio ha sido la contemplación de la belleza.