FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Schwerpunkte (HS)

Knacken von EKKs?

Knacken von EKKs? 2007-10-25 13:57
Popcorn
Mir ist bei diesem Verfahren eines wirklich noch nicht klar. Es geht im wesentlichen um die Frage, welches k denn die Gleichung für Q = kP erfüllt, wobei Q und P Punkte auf der elliptischen Kurve sind. Der Brute-Force-Angriff geschieht darüber, die ks einfach durchzuprobieren. Das soll lange dauern. Nun kennt der rechtmäßige Empfänger k bereits, muss also nicht probieren, sondern kann es direkt ausrechnen.

Mal abgesehen davon, dass der Angreifer im jeden Schritt kurz kP mit Q vergleichen muss, sehe ich nicht, an welche Stelle dies nun langsamer für ihn ist. Die Multiplikation ist in diesem System wie gewohnt über die wiederholte Addition definiert. Beide tun also das Gleiche. In einem dezimalen oder binären System verstehe ich das ja noch. Für x10 im dezimalen System hänge ich einfach eine Null an, da kann man viel sparen. Aber wie funktioniert das bei EKKs? Funktioniert das überhaupt darüber oder habe ich noch etwas wesentliches übersehen?

RE: Knacken von EKKs? 2007-10-25 22:58
garou
[strike]Nur daß eine Multiplikation keine O(n)-, sondern eine O(1)-Operation setzt; wo Bob nur eine Multiplikation durchführt, muß Eve k machen, was bei Z_2^(keylength) halt durchaus eine recht große Zahl sein kann. Plus in der Praxis noch den overhead, zu erkennen, daß man tatsächlich das richtige k hat. Fröhliches ausprobieren.[/strike]
Moment, ich les' das lieber nochmal nach…