RSA Verfahren: Phi(n) und n damit q und p bekannt

Question

Aufgabe:

Der Angreifer kennt beide n und  Φ(n). Zeige, dass der Angreifer effizient die Faktoren p und q berechnen kann.

Problem/Ansatz:

Ich weiss, dass Φ(n) =(p-1) (q-1).

Mein Ansatz wäre, dass jede natürliche Zahl n eine eindeutige Primfaktorzerlegung hat. Da man n kennt, kennt man somit auch die Zerlegung n=pq.

Ich glaube aber nicht, das das die richtige Lösung ist, den mit kommt sie zu einfach vor.

Danke schon mal für eure Hilfe

Answer 1

Ja, wenn man erstmal drauf gekommen ist, erscheint Vieles zu einfach. Ich glaube schon, dass das der richtige Ansatz ist.

Comments

danke für die schnelle Antwort. Ich würd des dann eben als Text ausformulieren weil richtig zeigen ist immer so ne Sache, weil da hätte ich gerade überhaupt keine Idee

---

Schreib doch: "Wenn n und Φ(n) bekannt sind, ergibt sich ein System von zwei Gleichungen mit zwei Unbekannten p und q, (1) Φ(n) =(p-1)·(q-1) und (2) n=pq das sich lösen lässt."

Answer 2

Hallo Klinei,

Nein, dein Ansatz ist leider falsch. Nur weil du n kennst, kennst du noch lange nicht seine PFZ. Das heißt du musst diese berechnen und das geht eben nicht effizient! Das ist ja gerade der Witz beim RSA Verfahren.

Ich habe diese Frage aber schonmal auf der Stacklounge beantwortet. Hier der Link:

https://www.stacklounge.de/3870/rsa-primzahlen-bestimmen

Edit: Rolands Idee mit dem Gleichungssystem ist auch richtig.

n=pq

phi(n)=(p-1)(q-1)

Wichtig ist nur, dass du beides kennen musst. n und phi(n). Ansonsten kann der Angriff (meist) nicht effizient durchgeführt werden.

Comments

Danke für die Antwort, die hat mir sehr weiter geholfen. Deshalb habe ich auch an meinem Ansatz gezweifelt das er richtig ist

---

Ich gebe dir mal ein +1 weil deine Antwort, richtig ist!

Der Ansatz mit n=p*q ist aber genau das interessante beim RSA-Verfahren, letztlich argumentiert man ja über die Komplexität...