Unter http://www.rsasecurity.com/rsalabs/challenges/factor… werden große Zahlen vorgestellt, die man für hohes Preisgeld faktorisieren soll… RSA-576 (mit 174 Dezimalstellen) wurde z.B. bereits zerlegt. RSA-640 und viele andere warten noch darauf…
Was mich interessieren würde, ist wie diese großen Zahlen zustande gekommen sind.
Es ist ja bekannt, dass jede nicht prime natürliche Zahl eine Primfaktorzerlegung hat – dabei sind es meistens mehr als zwei Faktoren.
Offensichtlich sollen die dort vorgestellten Zahlen immer in zwei Primfaktoren p und q zerlegbar sein. Meine eigentliche Frage nun, weiß rsasecurity.com denn selbst die Lösung oder kann man durch irgendwelche Verfahren große Zahlen bilden, die in genau zwei Primfaktoren zerlegt werden können, diese Primfaktoren aber dennoch unbekannt sind?
Offensichtlich sollen die dort vorgestellten Zahlen immer in
zwei Primfaktoren p und q zerlegbar sein. Meine eigentliche
Frage nun, weiß rsasecurity.com denn selbst die Lösung oder
kann man durch irgendwelche Verfahren große Zahlen bilden, die
in genau zwei Primfaktoren zerlegt werden können, diese
Primfaktoren aber dennoch unbekannt sind?
Selbstverständlich ist die Lösung dem Verschlüsselnden bekannt, sonst wäre das Verfahren wohl kaum praktikabel, oder?
Selbstverständlich ist die Lösung dem Verschlüsselnden
bekannt, sonst wäre das Verfahren wohl kaum praktikabel, oder?
das nehme ich zwar auch an aber die Frage ob man Zahlen generieren kann, die garantiert zu zwei Primfaktoren faktorisieren (ohne vorherige Kenntnis dieser Faktoren) ist an sich schon interessant.
Aber woher weiß man,dass es genau 2 Faktoren sind?
Hallo,
Deine Antwort bezieht sich aber eher allgemein auf das RSA-Verfahren - da ist es klar, dass n die öffentliche Zahl ist und die Zahlen p und q (mit n = p * q) geheime Zahlen sind, die nur dem Empfänger bekannt sind…
Was ich aber eigentlich wissen wollte, ist woher rsasecurity.com sich sicher ist, dass die dort vorgestellten Zahlen in GENAU ZWEI Primzahlen p und q zerlegbar sind, wenn sie diese Zahlen selbst nicht kennen. Wenn ich eine große natürliche Zufallszahl nehme, ist es zwar garantiert, dass sie sich in Primfaktoren zerlegen lässt, aber nicht unbedingt in genau zwei.
Was ich aber eigentlich wissen wollte, ist woher rsasecurity.com sich sicher ist, dass die dort vorgestellten
Zahlen in GENAU ZWEI Primzahlen p und q zerlegbar sind, wenn
sie diese Zahlen selbst nicht kennen.
rsasecurity.com kennt die Faktorisierungen der vorgestellten Zahlen, einfach deshalb, weil sie diese Zahlen durch Multiplizierung zweier großer Primzahlen hergestellt haben, wobei sie sich selbige von einem Zufallszahlengenerator mit nachgeschaltetem probabilistischen Primzahltester erzeugen ließen. Also genau so, wie es z. B. auch in dem Programm PGP geschieht, wenn Du Dir einen Schlüssel generieren läßt. Probabilistische Primzahltest-Algorithmen können „schnell“ feststellen, ob eine gegebene Zahl prim ist (mit einer extrem kleinen Irrtumswahrscheinlichkeit).
Das Interesse von rsasecurity.com besteht nicht an den Faktorisierungen selbst, sondern darin, ob jemand in der Lage ist, die Faktorisierungen herauszufinden/berechnen zu können.
Was ich aber eigentlich wissen wollte, ist woher rsasecurity.com sich sicher ist, dass die dort vorgestellten
Zahlen in GENAU ZWEI Primzahlen p und q zerlegbar sind, wenn
sie diese Zahlen selbst nicht kennen.
Das ist doch ein Mißverständnis. So, wie ich mir das Verfahren reingezogen habe, stehen doch am Anfang zwei hinreichend große, bekannte Primzahlen (wie man diese bekommt, dürfte Dir doch klar sein). Beide multipliziert man miteinander und erhält dann die zu faktorisierende Zahl.
Wenn rsasecurity.com die Zahlen aus dem Produkt von p und q gebildet hat, ist natürlich automatisch garantiert, dass sie in genau zwei Primfaktoren zerlegt werden können, wobei diese Faktoren rsasecurity.com bekannt sind.
Was ich ursprünglich wissen wollte, ist ob rsasecurity.com die Lösung selbst kennt. Wenn ja, dann ist die Sache klar. Wenn nicht, hätte mich dann interessiert, wie sie sicherstellen, dass die vorgestellten RSA-Zahlen in genau zwei Primfaktoren zerlegbar sind. Doch ein derartiges Prüfverfahren (nicht Faktorisierung, sondern Ermittlung der Anzahl von Faktoren) ist weder mir noch meinen Kollegen bekannt
Hallo
Also ich würde davon ausgehen, dass die die Faktoren kennen. Aber allgemein funktioniert das Verfahren so, dass die Zahl n=p*q und eine weitere Zahl (z.B. e) öffentlich sind, das heisst die kann man überall abrufen. Der Trick dabei ist ja gerade, dass nur derjenige, der auch eine Zahl d kennt das Ganze wieder entschlüsseln kann.Kann mir also durchaus vorstellen, das diese Zahlen aus irgendeiner Liste kommen(z.B von der Konkurenz) und die die Lösung nicht kennen.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
