-
Mal ne Frage
Autor: QuickNick 13.10.16 - 09:50
Kurze Zwischenfrage:
Welche Länge haben denn die verwendeten Primzahlen ungefähr? Mich interessiert nur die ungefähre Größenordnung. Werden die Primzahlen tatsächlich bei der Erstellung der Schlüssel berechnet oder irgendwo ausgelesen?
Schöne Grüße -
Re: Mal ne Frage
Autor: ipodtouch 13.10.16 - 12:23
1024 bit - damit kannst du es dir selbst ausrechnen ;)
-
Re: Mal ne Frage
Autor: Mingfu 13.10.16 - 12:31
Die Größe der Primzahlen steht doch im Artikel: 1024 bit. Das sind also rund 300 Dezimalstellen.
Klassischerweise werden diese Primzahlen beim Erstellen der Schlüssel live erzeugt. Allerdings braucht man dort einen Trick, denn bei Zahlen dieser Größenordnung kann man nicht wirklich beweisen, ob es sich um eine Primzahl handelt. Vielmehr kann man nur die Wahrscheinlichkeit dafür beliebig groß machen. Dazu wählt man einen entsprechenden Zahlenkandidaten zufällig aus und wendet dann probabilistische Primzahltests an, die bei jedem Durchgang die Wahrscheinlichkeit dafür weiter senken können, dass eine zusammengesetzte Zahl all diese Durchgänge besteht. (Vereinfacht kann man sich das wie Probedivisionen durch kleine Primfaktoren 2, 3, 5, 7, 11, 13, ... vorstellen. Die Wahrscheinlichkeit, dass es sich bei einer Zahl, die bei all diesen Divisionen einen Rest hinterlässt, um eine Primzahl handelt, steigt immer weiter an bzw. die Wahrscheinlichkeit, dass die Zahl zusammengesetzt ist, nimmt immer mehr ab.)
Eine Primzahl zu finden, die eine Hintertür hat, mit der man dann den diskreten Logarithmus innerhalb der durch die Primzahl definierten Gruppe leichter berechnen kann (also das, um was es in dem Artikel eigentlich geht), ist allerdings komplizierter. -
Re: Mal ne Frage
Autor: QuickNick 14.10.16 - 07:50
Vielen Dank für die präzise Antwort. Mir war das neu, ich ging immer von genauen Primzahlen aus. Kannst du ein Beispiel für einen solchen probalistischen Primzahltest nennen?
Für mich stellt sich eine weitere Frage: wenn ich für private Zwecke einen 4096 er Schlüssel erzeuge, geht das auf meinen Laptop gefühlt "schnell". Warum geht man nicht gleich auf 8192 oder höher? Die Sicherheit steigt doch deutlich an und das mehr an Warten überbrücke ich indem ich mir einen Kaffee hole.
Viele Grüße
1 mal bearbeitet, zuletzt am 14.10.16 07:50 durch QuickNick. -
Re: Mal ne Frage
Autor: Mingfu 14.10.16 - 10:16
QuickNick schrieb:
--------------------------------------------------------------------------------
> Kannst du ein Beispiel für einen solchen probalistischen Primzahltest nennen?
Ein einfacher Test wäre der Fermatsche Primzahltest. Real wird eher der Miller-Rabin-Test verwendet werden.
> Für mich stellt sich eine weitere Frage: wenn ich für private Zwecke einen
> 4096 er Schlüssel erzeuge, geht das auf meinen Laptop gefühlt "schnell".
> Warum geht man nicht gleich auf 8192 oder höher?
Das Problem ist nicht nur die Erzeugung des Schlüssels. Das ist vielfach eine einmalige Angelegenheit, dafür würde man auch mehr Zeit in kauf nehmen. Mit längeren Schlüsseln wird aber auch die Ver- bzw. Entschlüsselung langsamer (der Aufwand steigt mindestens quadratisch bezüglich der Länge der Schlüssel). Und das ist, gerade für größere Server, dann nicht mehr egal. Denn dann braucht man mehr Rechenleistung und gleichzeitig steigt auch die Gefahr, für DoS-Angriffe verwundbar zu werden, indem massenhaft Verbindungswünsche für verschlüsselte Verbindungen eingehen, die der Server aufwendig entschlüsseln muss und somit überausgelastet wird.
Privat kann man in der Regel durchaus auch etwas längere Schlüssel akzeptieren - wartet man eben etwas länger. Im Großmaßstab spielt aber die Performance eine sehr entscheidende Rolle, gerade bei klassischer auf Primzahlen basierender asymmetrischer Kryptographie.



