Nuevo criptoanálisis de RSA de potencia prima con dos exponentes privados
Autores: Wang, Shixiong; Sun, Minghao
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Nuevo criptoanálisis de RSA de potencia prima con dos exponentes privados
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Variante
RSA de potencia prima
Ataques
Módulo
Factorización
Red enrejada
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
El RSA de Potencia Prima es una variante del esquema RSA debido a Takagi con módulo para , donde son del mismo tamaño de bits. En este documento, nos concentramos en un tipo de RSA de Potencia Prima que asume . Se presentan dos nuevos ataques a este tipo de RSA de Potencia Prima cuando se proporcionan dos pares de exponentes públicos y privados, a saber, y con el mismo módulo . Supongamos que . En 2015, Zheng y Hu demostraron que cuando , se puede factorizar en tiempo polinómico probabilístico. El primer ataque de este documento muestra que se puede obtener la factorización de en tiempo polinómico probabilístico, siempre que . Posteriormente, en el segundo ataque, mejoramos tanto el primer ataque como el ataque de Zheng y Hu, y mostramos que la condición ya es suficiente para romper el RSA de Potencia Prima. Al introducir múltiples parámetros, nuestras construcciones de retículas aprovechan al máximo la información conocida y obtienen el mejor ataque conocido. Específicamente, hacemos pleno uso de la información de que es un divisor de , mientras que el ataque de Zheng y Hu solo asume que es un divisor de . Como consecuencia, este método implica una mejor construcción de retícula y, por lo tanto, mejora el ataque anterior. Los experimentos que alcanzan un límite superior mejor que antes también lo verifican. Nuestros enfoques se basan en el método de Coppersmith para encontrar raíces pequeñas de ecuaciones polinómicas modulares bivariadas.
Descripción
El RSA de Potencia Prima es una variante del esquema RSA debido a Takagi con módulo para , donde son del mismo tamaño de bits. En este documento, nos concentramos en un tipo de RSA de Potencia Prima que asume . Se presentan dos nuevos ataques a este tipo de RSA de Potencia Prima cuando se proporcionan dos pares de exponentes públicos y privados, a saber, y con el mismo módulo . Supongamos que . En 2015, Zheng y Hu demostraron que cuando , se puede factorizar en tiempo polinómico probabilístico. El primer ataque de este documento muestra que se puede obtener la factorización de en tiempo polinómico probabilístico, siempre que . Posteriormente, en el segundo ataque, mejoramos tanto el primer ataque como el ataque de Zheng y Hu, y mostramos que la condición ya es suficiente para romper el RSA de Potencia Prima. Al introducir múltiples parámetros, nuestras construcciones de retículas aprovechan al máximo la información conocida y obtienen el mejor ataque conocido. Específicamente, hacemos pleno uso de la información de que es un divisor de , mientras que el ataque de Zheng y Hu solo asume que es un divisor de . Como consecuencia, este método implica una mejor construcción de retícula y, por lo tanto, mejora el ataque anterior. Los experimentos que alcanzan un límite superior mejor que antes también lo verifican. Nuestros enfoques se basan en el método de Coppersmith para encontrar raíces pequeñas de ecuaciones polinómicas modulares bivariadas.