Hi, nach dem Vortrag zu GnuPG neulich kam bei den Diskussionen die Frage nach den unterschiedlichen Primzahlentest auf und wie GnuPG sich seine Primzahlen beschafft. Bin grade nochmal zufällig drüber gestoßen. Es gibt mehre schnelle Tests die aber False-positives liefern und unterschiedliche "Sicherheit" haben: Fermatscher Primzahltest, Solovay-Strassen-Test & Miller-Rabin-Test Es gibt seit 2002 jedoch auch einen Test der in Polynomialzeit garantiert sagt, ob eine Zahl prim ist oder nicht: AKS-Methode Numberphile erklärt die Tests: http://youtu.be/jbiaz_aHHUQ http://youtu.be/HvMSRWTE2mI
Hier findet man dann wie GnuPG das konkret handhabt: [1] Sie erzeugen zuerst einen Pool an kleineren Primzahlen (mit dem Algorithmus von Lim & Lee, den man aber nicht kennen muss) und errechnen daraus dann mögliche große Primzahlen die sie zuerst gegen kleine Primzahlen testen, dann mit Fermat und schließlich mit 5 Runden Rabin-Miller testen. Die Zahlen sind also nicht garantiert Prim, aber es ist extrem unwahrscheinlich, das nicht. Es ist wohl auch nicht klar, ob das den Schlüssel überhaupt nennenswert schwächt. [2] Lg, Michi [1]: http://www.gnupg.org/documentation/manuals/gcrypt/Prime_002dNumber_002dGenerator-Subsystem-Architecture.html#fn-1 [2]: hier diskutieren GnuPG-Entwickler darüber: http://www.gossamer-threads.com/lists/engine?do=post_view_flat;post=55353;page=1;sb=post_latest_reply;so=ASC;mh=25;list=gnupg -- Michael F. Schönitzer Magdalenenstr. 29 80638 München Mail: [email protected] Jabber: [email protected] Tel: 089/152315 - Mobil: 017657895702
signature.asc
Description: This is a digitally signed message part
-- Abmelden und Archiv: https://lists.frodev.org/mailman/listinfo/opensourcetreffen-discuss Tipps zu Listenmails: http://wiki.documentfoundation.org/Netiquette/de Alle E-Mails an diese Liste werden unlöschbar öffentlich archiviert
