Double Add Algorithmus ECC

01.05.2012, 14:32

Kelloggz

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??

01.05.2012, 14:51

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 $\begin{eqnarray*} E(\mathbb F_p) \end{eqnarray*}$ an.
Warum kann k nicht auch größer sein?
(im Übrigen ist die Ordnung von P kleiner als die Mächtigkeit der Gruppe, $\begin{eqnarray*} E(\mathbb F_p) \cong C_m \times C_{mn} \end{eqnarray*}$ 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?

01.05.2012, 15:02

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

01.05.2012, 15:05

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.

01.05.2012, 15:28

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 $\begin{eqnarray*} E(\mathbb F_p) \end{eqnarray*}$ 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 $\begin{eqnarray*} E(\mathbb F_p) \end{eqnarray*}$ die Menge aller Punkte auf der Kurve aus dem Körper $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ 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. $\begin{eqnarray*} P \neq \mathcal{ O} \end{eqnarray*}$ ?

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

01.05.2012, 15:56

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

01.05.2012, 16:02

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 $\begin{eqnarray*} k < p+1 +2 \sqrt p \end{eqnarray*}$ 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!)...

01.05.2012, 16:10

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 $\begin{eqnarray*} E(\mathbb F_p) \end{eqnarray*}$ aussieht (auch wenn ihr das garantiert noch nicht bewiesen habt) und dass es insbesondere nicht zyklisch ist.

Das Gegenteil ist wahr es gibt zyklische $\begin{eqnarray*} E(\mathbb F_p) \end{eqnarray*}$ , 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 $\begin{eqnarray*} p+1+2\sqrt{p}<2^160+2^{81} \end{eqnarray*}$ wieder in der Größenordnung 160 bit ist.

01.05.2012, 16:21

Kelloggz

Auf diesen Beitrag antworten »

eieiei, mir geht die Aufgabe da ein wenig auf die Nerven smile