0 Daumen
829 Aufrufe

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

von

2 Antworten

+1 Daumen

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

von

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."

+1 Daumen

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.

von

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...

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community