Czy problem faktoryzacji liczb całkowitych jest trudniejszy niż faktoryzacja RSA:

To jest cross-post z math.stackexchange.

Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych a całkowite tak, że $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Niech RSA oznacza szczególny przypadek problemu faktoringowego, w którym i są liczbami pierwszymi. To znaczy, biorąc pod uwagę znaleźć liczby pierwsze lub NONE, jeśli nie ma takiego podziału na czynniki. $n = pq$ $p,q$ $n$ $p,q$

Oczywiście RSA jest instancją FACT. Czy FACT jest trudniejszy niż RSA? Biorąc pod uwagę wyrocznię, która rozwiązuje RSA w czasie wielomianowym, czy można go użyć do rozwiązania FAKTU w czasie wielomianowym?

(Wskaźnik do literatury jest bardzo ceniony).

Edycja 1: Dodano ograniczenie mocy obliczeniowej jako czasu wielomianu.

Edycja 2: Jak wskazano w odpowiedzi Dana Brumleve'a, że istnieją dokumenty argumentujące za i przeciw RSA trudniejsze (lub łatwiejsze niż) FAKT. Do tej pory znalazłem następujące dokumenty:

D. Boneh i R. Venkatesan. Złamanie RSA może być łatwiejsze niż faktoring. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Złamanie RSA może być tak samo trudne jak faktoring. Archiwum ePrint w dziedzinie kryptologii, raport 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander i A. Rupp. O równoważności RSA i faktoringu w odniesieniu do ogólnych algorytmów pierścieniowych. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal i U. Maurer. Przełamanie RSA jest ogólnie równoważne faktoringowi. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Muszę je przejrzeć i znaleźć konkluzję. Czy ktoś wie o tych wynikach, może przedstawić streszczenie?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Społeczność
źródło

ϕ (n)

$\phi(n)$

Mohammad, dlaczego FACT nie można zredukować do RSA?

Dan Brumleve

Może nie rozumiem czegoś podstawowego. Jak wykazać, że istnienie algorytmu do obliczenia wartości półpierwszej w czasie wielomianowym nie oznacza istnienia algorytmu do uwzględnienia liczby z trzema podstawowymi czynnikami w czasie wielomianowym?

Dan Brumleve

Skąd wiesz, że to jest to, co to oznacza?

Dan Brumleve

P \neq N P

$P\neq NP$

Odpowiedzi:

$e$ $n=pq$ $n=pq$

$n=pq$

Dan Brumleve
źródło

Dzięki! Znalazłem kilka innych artykułów z powiązanymi tytułami i odsyłaczami. Zamieszczę poniższe linki. (Edytuj: poniższe linki są brzydkie. Nie mogę uzyskać odpowiedniego formatowania w komentarzach.)

D. Boneh i R. Venkatesan. Złamanie RSA może być łatwiejsze niż faktoring. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Złamanie RSA może być tak samo trudne jak faktoring. Cryptology ePrint Archive, Report 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal i U. Maurer. Przełamanie RSA jest ogólnie równoważne faktoringowi. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander i A. Rupp. O równoważności RSA i faktoringu w odniesieniu do ogólnych algorytmów pierścieniowych. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Czytam abstrakty, a praca Aggarwal i Maurer wydaje się dotyczyć nieco innego problemu (faktoryzacja semiprime vs. obliczenie funkcji phi?) Inni twierdzą wyraźnie, że problem jest otwarty. Przypuszczam, że nadal tak jest, chyba że wynik jest nowszy niż 2006?

Dan Brumleve

Prawdopodobnie warto wspomnieć, że w pracy Boneh i Venkatesan chodzi o twardość faktorowania semiprime w porównaniu z twardością łamania RSA. To, co pytanie nazywa „RSA”, jest w rzeczywistości problemem faktorowania półpierwszych, które może być trudniejsze niż łamanie RSA (co sugeruje artykuł 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$

Co więcej, ogólne sito pola liczbowego , najszybszy znany klasyczny algorytm faktorowania, oraz algorytm Shora, algorytm faktorowania kwantowego z czasem wielomianowym, działają równie dobrze w przypadku elementów innych niż półpierwsze. Ogólnie rzecz biorąc, wydaje się o wiele bardziej istotne, że czynniki według względnie pierwsze niż one być pierwsza.

Wydaje mi się, że częściowo dlatego, że wersja decyzyjna fakturowania współpierwszych jest najbardziej naturalnie opisana jako problem obiecujący , a każdy sposób na usunięcie obietnicy, że dane wejściowe są półpierwsze, to albo

wprowadzić indeksowanie semiprime (które, jak podejrzewam, jest tak samo trudne jak faktoring), lub
przez uogólnienie problemu tak, aby obejmował elementy inne niż częściowe.

$P\neq NP$

Na koniec warto zauważyć, że RSA (kryptosystem, a nie zdefiniowany powyżej problem faktoringu) w sposób trywialny uogólnia poza półpierwsze.

Joe Fitzsimons
źródło

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

Nie do końca pełna odpowiedź, ale wydaje się być poprawą:

Cytowane powyżej artykuły badawcze porównują problem obliczania korzeni et mod mod N, tj. Wykonywania operacji na kluczu prywatnym w kryptosystemie RSA, z problemem faktoringu, tj. Znalezienia klucza prywatnego, w obu przypadkach przy użyciu tylko klucza publicznego. W tym przypadku problemem faktoringu nie jest przypadek ogólny, ale przypadek semiprime. Innymi słowy, zastanawiają się nad innym pytaniem.

Wierzę, że wiadomo, patrz AoCP Knutha, że większość liczb N ma czynniki pierwsze, których długości bitów są porównywalne pod względem długości do długości N, średnio około 1/2, 1/4, 1/8, ..., a może nawet bardziej gwałtownie spadają, jak w 2/3, 2/9, 2/27, ... ale może się spłaszczają. Tak więc, dla ogólnego losowego N o rozmiarze wystarczająco małym, aby można było oczekiwać, że mniejsze czynniki zostaną szybko znalezione przez podział próbny lub ECM Lenstry, wówczas to, co pozostaje, może być półpierwszym, choć niezrównoważonym. Jest to rodzaj redukcji, ale w dużym stopniu zależy od rozkładu czynników i jest powolną redukcją, ponieważ wywołuje inne algorytmy faktoryzacji.

Ponadto nie jest znany test pozwalający ustalić, czy liczba jest półpierwsza, czy nie. Oznacza to tylko, że jeśli zastosuje się algorytm faktoryzacji semiprime do ogólnej liczby i zawsze się to nie powiedzie, wówczas rozwiązany zostanie nieznany problem.

użytkownik18217
źródło

Algorytm faktoryzacji musiałby jednak działać w czasie wielomianowym. Naprawdę mówisz: „gdybyś miał algorytm wieloczynnikowy obliczania czasu, rozwiązałbyś nieznany problem”. Ponieważ można użyć naiwnego algorytmu faktoryzacji, aby dowiedzieć się, czy liczba jest semiprime, czy nie.

Elliot Gorokhovsky