DSA oder RSA

Jens Ruehmkorf ruehmkorf at informatik.uni-koeln.de
So Dez 15 14:53:28 CET 2002


Hallo Aristoteles, hallo Leute!

On Fri, 13 Dec 2002, A. Pagaltzis wrote:
> * Jens Ruehmkorf <ruehmkorf at informatik.uni-koeln.de> [2002-12-13 18:30]:
> > Immerhin hat man fuer das Problem, zu testen, ob eine Zahl
> > prim ist, im August 2002 einen Polynomzeit-Algorithmus
> > veroeffentlicht.
>
> Selbst geometrische Zeit ist aber immer noch eine bedeutende Hürde
> beim Bruteforce, und ausserdem ist die Antwort auf die Frage, ob eine
> Zahl prim ist, wesentlich weniger hilfreich als es eine Liste ihrer
> Faktoren wäre.
>
> Was natürlich alles nichts an der grundlegenden Unsicherheit ändert,
> die die Komplexität einer Reversion der gängigen Falltürfunktionen
> betrifft.

Ich verstehe Deinen Einwand nicht.

> > Soweit ich weiss, hat man von keinem der beiden Verfahren > bisher
> feststellen koennen, dass sie unsicher sind.
>
> Jein. DSA kann unsicher sein, wenn man keinen "echten"
> Zufallszahlengenerator hat - deswegen hat sich der PuTTY-Author sehr
> lange geweigert, DSA in PuTTY zu unterstützen (Win32 hat kein
> /dev/urandom).

Ja, das stimmt. Der Random-Generator ist wichtig bei vielen Algorithmen.
Dein Einwand, dass *deswegen* DSA unsicher sei, ist hoffentlich nicht
ernst gemeint.

Das Thema der Erzeugung von "zufaelligen" Zahlen ist hinlaenglich
untersucht und man schreibt sich einfach einen Generator mit den
statistischen Eigenschaften, passend zur Anforderung, selbst (siehe z.B.
ran1 usw. aus Knuth, TAOCP, "Numerical Recipes").

> Bis auf diese Fussangel hat sich der Algorithmus als solcher jedoch
> bisher als standfest erwiesen.

Es gibt (bzw. gab) fuer das anfangs veroeffentlichte Verfahren DSA in der
Tat echte Fussangeln: DSA berechnet den diskreten Algorithmus fuer
bestimmte Untergruppen des endlichen Koerpers {\mathbb Z}_p fuer eine
Primzahl p. Fuer mache "trapdoor"-Primzahlen p kann man DSA-Schluessel
leicht knacken. Diese Primzahlen sind aber selten und koennen bei der
Schluessel-Erzeugung ausgelassen werden (wie es auch gemacht wird).
Nachzulesen in [0].

Hm. Naja, die Frage nach dem Anwendungsbezogenen Vergleich wuerde mich
immer noch interessieren, fuer die Nachfolger bzw. AES-Kandidaten konnte
man ja so einen Vergleich in der iX lesen. Aber fuer {D,R}SA?

Noch'n schoenen Sonntag,
Jens

[0] Smid, Branstad; "Response to comments on the NIST proposed Digital
Signature Standard"; Advances in Cryptology - Crypto '92

--
ruehmkorf at informatik dot uni hyphen koeln dot de




Mehr Informationen über die Mailingliste Linux-Users