Double Add Algorithmus ECC

Neue Frage »

Kelloggz Auf diesen Beitrag antworten »
Double Add Algorithmus ECC
Meine Frage:
Ich habe ein Problem. Ich habe eine 160 bit Primzahl. Nun soll k*P mit Hilfe des Double-Add Algorithmus berechnet werden. Die Frage ist nun für welches k müssen wie viele Punktadditionen und wie viele Punktverdopplungenmüssen (i) im Durchschnitt,
(ii) im besten Fall, und (iii) im schlechtesten Fall berechnet werden?

Meine Ideen:
Ich dachte zunächst ok, 16bit=> 160 mal 11111... wäre z.b. der schlechteste Fall, also die meisten Operationen. Aber k kann ja p+1+2sqrt(p) groß sein. Ist das der richtige weg??
soase Auf diesen Beitrag antworten »

So wie du es schreibst verstehe ich die AUfgabe nicht.
Was macht die Primzahl? Ich vermute mal, sie gibt die Mächtigkeit des Körpers an über dem gearbeitet wird?
Zitat:
Die Frage ist nun für welches k müssen wie viele Punktadditionen

Diesen Satz versteh ich nicht. Das erweckt den Eindruck als würde nach einem konkreten k gesucht werden. Das tust du aber nicht.
Wie kommst du von 16 bit auf 160 mal 1111.. (was auch immer letztere Zahl sein soll)?
Zitat:
Aber k kann ja p+1+2sqrt(p) groß sein.

Ich vermute du spielst hier auf die max. Mächtigkeit von an.
Warum kann k nicht auch größer sein?
(im Übrigen ist die Ordnung von P kleiner als die Mächtigkeit der Gruppe, wobei die C_i zklische Gruppe der Ordnung i, p kein teiler von m und n eine positive natürliche zahl)

Ach ja und was genau ist für dich der Double-Add Algorithmus?
 
 
Kelloggz Auf diesen Beitrag antworten »

also habe grade gesehen dass das 16 bit von mir ein Fehler war. Sollte 160 bit heißen.

Die genaue Fragestellung lautet:
Wir betrachten eine 160 bit Primzahl p und wollen k · P (P ist ein Punkt auf der elliptischen Kurve)mit Hilfe des Double-And-Add Algorithmus berechnen.
a) Wie viele Punktadditionen und wie viele Punktverdopplungenmüssen (i) im Durchschnitt,
(ii) im besten Fall, und (iii) im schlechtesten Fall berechnet werden?
b) Welche Werte von k sind der “beste Fall” und der “schlechteste Fall”?

Sry wenns von mir bissl falsch ausgedrückt war.
Also ich weiß ja, dass k aus dem Bereich {2,3.....ord(e)} e=elliptische Kurve gewählt wird. Die Ordnung von e ist ja zwischen:
p+1-2sqrt(p)=<e=<p+1+2sqrt(p). Da wollte ich ungefähr ansetzen.

Der Double-Add:
http://en.wikipedia.org/wiki/Elliptic_cu..._multiplication genauso wie er hier steht
Kelloggz Auf diesen Beitrag antworten »

Zitat:
im Übrigen ist die Ordnung von P kleiner als die Mächtigkeit der Gruppe


Die Ordnung des Punktes teilt die Gruppenordnung. Das heißt die Ordnung des Punktes P kann auch gleich der Ordnung der Gruppe sein. Also quasi ein Generator.
soase Auf diesen Beitrag antworten »

Zitat:
Die Ordnung des Punktes teilt die Gruppenordnung. Das heißt die Ordnung des Punktes P kann auch gleich der Ordnung der Gruppe sein. Also quasi ein Generator.

Schön, du kennst den Satz von Lagrange. Leider hast du nicht weiter gelesen, ich habe doch darunter angegeben wie aussieht (auch wenn ihr das garantiert noch nicht bewiesen habt) und dass es insbesondere nicht zyklisch ist.
Und eine elliptische Kurve an sich hat keine Ordnung (es ist auch keine Gruppe), sondern die Menge aller Punkte auf der Kurve aus dem Körper ist eine Gruppe und hat eine Ordnung.
Zitat:
Also quasi ein Generator.

Die deutsche Bezeichnung ist Erzeuger.

Zitat:
Also ich weiß ja, dass k aus dem Bereich {2,3.....ord(e)} e=elliptische Kurve gewählt wird

Woher weißt du das? Habt ihr das so festgesetzt? (ich hoffe ja)

Weiß man noch was über P, z.B. ?

Aber zur eigentlichen Aufgabe:
Überleg dir mal wieviele Punktadditionen und Verdoplungen du z.B. für 32P und 31P brauchst.
Kelloggz Auf diesen Beitrag antworten »

32*P=>32bin= 100000*P dh. da brauche ich 5 mal eine Punktverdopplung

31*P=> 31bin= 11111*P dh. 4 Verdopplungen und 4 Additionen.

Über P weiß man sonst gar nix. Wenn die Aufgabenstellung so gemeint war das k eine 160 bit Zahl ist, dann wäre doch der schlechteste Fall: (iii)160 mal die 1, also 159 ADD und 159 DOUBLE,
(ii) der beste Fall:???,
(i) Durchschnitt=80mal 1 und 80 mal 0: 79 ADD und 159 Double
Mystic Auf diesen Beitrag antworten »

Wie der Threadersteller schon geschrieben hat, ist alles was man weiß (und hier auch wissen muss!), dass k eine natürliche Zahl ist, für die gilt, woraus folgt, dass ihre Bitlänge mit großer Wahrscheinlichkeit ebenfalls 160 (oder nicht viel kleiner) ist... Die Struktur der elliptischen Gruppe ist in diesem Zusammenhang m.E. nicht hilfreich (davon mal abgesehen, dass m sogar Teiler von p-1 sein muss!)...
soase Auf diesen Beitrag antworten »

Erstmal eine große Korrektur (offenbar ist mir zu heiß oder so..)
Zitat:
Leider hast du nicht weiter gelesen, ich habe doch darunter angegeben wie aussieht (auch wenn ihr das garantiert noch nicht bewiesen habt) und dass es insbesondere nicht zyklisch ist.

Das Gegenteil ist wahr es gibt zyklische , in obiger Darstellung falls m=1.

Ok wir sind uns einig dass die Aufgabenstellung sehr schwammig ist.
Der beste fall ist ist definitiv k=2, der (ii) stimme ich zu.
bei der (i) sehe ich es etwas anders: auch 2^100 ist eine 160 bit-Zahl, die aber deutlich weniger als 159 Verdopplungen braucht.
Ich fürchte hier ist etwas Wahrscheinlichkeitsrechnung angesagt.

Vielleicht sollte man noch erwähnen, dass wieder in der Größenordnung 160 bit ist.
Kelloggz Auf diesen Beitrag antworten »

eieiei, mir geht die Aufgabe da ein wenig auf die Nerven smile . Aber schonmal Danke für eure Hilfe.

Also schlechtester Fall ist 160 mal die 1 wegen 159 Double und 159 ADD?
Mystic Auf diesen Beitrag antworten »

je 160... Augenzwinkern Siehe eigene Quelle von oben:

Zitat:

* Q = 0
* for i from m to 0 do
* Q := 2Q (using point doubling)
* if di = 1 then Q := Q + P (using point addition)
* Return Q
Kelloggz Auf diesen Beitrag antworten »

jo gebe dir recht smile ,
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »