RSA - Reichen starke Pseudoprimzahlen?

nici
Erstie
Erstie
Beiträge: 22
Registriert: 30. Sep 2008 16:45

RSA - Reichen starke Pseudoprimzahlen?

Beitrag von nici »

Hallo,

beim RSA müssen wir ja Primzahlen erstellen. Aber es dauert ja ewig zu testen ob so große Zahlen wirklich Primzahlen sind. Reicht es da Zahlen zu nehmen die mit einer Wahrscheinlichkeit von ca. (1/2)^1000 keine Primzahlen sind?

Gruß,
nici

ice-breaker
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 216
Registriert: 14. Okt 2008 17:56

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von ice-breaker »

wenn die "Primzahl" keine Primzahl ist, dann funktioniert RSA nicht mehr ;)

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Osterlaus »

ice-breaker hat geschrieben:wenn die "Primzahl" keine Primzahl ist, dann funktioniert RSA nicht mehr ;)
Zufällig habe ich gerade bei Wikipedia gelesen, dass RSA auch bei Nicht-Primzahlen funktionieren kann. Ob das stimmt und ob die Verschlüsselung dann noch sicher ist, weiß ich aber nicht ;)

ice-breaker
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 216
Registriert: 14. Okt 2008 17:56

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von ice-breaker »

Würde mich mittlerweile auch mal interessieren ob das ok ist, denn der eingebaute Primzahlentest von BigInteger arbeitet schnell und hat eine sehr sehr geringe Fehlerwahrscheinlichkeit, mein Test dauert Ewigkeiten, ich habe ihn bei großen Zahlen noch nicht terminieren sehen.

Und den AKS-Primzahltest zu implementieren, kann ja denke ich nicht Sinn der Sache sein.

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Blub »

hey,

du darfst dir in Java eine Primzahl mit dem PseudoPrimzahlgenerator generieren lassen und kannst davon ausgehen das der Java interne Test korrekt war.

Einen eigenen Test muss man imho nicht schreiben. In der Aufgabenstellung steht ja, das ihr diese Lib verwenden dürft und diese hat ja bereits einen Test implmenetiert. Ein zweiter von euch programmierter Test wäre dann nur mehr Arbeitsaufwand eigentlich.



Zur eigenen Überprüfung kannst du deine Ausgabe doch einfach so gestalten:
public Key:
private Key:
input m:
encrypted m:
decrypted m:

so siehst du ja wenn input m == decrypted m, dann hat der RSA korrekt gearbeitet. Die Chance das der Test mal fehlschlägt und wirklich keine Pseudoprimzahl generiert wird ist so gering, das sich hier kein weiterer Test lohnen würde. Und gute Tests zu implementieren dauert auch seine Zeit.
AKS ist schon recht strange. Als Alternative gäbe es noch bis 5-10 Mio das Sieb verwenden, und ab 5-10 Mio dann mit Miller-Rabin zu testen. Das habe ich letztes Jahr programmiert, das war aber auch da nicht notwendig, also würde ich hier erstmal davon ausgehen das es hier auch nicht nötig ist.



Christian
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Christoph-D »

Blub hat geschrieben:Und gute Tests zu implementieren dauert auch seine Zeit.
AKS ist schon recht strange. Als Alternative gäbe es noch bis 5-10 Mio das Sieb verwenden, und ab 5-10 Mio dann mit Miller-Rabin zu testen.
Miller-Rabin ist aber wieder ein probabilistischer Test* und damit eigentlich keine Alternative zum AKS, oder?

* Wenn ich das richtig sehe, fehlt für die deterministische Variante bisher ein Korrektheitsbeweis.
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Blub »

hey,

eine richtige Alternative zu AKS ist es nicht, wenn man betrachtet das AKS deterministisch ist und Miller-Rabin "nur" probabilistisch.
Von der Laufzeit her sollte Miller-Rabin aber besser sein, nur leider halt nicht deterministisch. Wenn ich wählen müsste würde ich natürlich auch lieber den AKS nehmen, aber dieser ist für die meisten hier doch recht schwer zu programmieren imho. Daher wäre eine "Alternative" auf Miller-Rabin zurückzugreifen, wenn man denn einen Primzahltest programmieren will. (wenn man die Zeit hat ist es sicherlich eine nette Übung auch man sowas implementiert zu haben)


Christian



//€ hier stand vorher was nicht ganz korrektes, hatte bei den Laufzeiten was durcheinandergebracht, daher stark editiert
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von zeri »

Blub hat geschrieben:eine richtige Alternative zu AKS ist es nicht, wenn man betrachtet das AKS deterministisch ist und Miller-Rabin "nur" probabilistisch.
"nur" probabilistisch ist gut ^^

Wenn man mal bei Wikipedia nachkuggt, ist die Wahrscheinlichkeit dafür, dass der miller-rabin-test eine nichtprimzahl als prim bezeichnet < 1/4 für für jede runde die man mit einer zufällig gewählten Zahl fährt. Wenn du nun also 20 zufällig gewählte Zahlen nimmst und mit jeder den miller-rabin-test einmal durchführst, ist die wahrscheinlichkeit für eine falsche Aussage < 1/(4**20) irgendwas wo 12 0en hinter dem komma. Ich würde jetzt gerne einen Vergleich anbringen, in dem Meteore geflogt von Blitzen in deinen kopf einschlagen, finde aber keine statistischen daten dazu.

die 6 richtigen im lotto sind laut wiki 1000mal so wahrscheinlich.

*EDIT* letzter edit war bullshit
Zuletzt geändert von zeri am 4. Jan 2010 20:25, insgesamt 1-mal geändert.
don't get even, get odd!

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Blub »

daher setzte ich es in "nur" ;) (ok, das es keine Alternative ist war vllt etwas doof formuliert, gebe ich zu ^^) Der Test ist nahezu standard, aber ein deterministischer Test ist trotzalledem imho besser (gut, ausser die Laufzeit ist total schlecht ^^). Nur allerdings ist AKS beispielsweise etwas langsamer als Miller-Rabin. Kommt daher wohl immer darauf an worauf man mehr wert legt. Ich würde AKS wählen. (gut, ausser ich muss es selber programmieren, dann würde ich definitiv auch Miller-Rabin wählen :p)



//€ was stand denn im letzten Edit? :p
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von zeri »

Blub hat geschrieben:daher setzte ich es in "nur" ;) (ok, das es keine Alternative ist war vllt etwas doof formuliert, gebe ich zu ^^) Der Test ist nahezu standard, aber ein deterministischer Test ist trotzalledem imho besser (gut, ausser die Laufzeit ist total schlecht ^^). Nur allerdings ist AKS beispielsweise etwas langsamer als Miller-Rabin. Kommt daher wohl immer darauf an worauf man mehr wert legt. Ich würde AKS wählen. (gut, ausser ich muss es selber programmieren, dann würde ich definitiv auch Miller-Rabin wählen :p)



//€ was stand denn im letzten Edit? :p

Das ist total fies von dir weiste es war schwer genug den miller rabin zu implementierten ... und der AKS ist im pseudocode schon hässlich.
Ich wette, dass wegen dem kram den du schreibst einige arme studies jetzt da sitzen und den rest der Woche damit verschwenden aks zu implementieren und sich dann wundern, dass die erzeugung eines 140bit moduls irgendwie 20 minuten dauert. </irony>

Der letzte edit:
Ich hatte mit 2 konsekutiven Gewinnen im Lotto (6 richtige aus 49) argumentiert. Das war aber etwas zu unwahrscheinlich.
don't get even, get odd!

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: RSA - Reichen starke Pseudoprimzahlen?

Beitrag von Blub »

zeri hat geschrieben:
Blub hat geschrieben:daher setzte ich es in "nur" ;) (ok, das es keine Alternative ist war vllt etwas doof formuliert, gebe ich zu ^^) Der Test ist nahezu standard, aber ein deterministischer Test ist trotzalledem imho besser (gut, ausser die Laufzeit ist total schlecht ^^). Nur allerdings ist AKS beispielsweise etwas langsamer als Miller-Rabin. Kommt daher wohl immer darauf an worauf man mehr wert legt. Ich würde AKS wählen. (gut, ausser ich muss es selber programmieren, dann würde ich definitiv auch Miller-Rabin wählen :p)



//€ was stand denn im letzten Edit? :p

Das ist total fies von dir weiste es war schwer genug den miller rabin zu implementierten ... und der AKS ist im pseudocode schon hässlich.
Ich wette, dass wegen dem kram den du schreibst einige arme studies jetzt da sitzen und den rest der Woche damit verschwenden aks zu implementieren und sich dann wundern, dass die erzeugung eines 140bit moduls irgendwie 20 minuten dauert. </irony>

Der letzte edit:
Ich hatte mit 2 konsekutiven Gewinnen im Lotto (6 richtige aus 49) argumentiert. Das war aber etwas zu unwahrscheinlich.
yy. Das solltest du auch machen :p
Also wenn du keinen AKS gemacht hast gibts natürlich 0 Punkte für dich :p

Ne scherz. Also ich würde eh nicht soooviel Zeit in die Programmieraufgabe stecken. Imho sind die anderen Übungen wichtiger. Ihr werdet in der Klausur wohl keine Aufgabe bekommen ala "proggen sie mal eben xyz in einer Sprache ihrer Wahl. Whitespace bevorzugt". Die anderen Aufgaben sind schon wahrscheinlicher.

Und ja, der AKS Pseudocode ist schon recht strange, das zu implementieren ist schon nicht einfach. Wer es schafft, respect. Mich hat das im letzten Jahr abgeschreckt, gerade weil meine Java Kenntnisse da doch noch recht minimal waren (war da noch Mathematiker und gerade erst GDI I gehört) und der Miller-Rabin um einiges einfacher aussah ^^
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

Antworten

Zurück zu „Archiv“