¿Es el problema de factorización de enteros más difícil que la factorización de RSA: ?

Esta es una publicación cruzada de math.stackexchange.

Deje que FACT denote el problema de factorización de enteros: dado encuentre los primos y los enteros modo que $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Supongamos que RSA denota el caso especial de problema de factorización donde y son números primos. Es decir, dado encontrar primos o NINGUNO si no existe tal factorización. $n = pq$ $p,q$ $n$ $p,q$

Claramente, RSA es una instancia de FACT. ¿Es FACT más difícil que RSA? Dado un oráculo que resuelve RSA en tiempo polinómico, ¿podría usarse para resolver FACT en tiempo polinómico?

(Un puntero a la literatura es muy apreciado).

Edición 1: se agregó la restricción en el poder computacional para que sea tiempo polinómico.

Edición 2: Como se señala en la respuesta de Dan Brumleve, hay documentos que argumentan a favor y en contra de RSA más difícil (o más fácil que) HECHO. Encontré los siguientes documentos hasta ahora:

D. Boneh y R. Venkatesan. Romper RSA puede ser más fácil que factorizar. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Romper RSA puede ser tan difícil como factorizar. Criptología ePrint Archive, Informe 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander y A. Rupp. Sobre la equivalencia de RSA y factoring con respecto a algoritmos de anillo genérico. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal y U. Maurer. Romper RSA genéricamente es equivalente a factorizar. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Tengo que revisarlos y encontrar una conclusión. ¿Alguien conoce estos resultados y puede proporcionar un resumen?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Comunidad
fuente

si no recuerdo mal, calcular o descubrir d es equivalente a factorizar, pero como tal podría haber alguna forma de que RSA sea más débil que factorizar. En resumen, RSA puede no implicar resolver el problema de factorización. No se conocen pruebas formales de que sean equivalentes (hasta donde yo sé)

ϕ (n)

$\phi(n)$

singhsumit

Mohammad, ¿por qué FACT no es reducible a RSA?

Dan Brumleve

Tal vez estoy malinterpretando algo básico. ¿Cómo demostrar que la existencia de un algoritmo para factorizar un semiprime en tiempo polinómico no implica la existencia de un algoritmo para factorizar un número con tres factores primos en tiempo polinomial?

Dan Brumleve

¿Cómo sabes que eso es lo que equivale?

Dan Brumleve

Si no hay una reducción del tiempo múltiple entre los dos problemas establecidos, entonces será difícil mostrar esto, ¿verdad? Para probar que no puede existir una reducción de poli-tiempo se requiere que demostremos .

P \neq N P

$P\neq NP$

Fixee

Respuestas:

Encontré este documento titulado Romper RSA puede ser más fácil que factorizar . Argumentan que calcular el módulo de raíces podría ser más fácil que factorizar . $e$ $n=pq$ $n=pq$

Sin embargo, no abordan la pregunta que usted hizo: no consideran si factorizar enteros de la forma podría ser más fácil que factorizar enteros arbitrarios. Como resultado, esta respuesta es prácticamente irrelevante para su pregunta particular. $n=pq$

Dan Brumleve
fuente

¡Gracias! Encontré varios otros artículos con títulos relacionados, referencias cruzadas. Publicaré enlaces a continuación. (Edición: enlaces inferiores son feos no puedo obtener el formato correcto en los comentarios..)

D. Boneh y R. Venkatesan. Romper RSA puede ser más fácil que factorizar. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Romper el RSA puede ser tan difícil como factorizar. Cryptology ePrint Archive, Report 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal y U. Maurer. Romper RSA genéricamente es equivalente a factorizar. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander y A. Rupp. Sobre la equivalencia de RSA y factoring con respecto a algoritmos de anillo genérico. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Leí los resúmenes, y el artículo de Aggarwal y Maurer parece ser sobre un problema ligeramente diferente (¿factorizar un semiprime versus calcular la función phi?) Los otros dicen explícitamente que el problema está abierto. ¿Supongo que todavía lo es a menos que haya un resultado más reciente que 2006?

Dan Brumleve

Probablemente vale la pena mencionar que el artículo de Boneh y Venkatesan trata sobre la dureza de factorizar semiprimes frente a la dureza de romper RSA. Lo que la pregunta llama "RSA" es, de hecho, el problema de factorizar semiprimes, que puede ser más difícil que romper RSA (que es lo que sugiere el artículo de Boneh-Venkatesan)

Sasho Nikolov

e

$e$

n

$n$

n

$n$

n

$n$

n = p q

$n=pq$

$N$ $f$ $\lfloor N^\frac{1}{f} \rfloor$ $\frac{f N^\frac{1}{f}}{\log(N)}$ $f$ $f$ $f=2$

Además, el Tamiz de campo de número general , el algoritmo de factorización clásico más rápido conocido, y el algoritmo de Shor , el algoritmo de factorización cuántica de tiempo polinómico, funcionan igualmente bien para no semiprimes. En general, parece mucho más importante que los factores coprimos sean primos.

Creo que parte de la razón de esto es que la versión de decisión de factorizar co-primos se describe más naturalmente como un problema prometedor , y cualquier forma de eliminar la promesa de que la entrada es semiprime es

introducir una indexación en los semiprimes (que en sí mismo sospecho es tan difícil como factorizarlos), o
generalizando el problema para incluir no semiprimes.

$P\neq NP$

Por último, vale la pena señalar que RSA (el criptosistema, no el problema de factorización que definió anteriormente) generaliza trivialmente más allá de los semi-primos.

Joe Fitzsimons
fuente

P

$P$

P \neq N P

$P \neq NP$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} \neq P^{F A C T}

$P^{RSA} \neq P^{FACT}$

F A C T \in P^{R S A} ?

$FACT \in P^{RSA}?$

F A C T \in P

$FACT \in P$

F A C T \notin P

$FACT \notin P$

F A C T \in P^{R S A}

$FACT \in P^{RSA}$

No es una respuesta completa, pero parece ser una mejora:

Los trabajos de investigación citados anteriormente comparan el problema de calcular las raíces éticas mod N, es decir, realizar la operación de clave privada en el criptosistema RSA, con el problema de factorizar, es decir, encontrar la clave privada, en ambos casos, utilizando solo la clave pública. En este caso, el problema de factorización no es el caso general, sino el caso de semiprime. En otras palabras, están considerando una pregunta diferente.

Creo que se sabe, vea el AoCP de Knuth, que la mayoría de los números N tienen factorizaciones primas cuyas longitudes de bits se comparan en longitud de bits con la de N, en promedio algo así como 1/2, 1/4, 1/8, ..., o tal vez incluso cayendo más bruscamente, como en 2/3, 2/9, 2/27, ... pero tal vez aplanándose. Entonces, para un N aleatorio general de tamaño lo suficientemente pequeño como para que los factores más pequeños se puedan encontrar rápidamente por la división de prueba o el ECM de Lenstra, entonces lo que queda puede ser un semiprime, aunque no equilibrado. Este es un tipo de reducción, pero depende en gran medida de la distribución de factores, y es una reducción lenta, ya que invoca otros algoritmos de factorización.

Además, no existe una prueba conocida para determinar si un número es semiprime o no. Esto solo significa que si uno acaba de aplicar un algoritmo de factorización de semiprime a un número general, y siempre falla, entonces uno ha resuelto un problema desconocido.

usuario18217
fuente

Sin embargo, el algoritmo de factorización tendría que ejecutarse en tiempo polinómico. Entonces realmente estás diciendo "si tuvieras un algoritmo de factorización de poli-tiempo, habrías resuelto un problema desconocido". Porque uno puede usar el ingenuo algoritmo de factorización para averiguar si un número es un semiprime o no.

Elliot Gorokhovsky