Является ли проблема целочисленной факторизации сложнее, чем факторизация RSA: ?

Это кросс-пост от math.stackexchange.

Обозначим через FACT целочисленную задачу факторинга: для найдите простые числа и целые числа такие что $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Обозначим через RSA частный случай задачи факторинга, где и - простые числа. То есть, если дано найти простые числа или NONE, если такой факторизации нет. $n = pq$ $p,q$ $n$ $p,q$

Очевидно, что RSA является примером FACT. ФАКТ сложнее, чем RSA? Учитывая оракула, который решает RSA в полиномиальное время, можно ли его использовать для решения FACT в полиномиальное время?

(Указатель на литературу очень ценится.)

Редактировать 1: Добавлено ограничение вычислительной мощности для полиномиального времени.

Редактировать 2: Как указано в ответе Дэна Брамлева, что есть документы, спорящие за и против RSA более жесткий (или более легкий, чем) ФАКТ. До сих пор я нашел следующие документы:

Д. Бонех и Р. Венкатесан. Разорвать RSA может быть проще, чем факторинг. ЕВРОКРИПТ 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

Д. Браун: Взлом RSA может быть таким же сложным, как и факторинг. Cryptology ePrint Archive, Отчет 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

Г. Леандер и А. Рупп. Об эквивалентности RSA и факторинге в отношении общих кольцевых алгоритмов. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Д. Аггарвал и У. Маурер. Разрыв RSA в целом эквивалентен факторингу. ЕВРОКРИПТ 2009. http://eprint.iacr.org/2008/260.pdf

Я должен пройти их и найти заключение. Кто-нибудь в курсе этих результатов может предоставить резюме?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Сообщество
источник

если я правильно помню, то вычисление или обнаружение d эквивалентно факторингу, но как таковой, возможно, RSA слабее, чем факторинг. Короче говоря, решение RSA может не означать решение проблемы факторинга. Не известно никаких формальных доказательств их эквивалентности. (Насколько я знаю)

ϕ (n)

$\phi(n)$

singhsumit

Мохаммед, почему FACT не сводится к RSA?

Дэн Брумлев

Может быть, я неправильно понимаю что-то основное. Как показать, что существование алгоритма для факторизации полупростого числа за полиномиальное время не подразумевает существование алгоритма для факторизации числа с тремя простыми множителями за полиномиальное время?

Дэн Брумлев

Откуда ты знаешь, что это то, что это значит?

Дэн Брумлев

Если между двумя указанными проблемами не будет сокращения времени, то показать это будет сложно, верно? Чтобы доказать, что сокращение времени не может существовать, требуется доказать .

P \neq N P

$P\neq NP$

Фикси

Ответы:

Я нашел эту статью под названием « Взлом RSA может быть проще, чем факторинг» . Они утверждают, что вычисление -корней по модулю может быть проще, чем факторинг . $e$ $n=pq$ $n=pq$

Тем не менее, они не отвечают на вопрос, который вы задали: они не учитывают, проще ли разложить целые числа вида , чем разложить произвольные целые числа. В результате этот ответ в значительной степени не имеет отношения к вашему конкретному вопросу. $n=pq$

Дэн Брумлев
источник

Благодарность! Я нашел несколько других статей с соответствующими названиями, перекрестными ссылками. Я буду размещать ссылки ниже. (Изменить: ссылки ниже ужасны. Я не могу получить правильное форматирование в комментариях.)

Д. Бонех и Р. Венкатесан. Разорвать RSA может быть проще, чем факторинг. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf Д. Браун: Разорвать RSA может быть так же сложно, как факторинг. Cryptology ePrint Archive, Report 205/380 (2006) eprint.iacr.org/2005/380.pdf Д. Аггарвал и У. Маурер. Разрыв RSA в целом эквивалентен факторингу. ЕВРОКРИПТ 2009. eprint.iacr.org/2008/260.pdf Г. Леандер и А. Рупп. Об эквивалентности RSA и факторинге в отношении общих кольцевых алгоритмов. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Я читаю тезисы, и статья Аггарвала и Маурера, кажется, о слегка отличающейся проблеме (факторизации полупростой задачи по сравнению с вычислением функции фи?) Другие явно говорят, что проблема открыта. Я полагаю, что это все еще есть, если есть результат, более поздний, чем 2006?

Дэн Брамлев

Вероятно, стоит упомянуть, что статья Boneh и Venkatesan посвящена твердости факторизации полуэлементов по сравнению с трудностью разрушения RSA. То, что этот вопрос называет «RSA», на самом деле является проблемой факторизации полупримесов, что может быть сложнее, чем разрыв RSA (что и предлагает газета Boneh-Venkatesan)

Сашо Николов

Этот ответ не правильный. Вы неправильно поняли, что эти бумаги доказывают. Под «проблемой RSA» они понимают проблему вычисления модульного корня (mod ) и связывания его со сложностью факторизации . В обоих случаях является номером RSA, т.е. . Таким образом, документы, которые вы цитируете, на самом деле не касаются вопроса, который вы задали. Путаница здесь возникает из-за того, что вопрос «проблема RSA» не совпадает с тем, что эти документы называют «проблемой RSA».

e

$e$

n

$n$

n

$n$

n

$n$

n = p q

$n=pq$

Насколько я могу видеть, эффективный алгоритм для факторизации полупростых чисел (RSA) автоматически не переводится в эффективный алгоритм для факторизации общих целых чисел (FACT). Тем не менее, на практике, полупростые числа являются самыми сложными целыми числами. Одна из причин этого заключается в том, что максимальный размер наименьшего простого числа зависит от количества факторов. Для целого числа с простыми множителями максимальный размер наименьшего простого множителя равен , и поэтому (с помощью теоремы о простых числах ) существует приблизительно возможностей для этого. Таким образом, увеличение $N$ $f$ $\lfloor N^\frac{1}{f} \rfloor$ $\frac{f N^\frac{1}{f}}{\log(N)}$ $f$ уменьшает количество возможностей для наименьшего простого множителя. Любой алгоритм, который работает, последовательно уменьшая это пространство вероятностей, будет тогда работать лучше всего для большого и худшим для . Это подтверждается на практике, так как многие классические алгоритмы факторинга работают намного быстрее, когда факторизованное число имеет более 2 простых факторов. $f$ $f=2$

Кроме того, сито полевых чисел общего числа , самый известный из известных классических алгоритмов факторинга, и алгоритм Шора, алгоритм квантового факторинга за полиномиальное время, одинаково хорошо работают и для неполупростых чисел. В общем, кажется, что гораздо важнее, чтобы факторы взаимно просты, чем чтобы они были простыми.

Я думаю, что одна из причин этого заключается в том, что вариант решения о факторинге простых чисел наиболее естественно описывается как проблема обещания , и любой способ устранения обещания входного значения, являющегося полупростым, заключается в

ввести индексацию на полупростых числах (что само по себе, как я подозреваю, так же сложно, как их разложение), или
Обобщая проблему, включив непервичные числа.

Представляется вероятным, что в последнем случае наиболее эффективный алгоритм будет решать FACT, а также RSA, хотя у меня нет доказательств этого. Тем не менее, доказательств мало, чтобы требовать, так как если бы оракул RSA доказал, что это не может эффективно решить FACT, то это доказывает, что . $P\neq NP$

Наконец, стоит отметить, что RSA (криптосистема, а не проблема факторинга, которую вы определили выше) тривиально обобщает за пределы простых чисел.

Джо Фитцсимонс
источник

Джо, я думаю, что было бы разумно предположить, что факторинг не находится в (и, следовательно, ) для этого вопроса (и тогда ответ не будет означать результат сложности прорыва, как вы заявили в предыдущем абзаце).

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

Не совсем полный ответ, но, кажется, улучшение:

В цитированных выше исследовательских работах проблема вычисления этно-корней mod N, т. Е. Выполнения операции с закрытым ключом в криптосистеме RSA, сравнивается с проблемой факторинга, т. Е. Поиска секретного ключа, в обоих случаях с использованием только открытого ключа. В этом случае проблема факторинга является не общим, а полупростым случаем. Другими словами, они рассматривают другой вопрос.

Я полагаю, что известно, см. ACPCP Кнута, что большинство чисел N имеют простые разложения, длина битов которых сравнивается по длине в битах с длиной N, в среднем что-то типа 1/2, 1/4, 1/8, ..., или, возможно, даже более резко падают, как в 2/3, 2/9, 2/27, ... но, возможно, сглаживаются. Таким образом, для общего случайного N размера, достаточно малого, чтобы можно было ожидать, что меньшие факторы могут быть быстро найдены пробным делением или ECM Ленстры, тогда то, что остается, может быть полупростым, хотя и несбалансированным. Это своего рода сокращение, но оно сильно зависит от распределения факторов, и это медленное сокращение, так как оно вызывает другие алгоритмы факторизации.

Кроме того, не существует известного теста для определения, является ли число полупростым или нет. Это означает только то, что если кто-то только что применил алгоритм полупростой факторизации к общему числу, и он всегда терпел неудачу, то он решил неизвестную проблему.

user18217
источник

Однако алгоритм факторизации должен работать за полиномиальное время. Так что на самом деле вы говорите: «Если бы у вас был алгоритм факторизации с использованием многовременности, вы бы решили неизвестную проблему». Потому что можно использовать алгоритм наивной факторизации, чтобы выяснить, является ли число полупростым или нет.

Эллиот Гороховский