| |
 |
| Wird asymmetrische Verschlüsselung bald obsolet? |
|
|
Veröffentlicht durch maradong am Montag 08. August 2005, 18:41
Aus der wer-rechnet-mit? Abteilung
|
|
|
|
|
benz schreibt: "Wie Telepolis, die Online-Zeitschrift aus dem Heise-Verlag schreibt, haben indische Forscher ein besonders effizientes Primzahlsieb entdeckt. Damit variiert die Rechenzeit zur Primfaktorzerlegung nur noch polynomisch statt exponentiell mit der Zahl der Ziffern. Die Grundlage asymmetrischer Kryptographie ist aber die Schwierigkeit sehr große Zahlen in Primfaktoren zu zerlegen. Demnach spekuliert der Artikel darüber, ob das letzte Stündchen der asymmetrischen Verschlüsselung (verwendet u.a. in PGP/GnuPG sowie SSL) geschlagen hat."
|
|
|
|
< MPlayer benötigt neuen Server | Druckausgabe | Nach Wikipedia: 10 Dinge, die umsonst sein werden > | |
|
|
Diese Diskussion wurde archiviert.
Es können keine neuen Kommentare abgegeben werden.
|
|
|
|
|
Von Anonymer Feigling am Monday 08. August 2005, 19:25 MEW (#1)
|
|
|
|
|
Siehe dazu die Kommentare zum Artikel auf Telepolis.
Die lassen bei Heisse alle Woche mal so einen Spinner an die Tastatur.
tz tz tz...
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Details findet man unten bei Wikipedia:Primzahltest. Kurz: Ja, es gibt offenbar schon lange einen Primzahlentest in polynomialer Zeit. Nein, um unsere vertraute Kryptographie ins Wanken zu bringen muss man was anderes haben, nämlich schnelle Faktorzerlegung. (Wenn ich das richtig verstanden habe.)
|
|
|
|
|
|
|
|
|
|
|
|
|
Genau so habe ich das auch verstanden. Die Tendenz der Rechenzeit per zusätzlichem bit ist noch erstaunlich hoch. Man könnte demnach einfach auf 16kbit wechseln, und käme wieder in gescheite Bereiche.
Stimmt das so?
--
Some people drink from the fountain of knowledge, others just gurgle.
|
|
|
|
|
|
|
|
|
|
|
|
|
Also erstens war die Primfaktorzerlegung schon bisher nicht exponentiell (sondern knapp weniger), und zweitens sind ja auch andere asymmetrische Verschlüsselungsverfahren denkbar, die nicht auf Primzahlen basieren.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Em...
Die Faktorenzerlegung verhällt sich ohne diese Methode wenn ich mich recht erinnere nach 2^n-€. wo € = epsylon = sehr kleine constante und n die länge der zu analysierenden Zahl.
--
Some people drink from the fountain of knowledge, others just gurgle.
|
|
|
|
|
|
|
|
|
Von Anonymer Feigling am Monday 08. August 2005, 20:17 MEW (#4)
|
|
|
|
|
|
Ziemlich schwach dieser Artikel. Nicht nur, dass das Faktorisierungsproblem nicht die einzige Basis für PublicKey Kryptographie ist (RSA basiert darauf, ElGamal z.B. auf dem Diskreten Logarithmus Problem), auch für RSA ist dieses (zugegebenermassen interessante) Verfahren keine Gefahr, wie der tp-Autor selbst ja auch am Ende des Artikels andeutet.
Denn was im eigentlichen Artikel sehr verquer formuliert wurde, hat der Schreiber dieses Newseintrags völlig falsch interpretiert:
Richtig ist: "Die Grundlage asymmetrischer Kryptographie ist aber die Schwierigkeit sehr große Zahlen in Primfaktoren zu zerlegen."
Aber genau dort ist der Haken - das Verfahren liefert gar keine Zerlegung, es liefert einen *Test*, ob eine Zahl prim ist. Und dafür ein deterministisches Verfahren zu haben, das in polynomialer Zeit arbeitet ist zwar neu und schön, aber Primzahl-*Tests* (bisher probabilistische), die effektiv arbeiten, sind schon lange bekannt - ohne sie wäre RSA gar nicht möglich, da man ja erstmal 2 große Primzahlen *finden* muss.
In Anbetracht der sonst eigentlich guten Artikel bei Symlink wäre eine Korrektur dieses haarsträubenden Eintrags stark zu empfehlen :)
|
|
|
|
|
|
|
|
|
|
|
Von Anonymer Feigling am Tuesday 09. August 2005, 12:23 MEW (#7)
|
|
|
|
|
Extren schwach. Vorallem viel zu spät. Der "Primes in P" Artikel ist schon UR-Alt.
Ich würde auch sagen Symlink sollte da seinen Kommentar korrigieren, das ist ja Haarsträubend wenn man am Morgen solch eine Schlagzeile liest und dann kommt ein Jahre alter Artikel zum Vorschein
*schweiz von der Stirn wisch*
|
|
|
|
|
|
|
|
|
Von Anonymer Feigling am Tuesday 09. August 2005, 13:33 MEW (#8)
|
|
|
|
|
Dazu kommt noch, daß heise ohnehin seit langer
Zeit bereits recht unseriös ist/arbeitet/gilt,
und dies ein verzweifelter Versuch zu sein
scheint, das mittlerweile obsolete symlink.ch
noch zu retten.
Ich glaube nicht an Medien.
|
|
|
|
|
|
