RSA-Angriff n faktorisieren

02.08.2022, 21:21

_Bastii

RSA-Angriff n faktorisieren

Hallo,

in einer Aufgabe ist die Frage, ob ich das RSA-Modul $\begin{eqnarray*} n = 2759 \end{eqnarray*}$ aus dem öffentlichen Schlüssel faktorisieren kann, wenn mir $\begin{eqnarray*} \varphi(n) = 2640 \end{eqnarray*}$ bekannt ist.

Ich weiß das $\begin{eqnarray*} \varphi(n) = (p-1) \cdot (q-1) \end{eqnarray*}$ .
Meine Idee wäre jetzt $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ zu faktorisieren um $\begin{eqnarray*} (p-1) \cdot (q-1) \end{eqnarray*}$ herauszubekommen und dann $\begin{eqnarray*} n \end{eqnarray*}$ zu berechnen mit $\begin{eqnarray*} n = ((p-1)+1) \cdot ((q-1)+1) \end{eqnarray*}$ .

Das faktorisieren hat soweit auch geklappt:

$\begin{eqnarray*} \varphi(n) = 2640 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 11 = 2^4 \cdot 3 \cdot 5 \cdot 11 \end{eqnarray*}$

Nun weiß ich aber nicht, wie ich diese Faktorisierung sinnvoll aufteile um die beiden Primzahlen $\begin{eqnarray*} p, q \end{eqnarray*}$ zu erhalten. Habt ihr Tipps für mich?

02.08.2022, 21:43

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} n-\varphi (n) =pq-pq+p+q-1 \end{eqnarray*}$

02.08.2022, 22:49

systemshock

Auf diesen Beitrag antworten »

$\begin{eqnarray*} p \cdot q = 2759 \end{eqnarray*}$

$\begin{eqnarray*} (p-1)(q-1)=2640 \end{eqnarray*}$

2 Gleichungen und 2 Unbekannte.
Das sollte mit einer quadratischen Gleichung machbar sein.

Hinweis: Die zweite Gleichung lässt sich zu mit pq=2759 zu p+q=120 umformen oder du subtrahierst die Gleichungen voneinander

03.08.2022, 08:26

HAL 9000

Auf diesen Beitrag antworten »

So ist es - man bekommt via

$\begin{eqnarray*} pq = n \end{eqnarray*}$
$\begin{eqnarray*} p+q = n-\varphi(n)+1 \end{eqnarray*}$

gemäß Víeta, dass $\begin{eqnarray*} p,q \end{eqnarray*}$ die beiden Lösungen der quadratischen Gleichung $\begin{eqnarray*} x^2 - (n-\varphi(n)+1)x + n = 0 \end{eqnarray*}$ sind; im vorliegenden Beispiel ist das die Gleichung $\begin{eqnarray*} x^2-120x+2759=0 \end{eqnarray*}$ .

03.08.2022, 13:06

Elvis

Auf diesen Beitrag antworten »

Aus $\begin{eqnarray*} p+q=n-\varphi(n)+1=120 \end{eqnarray*}$ und wegen $\begin{eqnarray*} 20\cdot 100<n=2759\approx 30\cdot90<40\cdot 80 \end{eqnarray*}$ kann man ganz schnell auf $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} q \end{eqnarray*}$ schließen.

03.08.2022, 13:21

HAL 9000

Auf diesen Beitrag antworten »

Naja, das Beispiel soll ja wohl eher exemplarisch für größere Primzahlen stehen, wo man mit probieren dann schon etwas länger braucht, beispielsweise

$\begin{eqnarray*} n = 20389424557990665288622710584030660045807819854215049373548751 \end{eqnarray*}$
$\begin{eqnarray*} \varphi(n) = 20389424557990665288622710584021623202068436512760919360536712 \end{eqnarray*}$ .

EDIT: Jetzt habe ich wohl leider die maximale Zeilenlänge des Matheboards für Zahlen gesprengt. Ging aber nicht anders - deutlich kürzere $\begin{eqnarray*} n \end{eqnarray*}$ konnte das CAS noch ziemlich mühelos faktorisieren. Augenzwinkern

EDIT2: Hat sich dank Hinweis von IfindU erledigt.

03.08.2022, 14:21

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Naja, das Beispiel soll ja wohl eher exemplarisch für größere Primzahlen stehen, wo man mit probieren dann schon etwas länger braucht, beispielsweise

$\begin{eqnarray*} n = 20389424557990665288622710584030660045807819854215049373548751 \end{eqnarray*}$
$\begin{eqnarray*} \varphi(n)=20389424557990665288622710584021623202068436512760919360536<br /> 712 \end{eqnarray*}$ .

EDIT: Jetzt habe ich wohl leider die maximale Zeilenlänge des Matheboards für Zahlen gesprengt. Ging aber nicht anders - deutlich kürzere $\begin{eqnarray*} n \end{eqnarray*}$ konnte das CAS noch ziemlich mühelos faktorisieren. Augenzwinkern

Interessanter funktioniert es, wenn man ein Leerzeichen beim Gleichheitszeichen macht:
$\begin{eqnarray*} \varphi(n)= 20389424557990665288622710584021623202068436512760919360536712 \end{eqnarray*}$
Das funktioniert auch mit Pausen in den Zahlen:
$\begin{eqnarray*} \varphi(n)= 203894245579906652886227105840216232020684365127609193605367129999999999999<br /> 99 \end{eqnarray*}$
vs.
$\begin{eqnarray*} \varphi(n)= 20389424557990665288622710584021623202068436512760919360536712 999999999999999 \end{eqnarray*}$ .

Offenbar gibt es eine Zwangsumbrechung, wenn ein Wort zu lang wird.

03.08.2022, 14:49

HAL 9000

Auf diesen Beitrag antworten »

Ah verdammt, bei "n = " hatte ich noch Leerzeichen gemacht ... Danke für den Hinweis, werde ich nachbessern.

03.08.2022, 15:12

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
deutlich kürzere $\begin{eqnarray*} n \end{eqnarray*}$ konnte das CAS noch ziemlich mühelos faktorisieren. Augenzwinkern

Da wollte ich aus Spaß und Tollerei doch mal sehen, wie lange mein altersschwacher Rechner braucht:

[attach]55718[/attach]

Gut 2 Minuten geht noch so. Viel mehr Stellen hätte $\begin{eqnarray*} n \end{eqnarray*}$ nicht haben dürfen.

03.08.2022, 15:15

HAL 9000

Auf diesen Beitrag antworten »

Ja, ich hatte es so gewählt, dass es durchaus möglich ist, aber man eben schon etwas Geduld aufbringen muss. Augenzwinkern

P.S.: Jedenfalls scheint Wolframs "FactorInteger" deutlich besser programmiert zu sein als Matlab-MuPads "ifactor", denn auf meinem zwar ebenfalls betagten, aber zum Kaufzeitpunkt 2015 doch recht fixen i7 4790K habe ich die Rechnung nach 15 Minuten abgebrochen - ohne Ergebnis. Dagegen hat es PARI/GP in beeindruckenden 10 Sekunden geschafft. geschockt

Neue Frage »

Antworten »

RSA-Angriff n faktorisieren

Verwandte Themen