O problema da fatoração inteira é mais difícil que a fatoração RSA: ?

Esta é uma postagem cruzada de math.stackexchange.

Deixe FACT denotar o problema de fatoração de número inteiro: dado encontre os números primos e os números inteiros 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}.$

Let RSA denotar o caso especial de problema factoring onde e são números primos. Ou seja, dado encontre primos ou NONE se não houver essa fatoração. $n = pq$ $p,q$ $n$ $p,q$

Claramente, o RSA é uma instância do FACT. FACT é mais difícil que o RSA? Dado um oráculo que resolve a RSA em tempo polinomial, ele poderia ser usado para resolver o FACT em tempo polinomial?

(Um indicador da literatura é muito apreciado.)

Edit 1: Adicionada a restrição de poder computacional ao tempo polinomial.

Edit 2: Como apontado na resposta de Dan Brumleve, existem documentos discutindo a favor e contra a RSA com mais (ou mais fácil que) FATO. Encontrei os seguintes documentos até agora:

D. Boneh e R. Venkatesan. Quebrar a RSA pode ser mais fácil do que fatorar. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Quebrar a RSA pode ser tão difícil quanto fatorar. Cryptology ePrint Archive, Relatório 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander e A. Rupp. Sobre a equivalência de RSA e fatoração em relação a algoritmos genéricos de anel. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal e U. Maurer. Quebrar o RSA genericamente é equivalente ao fatoramento. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Eu tenho que passar por eles e encontrar uma conclusão. Alguém ciente desses resultados pode fornecer um resumo?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Comunidade
fonte

se bem me lembro, calcular ou descobrir d equivale a fatorar, mas, como tal, pode haver alguma maneira de o RSA ser mais fraco que o fatorar. Resumindo, a RSA pode não implicar na solução do problema de fatoração. Não há provas formais conhecidos para eles sendo equivalente (tanto quanto eu sei).

ϕ (n)

$\phi(n)$

singhsumit

Mohammad, por que o FACT não é redutível à RSA?

Dan Brumleve

Talvez eu esteja entendendo mal algo básico. Como mostrar que a existência de um algoritmo para fatorar um semiprime no tempo polinomial não implica a existência de um algoritmo para fatorar um número com três fatores primos no tempo polinomial?

Dan Brumleve

Como você sabe que isso é o que significa?

Dan Brumleve

Se não houver redução de tempo poli entre os dois problemas declarados, será difícil mostrar isso, certo? Para provar que nenhuma redução de tempo poli pode existir, é necessário provar .

P \neq N P

$P\neq NP$

Fixee

Respostas:

Encontrei este artigo intitulado Quebrar a RSA pode ser mais fácil do que fatorar . Eles argumentam que a computação th raízes módulo pode ser mais fácil do que factoring . $e$ $n=pq$ $n=pq$

No entanto, eles não abordam a pergunta que você fez: não consideram se fatorar números inteiros no formato pode ser mais fácil do que fatorar números inteiros arbitrários. Como resultado, essa resposta é praticamente irrelevante para sua pergunta em particular. $n=pq$

Dan Brumleve
fonte

Obrigado! Encontrei vários outros trabalhos com títulos relacionados, referências cruzadas. Vou postar os links abaixo. (Editar: links abaixo são feios eu não posso começar a formatação adequada nos comentários..)

D. Boneh e R. Venkatesan. Quebrar a RSA pode ser mais fácil do que fatorar. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Quebrar a RSA pode ser tão difícil quanto fatorar. Cryptology ePrint Archive, Relatório 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal e U. Maurer. Quebrar o RSA genericamente é equivalente ao fatoramento. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander e A. Rupp. Sobre a equivalência de RSA e fatoração em relação a algoritmos genéricos de anel. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Li os resumos e o artigo de Aggarwal e Maurer parece tratar-se de um problema ligeiramente diferente (fatorar um semiprime versus calcular a função phi?). Os outros dizem explicitamente que o problema está aberto. Suponho que ainda seja, a menos que haja um resultado mais recente que 2006?

Dan Brumleve 28/05

Provavelmente vale a pena mencionar que o artigo de Boneh e Venkatesan trata da dureza de fatorar semiprimes versus a dureza de quebrar a RSA. O que a questão chama de "RSA" é na verdade o problema de número semiprimo factoring, que pode ser mais difícil do que quebrar RSA (que é o que o papel Boneh-Venkatesan sugere)

Sasho Nikolov

Esta resposta não está correta. Você entendeu mal o que esses documentos estão provando. Por "problema RSA", que significa que o problema de computar uma modular th raiz (mod ), e relacionar isso com a dificuldade de factoring . Nos dois casos, é um número RSA, ou seja, . Portanto, os documentos que você cita não estão realmente abordando a pergunta que você fez. A confusão aqui vem porque o "problema da RSA" da questão não é o mesmo que aqueles documentos se referem como "o problema da RSA".

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$

Além disso, o General Number Field Sieve , o algoritmo de fatoração clássico mais rápido conhecido, e o algoritmo de Shor , o algoritmo de fatoração quântica de tempo polinomial, funcionam igualmente bem para os não-semiprimes. Em geral, parece muito mais importante que os fatores por coprime do que sejam primos.

Acho que parte da razão para isso é que a versão de decisão dos fatores primos de fatoração é mais naturalmente descrita como um problema de promessa , e qualquer maneira de remover a promessa da entrada como semiprime é

introduzir uma indexação nos semiprimes (que, por si só, suspeito é tão difícil quanto fatorá-los), ou
generalizando o problema para incluir não-semiprimes.

$P\neq NP$

Por fim, vale ressaltar que o RSA (o sistema de criptografia, não o problema de fatoração que você definiu acima) generaliza trivialmente além dos semim Primos.

Joe Fitzsimons
fonte

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}$

Não é uma resposta completa, mas parece ser uma melhoria:

Os trabalhos de pesquisa citados acima comparam o problema de calcular o método de raízes N, isto é, fazer a operação de chave privada no sistema de criptografia RSA, com o problema de fatorar, ou seja, encontrar a chave privada, em ambos os casos, usando apenas a chave pública. Nesse caso, o problema de fatoração não é o caso geral, mas o semiprime. Em outras palavras, eles estão considerando uma pergunta diferente.

Acredito que se sabe, veja AoCP de Knuth, que a maioria dos números N tem fatorações primárias cujos comprimentos de bits se comparam em comprimento de bits aos de N, em média algo como 1/2, 1/4, 1/8, ..., ou talvez até cair mais bruscamente, como em 2/3, 2/9, 2/27, ... mas talvez achatando. Assim, para N aleatório geral de tamanho pequeno o suficiente para que os fatores menores possam ser encontrados rapidamente pela divisão de teste ou pelo ECM de Lenstra, o que resta pode ser um semiprime, embora desequilibrado. Esse é um tipo de redução, mas depende muito da distribuição de fatores e é uma redução lenta, na medida em que invoca outros algoritmos de fatoração.

Além disso, não há um teste conhecido para determinar se um número é semiprime ou não. Isso significa apenas que, se alguém aplicou um algoritmo de fatoração semiprime a um número geral e sempre falhou, resolveu um problema desconhecido.

user18217
fonte

O algoritmo de fatoração teria que ser executado em tempo polinomial, no entanto. Então, na verdade, você está dizendo "se você tivesse um algoritmo de fatoração de politempo, teria resolvido um problema desconhecido". Porque é possível usar o algoritmo de fatoração ingênuo para descobrir se um número é semiprime ou não.

Elliot Gorokhovsky 29/03