Ist das Problem der ganzzahligen Faktorisierung schwieriger als die RSA-Faktorisierung:

Dies ist ein Cross-Post von math.stackexchange.

Lassen Sie FACT bezeichnen die ganze Zahl Faktorisierungsproblem: Da finden Primzahlen und ganze Zahlen so dass $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Es sei RSA der Spezialfall des Faktorisierungsproblems, bei dem und Primzahlen sind. Das heißt, wenn Primzahlen oder NONE gefunden werden, liegt keine solche Faktorisierung vor. $n = pq$ $p,q$ $n$ $p,q$

Natürlich ist RSA eine Instanz von FACT. Ist FACT schwieriger als RSA? Könnte ein Orakel, das RSA in Polynomzeit löst, verwendet werden, um FACT in Polynomzeit zu lösen?

(Ein Hinweis auf Literatur wird sehr geschätzt.)

Edit 1: Die Einschränkung der Rechenleistung wurde als Polynomialzeit hinzugefügt.

Bearbeiten 2: Wie in der Antwort von Dan Brumleve darauf hingewiesen, dass es Artikel gibt, die für und gegen RSA argumentieren, die schwieriger (oder einfacher als) FACT sind. Bisher habe ich folgende Papiere gefunden:

D. Boneh und R. Venkatesan. RSA zu brechen kann einfacher sein als Factoring. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: RSA zu brechen kann genauso schwierig sein wie Factoring. Kryptologie ePrint-Archiv, Bericht 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander und A. Rupp. Zur Äquivalenz von RSA und Faktorisierung in Bezug auf generische Ringalgorithmen. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal und U. Maurer. RSA generisch zu brechen ist gleichbedeutend mit Factoring. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Ich muss sie durchgehen und eine Schlussfolgerung ziehen. Ist jemandem bekannt, dass diese Ergebnisse eine Zusammenfassung liefern können?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Gemeinschaft
quelle

Wenn ich mich richtig erinnere, dann ist das Berechnen von

oder das Herausfinden von d gleichbedeutend mit Factoring, aber als solches könnte es eine Möglichkeit geben, dass RSA schwächer ist als Factoring. Kurz gesagt, bedeutet RSA möglicherweise nicht, das Factoring-Problem zu lösen. Es sind keine formalen Beweise dafür bekannt, dass sie gleichwertig sind (soweit ich weiß)

ϕ (n)

$\phi(n)$

singhsumit

Mohammad, warum ist FACT nicht auf RSA reduzierbar?

Dan Brumleve

Vielleicht verstehe ich etwas Grundlegendes falsch. Wie lässt sich zeigen, dass die Existenz eines Algorithmus zur Faktorisierung eines Semiprimes in der Polynomzeit nicht die Existenz eines Algorithmus zur Faktorisierung einer Zahl mit drei Primfaktoren in der Polynomzeit impliziert?

Dan Brumleve

Woher weißt du, dass es das ist, worauf es ankommt?

Dan Brumleve

Wenn es keine Poly-Time-Reduktion zwischen den beiden genannten Problemen gibt, wird es schwierig sein, dies zu zeigen, oder? Um zu beweisen, dass keine Polyzeitreduktion existieren kann, müssen wir

beweisen .

P \neq N P

$P\neq NP$

Fixee

Antworten:

Ich fand dieses Papier mit dem Titel RSA brechen ist möglicherweise einfacher als Factoring . Sie argumentieren , dass die Berechnung te Wurzeln modulo könnte einfacher sein , als factoring . $e$ $n=pq$ $n=pq$

Sie beschäftigen sich jedoch nicht mit der Frage, die Sie gestellt haben: Sie berücksichtigen nicht, ob die Faktorisierung von Ganzzahlen der Form einfacher sein könnte als die Faktorisierung von beliebigen Ganzzahlen. Infolgedessen ist diese Antwort für Ihre spezielle Frage so gut wie irrelevant. $n=pq$

Dan Brumleve
quelle

Vielen Dank! Ich fand mehrere andere Artikel mit verwandten Titeln, Querverweisen. Ich werde unten Links posten. (Bearbeiten: Links unten sind hässlich. Ich kann keine korrekte Formatierung in Kommentaren bekommen.)

D. Boneh und R. Venkatesan. RSA zu brechen kann einfacher sein als Factoring. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: RSA zu brechen kann genauso schwierig sein wie Factoring. Kryptologie ePrint-Archiv, Bericht 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal und U. Maurer. RSA generisch zu brechen ist gleichbedeutend mit Factoring. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander und A. Rupp. Zur Äquivalenz von RSA und Faktorisierung in Bezug auf generische Ringalgorithmen. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

Ich habe die Zusammenfassungen gelesen, und in der Arbeit von Aggarwal und Maurer scheint es sich um ein etwas anderes Problem zu handeln (Berücksichtigung von Semiprime vs. Berechnung der Phi-Funktion?). Die anderen sagen ausdrücklich, dass das Problem offen ist. Ich nehme an, es ist immer noch so, es sei denn, es gibt ein Ergebnis, das jünger als 2006 ist.

Dan Brumleve

Es ist wahrscheinlich erwähnenswert, dass sich das Boneh- und Venkatesan-Papier mit der Härte der Faktorisierung von Semiprimes im Vergleich zur Härte des RSA-Bruchs befasst. Was die Frage "RSA" nennt, ist in der Tat das Problem des Faktorierens von Semiprimes, was schwieriger sein kann als das Brechen von RSA (was das Boneh-Venkatesan-Papier vorschlägt)

Sasho Nikolov,

Diese Antwort ist nicht richtig. Sie haben falsch verstanden, was diese Papiere beweisen. Mit "RSA-Problem" ist das Problem gemeint, eine modulare

te Wurzel (mod

) zu berechnen und dies mit der Schwierigkeit in Verbindung zu bringen,

faktorisieren . In beiden Fällen ist

eine RSA-Zahl, dh

. Die von Ihnen zitierten Artikel befassen sich also nicht wirklich mit der Frage, die Sie gestellt haben. Die Verwirrung entsteht hier, weil das "RSA-Problem" der Frage nicht mit dem identisch ist, was diese Artikel als "das RSA-Problem" bezeichnen.

e

$e$

n

$n$

n

$n$

n

$n$

n = p q

$n=pq$

Ein effizienter Algorithmus zum Faktorisieren von Semiprimes (RSA) führt meines Erachtens nicht automatisch zu einem effizienten Algorithmus zum Faktorisieren von allgemeinen Ganzzahlen (FACT). In der Praxis sind Semiprimes jedoch die am schwierigsten zu berücksichtigenden ganzen Zahlen. Ein Grund dafür ist, dass die maximale Größe der kleinsten Primzahl von der Anzahl der Faktoren abhängt. Für eine ganze Zahl mit Primfaktoren beträgt die maximale Größe des kleinsten Primfaktors $N$ $f$ , und so gibt es (über denPrimzahlsatz) ungefähr $\lfloor N^\frac{1}{f} \rfloor$ Möglichkeiten dafür. Somitverringert eineErhöhung vondie Anzahl von Möglichkeiten für den kleinsten Primfaktor. Jeder Algorithmus, der diesen Wahrscheinlichkeitsraum sukzessive reduziert, funktioniert dann am besten für großesund am schlechtesten für. Dies wird in der Praxis bestätigt, da viele klassische Factoring-Algorithmen viel schneller sind, wenn die zu berücksichtigende Zahl mehr als zwei Primfaktoren enthält. $\frac{f N^\frac{1}{f}}{\log(N)}$ $f$ $f$ $f=2$

Weiterhin funktionieren das General Number Field Sieve , der schnellste bekannte klassische Faktorisierungsalgorithmus, und Shors Algorithmus , der polynomielle Zeitquantenfaktorisierungsalgorithmus, gleichermaßen gut für Nicht-Semiprimes. Im Allgemeinen scheint es viel wichtiger zu sein, dass die Faktoren von Coprime als dass sie Primzahlen sind.

Ich denke, ein Teil des Grundes dafür ist, dass die Entscheidungsversion des Faktorisierens von Co-Primzahlen am natürlichsten als ein Versprechensproblem beschrieben wird , und jede Möglichkeit, das Versprechen zu entfernen, dass die Eingabe semiprime ist, ist eine von beiden

eine Indizierung der Semiprimes einführen (was meiner Meinung nach genauso schwierig ist, wie sie zu faktorisieren), oder
durch Verallgemeinerung des Problems auf Nicht-Semiprimes.

$P\neq NP$ .

Abschließend sei darauf hingewiesen, dass RSA (das Kryptosystem, nicht das oben definierte Faktorisierungsproblem) trivial über Semi-Primzahlen hinaus verallgemeinert wird.

Joe Fitzsimons
quelle

Joe, ich denke, es wäre vernünftig anzunehmen, dass Factoring für diese Frage nicht in

(und daher

) steht (und die Antwort dann kein Ergebnis einer durchbrechenden Komplexität impliziert, wie Sie im letzten Absatz angegeben haben).

P

$P$

P \neq N P

$P \neq NP$

Kaveh

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}$ durch Aufzeigen eines polynomialen Zeitalgorithmus für RSA und Verwendung der Annahme über die Komplexität von FACT.

Joe Fitzsimons

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

Keine vollständige Antwort, scheint aber eine Verbesserung zu sein:

In den oben zitierten Forschungsarbeiten wird das Problem der Berechnung von eth roots mod N, dh der Ausführung der privaten Schlüsseloperation im RSA-Kryptosystem, mit dem Problem des Factorings, dh der Ermittlung des privaten Schlüssels, in beiden Fällen nur unter Verwendung des öffentlichen Schlüssels verglichen. In diesem Fall ist das Factoring-Problem nicht der allgemeine Fall, sondern der Semiprime-Fall. Mit anderen Worten, sie überlegen sich eine andere Frage.

Ich glaube, dass es bekannt ist, siehe Knuths AoCP, dass die meisten Zahlen N Primfaktoren haben, deren Bitlänge mit der von N verglichen wird, im Durchschnitt etwa 1/2, 1/4, 1/8, ..., oder vielleicht sogar stärker abfallen, wie in 2/3, 2/9, 2/27, ... aber vielleicht abflachen. Für allgemeine Zufallszahlen N mit einer Größe, die so klein ist, dass erwartet werden kann, dass die kleineren Faktoren durch die Testdivision oder durch Lenstra's ECM schnell gefunden werden, kann es sich also um Semiprime handeln, wenn auch um ein unausgeglichenes. Dies ist eine Art von Reduktion, hängt jedoch stark von der Verteilung der Faktoren ab, und es ist eine langsame Reduktion, da andere Faktorisierungsalgorithmen aufgerufen werden.

Es ist auch kein Test bekannt, um festzustellen, ob eine Zahl semiprime ist oder nicht. Dies bedeutet nur, dass man ein unbekanntes Problem gelöst hat, wenn man gerade einen Semiprime-Faktorisierungsalgorithmus auf eine allgemeine Zahl angewendet hat und dieser immer fehlgeschlagen ist.

user18217
quelle

Der Faktorisierungsalgorithmus müsste jedoch in Polynomzeit ablaufen. Sie sagen also wirklich: "Wenn Sie einen Algorithmus zur Faktorisierung in mehreren Zeiten hätten, hätten Sie ein unbekanntes Problem gelöst." Weil man mit dem naiven Faktorisierungsalgorithmus herausfinden kann, ob eine Zahl ein Semiprime ist oder nicht.

Elliot Gorokhovsky